На головну

квантори

Р (х1, х2, ..., хn), де Р - символ предиката, х1, х2, ..., хn - предметні змінні а1, а2, ..., аn

Р (а1, а2, ..., аn) - Істинне або помилкове n - капредметів <а1, а2, ..., аn> Операції зв'язування кванторами (або навішування кванторів)

У першому випадку істинно висловлювання: «Для всіх х (з М) має місце (істинно) Р (х)», у другому - висловлювання «Існує х (з М) таке, що Р (х) істинно».

Вираз «для всіх х» ( «для будь-якого х», «для всякого х») називається квантором спільності і позначається символом ( "х).

Вираз «існує х таке, що ...» називається квантором існування і позначається символом ($ х).

пов'язана змінна

Наприклад, якщо Р (х) - предикат: «х - просте число» на безлічі N, то ( "х) Р (х) - хибне висловлювання« Будь-яке натуральне число х - просте », а ($ х) Р (х) - справжнє висловлювання «Існує натуральне число х таке, що воно просте».

Квантор спільності можна розглядати як узагальнення кон'юнкції, а квантор існування - як узагальнення диз'юнкції.

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

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

( "Х) Р (х) рівносильно кон'юнкції

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

($ Х) Р (х) рівносильно диз'юнкції

Р (а1) UР (а2) U ... UР (аn).

Якщо предикат Р (х) визначено на нескінченній множині, то квантори грають роль «нескінченних» кон'юнкція і диз'юнкцій.

Визначення формули логіки предикатів даної сигнатури (сигнатура -signum - знак)

алфавіт:

1. x, y, z, ..., - Предметні (індивідуальна) змінні;

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

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

4. ®, O, &, U - логічні зв'язки;

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

6. (,), , - Три технічних символу;

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

сигнатура терми

s = (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 - формули даної сигнатури, то (AUB), (A & B), (A®B) є формулами тієї ж сигнатури.

5. Якщо A (x) - Формула сигнатури s, що містить x вільно, то вирази "xA (x), $xA (x) - Формули тієї ж сигнатури.

6. Інших формул немає.



Способи завдання предикатів | повнота ІВ

Поняття про елементарні теоріях. | Побудова числення предикатів: алфавіт, формула, аксіоми. Правила виведення, опр. Виведення формули та виведення з гіпотез в ВП. Теорема ЛП. Несуперечливість ВП. | Попереджання нормальна форма (ПНФ), її знаходження. | Метод Генцен для вирішення проблеми виконуваності формул логіки предикатів. | протиріччя | Проблеми здійсненності, общезначимости в тотожною хибності формул логіки предикатів. Зв'язок між цими проблемами. Т. Черча (без док-ва). | Поняття моделі даної сигнатури і істинності формули на моделі. | Приклади запису математичних пропозицій формулами логіки предикатів | Лемма про повноту ІВ | Висновок формул з гіпотез |

© um.co.ua - учбові матеріали та реферати