<<
>>

Элементы исчисления предикатов

Развитием исчисления высказываний является исчисление предикатов. Пусть хг- (/ = 1, 2, ..., т) - заданные на некотором конечном или бесконечном множестве (поле) М переменные, называемые предметными, а их конкретные значения - индивидуальные предметы из этого множества.
Предметными переменными могут быть, например, целые, действительные, комплексные числа; буквы различных алфавитов, химические символы, геометрические фигуры, фамилии (имена) членов некоторого коллектива и многое

24

др. Пусть также имеется набор функциональных символов (функций) с различным числом аргументных мест. Такими функциональными символами могут быть символы, описывающие математические функции; химические, экономические или финансовые формулы (правила), заготовки для слов, строк, таблиц, изображений, диаграмм, блок-схем с различным числом свободных (аргументных) мест и т.п.
Из предметных переменных и функциональных символов можно конструировать так называемые термы, интерпретируемые как имена объектов исследования (математические выражения, слова и тексты, химические или ядерные реакции, изображения, блок-схемы и др.).

Тогда п-местным (п-арным) предикатом называется функция Р(?1, 12,...,tn ), которая представляет собой некоторое высказывание о термах ^,12,...,tn (п > 0) и может принимать лишь значения «истина» или «ложь» в зависимости от индивидуальных предметов X}, Х2,... из М, входящих в эти термы. При п = 1 предикат называют свойством, а при п > 1 - отношением или, конкретнее, п-арным отношением. Изучаемые в исчислении высказываний отдельные высказывания могут формально рассматриваться как нульместные предикаты.

Таким образом, аргументами функций исчисления высказываний являются лишь высказывания, тогда как аргументами предикатов могут быть любые предметные переменные.

При этом число мест, т.е. число термов в предикате, вообще говоря, отличается от числа аргументов. Пусть, например,- буквы русского алфавита,

а- действительные числа. Образуем термы

(слово из четырех букв с одинаковыми первой и третьей буквами):Тогда высказывание «- имя

собственное» - одноместный предикат (свойство) с тремя аргументами (), а высказывание «» - двуместный предикат

(отношение), зависящий от четырех аргументовДля

простейших математических отношений «меньше», «меньше или равно», «равно», «не равно», «больше или равно», «больше» в алгоритмических языках программирования имеются соответствующие символы или зарезервированные слова.

25

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

которые можно также рассматривать как новые предикаты. В этих формулах могут использоваться и высказывания алгебры логики (нульместные предикаты).

Помимо операций алгебры высказываний, в исчислении предикатов используются так называемые кванторы - логические операторы, переводящие одну высказывательную форму в другую и позволяющие указывать объем тех значений предметных переменных х, для которых данная высказывательная форма истинна.

Обычно в логике предикатов ограничиваются двумя кванторами - квантором общности Ух и квантором существования Зх. Пусть х - предметная переменная, принимающая значения из множества (поля) М. Тогда выражение

(1.9)

начинающееся квантором общности, представляет собой высказывание: «для всякогоистинно. Поскольку задание лю

бых индивидуальных предметов (значений) х е М не нарушает истинность Р(х), высказывание (1.9) уже не зависит от х. Говорят, что предметная переменная х связана квантором общности, и поэтому такие переменные называют связанными.

Выражение

(1.10)

начинающееся квантором существования, понимается как высказывание: «существует такой элемент х е М , для которого Q(x) истинно». Это высказывание также вполне определено и уже не зависит от х, т.е. переменная х связана квантором существования и является связанной переменной.

Кванторы общностии существования Зх называются двойственными друг другу. В формулы (1.9), (1.10), кроме х, могут входить и другие предметные переменные (не показанные в формулах). Поскольку эти формулы не зависят от х, они полностью определяются заданием остальных переменных. Такие предметные пе-

26

ременные, не связанные никакими кванторами, называют свободными.

Существует закон, связывающий кванторы со знаком отрицания. Рассмотрим выражение

(1.11)

Очевидно, выраженное (1.11) высказывание «УхР(х) ложно» равносильно высказыванию «существует такой элемент х е М , для которого Р(х) ложно» или, что то же самое, «существует элемент х, для которого 1 Р( х) истинно».

Следовательно, выражение (1.11) равносильно выражению

(1.12)

Аналогично, выражение

(1.13)

означающее высказываниеложно», равносильно высказыванию «для всех х ложноили «для всех х истинно».

Следовательно, выражение (1.13) равносильно выражению

. (1.14)

Таким образом, стоящий перед квантором знак отрицания можно внести под знак квантора, заменив квантор на двойственный. Рассмотренные конструкции математической логики часто используются при записи алгоритмов.

1.1.

<< | >>

Еще по теме Элементы исчисления предикатов:

  1. Позиции-предикаты
  2. Позиции-предикаты
  3. § 27 Действие давности на обязательства. – Погашение права на иск. – Начало исчисления давности. – Открытие права на иск. – Исчисление давности в срочных и бессрочных договорах, при периодическом исполнении, по обязательствам главным и зависящим. – Перерыв давности – признанием долга. – Постановления русского закона о сем предмете.
  4. Статья 73. Исчисление сроков наказания
  5. 1. Понятие, исчисление и виды сроков в гражданском праве
  6. Глава 18 - Гражданского кодекса Определение и исчисление сроков
  7. Глава 18 - Гражданского кодекса Определение и исчисление сроков
  8. 2. Исчисление сроков
  9. 3. Исчисление сроков исковой давности
  10. § 2. Исчисление, приостановление и восстановление процессуальных сроков
  11. Статья 90. Исчисление сроков погашения судимости
  12. 20. Сроки в гражданском праве: понятие, виды, исчисление (56-Й ВОПРОС)
  13. 21. ИСКОВАЯ ДАВНОСТЬ: ПОНЯТИЕ, ВИДЫ, ПРИМЕНЕНИЕ И ИСЧИСЛЕНИЕ (57-Й ВОПРОС)