Дисциплина «Математическая логика и теория алгоритмов» (стр. 3 )

Конъюнкция U?V соответствует последовательному соединению, а дизъюнкция U?V – параллельному соединению схем U и V.

Построим эту переключательную схему:

A	B	C
A	B	C
A
B
C

Чтобы упростить схему, используя законы алгебры Буля, упростим ее формулу:

(A?B?C)?(A?B?C)?(A?(B?C))=(дистрибутивный закон ? относительно ?)

=(A?(B?B)?C)?(B?(A?C))=(тождествоB?B=1, определение ?)

=(A?1?C)?(B?(A?C))=(тождество A?1=A, коммутативность и ассоциативность ?)

=(A?C)?(A?C)?B=(дистрибутивный закон ? относительно ?)

=((A?A)?C)?B=(1?C)?B=C?B.

Ответ:

A

B

C

№4. Приведите формулу X к совершенно дизъюнктивной нормальной форме (СДНФ).

0	X=((R?S)?R)
1	X=(R?(S?T))? ((R?S)?T)
2	X=R?(S?((R?T)?(S?T)))
3	X=(R?(S?T))?((R?S)?T)
4	X=((R?(R?S))?(T?S))?T
5	X=(R?(S?T))?((R?S)?T)
6	X=(R?(S?T))?((R?S)?T)
7	X=R?(S?((R?T)?(S?T)))
8	X=((R?S)?T)?((R?S)?T)
9	X=((R?(R?S))?(T?S))?T
10	X=(R?(S?T))?((R?S)?T)

Решение варианта 0. Построим таблицу истинности для формулы X:

R	S	R?S	R	(R?S)?R	X
1	1	1	0	0	1
1	0	1	0	0	1
0	1	1	1	1	0
0	0	0	1	0	1

Формула X – не противоречие. Значит, формулу X можно привести к СДНФ.

Из таблицы истинности видно, что X=1 тогда и только тогда, когда одновременно истинны следующие простейшие высказывания: (1 случай)R, S; (2 случай)R, S; (3 случай)R, S. Другими словами, X=1 тогда и только тогда, когда R=S=1, или R=S=1, или R=S=1; ?R?S=1, или R?S=1, или R?S=1; ?(R?S)?(R?S)?(R?S)=1.

Формула (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 только первой компонентой.