Размещено на http://www.allbest.ru/

Министерство образования И НАУКИ Российской Федерации

ГОУ ВПО

Воронежская государственная технологическая академия

Кафедра информационных технологий, моделирования и управления

Методические указания к практическим занятиям по дисциплине "Математика"

"Математическая логика и теория алгоритмов"

Воронеж 2010

УДК 51(075); 681.3.06

Исчисление высказываний: Методические указания к практическим занятиям по курсу "Математическая логика и теория алгоритмов" /Воронеж. гос. технол. акад. : Сост. И.Ю. Шурупова, С.В. Кулакова, О.Ю. Никифорова. Воронеж, 2003. 28 с.

Излагаются основные разделы исчисления высказываний: понятие выводимости, естественного вывода, отношения эквивалентности. Приведены примеры решения задач и варианты заданий для самостоятельной работы. Задания разработаны в соответствии с требованиями ГОС ВПО подготовки инженеров по специальности 071900 - "Информационные системы и технологии". Они предназначены для закрепления теоретических знаний дисциплины цикла ЕН.

Составители: доцент И.Ю. ШУРУПОВА,

доцент С.В. Кулакова,

ассистент О.Ю. НИКИФОРОВА

Научный редактор профессор В.В. СЫСОЕВ

Рецензент профессор Десятов Д.Б.

Печатается по решению редакционно-издательского совета

Воронежской государственной технологической академии Шурупова И.Ю., Кулакова С.В., Никифорова О.Ю., 2003

Воронежская государственная технологическая академия, 2003

Оригинал-макет данного издания является собственностью Воронежской государственной технологической академии, его репродуцирование (воспроизведение) любым способом без согласия академии запрещается. Данные методические указания рассчитаны на 2 практических занятия (4 часа). Цель занятий - изучить основы исчисления высказываний и научиться выводить формулы в алгебре и исчислении высказываний.

Введение

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

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

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

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

1. Выводимость

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

Пусть задано множество формул от высказывательных переменных

(), (), . . . , (). (1)

Это множество формул назовем системой посылок.

Определение. Формула () называется выводимой из системы формул (1) в алгебре высказываний, что обозначается , . . , , тогда и только тогда, когда формула

(2)

является ТИ-высказыванием, т.е.

.

Из определения следует, что если конъюнкция

(3)

тождественно истинна, то из такой системы посылок (1) выводимы только тождественно истинные формулы, которые выводимы из любой системы посылок. Если же конъюнкция (3) тождественно ложна, то из системы посылок (1) выводима любая формула.

Если формула выводима из системы формул (1), то из истинности всех формул системы при некоторых значениях высказывательных переменных следует истинность формулы при тех же значениях переменных.

Нетрудно доказать следующие свойства выводимости.

1. Если и то .

2. Если и ~, то .

Проверка выводимости формулы из системы посылок (1) непосредственно по определению, т.е. путем доказательства тождественной истинности формулы (2), достаточно громоздко. Рассмотрим более простой способ доказательства выводимости формулы из системы посылок (1), для которых конъюнкция (3) не является ни ТИ-высказыванием, ни ТЛ-высказыванием.

Теорема 1.1. Формула () тогда и только тогда выводима из системы формул (1), когда все полные элементарные дизъюнкции формулы входят в СКН-форму , эквивалентную формуле (3) относительно высказывательных переменных .

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

Из системы посылок (1) строится конъюнкция (3).

Находим СКН-форму от высказывательных переменных для формулы (3).

Строим СКН-форму для формулы и проверяем вхождение полных элементарных дизъюнкций СКН-формы для формулы в СКН-форму для формулы (3).

Задание 1. Доказать выводимость .

Решение.

1. Обозначим = X, =. Строим их конъюнкцию .

2. Найдем СКН-форму эквивалентную этой конъюнкции.

V

3. Получим СКН-форму для формулы B.

Так как обе дизъюнкции входят в СКН-форму , то выводимость доказана.

