Предикатна логіка

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

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

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

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

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

Алфавіт[ред.ред. код]

  • маленькі латинські літери можливо з індексами або без них, які називаються предикатними змінними або термами;
  • великі латинські літери з індексами знизу або без них, які називаються висловдюваними змінними;
  •  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) як кон'юнкцію одиничних висловлювань, що означає: формула виду ∃ x (P(x)) еквівалентна формулі  P(x_1) P(x_2)  P(x_3)P(x_4) ; 2) як диз'юнкцію одиничних висловлювань, що означає: формула виду ∀х(Р(х)) — еквівалентна формулі  P(x_1)P(x_2) P(x_3) P(x_4) .

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

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

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

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

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

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

Див. також[ред.ред. код]

Джерела[ред.ред. код]