Предметом изучения в этой главе будут предикаты — отображения произвольных множеств во множество высказываний. Фактически, мы совершаем переход на новый уровень абстракции, переход такого типа, какой был совершен в школе — от арифметики вещественных чисел к алгебре числовых функций.
Определение. Пусть X1,X2 … Xn — символы переменных произвольной природы. Эти переменные будем называть предметными. Пусть наборы переменных (X1,X2 … Xn) принадлежат множеству M=(M1,M2 … Mn), которое будем называть предметной областью (т.е. Xi∈Mi, где Мi называются областью определения переменной Xi). Предикатом местности n (n-местным предикатом), определенным на предметной области M, называют логическую функцию принимающую либо значение И либо значение Л.
Пример 1. D(x1,x2) = «Натуральное число х1 делится (без остатка) на натуральное число х2» — двуместный предикат, определенный на множестве пар натуральных чисел M=N N. Очевидно, D(4,2) = И, D(3,5) = 0.
Пример 2. Q(x) == «x2<-1, х∈R» — одноместный предикат, определенный на множестве действительных чисел М=R. Ясно, что Q(-1) = Л, Q(5) = Л, и вообще предикат Q(x) — тождественно ложен, т. е. Q(x) = Л для всех х∈R.
Пример 3. В(x,у,z) = «х2+y2<z; х,у,z∈R» — трехместный предикат, определенный на R3. В(1,1,-2)=Л, В(1,1,2)=И.
Предикат Р, определенный на M, называется тождественно истинным, если он принимает значение И при любых значениях предметных переменных; Предикат Р называется тождественно ложным, если он принимает значение Л при любых значениях предметных переменных. Предикат Q из примера 2 является тождественно ложным.
Поскольку предикаты — это функции со значениями во множестве высказываний, где введены логические операции, то эти операции естественно определяются и для предикатов. Пусть P и Q — предикаты, определенные на M. Тогда:
1. ¬P(x1,x2 … xn) = ¬(P(x1,x2 … xn))
2. (P&Q)(x1,x2 … xn) = P(x1,x2 … xn)&Q(x1,x2 … xn)
3. (PvQ)(x1,x2 … xn) = P(x1,x2 … xn)vQ(x1,x2 … xn)
4. (P→Q)(x1,x2 … xn) = P(x1,x2 … xn)→Q(x1,x2 … xn)
Предикаты Р и Q, определенные на M, называются равносильными (пишут Р=Q), если P(x1,x2 … xn)=Q(x1,x2 … xn) для любого набора (x1,x2 … xn) предметных переменных из M.
Теорема. Множество n-местных предикатов, определенных на M, образует булеву алгебру предикатов. Т.е. для них справедливы основные эквивалентности.