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

которые делятся на число семь». То есть, в результате применения кванторов x, x к одноместному предикату Р(х), получили высказывания

xP x , xP x , причем первое из них ложное, а второе – истинное. Высказывания являются нульместными предикатами.

Следовательно, применение кванторов к предикатам понижает местность

исходного предиката на единицу. Если Р(х1, х2, … , хn) – n-местный предикат, то в результате применения квантора общности получим

новый предикат Q(х1, х2, … , хn) = x1Р(х1, х2, … , хn), а применяя квантор существования x получим предикат R(х1, х2, … , хn) = x1Р(х1, х2, … , хn) который зависит только от переменных х1, х2, … , хn, то есть, является (n – 1)-местным предикатом.

Пример. Пусть Р(х, у) – двухместный предикат, заданный неравенством " x2 y 2 1" на декартовом произведении множества действительных чисел. Множеством истинности предиката Р(х, у) является множество всех точек координатной плоскости, расположенных внутри окружности радиуса 1, включая точки окружности. Найдем множества

истинности следующих предикатов: Q y		xP x, y ,	R x	yP x, y ,
S	x yP x, y . Множеством истинности	предиката	Q(y)	является

множество таких у, для которых данное неравенство выполняется при любых х. Однако таких у не существует. Следовательно, множество истинности предиката Q(у) не содержит ни одного элемента, то есть

Q . Множеству истинности предиката R(x) принадлежат все такие

х, для которых можно найти число у, удовлетворяющее данному неравенству. Такие значения лежат в интервале [–1; 1]. Следовательно, этот интервал и будет множеством истинности предиката R. Предикат S – нульместный предикат, то есть является высказыванием. В высказывании S говорится, что для любых х можно найти такое у, для которых выполняется данное неравенство. Однако это неверно. Например, для х, лежащих вне интервала [–1; 1], такое у не существует. Тогда S – ложное высказывание.

Порядок выполнения работы

1.Определить множества истинности для данных предикатов.

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

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

4.Изобразить множества истинности на декартовой плоскости.

51

Образец выполнения заданий

На множестве действительных чисел (a) и на его декартовой степени (б), (в) заданы предикаты P и Q. Найти область истинности предикатов

P Q ,	P Q, P Q ; найти область истинности предикатов
xP x, y .	xQ x, y .

а) P x : "	x 2	3", Q x : "x2		4 12";
б) P x, y : " x2		y2	4"; Q x, y : " xy		0";
в) P x, y : " x2		y2	9" ; Q x, y : " x2		y2	16".

Решение. а) Найдем сначала множества истинности предикатов Р и Q. По определению, множества истинности Р+ и Q+ соответственно равны множествам всех решений неравенств x 2 3, x2 4 12 . Следовательно,

Р+ = ; 5 1; , Q+ = [-4; 4]. По свойствам множеств истинности:

P(x)

Q x

P

Q

; 5

4;1

1;

P(x)

Q x

P

Q

1;4

P x Q x

P Q Q P

P Q

Q P

P

5;1 , Q

; 4

4;

Таким образом,

P x

Q x

5;

4

1;4 .

б) Найдем для начала множества истинности предикатов Р и Q. По определению, множества истинности Р+ и Q+ равны множествам решений

неравенств x2

y 2

4, xy 0 . Значит, Р+ – это множество всех точек

плоскости, которые лежат вне окружности радиуса 2 с центром в начале координат, а Q+ – это множество всех точек плоскости, принадлежащих первой и третьей координатной четверти. По свойствам множеств

истинности получим: P Q	P Q , P		Q	P	Q (рис.1а).
Тогда множество истинности предиката		P – это все точки внутри

окружности, включая точки окружности, а множество истинности предиката Q – это вторая и четвертая четверти, исключая точки координатных осей. Выполняя операции над полученными множествами,

52

а)

б)

Рис. 1. Множества истинности предикатов P Q и Р Q

получим искомое множество истинности (рис. 1б):

P Q		P Q		Q P .
в) Предикат xP x, y	– одноместный, зависит от переменной у.

Множеством его истинности будет множество таких b R , что

неравенство x2 + b2 < 9 выполняется для		всех x R .	Но	таких b	не
существует. Следовательно,	xP x, y	.
Предикат xQ x, y	– одноместный	относительно	переменной		у.
Множеством истинности данного предиката будут все a			R ,	для которых
найдется x R такое, что выполняется неравенство x2 + a2				16. Такие

x R найдутся для a [–4; 4]. Следовательно, ( xQ x, y )+ = [–4; 4].

53

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

1.Что называется предикатом?

2.В чем сходство и отличие предикатов и высказываний?

3.Что такое множество истинности предиката?

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

5.Определите кванторные операции над предикатами.

6.Перечислите основные свойства множеств истинности предикатов.

Литература: [3], гл. 3, с. 56–74; [2], Часть 4, с. 68–80; [7], гл. 3, стр. 80–88. [12], § 7, стр. 96–117.

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

Вариант 1.

а)

P x : " x2

x

0" ;

Q x : " x2

x

0";

б) P x, y :" x2

y 2

1";

Q x, y :" x2

y 2

1";

в) P x, y :"x2

y" ;

Q x, y :"

x

y

1".

Вариант 2.

а)

P x : "

x

1

1";

Q x : "

x

1

1";

б) P x, y :" y x2 " ;

Q x, y :" x y2 ";

в)

P x, y :"x2

y" ;

Q x, y :"x2

y2

1".

Вариант 3.

а)

P x : " x

1";

Q x : "

x

1";

б)

P x, y :"

x

y";

Q x, y :"

y

x";

в)

P x, y :"x

y ;

Q x, y :"sin x

y".

Вариант 4.

а)

P x : " x3

x 2

0";

Q x : " x3

x 2

0" ;

б)

P x, y :"

x 1

y";

Q x, y :"

y 1

x";

в)

P x, y :"

x

y

1;

Q x, y :"sin x

y

1 .

Вариант 5.

а)

P x : "

1

1"

;

Q x : "

1

1";

1

x

1

x

б) P x, y :" y x3

1" ;

Q x, y :" x y2

1";

54

в)

P x, y :" y2

x2

1" ;

Вариант 6.

а)

P x : " x3

x

0";

б) P x, y :" x2

y 1";

в) P x, y :" x2

y

2

1"

;

4

Вариант 7.

а)

P x : " x2

x

0";

б) P x, y :" x2

y2

1";

в)

P x, y :" y

2x

";

1

x2

Вариант 8.

а)

P x : "

x

1

1";

б) P x, y :" y x2 " ;

x2

в)

P x, y :"

y

1";

Вариант 9.

а)

P x : "

x

1

x";

б) P x, y :" y x2

1";

в) P x, y :"

x

y

1";

Q x, y :" xy 1".

Q x : " x3 x 0";

Q x, y :" y 2 x 1";

Q x, y :" y ln 1 x2 ".

Q x : " x2 x2 1";

Q x, y :" y2 x2 2" ;

Q x, y :"					x			y".
Q x : "	x		1				1";
Q x, y :" y2							x	1";
Q x, y :"x2							y 2 2		4".
Q x : "	x		1				x";
Q x, y :" y2							x	1";
Q x, y :"		cos x						y".

Вариант 10.

а) P x : "

x

x 1";

Q x : "

x

x

1";

б) P x, y :" y x2

1 x" ;

Q x, y :" y2

2x 1";

Q x, y :"

cos x

y

1".

в) P x, y :"

x

y

1

1" ;

1

Вариант 11.

а) P x : "

1"

;

Q x : "

x

x

1";

x

1

Q x, y :" y2

б) P x, y :" y x2

1 x" ;

2x 1";

Q x, y :"

sin x

y

1".

в) P x, y :"

x

1

y

1" ;

1

Вариант 12.

а) P x : "

1"

;

Q x : "

x

x

1";

x

1

1 2x"; Q x, y :" y2

б) P x, y :" y x2

2x 1" ;

Q x, y :"

sin x

2

y 1".

в) P x, y :"

x

1

y

1";

55

Вариант 13. а) P x : "x3

