Основы алгебры логики

Для анализа и синтеза схем в ЭВМ при алгоритмизации и программировании решения задач широко используется математический аппарат алгебры логики.

Алгебра логики - это раздел математической логики, значениявсех элементов (функций и аргументов) которой определены в двухэлементном множестве: 0 и 1. Алгебра логики оперирует с логическими высказываниями.

Высказывание - это любое предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. При этом считается, что высказывание удовлетворяет закону исключенного третьего, т.е. каждое высказывание или истинно, или ложно и не может быть одновременно и истинным, и ложным.

Пример 4.11. Высказывания: "Сейчас идет снег"- это утверждение может быть истинным или ложным; "Вашингтон столица США" истинное утверждение; "Частное от деления 10 на 2 равно 3" -ложное утверждение.

В алгебре логики все высказывания обозначают буквами а, b, с и т.д. Содержание высказываний учитывается только при введении их буквенных обозначений, и в дальнейшем над ними можно производить любые действия, предусмотренные данной алгеброй. Причем если над исходными элементами алгебры выполнены некоторые разрешенные в алгебре логики операции, то результаты операций также будут элементами этой алгебры.

Простейшими операциями в алгебре логики являются операции логического сложения (иначе, операция ИЛИ, операция дизъюнкции) и логического умножения (иначе, операция И, операция конъюнкции). Для обозначения операции логического сложения используют символы + или V, а логического умножения - символы * или L .

Правила выполнения операций в алгебре логики определяются рядом аксиом, теорем и следствий.

В частности, для алгебры логики выполняются законы:

1) сочетательный:

(a + b) + с = а + ( b + с);

(а * b) * с = а * (b * с);

2) переместительный:

а + b = b + а;

а * b = b * а;

3) распределительный:

а* (b + с) = a * b + а* с;

а+ b * с= а * b + а* с.

Справедливы соотношения:

a+a=a; a+b=b, если а≤b;

a*a=a; a*b=a,если a≤b;

a+a*b=a; a+b=b,если a≥b

a+b=a, если а≥b; и др.

Наименьшимэлементом алгебры логики является 0, наибольшимэлементом-1.

В алгебре логики также вводится еще одна операция- операция отрицания (иначе, операция НЕ, операция инверсии), обозначаемая чертой над элементом.

По определению: a+ā=1,a* ā=0, 0=1, 1=0.

Справедливы, например, такие соотношения: а=а, a+b=а*b, a*b=а+b.

Функция в алгебре логики это алгебраическое выражение, содержащее элементы алгебры логики а, b, с ..., связанные между собой операциями, определенными в этой алгебре.

Пример 4.12. Примеры логическихфункций.

f(a,b,c) = ā + a*b*ń + a+c;

f(a,b,c) = a*b + а*с +a*b*c

Согласно теоремам разложения функций на конституэнты (составляющие) любая функция может быть разложена на конституэнты "1":

f(a)=f(1)*a+f(0)* ā;

f(a,b)=f(1,b)*a+f(0,b)*ā=f(1,1)*a*a+f(1,0)*a*b+f(0,1)*ā*b+f(0,0)*ā*b, (2)

и т.д.

Эти соотношения используются для синтеза логических функций и вычислительных схем.