Математическая логика и теория алгоритмов (стр. 4 )

Формула (R?S)?(R?S)?(R?S) написана в СДНФ, и эквивалентна X.

Ответ: X=(R?S)?(R?S)?(R?S)

№5. Образуют ли заданные логические связки полную систему связок?

Считайте известными, что системы {, ?, ?}, {, ?} и {, ?} – полные системы связок. Слева приведены таблицы истинности для «новых» логических связок:

? (обратная импликация),

? (отрицание импликации),

• (отрицание обратной импликации),

? (отрицание эквивалентности: «либо…, либо»),

(постоянной функции «истинно»),

| (штрих Шеффера),

а справа – задания вариантов.

A	B	A?B	0	a)	|
1	1	1	A	B	A?B	b)	•, ?, ?
1	0	1	1	1	0	1	a)	?, ?
0	1	0	1	0	1	b)	?, ?
0	0	1	0	1	1	2	a)	?, •
0	0	0	b)	?, ?
3	a)	?, ?
b)	?, •
A	B	A?B	4	a)	?, ?
1	1	0	A	B	AB	b)	?, •
1	0	1	1	1	1	5	a)	?, ?
0	1	0	1	0	1	b)	?, ?
0	0	0	0	1	1	6	a)	?, ?
0	0	1	b)	?, •
7	a)	?, ?
b)	?, ?
A	B	A•B	8	a)	?, •
1	1	0	A	B	A|B	b)	?, ?
1	0	0	1	1	0	9	a)	?, •
0	1	1	1	0	1	b)	, ?
0	0	0	0	1	1	10	a)	?, ?
0	0	1	b)	, •

Решение варианта 0. a) Так как система {, ?} – полная система связок, то любую логическую операцию (функцию истинности) можно выразить через операции и ?. Отрицание и конъюнкцию можно выразить через операцию |. Действительно, в силу определения штриха Шеффера, A=A|A и A?B=(A|B)=(A|B)|(A|B). Значит, любую логическую операцию можно выразить через штрих Шеффера.

Ответ: система { | } – полная система связок.

b) Пусть функция истинности h(x1,...,xn) выражена через операции •, ?, ?. Тогда, так как 0•0=0?0=0?0=0, то h(0,...,0)=0.

В частности, если операция выражена через операции •, ?, ?, то 0=0, что неверно. Значит, операцию нельзя выразить через операции •, ?, ?.

Ответ: система {•, ?, ?} не является полной системой связок.

№6. Постройте отрицание формулы.

0	?x?y(A?B)??x(?yA??yB)
1	?y(?x(?zA?B)??x(A??zB))
2	?y(?x(A?(B?C))??x(A?(B?C)))
3	?x(A?B)??y((A??xC)?(B??xC))
4	?y(?x(?zA?B)??x(A??zB))
5	?y(?x(A?(B?C))??x(A?(B?C)))
6	?x(A?B)??y((A??xC)?(B??xC))
7	?y(?x(A??zB)??x(?zA?B))
8	?y(?x(A?(B?C))??x(A?(B?C)))
9	?x(A?B)??y((A??xC)?(B??xC))
10	?y(?x(A??zB)??x(?zA?B))

Решение варианта 0. Используя свойства кванторов и тавтологии, получим:

(?x?y(A?B)??x(?yA??yB))=(закон де Моргана (P?Q)=P?Q)

=?x?y(A?B)?(?x(?yA??yB))=(свойства квантора ?xP=?xP, ?xP=?xP)

=?x?y(A?B)??x(?yA??yB)=(свойство квантора ?xP=?xP)

=?x?y(A?B)??x(?yA??yB)=(тавтологическое тождество (P?Q)=P?Q)

=?x?y(A?B)??x(?yA??yB)=(свойство квантора ?xP=?xP)

=?x?y(A?B)??x(?yA??yB).

№7. Являются ли логически общезначимыми следующие формулы:

