等價表達式

Question

證明下列三個表達式是等效

 1. if x then y else z 
    2. if y then x or z else z > x 
    3. if z then x≤y else x∧y 

詢問一些指針哪裏開始，或至少一個鏈接到閱讀有關

Answer 1

一個直接的方法是通過證明等價詳盡地寫下真值表中所有可能的狀態。 （它有助於只有三個布爾變量參與;-)

+---+---+---+--------------------+----------------------------+---------------------------- 
| x | y | z | if x then y else z | if y then x v z else z > x | if z then x ≤ y else x ∧ y 
+---+---+---+--------------------+----------------------------+---------------------------- 
| 0 | 0 | 0 |    0 |    0 > 0 = 0 |    0 ∧ 0 = 0 
| 0 | 0 | 1 |    1 |    1 > 0 = 1 | 0 <= 0 = 1 
| 0 | 1 | 0 |    0 | 0 v 0 = 0     |    0 ∧ 1 = 0 
| 0 | 1 | 1 |    1 | 0 v 1 = 1     | 0 <= 1 = 1 
| 1 | 0 | 0 | 0    |    0 > 1 = 0 |    1 ∧ 0 = 0 
| 1 | 0 | 1 | 0    |    1 > 1 = 0 | 1 <= 0 = 0 
| 1 | 1 | 0 | 1    | 1 v 0 = 1     |    1 ∧ 1 = 1 
| 1 | 1 | 1 | 1    | 1 v 1 = 1     | 1 <= 1 = 1 
+---+---+---+--------------------+----------------------------+---------------------------- 

通知所有三個功能如何有）的所有可能的組合（X，Y，Z相同的結果。

或者，直接證明也是可能的。

首先是一些符號：

x + y  x or y 
xy   x and y 
x'   not(x) 
x = 0  x is false 
x = 1  x is true 

還有一些意見：

• if x then y else z相當於xy + x'z。
• z > x相當於x'z（因爲z > x是真的當且僅當z是真實的，x是假的。）
• x ≤ y相當於x' + y

因此，證明從問題的等價之一：

if y then x + z else z > x 
= y(x + z) + y'(z > x)    (if-then-else) 
= y(x + z) + y'(x'z)     (z > x) 
= xy + yz + x'y'z      (distributivity, commutativity) 
= xy(z + z') + (x + x')yz + x'y'z  (x + x' = z + z' = 1, and and-ing with 1 has no effect) 
= xyz + xyz' + xyz + x'yz + x'y'z 
= xyz + xyz'  + x'yz + x'y'z  (xyz + xyz = xyz, or-ing with itself has no effect) 
= xy(z + z') + x'z(y + y')   (regroup terms) 
= xy + x'z       (z + z' = y + y' = 1) 
= if x then y else z 

對於問題中的其他等價物也是類似的。