<<
>>

3.2. Исчисление предикатов

Исчисление предикатов первого порядка – это формальная теория K, в которой определены :

1. Алфавит:

· Связки: (основные), & , ( дополнительные).

· Служебные символы: (,).

· Кванторы ,.

· Предметные константы a,b,c,….

· Предметные переменные x, y, z,….

· Символы предикатов P,Q,R,….

· Символы функций f, g, h,….

Константы, переменные, функторы – называются термами.

2. Формулы. Слово называется формулой, если оно имеет следующий синтаксис:

1) Р(х1,…,хn) – атомарная формула (А).

Вхождения переменных в атомарную формулу называются свободными.

2) Если А – формула, то - тоже формула.

3) Если А и В – формулы, то - формулы.

4) Если А – формула, содержащая свободную переменную х, то - формулы.

Слово является формулой, если это следует из 1-4.

Вхождения переменных в формулах называются связанными, переменные не равные х остаются свободными.

Пример

- х – свободная переменная, у – связанная переменная.

Формула, не содержащая свободных переменных, называется замкнутой.

3. Аксиомы (логические).

1) Любая система аксиом исчисления высказываний.

А1:

А2:

А3:

2) Собственные аксиомы.

P1: ,

P2:,

где t – терм.

4. Правила вывода.

1. ,

2. - введение квантора общности,

3. - введение квантора существования.

Исчисление предикатов, в котором кванторы могут связывать только предметные переменные и не могут связывать функторы или предикаты называется исчислением первого порядка.

<< | >>
Источник: Викентьева О. Л.. Математическая логика и теория алгоритмов. Конспект лекций для студентов специальностей АСУ, ЭВТ, КЗИ. Пермь, 2007г.. 2007

Еще по теме 3.2. Исчисление предикатов:

  1. Глава 10. Теория доказательства: кваиториые правила
  2. Выражение силлогистики средствами логики предикатов
  3. Наука как специфический тип знания
  4. § 1. Расчетливость (to loyiaxikov) как разумная способность человеческой души
  5. ВВЕДЕНИЕ[*]
  6. Базисный ассерторический язык
  7. Примеры
  8. Вопросы типа элементарных
  9. Почему-вопросы
  10. ГЛАВА 4 ВОЗМОЖНЫЕ ПРИЛОЖЕНИЯ
  11. Список сокращений
  12. Исчисление предикатов.
  13. ГИЛЬБЕРТ