Логические операции над предикатами

Если заданы два предиката P(x₁ , … , x_n ) и Q(x₁ , … , x_n) с одной и той же областью определения Aⁿ и одним и тем же набором переменных, то можно рассмотреть предикаты (x₁ , … , x_n), (P Ù Q)(x₁ , … , x_n), (P Ú Q)(x₁ , … , x_n), (P ® Q)(x₁ , … , x_n), (P « Q)(x₁ , … , x_n), называемые соответственно отрицанием предикатаP, а также конъюнкцией, дизъюнкцией, импликацией и эквивалентностью предикатовP и Q. Эти новые предикаты определяются следующим образом: для любых a₁ , … , a_n Î A полжим (a₁ , … , a_n) = и при w Î {Ù , Ú , ® , « } (P w Q)(a₁ , … , a_n) = (P(a₁ , … , a_n) w Q(a₁ , … , a_n)).

Примеры: 1. Пусть на Rзаданы два предиката: P(x) = “x > 3” и Q(x) = = “x £ 5”. Тогда для любого a Î Rимеем

(a) = = “a £ 3”, (a) = = “a > 5”,

(PÙQ)(a) = “a > 3” Ù “a £ 5” = “3 < a £ 5”,

(PÚQ)(a) = “a > 3” Ú “a £ 5” = “a Î R” = 1,

(P®Q)(a) = “a > 3” ® “a £ 5” º Ú “a £ 5” = “a £ 3” Ú “a £ 5” = “a £ 5”,

(P«Q)(a) = “a > 3”« “a £ 5” º ( ) Ú (“a > 3” Ù “a £ 5”) =

= (“a £ 3”Ù“a > 5”) Ú “3 < a £ 5” º 0 Ú “3 < a £ 5” º “3 < a £ 5”.

Ясно, что в этом примере верны следующие равенства множеств:

D₁( ) = D₀(P), D₀( ) = D₁(P), D₁(PÙQ) = D₁(P) Ç D₁(Q),

D₀(PÙQ) = D₀(P) È D₀(Q), D₁(PÚQ) = D₁(P) È D₁(Q), D₁(P®Q) = D₀(P) È D₁(Q),

D₁(P«Q) = (D₁(P) Ç D₁(Q)) È (D₀(P) Ç D₀(Q)) (проверьте !!).

2. Пусть P(x, y) = “x² < y”, Q(x, y) = “y £ x” – два предиката на Z. Вычислим предикат P ® Q и его область истинности.

По определению для любых a, b Î Z :(P ® Q)(a, b) = (P(a, b) ® Q(a, b)) = = “a² < b” ® “b £ a” º Ú “b £ a” º “a² ³ b” Ú “b £ a”. Когда истинна последняя дизъюнкция ? Она истинна, если b £ a. Но учитывая, что a Î Z, имеем a £ a², так что из b £ a следует b £ a², и (P ® Q)(a, b) º “b £ a ”.

Как и ранее, нетрудно понять, что D₁(P ® Q) = D₀(P) È D₁(Q).

Оказывается, что отмеченные в этих примерах соотношения, связывающие множества D₁(P w Q) и D₁(P), D₁(Q), D₀(P), D₀(Q), справедливы всегда.

Лемма (об областях истинности).Пусть P(x₁ , … , x_n), Q(x₁ , … , x_n) – два предиката на множестве А. Тогда верны равенства множеств:

D₁( ) = D₀(P) = D(P) \ D₁(P),

D₁(P Ù Q) = D₁(P) Ç D₁(Q),

D₁(P Ú Q) = D₁(P) È D₁(Q),

D₁(P ® Q) = D₀(P) È D₁(Q),

D₁(P « Q) = (D₁(P) Ç D₁(Q)) È (D₀(P) Ç D₀(Q)).

Доказательство. Все равенства доказываются однообразно, исходя из определения области истинности и логических операций над предикатами. Например,

