Лабораторный Практикум по Дискрмат2

Рис.1. Зависимость функции риска f 4 от x и y для гипотез F1, F2, F3

>plot3d (x + y – x*y, x = 0..1, y = 0..1);

Рис.2. Зависимость вероятности события H от x и y

> x =0.3; y =0.7; f 4; H; f 4*H;

f 4 =0.250096; H =0,79; f 4*H =0.19757584.

Согласно результатам вычислений, при риске ( или условие) равном 0,250096 вероятность события H равна 0,19757584 (рис.2).

При помощи функции риска для гипотез F1 , F2 задания (б) определим графически условие наибольшего риска для данных а = 0.5 и b = 0.8

(рис.3):

> f 1:= x + y – x*y; f 2:= 1 - f 1 – z + 2*f 1*z; > f 3:=x* (1 - y); f 4:=1 – f 3 + f 3*z; f :=f 2* f 4;

41

> x:=0.5; y:=0.8; f ;

f = (0.1 + 0.8z)(0.9 + 0.1z ) >plot3d ((0.1 + 0.8*z)(0.9 + 0.1*z ), z = 0..1);

Рис.3. Зависимость функции f риска от z

Согласно графику функции f , наибольший риск будет при условии z

= 1.

Вычислим логическую вероятность каждого из логических следствий из полного списка для заданных значений а = 0,45, b = 0,88 и c = 0,89:

> f 1:= x + y – x*y; f 2:= 1– f 1 – z + 2*f 1*z; >f 3:= x*(1–y); f 4:= 1 – f 3 + f 3* z; f := f 2 * f 4;

f = (1– x – y + xy – z + 2(x + y – xy)z)(1– x(1 – y) + x(1– y)z)

>DA:= x + y – x*y; D1:= DA + 1 – z – DA*(1 – z );

>DB:= x + 1– y – x*(1 – y); D2:= DB + z – DB*z ;

>DC:= 1– x + y –(1– x)*y; D3:= DC + z – DC*z ;

>DD:=1– x +1– y –(1 – x)*(1 – y); D1:= DD + z – DD* z;

>x := 0.45; y:= 0.88;	z:= 0.89; f*D1; f*D2; f*D3; f*D4;
f*D1 = 0.7846; f*D2 = 0.7892 ; f*D3 = 0.8286; f*D4 = 0.7972;
> f*D1*D2; f*D1*D3; f*D1*D4; f*D2*D3; f*D2*D4; f *D3*D4;
f*D1*D2	= 0.7428;	f*D1*D3 = 0.7799;	f*D1*D4 = 0.7504;
f*D2*D3	= 0.7845;	f*D2*D4 = 0.7548;	f *D3*D4 = 0.7925;

42

>f*D1*D2*D3; f*D1*D2*D4; f*D1*D3*D4; f*D2*D3*D4; f*D1*D2*D3 = 0.7384; *D1*D2*D4 = 0.7104; f*D1*D3*D4= 0.7459; f*D2*D3*D4 = 0.7503;

>f*D1*D2*D3*D4;

f*D1*D2*D3*D4 = 0.7062.

Согласно вычислениям, логические вероятности следствий будут равны соответственно: 0,7846; 0,7892; 0,8286; 0,7972; 0,7428; 0,7799; 0,7504; 0,7845; 0,7548; 0,7925; 0,7384; 0,7104; 0,7459; 0,7503; 0,7062.

Вопросы для самопроверки

1.Что называется логическим следствием?

2.Что называется гипотезой или посылкой?

3.На основе теоремы сформулируйте правило нахождения всех следствий из данных гипотез.

4.В каком случае логическое следствие становится только вероятным?

5.Как определяется функция риска и вычисляется вероятность логического следствия?

Литература: [3], гл.1, с. 13–14; [2], Часть 1, с. 7–38; [7], гл. 3, стр. 50–56; [12], гл. 1, стр. 4–34.

Задания для самостоятельной работы

Вариант 1.

а) F1

(a b a), F2

(a b), F3

a, H a b;

б) F1

(a b c), F2

(a b c) .

Вариант 2.

а) F1

(a b a), F2

(a b), F3

b, H a b ;

б) F1

(a b c), F2

(c b a) .

Вариант 3.

а) F1

(a b a), F2

(a b), F3

a b, H a b ;

б) F1

(a b c), F2

(a b c) .

43

Вариант 4.

а) F1

(a b a), F2

(a b ), F3

a b, H a b ;

б) F1

(a b c), F2

(a b c) .

Вариант 5.

а) F1

(b b a), F2

(a b ), F3

b, H a b;

б) F1

(a b c), F2

(a b c) .

Вариант 6.

а) F1

(b b a), F2

(a b ), F3

b a, H a b ;

б) F1

(a b c), F2

