2.1.3. Формулы алгебры логики

Под алгеброй логикибудем понимать алгебру, образованную множествомE= {0, 1} вместе со всеми возможными операциями на этом множестве.

В отличие от обычной алгебры, порожденной бесконечным множеством действительных чисел R, алгебра логики базируется на конечном множествеE, состоящем из двух элементов:1 («истина») и0 («ложь»).

Пусть А, В, С – произвольные высказывания, которые рассмат­риваются как величины, принимающие одно из двух логических значений (1 или 0). Применяя к ним операции конъюнкции, дизъюнкции, импли­кации, эквивалентности и отрицания, можно получить новые слож­ные высказывания, например:

((АВ)С) ~ АВ. (1)

В алгебре логики, в отличие от обычной речи, значение сложного высказывания полностью определяется значениями его составляющих. Предположим, что А – ложное высказывание, В – истинное, С – ложное. Тогда высказывание (1) является ложным в силу определения логических операций.

Наряду с высказываниями, принимающими определенные постоянные значения (1 или 0) и называемыми постоянными высказываниями, в алгебре логики рассматривают переменные высказывания, которые не являются таковыми. Таким образом, вводятся понятия логических констант и переменных.

Так, если X, Y, Z – логические переменные то, применяя к ним операции конъюнкции, дизъюнкции, импликации, эквивалентности и отрицания, можно получить формулы алгебры логики.

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

Переменные и функции принимают только два значения (1 или 0), поэтому логические функции можно описать конечной таблицей, которую называют таблицей истинности.

Рассмотренные выше логические выражения определяют основные функции двух переменных f(x, y) формулами: x  y, x  y, х  у, х  у,x. Ниже приведена их таблица истинности (табл. 2.1).

Таблица 2.1. Таблица истинности основных функций

x	y	x y	x  y	х  у	x  y	x
0	0	0	0	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	0	0
1	1	1	1	1	1	0

Выполнять логические операции нужно в следующем порядке:

1. отрицание ( );

2. конъюнкция ();

3. дизъюнкция ();

4. импликация ();

5. эквивалентность ().

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

Пример 1. ФормулуF=xyzследует понимать так:

F = (x  y)  z.

Возможен случай, когда две формулы имеют одну и ту же таблицу истинности, т.е. определяют одну и ту же логическую функцию. Такие формулы называют равносильными. При этом количество и состав переменных в формулах не обяза­тельно должны совпадать.

Пример 2.Следующие две формулы:

F₁ =y  z и F₂ = (( x  y ) z)  ( x  y )

являются равносильными. Они определяют одну и ту же функцию f (x, y, z), что следует из таблицы 2.2.

Если все значения функции в таблице истинности равны 1, то функции называется тождественно истинной. Формула для такой функции называетсятавтологией. Тавтологичность формулы можно легко обнаружить с помощью таблиц истинности.

Таблица 2.2. Таблица для равносильных формул

x	y	z	F1 =y  z	F2=((xy) z)  (x y)
0	0	0	1	1
0	0	1	1	1
0	1	0	0	0
0	1	1	1	1
1	0	0	1	1
1	0	1	1	1
1	1	0	0	0
1	1	1	1	1