Предикат

Предикат ( лат. praedicatum - Заявлене, згадане, сказане) - будь-математичне висловлювання, в якому є, щонайменше, одна змінна . Предикат є основним об'єктом вивчення логіки першого порядку.

1. Визначення

Предикат (n-місцевий, або n - арний) - це функція з безліччю значень {0,1} (Або "брехня" і "істина"), визначена на множині . Таким чином, кожен набір елементів множини M характеризується або як "щирий", або як "помилковий".

Предикат можна зв'язати з математичним ставленням : якщо n-ка належить відношенню, то предикат буде повертати на ній 1. Зокрема, одномісний предикат визначає ставлення приналежності деякого безлічі.

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

Предикат називають тотожно-істинним і пишуть:

якщо на будь-якому наборі аргументів він приймає значення 1.

Предикат називають тотожно-помилковим і пишуть:

якщо на будь-якому наборі аргументів він приймає значення 0.

Предикат називають здійсненним, якщо хоча б на одному наборі аргументів він приймає значення 1.

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

2. Приклади

Наприклад, позначимо предикатом EQ (x, y) відношення рівності ("x = y"), де x і y належать безлічі дійсних чисел. У цьому випадку предикат EQ буде приймати справжнє значення для всіх рівних x і y.

Більше життєвим прикладом може служити предикат проживають (x, y, z) для відносини "x проживає в місті y на вулиці z" або ЛЮБИТЬ (x, y) для "x любить y", де безліч M - це множина всіх людей.

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

x, y, z належить R

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

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

3.1. Логічні операції

Кон'юнкція двох предикатів А (х) і В (х) називається новий предикат , Який приймає значення "істина" при тих і тільки тих значеннях х Т, при яких кожен з предикатів приймає значення "істина", і приймає значення "брехня" у всіх інших випадках. Безліччю істинності Т предиката А (х) В (х), х Х є перетин множин істинності предикатів А (х) - Т1 і В (х) - Т2, тобто Т = Т1 ∩ Т2. Наприклад: А (х): "х - парне число", В (х): "х кратно 3". А (х) В (х) - "х - парне число і х кратно 3". Тобто предикат "х ділиться на 6".

Диз'юнкцією двох предикатів А (х) і В (х) називається новий предикат , Який приймає значення "брехня" при тих і тільки тих значеннях х Т, при яких кожен з предикатів приймає значення "брехня" і приймає значення "істина" в усіх інших випадках. Областю істинності предиката А (х) В (х) є об'єднання областей істинності предикатів А (х) В (х).

Запереченням предиката А (х) називається новий предикат, який приймає значення "істина" при всіх значеннях х Т, при яких предикат А (х) приймає значення "брехня", і приймає значення "брехня", якщо А (х) приймає значення " істина ". Безліччю істинності предиката, х Х є доповнення Т 'до безлічі Т в множині Х.

Імплікацією предикатів А (х) і В (х) називається новий предикат А (х) В (х), який є хибним при тих і тільки тих значеннях х Т, при яких А (х) приймає значення "істина", а В ( х) - значення "брехня" і приймає значення "істина" в усіх інших випадках. Читають: "Якщо А (х), то В (х)". Наприклад. А (х): "Натуральне число х ділиться на 3". В (х): "Натуральне число х ділиться на 4", можна скласти предикат: "Якщо натуральне число х ділиться на 3, то воно ділиться і на 4". Безліччю істинності предиката А (х) В (х) є об'єднання безлічі Т2 - істинності предиката В (х) і додатки до безлічі Т1 істинності предиката А (х).

3.2. Кванторное операції

Квантор (все-) спільності

Квантор існування

Квантор існування по змінній x ₁