Предикати і квантори

Оскільки предикати можуть приймати тільки два значення (істинно / хибно або $ 0/1 $), то до них можна застосовувати всі операції алгебри логіки: заперечення, кон'юнкція, диз'юнкція і т.д.

приклади предикатів

Нехай предикат $ R (x, y) $: $ «x = y» $ позначає відношення рівності, де $ x $ і $ y $ належать множині цілих чисел. В цьому випадку предикат R буде приймати справжнє значення для всіх рівних $ x $ і $ y $.

Інший приклад предиката - ПРАЦЮЄ ($ x, y, z $) для відносини «$ x $ працює в місті y в компанії $ z $».

Ще один приклад предиката - ПОДОБАЄТЬСЯ ($ x, y $) для «x подобається y» для $ x $ і $ y $, які належать $ M $ - безлічі всіх людей.

Таким чином, предикатом є все те, що стверджується або заперечується про суб'єкта судження.

Операції над предикатами

Розглянемо застосування операцій алгебри логіки до предикатам.

Кон'юнкція двох предикатів $ A (x) $ і $ B (x) $ - предикат. який приймає істинне значення при тих і тільки тих значеннях $ x $ з $ T $, при яких кожен з предикатів приймає істинне значення, а помилкове значення - у всіх інших випадках. Безліч істинності $ T $ предиката - перетин множин істинності предикатів $ A (x) $ і $ B (x) $. Наприклад: предикат $ A (x) $: «$ x $ - парне число», предикат $ B (x) $: «$ x $ ділиться на $ 5 $». Таким чином, предикатом буде вираз «$ x $ - парне число і ділиться на $ 5 $» або «$ x $ ділиться на $ 10 $».

Диз'юнкція двох предикатів $ A (x) $ і $ B (x) $ - предикат. який приймає помилкове значення при тих і тільки тих значеннях $ x $ з $ T $, при яких кожен з предикатів приймає помилкове значення і приймає істинне значення у всіх інших випадках. Безліч істинності предиката - об'єднання областей істинності предикатів $ A (x) $ і $ B (x) $.

Заперечення предиката $ A (x) $ - предикат, який приймає істинне значення при всіх значеннях $ x $ з $ T $, при яких предикат $ A (x) $ приймає помилкове значення і навпаки. Безліч істинності предиката $ A (x) $ - доповнення $ T '$ до безлічі $ T $ в безлічі $ x $.

Імплікація предикатів $ A (x) $ і $ B (x) $ - предикат. який є хибним при тих і тільки тих значеннях $ x $ з $ T $, при яких $ A (x) $ - істинно, а $ B (x) $ - помилково, і приймає істинне значення у всіх інших випадках. Новомосковскется: «Якщо $ A (x) $, то $ B (x) $».

Нехай $ A (x) $: «Натуральне число $ x $ ділиться на $ 3 $»;

$ B (x) $: «Натуральне число $ x $ ділиться на $ 4 $».

Складемо предикат: «Якщо натуральне число $ x $ ділиться на $ 3 $, то воно ділиться і на $ 4 $».

Безліч істинності предиката - об'єднання безлічі істинності предиката $ B (x) $ і доповнення до безлічі істинності предиката $ A (x) $.

Над предикатами крім логічних операцій можна виконувати квантові операції: застосування квантора загальності, квантора існування і т.д.

існують натуральні числа, які діляться на $ 7 $;

знайдеться натуральне число, яке ділиться на $ 7 $;

хоча б одне натуральне число ділиться на $ 7 $.

Запис буде мати вигляд:

Нехай на безлічі $ x $ простих чисел заданий предикат. «Просте число є непарним». Поставивши перед предикатом слово «будь», отримаємо помилкове висловлювання: «Будь-яке просте число є непарним» (наприклад, $ 2 $ є простим парним числом).

Поставимо перед предикатом слово «існує» і отримаємо справжнє висловлювання: «Існує просте число. яке є непарних »(наприклад, $ x = 3 $).

Таким чином, предикат можна перетворити в висловлювання, якщо поставити перед предикатом квантор.

Операції над кванторами

Для побудови заперечення висловлювань, які містять квантори, застосовується правило заперечення кванторів: