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

Сентябрь 13, 2022

Главная
Математика
Исчисление высказываний

Содержание

2. Исчисление высказываний – формальная теория Т, в которой заданы: 1. Алфавит А: переменные - x, y,
3. 2. Язык состоит из слов. Словом (формулой исчисления) называют любую конечную последовательность алфавита. 3. Правильно построенные
4. 4. Аксиомы. А 1: А2: А3:
5. 5. Правило вывода. МР принимается без доказательства!
6. 6. Вывод формулы - конечная последовательность формул А1, А2, …, Аn, такая, что: последняя формула совпадает
7. Исчисление высказываний представляет собой множество выводимых формул в данном алфавите при данном наборе аксиом и правил
8. Первые теоремы ИВ Д-во первых теорем выглядит громоздко и непредсказуемо. В дальнейшем выводятся некоторые правила, которые
15. Выводимость из гипотез Пусть даны формулы – гипотезы А1, А2, …, Аn Нужно доказать А1, А2,
16. Свойства выводимости из гипотез Если Г, А⊢А (самовыводимость). Если Г⊢А, то Г, В⊢А (расширение списка гипотез).
17. Теорема дедукции (ТД) выявляет некоторую общую закономерность при таких построениях и тем самым облегчает процесс построения
18. Связь ⊢ и → Наличие МР и ТД позволяет взаимно заменять знаки. Г, А⊢В ~ Г⊢А→В
19. Если ТД применять в качестве аксиомы, то А1, А2 можно доказать как теоремы. Докажем А1: ⊢А
20. Д-во: А , В ⊢А 10 А ⊢ В →А 1), ТД А1: ⊢А →(В →А)
21. Докажем А2: ⊢(А →(В →С)) → (А →В) →(А→С) Анализ: ТД (А →(В →С)) ⊢ (А
22. Д-во: А →(В →С), А →В, А⊢В МР А →(В →С), А →В, А⊢В →С МР
23. Докажем А →В, В →С ⊢ А→С Анализ: ТД А →В, В →С, А⊢С Д-во: А
24. Докажем А →В⊢ В→А Д-во: А →А, А →В⊢ А → В Т3 А →В, В
25. 4) А →В⊢ В → А А3 5) А →В⊢ В → А 3, 4, 40
26. Т5
27. Производные правила вывода Лемма – доказанное утверждение, полезное для доказательства других утверждений.
28. Из & двух высказываний выводится каждый член АВ ⊢А Анализ: А →В ⊢ А Д-во: закон
29. АВ ⊢В Анализ: А →В ⊢ В Д-во: закон контрапозиции 1) В, А ⊢ В 10
30. А,В ⊢АВ Анализ: А, В⊢ А →В Д-во: закон контрапозиции 1) А, А→В⊢В (МР) А, А→В⊢В
31. А ⊢АvB Анализ: А ⊢ А →В Д-во: ТД 1) А, В →А 10 А, А
32. Если А ⊢С, В ⊢С, то АvB⊢С Д-во: А ⊢С – дано С⊢А 1), контр. В
36. Скачать презентацию

Слайд 2

Исчисление высказываний – формальная теория Т, в которой заданы:
1. Алфавит А:
переменные

