Презентация на тему: Логические цепи «И» – конъюнктор «ИЛИ» – дизъюнктор «НЕ» – инвертор Рис. 1

Логические цепи «И» – конъюнктор «ИЛИ» – дизъюнктор «НЕ» – инвертор Рис. 1.
Пример: построить комбинационную схему, реализующую функцию f, заданную таблицей истинности:
Логические цепи «И» – конъюнктор «ИЛИ» – дизъюнктор «НЕ» – инвертор Рис. 1.

Исчисление высказываний (ИВ)
Построение исчисления высказываний
II. Определение формулы исчисления высказываний ( п.п.ф. ):
III. Аксиомы
Пример: (А1): А  ( В  А );
IV. Правило вывода ( modus ponens )
V. Вывод формулы А (формальное доказательство)
Примеры выводимых формул 1. ├ А  А
1. ├ А  А
2. ├  ( А  B )
2. ├  ( А  B )
3. ├
3. ├
4. ├
4. ├
5. ├
Вывод формул из гипотез
Пример:
Свойства вывода формул из гипотез.
Свойства вывода формул из гипотез.
Теорема дедукции
1/25
Средняя оценка: 4.3/5 (всего оценок: 39)
Код скопирован в буфер обмена
Скачать (247 Кб)
1

Первый слайд презентации

Логические цепи «И» – конъюнктор «ИЛИ» – дизъюнктор «НЕ» – инвертор Рис. 1. Элементы «И», «ИЛИ», «НЕ»

Изображение слайда
2

Слайд 2: Пример: построить комбинационную схему, реализующую функцию f, заданную таблицей истинности:

x y z f 0 0 0 1  0 0 1 1  f 0 1 0 1  0 1 1 0 1 0 0 1  1 0 1 0 1 1 0 1  1 1 1 1  C ДНФ: – 10 элементов;        –      6 элементов (рис.2) СКНФ: – 6 элементов;  – 7 элементов (рис. 3)

Изображение слайда
3

Слайд 3

Изображение слайда
4

Слайд 4: 

Изображение слайда
5

Слайд 5: Исчисление высказываний (ИВ)

План построения формальных теорий: задается алфавит; дается определение формулы; некоторые из формул объявляются аксиомами; формулируются правила вывода; дается определение вывода формулы (формального доказательства); дается определение выводимой формулы (теоремы).

Изображение слайда
6

Слайд 6: Построение исчисления высказываний

I. Алфавит : x, y, …, z,..., А, В, … – пропозициональные переменные; ,  – логические связки; (, ) – технические символы.

Изображение слайда
7

Слайд 7: II. Определение формулы исчисления высказываний ( п.п.ф. ):

каждая пропозициональная переменная является п.п.ф.; если А – п.п.ф. ( ИВ ), то (  А ) – п.п. ф. ( ИВ ); если А и В – п.п. формулы ( ИВ ), то ( А  В ) – тоже п.п. формула ( ИВ ); никаких других п.п. ф. ( ИВ ), кроме получающихся согласно п.п.1–3, нет.

Изображение слайда
8

Слайд 8: III. Аксиомы

(А1): А  ( В  А ); (А2): А  ( В  С )  (( А  В )  ( А  С )) – закон самодистрибутивности импликации; (А3): – закон контрапозиции.

Изображение слайда
9

Слайд 9: Пример: (А1): А  ( В  А );

(А1): ( x  y )  (( ( z  x ))  ( x  y )) – сделаны замены А=( x  y ), В= ( z  x ).

Изображение слайда
10

Слайд 10: IV. Правило вывода ( modus ponens )

( MP ):

Изображение слайда
11

Слайд 11: V. Вывод формулы А (формальное доказательство)

VI. ├ А ИСЧИСЛЕНИЕ содержит выводимые формулы (теоремы)

Изображение слайда
12

Слайд 12: Примеры выводимых формул 1. ├ А  А

├ x  (y  z)  ((x  y)  (x  z)) (A2) A  ((B  A)  A)  ((A  (B  A))  (A  A)) A1 A1

Изображение слайда
13

Слайд 13: 1. ├ А  А

