Полнота, непротиворечивость исчисления высказываний

1.

Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет
имени М. Т. Калашникова»
Кафедра «АСОИУ»
Курс «Математическая логика и теория алгоритмов»
Тема «ПОЛНОТА, НЕПРОТИВОРЕЧИВОСТЬ
ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ»
Автор Исенбаева Е.Н., старший преподаватель
Ижевск
2013

2.

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Теорема1.
Всякая теорема исчисления
высказываний является
тождественно истинным
высказыванием.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
2

3.

СПОСОБЫ ПРОВЕРКИ ИСТИННОСТИ АКСИОМ
Тождественная истинность аксиом
проверяется:
• прямым вычислением на всех
наборах переменных;
• приведением их к константе 1
путем тождественных
преобразований булевой алгебры.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
3

4.

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Любая подстановка в
тождественно истинную
формулу также дает
тождественно-истинную
формулу.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
4

5.

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Покажем, что правило заключения сохраняет тождественную
истинность.
Пусть формулы α и α
β тождественно-истинны, то есть
то есть формула β выводимая из α и α
β по правилу m.p.
тоже тождественно-истинна.
ВЫВОД: аксиомы тождественно-истинны, правила вывода
сохраняют тождественную истинность→ любая доказуемая
формула тождественно-истинная.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
5

6. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

Справедлива и обратная теорема.
Теорема 2. Всякая тождественно-истинная
формула является теоремой исчисления
высказываний.
Исчисление высказываний выполняет задачу
порождения общелогических законов –
тождественно-истинных высказываний.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
6

7.

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Эквивалентные соотношения булевой алгебры
соединяются знаком «=» формулы, которые, которые
одновременно равны «0» или «1».
В логике такая равнозначность выражается
функцией «<=>».
Если f1=f2 - эквивалентное соотношение, то
формула
является тождественно-истинным
высказыванием.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
7

8.

ПОЛНОТА АКСИОМАТИЧЕСКОЙ ТЕОРИИ
Полнота аксиоматической теории – это
такое ее свойство, заключающееся в том,
что если формула A выражает какой-либо
логический закон, как тождественноистинная формула, то она выводима в этой
теории (полнота в широком смысле).
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
8

9.

ТЕОРЕМА ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
Теоремами исчислений высказываний являются все
эквивалентности алгебры логики.
Пример:
1.
2.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
9

10.

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
ТЕОРЕМА 3.
Исчисление высказываний – это полная
аксиоматическая теория.
Непротиворечивой называется
аксиоматическая теория, если не существует
формулы A такой, что
одновременно выводимы формулы А и .
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
10

11.

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
ТЕОРЕМА 4. Исчисление высказываний
непротиворечиво.
Доказательство:
Согласно теореме 1 всякая выводимая
формула тождественно истинна. Отрицание
этой формулы не является тождественноистинной формулой. Следовательно, ни для
какой формулы А невозможно,
чтобы одновременно ├А и ├
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
11

12.

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Полной в узком смысле называется
формальная аксиоматическая теория ,
если добавлением любой не выводимой
формулы в качестве схемы аксиом
приводит к противоречивости теории.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
12

13.

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Теорема 5. Исчисление высказываний – это
аксиоматическая теория, полная в узком смысле.
Аксиоматическая теория разрешима,
если существует алгоритм, который для любой
формулы определяет, является ли она теоремой в
этой теории или нет.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
13

14. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

Теорема
6
ИСЧИСЛЕНИЕ
ВЫСКАЗЫВАНИЙ
Теорема 6. Исчисление высказываний
разрешимо.
Разрешающий алгоритм для
формулы F исчисления высказываний
заключается в вычислении значений F на всех
наборах значений ее переменных. Ввиду полноты
исчисления высказываний F является его
теоремой, если и только если она истинна на всех
наборах.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
14

15.

АЛГОРИТМЫ ПРОВЕРКИ ОБЩЕЗНАЧИМОСТИ
Алгоритм Квайна.
Формула φ от пропорциональных
переменных A1, A2,…, Ak является тождественноистинной (доказуемой), если булева функция fφ этой
формулы равна 1.
Для проверки значений функции fφ используется
семантическое дерево(бинарное дерево),
удовлетворяющее следующим условиям:
1) каждое ребро помечено литерой А;
2) литеры, выходящие из одной вершины контрарны:
А и ¬А;
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
15

16.

АЛГОРИТМЫ ПРОВЕРКИ ОБЩЕЗНАЧИМОСТИ
Алгоритм Квайна.
3) семантическое дерево имеет 2k висящих
вершин и для проверки общезначимости
необходимо пройти 2k маршрутов от корня до
этих вершин;
4) ребра соответствуют литере одной и той же
пропозициональной переменной А тогда и только
тогда, когда они находятся на одинаковом
расстоянии до корня.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
16

17.

ПРИМЕР
Проверить общезначимость формулы:
φ=(((A&B) → C)&(A→ B)) → (A → C)
1. Упорядочим переменные (A,B,C).
2. Придадим первой переменной A=1. Тогда формула
преобразится: (((1&B) → C)&(1 → B)) → (1 → C)
3. Придадим значение переменной B=1:
(((1&1) → C)&(1 → 1)) → (1 → C) = C → C = 1
Формула общезначима.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
17

18.

ПРИМЕР
4. Придадим значение переменной B=0:
((0 → C)&0) → C = 0 → C = 1
Тоже общезначимая формула.
5. В случае А=0:
(((0&B) → C)&(0 → B)) → (0 → C)=(1&1) →1=1Общезначимая формула.
Все возможные случаи привели к тождественноистинным формулам → исходная формула
тождественно-истинная.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
18

19.

АЛГОРИТМЫ ПРОВЕРКИ ОБЩЕЗНАЧИМОСТИ
Алгоритм редукции
Решает ту же задачу, что и алгоритм Квайна.
Используется, когда в формуле содержится
достаточно много импликаций.
Идея: попытка найти значения пропорциональных
переменных формулы, при которых значение ее
равно 0, на основании того, что импликация
является ложной в том и только в том случае, когда
посылка истинна, а заключение ложно.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
19

20.

АЛГОРИТМЫ ПРОВЕРКИ ОБЩЕЗНАЧИМОСТИ
Пример: Проверить тождественную истинность
формулы: ((А & В)→ С) → (А → (В → С)).
Предположим, что формула ложна на некотором
наборе переменных А,В,С. Тогда:
((А&В) → С)=1
(А → (В → С))=0
Из равенства 2 получаем А=1; В → С=0.
Откуда В=1; С=0. При этих значениях равенство 1
(А&В) → С=0. Получаем противоречие. Т.о.,
исходная формула тождественно-истинная.
Курс «Математическая логика и теория алгоритмов»
«Полнота, непротиворечивость исчисления высказываний»
20

21. Спасибо за внимание

© ФГБОУ ВПО ИжГТУ имени М.Т. Калашникова, 2013
© Исенбаева Елена Насимьяновна, 2013