§ 4. Понятие формулы логики предикатов

В логике предикатов будем пользоваться следующей символикой:

1. Символы р, ^, г, ... - переменные высказывания, принимающие два значения: 1 — истина, 0 — ложь.

2. Предметные переменные — х, у, г, ..., которые про­ бегают значения из некоторого множества М; х°, у°, г°, ... - предметные константы, то есть значения предметных пере­ менных.

3. Р(-), ^"('} ~~ одноместные предикатные перемен­ ные; (?(•,•,...,•), Л(•,-,...,•) - и-местные предикатные переменные.

'*(')» 9 ('»•»•••>•) ~ символы постоянных предика­тов.

4. Символы логических операций: &, v ,-»,-.

5. Символы кванторных операций: Уж, Зл:.

6. Вспомогательные символы: скобки, запятые. Определение формулы логики предикатов.

1. Каждое высказывание как переменное, так и по­ стоянное, является формулой (элементарной).

2. Если Р\ •,-,...,•) - га-местная предикатная пе­ ременная или постоянный предикат, а х_г, х₂ х_п пред­ метные переменные или предметные постоянные (не обяза­ тельно все различные) , то Р(х1,х₂,...,х_п) есть формула.

ЛОГИКА ПРЕДИКАТОВ

91

_ Курс лекций по математической лоаиме

Такая формула называется элементарной, в ней пред­метные переменные являются свободными, не связанны­ми кванторами.

3. Если А и В - формулы, причем такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой — свободной, то слова А v В , А&В , А —> В есть формулы. В этих формулах те переменные, которые в исходных формулах были свободными, явля­ ются свободными, а те, которые были связанными, яв­ ляются связанными.

4. Если А - формула, то А - формула, и характер предметных переменных при переходе от формулы А к

формуле А не меняется.

5. Если А(х) - формула, в которую предметная пере­ менная х входит свободно, то слова ЧхА(х} и ЭхА(ж) яв­ ляются формулами, причем предметная переменная входит в них связанно.

6. Всякое слово, отличное от тех, которые названы формулами в пунктах 1-5, не является формулой.

Например, если р(х) и (}(х,у) - одноместный и двухме­стный предикаты, а д, г - переменные высказывания, то

формулами будут слова: д, р(х], Р(*)&Ф(*°,{П, УхР(х\ ->•

^ / \ / '

->• Эx^(x, у), Ю(х, у) v д\ -+ г .

Не является формулой слово: Ух()(х, у) -» р(х} . Здесь нарушено условие п.З, так как в формулу Ух()(х,у} пе­ременная х входит связано, а в формулу р(х] перемен­ная х входит свободно.^--"'

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

* § 5. Значение формулы логики предикатов

О логическом значении формулы логики предика­тов можно говорить лишь тогда, когда задано множе­ство М, на котором определены входящие в эту форму­лу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов пере­менных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикат­ных переменных.

При конкретных значениях каждого из трех видов переменных формула логики предикатов становится высказыванием, имеющим истинное или ложное зна­чение.

В качестве примера рассмотрим формулу

(1)

в которой двухместный предикат Р\х,у) определен на множестве М х М , где М = {0,1,2,...,га,...} .

В формулу (1) входит переменный предикат Р(х,у),

предметные переменные х, у, г, две из которых у и г -связанные кванторами, а х — свободная.

Возьмем за конкретное значение предиката р(х, у) фиксированный предикат Р°(х,у}: «х<у», а свобод­ной переменной х придадим значение х° - 5 е М . Тогда при значениях у, меньших х° = 5 предикат Р⁰(*⁰>у) при­нимает значение ложь, а импликация р(х, у) -> р(у, г) при всех г е М принимают значение истина, то есть

высказывание Зу Уг1р°(х,у)-+ Р^й(у,г)\ имеет значение «истина».