Кванторы

Р(х1, х2, …, хn), где Р – символ предиката, х1, х2, …, хn – предметные переменные а1, а2, …, аn

Р(а1, а2, …, аn) - истинное или ложное n – ка предметов < а1, а2, …, аn > Операции связывания кванторами (или навешивания кванторов)

В первом случае истинно высказывание: «Для всех х (из М) имеет место (истинно) Р(х)», во втором – высказывание «Существует х (из М) такое, что Р(х) истинно».

Выражение «для всех х» («для любого х», «для всякого х») называется квантором общности и обозначается символом ("х).

Выражение «существует х такое, что…» называется квантором существования и обозначается символом ($х).

связанная переменная

Например, если Р(х) – предикат: «х – простое число» на множестве N, то ("х)Р(х) – ложное высказывание «Всякое натуральное число х – простое», а ($х)Р(х) – истинное высказывание «Существует натуральное число х такое, что оно простое».

Квантор общности можно рассматривать как обобщение конъюнкции, а квантор существования – как обобщение дизъюнкции.

М - область определения предиката Р(х)

М={ а1, а2, …, аn }

("х)Р(х) равносильно конъюнкции

Р(а1)&Р(а2)&…&Р(аn)

($х)Р(х) равносильно дизъюнкции

Р(а1)ÚР(а2)Ú…ÚР(аn).

Если предикат Р(х) определен на бесконечном множестве, то кванторы играют роль «бесконечных» конъюнкций и дизъюнкций.

Определение формулы логики предикатов данной сигнатуры (сигнатура –signum – знак)

Алфавит:

1. x, y, z, …, - предметные (индивидные) переменные;

2. P1^(k1), P2^(k2), …, - список символов предикатов - предикатная сигнатура;

3. f1^(m1), f2^(m2), … - список символов операций;

4. ®, Ø, &, Ú - логические связки;

5. $, " - кванторы;

6. (,),, - три технических символа;

7. C1, C2, …, - символы констант.

Сигнатура термы

s=<P1^(k1), P2^(k2), …; f1^(m1), f2^(m2), …; C1, C2, …>

Опр.:

1. отдельно стоящая переменная – терм, отдельно стоящая const – терм;

2. если t1, …, tn – термы данной сигнатуры и f(n) – символ операции из данной сигнатуры, то f(t1, …, tn) – терм этой же сигнатуры;

3. других термов нет.

$ x, " x

Опр.:

1. Если t1, t2 – термы данной сигнатуры, то t1=t2 – формула данной сигнатуры.

2. Если t1, …, tn – термы данной сигнатуры и P(n) – символ предиката из данной сигнатуры, то P(t1, …, tn) – формула данной сигнатуры.

3. Если A – формула данной сигнатуры, то - формула той же сигнатуры.

4. Если A и B – формулы данной сигнатуры, то (AÚB), (A&B), (A®B) являются формулами той же сигнатуры.

5. Если A(x) – формула сигнатуры s, содержащая x свободно, то выражения " x A(x), $ x A(x) – формулы той же сигнатуры.

6. Других формул нет.