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

Из таблицы 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=, т.е. функция Пирса, равносильна функции НЕ – ИЛИ. Здесь также равносильность функций не ведет к наличию одинаковых свойств у этих функций.