2x 0";

Q x : "

x

2x 1";

б) P x, y :" y x2

2x"; Q x, y :" y2

2x

1";

в) P x, y :" y

1

" ;

Q x, y :"x2

y

2

1".

x2

4

1

а) P x : " x3

Вариант 14.

2x

0" ;

Q x : "

x

2x

1";

б) P x, y :" y x2

1 2x" ;

Q x, y :" y2

2x

x2 ";

в) P x, y :" y

1

";

Q x, y :"x2

y

2

1".

x2

16

1

а) P x : "x3

Вариант 15.

2x

0";

Q x : "

x

2x

2" ;

б) P x, y :" y x2

3 2x";

Q x, y :" y2

2x x2 " ;

в) P x, y :" y

1

" ;

Q x, y :"x2

y

2

1".

x2

16

1

а) P x : " x3

Вариант 16.

3x

0";

Q x : "

x

2

x

2";

б) P x, y :" y x2

3 x" ;

Q x, y :" y2

5 x2 ";

в) P x, y :" y

1

1"

Q x, y :"x2

y

2

4".

;

x2

16

1

1

Вариант 17.

а) P x : "

1"

;

Q x : "

x

2

x";

x

1

Q x, y :" y2

5 x2 " ;

б) P x, y :" y x2

1";

в) P x, y :" y

1

1";

Q x, y :"tg x y" .

x2

1

Вариант 18.

а) P x : "

1

1"

;

Q x : "| x

3 |

x";

x

1

б) P x, y :" y x2

1";

Q x, y :" y2

1 x" ;

в) P x, y :" y

3

";

Q x, y :"tg x y".

x2

2

Вариант 19.

а) P x : "

1

x";

Q x : "| 2x

3|

4";

1

x

56

б) P x, y :" y x2

1";

Q x, y :" y2

1 3x";

в) P x, y :" y

ln(x)";

Q x, y :"ctg x

y".

Вариант 20.

а) P x : "

1

x";

Q x : "| 2x

3|

4";

x 1

б) P x, y :" y 2x2

1" ;

Q x, y :" y2

2 x";

в) P x, y :" y

2 ln(x)";

Q x, y :"ctg x

y".

Вариант 21.

а) P x : "

1

x

2" ;

Q x : "| 2x

3|

4x";

x

б) P x, y :" y x2

x 1"; Q x, y :" y2

2 x";

в) P x, y :" y3

x

1";

Q x, y :"

x

y".

Вариант 22.

а) P x : "

1

x

2";

Q x : "x(2x

3)

4x";

x

б) P x, y :" y x2

3x 1"; Q x, y :" y2

2 x";

в) P x, y :"y3

x 1";

Q x, y :"

x 1

y".

Вариант 23.

а) P x : "

1

x";

Q x : "x(2x

3)

x

1";

x

б) P x, y :" y x2

3x 1"; Q x, y :" y2

2 x";

в) P x, y :" y2

x 2

";

Q x, y :"

x 1

y".

Вариант 24.

а) P x : "

1

x";

Q x : "x(2x

3)

3x

1";

x

б) P x, y :" y x2

3x 1"; Q x, y :" y2

2

x" ;

в) P x, y :" y2

3x 2

";

Q x, y :"

x 1

y".

Вариант 25.

а) P x : "

1

x" ;

Q x : "x(x

3)

x

2";

2

x

б) P x, y :" y x2

1";

Q x, y :" y2

2 x";

в) P x, y :"y2

3x 1";

Q x, y :"

x 1

y 1".

57

Лабораторная работа 7

КЛАССИФИКАЦИЯ ФОРМУЛ ЛОГИКИ ПРЕДИКАТОВ. РАВНОСИЛЬНОСТЬ ФОРМУЛ

Цель работы

Доказать равносильность данных формул логики предикатов. Проверить правильность логического следствия.

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

Формулы логики предикатов

Определение формулы логики предикатов имеет индуктивный

характер. Формулами логики предикатов являются:
а) предметные переменные: x, y, z, xi, yi, zi, … i	N	;
б) нульместные предикатные переменные: P,	Q,	R, Pi, Qi, Ri, ...
i N ;

