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

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


Отрицанием предиката Р(х), заданного на множестве Х, называется предикат Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage590.gif, заданный на том же множестве  и истинный при тех и только тех значениях хОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage002.gifХ, при которых предикат Р(х) принимает значение лжи. 


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


Конъюнкцией предикатов Р(х) и Q(x), заданных на множестве Х, называется предикат  Р(х)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage553.gifQ(x), заданный на том же множестве и обращающийся в истинное высказывание при тех и только тех значениях хОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage002.gifХ, при которых оба предиката принимают значения истины.


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


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


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


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


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


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


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


Дизъюнкцией предикатов Р(х) и Q(x) называется предикат Р(х)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage556.gifQ(x), определенный на том же множестве Х и обращающийся в истинное высказывание при тех и только тех значениях хОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage002.gifХ, при которых принимает значение истины  хотя бы один из предикатов Р(х) или Q(x).

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

 


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


Импликацией предикатов Р(х) и Q(x), заданных на множестве Х, называется предикат Р(х)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage268.gif Q(x), определенный на том же множестве Х и обращающийся в ложное высказывание при тех и только тех значениях хОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage002.gifХ, при которых Р(х) принимает значение истины, а Q(x) – значение лжи.


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


Эквиваленцией предикатов Р(х) и Q(x), заданных  на множестве Х, называется предикат Р(х)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage544.gif Q(x), определенный на том же множестве Х и принимающий значение истины при тех и только тех значениях хОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage002.gifХ, при которых значения каждого из предикатов либо истинны либо ложны. Множество истинности в таком случае выглядит так:












 
 

 



          TPÛQ = Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage609.gif.


Пример.  На множестве М={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) А(х)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage553.gifВ(х);   b)  A(x)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage553.gifОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage610.gifc)  C(x)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage268.gifA(x);  d)  B(x)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage556.gifD(x) и изобразить их при помощи диаграмм Эйлера-Венна.


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


А(х):  T Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gif= {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19};


В(х):  Т Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif= {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}.


Множество истинности конъюнкции  А(х)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage553.gifВ(х) есть пересечение множеств истинности TОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gif и ТОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif.


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


b)  Множествa истинности   А(х):  T Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gif= {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19};    Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage610.gif:  T Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif={1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20}.


Тогда множество истинности  A(x)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage553.gifОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage610.gif  будет следующим:


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


с)  Множествa истинности  С(х): Т Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gif={1, 2, 3, 5, 7, 11, 13, 17, 19};    А(х):  T Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif= {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19}.


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


Значит множество истинности импликации  C(x)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage268.gifA(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 Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif= {3, 6, 9, 12, 15, 18}. Тогда множество истинности дизъюнкции B(x)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage556.gifD(x) есть объединение множеств истинности Т1 и T2 и будет следующим:  Т = {2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}.


Просмотров 40 526 Комментариев 0
Познавательно:
Скажи свое мнение:
Добавить комментарий
Имя:* E-Mail:*

Вопрос:
1+1=
Ответ:*