Проверим двумя способами эквивалентность формул: * Составлением таблиц истинности; * с помощью эквивалентных преобразований. 2. С помощью

Проверим двумя способами эквивалентность формул: * Составлением таблиц истинности; * с помощью эквивалентных преобразований. 2. С помощью эквивалентных преобразований привести формулы к ДНФ, КНФ, СДНФ, СКНФ, 3. Построить многочлен Жегалкина. 4. Упростить функции алгебры логики, используя методы минимизации. 5. Проверить, является ли полной данная система функций. Образует ли она базис? 6. Составить контактную схему для формул.

Составим таблицы истинности для заданных функций.
x1 x2 x3 A=x2|x3 B=x1↓A C=x1|x3 D=x2↓C B↓D E=x3|x2 f
0 0 0 1 0 1 0 1 1 0
0 0 1 1 0 1 0 1 1 0
0 1 0 1 0 1 0 1 1 0
0 1 1 0 1 1 0 0 0 1
1 0 0 1 0 1 0 1 1 0
1 0 1 1 0 0 1 0 1 0
1 1 0 1 0 1 0 1 1 0
1 1 1 0 0 0 0 1 0 0
x y z A=y⊕z
B=x→A
B
C=x→y
D=x→z
E=C↔D E
f2
0 0 0 0 1 0 1 0 0 1 1
0 0 1 1 1 0 1 1 1 0 1
0 1 0 1 1 0 1 0 0 1 1
0 1 1 0 1 0 1 1 1 0 1
1 0 0 0 0 1 0 1 0 1 1
1 0 1 1 1 0 0 1 0 1 1
1 1 0 1 1 0 1 1 1 0 1
1 1 1 0 0 1 1 1 1 0 0
Формулы не эквивалентны.
2. Преобразуем формулы, используя следующие соотношения:
a|b=ab=a⋁b; a↓b=ab=a⋁b; a→b=a⋁b; a⊕b=ab⋁ab;
a↔b=ab⋁ab.
Обозначим
f1x1,x2,x3=x1↓x2x3↓x2↓x1x3↓x3x2;
f2x,y,z=(x→y⊕z)→(x→y↔x→z).
Находим
f1(x1,x2,x3)=x1↓x2x3↓x2↓x1x3↓x3x2=
=x1↓x2x3↓x2↓x1x3↓x3x2=
=x1x2x3↓x2x1x3↓x2x3=
=x1x2x3x1x2x3↓ x2x3=
=x1x2x3x1x2x3 x2x3=
=x1x2x3⋁x1x2x3x2x3=x1x2x3.
f2x,y,z=x→y⊕z→x→y↔x→z=
=x→yz⋁yz→x⋁y↔x⋁z=
=x⋁yz⋁yz→x⋁yx⋁z⋁x⋁yx⋁z=
=x⋁yz⋁yz⋁(xyx⋁z⋁x⋁yxz=
=x⋁yz⋁yz⋁xy⋁xz=x⋁yz⋁yz⋁xy⋁xz=
=x⋁y⋁z.
Запишем ДНФ и, одновременно, КНФ функций:
fx1,x2,x3=x1x2x3;
fx,y,z=x⋁y⋁z.
Построим СДНФ:
fx1,x2,x3=x1x2x3
fx,y,z=x⋁y⋁z=
=xyz⋁yz⋁yz⋁yz⋁zxy⋁xy⋁xy⋁xy⋁yxz⋁xz⋁xz⋁xz=
=xyz⋁xyz⋁xyz⋁xyz⋁xyz⋁xyz⋁xyz.
Построим СКНФ:
fx1,x2,x3=x1x2x3=
=x1⋁x2⋁x3x1⋁x2⋁x3x1⋁x2⋁x3x1⋁x2⋁x3&
&(x1⋁x2⋁x3)(x1⋁x2⋁x3)x1⋁x2⋁x3;
fx,y,z=x⋁y⋁z.
3

. Построим многочлен Жегалкина.
Учитывая, что a=1⊕a, a⋁b=a⊕b⊕ab находим:
fx1,x2,x3=x1x2x3=x2x3⊕x1x2x3;
fx,y,z=x⋁y⋁z=x⊕y⊕xy⋁z=
=(1⊕x⊕1⊕y⊕1⊕x⊕y⊕xy)⋁z=(1⊕xy)⋁z=
=1⊕xy⊕z⊕z1⊕xy=1⊕xy⊕1⊕z⊕1⊕xy+z⊕xyz=
=1⊕xyz.
4