Формальные теории и исчисления. Модуль 3 презентация

Содержание
Алфавит исчисления предикатов
Формулы исчисления предикатов
Аксиомы исчисления предикатов
Правила вывода исчисления предикатов
Свойства исчисления предикатов

Алфавит
связки основные
вспомогательные
служебные символы ( , )
кванторы всеобщности
существования
предметные константы a, b,…a1, b1,
переменные x,y,….x1,y1
предметные предикаты P, Q, R, ….
функторы f, g, h,….
.

Формулы
<формула> ::= <атом>│ │<формула> <формула>│
│<переменная><формула>│ │переменная><формула>
<атом>::= <предикат>( <список термов> )
<список термов> ::= <терм> │<терм> , <список термов>
<терм>::= <константа> │<переменная>│
│<функтор>(<список термов>)

Аксиомы
И все аксиомы исчисления высказываний

Аксиомы

Правила вывода!!!!!
Правило обобщения

Равносильные формулы
1.Равносильности для двойственности
2.Равносильности для конъюнкции и квантора всеобщности
3.Равносильности для дизъюнкции и квантора существования
4. Вынесение константы

Равносильности для двойственности

Равносильности для &

Равносильности для V

Вынесение константы

Пример №1
Показать равносильность формулы

Решение примера №1
Если предикаты P(x) и Q(x) тождественно истинны, то тождественно истинен предикат , а поэтому, будут истинны высказывания
2. Если один из предикатов, например, P(x), будет не тождественно истинен, то предикат не будет тождественно истинен, следовательно, ложными будут высказывания

Решение примера №1
Если оба предиката P(x) и Q(x) не будут тождественно истинны, то не будет тождественно истинен предикат Следовательно, будут ложными высказывания
4. Следовательно, обе части равносильности равны при любых значениях P(x) и Q(x)

Общезначимость и выполнимость
Формула А выполнима в области М, если существуют значения переменных, входящих в эту формулу и отнесенных к области М, при которых формула принимает и истинные значения
Формула А выполнима, если существует область, на которой она выполнима

Общезначимость и выполнимость
Формула А тождественно истинна в области М, если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области
Формула А тождественно ложна в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области
Формула А общезначима, если она тождественно истинна во всякой области

Общезначимость и выполнимость
Если формула А общезначима, то она и выполнима на любой области
Если формула А тождественно истинна в области М, то она и выполнима в этой области
Если формула А невыполнима, то она тождественно ложна в любой области

Пример № 2
Показать общезначимость правила обобщения квантора всеобщности

Решение примера № 2
1.
2.
3.
Так как формула R тождественно истинна в любой области, значит она общезначима