Базис И, ИЛИ, НЕ. Свойства элементарных функций алгебры логики

 

Пусть x - некоторая логическая переменная. Тогда:

1. , что означает возможность исключения из логического выражения всех членов, имеющих двойное отрицание, заменив их исходной величиной;

2. - правила подобных преобразований, которые позволяют сокращать длину логических выражений;

3. xÚ0=x;

4. xÚ1=1;

5. x ^. 0=0;

6. x ^.1=x;

7. ;

8. .

Дизъюнкция и конъюнкция обладают рядом свойств, аналогичных свойствам обычных арифметических операций сложения и умножения:

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

x₁Ú(x₂Úx₃)=(x₁Úx₂)Úx₃, x₁(x₂ x₃)=(x₁ x₂) x₃;

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

x₁Úx₂=x₂Úx₁, x₁x₂=x₂ x₁;

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

для конъюнкции относительно дизъюнкции

x₁&(x₂Úx₃)=(x₁&x₂)Ú(x₁&x₃);

для дизъюнкции относительно конъюнкции

x₁Úx₂&x₃=(x₁Úx₂)&(x₁Úx₃).

Свойство дистрибутивности фактически определяет правила раскрытия скобок или взятия в скобки логических выражений.

Справедливость указанных свойств легко доказывается с помощью вышеизложенных аксиом.

Докажем, например, что

x₁Úx₂&x₃=(x₁Úx₂)&(x₁Úx₃).

В самом деле, (x₁Úx₂)(x₁Úx₃) = x₁x₁Ú x₁x₃Ú x₁x₂Ú x₂x₃ = x₁Ú x₁x₂Ú x₁x₃Ú Úx₂x₃ = x₁(1Ú x₂Ú x₃) Ú x₂x₃.

Аналогично можно доказать и другие законы.

Таким же образом доказывается правильность соотношений, известных как законы де Моргана:

, (5)

. (6)

Из законов де Моргана следует, что:

. (7)

, (8)

помощью которых появляется возможность выражать конъюнкцию через дизъюнкцию и отрицание или дизъюнкцию через конъюнкцию и отрицание.

Законы де Моргана и следствия из них справедливы для любого количества переменных:

, (9)

. (10)

Для логических функций устанавливаются соотношения, известные как законы поглощения:

x₁Ú x₁x₂ = x₁, (11)

x₁&(x₁Úx₂) = x₁. (12)

Очень важными в теории ФАЛ являются действия полного склеивания и неполного склеивания. Примеры выполнения этих действий с двумя конституентами 1 приведены ниже:

- полное склеивание; (13)

- неполное склеивание. (14)

Более важным для практики является неполное склеивание, так как для сложных ФАЛ исходные конституенты 1 F_i и F_j после получения результата склеивания друг с другом F_k сохраняются для сопоставления с другими минтермами в записи заданной ФАЛ и нового склеивания по одной из переменных, входящих в сопоставимые минтермы с отрицанием и без отрицания (отличающихся по одной переменной).

Рассмотренные основные соотношения позволяют описать равносильные булевы функции различными способами, вследствие чего открываются возможности выбора самых простых форм описания ФАЛ. Самые простые по форме ФАЛ реализуются на элементной базе по принципиальным схемам, имеющим самую низкую стоимость.