Формулы алгебры высказываний

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

Определение 6. Формулами алгебры высказываний являются:

1) элементарные формулы;

2) если А и В – формулы, то (), (А В), (А В), (А В), (А В) также являются формулами алгебры высказываний;

3) никаких других формул алгебры высказываний, кроме получающихся согласно пунктам 1) и 2), нет.

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

Определение 7. Число операций, с помощью которых из атомов получена формула А, называется рангом формулы А и обозначается r(A).

Определение 8. Часть формулы А алгебры высказываний называется подформулой формулы А, если она сама является формулой алгебры высказываний.

Замечание 2. Если формула содержит n атомов, то таблица истинности для нее содержит 2ⁿ строк. В частности, при n=3 таблица содержит 8 строк, причем атомам удобно придавать значения следующим образом: первому атому – четыре значения 1 и четыре значения 0; второму – два значения 1, два значения 0, два 1, два 0; третьему – значения 1 и 0, чередуя.

Определение 9. Формула А называется тождественно истинной (тавтологией, законом логики высказываний) и обозначается ╞ А, если при любых значениях атомов, входящих в формулу А, А принимает значение 1.

Определение 10. Формула А называется тождественно ложной (противоречием), если при любых значениях атомов, входящих в формулу А, А принимает значение 0.

Определение 11. Формула А называется выполнимой, если найдется такой набор значений атомов, входящих в формулу А, при котором А принимает значение 1.

Определение 12. Формула А называется опровержимой, если найдется такой набор значений атомов, входящих в формулу А, при котором А принимает значение 0.

Определение 13. Формулы А и В называются равносильными и обозначаются А В, если при любых истинностных значениях атомов, входящих в формулы А и В, истинностные значения А и В совпадают.

Замечание 3. Отношение равносильности на множестве всех формул алгебры высказываний является отношением эквивалентности.

Теорема 1. Формулы А и В равносильны тогда и только тогда, когда формула А В является тавтологией.

Доказательство. 1.Необходимость. Пусть А В. Тогда, согласно определению 13, при любых значениях атомов, входящих в формулы А и В, истинностные значения А и В совпадают. Последнее, в силу определения 2.5, означает, что формула А В принимает значение И при любом наборе атомов, в нее входящих, т.е., по определению 10, А В – тавтология.

2. Достаточность. Пусть ╞ А В. Это означает, что формула А В принимает значение И при любых значениях атомов, входящих в нее. Согласно определению 5, это означает, что А и В одновременно принимают либо значение 1, либо значение 0, т.е. являются равносильными. Теорема доказана.

Теорема 2. Для равносильности формул логики высказываний выполняются следующие свойства:

(1) ; (1') — коммутативность;

(2) ; (2') — ассоциативность;

(3) ; (3') — дистрибутивность;

(4) ; (4') — идемпотентность;

(5) ; (5') — законы де Моргана;

(6) 1; (6') 0 — закон исключения третьего;

(7) ; (7')

(8) 1 1; (8') 0 0 — законы поглощения;

(9) 0 ; (9') 1

(10) — закон двойного отрицания;

(11) — исключение эквиваленции;

(12) — исключение импликации.

Доказательство.

Все свойства доказываются с помощью таблиц истинности. Докажем одно из свойств, например, свойство (12). Формулы в левой и правой частях (12) содержат лишь два атома и . Поэтому таблица истинности примет вид:

[ A ]	[ B ]	[ ]	[ A B ]	[ Ú B ]

Из четвертого и пятого столбцов следует, что значения формул и совпадают при любых значениях атомов и . Следовательно, по определению 3.1, формулы и равносильны, т.е. º . Теорема доказана.

Теорема 3 (о замене). Пусть - формула . Если в формуле заменить некоторую её подформулу равносильной ей формулой , то получится формула, равносильная формуле .