Математическая логика - Логические операции

Отрицание предиката

Определение 19.1. Отрицанием n-местного предиката $P(x_1,x_2,\ldots,x_n)$ , определенного на множествах $M_1,M_2,\ldots,M_n$ , называется новый n-местный предикат, определенный на тех же множествах, обозначаемый $\lnot P(x_1,x_2,\ldots,x_n)$ (читается: "неверно, что $P(x_1,x_2,\ldots,x_n)$ , который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых исходное высказывание превращается в ложное высказывание.

Другими словами, предикат $\lnot P(x_1,x_2,\ldots,x_n)$ таков, что для любых предметов $a_1\in M_1,a_2\in M_2,\ldots,a_n\in M_n$ высказывание $\lnot P(a_1,a_2,\ldots,a_n)$ является отрицанием высказывания $P(a_1,a_2,\ldots,a_n)$ .

Например, нетрудно понять, что отрицанием одноместного предиката " $x \leqslant 3$ ", определенного на множестве $\mathbb{R}$ , является одноместный предикат " $x>3$ ", определенный на том же множестве $\mathbb{R}$ . Отрицанием предиката "Река $x$ впадает в озеро Байкал" является предикат "Река $x$ не впадает в озеро Байкал" (оба одноместных предиката определены на множестве названий рек). Отрицанием предиката " $\sin^2x+\cos^2x=1$ " является предикат " $\sin^2x+\cos^2x\ne1$ " $(x,y\in \mathbb{R})$ .

Теорема 19.2. Для n-местного предиката $P(x_1,x_2,\ldots,x_n)$ , определенного на множествах $M_1,M_2,\ldots,M_n$ , множество истинности его отрицания $\lnot P(x_1,x_2,\ldots,x_n)$ совпадает с дополнением множества истинности данного предиката: $(\lnot P)^{+}= \overline{P^{+}}$ .

Здесь следует понимать, что дополнение рассматривается в множестве

$M_1\times M_2\times \ldots\times M_n$ , то есть $(\lnot P)^{+}= M_1\times M_2\times \ldots\times M_n\setminus P^{+}$ .

Доказательство. Согласно определениям 19.1, 18.3 и определению дополнения множества имеем

$\begin{aligned}(\lnot P)^{+}&= \bigl\{(a_1,a_2, \ldots, a_n)\colon\, \lambda \bigl(P(a_1,a_2,\ldots, a_n)\bigr)=0\bigr\}=\\ &= \bigl\{(a_1,a_2,\ldots,a_n)\colon\, (a_1,a_2,\ldots,a_n)\notin P^{+}\bigr\}=\\ &= \overline{P^{+}}= (M_1\times M_2\times \ldots\times M_n)\setminus P^{+}, \end{aligned}$

что и требовалось доказать.

Следствие 19.3. Отрицание предиката будет тождественно истинным тогда и только тогда, когда исходный предикат тождественно ложен.

Доказательство. В предыдущей лекции (пункт "Множество истинности предиката") тождественная истинность предиката выражена на языке множества истинности; она означает, что $(\lnot P)^{+}= M_1\times M_2\times \ldots\times M_n$ . Подставим в это равенство значение для $(\lnot P)^{+}$ из настоящей теоремы:

$(M_1\times M_2\times \ldots\times M_n) \setminus P^{+}= M_1\times M_2\times \ldots\times M_n\,.$

Вспоминая определение разности двух множеств и учитывая, что $P^{+}\subseteq M_1\times M_2\times \ldots\times M_n$ , заключаем, что $P^{+}=\varnothing$ . Значит, предикат $P(x_1,x_2,\ldots,x_n)$ тождественно ложен. Следствие доказано.

Рассмотрим еще один пример. Требуется выяснить, является ли предикат $O(f)\colon$ " $f$ — нечетная функция" отрицанием предиката $E(f)\colon$ " $f$ — четная функция" (оба одноместных предиката определены на множестве всех действительных функций одного действительного аргумента). Множество истинности $O^{+}$ предиката $O(f)$ не является дополнением множества истинности $E^{+}$ предиката $E(f)$ , потому что не всякая функция, не являющаяся четной, будет непременно нечетной. Другими словами, существуют функции, не являющиеся одновременно ни четными, ни нечетными (приведите пример!). Следовательно, предикат $O(f)$ не есть отрицание предиката $E(f)$ .

Замечание 19.4. В алгебре высказываний существенным было не содержание высказывания, а лишь его значение истинности, т.е. отождествлялись (не различались) между собой, с одной стороны, все истинные высказывания, а с другой — все ложные. В некотором смысле аналогичная ситуация имеется и в алгебре предикатов: здесь не различают равносильные предикаты. Подходя с такой точки зрения к определению 19.1 отрицания предиката, можем за отрицание данного предиката $P(x_1,x_2,\ldots,x_n)$ принять любой из равносильных предикатов, удовлетворяющих этому определению. Например, отрицанием предиката " $|x|>2$ ", заданного на $\mathbb{R}$ , является каждый из следующих (равносильных между собой) предикатов:

$|x|\leqslant 2,\qquad (x \geqslant -2)\lor (x \leqslant 2),\qquad x\in[-2;2],$

а отрицанием предиката " $x^2 \geqslant 0$ ", также определенного на $\mathbb{R}$ (этот предикат тождественно истинный), является каждый из следующих предикатов:

$\sin{x}=2,\quad x^2<0,\quad e^x<0,\quad |x|<0$ и т.д.

Сделанное замечание следует иметь в виду при рассмотрении и остальных логических операций в настоящем параграфе.

Конъюнкция двух предикатов

Определение 19.5. Конъюнкцией "-местного предиката $P(x_1,x_2,\ldots,x_n)$ , определенного на множествах $M_1,M_2,\ldots,M_n$ , и m-местного предиката $Q(y_1,y_2,\ldots,y_m)$ , определенного на множествах $N_1,N_2,\ldots,N_m$ , называется новый (n+m)-местный предикат, определенный на множествах

$M_1,M_2,\ldots,M_n,\, N_1,N_2,\ldots,N_m$ , обозначаемый $P(x_1,x_2,\ldots,x_n)\land Q(y_1,y_2,\ldots,y_m)$

(читается " $P(x_1,x_2,\ldots,x_n)$ и $Q(y_1,y_2,\ldots,y_m)$ "), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания.

Другими словами, предикат $P(x_1,x_2,\ldots,x_n)\land Q(y_1,y_2,\ldots,y_m)$ таков, что для любых предметов $a_1\in M_1,a_2\in M_2,\ldots,a_n\in M_n$ и $b_1\in N_1,b_2\in N_2,\ldots,b_m\in N_m$ высказывание $P(a_1,a_2,\ldots,a_n)\land Q(b_1, b_2, \ldots, b_n)$ является конъюнкцией высказываний $P(a_1,a_2,\ldots,a_n)$ и $Q(b_1, b_2, \ldots,b_m)$ .

Например, конъюнкцией двух одноместных предикатов " $x>-3$ " и " $x<3$ ", определенных на $\mathbb{R}$ , будет одноместный предикат " $(x>-3)\lor (x<3)$ ", записываемый короче в виде: " $-3<x<3$ ", который равносилен предикату " $|x|<3$ " (см. замечание 19.4).

Другой пример. Конъюнкцией двух одноместных предикатов " $x=0$ " и " $y=0$ ", заданных на $\mathbb{R}$ , является двухместный предикат " $(x=0)\lor (y=0)$ ", заданный на $\mathbb{R}^2$ , который равносилен предикату " $x^2+y^2=0$ ", определенному также на $\mathbb{R}^2$ .

Операцию конъюнкции можно применять к предикатам, имеющим общие переменные. В этом случае число переменных в новом предикате равно числу $n+m-k$ , где $n$ — число переменных первого предиката, $m$ — число переменных второго предиката, $k$ — число переменных общих для обоих предикатов. Именно таков первый из только что рассмотренных двух примеров. Более того, если оба предиката определены на одних и тех же множествах и зависят от одних и тех же переменных, то для них справедлива следующая теорема.

Теорема 19.6. Для n-местных предикатов $P(x_1,x_2,\ldots,x_n)$ и $Q(x_1,x_2,\ldots,x_n)$ , определенных на множествах $M_1,M_2,\ldots,M_n$ , множество истинности конъюнкции $P(x_1,x_2,\ldots,x_n)\land Q(x_1,x_2,\ldots,x_n)$ совпадает с пересечением множеств истинности исходных предикатов:

$(P\land Q)^{+}= P^{+}\cap Q^{+}$

Доказательство. Согласно определениям 19.5, 18.3 и определению пересечения множеств имеем

$\begin{aligned}(P\land Q)^{+}&= \bigl\{(a_1,a_2,\ldots, a_n)\colon\, \lambda\bigl(P(a_1, a_2, \ldots, a_n)\land Q(a_1,a_2, \ldots,a_n\bigl)\bigr)=1\bigr\}=\\[2pt] &= \bigl\{(a_1,a_2,\ldots,a_n)\colon\, \lambda\bigl(P(a_1,a_2,\ldots,a_n)\bigr)=1,\, \lambda\bigl(Q(a_1,a_2, \ldots,a_n)\bigl)=1\bigl\}=\\[2pt] &= \bigl\{(a_1,a_2,\ldots,a_n)\colon\, \lambda\bigl(P(a_1, a_2,\ldots, a_n)\bigr)= 1\bigr\}\,\cap\\ &\phantom{=~} \cap \bigl\{(a_1,a_2,\ldots,a_n)\colon\, \lambda\bigl(Q(a_1,a_2, \ldots, a_n)\bigr)=1\bigr\}=\\[2pt] &= P^{+}\cap Q^{+}.\end{aligned}$

Дизъюнкция двух предикатов

Определение 19.8. Дизъюнкцией n-местного предиката $P(x_1, x_2, \ldots, x_n)$ , определенного на множествах $M_1,M_2,\ldots,M_n$ , и m-местного предиката $Q(y_1,y_2,\ldots,y_m)$ , определенного на множествах $N_1,N_2,\ldots,N_m$ , называется новый (n+m)-местный предикат, определенный на множествах $M_1,M_2,\ldots,M_n$ и $N_1,N_2,\ldots,N_m$ , обозначаемый

$P(x_1, x_2, \ldots, x_n)\lor Q(y_1,y_2,\ldots,y_m)$

(читается " $P(x_1, x_2, \ldots, x_n)$ или $Q(y_1,y_2,\ldots,y_m)$ "), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один из исходных предикатов.

Другими словами, предикат $P(x_1, x_2, \ldots, x_n)\lor Q(y_1,y_2,\ldots,y_m)$ таков, что для любых предметов

$a_1\in M_1,a_2\in M_2,\ldots,a_n\in M_n$ и $b_1\in N_1,b_2\in N_2,\ldots,b_m\in N_m$

высказывание $P(a_1, a_2, \ldots, a_n)\lor Q(b_1,b_2, \ldots, b_m)$ является дизъюнкцией высказываний $P(a_1, a_2, \ldots, a_n)$ и $Q(b_1,b_2,\ldots,b_m)$ .

Операцию дизъюнкции, как и операцию конъюнкции (см. абзац перед теоремой 19.6), можно применять, в частности к предикатам, имеющим общие переменные. Например, дизъюнкцией двух одноместных предикатов " $x$ — четное число" и " $x$ — простое число", определенных на $\mathbb{N}$ , является одноместный предикат, определенный на $\mathbb{N}:$ " $x$ — четное или простое число".