Эквивалентные функции

Зная таблицу истинности для элементарных функций, можно вычислить таблицу истинности той функции, которую реализует данная формула.

Пример 1: F1=X1•X2v(X1•¬X2v¬X1•X2)

X1X2X1•¬X2¬X1•X2X1•¬X2v¬X1•X2X1•X2F1
0000000
0101101
1010101
1100011

Таким образом, формула F1 реализует дизъюнкцию.

Пример 2: F2=X1•X2→X1

X1X2X1•X2F2
0001
0101
1001
1111

Таким образом, формула F2 реализует константу 1.

Пример 3: F3=((X1•X2)⊕X1)⊕X2

X1X2X1•X2(X1•X2)⊕X1F3
00000
01001
10011
11101

Таким образом, формула F3 реализует дизъюнкцию.

Булевы функции F1 и F2 называются эквивалентными, если на всяком наборе (a1, a2 ... an) нулей и единиц значения функций совпадают. Обозначение эквивалентных функций следующее: F1=F2.

Согласно приведенным примерам 1-3, можно написать:

X1•X2v(X1•¬X2v¬X1•X2)=X1vX2

X1•X2→X1=1

((X1•X2)⊕X1)⊕X2=X1vX2