Замечание. Выводимость формулы можно получить и без нахождения ее СКН-формы. Для этого нужно преобразовать с помощью известных эквивалентностей формулу (3) или даже конъюнкцию некоторых полных дизъюнкций из этой СКН-формы. Например, конъюнкция 1-ой и 3-ей полных дизъюнкций формулы из задания 1 преобразуется с помощью формулы склеивания к искомой формуле.

Кроме того, воспользовавшись теоремой 1, можно построить все СКН-формы выводимые из данной системы посылок. Для этого требуется небольшая модификация алгоритма доказательства выводимости формулы. После построения СКН-формы для формулы (3) необходимо

3. Из полных элементарных дизъюнкций полученной СКН-формы строим различные комбинации конъюнкций. Эти конъюнкции и будут исчерпывать все СКН-формы, выводимые из системы посылок (1).

Задание 2. Найти все формулы, выводимые из системы посылок задания 1.

Решение. Построим различные комбинации полных элементарных дизъюнкций формулы .

1. 

2.

3.

4.

5.

6.

7.

Как легко видеть, при построении всех СКН-форм, выводимых из данной системы посылок, мы получили, как частный случай, формулу .

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

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

является ТИ-высказыванием. В силу определения выводимости, это означает, что формула выводима из формул и .

Варианты заданий.

Показать выводимость формул в алгебре высказываний, используя определение выводимости (1 - 6).

1. X Y, Y Z X Z

2. X (Y Z) Y (X Z)

3. X Y, Y Z, X Z

4. X Y,

5. X (Y Z), X Y, X Z

6. X,

Доказать выводимость формул в алгебре высказываний, используя СКН-формы (7 - 21).

7. Z Y

8. (A B) C A (B C)

9. A B (B C) (A C)

10. U B (G U) (G B)

11. U B (G U) (G B)

12. U (B C)) ~ ((U B) C)

13. (U (B C)) ~ ((U B) (U C))

14. ~

15. (A B) ~ B

16. (A B) (B A)

17. A (B A) ~ A

18. A B (A B)

19.

20.

21.

Построить множество формул, выводимых из данной системы посылок (22 - 25).

22.

23.

24.

25.

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

Логическим исчислением принято называть синтаксическую (т.е. формализованную аксиоматическую) теорию математической логики. Описание всякого исчисления включает:

1) описание алфавита, т.е. множества символов, используемых для построения формул теории;

2) описание языка, т.е. правил построения допустимых последовательностей символов (слов) в алфавите, называемых формулами;

3) задание системы аксиом - некоторого множества истинных формул, называемых аксиомами;

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

Исчисление высказываний - это аксиоматическая логическая система, адекватная алгебре высказываний. Опишем это исчисление.

В качестве алфавита исчисления высказываний возьмем следующее множество символов:

1) счетное множество высказывательных переменных, обозначаемых прописными латинскими буквами с индексами и без них;

2) символы логических операций ;

3) скобки ( , ).

Вместе с символами алфавита будем использовать и метасимволы: латинские буквы жирного шрифта для обозначения формул и знак = для обозначения формул метасимволами.

Множество формул обычно задается индуктивным определением. Допустимыми последовательностями символов или словами в языке исчисления высказываний являются формулы алгебры высказываний. Пункты 1 и 2 этого определения (см. методические указания “Алгебра высказываний. Булевы функции”) определяют элементарные формулы, а п. 3 - механизм образования новых формул.

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

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

Сначала определим исходные истинные формулы, называемые аксиомами. В качестве системы аксиом примем следующие формулы (аксиоматика П.С. Новикова).

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

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

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

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

Пусть U - формула, содержащая высказывательную переменную A. Тогда если U - истинная формула в исчислении высказываний, то, заменяя в ней переменную A всюду, куда она входит, произвольной формулой B, мы также получим истинную формулу.

2. Правило заключения (modus ponens).

Если U и UB истинные формулы в исчислении высказываний, то B также истинная формула.

