Определение исчисления высказываний

Исчисление высказываний – аксиоматическая теория L (logic) - совокупность правил, используемых для установления истинности утверждений, являющихся комбинациями выражений, построенных на высказывании.

Формальная теория L строится следующим образом:

1. Алфавит – множество переменных – пропозициональных букв, обозначающих высказывания:

А, В, С,...

2. Множество логических связок – операций над высказываниями:

ù, É, (,).

3. Формулы – правильно построенные выражения:

· любая буква, обозначающая высказывание – формула,

· если А и В формулы, то ù А, А É В тоже формулы,

· других формул нет.

Примечание: в формулах могут использоваться парные скобки.

Примечание: в формулах в качестве переменных могут использоваться другие формулы.

4. Аксиомы. Формула алгебры высказываний, которая является истинной на всех наборах переменных, называется тавтологией -тождественно – истинной формулой. Поэтому тавтологию можно принять в виде аксиомы исчисления высказываний.

Примечание: исчисление высказываний может иметь множество аксиом, но необходимо чтобы они были независимы, т.е., чтобы одна из них не выводилась из других.

Каковы бы ни были формулы A, B, C, в теории L следующие формулы являются аксиомами теории L:

1. (A É (B ÉA));

2. ((A É (B ÉС)) É ((A É B) É (A É С)));

3. ((ù B Éù A)) É ((ù B ÉA) É B)).

5. Правило вывода – в теории L только одно: сокращение посылки – формула B является непосредственным следствием формул A и A É B (modus ponens). Т.е., если истинно A и истинно, что из A следует B, то истинно и B:

A, A É B B.

Примечания:

· Пункт 4 указывает не просто три аксиомы, а три формульные схемы, порождающие бесконечное множество аксиом при подстановке в них произвольных формул A, B, C,. Для любой произвольной формулы, очевидно, легко проверить, является ли она аксиомой, или нет, поэтому L – э ффективно аксиоматизированная теория.

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

Для удобства записи формул по определению вводятся такие связки, как Ú, Ù, ~, что означает:

A Ú B Û ù A É B;

A Ù B Û ù (A Éù B)

A ~ B Û (A É B) Ù (B ÉA).

В теории L согласно определению исчисления, формальным выводом формулы B из формул - посылок A₁,…, A_n называется последовательность формул B₁,…, B_k, заканчивающаяся формулой B (т.е. B_k = B), причем каждая формула этой последовательности или одна из посылок A₁,…, A_n, или аксиома, или формула, полученная из некоторых предшествующих формул из A₁,…, A_n, по правилу вывода modus ponens. Если существует формальный вывод формулы B из формул A₁,…, A_n, то формула B называется формально выводимой в L из формул A₁,…, A_n, что обозначается так:

A₁,…, A_n B или Г B, где Г = {A₁,…, A_n }.

Формальным доказательством в теории L называется конечная последовательность формул B₁,…, B_k, такая, что каждая формула этой последовательности либо аксиома, либо получена по правилу modus ponens из каких-нибудь двух предшествующих формул этой последовательности. Формальное доказательство является доказательством последней в последовательности B₁,…, B_k формулы B_k.

Формула B называется формально доказуемой или теоремой теории L, если и только если она имеет формальное доказательство. Обозначается:

B.

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

Существует два способа доказательств тавтологии:

1. Построением таблицы истинности для данной формулы.

2. Упрощением исходной формулы до вида: (А Ú ù А) или (А Ú «истина»).

Пример: Доказать истинность А É (В É А).

Таблица 3.1 – Доказательство по таблице истинности

А	В	В É А	А É (В É А)
и	и	И	и
и	л	И	и
л	и	Л	и
л	л	И	и

Доказательство вторым способом:

А É (В É А) = А É (ù В Ú А) = ù А Ú (ù В Ú А) = ù А Ú А Úù В =

«истина»

= «истина» Ú ù В = «истина».

Дата добавления: 2014-01-06