Logic and proofs(2/5)

A compound proposition is always true or false

• tautology(always true)

• contradiction(always false)

注意一定要複合陳述

Ex:

(1) tautology

• p or ~p

(2) contradiction

• p and ~p

Def: Logic Equivalence

two compound propositions p and q are called logical equivalent,

if p <--> is a tautology

當p ≡ q， p = true, q = true; p = false, q = false

則 p <--> q is a tautology

if and only if 的 truth table

Demorgan' s Law

以truth table 驗證

結合率，交換率

Ex:

• p and (q or r) ≡ (p and q) or (p and r)

比較特別的是在數的四則運算，乘法對加法滿足分配律，

X(Y + Z) = XY + XZ，但反之

而Logic operator 內 or 跟 and 地位是一樣的，這邊比較不一樣所以

• p or (q and r) ≡ (p or q) and (p or r)

重要的要記的，最基本的

Algebra operation

Truth table 可以拿來證明， 相對的Algebra 的運算也可以拿來推演。

Show p ^ q --> p v q is tautology