Элементы алгебры логики
Алгебра логики — это раздел математической логики, значение всех элементов (функций и аргументов) которой определены в двухэлементном множестве: 0 и 1. Алгебра логики оперирует с логическими высказываниями.
Высказывание — это любое предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. При этом считается, что высказывание удовлетворяет закону исключенного третьего, то есть каждое высказывание или истинно, или ложно, и не может быть одновременно и истинным и ложным.
Высказывания:
l «Сейчас идет снег» — это утверждение может быть истинным или ложным;
l «Вашингтон — столица США» — истинное утверждение;
l «Частное от деления 10 на 2 равно 3» — ложное утверждение.
В алгебре логики все высказывания обозначают буквами a, b, c и т. д. Содержание высказываний учитывается только при введении их буквенных обозначений, и в дальнейшем над ними можно производить любые действия, предусмотренные данной алгеброй. Причем если над исходными элементами алгебры выполнены некоторые разрешенные в алгебре логики операции, то результаты операций также будут элементами этой алгебры.
Простейшими операциями в алгебре логики являются операции логического сложения (иначе: операция ИЛИ (OR), операция дизъюнкции) и логического умножения (иначе: операция И (AND), операция конъюнкции). Для обозначения операции логического сложения используют символы + или \/, а логического умножения — символы · или /\. Правила выполнения операций в алгебре логики определяются рядом аксиом, теорем и следствий. В частности, для алгебры логики применимы законы:
1. Сочетательный:
(a + b) + c = a + (b + c),
(a · b) · c = a · (b · c).
2. Переместительный:
(a + b) = (b + a),
(a · b) = (b · a).
3. Распределительный
a · (b + c) = a · b + (a · c),
(a + b) · c = a · c + b · c.
Справедливы соотношения, в частности:
Наименьшим элементом алгебры логики является 0, наибольшим элементом — 1. В алгебре логики также вводится еще одна операция — отрицания (операция НЕ (NOT), инверсия), обозначаемая чертой над элементом.
По определению:
Справедливы, например, такие соотношения:
Функция в алгебре логики — выражение, содержащее элементы алгебры логики a, b, c и др., связанные операциями, определенными в этой алгебре.
Примеры логических функций:
Согласно теоремам разложения функций на конституанты (составляющие), любая функция может быть разложена на конституанты 1:
(4)
и т. д. Эти соотношения используются для синтеза логических функций и вычислительных схем.
Дата добавления: 2016-04-02; просмотров: 913;