Из таблицы 1.2 видно, что элементарные функции типа отрицания, дизъюнкции, Шеффера, Пирса, импликации и другие находятся в определенной связи друг с другом. Рассмотрим эти связи и свойства исходных функций.
Конъюнкция, дизъюнкция, отрицание (функции И, ИЛИ, НЕ). Используя основные положения алгебры логики, нетрудно убедиться в справедливости следующих восьми аксиом. Пусть х – некоторая логическая переменная. Тогда:
1. =, что означает возможность исключения из логического выражения всех членов, имеющих двойное отрицание, заменив их исходной величиной;
2. +=; = – правила подобных преобразований позволяют сокращать длину логических выражений;
3. +0=;
4. +1=1;
5. 0=0;
6. 1 =;
7. =0;
8. +=1.
Дизъюнкция и конъюнкция обладают рядом свойств, аналогичных свойствам обычных арифметических операций сложения и умножения:
1) свойство ассоциативности (сочетательный закон):
1+(2+3)= (1+2)+ 3, 1(23)= (12) 3;
2) свойство коммутативности (переместительный закон):
1+2=2+1, 12= 21;
3) свойство дистрибутивности (распределительный закон):
для конъюнкции относительно дизъюнкции
1&(2+3)= (1&2)+ (1&3);
для дизъюнкции относительно конъюнкции
1+23= (1+2)&(1+3).
Свойство дистрибутивности фактически определяет правила раскрытия скобок или взятия в скобки логических выражений.
Справедливость указанных свойств легко доказывается с помощью вышеизложенных аксиом.
Докажем, например, что 1+23= (1+2)&(1+3).
В самом деле: (1+2)(1+3)= 11+13+12+23= =1+12+13+23=1(1+2+3)+23=1+23
Аналогично можно доказать и другие законы.
Несложно установить правильность соотношений, известных как законы де Моргана:
,
.
Из законов де Моргана вытекают следствия (закон отрицания):
,
,
с помощью которых появляется возможность выражать конъюнкцию через дизъюнкцию и отрицание или дизъюнкцию через конъюнкцию и отрицание.
Законы де Моргана и следствия из них справедливы для любого количества переменных:
,
.
Для логических функций устанавливаются соотношения, известные как закон склеивания:
12+ 12=1,
(1+2)(1+2)=1;
законы поглощения:
,
.
В таблице 1.5 показана справедливость законов поглощения.
Таблица 1.5
Функция сложения по модулю 2 (исключительное ИЛИ) – функция, выражаемая следующим образом:
.
Функция сложения по модулю 2 обладает следующими свойствами:
– коммутативности (переместительный закон):
12= 21,
– ассоциативности (сочетательный закон):
1(23)= (12) 3,
– дистрибутивности (распределительный закон):
1(23)= (12) (13).
Для этой функции справедливы аксиомы:
=0; 1=;
=1; 0=.
На основании аксиом и свойств можно вывести правила перевода функций И, ИЛИ, НЕ через функцию сложения по модулю 2, и наоборот:
;
;
.
Функция импликации () – функция, выражаемая следующим образом: 12=1+2.
Для функции импликации справедливы аксиомы:
;;;
;;.
Из аксиом следует, что импликация обладает только свойством коммутативности (переместительный закон) в измененном виде: 12=21.
Свойство ассоциативности для этой функции несправедливо (табл. 1.6).
Таблица 1.6
Функции И, ИЛИ, НЕ через импликацию выражаются так:
;
;
.
Функция Шеффера (/) – функция, которая может быть выражена соотношением 1/2=.
Для нее характерны аксиомы:
;;;
;;;
что подтверждается таблицей 1.7.
Таблица 1.7
Эти аксиомы позволяют сформулировать следующие правила преобразования:
;
;
.
Для функции Шеффера справедливо свойство коммутативности для двух переменных 1/2=2/1, что легко проверяется. Для трех и более переменных это свойство уже не выполняется.
В самом деле, функция Шеффера является строго двуместной функцией, т.е. для нее невозможны записи вида 1/2/3, так как непонятно, в какой очередности применять операцию Шеффера в этом выражении. Следовательно, очередность применения операции Шеффера должна указываться с помощью скобок, как, например, ((1/2)/3)/4.
Эти выводы подтверждаются также тем, что свойства ассоциативности и дистрибутивности для функции Шеффера несправедливы.
Необходимо указать на возможность возникновения следующего заблуждения: функция Шеффера равносильна функции отрицания конъюнкции. Так как конъюнкция обладает всеми свойствами (коммутативностью, ассоциативностью, дистрибутивностью), то по этой причине и функция Шеффера должна была бы иметь эти же свойства. Однако равносильность функций на всех наборах не обязательно совпадает с наличием одинаковых свойств, что и подтверждает пример функций Шеффера и НЕ – И.
Функция Пирса (Вебба) () – функция, которая описывается выражением
12==12.
Для функций Пирса (Вебба) справедливы аксиомы:
;;;
;;.
что подтверждается таблицей 1.8.
Таблица 1.8
Элементарные булевы функции И, ИЛИ, НЕ выражаются через функцию Пирса (Вебба) следующим образом:
;
;
.
Для функции Пирса (Вебба) справедливо свойство коммутативности только для двух переменных: 12=21. Функция Пирса (Вебба), так же, как и функция Шеффера, является двуместной функцией. Следовательно, невозможны записи вида: 123; для установления приоритетов обязательно должны использоваться скобки, которые определяют последовательность осуществления операций
(12)(3(45)).
Аналогично с функцией Шеффера для функции Пирса (Вебба) несправедливы свойства ассоциативности и дистрибутивности.
Надо заметить также, что 12=, т.е. функция Пирса, равносильна функции НЕ – ИЛИ. Здесь также равносильность функций не ведет к наличию одинаковых свойств у этих функций.