Указанием аксиом и правил вывода мы полностью определили понятие истинной, или выводимой в исчислении высказываний, формулы. Пользуясь правилами вывода, мы можем, исходя из аксиом, конструировать новые истинные формулы и получать, таким образом, каждую истинную формулу. Формула B называется доказуемой (теоремой в исчислении высказываний), если существует конечная последовательность формул

B₁, B₂, . . . , B_t , (4)

в которой каждая из формул B_i является либо аксиомой, либо, получена по правилам вывода из некоторых предыдущих формул последовательности (4). Эта последовательность называется доказательством формулы (теоремы). Рассмотрим примеры таких доказательств.

Задание 1. Показать, что формулы:

1) ;

2)

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

Решение.

1) Формула

является результатом подстановки в аксиому 2 высказывательной переменной A вместо C. Так как посылка полученного следования есть аксиома 1, то, применяя правило заключения, получим, что

истинная формула.

2) В соответствии с правилом подстановки, заменив все вхождения переменной A в аксиоме 5 на формулу , получим

.

Так как посылка этой аксиомы является аксиомой 4, то по правилу заключения формула

является истинной формулой. Заменим в этой формуле высказывательную переменную C на A

.

Снова воспользовавшись правилом заключения, что возможно, так как посылка истинной формулы является аксиомой 3, получим требуемую формулу

.

Замечание. Рассмотренная нами аксиоматика не является единственно возможной. Приведем и другие, эквивалентные данной, системы аксиом.

I. Операции: (аксиоматика С. Клини (1952)).

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

II. Операции: (аксиоматика Россера (1953)).

1.

2.

3.

III. Операции: (аксиоматика Д.Гильберта и Аккермана (1938)).

1.

2.

3.

4.

IV. Операции: (аксиоматика Лукасевича).

1.

2.

3.

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

Мы будем говорить, что формула B выводима из формул U₁, U₂, . . . ,U_n в исчислении высказываний, если формулу B можно вывести только путем правила заключения, приняв за исходные формулы U₁, U₂, . . . ,U_n и все истинные в исчислении высказываний формулы.

Точное определение выводимости формулы в исчислении высказываний имеет вид: формула B выводима из формул U₁, U₂, . . . ,U_n, называемых исходными, что записывается символически как

U₁, U₂, . . . ,U_n B,

если существует такая конечная последовательность формул (4), что B_t есть B и для каждой формулы B_i выполнено одно из условий:

1) B_i есть посылка или теорема исчисления высказываний;

2) B_i получена из некоторых предыдущих формул последовательности (4) по правилу заключения.

Последовательность (4) называется в этом случае выводом формулы B из системы посылок U₁, U₂, . . . ,U_n.

Рассмотрим пример вывода формулы.

Задание 2. Доказать, что A.

Решение. Для данного примера система посылок содержит 1 формулу U₁=A, а выводимая формула B =. Построим вывод этой формулы.

1) B₁ = A

2) B₂ = - аксиома 1

3) B₃ = B = - получено из B₁ и B₂ в силу правила заключения.

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

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

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

Например, из формулы

возникает схема формул

. (5)

Этой схеме принадлежит формула

.

Новые схемы формул можно получить заменой ее метасимволов схемами формул. Эти схемы выделяют некоторое подмножество формул из множества формул, принадлежащих исходной схеме. Например, из схемы (5) можно получить схему формул

. (6)

Формула принадлежит как схеме формул (5), так и (6).

Для формул, являющимися аксиомами или теоремами, схемы формул называются соответственно схемами аксиом или схемами теорем. Схемами аксиом являются:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

Таким образом, при выводе формулы из системы посылок (которая может быть и пустой) будут использоваться схемы аксиом и правило заключения, правило подстановки применяется неявно в схеме аксиом. Наряду с правилом заключения, мы будем использовать и другие правила образования истинных и выводимых формул. Эти правила являются производными от основных и используются для сокращения многократного применения основных правил. Перечислим основные из производных правил вывода. Как и прежде, метасимволы являются произвольными формулами, а через T обозначим конечное множество формул (возможно пустое).

