Лекция 10_3гр (1)

1. Аксиоматический метод

2.

Было определено множество формул алгебры
высказываний FАВ
Затем было выделено подмножество этого
множества TАВ FАВ, состоящие из специальных
формул – тавтологий.
При этом в основе определения тавтологии
лежит понятие интерпретации формул, т.е.
придание
некоторого
конкретного
содержательного смысла входящих в них
переменных. Такой подход к логическим
формулам носит теоретико-множественный
характер и называется семантическим.

3.

Альтернативой семантического подхода
является синтаксический подход, при котором
логические
формулы
выводятся
из
первоначально
выделенного
множества
формул – аксиом по определенным правилам
преобразования формул логического языка
без привлечения вспомогательных теоретикомножественных понятий.
.

4.

Построение математических теорий в виде
аксиоматических теорий соответствующих
формальных исчислений составляет суть
аксиоматического метода в математике.
Простейшей
аксиоматической
теорией
является
аксиоматическая
логика
высказываний, которая строится на основе
соответствующего формального исчисления,
называемого
исчислением
высказываний
(сокращенно, ИВ).

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

6.

7.

Исчисление высказываний имеет единственное
правило вывода, которое называется правилом
заключения или правилом modus ponens (сокращенно
MP) и которое для произвольных формул
исчисления высказываний , определяется по
формуле MP , .
Символически это правило вывода записывается
следующей схемой:
,
MP :
.

8.

В основе алгоритма вывода теорем исчисления
высказываний лежит следующее понятие.
Определение. Формула называется теоремой
исчисления высказываний, если найдется такая
конечная последовательность формул 1 ,..., n , в
которой:
1) n = ;
2) каждая формула i 1 i n либо является
аксиомой, либо получается из некоторых двух
предыдущих формул j , k 1 j, k i по
правилу вывода MP.
Последовательность формул 1 ,..., n называется
выводом или доказательством формулы .

9.

Вывод формулы сокращенно обозначают
символом | и говорят, что « есть теорема».
Множество всех таких теорем обозначается
символом Th(ИВ) и называется теорией
исчисления высказываний.
Главной целью построения исчисления
высказываний является определение такой
теории Th(ИВ), которая совпадает с множеством
тавтологий TАВ.

10.

Лемма.
Справедливы следующие утверждения:
1)всякая аксиома ИВ является тавтологией;
2)результат применения правила вывода MP
к любым тавтологиям , дает
тавтологию ;
3)всякая теорема ИВ является тавтологией,
т.е. выполняется Th(ИВ) TАВ.

11.

Теорема полноты ИВ.
Всякая тавтология является теоремой ИВ,
т.е. выполняется TАВ Th(ИВ) и, следовательно,
TАВ=Th(ИВ).

12.

13.

Следствия теоремы полноты ИВ.
Теорема о непротиворечивости ИВ.
В исчислении высказываний невозможно
доказать никакую формулу вместе с ее
отрицанием .
Теорема о разрешимости ИВ.
Существует универсальная эффективная
процедура (алгоритм), которая для любой
формулы определяет, является ли эта формула
теоремой ИВ.

14. Исчисление предикатов

15.

Множество аксиом Ax(ИП) исчисления
предикатов описывается пятью схемами аксиом
– тремя определенными в предыдущем разделе
схемами A1 A3 , в которых , , i i 1,2,3
являются
произвольными
формулами
исчисления предикатов, и двумя новыми
схемами:
( A4 ) x ( x) ( y )
для произвольной формулы (x), в которую y
не входит связно;
A5 x ( x) x ( x)
для таких формул , , что x в формулу не
входит свободно.

16.

Исчисление предикатов имеет два правила
вывода – правило modus ponens (сокращенно,
MP) и правило обобщения (сокращенно, Gen),
которые для произвольных формул исчисления
предикатов , символически записываются
следующими схемами:
,
Gen :
MP :
и
x .

17.

Определение. Формула называется теоремой
исчисления предикатов, если найдется такая
последовательность 1 ,..., n , в которой n = и
каждая формула i 1 i n либо является
аксиомой,
либо
получается
из некоторых
предыдущих формул этой последовательности
j 1 j i по одному из правил вывода MP или
Gen. При этом 1 ,..., n называется выводом или
доказательством формулы .
Вывод формулы обозначают | и говорят,
что « есть теорема». Множество всех таких теорем
обозначается символом Th(ИП) и называется
теорией исчисления предикатов.

18.

Цель построения исчисления предикатов определение такой теории Th(ИП), которая
совпадает с множеством тавтологий TАП.
Лемма 1.
Справедливы следующие утверждения:
1)всякая аксиома ИП является тавтологией;
2)результат применения правил вывода MP и
Gen к тавтологиям является тавтологией;
3)любая теорема ИП является тавтологией
ИП, т.е. имеет место включение
Th(ИП) TАП.

19.

Доказательство TАП Th(ИП) было получено
австрийским математиком К.Геделем в 1930
году.
Теорема полноты ИП.
Формула исчисления предикатов в том и
только том случае является тавтологией, если
она есть теорема ИП, т.е. выполняется
равенство TАП=Th(ИП).
Таким образом, ИП является адекватным
инструментом получения логических законов.

20.

Теорема о непротиворечивости ИП.
В исчислении предикатов невозможно
доказать никакую формулу вместе с ее
отрицанием .
С другой стороны, английский математик
А.Черч в 1936 году доказал следующий
принципиально важный результат.
Теорема о неразрешимость ИП.
Не существует универсальной эффективной
процедуры (алгоритма), которая для любой
формулы определяет, является ли эта формула
теоремой ИП.

21. Элементы теории алгоритмов

22.

Важные математические проблемы имеют вид:
для некоторого данного множества X найти
эффективную процедуру (т.е. алгоритм), с помощью
которой можно для каждого элемента x этого
множества X определить за конечное число шагов,
будет этот элемент обладать некоторым данным
свойством P или нет (т.е.
или
).
Решением такой проблемы является построение и
обоснование искомого алгоритма.
Массовые задачи – задачи распознавания и
оптимизации.

23.

Примеры массовых задач:
ВЫП (SАТ) –
задача выполнимости
формулы логики высказываний.
ТЕОРЕМА (THM) – задача доказуемости
формулы логики предикатов.

24. Унификация распознавательных задач

25.

Распознавательная
задача
называется
алгоритмически
разрешимой или алгоритмически неразрешимой в зависимости от
того, имеется или нет алгоритм решения этой задачи.
Конструктивные объекты любого множества X можно
кодировать словами конечного множества (например, состоящего
из двоичных символов 0 и 1) с помощью взаимно-однозначного
отображения
, где
- множество всех конечных
последовательностей символов алфавита
Элементы множества
множества
.
называются словами и подмножества
называются языками над алфавитом

26.

Кодировка экземпляров ВЫП
Используется следующий код для алфавита
.
1. Символы , , , и скобки (,) представляют самих себя.
2. Переменная Xi представляется символом X с дописанной к нему
последовательностью нулей и единиц — двоичной записью числа i.
Таким образом, алфавит
проблемы-языка ВЫП содержит
всего восемь символов
. Все экземпляры ВЫП
являются конечными последовательностями символов - словами в
этом фиксированном конечном алфавите.

27.

Произвольная распознавательная задача универсально
формулируется следующим образом:
имеется множество слов
над некоторым
алфавитом
и определенный язык
найти эффективную процедуру (т.е.
помощью которой для любого слова
определить
или
.
,
требуется
алгоритм), с
можно