Похожие презентации:
Полнота, непротиворечивость исчисления высказываний
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