1. Правило повторения посылки.

T,

2. Правило введения посылки.

Если T, то T, .

3. Правило удаления посылки.

Если T, и T, то T.

4. Правило силлогизма.

Если T, . . . , T и , то T.

5. Правило введения импликации.

Если T,, то T.

Это весьма важное свойство называют еще теоремой дедукции. Учитывая, что - конечное множество формул, свойство 5 можно сформулировать в следующем виде:

Теорема дедукции. Если

B,

.

6. Правило удаления импликации.

Если T, то T,.

7. Правило введения конъюнкции.

T, .

8. Правило удаления конъюнкции.

T, ,

T, .

9. Правило введения дизъюнкции.

T, ,

T, .

10. Правило удаления дизъюнкции.

Если T, и T, , то T, .

11. Правило введения отрицания.

Если T, и T, , то T.

12. Правило удаления отрицания.

T,

13. Правило контрапозиции.

Если T, , то T, .

Правила 1-13 называют обычно правилами естественного вывода, а вывод формулы из системы посылок, при котором используются эти правила, - естественным выводом.

Рассмотрим примеры вывода формул с использованием правил естественного вывода. Несложно доказать, таким образом, справедливость основных эквивалентностей алгебры высказываний. Всюду далее, строя вывод формулы, будем рядом с каждой формулой последовательности указывать применяемое правило (его номер), а затем, в круглых скобках, номера формул исходных посылок, к которым применялось данное правило.

Задание 3. Доказать выводимость формул закона двойственности:

1) ;

2) .

Решение. Покажем вначале справедливость формулы 1).

1. A	9
2. B	9
3.	13 (1)
4.	13 (2)
5. ,	7
6.	4 (3, 4, 5)
7.	5 (6)

Построим теперь обратный вывод.

1.	8
2.	8
3.	13 (1)
4.	13 (2)
5.	10 (3, 4)
6.	13 (5)
7.	5 (6)

Выводить, как уже отмечалось, можно не только ТИ-формулы (теоремы исчисления высказываний), но и формулы, которые будут истинными при условии истинности системы посылок. Рассмотрим пример такого вывода.

Задание 4. Доказать, что

Решение. Построим вывод этой формулы.

1.	8
2.	8
3.	8
4.	6 (1)
5.	6 (2)
6.	9
7.	4 (4, 6)
8.	2 (3)
9.	11 (7, 8)
10.	9
11.	4 (5, 10)
12.	2 (3)
13.	11 (11, 12)
14. ,	7
15.	4 (9, 13, 14)
16.	Теорема ИВ
17.	4 (15, 16)

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

“Если формулы U, B, . . . истинны, то формулы M, N, . . . также истинны”. Такие утверждения записываются в виде схемы:

.

Так, правило заключения запишется как

.

В виде аналогичной схемы можно записывать правило получения выводимости из некоторой системы посылок. Обозначим через - систему посылок . Выражение вида

U₁ , . . . , U_n

B

назовем допустимым в исчислении высказываний правилом, если в исчислении высказываний из U₁ , . . . , U_n следует B.

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

Теорема 2.1. Имеют место следующие выводимости:

1) ,;

2) ,;

3) ,.

Следствие. Если и , то:

1) ;

2) ;

3) .

Варианты заданий.

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

;

a) ;

b) ;

c) ;

d) .

2. Выписать все подформулы формул:

a) ;

b) ;

c) ;

d) .

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

3.

4.

5.

6.

7.

8.

9.

10.

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

11. 

12.

13.

14.

15.

Являются ли выводами в исчислении высказываний следующие последовательности формул (16 - 18).

16.

17.

18.

Применяя производные правила вывода, показать, что доказуемы формулы (19 - 36).

19. U B, P Q (U P) (B Q)

20. U B, P Q (U P) (B Q)

21. U B, P Q (B P) (U Q)

