ЛОГІКА ПРЕДИКАТІВ привычки

ЛОГІКА ПРЕДИКАТІВ

[if !supportLists]1. [endif]Поняття предиката. Формули логіки предикатів. Загальнозначущі формули логіки предикатів

[if !supportLists]2. [endif]Випереджена нормальна форма

1. Поняття предиката Формули логіки предикатів. Загальнозначущі формули логіки

предикатів

Внутрішню структуру висловлень можна розділити на суб’єкт та предикат, де суб’єктом є підмет, а предикат визначає властивість суб’єкта. Наприклад, у висловленні «Соркат - це людина» Сократ - це суб’єкт, який має властивість бути людиною. Ця властивість представляє собою одномісний предикат, визначений на множині людей: “бути людиною”. Позначимо його Р(х), де х - змінна. Підставляючи на місце змінної х об’єкти з області визначення предиката, отримуємо висловлення. Таким чином, одномісний предикат, визначений на деякій множині об’єктів, задає властивість, якою ці об’єкти можуть володіти чи не володіти. Отже, предикат розбиває цю множину на дві області: область істинності та хибності.

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

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

Означення. И-місним предикатом, визначеним на множинах Мі,...,Мл, називається вираз, який перетворюється у висловлення після заміни кожної предметної змінної на елемент з її області визначення. Якщо всі змінні визначені на одній та й самій множині, то предикат називається однорідним.

Отже предикат можна розглядати як функцію, що відображає множину (або декартовий добуток множин) об’єктів на множину {Т, Р}. Таким чином, над предикатами визначено всі булеві операції, а також дві нові операції - квантори: V- квантор загальності та 3- квантор існування.

Якщо Р(х) означає деяку властивість на множині М, то формула УхР(х) означає висловлення: “для будь-якого предмету шєМ виконується властивість Р(х)” або “всі х мають властивість Р(х)". Формула \/хР(х) набуває значення “істина”, коли властивість Р виконується для всіх об’єктів з А/, та набуває значення “хибність” у протилежному випадку, тобто коли існує хоча б один об’єкт з множини М, для якого ця властивість не виконується.

Формула 3хР(х) означає: “існує принаймні один предмет х, який має властивість Р» або «деякі х мають властивість Р». Значення формули ЗхР(х) є істинним, коли властивість Р виконується хоча б дам одного об’єкту з множини М, та хибним, коли не існує жодного об’єкта, для якого ця властивість виконувалась би.

Означення. Формула, на яку розповсюджується дія квантора, називається областю дії квантора. Змінна, за якою “навішується” квантор та яка попадає в його область дії, називається зв'язаною змінною. Змінна, яка лежить за межами області дії квантора, називається вільною змінною.

Означення. Формула, що не містить вільних змінних, називається замкненою.

Замкнуті формули є висловленнями.

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

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

Означення. Дві формули логіки предикатів А і В називаються рівносильними на області М, якщо вони приймають однакові логічні значення при всіх значеннях вхідних у них змінних, віднесених до області М.

Означення. Дві формули логіки предикатів А і В називаються рівносильними, якщо вони рівносильні на будь-якій області.

Означення формули логіки предикатів:

[if !supportLists]- [endif]нуль-міский предикат е формулою логіки предикатів.

[if !supportLists]- [endif]якщо Р" - п-місний предикат, то Р"(х,хп) є формулою логіки предикатів, в якій ЗМІННІ X,... ,Х„ € вільними.

[if !supportLists]- [endif]якщо Р є формулою логіки предикатів, то Р € теж формулою логіки предикатів, при чому вільні змінні формули Р будуть вільними у формулі Р і зв’язані змінні формули Р будуть зв’язаними у формулі Р .

[if !supportLists]- [endif]якщо Ці і 0 формули логіки предикатів, то 0 А0, 0У0, £/,<->0, теж є

формулою логіки предикатів, причому вільні (зв’язані) змінні будуть вільними (зв’язаними) в утворених формулах.

