7.3. Логика предикатов

1. Пусть заданы предикаты:  x  четное число и  x  число, кратное трем. Предикаты определены на множестве N  натуральных чисел. Определить области истинности предикатных выражений:

а)

б)

в)

г) .

2. Пусть Р(х) обозначает «х  простое число», Е(х)  «х  четное число», О(х)  «х  нечетное число» и D(x,y) - «у делится на х». Перевести на русский язык следующие предикатные выражения:

1. Р(7);

2. Е(2)&Р(2);

3. 

4. 

5. 

6. 

7. 

8. 

Пусть предикаты определены на множестве N  натуральных чисел:

•  n делится на 3;

•  n делится на 2;

•  n делится на 4;

•  n делится на 6;

•  n делится на 12.

Определить, какие из предикатных выражений истинные, а какие – ложные:

а) ;

б) ;

в) ;

г) .

4. Найти отрицание следующих формул:

а) ;

б) .

Пример. Доказать тождественную истинность заданного предикатного выражения

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

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

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) .

4. Привести к нормальной форме следующие выражения:

а) ;

б) ;

в) .

5. Представить утверждения, сформулированные на естественном языке в виде предикатных выражений:

1. все судьи — юристы (J(x) обозначает «х  судья»; L(x) обозначает «х  юрист);

2. некоторые юристы — жулики (S(x) обозначает «х  жулик»);

3. ни один судья не является жуликом;

4. некоторые судьи — старики, но бодрые (O(x) обозначает «х  старый»; V(x) обозначает «х  бодрый»);

5. судья Сидоров не стар и не бодр (константу «Сидоров» обозначает символ «j»);

6. не все юристы — судьи;

7. некоторые юристы, являющиеся политиками, - члены государственной Думы (P(x) обозначает «х  политик»; C(x) обозначает «х  член государственной Думы»);

8. ни один член государственной думы не бодр;

9. все старые члены государственной думы - юристы;

10. некоторые женщины одновременно являются юристами и членами государственной думы (W(x) обозначает «х  женщина»);

11. ни одна женщина не является одновременно политиком и домашней хозяйкой (Н(х) обозначает «х  домашняя хозяйка»);

12. некоторые женщины-юристы являются домашними хозяйками;

13. все женщины-юристы восхищаются каким-нибудь судьей (А(х,у) обозначает «х  восхищается y);

14. некоторые юристы восхищаются только судьями;

15. некоторые юристы восхищаются женщинами;

16. некоторые жулики не восхищаются ни одним юристом;

17. судья Сидоров не восхищается ни одним жуликом;

18. существуют как юристы, так и жулики, которые восхищаются судьей Сидоровым;

19. только судьи восхищаются судьями;

20. все судьи восхищаются только судьями.

Пример. Доказать с помощью метода резолюций справедливость следующих рассуждений.

1. Некоторые руководители с уважением относятся ко всем программистам.

2. Ни один руководитель не уважает бездельников.

Следовательно, ни один программист не является бездельником.

Введем следующие предикаты:

C(x) – «x – руководитель»;

P(x) – «x – программист»;

B(x) – «x – бездельник»;

U(x,y) – «x уважает y».

Тогда посылки, записанные в виде предикатных выражений, будут выглядеть так:

1. ;

2. .

Заключение примет следующий вид:

.

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

:

		(1 - 3)	S={a/x}
		(2 - 4)	S={b/y}
		(6 - 7)	S={a/x, b/y}
	Пустой дизъюнкт	(5 - 8)

6. Представить утверждения, сформулированные на естественном языке в виде множества предикатных выражений. Доказать их справедливость, используя метод резолюций:

1. Все мексиканцы носят сомбреро. Ни одна обезьяна не носит сомбреро. Следовательно, ни одна обезьяна не является мексиканцем.

2. Каждый член демократической партии голосует за президента и не любит коммунистов. Некоторые демократы являются предпринимателями. Следовательно, существуют предприниматели, которые не любят коммунистов.

