Розділ 1. Основні теоретичні відомості з модуля логіки предикатів (в даному розділі використовується матеріал з таких джерел [1], [2],[3],[6],[7],[8],[26],[30])

1.1. Предикати. Логічні операції над предикатами

Нехай є деяка множина

п-місним предикатом, заданим на множині М, називається речення, що містить змінних (предметні змінні), яке перетворюється на висловлення при підстановці замість цих змінних відповідних конкретних значень М (предметні константи).

Позначаються предикати великими літерами з індексами або без, наприклад . Довільне висловлення є 0-місним предикатом. Предикат можна вважати функцією п змінних, областю визначення якої є множина М, а множиною значень - логічні значення 1 (істина) та 0 (хиба).

Вираз, яким записується предикат — висловлювальна форма. Нехай Р(х, у)="х + у= 4" — двомісний предикат, визначений на множині N ×N, тоді логічні значення відповідних висловлень записують, наприклад, як і т. д. При конструюванні предикатів часто використовують функціональні символи. Тут таким символом є "+" або "сума(x,у)",а Р — предикатний символ "дорівнює 4”.

Предикат _, заданий на множині М, називається тотожно істинним, якщо для будь-якого набору предметних констант М він перетворюється в істинне висловлення, тобто . Аналогічно формулюються означення тотожно хибного, виконуваного та спростовного предиката.

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

Запереченням предиката , заданого на множині М, називається предикат заданий на тій же множині, який перетворюється в хибне висловлення для будь-якого набору з множини істинності предиката і в істинне для всіх інших наборів.

Якщо — множина істинності (сукупність всіх наборів М, для кожного з яких ) предиката Р, то множина істинності предиката буде

Нехай деякий m-місний предикат заданий на множині , причому всі змінні та різні.

Кон'юнкцією двох предикатів Р та Q називається (п+т)-місний предикат , заданий на множині M×L, якийперетворюється в істинне висловлення для всіх тих і тільки тих значень змінних, при яких перетворюються в істинне висловлення обидва задані предикати.

Якщо предикати Р та Q мають k спільних змінних, то місність кон’юнкції буде s = п + т — k, а загалом max .

Означення диз’юнкції, імплікації та еквіваленції аналогічне. [2, ст. 17]

Якщо і - множини істинності предикатів Р та Q, визначених на одній множині М, то множини істинності предикатів , , та можна записати у вигляді:

;

;

;

;

Крім вказаних операцій над предикатами виконують кванторні операції (квантифікацію).

Зв ’язуванням квантором загальності одномісного предиката Р(х) називається операція, яка предикату Р(х) ставить у відповідність висловлення ("для будь-якого х має місце Р(х)"), яке істинне тоді і тільки тоді, коли предикат тотожно істинний. Отже,

=

Наприклад, висловлення на множині дійсних чисел істинне, а - хибне.

Зв'язуванням квантором існування одномісного предиката Р(х) називається операція, яка предикату Р(х) ставить у відповідність висловлення ("існує х, що має місце Р(х)") ,яке хибне тоді і тільки тоді, коли предикат тотожно хибний. Отже,

= Р(х) – тотожно хибний предикат.

Наприклад, висловлення на множині дійсних чисел хибне, а - істинне.

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

А: загальностверджувальне судження "всі S суть Р" (всі елементи х,які мають властивість S, мають і властивість Р) - ;

Е: загальнозаперечувальне судження "будь-яке S не є Р" (будь-який елемент х, який має властивість S,не має властивості Р)- ;

I: частково стверджувальне судження "деякі S суть Р" (деякі елементи х, які мають властивість S, мають і властивість Р) - ;

О: частково заперечувальне судження "деякі S не є Р" (деякі елементи х, які мають властивість S,не мають властивості Р) - ;

Комбінуючи речення А-O, можна записувати у символічній формі досить складні твердження.

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

Зв’язування квантором загальності чи існування за деякою змінною х,

n-місного предиката приводить до (n-1)-місного предиката чи ,який залежить від змінних .При цьому висловлення

істинне тоді і тільки тоді, коли предикат тотожно істинний на множині , а висловлення хибне тоді і тільки тоді, коли предикат тотожно хибний на .

Далі можна по черзі зв’язувати різними кванторами інші змінні. Коли всі змінні будуть зв’язані, отримується висловлення. Наприклад, тримісний предикат , заданий на множині дійсних чисел, можна перетворити на двомісний , одномісний , предикати або ж на істинне висловлення , Якщо Р — 0-місниЙ предикат (висловлення), то записи та означають те саме, що і Р. [2,ст 23]

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

Предикати та ,задані на одній множині М, називаються рівносильними(Р Q), якщо = (один з них перетворюється в істинне висловлення на всіх тих наборах ,на яких і інший перетворюється в істинне висловлення). Предикат називається логічним наслідком предиката (P Q), якщо .