ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5048
Скачиваний: 25
6
Теоремой называется такая формула
A
теории, что существует
доказательство, в котором последней формулой является формула
A
.
Для аксиоматической теории введено понятие полноты. Ак-
сиоматическая теория полна (в смысле Поста), если присоединение
к ее аксиомам формулы, не являющейся теоремой, при сохранении
неизменными правил вывода, делает теорию противоречивой.
Чтобы установить связь между формальной теорией и какой-
либо конкретной содержательной теорией, нужно решить вопрос об
интерпретации формальной теории в содержательную. Говорят,
что существует интерпретация формальной теории в содержатель-
ную, если существует соответствие между формулами формальной
теории и объектами – утверждениями содержательной теории. Ин-
терпретация называется правильной, если каждой теореме фор-
мальной теории ставится в соответствие истинное утверждение со-
держательной теории. Интерпретация называется адекватной, если
она правильная и каждому истинному утверждению содержательной
теории ставится в соответствие теорема формальной теории (т.е.
существует взаимно однозначное соответствие между утверждения-
ми содержательной теории и теоремами формальной теории).
Теперь, прежде чем перейти к рассмотрению некоторых фор-
мальных логических теорий, сделаем следующее замечание. Для
того чтобы ввести формальный язык, мы должны пользоваться ка-
ким-то языком, (например, русским, дополненным некоторыми сим-
волами). Этот язык мы будем называть метаязыком, в отличие от
первого (т.е. формального языка), который называют языком-
объектом.
В метаязыке доказывают некоторые утверждения формальной
теории, их относят к метатеории. Поэтому следует различать упот-
ребление слов «доказательство» и «теорема» в формальном языке
(языке-объекте) и в метаязыке.
В математике существует термин «исчисление». Он имеет два
смысла.
В первом смысле исчисление – составная часть названия неко-
торых разделов математики, трактующих правила вычислений и
оперирования с объектами того или иного типа, например, инте-
гральное исчисление, вариационное исчисление.
7
Во втором смысле исчисление – дедуктивная система, т.е. спо-
соб задания того или иного множества путем указания исходных
элементов (аксиом исчисления) и правил вывода, каждое из которых
описывает, как строить новые элементы из исходных и уже постро-
енных.
Построение формальных теорий основано именно на этом спо-
собе. Поэтому исчисления являются одним из основных аппаратов
математической логики. В связи с этим построение формальной тео-
рии для алгебры высказываний называется исчислением высказы-
ваний, а для логики предикатов – исчислением предикатов.
1.2
Исчисление
высказываний
Исходными символами или алфавитом исчисления высказыва-
ний является бесконечное число переменных высказываний
X , Y , Z , X
1
, X
2
, X
3
... ,
четыре символа логических операций
٨, ٧,
→, ⎯
и скобки ( , ).
Определим формулы исчисления высказываний.
1.
Переменное высказывание – формула.
2.
Если
A
и
B
– формулы, то (
A
٨
B
), (
A
٧
B
), (
A
→
B
),
⎯
A
– фор-
мулы.
3.
Никаких формул, кроме выделенных согласно п.п. 1 и 2 нет.
Исчисление высказываний будем базировать на бесконечном
числе аксиом. Поскольку бесконечное число аксиом полностью опи-
сать нельзя, выпишем так называемые аксиомные схемы.
1.
(
A
→ (
B
→
A
)).
2.
((
A
→ (
B
→
C
))
→ ((
A
→
B
)
→ (
A
→
C
))).
3.
((
A
→
B
)
→ ((
A
→
C
)
→ (
A
→ (
B
٨
C
)))).
4.
((
A
٨
B
)
→
A
).
5.
((
A
٨
B
)
→
B
).
6.
((
A
→
C
)
→ ((
B
→
C
)
→ ((
A
٧
B
)
→
C
))).
7.
(
A
→ (
A
٧
B
)).
8.
(
B
→ (
A
٧
B
)).
9.
((
A
→
B
)
→ (
B
→
A
)).
8
10.
A
→
A
.
11.
A
→
A
.
Каждая аксиомная схема представляет собой бесконечное чис-
ло аксиом после замены
A
,
B
,
C
на произвольные формулы исчис-
ления высказываний.
Введем только одно правило вывода, с помощью которого из
формул
A
и
A
→
B
получаем новую формулу
B
. Это правило назы-
вается правилом заключения.
Пользуясь аксиомами и правилом заключения, мы можем стро-
ить доказательства и получать новые формулы – теоремы.
Примеры теорем исчисления высказываний.
Пример 1. Покажем, что (Х
→ Х) – теорема. Для этой цели
построим доказательство, т.е. последовательность формул, послед-
ней в которой должна быть формула (X
→ X):
1)
((Х
→ (Х
̿ → Х)) → ((Х → Х̿) → (Х → Х))) (по схеме 2, где
A
заменено на X,
B
на X
̿,
C
на X);
2)
(X
→ (X
̿ → X)) (по схеме 1);
3)
((X
→ X
̿) → (X → X))) (из 2) и 1) по правилу заключения);
4)
(X
→ X
̿) (по схеме 11);
5)
(X
→ X) (из 4) и 3) по правилу заключения);
По определению доказательства и теоремы (X
→ X) есть тео-
рема.
Пример 2. Покажем, что ((X
٨ Y) → (Y ٨ X)) – теорема.
Соответствующая последовательность формул (
A
заменяем на
X ٨ Y,
B
- на Y,
C
- на X):
1)
((X ٨ Y)
→ Y) → (((X ٨ Y) → X) → ((X ٨ Y) →
(Y ٨ X))) (из схемы 3);
2)
((X ٨ Y)
→ Y) (из схемы 5);
3)
(((X ٨ Y)
→ X) → ((X ٨ Y) → (Y ٨ X))) (из 1), 2) по прави-
лу заключения);
4)
((X ٨ Y)
→ X) (из схемы 4);
5)
((X ٨ Y)
→ (Y ٨ X)) (из 3), 4) по правилу заключения).
Исследуем некоторые свойства построенного исчисления вы-
сказываний. Будем интерпретировать исчисление высказываний в
алгебру высказываний, ставя в соответствие каждой формуле исчис-
ления высказываний аналогичную формулу алгебры высказываний.
9
Можно показать, что такая интерпретация адекватна. Покажем
только правильность интерпретации.
Теорема 1. Всякая теорема исчисления высказываний являет-
ся тавтологией алгебры высказываний.
Доказательство будем проводить индукцией по длине доказа-
тельства теоремы в исчислении высказываний.
Пусть
A
n
– теорема, а
A
1
,
A
2
, ... ,
A
n
– ее доказательство. При
n = 1 теорема
A
n
есть аксиома. Из определения операций в алгебре
высказываний следует, что аксиома является тавтологией. Индук-
тивный шаг следует из того, что правило заключения, примененное
к тавтологиям, приводит к тавтологии.
g
Эта теорема доказывает правильность интерпретации.
Относительно исчисления высказываний можно показать его
полноту (по Посту) и непротиворечивость.
Непротиворечивость – свойство аксиоматической теории, со-
стоящее в том, что в этой теории нельзя получить противоречие, т.е.
доказать некоторое предложение вместе с его отрицанием или дока-
зать некоторое заведомо абсурдное утверждение.
Для широкого класса аксиоматических теорий непротиворечи-
вость имеет место тогда и только тогда, когда существует предло-
жение, формулируемое в данной теории и недоказуемое в ней.
Теорема 2. Исчисление высказываний непротиворечиво.
Доказательство. Всякая теорема исчисления высказываний
является тавтологией. Отрицание теоремы тождественно ложно в
алгебре высказываний и значит, не является теоремой исчисления
высказываний.
Теорема 3. (Теорема о полноте исчисления высказываний)
Пусть
A
(X
1
,..., X
n
)
−
формула, не являющаяся теоремой. Тео-
рия, которая получается из исчисления высказываний добавлением
в качестве аксиом всех формул, получающихся из
A
(X
1
,..., X
n
) заме-
ной переменных высказываний на произвольные формулы, противо-
речива.
Доказательство. Формула
A
(X
1
,..., X
n
) не является тавтологи-
ей алгебры высказываний, поэтому существует набор
(
α
1
, ... ,
α
n
) такой, что
A
(
α
1
, ... ,
α
n
) = 0.
Рассмотрим формулу
A
´, которая получится из
A
(X
1
,..., X
n
) за-
меной каждого переменного высказывания X
i
на аксиому, если
10
α
i
= 1 и на отрицание аксиомы, если
α
i
= 0. Формула
A
´ тождествен-
но ложна, следовательно,
A
´ – тавтология.
В силу адекватности интерпретации исчисления высказываний
в алгебру высказываний формула
A
´ является теоремой исчисления
высказываний. Формула же
A
´– аксиома полученного исчисления.
Получили, что формулы
A
´ и
⎯
A
´ являются теоремами исчис-
ления высказываний. Покажем, что произвольная формула
B
явля-
ется теоремой. Это следует из цепочки формул:
(
⎯
B
→
A
´)
→ (⎯
A
´
→
B
) (схема 9);
A
´
→ (⎯
B
→⎯
A
´) (схема 1);
A
´ (аксиома);
B
→
A
´ (по правилу заключения);
A
´
→
B
(по правилу заключения);
A
´ (теорема);
B
(по правилу заключения);
B
→
B
(схема 10);
B
(по правилу заключения).
Полученная теория противоречива.
g
Эта теорема показывает полноту (по Посту) исчисления выска-
зываний.
1.3
Исчисление
предикатов
Алфавит исчисления предикатов состоит из предметных пере-
менных
x , y , z , ... , x
1
, x
2
, x
3
, ... ,
переменных высказываний
X , Y , Z , ... , X
1
, X
2
, X
3
, ... ,
переменных предикатов
W
p
, U
k
, ... , W
1
1
, W
1
2
, ... , W
i
j
, ... ,
символов логических операций
٨ , ٧,
→ ,⎯ , ∀ , ∃
и скобок ( , ).
Определим формулы исчисления предикатов.
1.
Переменное высказывание – формула.
2.
Если W
p
– переменный предикат, то W
p
(x
1
, x
2
, ... , x
p
) – форму-