3. Все отцы – мужчины. Если у детей один отец, то они единокровны. Брат – это единокровный мужчина. Джон – отец Боба. Джон – отец Сида. Сид – отец Лиз. Следовательно, Сид и Боб  братья.

4. Ни один человек не является четвероногим. Все женщины – люди. Следовательно, ни одна женщина не является четвероногой.

5. Некоторые республиканцы любят всех демократов. Ни один республиканец не любит ни одного социалиста. Следовательно, ни один демократ не является социалистом.

6. Ни один торговец наркотиками не является наркоманом. Некоторые наркоманы привлекаются к ответственности. Следовательно, не все привлекающиеся к ответственности являются торговцами наркотиками.

7. Все рациональные числа являются действительными числами. Некоторые рациональные числа – целые числа. Следовательно, некоторые действительные числа – целые числа.

8. Все первокурсники общаются со всеми второкурсниками. Ни один первокурсник не общается ни с одним студентом последнего курса. Следовательно, ни один второкурсник не является студентом последнего курса.

9. Некоторым нравится группа «Queen». Некоторые не любят никого, кому нравится группа «Queen». Следовательно, некоторых любят не все.

10. Каждый родитель имеет ребёнка. Если родитель – женщина, то это – мать. Лиз – женщина. Анна – родитель Лиз. Следовательно, Анна – мать.

11. Если родитель – мужчина, то это отец. Если ребёнок – мужчина, то это сын. Иван – мужчина. Сидор – мужчина. Иван – отец Сидора. Следовательно, Иван – отец и Сидор – сын.

12. Если два человека являются родственниками третьего, то первый – родственник второго. Каждый – чей-нибудь родственник. Значит, если Иван – родственник Петра, а Петр – родственник Сидора, то Иван – родственник Сидора.

13. Таможенники возвращают всех, кто въехал в страну без паспорта. Люди на машинах въехали в страну и были возвращены только другими людьми на машинах. Ни один человек на машине не имел паспорта. Следовательно, некоторые таможенники были на машинах.

7. Используя метод резолюций для предикатных выражений для заданного множества гипотез Н={h₁, h₂ ,..., h_n} и утверждения S , доказать справедливость выражения Н | S :

	h1 = x(K(x)&y(R(y)U(x, y))), h2 = x(K(x)y(B(y) (x, y))), S = y(R(y) (y));
	h1 = x(T(x) (x)), h2 = x(N(x)&(x)), S = x(N(x)& (x));
	h1 = x(C(x)W(x)&R(x)), h2 = x(C(x)&O(x)), S = x(P(x)&R(x));
	;
	h1 = x(P(x)Q(x)), h2 = x(Q(x)R(x)), S = x(P(x)R(x));
	h1 = xy(F(x, y)M(x)), h2 = xyw(F(x, y)&F(x, w)E(y, w)), h3 = xy(E(x, y)&M(x)B(x, y)), h4 = F(Y, H), h5 = F(Y, D), h6 = F(D, L), S = B(z, H);
	h1 = z(H(z) (z)), h2 = y(W(y)H(z)), S = x(W(x) (x));
	h1 = xy(P(x)&V(y)W(x, y)), h2 = xy(P(x)&E(y) (x, y)), S = x(V(x) (x));
	h1 = xy(R(x, y)&M(x)O(x)), h2 = xy(R(x, y)&M(y)C(y)), h3 = M(D), h4 = M(B), h5 = R(D,B), S = O(D)&C(B));
	h1 = x(M(x)W(x)), h2 = x(N(x) (x)), S = x(N(x) (x));
	h1 = x(D(x) (x,K)), h2 = x(D(x)&P(x)), S = x(P(x)& (x,K));
	h1 = x (H(x)&U(x,Q)), h2 = xy(H(x)&H(y)& U(x,Q) (x,y)), S = xy(H(x)&H(y)&L(x,y));
	h1 = z(H(z)&R(z) (z)), h2 = y(W(y)H(z)), h3 = R(A), h4 = W(x), S = x( (x)& (x)).