Кванторы и связанные переменные

 

Все формулы логики высказывания являются частными случаями логики предикатов. Все операции логики высказывания переносятся в логику предикатов для связывания предметных букв. Дополнительно используются обозначения кванторов:

"x F(х), т.е. «Все х обладают свойством F»;

"$x F(х), т.е. «Некоторые х обладают свойством F (но возможно и все)»,

где "– квантор общности, $– квантор существования.

Квантор общности и квантор существования называются двойственными.

Иногда используют обозначения квантора «Равно один»: $!.

Если переменная связана квантором, то она называется связанной, иначе – свободной.

Например: "x F(x,y), $x F(x,y), здесь x – связанная переменная, y – свободная переменная.

 

Синтаксис языка логики предикатов.

Формулы логики предикатов и формализация суждений

 

В качестве алфавита в логике предикатов используется латинский язык, как и в логике высказываний [25].

Вводятся следующие обозначения:

· константы: a,b,c,d,e,... – строчные буквы из начала латинского алфавита;

· логические константы (0 – ложь, 1 – истина);

· предметные переменные: x, y, z, v, w,... – строчные буквы из конца латинского алфавита;

· функции: f,g,h,... –строчные буквы из середины латинского алфавита;

· предикатные символы: F, G, H, P, Q,... – прописные буквы латинского алфавита;

· символы логических операций и кванторов (¯, |, Ú, ®,Ù, ,…);

· служебные символы, например, символы скобок ([, ], {, }, (,)).

Символы функций и предикатов называют сигнатурой.

Функции и предикаты иногда снабжаются верхним индексом местности операции.

При определении формулы используется понятие «терм». Терм – объединяет понятия переменных и функций, к которым применяются предикатные буквы.

Всякая предметная переменная или константа – терм.

Если f – n-местная функция, а t₁,t₂,...,t_n – терм, то f_n(t₁,t₂,...,t_n) – тоже терм.

Никакие другие выражения не являются термами.

Пример. f³(a,x,g²(x,y)) – это терм с трехместной функцией f, двухместной функцией g, a – константа.

Если F – n-местный предикат, t₁,t₂,...,t_n – термы, то Fⁿ(t₁,t₂,...,t_n) – элементарная формула. Никакие другие выражения не являются элементарными формулами.

Элементарную формулу иногда называют атомарной или атомом.

Введем понятие формула:

1) всякая элементарная формула – это формула;

2) если F и Q – формулы, а х – предметная переменная, которая входит в F, то "x F(x), $x F(x), , F× Q, FÚ Q, F® Q, F«Q – являются формулами.

Примеры.

P²(a,f¹(x)) – формула;

Q¹(x,g²(x,b)) – не формула, так как предикат Q должен быть одноместным;

P²(y,Q¹(z)) – не формула, так как Q¹(z) – не терм;

f¹(g²(x,y)) – не формула, а терм;

F²(a,y)®Q¹(b) – формула.