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

№2. Докажите двумя способами (при помощи таблицы истинности и методом доказательства от противного), что формула X – тавтология. Решение 2-м способом постройте так, чтобы на каждом шаге истинностное значение определялось бы однозначно.

0	X=[A?(B?C)]?[(A?B)?(A?C)]
1	X=[(A?B)?(A?C)]?[A?(B?C)]
2	X=[(A?C)?(B?C)]?[(A?B)?C]
3	X=[A?(B?C)]?[(A?B)?(A?C)]
4	X=[(A?B)?C]?[(A?C)?(B?C)]
5	X=[A?(B?C)]?[(A?B)?(A?C)]
6	X=[(A?B)?(A?C)]?[A?(B?C)]
7	X=[(A?B)?C]?[(A?C)?(B?C)]
8	X=[(A?C)?(B?C)]?[(A?B)?C]
9	X=[(A?B)?(A?C)]?[A?(B?C)]
10	X=[(A?C)?(B?C)]?[(A?B)?C]

Решение варианта 0. 1-й способ (построение таблицы истинности).

A	B	C	B?C	A?(B?C)	A?B	A?C	(A?B)?(A?C)	X
1	1	1	1	1	1	1	1	1
1	1	0	0	0	1	0	0	1
1	0	1	1	1	0	1	1	1
1	0	0	1	1	0	0	1	1
0	1	1	1	1	1	1	1	1
0	1	0	0	1	1	1	1	1
0	0	1	1	1	1	1	1	1
0	0	0	1	1	1	1	1	1

Переменным A, B, C приписываются все возможные распределения истинностных значений 1 (истинно) и 0 (ложно). Истинностные значения формул B?C, A?(B?C), A?B, A?C, (A?B)?(A?C), X вычисляются по таблице истинности для импликации. Видно, что формула X принимает истинностное значение 1 при любом распределении истинностных значениях букв A, B, C. Значит, формула X – тавтология.

2-й способ (доказательство от противного). Пусть формула X принимает истинностное значение 0 при некотором распределении истинностных значений букв A, B, C.

Тогда: (1) A?(B?C)=1 по определению импликации;

(2) (A?B)?(A?C)=0 по определению импликации;

(3) A?B=1,

(4) A?C=0, – в силу (2), по определению импликации;

(5) A=1,

(6) C=0, – в силу (4), по определению импликации;

(7) B?C=1, в силу (1) и (5), по определению импликации;

(8) B=1, в силу (3) и (5), по определению импликации;

(9) C=1, в силу (7) и (8), по определению импликации.

Конъюнкция условий (6) и (9) есть противоречие. Значит, формула X принимает истинностное значение 1 при любом распределении истинностных значений букв A, B, C, и поэтому является тавтологией.

№3. Постройте переключательную схему с переключателями A, B и C, удовлетворяющую заданию. Запишите ее формулу. Упростите схему, преобразуя формулу при помощи булевых преобразований.

0	Должно выполняться хотя бы одно из следующих трех условий: 1) переключатель A включен, а переключатели B и C выключены; 2) переключатели A и B включены, а переключатель C выключен; 3) если переключатель B включен, то переключатели A и C выключены.
1	Хотя бы один из переключателей A, B и C выключен, а переключатель A включен тогда и только тогда, когда переключатели B и C выключены.
2	Если переключатель A выключен, то переключатели B и C включены, и переключатель B выключен тогда и только тогда, когда переключатели A и C включены.
3	Ровно два из трех переключателей A, B и C включены, а один из переключателей B и C выключен.
4	Переключатели A, B и C одновременно включены или одновременно выключены, или переключатель A включен, а один из переключателей B и C выключен.
5	Если переключатель C выключен, то переключатели A и B включены, и переключатель A выключен тогда и только тогда, когда переключатели B и C включены.
6	Хотя бы один из переключателей A, B и C включен, а переключатель A выключен тогда и только тогда, когда переключатели B и C включены.
7	Если переключатель B выключен, то переключатели A и C включены, и переключатель C выключен тогда и только тогда, когда переключатели A и B включены.
8	Переключатели A, B и C одновременно включены или одновременно выключены, или переключатель B выключен, а один из переключателей A и C включен.
9	Ровно два из трех переключателей A, B и C выключены, а один из переключателей A и B включен.
10	Переключатели A, B и C одновременно включены или одновременно выключены, или один из переключателей A и B выключен, а переключатель C включен.

Решение варианта 0. Пусть буква X обозначает включенный переключатель X, а отрицание X – выключенный переключатель X. Тогда задание можно записать в виде следующей формулы: (A?B?C)?(A?B?C)?(B?(A?C)).

Конъюнкция 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.