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

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

Установим правила, которые позволяют найти множество истинности составного предиката, если известны множества истинности составляющих его элементарных предикатов.

Пусть на множестве Х задан предикат А (х). Его отрицанием называют предикат , определённый на том же множестве Х, причём предикат – «И» при тех значениях х из Х, при которых А (х) – «Л», и наоборот.

П р и м е р. На множестве Х = {10, 15, 20, 21, 19, 17} рассмотрим предикат А (х): «х кратно 3». Тогда : «х не кратно 3». Легко видеть, что множеством истинности предиката А (х) является Т = {15, 21}, а для множеством истинности является = {10, 20, 19, 17}, т.е. дополнение к множеству Т.

Вообще, если Т – множество истинности предиката А (х), х Î Х, то множеством истинности предиката , х Î Х является (дополнение к Т в множестве Х). Запишем эти множества символически:

Т = { х Î Х | А (х)} .

Изобразим множество истинности предиката на диаграмме Эйлера-Венна заштрихованной областью (рис. 2).

Пусть теперь на множестве Х заданы два предиката А (х) и В (х). Образуем их конъюнкцию, т.е. А (х) Ù В (х). Полученный предикат истинный при тех значениях х Î Х, при которых «И» оба предиката А (х) и В (х).

П р и м е р. На множестве Х = {10, 15, 16, 20, 35} заданы предикаты А (х): «число х – чётное» и В (х): «х кратно 5». А (х) Ù В (х) обращается в истинное высказывание, если х Î {10, 20}. Обозначим Т ₁ = {10, 16, 20} – множество истинности предиката А (х), Т ₂ = {10, 15, 20, 35} – множество истинности предиката В (х), тогда ={10, 20}.

Вообще, если Т₁ – множество истинности предиката А (х), х Î Х, а Т ₂ –множество истинности предиката В (х), х Î Х, то множество истинности Т предиката А (х) Ù В (х), х Î Х есть пересечение множеств Т ₁ и Т ₂. Запишем это множество символически:

}.

Изобразим множество истинности предиката на диаграмме Эйлера-Венна заштрихованной областью (рис. 3).

Рис. 3

Предикат А (х) Ú В (х), называют дизъюнкцией предикатов А (х),
х Î Х и В (х), х Î Х. Он истинный при тех значениях х из Х, при которых истинный хотя бы один из предикатов А (х) и В (х).

П р и м е р. Пусть предикат А (х): «х – студент I курса»; а предикат В (х): «х – спортсмен», заданные на X – множестве студентов некоторого института. Тогда A (x) Ú B (x) предикат: «студент х спортсмен или первокурсник".

Вообще, если Т ₁ – множество истинности предиката А (х), а Т ₂ – множество истинности предиката В (х), то множеством истинности предиката A (x) Ú B (x), х Î Х является множество . Запишем это множество символически:

Х

Изобразим множество истинности предиката на диаграмме Эйлера-Венна заштрихованной областью (рис. 4).

Составим теперь импликацию двух предикатов А (х) Þ В (х), где предикаты А (х) и В (х) заданы на некотором множестве X.

Предикат А (х) Þ В (х) превращается в ложное высказывание при подстановке вместо х таких значений а, при которых А (а) – «И», В (а) – «Л». Если T ₁ – множество истинности предиката А (х), T ₂ – множество истинности предиката В (х), то импликация А (х) Þ В (х) ложна на множестве , а на дополнении к этому множеству предикат
А (х) Þ В (х) истинный. Найдем это дополнение. По закону де Моргана: .

Значит, множеством истинности предиката А (х) Þ В (х) является объединение множества T ₂ (истинности предиката В (х)) и дополнения к множеству T ₁ (истинности предиката А (х)). Запишем это множество символически

Изобразим множество истинности предиката А (х) Þ В (х) на диаграмме Эйлера-Венна заштрихованной областью (рис. 5)

Рис. 5

Часто встречаются такие предикаты, что для всех значений х Î Х из истинности одного следует истинность другого. Например, из предиката А (х): «х делится на 4», следует В (х): «х делится на 2». Оба предиката определены на множестве натуральных чисел.

Рис. 6

Из истинности некоторого предиката А (х) следует истинность предиката В (х) в том и только в том случае, когда пусто (на котором предикат А (х) Þ В (х) ложен). Множества T ₁ и имеют пустое пересечение, если T ₁ Ì T ₂ (как изображено на рис. 6). В том случае, когда импликация А (х) Þ
Þ В (х), х Î Х истинна при всех значениях x, говорят, что В (х) логически следует из А (х) и для их множеств истинности выполняется , где Т₁ – множество истинности А (х),
Т ₂ – множество истинности В (х). Тогда предикат В (х) называют необходимым условием для А (х), предикат А (х) достаточным условием для В (х).

Если предикат А (х) Û В (х) задан на множестве X, то каждый из предикатов А (х) и В (х) называют необходимым и достаточным условием для другого. Например, для того, чтобы натуральное число х делилось на 10, необходимо и достаточно, чтобы последняя цифра в десятичной записи этого числа была равна 0. Запишем множество истинности Т предиката

А (х) Û В (х) символически:

.

Изобразим множество истинности предиката А (х) Û В (х) на диаграмме Эйлера-Венна заштрихованной областью (рис. 7).

Дата добавления: 2015-07-18