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

Составим таблицу истинности для первой функции:
x
y
z
x
y z
y z
x→ (y z)
( x→ (y z))
0 0 0 1 0 1 1 0
0 0 1 1 1 0 0 1
0 1 0 1 1 0 0 1
0 1 1 1 0 1 1 0
1 0 0 0 0 1 1 0
1 0 1 0 1 0 1 0
1 1 0 0 1 0 1 0
1 1 1 0 0 1 1 0
Продолжение
x
y
z
x → y
x →z
( x→ (y z))
(x → y)(x →z)
f1
0 0 0 1 1 0 0 1
0 0 1 1 1 1 0 0
0 1 0 1 1 1 0 0
0 1 1 1 1 0 0 1
1 0 0 0 0 0 0 1
1 0 1 0 1 0 1 1
1 1 0 1 0 0 1 1
1 1 1 1 1 0 0 1
Составим таблицу истинности для второй функции:
x
y
z
y z
x → (y z)
x → y
x → z
(x → y)(x → z)
f2
0 0 0 0 1 1 1 0 0
0 0 1 1 1 1 1 0 0
0 1 0 1 1 1 1 0 0
0 1 1 0 1 1 1 0 0
1 0 0 0 0 0 0 0 1
1 0 1 1 1 0 1 1 0
1 1 0 1 1 1 0 1 0
1 1 1 0 0 1 1 0 1
Проверим эквивалентность формул с помощью эквивалентных преобразований:
f1≡ x→ y z→x → yx →z=
y z=y ∧ z∨y ∧ z=y ∧ z∧y ∧ z=y ∨ z∧y ∨ z=
=y ∨ z∧y ∨ z;
x→ y z=x∨y ∨ z∧y ∨ z=x∨y ∨ z∧y ∨ z;
x→ y z=x∧y ∨ z∧y ∨ z=x∧y∨z∨y∨z=
=x∧y∧z∨y∧z=x∧y∧z∨y∧z=
=x∧y∨y∧y∨z∧z∨y∧z∨z=x∧y∨z∧z∨y.
x → yx →z=x ∨ yx ∨z=
=x ∨ y∧x ∨z∨x ∨y∧x ∨z=
=x ∨ y∧x ∧z∨x ∧y∧x ∨z=x ∧x∧z∨ y∧x ∧z∨
x ∧y∧x ∨x∧y∧z=x∧y∧z∨y∧z=
=x∧y∨y∧y∨z∧z∧y∧z∧z=x∧y∨z∧z∧y.
f1≡x∧y∨z∧z∨y∨x∧y∨z∧z∧y=
=x∨y∨z∨z∨y∨x∧y∨z∧z∧y=
=x∨y∧z∨y∧z∨x∧y∧z∨y∧z=x∨y∧z∨y∧z.
f1≡x∨y∧z∨y∧z.
f2≡ (x → (y z))↓((x →y)(x → z))
x → (y z)=x∨y ∧ z∨y ∧ z
x →yx → z=x ∨yx ∨ z=x ∨y∧x ∨ z∨x ∨y∧x ∨ z=
=x ∨y∧x∧z∨x∧y∧x ∨ z=x∧y∧z∨x∧y∧z=
=x∧y∨y∧y∨z∧z∨y∧z∨z=x∧y∨z∧y∨z.
f2≡x∨y ∧ z∨y ∧ z↓x∧y∨z∧y∨z=
=x∨y ∧ z∨y ∧ z∧x∧y∨z∧y∨z=
=x∧y ∧ z∧y ∧ z∧x∨y∨z∨y∨z=
=x∧y∨z∧y∨z∧x∨y∧z∨y∧z=
=x∧y∨z∧y∨z∧x∨y∨y∧y∨z∧z∨y∧z∨z=
=x∧y∨z∧y∨z∧x∨y∨z∧y∨z=
=x∧x∧y∨z∧y∨z∨x∧y∨z∧y∨z∧y∨z∧y∨z=
=x∧y∨z∧y∨z.
f2≡x∧y∨z∧y∨z.
Оба способа показали, что f1≠f2.
2 . С помощью эквивалентных преобразований приведем формулы к ДНФ, КНФ, СДНФ, СКНФ.
f1≡x∨y∧z∨y∧z- уже приведена к ДНФ. Приведем к СДНФ:
f1≡x∧y∨y∨y∧z∧x∨x∨y∧z∧x∨x=
=x∧y∧z∨z∨x∧y∧z∨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∨x∧y∧z∨x∧y∧z∨x∧y∧z∨x∧y∧z∨x∧y∧z.
Перейдем от ДНФ к КНФ, для этого ставим над ДНФ два отрицания и с помощью правил де Моргана:
f1≡x∨y∧z∨y∧z=x∧y∧z∧y∧z=x∧y∨z∧y∨z=
=x∧y∧y∨y∧z∨z∧y∨z∧z=x∧y∧z∨z∧y=
=x∧y∧z∨x∧z∧y=x∧y∧z∧x∧z∧y=x∨y∨z∧x∨y∨z.
В данном случае КНФ равно СКНФ.
f2≡x∧y∨z∧y∨z- уже приведена к КНФ. Перейдем от КНФ к СКНФ:
f2≡x∧y∨z∧y∨z=x∨y∧y∧x∧x∨y∨z∧x∧x∨y∨z=
=x∨y∨z∧z∧x∨y∨z∧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∧x∨y∨z∧x∨y∨z∧x∨y∨z∧x∨y∨z∧x∨y∨z.
Перейдем от КНФ к ДНФ, для этого ставим над ДНФ два отрицания и с помощью правил де Моргана:
f2≡x∧y∨z∧y∨z=x∨y∨z∨y∨z=x∨y∧z∨y∧z=
=x∨y∨z∧x∨y∨z=x∧y∧z∨x∧y∧z-она же СКНФ.
3