[if !supportLists]- [endif]якщо II - формула логіки предикатів, х - вільна змінна даної формули, то наступні вирази Ух II(х) і Зх II(х) теж будуть формулами логіки предикатів, причому х буде зв’язаною змінною. Якщо формула II містила крім х інші змінні, то вони залишаться вільними або зв’язаними в залежності від того, які вони е у даній формулі.

[if !supportLists]- [endif]інших формул, крім перелічених вище, не існує.

Означення. Формула А логіки предикатів називається виконуваною в області М, якщо існують значення змінних вхідних у цю формулу і віднесених до області М (інакше - існує модель), при яких формула А приймає істинні значення.

Означення. Формула А логіки предикатів називається виконуваною, якщо існує область, на якій ця формула виконувана.

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

Означення. Формула А логіки предикатів називається загальнозначущої, якщо вона тотожньо- істинна на будь-якій області (на будь-якій моделі).

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

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

Загальнозначущі формули логіки предикатів

[if !supportLists]1) [endif]якщо в тавтології алгебри висловлень замість змінних поставити предикат, то ми отримаємо формулу логіки предикатів, яка буде загальнозначущою.

[if !supportLists]2) [endif]закони де Моргана

УхР(х) <-> 3хй{х)

ЗхР(х)*+УхО(х)

[if !supportLists]3) [endif]закони вираження одного квантора через інший УхО{х)<^Зхй{х)

ЗхІІ{х) <-► УхО(х)

[if !supportLists]4) [endif]закони перенесення кванторів через д і V Ух(Р(х) А £(*)) <-* (УхР(*)) А (^хд(.т))

Зх(Р(х) V 0(х)) (ЗхР(х)) V (3х0(х))

Ух{Р(х) V 0 (УхР(х)) V (2

3*(Р(х)м0<->(3*/Ч*))^

[if !supportLists]5) [endif]закон перенесення кванторів через імплікацію Ух(Р(х) -> 0 <-> (ЗхДх)) -> 0

Зх{Р{х) ->0^ (УхР(х)) -х 0 Ух(0 -> Р(х)) <-» О -»(УхР(х))

3х(0 -> Р(х)) о• £> -> (3хР(х))

[if !supportLists]6) [endif]закони знищення квантора узагальнення і введення квантора існування

с

(УхР(х)) -> Р(у)

Р(у)^(ЗхР(х))

[if !supportLists]7) [endif]закони комутативності Ух\/уР(х, у) <г+ УуУлР(дг, у)

ЗхЗуР(х, у) <-» ЗуЗхР(х, у)

Зх'іуР{х,у) Зу\/хР(х,у)

Означення. Множина предметних змінних 7} = {х,у,г,...} , предметних сталих Г2 = {а,В,с,...}, функціональних символів Г3 = і предикатів Г4 = |р1',р2у,р34,...|, Г = {7],7’2,7’3,7’4} разом з

множиною логічних операцій р = {-і, л, V, <->, V, 3} утворюють алгебру предикатів.

Деякі правила запису складних формул алгебри предикатів.

[if !supportLists]1) [endif]логічні зв’язки л і V після розстановки дужок зв’язують ті елементи формули предикатів, які стоять безпосередньо біля логічного зв’язку.

[if !supportLists]2) [endif]пріоритет операцій ->,л,у,-»,<-»

[if !supportLists]3) [endif]за квантором V частіше всього іде оператор =>, за квантором 3 - л.

[if !supportLists]4) [endif]якщо формула містить підформулу, то внутрішня формула не повинна містити квантора, що зв’язує змінну, яка вже є зв’язаною квантором загальної формули.

[if !supportLists]5) [endif]всі предметні змінні і сталі повинні бути визначені на одній множині.

[if !supportLists]6) [endif]якщо у формулі задані загальні квантори 3 і V, то квантор 3 записується лівіше квантора V.

Основні закони алгебри предикатів

[if !supportLists]1) [endif]закон комутативності

[if !supportLists]2) [endif]закон дистрибутивності

[if !supportLists]3) [endif]закон ідемпотентності

Кх Р(х,у)\/ Кх Р(х,у) = Кх Р(х,у)

