Логика предикатов первого порядка является расширением логики высказываний: к языку логики высказываний добавляются следующие категории символов - индивидные константы, индивидные переменные, предикаты и кванторы.
Тем самым предполагается, что студент полностью усвоил материал из классической логики высказываний. Синтаксис и семантика логики предикатов § 1. Синтаксис логики предикатов Пунктами 1) - 6) зададим язык логики предикатов первого порядка. 1. Логические связки (константы.): л - (конъюнкция); v - (дизъюнкция); (отрицание); ^ - (импликация), о- - (эквивален- ция). 2. Конечное или счетное множество индивидных констант: а, в, с, aj, Bi, cj,— 3. Конечное или счетное множество индивидных переменных: х, у, z, Xj, yt, Zj,... 4. Конечное или счетное множество предикатных символов: PJ,—, P0, PJ,—, P;,—, P,., PJ;,..., где верхний индекс указывает число аргументных мест предиката; нульместный предикат P0есть пропозициональная переменная, т. е. символы высказываний. Предикаты, у которых не меньше двух аргументов, часто называют отношениями. 5. Кванторы: всеобщности - V (для всех, для каждого), существования - 3 (существует, для некоторых). 6. Технические (вспомогательные) знаки: «(» - левая скобка, «)» - правая скобка. Определение 1. Термом называется наименьшее множество, удовлетворяющее следующим условиям: - любая индивидная константа есть терм; - любая индивидная переменная есть терм. Ничто иное, кроме того, что указано в пунктах 1. и 2 не может быть термином. Условимся обозначать произвольный терм (индивидную константу или индивидную переменную) символом t, если они различны, то это будем отмечать различными нижними индексами, например tt, t2. Определение 2 (формулы): 1. Атомарной формулой называется выражение вида P(tx,—, tk), где к число аргументов атомарной формулы, 1 < к < n. 2. Любая атомарная формула языка логики предикатов первого порядка является формулой. 3. Если А произвольная формула логики предикатов первого порядка, то ~А - формула. 4. Если А и В произвольные формулы языка логики предикатов первого порядка, то АлВ, AvB, А^-В, АоВ тоже формулы. 5. Если А (х) - произвольная формула, то VxA (х), ЗхА (х) то - же формулы. Вхождение переменной «х» в формулы VхА(х), ЗхА(х) называются связанными (кванторами).
Методическое указание. Обратите внимание, что в отличие от логики высказываний, в логике предикатов атомарная формула определяется. «А» и «В» - это метапеременные для формул, т. е. они, могут обозначать произвольную формулу языка логики предикатов первого порядка. Определение 3 (свободного вхождение переменной в формулу): 1. Все переменные атомарной формулы являются свободными вхождениями переменной в атомарную формулу. 2. Если переменная «у» входит свободно в формулу А (т. е. А имеет вид А (у)), то переменная «у» входит свободно и в фор - мулу ~А. 3. Если переменная «у» свободно входит в формулу А или В, то она свободно входит и в формулы А л В, А v В, А ^ В, А о В. 4. Если переменная «у» входит свободно в формулу А, то она сво - бодно входит в формулы VхА (х), ЗхА (х), при условии, что пе - ременные «у» и «х» различны. Переменная называется связанной (квантором), если она не является свободной. Определение 4. Предложением (замкнутой формулой - другое название) называется формула языка логики предикатов, которая не имеет свободных вхождений переменной. Определение 5 (правильной подстановки термина на место свободной переменной). Подстановка есть отображение 8 из множества переменных в множество термов. Пусть 8 - подстановка. Через 8х обозначим подстановку, которая отличатся от подстановки 8 тем, что не замещает переменной «х» никаким термином, т. е. для любой переменной «у» имеем: 8 (у), если у ^ х х, если у=х Распространим понятие подстановки на формулу: 1. 8 (P (tlV..,tn)) = P (8 (^),...,8(tn)), где P (^,...фп) атомарная формула. 2. 8 (~А) = ~8 (А). 3. 8 (А ^ В) = 8 (А) ^ 8 (В). 4. 8 (VA (х)) = Vx (8хА (х)). 5. 8 (ЗА (х)) = Зх (8хА (х)), т. е. 8х не затрагивает связанную переменную х. Подстановка называется правильной (свободной), если результат фиксированной подстановки не содержит ни одной переменной, находящейся в области действия квантора. 1. 8 свободна для формул А, если А - атомарная формула. 2. 8 свободна для ~А, если 8 свободна для А. 3. 8 свободна для А ^ В, А л В, А v В, А о- В если 8 свободна для А и 8 свободна для В. 4. 8 свободна для формул VxА(x) и ЗхА(х), если 8 свободна для А (х), т. е. переменная у, у Фх, свободна для А (х). Например, в формуле с конкретным двуместным предикатом Зх(у