Исчисление

высказываний

Модуль 3. Умозаключения

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

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

Существуют два основных правила для построения новых

формул:

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

Пример:

A (B A)

((A & C) A) (B ((A & C) A))

2. Правило модус поненс. Если выведены некая формула вида (А1כ А2) и формула А1, то из этих двух формул можно

вывести формулу А2.

Общезначимость и выводимость формул

Пропозициональная формула называется общезначимой, если она превращается в истинное

высказывание при любых подстановках вместо пропозициональных переменных конкретных высказываний.

Пропозициональная формула Фn считается

выводимой в исчислении высказываний, если существует список формул Ф1, Ф2,…,Фn, такой, что

каждая формула в нём или является исходной, или получается из стоящей ранее её формулы по правилу подстановки или получается из двух стоящих ранее по правилу модус поненс.

Список Ф1, Ф2,…,Фn называется выводом формулы

Фn.

Секвенция – основной объект преобразо- вания в исчислении высказываний

Секвенция – выражение вида A1…An→B1…Bm, где

A1…An и B1…Bm являются формулами, стрелка интерпретируется и читается как связка «если, … то».

Список формул до стрелки называется посылкой, после стрелки –

заключением.

Секвенция

A1…An→B1…Bm A→B1…Bm

A→B A1…An→ →B →B1…Bm

Формульный образ

(A&…&An) כ (B1 … Bm) A כ(B1 … Bm)

A כ B ¬(A1&…&An) B (B1 … Bm)

Аксиома

Аксиомами (исходными секвенциями) являются все секвенции вида ГА → АΔ (и только они).

Г и – списки формул, А – формула.

Аксиомы становятся истинными высказываниями естественных или искусственных языков после подстановки любых высказываний этих языков на места пропозициональных переменных.

Выводимость и общезначимость секвенций

Секвенция является общезначимой, если пропозициональная формула, являющаяся её формульным образом, общезначима.

Секвенция является выводимой, если её формульный образ является выводимой формулой.

Аксиома есть выводимая секвенция.

Основные теоремы логики высказываний

Теорема 1. Теорема о корректности. Каждая формула выводимая в исчислении высказываний является общезначимой.

Теорема 2. Теорема о полноте.

Каждая тавтология выводима в исчислении высказываний.

Теорема 3.

Всякая секвенция выводима тогда и только тогда, когда общезначима.

Правила вывода

Правило вывода – правило, определяющее переход от посылок к следствиям .

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

Если над чертой находится аксиома, то и под чертой находится аксиома.

Если

* – логическая связка,

то

правило →* называется правилом введения * в заключение;

правило *→ называется правилом введения *в посылку.

Обозначения:

	Правила вывода	Г, Δ, Г1,Δ1 –
		списки формул;
		A,B – формулы.

Алгоритм проверки формулы на выводимость

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

2.Действие, которое в пропозициональной формуле выполняется в последнюю очередь, определяет то правило вывода, по которому будем действовать. Если это действие соответствует операции *, то будем действовать по правилу →*. Таким образом, получаем следующую строчку в выводе (находящуюся над первой), в которой снова записана секвенция или секвенции.

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

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

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