ОБЧИСЛЕННЯ ПРЕДИКАТІВ ПЕРШОГО ПОРЯДКУ

Визначення логіки предикатів

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

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

-л - «не», «невірно, що»,

V - «або», «або», л - «і», «а», «але»,

-> - «якщо», «за умови, що",

= - «рівносильно», «еквівалентно», «тоді і тільки тоді, коли».

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

Логіка предикатів дозволяє врахувати внутрішню структуру простих висловлювань, забезпечуючи тим самим більш точне уявлення знань і міркувань про властивості предметної області. Розглянемо простий вислів «5 є цілим позитивним числом». У логіці висловлювань воно може бути позначено єдиним пропозіціональним символом р. У логіці предикатів це просте висловлювання може бути представлено формулою / (5) л / > (5), в якій використані одномісні предикати: 1 (х) - означає «* - ціле число»,

Р (х) - означає «х - позитивне число».

Інша просте висловлювання «квадрат будь-якого дійсного числа позитивний» в логіці висловлювань може бути позначено єдиним пропозіціональним символом q. У логіці предикатів воно може бути представлено формулою

в якій

V - квантор спільності, що позначає фрази: «все», «будь-який», «довільний», «для всіх» і т. П.,

R (x) - предикат, що означає «х - дійсне число»,

Q (x) - предикат, що означає «х - невід'ємне число», s (x) - функція, що визначається рівністю s (x) = х 2 .

Поряд з квантором спільності в логіці предикатів використовується квантор існування 3, який служить для позначення фраз і словосполучень: «існує», «є», «який-небудь», «для деякого» і т. П.

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

1. Алфавіт

а , b , с, ... - константи, х, у, z , ... - змінні,

/, G, / 7, ... - функціональні символи; кожен символ характеризується деяким натуральним числом т - число аргументів символу; це число називають арность , або місцевість символу,

Р, Q, R , ... - предикатні символи; кожен символ також характеризується деякими натуральним числом п - число аргументів символу; це число називають арность , або місцевість , символу,

/ ?, q , г , ... - пропозіціональние символи (символи висловлювань), -1, -> - логічні зв'язки (заперечення, імплікація),

V - квантор спільності,

О, 1 - символи значень істинності: 0 - «брехня» і 1 - «істина»

  • (,) - дужки; використовуються для правильного запису та інтерпретації формул.
  • 2. Синтаксичні правила
  • - символи 0 і 1 є формулами,
  • - будь-який пропозіціональний символ є формула,
  • - якщо А є формула, то (А) теж є формулою,
  • - якщо А , А х і А 2 є формулами, то вираження -А, А { АА 2 , A t vA 2 , A t -> A 2 і А ] = А 2 теж є формулами,
  • - якщо Р- / 7-місцевий предикатний символ, х ,, х 2 , ..., х "- змінні, то вираз Р (х ь х ь ..., х") є формулою,
  • - якщо А (х ,, х 2 , ..., х ") - формула, в якій відсутні квантори, то вираз / г, Л (Xj, х 2 , ..., х") є формулою, при цьому в ній х, називається пов'язаної змінної , а інші змінні називаються вільними.
  • 3. Аксіоми (А) А ^> (А ^ В)
  • 042) 04-> (Я-> С)) -> (04 - "/?) -" 04-> 0)
  • 043) (-i /? - »- u4) -> 04-> Д)
  • 044) {VtB ( t )) -> В (і), де і - змінна і B (t ) не містить і як пов'язаної змінної,
  • 045) (/ t (A ^ B)) ^> (A-> Vt (B)), де А і В є формулами, а / не є вільною змінною в формулі А.

Зауважимо, що перші три аксіоми такі ж, як в логіці висловлювань.

4. Правила виведення

- правило modus ponens,

- правило узагальнення, де t - вільна змінна в А

 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >