Site Overlay

# 离散数学：题型和易错点总结 / Chapter 1: The Foundations:Logic and Proofs（上）

## 1.1 Propositional Logic

### 判断是否是命题

【例子】 Which of these sentences are propositions? What are the truth values of those that are propositions?

1. Do not pass go.
2. What time is it?
3. There are no black flies in Maine.
4. 4 + x = 5.

【分析与解答】

1. 不是
2. 不是
3. 是。假命题。
4. 不是命题。不能含有未知数，这样命题的真假就取决于未知数的值。

### 求命题的否定

【例子】 What is the negation of each of these propositions?

• Abby sent more than 100 text messages every day.

【分析与解答】

### 逻辑联结词的运用

【例子】

Let p and q be the propositions

• p : I bought a lottery ticket this week
• q : I won the million dollar jackpot.

Express each of these propositions as an English sen-
tence.

1. $p \to q$
2. $p \leftrightarrow q$
3. $\neg p \or (p \and q)$

【分析与解答】

1. If I bought a lottery ticket this week, then I won the million dollar jackpot on Friday.
2. I bought a lottery ticket this week if and only if I won the million dollar jackpot on Friday.
3. Either I did not buy a lottery ticket this week, or else I did buy one and won the million dollar jackpot on
Friday.

## 1.2 Applications of Propositional Logic

### 用逻辑命题表述自然语言

【例子】

You can see the movie only if you are over 18 years old or you have the permission of a parent.

Express your an swer in terms of m: “You can see the movie,” e: “You are
over 18 years old,” and p: “You have the permission of a
parent.”

【分析与解答】

$m \to (e \or p)$

• only if; only when 表示的是只有当 p 成立，q 才会成立，也即 $p\to q$

• if and only if; iff 当且仅当，双向箭头。$p \leftrightarrow q$

