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

Под алгеброй логики будем понимать алгебру, образованную множеством 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

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

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. Таблица для равносильных формул