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

Содержание
Алфавит
Формулы
Аксиомы
Правило вывода
Правило подстановки
Теорема дедукции
Свойства исчисления высказываний

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

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

Аксиомы

Правило вывода
правило отделения или правило заключения (MP)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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