Проверим двумя способами эквивалентность формул

Составим таблицы истинности для заданных функций.
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