1)├A  ((B  A)  A)  ((A  (B  A))  (A  A)) …......… (A2) A1 A1 2)├A  ((B  A)  A) …………………………………….... (A1) 3)├(A  (B  A))  (A  A) ………………………………..из 1), 2) по (MP) 2) – малая посылка, 1) – большая посылка 4)├ A  ( B  A )…………………………………………….( A 1) 5)├ A  A …………………………………………………..из 3), 4) по ( MP ) 4) – малая посылка, 3) – большая посылка

Изображение слайда
14

Слайд 14: 2. ├  ( А  B )

├ x  (y  z)  ((x  y)  (x  z)) (A2)  (( )  (A  B))  ((  ( ))  (  (A  B)) ) А3 А1

Изображение слайда
15

Слайд 15: 2. ├  ( А  B )

1)├ ( A 2) 2)├ ……………………………………………….( A 3) 3)├ ( A 1) 4)├ ……………….из 2) 3) по ( MP ) 5)├ ……………... из 1), 4) по ( MP ) 6)├ ………………………………………………...( A 1) 7)├ ………………………………………..из 5), 6) по ( MP )

Изображение слайда
16

Слайд 16: 3. ├

├ x  (y  z)  ((x  y)  (x  z)) (A2) А3

Изображение слайда
17

Слайд 17: 3. ├

1)├ ………….( A 2) 2)├ …………………………..……………………...( A 3) 3)├ ( A 1) 4)├ ………………...из 2), 3) по ( MP ) 5)├ ………………………...из 1), 4) по ( MP ) 6)├ ………...…….……………………….….(2 пример – 7 формул) 7)├ ………………………………………………..из 5), 6) по ( MP ) ├ x  (y  z)  ((x  y)  (x  z)) (A2)

Изображение слайда
18

Слайд 18: 4. ├

├ x  (y  z)  ((x  y)  (x  z)) (A2)

Изображение слайда
19

Слайд 19: 4. ├

1)├ ……………………………………(А2) 2)├ …………………………………3 пример – 13 формул 3)├...….………………………………...из 1), 2) по ( MP ) 4)├......………………………………………..1 пример – 5 формул 5)├ ……………………………………………….. из 3), 4) по ( MP )

Изображение слайда
20

Слайд 20: 5. ├

1)├ ………………………………………………..(А3) 2)├ ………………………………………….4 пример – 21 формула 3)├ ……………………………………………… из 1), 2) по ( MP ) ├ (А3)

Изображение слайда
21

Слайд 21: Вывод формул из гипотез

Опр. Выводом формулы А из множества гипотез Г называется конечная последовательность формул F 1, F 2, …, F k, заканчивающаяся формулой А ( F k = A ) и каждая формула в этой последовательности является или аксиомой, или гипотезой, или получена из двух предыдущих по правилу ( MP ). Обозн. Г├ А (из Г выводима А)

Изображение слайда
22

Слайд 22: Пример:

построить вывод формулы С из гипотез: А, А  В, В  С. 1) А гип.1; 2) А  В гип.2; 3) В  С гип.3; 4) В (МР) к 1), 2) 5) С (МР) к 3), 4).

Изображение слайда
23

Слайд 23: Свойства вывода формул из гипотез

1 . Г, А├А (свойство самовыводимости). 2 . Если Г├А, то Г, В├А, где В – любая формула (расширение списка гипотез). 3 . Г, В├А и Г├В, то Г├А (выводимые гипотезы можно исключать из списка гипотез, при этом выводимость данной формулы не нарушается).

Изображение слайда
24

Слайд 24: Свойства вывода формул из гипотез

4 . Если из Г├А и А├В, то Г├В ( свойство транзитивности вывода). 5 . Если из Г, А, А├В, то Г, А├В (свойство сокращения). 6 . Если из Г, А, В├С, то Г, В, А├С (свойство коммутативности).

Изображение слайда
25

Последний слайд презентации: Логические цепи «И» – конъюнктор «ИЛИ» – дизъюнктор «НЕ» – инвертор Рис. 1: Теорема дедукции

Т. Если Г, А├В, то Г├А  В. Дано: вывод формулы В из Г, А.: (1) F 1, F 2, …, F n = B. Доказать: формула А  В выводима из множества гипотез Г. Доказательство: (2) А  F 1, А  F 2, …, А  F n =А  B. Г, А├В Г├А  В

Изображение слайда