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

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

2.

Лемма 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 ;

3.

4. x ( ) x , где – символ одной
из операций , ;
5. x ( ) x , где – символ одной из
операций , ,
если в формулу предметная переменная x не
входит свободно.

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

5.

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

6.

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

7.

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

8.

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

9.

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

10.

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

11.

Алгоритм приведения формулы к ПНФ:
1) преобразуем формулу в эквивалентную ей
формулу , которая не содержит импликации и
эквивалентности и в которой отрицание
действует только на элементарные формулы;
2) в все кванторы последовательно выносим
вперед по теореме 5, при этом кванторы
общности x выносятся из конъюнкции и
кванторы существования x выносятся из
дизъюнкции, а для выноса кванторов общности
x из дизъюнкции и кванторов существования
x из конъюнкции переименовываем связанные
переменные x в новые переменные y, которые не
входят в рассматриваемую формулу.

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

13.

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

14.

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

15.

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

16.

Основные правила логического следования:
1) правило отделения (или правило модус поненс –
от латинского modus ponens)
, | ;
2) правило модус толленс (от латинского modus
tollens)
, | ;
3) правило контрапозиции
| ;
4) правило цепного заключения
1 2 , 2 3 | 1 3 .

17. Формальные исчисления

18.

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

19.

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

20.

В этом случае полностью отвлекаются от
содержания логических формул, и построение
математической логики осуществляется в виде
некоторого формального исчисления I, которое в
общем случае определяется следующим образом:
1) задается алфавит исчисления A(I), который
состоит из основных символов исчисления I, и
рассматривается множество W(I) всех слов над
этим алфавитом;
2) выделяется подмножество
E(I) W(I)
правильно построенных формул исчисления I;
3) задается подмножество Ax(I) E(I) аксиом
исчисления I;

21.

4) рассматривается конечное множество R(I)
частичных операторов R1, ,…, Rn на множестве
формул E(I), которые называются правилами
вывода исчисления I;
5) описывается алгоритм вывода из аксиом теорем
исчисления I;
6) множество всех таких теорем образует теорию
Th(I) формального исчисления I, которая
называется также аксиоматической теорией с
множеством аксиом Ax(I).

22.

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

23.

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

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

25.

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

26.

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

27.

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

28.

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

29.

Пример.
Для
любой
формулы
следующее утверждение:
| .
справедливо