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

С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний х, у, z можно построить высказывания: (x&y) и х .

Первое из них есть дизъюнкция конъюнкции х, у и отрицания выказывания z, а второе высказывание есть импликация, посылкой которой является высказывание х, а заключением - отрицание дизъюнкции высказывания у и конъюнкции высказываний х, z.

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

Формулы алгебры логики будем обозначать большими буквами латинского алфавита А, В, С, ...

Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквивалентность. Если над формулой стоит знак отрицания, то скобки тоже опускаются.

В связи с этим формулы:

(х&у) и х

могут быть записаны так:

и .

Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее элементарных высказываний. Например, логическим значением формулы в случае, если х = 1, у = 1, z= 0, будет истина, то есть =1.

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

Например, для формулы таблица истинности имеет вид:

х	у				х&

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