• unless, if not 除非，相当于或的关系。q 除非 p，$\neg p \to q$$p \or q ### 实例推理题 【例子】 Four friends have been identified as suspects for an unauthorized access into a computer system. They have made statements to the investigating authorities. Alice said “Carlos did it.” John said “I did not do it.” Carlos said “Diana did it.” Diana said “Carlos lied when he said that I did it.” a) If the authorities also know that exactly one of the four suspects is telling the truth, who did it? Explain your reasoning. b) If the authorities also know that exactly one is lying, who did it? Explain your reasoning. 【分析与解答】 这种题用假设法判断各个分支即可。 Note that Diana’s statement is merely that she didn’t do it. a) John did it. There are four cases to consider. If Alice is the sole truth-teller, then Carlos did it; but this means that John is telling the truth, a contradiction. If John is the sole truth-teller, then Diana must be lying, so she did it, but then Carlos is telling the truth, a contradiction. If Carlos is the sole truth-teller, then Diana did it, but that makes John truthful, again a contradiction. So the only possibility is that Diana is the sole truth-teller. This means that John is lying when he denied it, so he did it. Note that in this case both Alice and Carlos are indeed lying. b) Again there are four cases to consider. Since Carlos and Diana are making contradictory statements, the liar must be one of them (we could have used this approach in part (a) as well). Therefore Alice is telling the truth, so Carlos did it. Note that John and Diana are telling the ruth as well here, and it is Carlos who is lying. ## 1.3 Propositional Equivalences ### 逻辑等价的类型 等价关系 关系名称 p\and T\equiv p \\ p\or F\equiv p Identity laws 恒等律 p\or T\equiv T \\p\and F\equiv F Domination laws 支配律 p\or p\equiv p \\p\and p\equiv p Idempotent laws 幂等律 \neg (\neg p)\equiv p Double negation laws 双非律 p\or q\equiv q\or p \\ p\and q\equiv q\and p Commutative laws 交换律 (p\or q)\or r\equiv p\or (q\or r) \\ (p\and q)\and r\equiv p\and (q\and r) Associative laws 结合律 p\or (q\and r)\equiv (p\or q)\and (p\or r) \\ p\and (q\or r)\equiv (p\and q)\or (p\and r) Distributive laws 分配律 \neg (p\and q)\equiv \neg p\or \neg q \\\neg (p\or q)\equiv \neg p\and \neg q De Morgan's laws 德摩根律 p\or (p\and q)\equiv p \\p\and (p\or q)\equiv p Absorption laws 吸收律 p\or \neg p\equiv T\\ p\and \neg p\equiv F Negation laws 否定律 别记，会晕的。多做题。 【例子】 Use De Morgan’s laws to find the negation of each of the following statements. • Kwame will take a job in industry or go to graduate school. 【分析与解答】 • Kwame will not take a job in industry and will not go to graduate school. 写过代码人对德摩根律的应该很熟练吧 ### 证明逻辑等价（入门） 【例子】 Show that ¬(¬p) and p are logically equivalent 【分析与解答】 There are two cases. If p is true, then ¬(¬p) is the negation of a false proposition, hence true. Similarly, if p is false, then ¬(¬p) is also false. Therefore the two propositions are logically equivalent. (这里是证明 Double negation laws) #### 使用真值表证明 【例子】 Use truth tables to verify the associative laws (p ∧ q) ∧ r ≡ p ∧ (q ∧ r). 这种题穷举即可。对于带有逻辑联结词的，分解为最小单位的 p$$q$$p ? q 进行穷举 ## 1.4 Predicates and Quantifiers ### Domain 内等价形式转换问题 【例子】 Suppose that the domain of the propositional function P(x) consists of −5, −3, −1, 1, 3, and 5. Express these statements without using quantifiers, instead using only negations, disjunctions, and conjunctions. • ∃x(¬P(x)) ∧ ∀x((x < 0) → P (x)) 【分析与解答】 ∃x(¬P(x)) 是在说，存在 x 使得 \neg P(x) 为真，也就是 \neg P(-5) 为真或者 \neg P(-3) 为真……写下来就是 \neg P(-5) \vee \neg P(-3) \vee \neg P(-1) \vee \neg P(1) \vee \neg P(3) \vee \neg P(5)$$∀x((x < 0) → P (x)$ 的话，就是说 $P(-5) \wedge P(-3) \wedge P(-1)$ ，所以答案是

$$(\neg P(-5) \vee \neg P(-3) \vee \neg P(-1) \vee \neg P(1) \vee \neg P(3) \vee \neg P(5)) \wedge(P(-5) \wedge P(-3) \wedge P(-1))$$

$$(¬P(1) ∨ ¬P(3) ∨ ¬P(5)) ∧ (P(−1) ∧ P(−3) ∧ P(−5))$$

### 命题函数的自然语言实例化

【例子】

Let P(x), Q(x), R(x), and S(x) be the statements “x is a duck,” “x is one of my poultry,” “x is an officer,” and “x is willing to waltz,” respectively. Express each of
these statements using quantifiers; logical connectives; and P(x), Q(x), R(x), and S(x).

1. No ducks are willing to waltz.
2. All my poultry are ducks.

【分析与解答】

1. $\forall x (P(x) \to \neg S(x))$ 注意：这里容易错误地写成：$\forall x P(x) \and \neg S(x)$
2. $\forall x (Q(x) \to P(x))$

## 1.5 Nested Quantifiers

### 转写为前束范式

【例子】

Put these statements in prenex normal form. [Hint: Use logical equivalence from Tables 6 and 7 in Section 1.3, Table 2 in Section 1.4, Example 19 in Section 1.4, Exercises 45 and 46 in Section 1.4, and Exercises 48 and 49.]

1. $∃xP (x) ∨ ∃xQ(x) ∨ A,$ where A is a proposition not involving any quantifiers.
2. $∃xP (x) → ∃xQ(x)$

【分析与解答】

1. $\exists x (P(x) \or Q(x) \or A)$
2. $∀x∃y(¬P(x) ∨ Q(y))$ 容易错解为： $\exists x (P(x)\to Q(x))$