- x, y, z, xi ;
логические связки - , (дополнительно можно ввести связки , т.к.
( ) – технические символы (, не является символом алфавита).

Слайд 3

2. Язык состоит из слов. Словом (формулой исчисления) называют любую конечную

последовательность алфавита.
3. Правильно построенные формулы (ППФ).
других ППФ нет.

Слайд 4

4. Аксиомы.
А 1:
А2:
А3:

Слайд 5

5. Правило вывода.
МР принимается без доказательства!

Слайд 6

6. Вывод формулы - конечная последовательность формул
А1, А2, …, Аn,

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

Слайд 7

Исчисление высказываний представляет собой множество выводимых формул в данном алфавите при

данном наборе аксиом и правил вывода.

Слайд 8

Первые теоремы ИВ
Д-во первых теорем выглядит громоздко и непредсказуемо.
В дальнейшем выводятся

некоторые правила, которые будут предсказывать д-во теорем.
Ⱶ А – формула А выводима.
Перед всеми аксиомами можно поставить знак Ⱶ, т.к. они постулировались.

Слайд 9

Слайд 10

Слайд 11

Слайд 12

Слайд 13

Слайд 14

Слайд 15

Выводимость из гипотез
Пусть даны формулы – гипотезы А1, А2, …, Аn
Нужно

доказать А1, А2, …, Аn Ⱶ F
Совокупность этих гипотез обозначим Г
Выводом (доказательством) формулы F из гипотез Г называется последовательность формул F1, F2, …, Fn, в которых последняя формула совпадает с F и каждая Fi – аксиома или получена из предыдущих по МР.

Слайд 16

Свойства выводимости из гипотез
Если Г, А⊢А (самовыводимость).
Если Г⊢А, то Г, В⊢А (расширение

списка гипотез).
Если Г, А⊢В, Г⊢А, то Г⊢В (удаление).
Если Г⊢А, А⊢В, то Г⊢В (транзитивность).
Если Г, А,В⊢С, то Г, В,А⊢С (коммутативность).
Если Г, А, А⊢В, то Г, А⊢В (сокращение).

Слайд 17

Теорема дедукции (ТД)
выявляет некоторую общую закономерность при таких построениях и тем

самым облегчает процесс построения доказательства.
Если Г, В ├ А, то Г ├ В → А,
где Г - это набор некоторых формул
Г={F1, F2, ..., Fn}.

Слайд 18

Связь ⊢ и →
Наличие МР и ТД позволяет взаимно заменять знаки.
Г,

А⊢В ~ Г⊢А→В
МР: А, А → В А, А → В ⊢ В
В

Слайд 19

Если ТД применять в качестве аксиомы, то А1, А2 можно доказать

как теоремы.
Докажем А1: ⊢А →(В →А)
Анализ:
ТД
А ⊢ В →А
ТД
А , В ⊢А

Т1

Слайд 20

Д-во:
А , В ⊢А 10
А ⊢ В →А 1), ТД
А1: ⊢А

→(В →А) 2), ТД

Слайд 21

Докажем А2: ⊢(А →(В →С)) → (А →В) →(А→С)
Анализ: ТД
(А →(В

→С)) ⊢ (А →В) →(А→С)
ТД
А →(В →С), А →В ⊢ А→С
ТД
А →(В →С), А →В, А⊢С

Т2

Слайд 22

Д-во:
А →(В →С), А →В, А⊢В МР
А →(В →С), А →В,

А⊢В →С МР
А →(В →С), (А →В), А⊢С 1),2), МР
А →(В →С), А →В ⊢ А→С 3), ТД
(А →(В →С)) ⊢ (А →В) →(А→С) 4), ТД
⊢(А →(В →С)) → (А →В) →(А→С) 5), ТД

Слайд 23

Докажем А →В, В →С ⊢ А→С
Анализ: ТД
А →В, В

→С, А⊢С
Д-во:
А →В, В →С, А⊢В МР
А →В, В →С, А, В⊢С 1), МР
А →В, В →С, А⊢С 1), 2), 30
А →В, В →С ⊢ А→С 4), ТД

Т3

Слайд 24

Докажем А →В⊢ В→А
Д-во:
А →А, А →В⊢ А → В Т3
А →В,

В →В⊢ А → В Т3
А →В⊢ А → В 1, 2, 40

Т4

Слайд 25

4) А →В⊢ В → А А3
5) А →В⊢ В → А 3,

4, 40

Слайд 26

Т5

Слайд 27

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

Слайд 28

Из & двух высказываний выводится каждый член
АВ ⊢А
Анализ: А →В ⊢ А

Д-во:
закон контрапозиции 1) А, В →А 10
А ⊢ А→В 2) А , А→В 1),конт.
ТД 3) А ⊢ А→В 2),ТД
А , А→В 4) А →В ⊢ А 3), конт.
закон контрапозиции 5) АВ ⊢А
А, В →А

Lemma 1 (удаление &)

Слайд 29