Логіка предикатів

Логіка предикатів — це розділ класичної символічної логіки, що вивчає суб'єктно-предикатну структуру висловлювань, на підставі чого визначають значення істинності висловлювань; по-іншому — це дедуктивна теорія, яка моделює процес виведення одних висловлювань із інших, враховуючи їх структуру. Логіку предикатів трактують як розширення логіки висловлювань через виявлення внутрішньої структури висловлювань і введення нових термінів та системи аксіом.

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

Логіка предикатів як система створюється відповідно до загальних принципів побудови формальних систем. Особливість логіки предикатів полягає в тому, що вона є складнішою і за семантикою, і за синтаксисом порівняно з логікою висловлювань. Розрізняють семантику та синтаксис логіки предикатів.

У семантичному аспекті визначають суб'єктно-предикатну структуру висловлювань на змістовному рівні. Це дає змогу виявити властивості, притаманні певній сукупності емпіричних або абстрактних об'єктів, і ввести терміни, котрі відокремлюють сферу дії предикатів: висловлювання, властивість, відношення, предикат, одномісний предикат, багатомісний предикат, квантор загальності, квантор існування, істинне значення висловлення.

Висловлення, в якому емпіричному чи абстрактному об'єктові приписують певну властивість Р або визначаються відношення між об'єктами, надають два значення істинності: «істина» (і); «хиба» (х). Відповідно, логіка предикатів — двозначна за кількістю значень істинності висловлювань.

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

Структура логіки предикатів — алфавіт, правила побудови формул із символів алфавіту, правила дедуктивного виведення з аксіом нових формул (доведення теорем), правила інтерпретації.

Мова логіки предикатів — це система символів, що створюють алфавіт. До нього належать символи, введені в логіці висловлювань, і нові символи, які позначають терміни, введені в логіці предикатів.

Алфавіт

• маленькі латинські літери можливо з індексами або без них, які називаються предикатними змінними або термами;
• великі латинські літери з індексами знизу або без них, які називаються висловлюваними змінними;
• $P_{n}(x_{1},...,x_{n})$, $Q(x_{1},...,x_{n})$ предикатні змінні;
• символи логічних операцій ¬, ∧, ∨, →;
• символи кванторів ∃, ∀;
• технічні символи: ( — ліва дужка;) — права дужка.

Терм — будь-яка предметна константа чи предметна змінна.

Термін предикат

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

Під n-місним предикатом $P(x_{1},...,x_{n})$ будемо розуміти деяку логічну функцію n змінних $x_{1},x_{2},...,x_{n}$, що визначена на множині Ω і приймає значення істина або хиба.

Область визначення предиката — множина Ω на якій визначений предикат.

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

Квантор загальності позначає висловлювання, в якому властивість Р приписують певному непорожньому класу загалом, що означає: для всіх елементів класу А притаманна властивість Р. Цей квантор має вираз «для всіх» («усі», «кожний», «будь-який», «який би не був»). Його позначають символом ∀ , а повна формула — ∀xP(x) (чит. кожному х притаманна властивість Р). Так, висловлювання "Для всіх індивідів класу людей притаманна властивість «бути смертними» "(«Усі люди смертні») зображають формулою ∀x Р(х).

Квантор існування позначає висловлювання про певний непорожній клас, в якому властивість Р притаманна лише декотрим елементам цього класу, тобто існують елементи класу А, яким притаманна властивість Р.

Квантор існування має вираз «існує» («деякі», «лише один»). Його позначають символом ∃, а повна формула — ∃хР(х) (чит. «існує» х, яке має властивість Р). Наприклад, висловлювання «Існують люди, котрим притаманна властивість писати вірші» («Декотрі люди пишуть вірші») зображають формулою ∃х Р(х).

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

Побудова формул логіки предикатів

1. Окремо взятий предикат називається елементарною формулою.
2. Якщо F і Q — формули логіки предикатів, то ¬ F, (F ∧ Q), (F ∨ Q), (F → Q) — формули.
3. Р(х) — формула, що виражає властивість (одномісний предикат).
4. R(x, у) — формула, яка виражає двомісний предикат.
5. R(x, у, z) — формула, що виражає тримісний предикат.
6. Якщо Р — формула і х — предметна змінна, то ∀x Р(х) і ∃x Р(х) є формулами.