(a b c) .

Вариант 7.

а) F1

(b b a), F2

(a b ), F3

b a, H a b ;

б) F1

(b a c), F2

(a b c) .

Вариант 8.

а) F1

(b b a), F2

(a b ), F3

b, H a b ;

б) F1

(b a c), F2

(a b c) .

Вариант 9.

а) F1

(b a), F2 (a b ), F3 b a, H a ;

б) F1

(b a c), F2

(a b c) .

Вариант 10.

а) F1

(b a)

a, F2

(a b ), F3

b , H a b ;

б) F1

(b a c), F2

(a b c)

c .

Вариант 11.

а) F1

(b a)

a, F2

(a b ), F3

b a, H a b ;

б) F1

(b a c), F2

(a b c)

c .

Вариант 12.

а) F1

(b a)

a, F2

(a b ), F3

b a, H a b;

б) F1

(b a c), F2

(a b c) a .

Вариант 13.

а) F1

(b a)

a, F2

(a b), F3 b , H a b;

б) F1

(b a c), F2

(a b c)

a .

Вариант 14.

а) F1

(b a)

a, F2

(a b), F3

a, H a b ;

б) F1

(b a c), F2

(a b c)

b .

44

Вариант 15.

а) F1	(b a) a, F2					(a b), F3 a, H a b ;
б) F1	(b a c), F2					(a b c) b .
Вариант 16.

а) F1	(b a)								a, F2
б) F1	(b a)								c, F2
Вариант 17.
а) F1	(b a)								a, F2
б) F1	(b a)									c, F2
Вариант 18.
а) F1	(b a)									a, F2
б) F1	(b a)									c, F2
Вариант 19.
а) F1	(b a)								a, F2
б) F1	(b a)								c, F2
Вариант 20.
а) F1	(b a)									a, F2
б) F1	(c a)								b , F2
Вариант 21.
а) F1	(b a)								a, F2
б) F1	(c b )									a, F2
Вариант 22.

(a b), F3

a, H b ;

(a

b )

(c

b).

(a b), F3

a b, H b ;

(a

b)

(c

b) .

(a b ), F3

a b, H b a ;

(a

b)

(c

b) .

(a b ), F3

a b, H b a ;

(a

b)

(c

b) .

(a b ), F3

a b, H b a ;

(a

c)

(c

b ) .

(a b ), F3

a b, H b a ;

(a

c)

(a

b ) .

а) F1

(b a)

a, F2

(a b), F3

a b, H b a ;

б) F1

(c b)

a, F2

(a c)

(a b) .

Вариант 23.

а) F1

(b a)

a, F2

(a b), F3

a b , H b a ;

б) F1

(c b)

a, F2

(a c)

(a b) .

Вариант 24.

а) F1

(b a)

b, F2

(a b ), F3

a b , H b a ;

б) F1

(c b)

c a, F2 (b c)

(a c) .

Вариант 25.

а) F1

(b a)

b , F2

b , F3

a b , H b a ;

б) F1

(c b)

c a, F2

(a b)

(a c) .

45

Лабораторная работа № 6

ОПЕРАЦИИ НАД ПРЕДИКАТАМИ. КВАНТОРНЫЕ ОПЕРАЦИИ

Цель работы

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

Краткая теория

В математической практике наиболее часто используются предложения общего вида. Например, предложения «x < y» и «х делится на у», не являются ни истинными, ни ложными. То есть, не являются высказываниями. Однако эти предложения становятся высказываниями при конкретных значениях переменных х и у. Такие предложения рассматриваются в математической логике наряду с высказываниями и называются предикатами. Дадим точное определение предиката.

Предикатом, заданным на множествах М1, М2,…, Мn, называется предложение содержащее n переменных х1, х2, … , хn, которое становится высказыванием при подстановке вместо этих переменных – элементов а1, а2, … , аn из множеств М1, М2, … , Мn – соответственно. Предикаты обозначаются как Р(х1, х2, … , хn) и представляют собой отображения множества М1×М2×…×Мn на множество {0,1}. То есть, упорядоченному набору элементов (а1, а2, … , аn) из множества М1×М2×…×Мn ставится в соответствие один из элементов множества {0,1}, причем 0, если Р(а1, а2,

… , аn) – ложное высказывание, и 1 – если истинное высказывание. Местностью предиката называется число различных аргументов, от которых зависит предикат.

Примеры: 1) Предложение «х – четное число» представляет собой одноместный предикат, заданный на множестве целых чисел. Областью определения этого предиката является множество целых чисел, а областью значений – множество {0,1}.

2) Отношения «x < y» и «x делится на y» представляют собой двухместные предикаты, заданные на декартовом произведении множества действительных чисел и на декартовом произведении множества целых чисел соответственно.

46

