Свойства элементарных функций алгебры логики

 

Из таблицы 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 обладает следующими свойствами:

– коммутативности (переместительный закон):

12= 21,

– ассоциативности (сочетательный закон):

1(23)= (12) 3,

– дистрибутивности (распределительный закон):

1(23)= (12) (13).

Для этой функции справедливы аксиомы:

=0; 1=;

=1; 0=.

На основании аксиом и свойств можно вывести правила перевода функций И, ИЛИ, НЕ через функцию сложения по модулю 2, и наоборот:

;

;

.

 

Функция импликации () – функция, выражаемая следующим образом: 12=1+2.

Для функции импликации справедливы аксиомы:

;;;

;;.

 

Из аксиом следует, что импликация обладает только свойством коммутативности (переместительный закон) в измененном виде: 12=21.

Свойство ассоциативности для этой функции несправедливо (табл. 1.6).

 

Таблица 1.6

Функции И, ИЛИ, НЕ через импликацию выражаются так:

;

;

.

 

Функция Шеффера (/) – функция, которая может быть выражена соотношением 1/2=.

Для нее характерны аксиомы:

;;;

;;;

 

что подтверждается таблицей 1.7.

 

Таблица 1.7

Эти аксиомы позволяют сформулировать следующие правила преобразования:

;

;

.

 

Для функции Шеффера справедливо свойство коммутативности для двух переменных 1/2=2/1, что легко проверяется. Для трех и более переменных это свойство уже не выполняется.

В самом деле, функция Шеффера является строго двуместной функцией, т.е. для нее невозможны записи вида 1/2/3, так как непонятно, в какой очередности применять операцию Шеффера в этом выражении. Следовательно, очередность применения операции Шеффера должна указываться с помощью скобок, как, например, ((1/2)/3)/4.

Эти выводы подтверждаются также тем, что свойства ассоциативности и дистрибутивности для функции Шеффера несправедливы.

Необходимо указать на возможность возникновения следующего заблуждения: функция Шеффера равносильна функции отрицания конъюнкции. Так как конъюнкция обладает всеми свойствами (коммутативностью, ассоциативностью, дистрибутивностью), то по этой причине и функция Шеффера должна была бы иметь эти же свойства. Однако равносильность функций на всех наборах не обязательно совпадает с наличием одинаковых свойств, что и подтверждает пример функций Шеффера и НЕ – И.

Функция Пирса (Вебба) () – функция, которая описывается выражением

12==12.

 

Для функций Пирса (Вебба) справедливы аксиомы:

 

;;;

;;.

 

что подтверждается таблицей 1.8.

 

Таблица 1.8

Элементарные булевы функции И, ИЛИ, НЕ выражаются через функцию Пирса (Вебба) следующим образом:

;

;

.

 

Для функции Пирса (Вебба) справедливо свойство коммутативности только для двух переменных: 12=21. Функция Пирса (Вебба), так же, как и функция Шеффера, является двуместной функцией. Следовательно, невозможны записи вида: 123; для установления приоритетов обязательно должны использоваться скобки, которые определяют последовательность осуществления операций

 

(12)(3(45)).

 

Аналогично с функцией Шеффера для функции Пирса (Вебба) несправедливы свойства ассоциативности и дистрибутивности.

Надо заметить также, что 12=, т.е. функция Пирса, равносильна функции НЕ – ИЛИ. Здесь также равносильность функций не ведет к наличию одинаковых свойств у этих функций.