D₁( ) = {(a₁ ; … ; a_n) Î Aⁿ | (a₁ , … , a_n) = 1} =

= {(a₁ ; … ; a_n) Î Aⁿ | P(a₁ , … , a_n) = 0} = D₀(P) = D(P) \ D₁(P) = Aⁿ \ D₁(P),

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

Аналогично доказываются и остальные равенства множеств (в приводимых ниже вычислениях для краткости полагаем a = (a₁ ; … ; a_n), P(a) = P(a₁ ; … ; a_n)):

D₁(P Ù Q) = {(a₁ ; … ; a_n) Î Aⁿ | (PÙQ)(a₁ , … , a_n) = 1} =

= { aÎ Aⁿ | (P(a) Ù Q(a)) = 1} = { aÎ Aⁿ | (P(a) = 1) Ù (Q(a) = 1)} =

= { a Î Aⁿ | P(a) = 1} Ç { a Î Aⁿ | Q(a) = 1} = D₁(P) Ç D₁(Q),

D₁(P « Q) = { a Î Aⁿ | (P « Q)(a) = 1} = { a Î Aⁿ | (P(a) « Q(a)) = 1} =

= {a Î Aⁿ | ((P(a) Ù Q(a)) Ú ( )) = 1)} =

= {a Î Aⁿ | (P(a) Ù Q(a) = 1) Ú ( = 1)} =

= {a Î Aⁿ | P(a) Ù Q(a) = 1} È {a Î Aⁿ | = 1} =

= ({a Î Aⁿ | P(a) = 1} Ç {a Î Aⁿ | Q(a) = 1}) È

È ({a Î Aⁿ | = 1} Ç {a Î Aⁿ | = 1}) =

