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

       1. Операция отрицания.

Отрицанием предиката Р(х), заданного на множестве Х, называется предикат , заданный на том же множестве  и истинный при тех и только тех значениях хХ, при которых предикат Р(х) принимает значение лжи. 

       2. Операция конъюнкции.

Конъюнкцией предикатов Р(х) и Q(x), заданных на множестве Х, называется предикат  Р(х)Q(x), заданный на том же множестве и обращающийся в истинное высказывание при тех и только тех значениях хХ, при которых оба предиката принимают значения истины.

Если обозначить ТР – множество истинности предиката Р(х), ТQ – множество истинности предиката Q(х), а множество истинности их конъюнкции TPÙQ, то, по всей видимости, TPÙQ = TP Ç TQ.

Докажем это равенство.

1. Пусть а – произвольный элемент множества Х и известно, что а Î TPÙQ . По определению множества истинности это означает, что предикат  Р(х)Q(x) обращается в истинное высказывание при х = а, т.е. высказывание Р(а)Q(а) истинно. Так как данное высказывание конъюнкция, то по определению конъюнкции получаем, что каждое из высказываний Р(а) и Q(а) также истинно. Это означает, что а  ТР и а  ТQ . Таким образом, мы показали, что TPÙQ  Ì ТР Ç ТQ .

2. Докажем обратное утверждение. Пусть а – произвольный элемент множества Х и известно, что а Î TP Ç TQ . По определению пересечения множеств это означает, что а  ТР и а  ТQ , откуда получаем, что Р(а) и Q(а) – истинные высказывания, поэтому конъюнкция высказываний Р(а)Q(а) также будет истинна. А это означает, что элемент а принадлежит множеству истинности предиката Р(х)Q(x), т.е. а Î TPÙQ .

Из 1 и 2 в силу определения равных множеств вытекает справедливость равенства TPÙQ  = ТР Ç ТQ , что и требовалось доказать.

Наглядно это можно изобразить следующим образом.                                                       

       3.  Операция дизъюнкции.

Дизъюнкцией предикатов Р(х) и Q(x) называется предикат Р(х)Q(x), определенный на том же множестве Х и обращающийся в истинное высказывание при тех и только тех значениях хХ, при которых принимает значение истины  хотя бы один из предикатов Р(х) или Q(x).

Аналогично доказывается, что TPÚQ = TP È TQ.

 

      4. Операция импликации.

Импликацией предикатов Р(х) и Q(x), заданных на множестве Х, называется предикат Р(х) Q(x), определенный на том же множестве Х и обращающийся в ложное высказывание при тех и только тех значениях хХ, при которых Р(х) принимает значение истины, а Q(x) – значение лжи.

5 .Операция эквиваленции.

Эквиваленцией предикатов Р(х) и Q(x), заданных  на множестве Х, называется предикат Р(х) Q(x), определенный на том же множестве Х и принимающий значение истины при тех и только тех значениях хХ, при которых значения каждого из предикатов либо истинны либо ложны. Множество истинности в таком случае выглядит так:

          TPÛQ = .

Пример.  На множестве М={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} заданы предикаты: А(х) – «число х не делится на 5», В(х) – «х – число четное», С(х) – «х – число простое», D(x) – «число х кратно 3». Найти множество истинности следующих предикатов:                

a) А(х)В(х);   b)  A(x);  c)  C(x)A(x);  d)  B(x)D(x) и изобразить их при помощи диаграмм Эйлера-Венна.

Решение: a) Найдем множество истинности предикатов.

А(х):  T = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19};

В(х):  Т = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}.

Множество истинности конъюнкции  А(х)В(х) есть пересечение множеств истинности T и Т.

 Т = {2, 4, 6, 8, 12, 14, 16, 18}                                                     

b)  Множествa истинности   А(х):  T = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19};    :  T ={1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20}.

Тогда множество истинности  A(x)  будет следующим:

Т={1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19}.

с)  Множествa истинности  С(х): Т ={1, 2, 3, 5, 7, 11, 13, 17, 19};    А(х):  T = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19}.

Множество истинности импликации есть объединение множества истинности второго предиката с множеством истинности отрицания первого.

Значит множество истинности импликации  C(x)A(x)  будет следующим: Т = {1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,

d) Множества истинности В(х):  Т1= {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}  и  D(x):   T = {3, 6, 9, 12, 15, 18}. Тогда множество истинности дизъюнкции B(x)D(x) есть объединение множеств истинности Т1 и T2 и будет следующим:  Т = {2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}.