Исчисление высказываний - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Исчисление высказываний. Доклад-сообщение содержит 35 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

2. Язык состоит из слов. Словом (формулой исчисления) называют любую конечную последовательность алфавита. 3. Правильно построенные формулы (ППФ). других ППФ нет.

Слайд 4

Описание слайда:

4. Аксиомы.

Слайд 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: ⊢А (В А) Анализ: ТД А ⊢ В А ТД А , В ⊢А

Слайд 20

Описание слайда:

Д-во: А , В ⊢А 10 А ⊢ В А 1), ТД А1: ⊢А (В А) 2), ТД

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

Д-во: А (В С), А В, А⊢В МР А (В С), А В, А⊢В С МР А (В С), (А В), А⊢С 1),2), МР А (В С), А В ⊢ АС 3), ТД (А (В С)) ⊢ (А В) (АС) 4), ТД ⊢(А (В С))  (А В) (АС) 5), ТД

Слайд 23

Описание слайда:

Докажем А В, В С ⊢ АС Анализ: ТД А В, В С, А⊢С Д-во: А В, В С, А⊢В МР А В, В С, А, В⊢С 1), МР А В, В С, А⊢С 1), 2), 30 А В, В С ⊢ АС 4), ТД

Слайд 24

Описание слайда:

Докажем А В⊢ ВА Д-во: А А, А В⊢ А  В Т3 А В, В В⊢ А  В Т3 А В⊢ А  В 1, 2, 40

Слайд 25

Описание слайда:

4) А В⊢ В  А А3 5) А В⊢ В  А 3, 4, 40

Слайд 26

Описание слайда:

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

Lemma 1 (удаление &) Из & двух высказываний выводится каждый член АВ ⊢А Анализ: А В ⊢ А Д-во: закон контрапозиции 1) А, В А 10 А ⊢ АВ 2) А , АВ 1),конт. ТД 3) А ⊢ АВ 2),ТД А , АВ 4) А В ⊢ А 3), конт. закон контрапозиции 5) АВ ⊢А А, В А

Слайд 29

Описание слайда:

Lemma 2 (удаление &) АВ ⊢В Анализ: А В ⊢ В Д-во: закон контрапозиции 1) В, А ⊢ В 10 В ⊢ АВ 2) В ⊢ АВ 1), ТД ТД 3) А В ⊢ В 2), конт. В , АВ 4) АВ ⊢В

Слайд 30

Описание слайда:

Lemma 3 (введение &) А,В ⊢АВ Анализ: А, В⊢ А В Д-во: закон контрапозиции 1) А, АВ⊢В (МР) А, АВ⊢В 2) А, В⊢ А В 1), контр. 3) А,В ⊢АВ

Слайд 31

Описание слайда:

Lemma 4 (введение V) А ⊢АvB Анализ: А ⊢ А В Д-во: ТД 1) А, В А 10 А, А ⊢ В 2) А , АВ 1),конт. контр. 3) А ⊢ АВ 2), ТД А, В ⊢ А 4) А ⊢АvB Lemma 5 (введение V) В ⊢АvB (ВvA)

Слайд 32

Описание слайда:

Lemma 6 (удаление v) Если А ⊢С, В ⊢С, то АvB⊢С Д-во: А ⊢С – дано С⊢А 1), контр. В ⊢С – дано С⊢В 3), контр. А,В ⊢А∙В (А В) введ. & С⊢ А В 2),4),5),40 А В ⊢С 6), контр. АvB⊢С

Слайд 33

Описание слайда:

Слайд 34

Описание слайда:

Доказать: АvBC(AvB) ∙(AvC) Анализ: вв. & АvBCAvB, АvBCAvC уд. V уд. V АAvB, BCAvB АAvC, BCAvC уд. & уд. & B,CAvB B,CAvC Д-во: АAvB (вв. v) B,CAvB (вв. v) BCB (уд. &) BCC (уд. &) BCAvB (2), 3),40) АvBCAvB (5), уд.&) АAvC (вв. v) 10) АvBCAvC (7), 9), уд. v) B,CAvС (вв. v) 11) АvB, AvC(AvB) ∙(AvC) (10), вв. &) BCAvC (8), уд.&) 12) АvBC(AvB) ∙(AvC) (6), 10),11),40)