Для анализа и синтеза схем в ЭВМ при алгоритмизации и программировании решения
задач широко используется математический аппарат алгебры логики.
Алгебра логики— это раздел математической логики, значения всех элементов (функций и аргументов) которой определены в двухэлементном
множестве: 0 и 1. Алгебра логики оперирует с логическими высказываниями.
Высказывание— это любое предложение, в отношении которого имеет
смысл утверждение о его истинности или ложности. При этом считается,
что высказывание удовлетворяет закону исключенного третьего, т.е. каждое высказывание или истинно, или ложно и не может быть одновременно и истинным, и ложным.
Пример 4.11.Высказывания: "Сейчас идет снег" — это утверждение может быть истинным или ложным; "Вашингтон — столица США" — истинное утверждение;
"Частное от деления 10 на 2 равно 3" — ложное утверждение.
В алгебре логики все высказывания обозначают буквами а, Ь, с и т.д. Содержание высказываний учитывается только при введении их буквенных обозначений, и в дальнейшем над ними можно производить любые действия, предусмотренные данной алгеброй. Причем если над исходными элементами алгебры выполнены некоторые разрешенные в алгебре логики операции, то результаты операций также будут элементами этой алгебры.
Простейшими операциями в алгебре логики являются операции логического
сложения (иначе, операция ИЛИ, операция дизъюнкции) и логического умножения (иначе, операция И, операция конъюнкции). Для обозначения операции логического сложения используют символы + или V, а логического умножения — символы * или Λ.
Правила выполнения операций в алгебре логики определяются рядом аксиом, теорем
и следствий.
В частности, для алгебры логики выполняются законы:
1) сочетательный:
(а + Ь) + с = а + (b + с);
(а * Ь) * с = а * (Ъ * с);
2) переместительный:
а + Ь = Ь + а;
а * Ь = Ь * а;
3) распределительный:
а* (Ь + с)=а* b + а* с;
а+Ь* с=а* b + а* с
Справедливы соотношения:
а + а = а a + b=b, если а ≤ Ь;
а* а = а; а*b=а, если а ≤ Ь;
а + а* b = a; a + b=b, если а ≥ Ь
а + Ь = а, если а ≥ Ь; и др,
Наименьшим элементом алгебры логики является 0, наибольшим элементом — 1.
В алгебре логики также вводится еще одна операция — операция отрицания
(иначе, операция НЕ, операция инверсии), обозначаемая чертой над элементом.
По определению: а + а = 1, <з*а=0, 0-1, 1=0.
Справедливы, например, такие соотношения: а — а, а + b = а * 5, а* Ъ = а + Ъ.
Функция в алгебре логики — это алгебраическое выражение, содержащее элементы алгебры логики <з, Ь, с ..., связанные между собой операциями, определенными в этой алгебре.
Пример 4.12.Примеры логических функций:
f(a,b,c) = а + а*b*с + а+с;
f(a,b,c)=а*b + а*с + a*b*с
Согласно теоремам разложения функций на конституэнты (составляющие) любая
функция может быть разложена на конституэнты "1":
и т.д.
Эти соотношения используются для синтеза логических функций и вычислительных
схем.