Множеством истинности предиката Р(а1, а2, … , аn), заданного на множестве М1×М2×…×Мn, называется совокупность таких упорядоченных наборов элементов (а1, а2, … , аn) из М1×М2×…×Мn, для которых высказывания Р(а1, а2, … , аn) являются истинными. Обозначение Р+ =

{(а1, а2, …, аn) | Р(а1, а2, … , аn) – истинное высказывание}.

Примеры: 1) Множеством истинности двухместного предиката Р(х, у): «х делится на у», заданного на множестве M M где М = {1, 2, 3, 4, 5, 6}

является следующее множество Р+ = {(1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1), (4, 2), (6, 2), (6, 3)}.

2) Множество истинности двухместного предиката Р(х, у): «х < у», заданного на множестве М1×М2, где М1 = {1, 2, 3}, М2 = {2, 4, 6} равно P+

= {(1, 2), (1, 4), (1, 6), (2, 4), (2, 6), (3, 4), (3, 6)}.

Два предиката Р(х1, х2, … , хn) и Q(х1, х2, … , хn), заданные на одном и том же множестве М1×М2×…×Мn, называются равносильными, если оба

предиката принимают истинные значения на одних и тех же наборах (а1, а2, … , аn) из множества М1×М2×…×Мn, то есть, если Р+ = Q+.

Предикат Q(х1, х2, … , хn), заданный на множестве М1×М2×…×Мn,

называется следствием предиката Р(х1, х2, … , хn), заданного на том же множестве, если он становится истинным высказыванием при всех значениях переменных х1, х2, … , хn из соответствующих множеств М1, М2, … , Мn, при которых истинным высказыванием становится предикат Р(х1, х2, … , хn), то есть, если P Q.

Основные операции над предикатами

Отрицанием предиката Р(х1, х2, … , хn), заданного на множестве

М1×М2×…×Мn, называется новый предикат P (х1, х2, … , хn), заданный на том же множестве, который становится истинным высказыванием при

таких значениях (a1, a2, … , an) из множества М1×М2×…×Мn, при которых Р(a1, a2, … , an) является ложным высказыванием, и становится ложным

высказыванием, если Р(a1, a2, … , an) является истинным высказыванием. Например, отрицанием одноместного предиката Р(х): «х делится на 3», заданного на множестве М = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, будет предикат P : «х не делится на 3». Множествами истинности предикатов Р и P являются следующие множества Р+ = {0, 3, 6, 9}, ( P )+ = {1, 2, 4, 5, 7, 8}. Множество

			дополнением множества Р+. Тогда
истинности предиката P является
справедливо следующее равенство: Р+			(		)+ = M.
				P

47

Конъюнкцией двух n-местных предикатов Р(х1, х2, … , хn) и Q(х1, х2, … , хn), заданных на множестве М1×М2×…×Мn, называется новый n- местный предикат (Р Q)(х1, х2, … , хn), который становится истинным высказыванием только для таких элементов (а1, а2, … , аn) из множества

М1×М2×…×Мn, для которых Р(а1, а2, … , аn) и Q(а1, а2, … , аn) являются истинными высказываниями.

Дизъюнкцией двух n-местных предикатов Р(х1, х2, … , хn) и Q(х1, х2, … , хn), заданных на множестве М1×М2×…×Мn, называется новый n- местный предикат (Р Q)(х1, х2, … , хn), который становится ложным высказыванием только для таких элементов (а1, а2, … , аn) из множества

М1×М2×…×Мn, для которых Р(а1, а2, … , аn) и Q(а1, а2, … , аn) являются ложными высказываниями, а для остальных элементов – истинным

высказыванием.

Импликацией двух n-местных предикатов Р(х1, х2, … , хn) и Q(х1, х2, … , хn), заданных на множестве М1×М2×…×Мn, называется новый n- местный предикат (Р Q)(х1, х2, … , хn), который становится ложным высказыванием только для таких элементов (а1, а2, … , аn) из множества М1×М2×…×Мn, для которых Р(а1, а2, … , аn) является истинным

высказыванием, а Q(а1, а2, … , аn) является ложным. В остальных случаях

– истинным.

Эквивалентностью двух n-местных предикатов Р(х1, х2, … , хn) и Q(х1, х2, … , хn), заданных на множестве М1×М2×…×Мn, называется новый n-местный предикат (Р Q)(х1, х2, … , хn), который становится истинным высказыванием только для таких элементов (а1, а2, … , аn) из множества

М1×М2×…×Мn, для которых Р(а1, а2, … , аn) и Q(а1, а2, … , аn) либо одновременно являются истинными, либо одновременно ложными

высказываниями. В остальных случаях – является ложным.

Теоретико-множественный смысл предикатов

