3.1.6. Полнота

Формальная теория называется полной, если каждому истинному высказыванию соответствует теорема теории.

3.1.7. Независимость

Система аксиом формальной теории называется независимой, если ни одна из аксиом не выводится из оставшихся аксиом.

3.2. Исчисление высказываний

Алфавит состоит из набора переменных, связок и служебных символов:

a, b,…,a1, b1, … – пропозициональные переменные; ¯, – связки; ( , ) – служебные символы.

Формулы определяются согласно следующим правилам:

1)любая пропозициональная переменная есть формула;

2)если А, В – формулы, то (А) , ( A B ) – тоже формулы.

Аксиомы:

A1 :(A (B A)),

A2		:((A (B C)) ((A B) (A C))),
A3		:((					) ((		A) B)).
			B		A			B
Правило:
	A,A B								Modus ponens,
			B						Правило заключения (МР)

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

3.2.1. Интерпретация

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

96

Формализуя определение, мы говорим, что функция h называется интерпретацией, если для любых формул A и B исчисления высказываний h удовлетворяет условиям:

h(A) = h(A) ,

h(A → B) = h(A) → h(B) .

Задача 3.1. Найти значение формулы R = (A → B) → A → B при

интерпретации h(A) = h(B) = 1.

Решение. Правильное решение можно получить двумя способами – либо непосредственной подстановкой, либо через таблицу истинности.

Непосредственная подстановка дает следующий результат:

R = (A → B) → A → B = (1 →1) →1 →1 = (0 →1) →1 →1 =

=1 →1 = 0 →1 =1.

Формула A исчисления высказываний истинна при некоторой интерпретации h тогда и только тогда, когда h(A) = 1. В против-

ном случае, говорят, что A ложна при интерпретации h.

Внашем примере формула R истинна при интерпретации h(A) =

=h(B) = 1.

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

Таблицы истинности дают нам инструмент для определения того, является ли формула A тавтологией (противоречием) или нет.

A	B
			A	→ B	( A → B) → A			(		A	→ B) → A		(		A	→ B) → A → B
0	0	0			1			0					1
0	1	1			0			1					1
1	0	1			1			0					1
1	1	1			1			0					1

В нашем примере, таблица истинности показывает, что заданная формула R – тавтология.

Различные интерпретации дают возможность сформулировать правило подстановки (суперпозиции), которое расширяет набор правил вывода.

97

3.2.2. Правило подстановки

Пусть A – некая формула, выводимая (доказуемая) в исчислении высказываний, x – переменная, B – любая формула исчисления высказываний. Тогда формула, которая получается из формулы A путем подстановки в нее вместо переменной x формулы B, выводима (доказуема).

Попробуем применить правило подстановки для доказательства теоремы 3.1.

Теорема 3.1. Формула А→А выводима в исчислении высказываний.

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

1.Подставим в аксиому А2 вместо B А→А, вместо C – А: (A → ((A → A) → A)) → ((A → (A → A)) → (A → A)) .

2.Но (A → ((A → A) → A)) – это аксиома А1, и по правилу заключения получаем (A → (A → A)) → ( A → A) .

3.Но A → (A → A) – это аксиома А1 и по правилу заключения получаем (A → A) .

3.2.3.Связь между исчислением высказываний

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

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

Отсюда следуют утверждения:

•каждая аксиома – тождественно истинная;

•правило подстановки, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам;

•правило заключения, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам.

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

A & B = A → B ,

98

A B = A → B ,

(A = B) = (A → B) & (B → A) ,

A B = (A → B) → A → B .

Следующая теорема очень полезна при доказательстве других теорем, так как дает новое правило вывода.

Теорема 3.3 (о дедукции). Если Г – множество формул, А и В

– формулы из Г высказываний, А├В, то, Г├А→B.

Используем теорему о дедукции при доказательстве теоремы

3.4.

Теорема 3.4. Из A→B, В→С ├ А→С выводима в исчислении

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

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

1)А→В – гипотеза;

2)B→С – гипотеза;

3)А – тоже гипотеза;

4)B выводимо по правилу заключения из 1 и 3;

5)C выводимо по правилу заключения из 2 и 4;

6)следовательно, А→B, B→C A├C, и, по теореме о дедукции,

А→B, B→C ├A→С.

Мы показали свойство транзитивности импликации.

3.2.4. Основные результаты исследования исчисления высказываний

Разрешимость. Проблема разрешимости для исчисления высказываний разрешима.

Непротиворечивость. Исчисление высказываний непротиворечиво.

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

99