1.1 Propositional Logic
【例子】 Which of these sentences are propositions? What are the truth values of those that are propositions?
- Do not pass go.
- What time is it?
- There are no black flies in Maine.
- 4 + x = 5.
【例子】 What is the negation of each of these propositions?
- Abby sent more than 100 text messages every day.
命题的否定是：Abby sent fewer than 101 text messages yesterday
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-
- $p \to q$
- $p \leftrightarrow q$
- $\neg p \or (p \and q)$
- If I bought a lottery ticket this week, then I won the million dollar jackpot on Friday.
- I bought a lottery ticket this week if and only if I won the million dollar jackpot on Friday.
- Either I did not buy a lottery ticket this week, or else I did buy one and won the million dollar jackpot on
记住 $\to$ 翻译为 if...then...，$\leftrightarrow $ 翻译为 if and only if
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
$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
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
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).
- No ducks are willing to waltz.
- All my poultry are ducks.
- $\forall x (P(x) \to \neg S(x))$ 注意：这里容易错误地写成：$\forall x P(x) \and \neg S(x)$
- $\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.]
- $∃xP (x) ∨ ∃xQ(x) ∨ A,$ where A is a proposition not involving any quantifiers.
- $∃xP (x) → ∃xQ(x)$
- $\exists x (P(x) \or Q(x) \or A)$
- $∀x∃y(¬P(x) ∨ Q(y))$ 容易错解为： $\exists x (P(x)\to Q(x))$