Дата: 15.04.2020г.

Предмет: Элементы математической логики.

Группа: 29, 291

Тема 55-56. Предикаты и высказывательные формы. Логические операции над предикатами

Теоретические сведения

Предложение А(х) с переменной х, где хХ, которое в результате замены переменной допустимыми значениями обращается в высказывание, называется предикатом или высказывательной формой.

В зависимости  от числа переменных различают одноместные, двухместные, трехместные и т.д. предикаты:  А(х);  В(х, у);  С(х, у, z) и т.д.

Например: х >5 – одноместный предикат;  х делится на у – двухместный;  х + 2у = z – трехместный предикат.

Множество всех допустимых значений переменной, при подстановке которых в предикат Р(х) получается истинное или ложное высказывание, называют областью определения предиката.

Предикат считается заданным, если указать множество всех допустимых значений переменной. Например: предикат 3х + 7 = 15 может быть задан на множестве натуральных чисел N, или на множестве действительных чисел R.

Если множество истинности Тp предиката Р(х) совпадает с множеством Х, на котором он задан (Тp= Х), то такой предикат называют тождественно истинным.

Если множество истинности предиката Р(х) пусто (Тp = ), то   предикат называют тождественно ложным. Два предиката  Р(х) и  Q(x)  называют равносильными, если они заданы на одном и том же множестве Х и их множества истинности совпадают.

Пример.   Даны предикаты   Р(х) : х= 9   и   Q(x): (х – 3)(х + 3) = 0 на множестве Z. Так как   =    ={–3; 3}, значит, данные предикаты равносильны.

Множество истинности двухместного предиката Р(х,у) состоит из всех пар (a; b), при подстановке которых в этот предикат получается истинное высказывание. Например,  если Р(х;у) предикат «х делится на у» на множестве Z,  то, так как «6 делится на 3» – истинное высказывание, значит  (6; 3) .

Соответственно определяется множество истинности и для любого многоместного предиката.

Над предикатами, как и над высказываниями можно выполнять логические операции.

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

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 = .