22.

23.

24. (P Q) ((Q R) (P R))

25. (P Q) ((R P) (R Q))

26. Q R (P Q) (P R)

27. (P Q) (Q P),

28. P (Q (P Q))

29. (P Q) (P Q)

30. (P Q)((P (Q R)) (P R)))

31. ((P R) ((Q R) ((P Q) R)))

32. ((P Q) ((P Q) P))

33. (( Q P) (( Q P) Q))

34. Q ((P Q) (Q P)

35. Q (P Q) (P Q)

36. Q (P R Q Q)

Применяя производные правила вывода, построить вывод формул (37 - 43).

37. ,

38.

39.

40.

41.

42.

43.

Применяя производные правила вывода, построить вывод формул. Проверить, справедлива ли выводимость в обратную сторону, если да, то построить вывод (44 - 59).

44.

45.

46.

47.

48.

49.

50.

51.

52. A (C P) (A C) P

53.

54. () P

55. P Q (P)

56. P R Q ((P R) ( R

57. (P Q) (P (Q R)) ( P R)

58.

59.

Пусть А - формула, В - подформула формулы А, А₁ - результат замены некоторого вхождения В в А на формулу В₁. Доказать (В ~ В₁) (А ~ А₁). (Теорема о замене)

Доказать, что если выводима формула U₁, …, U_n B, то формула (U₁ … U_n B) тождественно истина.

Найти такие формулы и , что из доказуемости в исчислении высказываний следует доказуемость , но неверно, что .

3. Отношение эквивалентности

Определим эквивалентность формул в исчислении высказываний.

Определение 1. Формулы U и B называются эквивалентными, что обозначается , если

 (1)

Рассмотрим некоторые простые свойства отношения эквивалентности.

1. Рефлексивность: .

2. Симметричность: если , то .

3. Транзитивность: если и , то .

Задание 1. Доказать свойство симметричности отношения эквивалентности.

Решение.

1.

2.

3.

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

В исчислении высказываний имеют место следующие эквивалентности, которые соответствуют аналогичным свойствам отношения эквивалентности алгебры высказываний.

1. .

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

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

1.	по условию
2.	по условию
3.	5 (1)
4.	5 (2)
5. ,	7
6.	4 (3, 4, 5)

Последняя формула, в силу определения, означает .

Теорема эквивалентности. Если и - формулы, полученные заменой некоторых (одних и тех же) вхождений какой-либо высказывательной переменной в формуле U соответственно формулами и , то

.

Следствие. Если есть некоторая подформула формулы U и эквивалентна формуле , то формула, полученная заменой в формуле U на , эквивалентна U. Иными словами, если , то .

Свойства 2, 4, 10 и теорема эквивалентности позволяют формулу, составленную из высказывательных переменных лишь с помощью операции дизъюнкции, преобразовать к виду

.

Аналогично формула, составленная из с помощью операции конъюнкции эквивалентна формуле

.

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

Теорема 3.1. Для каждой формулы исчисления высказываний существуют эквивалентные ей дизъюнктивная и конъюнктивная нормальные формы.

Варианты заданий.

1. Доказать свойство рефлексивности отношения эквивалентности.

2. Доказать свойство транзитивности отношения эквивалентности.

3. Доказать, что если и , то .

4. Доказать, что если , то и .

5. Доказать, что если , то и .

6. Доказать, что если и , то .

Доказать эквивалентность формул в исчислении высказываний (7 - 21).

7. 

8.

9.

10.

11. ~

12.

13.

14. ~

15.

16.

17. ((P (P Q)) (R Q)) ~ (( P R) (P Q))

18. (( P Q) (P Q)) ~ P

19. (( P Q) (P Q)) ~ P

20. ~ (P Q)

21.

22. Доказать, что если Т U B и Т P Q, то

a) Т (U P) (B Q)

b) Т (U P) (B Q)

c) Т (В P) (U Q)

4. Метатеория исчисления высказываний

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