= (D₁(P) Ç D₁(Q)) È ({a Î Aⁿ | P(a) = 0} Ç {a Î Aⁿ | Q(a) = 0}

= (D₁(P) Ç D₁(Q)) È (D₀(P) Ç D₀(Q)).

Лемма доказана.

Упражнения: 1.Вычислите области истинности предикатов P, Q , , , P Ù Q , P Ú Q , P ® Q , P « Q , где P(x) = “x² > x ”, Q(x) = “x² – 4×x + 3 < 0”.

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

3.Сформулируйте и докажите лемму об областях ложности.

Рассмотренные логические операции над предикатами позволяют по заданным на множестве А предикатам строить новые предикаты. Другой способ построения новых предикатов дают кванторы. Квантор существования$ и квантор всеобщности" – это специальные математические знаки, служащие для сокращённого обозначения выражений “существует” и “для любого” соответственно.

Примеры: 1. Фразу “квадрат любого действительного числа неотрицателен” математики записывают так: " x Î R x² ³ 0 (читается: для любого действительного числа x выполнено свойство x² ³ 0).

2.Запись " m Î Z ($ n Î Z n < m) (читается: для любого целого числа m существует целое число n со свойством n < m)выражает тот факт, что у любого целого числа есть предшествующие ему целые числа.

В приведённых примерах написанные с помощью кванторов формулы являлись высказываниями. Оба этих высказывания были истинны, но не следует думать, что все высказывания, записанные с помощью кванторов истинны: почувствуйте разницу, прочитав и осмыслив следующие высказывания " x Î Z x ³ 0, " m Î N ($ n Î N n < m), " x Î R ($y Î R |x – y| < x).

Пусть теперь P(x) – предикат от одной переменной на множестве А. Тогда записи " x Î A P(x) (для любого x Î А выполнено свойство P(x))и $ x Î A P(x) (существует x Î А со свойством P(x)) являются высказываниями, не зависящими от переменной x. Говорят, что эти высказывания получены связыванием переменнойx с помощью квантора всеобщности " (и квантора существования $) соответственно. При этом высказывание " x Î A P(x) истинно тогда и только тогда, когда любой объектa из множества А принадлежит области истинности предиката P(x), оно ложно тогда и только тогда, когда хотя бы один объект a из множества А принадлежит области ложности предиката P(x). Высказывание $ x Î A P(x) истинно тогда и только тогда, когда хотя бы один объектa из множества А принадлежит области истинности предиката P(x), оно ложно тогда и только тогда, когда все объекты a из множества А принадлежат области ложности предиката P(x).

Примеры: 1. Если P(x) = “x делится нацело на 15” – предикат на Z, то высказывания " x Î Z P(x) и $ x Î Z P(x) ложно и истинно соответственно.

2. Если P(x) = “x² + 6×x + 100 > 0” – предикат на R, то " x Î R P(x) – истинное высказывание. А каковы высказывания $ x Î R P(x) , " x Î R (x) ?

Аналогично предыдущему случаю предикатов от одной переменной можно связывать кванторами и любую переменную в предикате от n переменных, получая при этом предикат от (n–1)-й переменной: если P(x₁ , … , x_n ) – предикат от n переменных на множестве А, то можно, связывая переменную x_i кванторами, образовать предикаты " x_i Î A P(x₁ , … , x_n ) и $ x_i Î A P(x₁ , … , x_n ) от (n–1)-й переменных x₁ , … x_i–1 , x_i+1 , … , x_n . Их области истинности состоят, по определению, из всех наборов (a₁ ; … ; a_i–1 ; a_i+1 ; … ; a_n) Î A^n–1 значений переменных x₁ , … x_i–1 , x_i+1 , … , x_n , для которых при любом (соответственно хотя бы при одном) x_i = a Î A истинноP(a₁ , … , a_i–1 ; a ; a_i+1 ; … ; a_n ) = 1.

Примеры: 1.Если P(x, y) = “x²+y² = 1” – предикат от двух переменных на множестве R, то предикат S(x) = (" y Î R P(x, y)) от одной переменной x принимает значение 0 (ложь) при любом x Î R(т.к., например, при y = 2 равенство x² + y² = 1 не верно, какой бы x Î R ни взять). Предикат T(x) = ($ y Î R P(x, y)) имеет область истинности D₁(T) = [–1; 1] (при любом x = a Î [–1; 1] можно найти y = со свойством x² + y² = 1).

2. Пусть А – множество всех прямых на плоскости, P(x, y, z) =”прямые x, y, z имеют общую точку” – предикат от трёх переменных x, y, z на А. Тогда предикат S(x, z) = (" yÎ A P(x, y, z)) от двух переменных x, z имеет пустую область истинности (?!), а предикат T(x, z) = ($ yÎ A P(x, y, z)) обладает тем свойством, что (T(x, z) = 1)Û (x Ç z ¹ Æ).

Для удобства дальнейших рассмотрений введём следующие сокращения:

1) вместо выражения " x₁ Î A (" x₂ Î A ( … (" x_n Î A P(x₁ , … , x_n))…)) будем писать " x₁ , … , x_n Î A P(x₁ , … , x_n), а $ x₁ , … , x_n Î A P(x₁ , … , x_n) – вместо $ x₁ Î A ($ x₂ Î A ( … ($ x_n Î A P(x₁ , … , x_n))…)). Здесь важно, что кванторы при всех элементах x₁ , … , x_n однотипны, т.е. либо все являются кванторами существования, либо же все – кванторами всеобщности, а также то, что все элементы x₁ , … , x_n выбираются из одного и того же множества А.

2) обозначение $ ! x_i Î A P(x₁ , … , x_i , … , x_n) будет использоваться для сокращения выражения “существует единственный элемент x_i во множестве А со свойством P(x₁ , … , x_i , … , x_n)”. Формально это высказывание записывается так: ($ x_i Î A P(x₁ , … , x_i , … , x_n)) Ù (" y_i Î A (P(x₁ , … , y_i , … , x_n) ® (y_i = x_i ))).