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

1.

Модуль 3
Формальные теории и
исчисления
Занятие 3.2. Исчисление
высказываний
2020 г.

2.

Содержание
1.
2.
3.
4.
5.
6.
7.
Алфавит
Формулы
Аксиомы
Правило вывода
Правило подстановки
Теорема дедукции
Свойства исчисления высказываний

3.

.
Алфавит
связки
,
служебные символы ( , )
пропозициональные переменные
a, b,…a1, b1,…

4.

Формулы
1. Переменные суть формулы
2. Если А, В формулы, то
( A ), ( A B ) - тоже формулы

5.

Аксиомы
A1 : ( A ( B A))
A2 : (( A ( B C ))
(( A B ) ( A C )))
A3 : (( B A) (( B A) B ))

6.

Правило вывода
A, A B
Modus _ ponens
B
правило отделения или
правило заключения (MP)

7.

Интерпретация
Функция h называется интерпретацией,
если для любых формул А и В исчисления
высказываний h удовлетворяет
следующим условиям
h( A) h( A)
h( A B ) h( A) h( B )

8.

Истинность и ложность
Формула А исчисления
высказываний истинна при
некоторой интерпретации h тогда
и только тогда, когда h(A)=1
В противном случае, говорят, что
А ложна при интерпретации h

9.

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

10.

Пример № 1
Проверить, что формула R
является тавтологией
R ( A B) A B

11.

Решение примера № 1
R ( A B) A B
A
0
0
1
1
B
0
1
0
1
R
1
1
1
1
Формула R - тавтология

12.

Правило подстановки
Пусть А – некая формула, выводимая
(доказуемая) в исчислении
высказываний, х- переменная,
В – любая формула исчисления
высказываний
Тогда формула, которая получается из
формулы А путем подстановки в нее
вместо переменной х формулы В,
выводима (доказуема)
А(……х…..)(B//x)

13.

Пример № 2
Проверить, что формула
выводима в исчислении
высказываний
А→А

14.

Решение примера № 2
1. Подставим в аксиому А2 вместо В
(А→А), вместо С подставим А
( A (( A A) A)) (( A ( A A)) ( A A))
2. Применив аксиому А1, и по правилу
заключения получаем
( A ( A A)) ( A A)
3. Применив аксиому А1 и по правилу
заключения получаем ( A A)

15.

Теорема
Каждая формула,
доказуемая в исчислении
высказываний,
тождественно истинна в
алгебре высказываний

16.

Пример № 3
Каждая аксиома – тождественно истинная
Правило подстановки, примененное к
тождественно истинным формулам,
приводит к тождественно истинным
формулам
Правило заключения, примененное к
тождественно истинным формулам,
приводит к тождественно истинным
формулам

17.

Теорема дедукции
Если Г – множество формул,
А и В – формулы из Г высказываний,
и А├В, то Г├А→В, т.е. в Г выводима
формула
А→В

18.

Пример № 4
Проверить, что из А→В, В→С
формула А→С выводима в
исчислении высказываний, т.е.
А→В, В→С ├ А→С

19.

Решение примера № 4
1.
А→В –гипотеза
2.
В→С - гипотеза
3.
А - тоже гипотеза
4.
В выводимо по правилу заключения из
5.
6.
п. 1 и п. 3
С выводимо по правилу заключения из
п. 2 и п. 4
Следовательно, А→В, В→С А├С, и , по
теореме о дедукции, А→В, В→С ├А→С

20.

Разрешимость и
независимость
Проблема разрешимости для
исчисления высказываний
разрешима
Система аксиом исчисления
высказываний независима

21.

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

22.

Исчисление высказываний
по Гильберту и Аккерману
Связки
, ( A B A B)
A A A
A В В A
A A В
(В С ) ( A В A С )
Правило вывода МР
Аксиомы

23.

Свойства исчисление
высказываний (ИВ)
Исчисление высказываний:
Разрешимо
Полно
Непротиворечиво
Система аксиом ИВ независима
Интерпретацией
ИВ
являются
алгебра
высказываний (АВ) и алгебра Буля (АБ)
Выводимые формулы
истинны в АВ и АБ
в
ИВ
тождественно