При определении множества истинности предиката, составленного из нескольких предикатов при помощи логических связок, можно воспользоваться соотношениями для их множеств истинности. Для двух n-

местных предикатов Р(х1, х2, … , хn) и Q(х1, х2, … , хn), заданных на множестве М1×М2×…×Мn, верны следующие соотношения для их множеств истинности:

48

1)

множество истинности отрицания предиката Р равно дополнению

)+=

множества истинности этого предиката, то есть (

P ;

P

2)

множество истинности конъюнкции двух предикатов Р и Q равно

пересечению множеств истинности Р+ и Q+, то есть (Р

Q)+ = Р+

Q+;

3)

множество истинности дизъюнкции двух предикатов Р и Q равно

объединению множеств истинности Р+ и Q+, то есть (Р

Q)+ = Р+

Q+;

4)

множество истинности импликации двух предикатов Р и Q равно

(Р Q)+ = (

)+

Q+;

P

5)

множество истинности эквивалентности двух предикатов Р и Q

равно: (Р Q)+ = [(

)+

Q+] [(

)+

P+].

P

Q

Примеры: 1) Пусть предикаты Р(х): « х кратно двум» и Q(х): « х кратно трем», заданы на множестве М = {1, 2, 3, 4, 5, 6, 7, 8}. Их

множествами истинности являются множества Р+ = {2, 4, 6, 8}, Q+= {3, 6}. Тогда по соотношениям 1) – 5) получим:

а)	P		1,3,5,7 , Q			1,2, 4,5,7,8 ;
б)	P Q		2, 4, 6,8			3, 6 6 ;

в)	P	Q	2,4,6,8	3,6	2,3,4,6,8 ;
г)	P	Q	1,3,5,7	3,6 1,3,5,6,7 ;
д)	P	Q	1,3,5, 6, 7	1,2, 4,5, 7,8 1, 5, 6, 7 .

2) Пусть предикаты P(x,y): «x > 0» и Q(x,y): «y < 0» заданы на декартовом произведение множества действительных чисел. Их множествами истинности являются: Р+ – множество точек первой и четвертой четвертей в координатной плоскости за исключением точек оси ординат и отрицательной части оси абсцисс; Q+ – множество точек второй и четвертой четвертей, за исключением оси абсцисс и положительной части оси ординат. По соотношениям 1) – 5) получим:

а)	P		– множество точек второй и третьей четвертей;
б)	P		Q	– множество точек четвертой четверти за исключением
точек осей координат;
в)	P		Q	– множество всех точек координатной плоскости, за

исключением положительной части оси Оу и отрицательной части оси Ох; г) P Q – множество всех точек плоскости, за исключением точек

первой четверти и положительной части оси Ох;

49

д) P Q – множество точек второй и четвертой четвертей, за исключением точек осей координат.

Предикат Р(х1, х2, … , хn), заданный на множестве М1×М2×…×Мn, называется тождественно истинным, если для всех элементов (а1, а2, … ,

аn) из множества М1×М2×…×Мn, высказывания Р(а1, а2, … , аn) будут истинными; и тождественно ложным, если для всех элементов (а1, а2, … ,

аn) из множества М1×М2×…×Мn, высказывания Р(а1, а2, … , аn) будут ложными. Предикат Р(х1, х2, … , хn), заданный на множестве М1×М2×…×Мn, называется выполнимым, если существует хотя бы один элемент (а1, а2, …, аn) из множества М1×М2×…×Мn, для которого высказывание Р(а1, а2, … , аn) будет истинным, и опровержимым, если хотя бы для одного элемента Р(а1, а2, … , аn) из множества М1×М2×…×Мn, высказывание Р(а1, а2, … , аn) будет ложным.

Кванторные операции над предикатами

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

Операцией действия квантора общности на одноместный предикат Р(х), заданный на множестве М, называется правило, согласно которому предикату Р(х) ставится в соответствие высказывание xP x , которое будет истинным, если предикат Р(х) является тождественно истинным и будет ложным, если Р(х) – опровержимый предикат.

Операцией действия квантора существования на одноместный предикат Р(х), заданный на множестве М, называется правило, согласно которому предикату Р(х) ставится в соответствие высказывание xP x , которое будет истинным, если Р(х) – выполнимый предикат, и ложным, если Р(х) – тождественно ложный предикат.

Если Р(х) – одноместный предикат, заданный на некотором множестве М, то в результате применения кванторов к предикату Р(х) получим новые предикаты xP x , xP x , означающие, соответственно:

«все х из М обладают свойством Р» и «некоторые х из М обладают свойством Р».

Пример. Пусть Р(х) – одноместный предикат «х делится на семь», заданный на множестве целых чисел. Применяя к этому предикату кванторы, получим следующие предикаты: «все х из множества целых чисел делятся на число семь» и « существуют х из множества целых чисел,

50