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

1. Составляем таблицы истинности:
- для формулы f1
x
y
z
y↓z
x→y↓z
x→y
x→z
x→y|x→z
f1
0 0 0 1 1 1 1 0 1
0 0 1 0 1 1 1 0 1
0 1 0 0 1 1 1 0 1
0 1 1 0 1 1 1 0 1
1 0 0 1 1 0 0 1 0
1 0 1 0 0 0 1 1 1
1 1 0 0 0 1 0 1 1
1 1 1 0 0 1 1 0 0
- для формулы f2
x
y
z
y→z
x→y→z
x→y
x→z
x→y→x→z
f2
0 0 0 1 1 1 1 1 0
0 0 1 1 1 1 1 1 0
0 1 0 0 1 1 1 1 0
0 1 1 1 1 1 1 1 0
1 0 0 1 1 0 0 1 0
1 0 1 1 1 0 1 1 0
1 1 0 0 0 1 0 0 1
1 1 1 1 1 1 1 1 0
Как видим, формулы не являются эквивалентными.
Преобразуем первую формулу x→y↓z⊕x→y|x→z:
- избавляемся от стрелки Пирса a↓b=ab и импликаций a→b=a∨b:
x→y↓z⊕x→y|x→z=x→yz⊕x∨y|x∨z
- избавляем от штриха Шеффера a|b=ab и импликации a→b=a∨b:
x→yz⊕x∨y|x∨z=x∨yz⊕x∨yx∨z=
=x∨yz⊕x∨y∨x∨z=x∨yz⊕xy∨xz
- избавляемся от исключающего или a⊕b=ab∨ab:
x∨yz⊕xy∨xz=x∨yzxy∨xz∨x∨yzxy∨xz
- и проводим преобразования:
x∨yzxy∨xz∨x∨yzxy∨xz=x∨yzxy∧xz∨xyzxy∨xz
=x∨yzx∨yx∨z∨xy∨zxy∨xz=
=x∨yzx∨yz∨xy∨xzxy∨xz=x∨xyz∨xyz
Получили: f1=x∨xyz∨xyz
Преобразуем вторую формулу x→y→z↓x→y→x→z:
- избавляемся от импликаций a→b=a∨b:
x→y→z↓x→y→x→z=x→y∨z↓x∨y→x∨z
- еще раз избавляемся от импликаций a→b=a∨b:
x→y∨z↓x∨y→x∨z=x∨y∨z↓x∨y∨x∨z=
=x∨y∨z↓xy∨x∨z
- избавляемся от стрелки Пирса a↓b=a∨b:
x∨y∨z↓xy∨x∨z=x∨y∨z∨xy∨x∨z
- и проводим преобразования:
x∨y∨z∨xy∨x∨z=x∨y∨z∧xy∨x∨z=
=xyz∧xyxz=xyz∧x∨yxz=xyz
Получили: f2=xyz
Поскольку x∨xyz∨xyz≠xyz, то формулы не являются эквивалентными.
2 . Приведем формулы к ДНФ, КНФ, СДНФ, СКНФ.
2.1 Формула f1x3=x→y↓z⊕x→y|x→z
Ранее мы получили следующую ДНФ:
f1=x∨xyz∨xyz
Которую можно упростить:
x∨xyz∨xyz∨xyz∨xyz=x∨yz∨yz
Таким образом, минимальная ДНФ:
x∨yz∨yz
Чтобы получить СДНФ, используем закон склеивания a=ab∨ab:
x∨xyz∨xyz=x∧y∨y∧z∨z∨xyz∨xyz=
=xyz∨xyz∨xyz∨xyz∨xyz∨xyz
Получили CДНФ:
xyz∨xyz∨xyz∨xyz∨xyz∨xyz
Приведем формулу к КНФ, используя найденное выражение для ДНФ:
x∨yz∨yz=x∨yz∨yz=x∧yz∧yz=x∧y∨z∧y∨z=
=xy∨xz∧y∨z=xyz∨xyz=xyz∧xyz=x∨y∨z∧x∨y∨z
Получили КНФ:
x∨y∨z∧x∨y∨z
Которая также является и СКНФ.
2.2 Формула f1x3=x→y→z↓x→y→x→z
Ранее мы получили следующую ДНФ:
f2=xyz
Которая также является и СДНФ.
Приведем формулу к КНФ, используя найденное выражение для ДНФ:
xyz=xyz∨0=xyz∨0=x∨y∨z∧1=x∨y∨z∧x∨x=
=xy∨xz∨x=x∧x∨y∧x∨z
Получили КНФ:
x∧x∨y∧x∨z
Чтобы получить СКНФ, используем формулы aa=0:
x∧x∨y∧x∨z=x∨yy∨zz∧x∨y∨zz∧x∨z∨yy=
=x∨y∨z∧x∨y∨z∧x∨y∨z∧x∨y∨z∧x∨y∨z∧x∨y∨z∧x∨y∨z
Получили СКНФ:
x∨y∨z∧x∨y∨z∧x∨y∨z∧x∨y∨z∧x∨y∨z∧x∨y∨z∧x∨y∨z
3. Построим многочлен Жегалкина.
3.1 Формула f1x3=x→y↓z⊕x→y|x→z
Чтобы построить полином Жегалкина, запишем таблицу истинности:
x
y
z
F
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Строим полином Жегалкина вида:
Px,y,z=a0⊕a1x⊕a2y ⊕a3z⊕a4xy⊕a5xz⊕a6yz⊕a7xyz
P0,0,0=1=a1.
P0,0,1=1=a0⊕a3=1⊕a3 a3=0.
P0,1,0=1=a0⊕a2=1⊕a2 a2=0.
P0,1,1=1=a0⊕a2⊕a3⊕a6=1⊕0⊕0⊕a6 a6=0.
P1,0,0=0=a0⊕a1=1⊕a1 a1=1.
P1,0,1=1=a0⊕a1⊕a3⊕a5=1⊕1⊕0⊕a5 a5=1.
P1,1,0=1=a0⊕a1⊕a2⊕a4=1⊕1⊕0⊕a4 a4=1.
P1,1,1=0=a0⊕a1⊕a2⊕a3⊕a4⊕a5⊕a6⊕a7 a7=0.
Тогда полином Жегалкина для функции f1:
Px,y,z=1⊕x⊕xy⊕xz
3.2 Формула f2x3=x→y→z↓x→y→x→z:
Записываем таблицу истинности:
x
y
z
F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
Строим полином Жегалкина вида:
Px,y,z=a0⊕a1x⊕a2y ⊕a3z⊕a4xy⊕a5xz⊕a6yz⊕a7xyz
P0,0,0=0=a1.
P0,0,1=0=a0⊕a3=0⊕a3 a3=0.
P0,1,0=0=a0⊕a2=0⊕a2 a2=0.
P0,1,1=0=a0⊕a2⊕a3⊕a6=0⊕0⊕0⊕a6 a6=0.
P1,0,0=0=a0⊕a1=0⊕a1 a1=0.
P1,0,1=0=a0⊕a1⊕a3⊕a5=0⊕0⊕0⊕a5 a5=0.
P1,1,0=1=a0⊕a1⊕a2⊕a4=0⊕0⊕0⊕a4 a4=1.
P1,1,1=0=a0⊕a1⊕a2⊕a3⊕a4⊕a5⊕a6⊕a7 a7=1.
Тогда полином Жегалкина для функции f2:
Px,y,z=xy⊕xyz
4