Математическая логика и теория алгоритмов. Стенюшкина В.А. - 14 стр.

ми. При замещении предметной переменной хк, к∈1..n, предметной постоянной
а∈M n-местный предикат Р(x1,…, xn) превращается в (n-1) местный предикат
Р(х1,…,хк-1,a,хк+1,…,хn) и от хк уже не зависит. Если заместить все переменные
постоянными, то получится высказывание, или нульместный предикат.
       Пример - Р(x1, x2, x3):= «x1+x2=x3» - трехместный предикат; Р(x1, x2, 5):=
«x1+x2=5» - двухместный предикат; Р(2,3,5):= «2+3=5» - высказывание.
       N-местным функтором на множестве M называется n-местная функция
f(x1,…, xu), принимающая, как и аргументы, значения из множества M (то есть
n-местный функтор задает n-местную операцию на M).

       3.2 Операции над предикатами. Кванторы

       Пусть Р(х), Q(x), х∈М, для которых предикат Р(х) ложен.
       Отрицанием предиката Р(х) на множестве M называется предикат  Р(х)
на том же множестве, истинный для тех и только тех значений х∈М, для кото-
рых предикат Р(х) ложен.
       Конъюнкцией предикатов Р(х), Q(x) на множестве M называется преди-
кат Р(х)∧Q(x) на том же множестве, истинный для тех и только тех значений
х∈М, для которых оба предиката Р(х), Q(x) истинны.
       Дизъюнкцией предикатов Р(х), Q(x) на множестве M называется преди-
кат Р(х)∨Q(x) на том же множестве, истинный для тех и только тех значений
х∈М, для которых истинен хотя бы один из предикатов Р(х), Q(x).
       Подобным образом вводятся предикаты Р(х) →Q(x), Р(х)↔Q(x).
       Пример – Даны предикаты: Р(х):= «х<5», Q(x):= «х≥2», х∈{1,2,3,4,5}
=М. Тогда Р(х):= «х≥5», Р(х)∧Q(x):=«2≤х<5»; Р(1)∧Q(1)=0, Р(2)∧Q(2)=1.
       Над многоместными предикатами операции определяются аналогичным
образом. Так, отрицанием n-местного предиката на некотором множестве М
называется n-местный предикат Р(x1,…, xn) на том же множестве М, истинный
для тех и только тех наборов значений аргументов, для которых предикат
Р(x1,…, xn) ложен.
       Для предикатов вводится также специфические логические операции,
или кванторы, - ∀ («каждый» или «для всех») – квантор общности и ∃ («сущес-
твует» или «для некоторых») – квантор единичности.
       Пусть Р(х), х∈М – одноместный предикат. Тогда запись ∀х Р(х) («для
любого х Р(х)») означает высказывание, истинное, если Р(х) – тождественно
истинен на М, и ложное, если Р(х) не является тождественно истинным на М;
запись ∃х Р(х) («существует х такой, что Р(х)») означает высказывание, истин-
ное, если Р(х) выполним на М, и ложное, если Р(х) невыполним на М.
       Пример – Если Р(х):= «х2=1», х∈М=(-∞,+∞), то ∀х Р(х)=0, ∃х Р(х)=1.

       Специфические равносильности:       ∀ хР( х) = ∃х Р( х), ∃ хР( х) = ∀ х Р( х).

       Дадим определение квантификации для многоместных предикатов.