Область дії квантора

Область дії квантора означає вираз, до якого належить квантор. ОДК обмежують дужками зліва і справа від виразу. Ліва дужка означає початок сфери дії, а права дужка — закінчення. У межах ОДК виокремлюють зв'язану та вільну змінні. Змінну, що слідує безпосередньо після квантора, називають підкванторною змінною, а формула, до якої належить квантор, — підкванторною формулою, або сферою дії квантора. Зв'язана змінна — змінна, яка входить до сфери дії кванторів загальності ∀ чи існування ∃ або обох відразу. Наприклад, у формулах ∀x P(x), ∃х Р(х) зв'язаною змінною є х.

Вільна змінна входить до певної формули, але не входить до сфери дії кванторів загальності ∀ чи існування ∃ на відміну від зв'язаної змінної. Так, у формулі ∀(P(x)) → Q(x) — змінна х зв'язана так само, як у формулі ∀x(P(x)), але вільна у виразі Q(x).

У логіці предикатів квантор загальності трактують як узагальнення кон'юнкції, а квантор існування — як узагальнення диз'юнкції, якщо множинність М значень змінної х є скінченною, тобто вона складається зі скінченної кількості предметів. Наприклад, $M=(x_{1},x_{2},x_{3},x_{4})$ записують:

1. як кон'юнкцію одиничних висловлювань, що означає: формула виду $\forall x(P(x))$ еквівалентна формулі $P(x_{1})\land P(x_{2})\land P(x_{3})\land P(x_{4})$;
2. як диз'юнкцію одиничних висловлювань, що означає: формула виду $\exists x(P(x))$ еквівалентна формулі $P(x_{1})\lor P(x_{2})\lor P(x_{3})\lor P(x_{4})$.

Квантифікація (лат. quantum — скільки; facio — роблю) — визначення обсягу суб'єкта та предиката в структурі висловлювання за допомогою кванторних термінів — «усі» («будь-який», «кожний») та «деякі»; логічна операція, за допомогою якої визначають сферу дії кванторів. Це перехід від формули виду Р(х) до формули виду ∃x(P(x)) або ∀х(Р(х)), унаслідок чого змінна х у формулі Р(х) перестає бути просто символом, а виражає певну властивість, притаманну класові А. Змінну х у формулі Р(х) називають вільною змінною, а після квантифікації — зв'язаною змінною, тобто у формулах ∃x(P(x)) і ∀х(Р(х)) змінна х стає зв'язаною. Квантифікація висловлювань набувають такого вигляду: Р(х, у) — двомісний предикат, визначений на множинності М. Квантор загальності та квантор існування можна використати і для змінної х і для змінної у. Змінна, до якої використано квантор, стає зв'язаною, а друга змінна — вільною.

За допомогою квантифікації (використання квантора для однієї зі змінних) двомісний предикат можна перетворити на одномісний, а тримісний — в двомісний. Значення істинності висловлювань з кванторами загальності й існування. Логіка предикатів є двозначною за кількістю значень істинності, тому висловлюванням із кванторами загальності й існування надають два значення істинності — «і», «х». Для визначення істинності висловлювання з кванторами загальності або існування задають множину М з певною кількістю елементів, для якої предикат є істинним. Значення істинності визначають за допомогою таблиці істинності.

Рівносильні формули логіки предикатів

Після квантифікації, тобто використання квантора загальності або існування до вільної змінної одномісного або n-місного предиката, можна отримати різні формули. Наприклад: ∀х∀yP(x, у); ∀у∀xP(x, у); ∃х∀yP(x, у); ∀х∃хР(х, у); ∃х∃yP(x, у).

Основні рівносильні формули логіки предикатів

Див. також

• Логіка першого порядку
• Методи представлення знань

Література

• Логічні числення // Філософський енциклопедичний словник / В. І. Шинкарук (гол. редкол.) та ін. — Київ : Інститут філософії імені Григорія Сковороди НАН України : Абрис, 2002. — 742 с. — 1000 екз. — ББК 87я2. — ISBN 966-531-128-X.
• Hurley, Patrick J. (2011 р.). A Concise Introduction to Logic (вид. 11). Wadsworth Publishing. ISBN 978-0840034175.

Джерела

• Логіка — Карамишева Н. В. [Архівовано 16 грудня 2013 у Wayback Machine.]