в) любой n-местный предикат: Р(х1, … , хn), Q(х1, х2, … , хn), R(х1, х2,

… , хn), …;

г) если F, G – формулы, не содержащие предметных переменных, которые связаны квантором в одной формуле и свободны в другой, то

выражения F , F G , F G , F G , F G также будут

формулами;

д) если F – формула, а х – предметная переменная, входящая свободно в F, то выражения xF x , xF x также будут формулами;

е) других формул в логике предикатов нет.

Из определения формулы логики предикатов следует, что все формулы алгебры высказываний также являются формулами логики предикатов.

Равносильность формул логики предикатов

Две формулы F и G называются равносильными, если при подстановке в эти формулы, вместо предикатных переменных - конкретных предикатов, а вместо предметных переменных - конкретных элементов, эти формулы преобразуются в высказывания с одинаковыми логическими значениями, то есть, либо оба - в истинные высказывания, либо оба - в ложные высказывания. Все основные равносильности алгебры высказываний верны также и для формул логики предикатов. Кроме них в

58

логике предикатов для формул, содержащих кванторы, основными равносильностями являются и следующие:

1. Законы отрицания:

xP x	xP x , xP x				xP x .

2. Законы дистрибутивности:

x P x	Q x	xP x	xQ x ,
x P x	Q x	xP x	xQ x .

3.Если предикат Q не зависит от переменной х, то верны следующие законы:

x P x Q	xP x Q, x P x Q	xP x Q,
x P x Q	xP x Q, x P x Q	xP x Q.

4. Законы переименования связанных переменных:

xP x yP y , xP x yP y .

5.Законы перестановки кванторов:

xyP x, y y xP x, y , x yP x, y y xP x, y .

Классификация формул логики предикатов

Формула F логики предикатов называется выполнимой (опровержимой) на множестве М, если можно найти такие конкретные предикаты, заданные на том же множестве, при подстановке которых вместо предикатных переменных, она преобразуется в выполнимый (опровержимый) предикат. Формула логики предикатов называется

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

F G .

59

Формула F1, равносильная F, называется ее приведенной нормальной

формой, если F1 из логических связок содержит только отрицание, конъюнкцию и дизъюнкцию, а отрицание только над переменными.

Предваренной нормальной формой формулы F называется такая ее приведенная форма, в которой все кванторы вынесены в начало формулы, а область действия каждого квантора распространяется до конца формулы. Для формул логики предикатов справедлива следующая теорема: для каждой формулы логики предикатов существует равносильная ей предваренная нормальная форма. Предваренные нормальные формы формул в логике предикатов используются для выяснения равносильности формул и для решения проблемы классификации формул. Одной из задач классификации формул является проблема разрешимости, которая состоит в следующем. Необходимо найти алгоритм, при помощи которого для произвольной формулы логики предикатов можно определить, будет она тавтологией или нет. Для формул логики предикатов, в отличие от алгебры высказываний, общего алгоритма не существует. То есть, проблема разрешимости имеет отрицательное решение. Несмотря на отсутствие алгоритма в общем случае, в некоторых частных случаях алгоритм существует. Например – для формул, содержащих только одноместные предикаты.

Логическое следствие в логике предикатов

Формула H называется логическим следствием формул F1, F2, … ,

Fn, если при подстановке в формулы F1, F2, … , Fn, H вместо предикатных переменных – конкретных предикатов, а вместо предметных переменных – конкретных элементов, высказывание Н будет логическим следствием

высказываний F1, F2, … , Fn. Основные признаки логического следствия алгебры высказываний верны и в логике предикатов. В частности, пусть

F1, F2, … , Fn, Н – формулы, не содержащие предметных переменных, которые связаны в одних формулах и свободны в других. Тогда формула Н

будет логическим следствием формул F1, F2, … , Fn тогда и только тогда,

когда тавтологией будет следующая формула F1 F2 ... Fn

H .

Порядок выполнения работы

1.Доказать равносильность данных формул логики предикатов.

2.Проверить правильность логического следствия.

60