Определение 1. Синтаксическая теория, содержащая знак операции отрицания, называется непротиворечивой, если ни для какой формулы этой теории формулы и не могут одновременно быть теоремами этой теории.

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

Определение 2. Синтаксическая теория называется непротиворечивой, если существует формула, не являющаяся ее теоремой.

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

и ,

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

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

.

Применяя к последней формуле правило 6, получим

, ,

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

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

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

Теорема 4.1. Всякая формула, являющаяся теоремой в исчислении высказываний, является ТИ-высказыванием в алгебре высказываний.

Непротиворечивость исчисления высказываний является непосредственным следствием этой теоремы. Действительно, в алгебре высказываний формулы и не могут быть одновременно ТИ-высказываниями. Следовательно, и одновременно не могут быть теоремами исчисления высказываний, что означает ее непротиворечивость.

Утверждение, обратное теореме 4.1, означает полноту исчисления высказываний относительно алгебры высказываний.

Теорема 4.2. В исчислении высказываний доказуема всякая формула, которая, как формула алгебры высказываний, является ТИ-высказываний.

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

Теоремы 4.1 и 4.2 формулируют необходимое и достаточное условия доказуемости формулы в исчислении высказываний.

Следствие 1. Для того чтобы формулы и были эквивалентны в исчислении высказываний, необходимо и достаточно, чтобы они были эквивалентны в алгебре высказываний.

Следствие 2. Формула выводима в исчислении высказываний из системы посылок , тогда и только тогда, когда она выводима из этой системы посылок в алгебре высказываний.

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

Кроме понятия полноты, названного относительной полнотой, существуют и другие понятия полноты.

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

Определение 4. Непротиворечивая синтаксическая теория называется полной в узком смысле, если добавление к ее аксиомам любой недоказуемой в ней формулы приводит к противоречивой теории.

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

Теорема 4.3. Исчисление высказываний полно в узком смысле.

Из теоремы 4.3 следует, что выбор аксиом исчисления высказываний был сделан корректно.

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

Для того чтобы решить вопрос, доказуема ли в исчислении высказываний формула , достаточно определить (в силу теорем 4.1 и 4.2) является ли она ТИ-высказыванием алгебры высказываний.

Варианты заданий.

1. Доказать, что:

a) все аксиомы исчисления высказываний тождественно истинны;

b) все доказуемые в исчислении высказываний формулы тождественно истинны

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

3. Доказать независимость схем аксиом исчисления высказываний.

4. Пусть L - исчисление высказываний со схемами аксиом Лукасевича.

a) Доказать, что все доказуемые в L формулы доказуемы в исчислении высказываний.

b) Доказать теорему дедукции для L.

c) Положим , . Доказать, что все доказуемые в исчислении высказываний формулы доказуемы в L.

Библиографический список

1. Яблонский С.В. Введение в дискретную математику: Учебное пособие для Вузов/ Под ред. В.А. Садовничего - 3-е изд. стер. - М.: Высш. шк., 2001. - 384 с.

2. Новиков Ф.А. Дискретная математика для программистов. - Спб: Питер, 2000. - 304 с.: ил.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. - М.: Энергоатомиздат, 1988. - 480 с.

4. Эдельман С.Л. Математическая логика. - М.: Высш. школа, 1975. - 176 с.

5. Коршунов Ю.М. Математические основы кибернетики: Учеб. Пособие для вузов. - 3-е изд. перераб. и доп. - М.: Энергоатомиздат, 1987. - 496 с.: ил.

6. Гудстейн Р.Л. Математическая логика: Пер. с англ. - М.: Издат. иностр. лит., 1961, - 162 с.

7. Мендельсон Э. Введение в математическую логику: Пер. с англ.- М.: Наука, 1976. - 320 с.

8. Слупецкий Е.С., Борковский Л. Элементы математической логики и теории множеств. Пер. с польского. - М.: Прогресс, 1965. - 368 с.

9. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 1984. - 223 с.

Размещено на Allbest.ru