Головна

 Предикати. |  Равносильность і проходження предикатів. |  обмежені предикати |  Контрольні завдання. |

квантори

  1.  Квантори спільності і існування
  2.  Квантори спільності і існування.
  3.  Заперечення висловлень, що містять квантори
  4.  Предикати і квантори
  5.  Предикати і квантори
  6.  Равносильности і тотожно істинні імплікації логіки предикатів, що містять квантори

Предикатам можуть бути приписані квантори. знак  називається квантором спільності, А знак  називається квантором існування.

Квантори в явному вигляді вперше було введено німецьким математиком Готлоб Фреге в роботі «Begriffsschrift» ( «Обчислення понять», 1879). У 1885 р англійський логік Чарльз Пірс ввів терміни «квантор», «квантификация», що відбулися відповідно від лат. quantun - «скільки» і лат. quantun + facio - «робити». Це означає, що квантор показує, про скількох (всіх або деяких) об'єктах йдеться в ту чи іншу пропозицію. Символіку для кванторів у вигляді перевернутих латинських букв ввів італійський математик Дж. Пеано в 90-і рр. XIX ст. Після використання кванторів математиками Пеано, Шредером, Расселом вони стали широко використовуватися.

символ  інтерпретується як фраза «для всіх х», Відповідно  - «Існує х».

вираз "x P(x) Інтерпретується наступним чином: для будь-якого х предикат Р(х) Істинний.

вираз $х Р(х) Інтерпретують наступним чином: існує таке х, Що предикат Р(х) Істинний.

Определеніе1. операцією зв'язування квантором спільності називається правило, за яким кожному одномісному предикату  , Визначеним на множині М, Зіставляється вислів, що позначається  , Яке істинно в тому і тільки в тому випадку, коли предикат  тотожно істинний, і помилково в іншому випадку.

висловлювання  називається універсальним висловлюванням для предиката  . символ  походить від першої літери англ. all - "Усе".

Визначення 2. операцією зв'язування квантором існування називається правило, за яким кожному одномісному предикату  , Визначеним на множині М, Ставиться у відповідність висловлювання, що позначається  яке помилково в тому і тільки в тому випадку, коли  тотожно хибна, і істинно в іншому випадку.

висловлювання  називається екзистенційним висловлюванням для предиката  . символ  походить від першої літери англ. exist - «Існувати».

Як приклад розглянемо предикат P(x) = «x - непарне число".

на безлічі  він є тотожно істинним, тому для нього справедливий вираз: ,  . на безлічі  вираз  істинним не буде, для нього справедливий вираз , .

Якщо одномісний предикат  заданий на кінцевій множині  , То неважко зрозуміти, що висловлювання  еквівалентно (має той же логічне значення) кон'юнкції  . Справді, за визначенням істинність висловлювання  означає, що предикат тотожно істинний, тобто кожне з висловлювань  , В які цей предикат перетворюється, істинно. Останнє рівносильно істинності кон'юнкції .

Якщо одномісний предикат  заданий на кінцевій множині  , То висловлювання  еквівалентно (має той же логічне значення) диз'юнкції  . Справді, за визначенням хибність висловлювання  означає, що предикат  тотожно хибна, тобто кожне з висловлювань  , В які даний предикат може перетворитися, помилково. Останнє рівносильно хибності диз'юнкції .

Отже, для предикатів, заданих на кінцевій множині, квантор спільності узагальнює операцію кон'юнкції, квантор існування узагальнює операцію диз'юнкції. Для предикатів, заданих на нескінченній множині, такого зробити не можна.

Тепер розглянемо питання про застосування операції зв'язування квантором спільності або існування до предикатам з будь-яким числом предметних змінних.

визначення 3. операцією зв'язування квантором спільності по змінній  називається правило, за яким кожному п-Місцеві  предикату  , Визначеним на множині М=  , Ставиться у відповідність новий  місний предикат, що позначається  , Який для будь-яких предметів ,  , ...,  перетворюється в висловлювання  , Справжнє в тому і тільки в тому випадку, коли одномісний предикат  , Певний на безлічі  , Тотожне правдивий, і помилкове в іншому випадку.

Наприклад, розглянемо двомісний предикат «  », Певний на безлічі  . Застосуємо до нього квантор спільності по змінної х. Отримаємо одномісний предикат  , Що залежить від змінної у. Цей предикат може перетворитися як в істинне висловлення (при  ), Так і в помилкове (при підстановці замість у будь-яких натуральних чисел, крім 1).

Зауважимо, що до  -Місцеві предикату  , Залежному від змінних  , Можна знову застосувати операцію зв'язування квантором спільності по одній з вільних змінних. В результаті вийде  місний предикат і т. д.

Наприклад, застосувавши до одномісному предикату  , де  , Квантор спільності по змінної у, Отримаємо нуль-місний предикат, тобто вислів  . Ясно, що отримане висловлення помилкове, тому що предикат  Спростовано.

визначення 4. операцією зв'язування квантором існування по змінній  називається правило, за яким кожному п-Місцеві  предикату  , Визначеним на множині М=  , Ставиться у відповідність новий  місний предикат, що позначається  , Який для будь-яких предметів ,  , ...,  перетворюється в висловлювання  , Помилкове в тому і тільки в тому випадку, коли одномісний предикат  , Певний на безлічі  , Тотожне хибна, і справжнє в іншому випадку.

Зауважимо, що до  -Місцеві предикату  , Залежному від змінних  , Можна знову застосувати одну з операцій квантификации - квантор спільності або квантор існування по одній з вільних змінних. В результаті вийде  -місцеві предикати и .

Визначення 5. Мінлива х, Що входить в предикат  , називається пов'язаної, Якщо вона знаходиться під дією квантора  або  . В іншому випадку, змінна х в предикате  є вільної.

Наприклад, в предикате

змінні х и z-пов'язані, а змінні у и v -Вільне.

приклад 1. нехай A (x, y) - Деякий двомісний предикат, визначений на множині з п'яти елементів: M = {A1, a2, a3, a4, a5}, Предикатні функція задана матрицею:

y x a1 a2 a3 a4 a5
a1
a2
a3
a4
a5

В результаті застосування квантифікації можна отримати чотири одномісних предиката.

x "(Y) A (x, y)   y "(X) A (x, y)
a1   a1
a2   a2
a3   a3
a4   a4
a5   a5

 

x $(Y) A (x, y)   y $(X) A (x, y)
a1   a1
a2   a2
a3   a3
a4   a4
a5   a5

Якщо до залишилася вільної змінної застосувати квантор, то одномісні предикати перетворяться в висловлювання:

$(X)"(Y) A (x, y) = 1 $(Y)"(X) A (x, y) = 0

" (X)$(Y) A (x, y) = 1 " (Y)$(X) A (x, y) = 1

Порядок застосування різнойменних кванторів істотний і може привести до різних висловлювань.

Приклад 2.

1. Нехай предикат  визначений на множині натуральних чисел.

предикат  означає - «для всякого х існує таке y, Що x ділить y ». Це твердження істинне. Якщо квантори поміняти місцями, то отримаємо предикат  , Значення якого - «існує таке число y, Що будь-який х його ділить ». Це твердження помилкове.

2. Нехай  - Предикат, визначений на множині людей. тоді  означає, що у кожної людини х є мати у. Предикат з іншим порядком кванторів  означає помилкове твердження, що існує мати всіх людей.



 Застосування логічних зв'язок |  Равносильности і тотожно істинні імплікації логіки предикатів, що містять квантори
© um.co.ua - учбові матеріали та реферати