X	Y
0	(?xA??xB)??x(A?B)	?x(A?B)?(?xA??xB)
1	?x(A?B)?(?xA??xB)	?x(A?B)?(?xA??xB)
2	(?xA??xB)??x(A?B)	(?xA??xB)??x(A?B)
3	?x(A?B)?(?xA??xB)	?x(A?B)?(?xA??xB)
4	(?xA??xB)??x(A?B)	(?xA??xB)??x(A?B)
5	?x(A?B)?(?xA??xB)	(?xA??xB)??x(A?B)
6	?x(A?B)?(?xA??xB)	(?xA??xB)??x(A?B)
7	(?xA??xB)??x(A?B)	?x(A?B)?(?xA??xB)
8	?x(A?B)?(?xA??xB)	(?xA??xB)??x(A?B)
9	?x(A?B)?(?xA??xB)	(?xA??xB)??x(A?B)
10	?x(A?B)?(?xA??xB)	?x(A?B)?(?xA??xB)

Решение варианта 0. 1) Пусть I – интерпретация, d=(d1, d2,…) – последовательность элементов интерпретации I, возьмем для определенности x=x1, а через d?=(u, d2,…) обозначим произвольную последовательность элементов интерпретации I, отличающуюся от последовательности d только первой компонентой.

Предположим, что I(?xA??xB)=1 на последовательности d. Тогда, в силу определения дизъюнкции, I(?xA)=1 на последовательности d или I(?xB)=1 на последовательности d. По смыслу квантора всеобщности верно хотя бы одно из следующих утверждений: I(A)=1 на любой последовательности d? или I(B)=1 на любой последовательности d?. В силу определения дизъюнкции, I(A?B)=1 на любой последовательности d? и в первом случае, и во втором случае. Вновь используя определение квантора всеобщности, получим, что ?x(A?B)=1 на последовательности d. Следовательно, в силу определения импликации, I(X)=1 на последовательности d.

Таким образом, для любой интерпретации I мы получили, что I(X)=1 на любой последовательности d элементов интерпретации I.

Ответ: формула X – логически общезначимая формула.

2) Пусть интерпретация I есть множество всех действительных чисел, x=x1, примером формулы A возьмем формулу x=5, а примером формулы B – формулу x?5. Тогда формула Y примет следующий вид: ?x(x=5?x?5)?(?x x=5??x x?5).

Вычислим истинностное значение I(Y) формулы Y на любой последовательности d элементов интерпретации I.

(a) I(x=5)=1 на любой последовательности вида d=(5, …).

(b) I(x?5)=1 на любой последовательности d, 1-я компонента которой отлична от 5.

В обоих случаях, в силу определения дизъюнкции, I(x=5?x?5)=1.

По смыслу квантора всеобщности I(?x(x=5?x?5))=1 на любой последовательности.

Из пункта (a) по смыслу квантора всеобщности следует I(?x x=5)=0 на любой последовательности. Из пункта (b) по смыслу квантора всеобщности следует I(?x x?5)=0 на любой последовательности.

В силу определения дизъюнкции, I(?x x=5??x x?5)=0 на любой последовательности. В силу определения импликации, I(Y)=0 на любой последовательности.

Ответ: формула Y не является логически общезначимой формулой.

№8. Пусть L – язык первого порядка со следующими собственными символами: = (бинарный предикатный символ); + (бинарный функциональный символ);? (бинарный функциональный символ); M (бинарный предикатный символ); (константа).

Данное математическое предложение запишите в виде формулы языка L. Истинна ли эта формула в интерпретации N с множеством интерпретации N – множеством натуральных чисел и с естественной интерпретацией собственных символов языка L?

0	Простое число имеет ровно два делителя.
1	Для любых двух чисел x и y найдется такое число d, что для всех чисел z числа x и y делятся на z тогда и только тогда, когда число d делится на z.
2	Если произведение двух чисел делится на простое число p, то хотя бы один из множителей делится на p.
3	Каждое простое число, отличное от 1, имеет простой делитель.
4	Если числа x и y взаимно просты, то существуют такие числа a и b, что ax+by=1.
5	Любые два числа имеют наибольший общий делитель.
6	Для любых двух чисел x и y найдется такое число c, что для всех чисел z числа x и y делят число z тогда и только тогда, когда число c делит число z.
7	Отношение делимости рефлексивно, симметрично и транзитивно.
8	Существуют два простых числа, таких, что одно больше другого на 1.
9	Неверно, что произведение двух чисел делится на z тогда и только тогда, когда хотя бы один из сомножителей делится на z.
10	Любые два числа имеют наименьшее общее кратное.

Решение варианта 0. Целое число p называется простым числом, если оно отлично от 1 и его делителями являются только делители 1 и кратные p. Значит, данное математическое предложение можно записать в виде следующей формулы: