2.1.3 Формулы

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

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

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

2. Если формула, то и это формулы.

3. Если и формулы, то , , это формулы.

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

Пример. Последовательности символов  это формулы. Последовательность формулой не является.

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

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

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

1. x x = x; x&x = x (идемпотентность);

2. x y = y x; xy = yx (коммутативность);

3. x (y z) = (x y) z; x(yz) = (xy)z (ассоциативность);

4. (xy) x = x; (x y)x = x (законы поглощения);

5. x (yz) = (x y)(x z); x(y z) = (xy) (xz) (законы дистрибутивности);

6. x 1 = 1; x&1 = x (свойства единицы);

7. x 0 = x; x&0 = 0 (свойства нуля);

8. (инволютивность);

9. (законы де Моргана);

10. (свойства дополнения).

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

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

= x|y = .

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

2.1.5. Примеры решения задач.

Пример 1.

Доказать равносильности: (один из законов де Моргана);

= x|y = .

Решение. Составим таблицу истинности некоторых из указанных функций (табл. 7).

Таблица 7

x	y	x→y		x~y
0	0	1	0	1	1	1	1	1	0
0	1	1	1	0	1	0	1	0	1
1	0	0	1	0	0	1	0	0	1
1	1	1	0	1	0	0	1	1	0

Пример 2. Преобразовать данную формулу к равносильной формуле, в которой отрицания стоят только над аргументами: .

Решение. .

Пример 3. Упростить формулу: .

Решение Пример 4. Составить таблицу истинности формулы:

Решение (табл. 8).

Таблица 8

x	y	z				|
0	0	0	1	1	1	0	0	1	1
0	0	1	0	1	1	1	0	1	0
0	1	0	1	0	1	0	0	1	1
0	1	1	0	0	1	1	0	1	0
1	0	0	1	1	1	0	0	1	1
1	0	1	0	1	1	1	0	1	0
1	1	0	1	0	0	1	1	0	1
1	1	1	0	0	0	1	1	0	1

Пример 5.

Функции и заданы таблицами истинности (табл. 9, табл. 10). Построить таблицу истинности суперпозиции

.

Таблица 9 Таблица 10

0	0	1		0	0	1
0	1	0		0	1	0
1	0	0		1	0	1
1	1	1		1	1	1

Решение. Построим таблицу истинности функции (табл. 11).

Таблица 11

0	0	0	1	1	1
0	0	1	1	0	0
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	0	1	0
1	0	1	0	0	1
1	1	0	1	1	1
1	1	1	1	1	1