Кх Р(х,у)лКх Р(х,у)= Кх Р(х,у), Вє{3,\/}

[if !supportLists]4) [endif]закон виключеного третього Кх Р{х,у) V Кх Р(х,у) = 1

[if !supportLists]5) [endif]закон протиріччя

Ях Р(х, у)лКх Р(х, у) = 0

[if !supportLists]6) [endif]закони де Моргана

[if !supportLists]7) [endif]закон доповнення Кх Р{х,у) = Кх Р{х,у)

[if !supportLists]8) [endif]властивості константи Кх Р(х, у) л 1 = Кх Р(х,у)

Кх Р(х,у)л 0 = 0 КхР{х,у)у 1 = 1

Кх Р(х, у)\/0-Кх Р(х, у)

2. Випереджена нормальна форма

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

Приклад. Ут (Р(х) V (Дх)) є зведеною.

Означення. Формула логіки предикатів називається відкритою, якщо вона не містить кванторів. Зведена формула логіки предикатів знаходиться у випередженій нормальній формі, якщо вона має вигляд

де В - відкрита формула логіки предикатів, £3 - квантор є {У,3}

Теорема. Будь-яку формулу логіки предикатів можна подати у випередженій нормальній формі. Доведення.

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

При т = 0 ми отримуємо нуль-місний предикат або предикатну формулу без операцій. Для даного предиката можна сказати, що він знаходиться у випередженій нормальній формі.

Припустимо, що дана теорема виконується при т-п-1. Доведемо, що вона справедлива для т-п. Нехай и, Vі,1}2 - формули логіки предикатів, які подані у випередженій нормальній формі з кількістю логічних операцій п-1. Додамо ще по одній операції, щоб отримати кількість п. Ми отримаємо вирази: О, 1/,лї/2, П, уП2, <2(17).

а) Р = 1]. Так як 17 - можна подати у випередженій нормальній формі, то

17 = 2г12<2"-0с,('®Х Р = У = С?*і6*2-йотС®) ■ Отримана формула Р подана у випередженій нормальній формі.

б) 17, л 17 2 = Р. В даному випадку виконується спрощення отриманого виразу за допомогою основних законів логіки предикатів (закони перенесення кванторів через л, V, закони комутативності). При необхідності здійснюється заміна змінних, оскільки у даних формулах можуть бути і зв’язані і незв’язані змінні. Виконавши наступну послідовність рівносильних дій ми прийдемо до випередженої нормальної форми.

в) 17, V17 2 = Р. Даний випадок аналогічний до попереднього.

г) £?(£/) = Р. Введення ще одного квантора не порушує випередженості нормальної форми. Згідно методу математичної індукції теорема доведена. Доведено.

Означення. Формула <У* називається двоїстою до формули 17, якщо її можна отримати з формули V заміною л,у,У,3 на V,л,3,V відповідно. З означення випливає (V ) =11.

іуПерший закон двоїстості.

Якщо'(/(*,,х„) = В(х,,хп), то І7'(х„хг) = В'(х1гхг).

[if !supportLists]2) [endif]Другий закон двоїстості.

Якщо 17(х,,х„) -> В(х:,х ), то В’(х,,х„)-* 17‘(хігха), Якщо перший вираз тавтологія, то і другий

%.

1 вираз теж тавтологія.

[if !supportLists]3) [endif]Третій закон двоїстості.

Якщо V - тавтологія, то 17 - суперечність.

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

Означення. Обмеженим квантором V, Ух Р(х) на множині М називається наступний вираз: Vих Р(х) = Ух (х є М -» Р(х)).

Означення. Обмеженим квантором 3, Зх Р(х) на множині М називається наступний вираз: Зих Р(х) = Зх (х є М л Р(х)).

Для обмежених кванторів має місце наступне твердження: якщо в загальнозначущій (тавтологія) формулі логіки предикатів замінити всі квантори і на обмежені квантори множини М, причому М Ф 0, то ми знову отримаємо тотожньоістинну формулу.

#советы #лайфхак