Булевы функции одной и двух переменных

Перечислим без дальнейших пояснений 4 логические функции одной переменной и 16 логических функций двух переменных (табл. 3, табл. 4, табл. 5, табл.6).

Таблица 3

x f1 f2 f3 f4

Таблица 4

Функция Название Обозначение Фиктивная переменная
f1 Ноль (противоречие) x
f2 Тождественная x  
f3 Отрицание Булевы функции одной и двух переменных - student2.ru  
f4 Единица (тавтология) x

Таблица 5

x1 x2 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16

Таблица 6

Функция Название Обозначение Фиктивная переменная
f1 Ноль (противоречие) x1, x2
f2 Логическое умножение; конъюнкция; и Булевы функции одной и двух переменных - student2.ru -
f3 - - -
f4 - Булевы функции одной и двух переменных - student2.ru x2
f5 - - -
f6 - Булевы функции одной и двух переменных - student2.ru x1
f7 Сложение по модулю 2 Булевы функции одной и двух переменных - student2.ru x1∆x2 -
f8 Логическое сложение; дизъюнкция; или Булевы функции одной и двух переменных - student2.ru -
Окончание табл. 6
f9 Стрелка Пирса Булевы функции одной и двух переменных - student2.ru -
f10 Эквивалентность x1~x2, Булевы функции одной и двух переменных - student2.ru -
f11 - Булевы функции одной и двух переменных - student2.ru x1
f12 - - -
f13 - Булевы функции одной и двух переменных - student2.ru x2
f14 Импликация; если, то Булевы функции одной и двух переменных - student2.ru -
f15 Штрих Шеффера x1|x2 -
f16 Единица (тавтология) x1, x2

Отметим, что в импликации Булевы функции одной и двух переменных - student2.ru переменная Булевы функции одной и двух переменных - student2.ru называется посылкой, а переменная Булевы функции одной и двух переменных - student2.ru − заключениемимпликации. Импликация ложна в одном единственном случае, когда посылка истинна, а заключение ложно. Логики говорят, что из истины не может следовать ложь, а из лжи может следовать что угодно.

Формулы

Символы логических операций Булевы функции одной и двух переменных - student2.ru | назовем логическими связками. Формула - это последовательность имен переменных, соединенных логическими связками, и составленная по определенным правилам. Формула может содержать также открывающие и закрывающие скобки. Связки Булевы функции одной и двух переменных - student2.ru назовем основными.

Перечислим правила построения формул.

1. Всякая переменная, быть может с индексами, - это формула. Логические константы 0 и 1 - это формулы.

2. Если Булевы функции одной и двух переменных - student2.ru формула, то Булевы функции одной и двух переменных - student2.ru и Булевы функции одной и двух переменных - student2.ru это формулы.

3. Если Булевы функции одной и двух переменных - student2.ru и Булевы функции одной и двух переменных - student2.ru формулы, то Булевы функции одной и двух переменных - student2.ru , Булевы функции одной и двух переменных - student2.ru , Булевы функции одной и двух переменных - student2.ru это формулы.

4. Других формул нет.

Пример. Последовательности символов Булевы функции одной и двух переменных - student2.ru - это формулы. Последовательность Булевы функции одной и двух переменных - student2.ru формулой не является.

Всякая формула определяет некоторую логическую функцию, по-другому говорят, что формула реализует некоторую логическую функцию. За каждой формулой скрыта таблица истинности. Поэтому нужно уметь вычислять значение формулы во всякой строке таблицы истинности, на всяком наборе значений ее аргументов. Порядок вычисления значения формулы определяется скобками. Если скобок нет, значение формулы вычисляется слева направо в соответствии со старшинством операций. Иерархия операций (в порядке убывания старшинства) задается так: Булевы функции одной и двух переменных - student2.ru ,(&, |, ↓), Булевы функции одной и двух переменных - student2.ru , →, (~, Булевы функции одной и двух переменных - student2.ru ). В скобках указаны равносильные операции.

Определение. Формулы, реализующие одну и ту же функцию, называются равносильными. Значит, у равносильных формул совпадают таблицы истинности».

Утверждение. Каковы бы ни были формулы x, y, z справедливы следующие равносильности

1. x Булевы функции одной и двух переменных - student2.ru x = x; x&x = x (идемпотентность);

2. x Булевы функции одной и двух переменных - student2.ru y = y Булевы функции одной и двух переменных - student2.ru x; x&y = y&x (коммутативность);

3. x Булевы функции одной и двух переменных - student2.ru (y Булевы функции одной и двух переменных - student2.ru z) = (x Булевы функции одной и двух переменных - student2.ru y) Булевы функции одной и двух переменных - student2.ru z; x&(y&z) = (x&y)&z (ассоциативность);

4. (x&y) Булевы функции одной и двух переменных - student2.ru x = x; (x Булевы функции одной и двух переменных - student2.ru y)&x = x (законы поглощения);

5. x Булевы функции одной и двух переменных - student2.ru (y&z) = (x Булевы функции одной и двух переменных - student2.ru y)&(x Булевы функции одной и двух переменных - student2.ru z); x&(y Булевы функции одной и двух переменных - student2.ru z) = (x&y) Булевы функции одной и двух переменных - student2.ru (x&z) (законы дистрибутивности);

6. x Булевы функции одной и двух переменных - student2.ru 1 = 1; x&1 = x (свойства единицы);

7. x Булевы функции одной и двух переменных - student2.ru 0 = x; x&0 = 0 (свойства нуля);

8. Булевы функции одной и двух переменных - student2.ru (инволютивность);

9. Булевы функции одной и двух переменных - student2.ru (законы де Моргана);

10. Булевы функции одной и двух переменных - student2.ru (свойства дополнения).

Замечание. Для упрощения обозначений символ коньюнкции & часто опускается, вместо x&y пишут просто xy.

Другие полезные равносильности:

Булевы функции одной и двух переменных - student2.ru

= Булевы функции одной и двух переменных - student2.ru Булевы функции одной и двух переменных - student2.ru x|y = Булевы функции одной и двух переменных - student2.ru .

Доказательство проводится построением соответствующих таблиц истинности.

Наши рекомендации