Лекция 12_2гр

1. Интерпретации формул алгебры предикатов

2.

Область интерпретации – непустое множество
M, которое является областью возможных
значений всех предметных переменных.
P
n-местным
предикатным
символам
присваиваются конкретные значения PM nместных предикатов на множестве M.
P PM
Соответствие
:
называется
интерпретацией предикатных символов.
Область
интерпретации
M
вместе
с
интерпретацией
предикатных
символов
называется интерпретацией формул алгебры
предикатов и обозначается (M , ) или просто M.

3.

При наличии интерпретации M конкретные
значения предметным переменным формул
алгебры
предикатов
присваиваются
с
помощью отображения множества всех
предметных переменных X в область
интерпретации M.
Такие отображения называются оценками
предметных переменных.

4.

Выполнимость формулы в интерпретации M
при оценке обозначается M | - читается
«формула истинна в интерпретации M при
оценке » и определяется следующим образом:
1) если P x1 ,..., xn для n-местного предикатного
символа P и предметных переменных x1 ,..., xn ,
то M | тогда и только тогда, когда
высказывание PM ( x1 ),..., ( xn ) истинно;
2) если для формулы , то M | тогда
и только тогда, когда неверно, что M | ;
3) если 1 2 для формул 1 , 2 , то M |
тогда и только тогда, когда M | 1 и M | 2 ;

5.

4) если 1 2 для формул 1 , 2 , то M | тогда
и только тогда, когда M | 1 или M | 2 ;
5) если 1 2 для формул 1 , 2 , то M |
тогда и только тогда, когда неверно, что M | 1 и
M | 2 ;
6) если 1 2 для формул 1 , 2 , то M |
тогда и только тогда, когда M | 1 , M | 2
одновременно верны или нет;
7) если x для некоторой формулы , то M |
тогда и только тогда, когда M | для всех оценок
, отличающихся от оценки возможно только на
элементе x;
8) если x для некоторой формулы , то M |
тогда и только тогда, когда M | для некоторой
оценки , отличающейся от оценки возможно
только на элементе x.

6.

7. Классификация формул алгебры предикатов

8.

Определение. Формула называется тождественно
истинной, если она тождественно истина в любой
интерпретации M. Такая формула называется также
общезначимой формулой, или тавтологией алгебры
предикатов и обозначается | . Множество всех
тавтологий алгебры предикатов обозначим TАП. .
Определение. Формула называется тождественно
ложной или противоречием, если она тождественно
ложна в любой интерпретации M.
По определению противоречивость формулы
равносильна условию | .
Определение. Формула называется выполнимой, если
она выполнима хотя бы в одной интерпретации M,
которая называется моделью этой формулы.

9.

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

10. Тавтологии алгебры предикатов

11.

Любая тавтология алгебры высказываний
является тавтологией алгебры предикатов.
Более того, тавтологии алгебры высказываний
дают возможность легко получать тавтологии
алгебры предикатов с помощью следующего
очевидного результата.
Лемма 1. Если X 1 ,..., X n – тавтология
алгебры высказываний, то для любых формул
алгебры предикатов 1 ,..., n формула 1 ,..., n
является тавтологией алгебры предикатов.

12.

С другой стороны, в алгебре предикатов можно
получить много принципиально новых тавтологий с
помощью следующих свойств кванторов.
Лемма 2. Для любых формул , следующие
формулы являются тавтологиями:
1. x x , x x ,
x x , x x ;
2. x y y x , x y y x ;
3. x ( ) x x ,
x ( ) x x ;

13. Логическая равносильность формул алгебры предикатов

14.

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

15.

Теорема 1 (Взаимосвязь между кванторами).
Для любой формулы справедливо равенство:
x y y x , x y y x .
С другой стороны, если в формулу
предметные переменные x,y входят свободно,
то равенство
y x x y
не выполняется, так как в этом случае формула
y x x y
не является тавтологией.

16.

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

17.

Теорема 3 (Законы де Моргана для кванторов). Для
любой
формулы
справедливы
следующие
утверждения:
x x , x x ,
x x , x x .
Теорема 4 (Взаимосвязь кванторов с конъюнкцией и
дизъюнкцией). Для любых формул , справедливы
следующие утверждения:
x ( ) x x ,
x ( ) x x .
Если в формулу предметная переменная x не входит
свободно, то справедливы также утверждения:
x x , x x , где
– символ одной из операций , .

18.

Следствие
7.
Любая
формула
представляется в следующем виде:
K1 x1 ... K n xn ,
где K1 ,..., K n – некоторые кванторы и –
формула без кванторов.
Таким образом, каждая формула логически
равносильна формуле K1 x1 ... K n xn , в которой
все кванторы стоят в самом начале формулы и
которая называется предваренной нормальной
формой (сокращенно ПНФ) формулы .

19. Логическое следование формул алгебры предикатов

20.

С помощью логического следования формул
определяются общие способы доказательства
взаимосвязи между истинностными значениями
утверждений
посредством
исследования
формальной структуры этих утверждений.
Определение. Формула алгебры предикатов
называется логическим следствием формулы ,
если | , т.е. в любой интерпретации M
формула истинна при любой оценке предметных
переменных , при которой истинна формула .

21.

Определение.
Формула
называется
логическим следствием множества формул ,
если в любой интерпретации M формула
истинна при любой оценке предметных
переменных , при которой истинны все
формулы из .
Такое логическое следствие обозначается
| и называется логическим следованием.
При этом формулы из называются посылками
и формула – следствием логического
следования | .
В случае, когда { 1 ,..., m } записывают
1 ,..., m | .

22.

Определение. Множество формул называется
противоречивым, если из него логически следует
любая (в том числе и тождественно ложная)
формула . Символически это записывается | .
Лемма 1 (Критерии логического следования).
Условие 1,..., m |
равносильно каждому из
следующих условий:
1 ... m | ,
a)
b) | 1 ... m ,
1 , , m , | .
c)
| .
В частности, | равносильно
Отсюда также следует, что равносильно
тому, что | и | .

23. Проблема общезначимости формул алгебры предикатов

24.

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

25.

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

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

27.

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

28.

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

29.

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

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

31.

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

32.

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

33.

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

34.

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