1 of 41

Discrete Mathematics

Chapter 1 �The Foundations : Logic and Proofs

大葉大學資訊工程系黃鈴玲

2 of 41

1-1 Propositional Logic 命題邏輯

Def : A proposition (命題) is a declarative (敘述) sentence that is either true or false, but not both.
Example 1 :

(1) Toronto is the capital of Canada.

(2) 1 + 1 = 2

都是命題！但(1)是錯誤的命題

Example 2 :

(1) What time is it ?

(2) Read this carefully.

(3) x + 1 = 2

都不是命題！但(3)若給了x的範圍，則可算是命題

Ch1-2

3 of 41

通常用小寫英文字母來表示命題，如p, q, r等
命題的真值(truth value)，也就是它的「真」或「假」，分別以 T, F 表示

接下來探討，如何從原有的數個命題，利用邏輯運算符號合成新的命題

Ch1-3

4 of 41

Logical operators (邏輯運算子) �and truth table (真值表)

Def : A truth table (真值表) displays the relationships between the truth values of propositions. �(列舉命題所有真假的可能性)

Table 1. The truth table for the Negation (not) (非) of a Proposition

eg. p : “Today is Friday.”

﹁p : “Today is not Friday.”

Ch1-4

p	﹁ p

F

T

F

5 of 41

Table 2. The truth table for the Conjunction (and) (且) of two propositions

eg. p : “Today is Friday.”

q : “It’s raining today.”

p ∧ q : “Today is Friday and it’s raining today.”

Ch1-5

p	q	p ∧ q
T	T
T	F
F	T
F	F

T

F

(p, q 都為T時，p∧q才是T)

6 of 41

Table 3. The truth table for the Disjunction (or) (或) of two propositions.

eg. p : “Today is Friday.”

q : “It’s raining today.”

p ∨ q : “Today is Friday or it’s raining today.”

Table 4. The truth table for the Exclusive or (xor) �(互斥或) of two propositions.�

eg. p : “Today is Friday.”

q : “It’s raining today.”

p ⊕ q : “Either today is Friday � or it’s raining today, � but not both.”

p	q	p ∨ q
T	T
T	F
F	T
F	F

Ch1-6

p	q	p ⊕ q
T	T
T	F
F	T
F	F

T

F

T

F

(p, q 只要有一個是T，p∨q就是T)

(p, q 真值不相等時，p⊕q才是T)

7 of 41

Table 5. The truth table for the Implication (p implies q) p → q (p蘊涵q) (If p then q).

�� eg. p : “You make more than $25000.”

q : “You must file a tax return.”

p → q : “If you make more than $25000, � then you must file a tax return.”

Some of the more common ways of expressing this implication are (下列幾種用法都是相同的):

(1) if p then q (若p則q，p是q的充分條件)

(2) p implies q

(3) p only if q (只有q是True時，p才可能是True，� 若q是False，則p一定是False)

p	q	p → q
T	T
T	F
F	T
F	F

Ch1-7

(若p則q，非q 則非p)

T

F

要求：若p對，則q一定要對� (若p錯，則不管q是T或F，p → q都是T)

8 of 41

Def : In the implication p → q , p is called the hypothesis (假設) and q is called the conclusion (結論).
Def : Compound propositions (合成命題) are formed from existing propositions using logical operators. (即 ∧ 、 ∨ 、 ⊕、 →等)
Table 6. The truth table for the Biconditional p ↔ q �(雙蘊涵) ( p → q and q → p )�

�� “p if and only if q”

“p iff q ”

“If p then q , and � conversely.”

Ch1-8

p	q	p → q	q → p	p ↔ q
T	T
T	F
F	T
F	F

(p若且唯若q)

and 運算

T

F

T

F

T

F

T

F

T

(p與q的真值相等時才會是T)

9 of 41

Ch1-9

13. 判定下列各條件句的真假值：� (a) 如果1+1=2，則2+2=5。� (b) 如果1+1=3，則2+2=4。� (c) 如果1+1=3，則2+2=5。� (d) 如果猴子會飛，則1+1=3。�

Exercise 1-1

10 of 41

※Truth Table for Compound Propositions

例11: 建構下列複合命題的真值表� (p ∨ ¬q) → (p ∧ q)

Ch1-10

p	q
T	T
T	F
F	T
F	F

F

T

F

T

F

T

F

T

F

T

F

T

F

¬q

p ∨ ¬q

p ∧ q

(p ∨ ¬q) → (p ∧ q)

not

or

and

imply�(if…then…)

11 of 41

Ch1-11

29. 建立下列複合命題的真值表：� (a) (p ∨ q) → (p ⊕ q)� (b) (p ⊕ q) → (p ∧ q)� (c) (p ∨ q) ⊕ (p ∧ q)� (d) (p ↔ q) ⊕ (¬p ↔ q)� (e) (p → q) ∧ r��提醒：複合命題中若有n個命題，真值表有2ⁿ列。

�

Exercise 1-1

12 of 41

Table 8. Precedence of Logical Operators �(邏輯運算的優先順序)

eg. (1) p ∧ q ∨ r means ( p ∧ q ) ∨ r

(2) p ∨ q → r means ( p ∨ q ) → r

(3) p ∧ ﹁ q means p ∧ ( ﹁ q )

Ch1-12

Operator	Precedence
﹁	1
∧	2
∨	3
→	4
↔	5

13 of 41

Example 12 : How can the following English sentence be translated into a logical expression ?

“You can access the Internet from campus only if

you are a computer science major or you are not

a freshman. ”

Sol :

a : “You can access the Internet from campus.”

c : “You are a computer science major.”

f : “You are a freshman.”

∴ a only if ( c or ( ﹁ f ))

即 a → ( c ∨ ( ﹁ f ))

Ch1-13

Translating (轉換) English Sentences �into Logical Expression

14 of 41

Example 13 : 將下列語句翻譯成邏輯符號：�「如果你低於四英尺高，就不能搭乘雲霄飛車，除非你已經滿16歲。」
Sol : q : “你可以搭乘雲霄飛車”

r : “你低於四英尺高”

s : “你已經滿16歲”

故得到 ( r ∧ ﹁s ) → ﹁q

Ch1-14

15 of 41

Exercise 1-1

9. 令p, q分別代表下列命題：� p: 你開車時速超過65英里

q: 你收到超速罰單� 用p,q及適當的邏輯連接詞表達下列敘述句。� (a) 你開車時速沒有超過65英里� (b) 你開車時速超過65英里，但並沒有收到超速罰單� (c) 如果你開車時速超過65英里，就會收到超速罰單� (d) 你開車時速沒有超過65英里，就不會收到超速罰單� (f) 雖然你收到超速罰單，但是你開車時速沒有超過65英里� (g) 每當你收到超速罰單時，就表示你開車時速超過65英里

Ch1-15

16 of 41

Ch1-16

Def: A set of propositional expressions is consistent (一致) if there is an assignment of truth values to the variables in the expressions that makes each expression true.�

(一組由數個命題p,q,r等合成的命題，� 如：p∧¬q, � q⊕r, � p→r�若存在一組真值的給法，� 如設 p ≡ T, � q ≡ F, � r ≡ T�使所有的命題都可以為真，即稱為consistent)

就像聯立方程式，�存在一組解

17 of 41

Ch1-17

Sol: �Let p be “此診斷訊息儲存於緩衝記憶體 ”, � q be “此診斷訊息被重新傳送”

�題目的敘述等同於：p ∨ q, � ¬p, � p → q

要找出p,q的真值，使上面三個式子都為 T

要使 ¬p ≡ T, 則 p ≡ F，

此時要使 p ∨ q ≡ T, 則 q ≡ T,

此時p → q必為T, 故是 consistent

例15: 判斷下列系統規格是否一致 (consistent):�“此診斷訊息儲存於緩衝記憶體或被重新傳送.” �“此診斷訊息並未儲存於緩衝記憶體 ” �“如果此診斷訊息儲存於緩衝記憶體，則它將被重新傳送”

18 of 41

邏輯謎題

例18: 一座島嶼上有兩種住民：� 永遠說實話的武士及總是說謊話的騙子。� 假設你面對島上的兩個人A與B，� A說：「B是位武士」，� B說：「我們兩個人是不同種類的住民」，� 那麼他們分別為何？

Ch1-18

Sol:

假設 A 是武士

⇒ A 說實話

⇒ B 是武士

⇒與B說法矛盾

⇒ A 是騙子

A 是騙子

⇒ B也是騙子

⇒ 與B說法相符

⇒ 成立

19 of 41

Ch1-19

Exercise 1-1

63.一名偵探訪談了四位兇殺案的目擊證人。從證人的言詞，偵探得到下面的若干結論：� “如果管家說了實話，廚師就也說了實話” � “廚師和園丁不可能都說實話” � “園丁和雜物工不可能都說謊話”

“如果雜物工說了實話，廚師就說了謊話”

這名偵探能據此判定誰說實話誰說謊話嗎？

Sol：� p: 管家說實話� q: 廚師說實話 � r: 園丁說實話 � s: 雜物工說實話

20 of 41

1-2 Propositional Equivalences

Def 1: A compound proposition that is always true

is called a tautology. (真理)

A compound proposition that is always false

is called a contradiction. (矛盾)

Example 1 :

Ch1-20

p	﹁p	p ∨ ﹁p	p ∧ ﹁p
T	F
F	T

(等價命題)

p ∨ ﹁p is a tautology.

T

F

p ∧ ﹁p is a contradiction.

always � true

always � false

21 of 41

Ch1-21

Exercise 1-2

9. 利用真值表證明以下的條件句為恆真句(tautology)。� (a) (p ∧ q) → p� (b) p → (p ∨ q)� (c) ¬p → (p → q)

22 of 41

Ch1-22

Def 2: The propositions p and q that have the same truth values in all possible cases are called logically equivalent (等價). (p與q在所有情況的真值都相等)�The notation p ≡ q ( or p ⇔ q ) denotes that p and q are logically equivalent.

23 of 41

Example 2 : Show that ﹁( p ∨ q ) ≡ ﹁p ∧ ﹁q.

pf :

p	q
T	T
T	F
F	T
F	F

Ch1-23

p ∨ q

﹁p ∧ ﹁q

﹁p

﹁q

F

T

﹁( p ∨ q )

T

F

T

F

T

F

T

F

T

相等

故得證﹁( p ∨ q ) ≡ ﹁p ∧ ﹁q

24 of 41

Ch1-24

Example 3 : Show that ﹁ p ∨ q ≡ p → q.

pf :

p	q
T	T
T	F
F	T
F	F

p →q

﹁p

T

F

T

﹁p ∨ q

F

T

F

T

相等

故得證﹁ p ∨ q ≡ p → q

25 of 41

Ch1-25

Exercise 1-2

17. 利用真值表證明¬(p ↔ q) 和 p ↔ ¬q在邏輯上等價。

26 of 41

Ch1-26

Example 4 : Show that p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).

pf :

p	q	r
T	T	T
T	T	F
T	F	T
T	F	F
F	T	T
F	T	F
F	F	T
F	F	F

p ∨ r

q ∧ r

T

p ∨ (q ∧ r)

T

F

T

相等

故得證 p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

p ∨ q

(p ∨ q) ∧ (p ∨ r)

T

F

T

F

T

F

T

F

T

F

T

F

27 of 41

※ Some important logically equivalences (表 6, 表7)

(1) p ∨ q ≡ q ∨ p

(2) p ∧ q ≡ q ∧ p

(3) ( p ∨ q ) ∨ r ≡ p ∨ (q ∨ r )

(4) ( p ∧ q ) ∧ r ≡ p ∧ (q ∧ r )

(5) p ∨ ( q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r )

(6) p ∧ ( q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r )

(7) ﹁( p ∧ q ) ≡ ﹁p ∨ ﹁q

(8) ﹁( p ∨ q ) ≡ ﹁p ∧ ﹁q

(9) p ∨ ﹁p ≡ T

(10) p ∧ ﹁p ≡ F

(11) p → q ≡ ﹁p ∨ q (例3)

Ch1-27

commutative laws. 交換律

associative laws. 結合律

distributive laws 分配律

((5)、(6)的觀念類似於c × (a + b) = (c × a) + (c × b)

De Morgan’s laws 笛摩根定律

28 of 41

Example 7 : Show that ﹁( p ∨ (﹁p ∧ q )) ≡ ﹁p ∧ ﹁q

pf : (也可用真值表証)

﹁( p ∨ (﹁p ∧ q ) ) ≡ ﹁p ∧ ﹁ (﹁p ∧ q )

≡ ﹁p ∧ ( p ∨ ﹁q )

≡ (﹁p ∧ p ) ∨ ( ﹁p ∧ ﹁q )

≡ F ∨ ( ﹁p ∧ ﹁q )

≡ ﹁p ∧ ﹁q

Ch1-28

by (7)

by (6)

by (10)

by (8)

29 of 41

Example 8 : Show ( p ∧ q ) → (p ∨ q) is a tautology.

pf :

( p ∧ q ) → (p ∨ q) ≡ ﹁( p ∧ q ) ∨ (p ∨ q )

≡ ( ﹁p ∨ ﹁q ) ∨ (p ∨ q )

≡ ( ﹁p ∨ p ) ∨ ( ﹁q ∨ q )

≡ T ∨ T

≡ T

Ch1-29

By (3)

By (11)

By (7)

30 of 41

Ch1-30

Exercise 1-2

11. 不要利用真值表，證明以下的條件句為恆真句(tautology)。� (a) (p ∧ q) → p� (b) p → (p ∨ q)

公式：(1) p ∨ q ≡ q ∨ p

(2) p ∧ q ≡ q ∧ p

(3) ( p ∨ q ) ∨ r ≡ p ∨ (q ∨ r )

(4) ( p ∧ q ) ∧ r ≡ p ∧ (q ∧ r )

(5) p ∨ ( q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r )

(6) p ∧ ( q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r )

(7) ﹁( p ∧ q ) ≡ ﹁p ∨ ﹁q

(8) ﹁( p ∨ q ) ≡ ﹁p ∧ ﹁q

(9) p ∨ ﹁p ≡ T

(10) p ∧ ﹁p ≡ F

(11) p → q ≡ ﹁p ∨ q

31 of 41

1-3 Predicates and Quantifiers

目標 : 了解 ∀ 及 ∃ 符號
Def : The statement P(x) is said to be the value of the propositional function P at x. (函數式命題，包含變數)
ex :

P(x) : “ x is greater than 3 ” (P(x): x > 3)

Example 1:� 若P(x)代表 “x > 3”，請問P(2)及P(4)的真值為何？

Sol: � P(2) ≡ F� P(4) ≡ T

Ch1-31

變數

predicate(屬性)

屬性

數量詞

32 of 41

Ch1-32

命題中出現變數 x 時

the domain of x 指的是 x 的定義域，即範圍

Quantifiers : (數量詞，如 some，any，all 等)

∀ : universal quantifier (for all, for every, 所有的 )

∃ : existential quantifier (there exist, there is, for some, 存在)

Example 1:� 若Q(x,y)代表 “x = y + 3”，請問Q(1, 2)及Q(3, 0)的真值為何？

Sol: � Q(1, 2) ≡ F� Q(3, 0) ≡ T

量詞(quantifier)

33 of 41

表 1. Quantifiers

Example 9 : 令 Q(x)表示 “x < 2”，若 x ∈ R (實數)，

∀x Q(x) 的真值為何?

Sol :

並非所有的實數都小於2，� 如： 3 > 2，3是 ∀x Q(x) 的反例

∴ ∀x Q(x) 為假.

敘述	何時為真?	何時為假?
∀x P(x)	每個x都使P(x) 為真	存在一個x使 P(x) 為假
∃x P(x)	存在一個x使 P(x)為真	每個x都使P(x)為假

Ch1-33

34 of 41

Ch1-34

Example 11 : Let P(x) : x² < 10, when x ∈ Z⁺ (正整數), x ≤ 4.

What is the truth value of ∀x P(x) ?

Sol :

x ∈ {1, 2, 3, 4}

∴ 4² = 16 > 10

∴ ∀x P(x) is false.

Example 16 : Let P(x) : x² > 10, when x ∈ Z⁺, x ≤ 4.

What is the truth value of ∃x P(x) ?

Sol :

x ∈ {1, 2, 3, 4}

∴ 4² = 16 > 10

∴ ∃x P(x) is true.

35 of 41

Ch1-35

13. 若n的定義域包含所有整數，下列各項的真假值為何？� (a)  ∀ n (n + 1 > n)

(b) ∃n (2n = 3n)� (c) ∃n (n = −n)� (d) ∀n (n² ≥ n)

Exercise 1-3

11. 令P(x)代表 “x = x²”，x的定義域(論域)包含所有整數。� 下列各項的真假值為何？� (a) P(0)

(b) P(1)� (c) P(2) � (d) P(-1)

(e) ∃x P(x)� (f) ∀x P(x)

36 of 41

Ch1-36

15. 若x的定義域包含所有整數，下列各項的真假值為何？� (a)  ∀ n (n² ≥ 0)

(b) ∃n (n² = 2)� (c) ∀n (n² ≥ n)� (d) ∃n (n² < 0)

Exercise 1-3

37 of 41

表 2. 否定量詞

Example 21 : ∀x (x²> x) 及 ∃x (x²= 2) 的否定句分別為何?

Sol : ¬∀x (x² > x) ≡ ∃x ¬(x² > x) ≡ ∃x (x² ≤ x)

¬∃x (x²= 2) ≡ ∀x ¬(x²= 2) ≡ ∀x (x²≠ 2)

否定句	等值命題	何時為真？	何時為假?
¬∃x P(x)	∀x ¬P(x)	對所有x，P(x) 為假	存在某個x使 P(x) 為真
¬∀x P(x)	∃x ¬P(x)	存在某個x使 P(x) 為假	對所有x，P(x) 為真

Ch1-37

38 of 41

補充 : 習題52

“∃!” 表示存在且唯一，只存在唯一的一個

∃!x P(x) 表示 “存在唯一的一個x 使P(x)為真”

Example : What is the truth values of the statements

(a) ∃! x ( x²= 1 )

(b) ∃! x ( x + 3 = 2x )

where x ∈ Z.

Ans : (a) 1² = 1, (−1)²=1 ⇒ False

(b) x=3 is the only solution ⇒ True

Ch1-38

39 of 41

1-4 Nested Quantifiers(群組量詞)

例: ∀x ∃y (x + y = 0 )
表1. Quantifications of Two Variables.

敘述句	何時為真?	何時為假?
∀x ∀y P(x,y) ∀y ∀x P(x,y)	每一組x,y都使P(x,y)為真	存在一組x,y，使得P(x,y)為假
∀x ∃y P(x,y)	對每一個x , 都存在一個y使得 P(x,y)為真	存在一個x，使得每一個y都讓 P(x,y)為假
∃x ∀y P(x,y)	存在一個x，使得每一個y都讓 P(x,y)為真	對每一個x , 都存在一個y使得 P(x,y)為假
∃x ∃y P(x,y) ∃y ∃x P(x,y)	存在一組x,y，使得P(x,y)為真	每一組x,y都使P(x,y)為假

Ch1-39

40 of 41

Ch1-40

Example : What is the truth values of the statements

(a) ∀x ∀y (x + y ≥ 0), x,y ∈ N (自然數)

(b) ∀x ∀y (xy = 0), x,y ∈ Z

(c) ∀x ∃y (x + y = 0), x,y ∈ Z

(d) ∀x ∃y (xy = −1), x,y ∈ Z

(e) ∃x ∀y (xy = 0), x,y ∈ Z

(f) ∃x ∀y (x + y = 0), x,y ∈ Z

(g) ∃x ∃y (xy = 0), x,y ∈ Z

(h) ∃x ∃y (x + y = ½), x,y ∈ Z

⇒ T

⇒ F

⇒ T

⇒ F

⇒ T

⇒ F

⇒ T

⇒ F

41 of 41

Ch1-41

27. 若所有變數的定義域皆為整數，下列各項的真假值為何？� (a)  ∀n ∃m (n² < m)

(b) ∃n ∀m (n < m²)� (c) ∀n ∃m (n + m = 0)� (d) ∃n ∀m (nm = m)� (e) ∃n ∃m (n²+ m² = 5)� (f) ∃n ∃m (n²+ m² = 6)� (g) ∃n ∃m (n+ m = 4 ∧ n – m = 1)� (h) ∃n ∃m (n+ m = 4 ∧ n – m = 2)� (i) ∀n ∀m ∃p (p = (m+ n)/2)�

Exercise 1-4