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

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

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

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

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

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

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

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

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

Алфавіт

  • маленькі латинські літери можливо з індексами або без них, які називаються предикатними змінними або термами;
  • великі латинські літери з індексами знизу або без них, які називаються висловлюваними змінними;
  • , предикатні змінні;
  • символи логічних операцій ¬, , , ;
  • символи кванторів , ;
  • технічні символи: ( — ліва дужка;) — права дужка.

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

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

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

Під n-місним предикатом будемо розуміти деяку логічну функцію 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).

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

  1. як кон'юнкцію одиничних висловлювань, що означає: формула виду еквівалентна формулі ;
  2. як диз'юнкцію одиничних висловлювань, що означає: формула виду еквівалентна формулі .

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

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

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

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

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

Див. також

Література

Джерела

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.