Chapter 01 Logic and Proofs 逻辑与证明

Part 01

Covering1.1 ~ 1.3

1. Proposition Logic 命题逻辑

Knowledge Frame 知识框架

Proposition 命题

Connectives 联结 (命题之间的关联)

Negation (NOT) 否定

Conjunction (AND) 合取

Disjunction (OR) 析取

Exclusive Or (XOR) 异或

Implication (if-then) 蕴含

Converse, Contrapositive, and Inverse 逆命题、逆否命题、否命题

Biconditional (if and only if) 双条件

Precedence 优先级

Truth Table 真值表 (一个工具)

Equivalent Propositions 等价命题

Bit Operations 位运算

1.1. Proposition 命题

A proposition is a declarative sentence that is either true or false, but not both.

命题是一个陈述语句，它或真或假，但不能既真又假。

1.1.1. 不是命题的几种典型反例

command 命令 (e.g. Read it loud!)
question 疑问 (e.g. What time is it?)
paradox 悖论 (e.g. This statement is false.)
equation with unknowns 含有未知数的等式 (e.g. x + y = z)

使用字母来表示命题变元(propositional variables)

1.2. Connectives 联结

1.2.1. Negation (NOT) 否定

The negation of a proposition p : ¬p (not p)

1.2.2. Conjunction (AND) 合取

The conjunction of propositions p and q : p ∧ q (p and q)

Note: The sun is shining , but it is raining.

自然语言和逻辑语言是有区别的，不要混为一谈。这一点在之后还会出现！

1.2.3. Disjunction (OR) 析取

The disjunction of propositions p and q : p ∨ q (p or q)

1.2.4. Exclusive Or (XOR) 异或

the exclusive or of p and q : p ⊕ q

(True when exactly one of p and q is true.)

Note: ∨ vs. ⊕

Inclusive or: ∨

Exclusive or: ⊕

1.2.5. Implication (if-then) 蕴含

Implication or conditional statement : p → q (if p, then q)

Note: 再次注意，自然语言和逻辑语言是有区别的，生活中的逻辑也不要强行带入

e.g. If the moon is made of green cheese, then I have more money than Bill Gates. 这句话的真值为T

Different Ways of Expressing p → q

大部分直接读读就知道了，但是有两个很坑

p only if q
q unless ¬p

思考它们的最佳办法就是带入一个实例

e.g. Mary will eat the fruit only if the fruit is apple.

p : Mary will eat the fruit

q : the fruit is apple

if (Mary will eat the fruit), then (the fruit is apple)

if p, then q

in English, not unless = only if

1.2.6. Converse, Contrapositive, and Inverse 逆命题、逆否命题、否命题

p → q	Implication
q → p	Converse
¬q → ¬p	Contrapositive
¬p → ¬q	Inverse

1.2.7. Biconditional (if and only if) 双条件

the biconditional proposition : p ↔ q (p if and only if q, p iff q, vice versa)

1.2.8. Precedence 优先级

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

1.3. Truth Table 真值表

真值表是研究命题逻辑的重要工具

在构建真值表时，其实就是在手工模拟计算机枚举的过程

不难，仅以一题为例

An island has two kinds of inhabitants, knights, who always tell the truth, and knaves, who always lie. You go to the island and meet A and B.

A says “B is a knight.”

B says “The two of us are of opposite types.”

What are the types of A and B?

Let p: "A is a knight"

q: "B is a knight"

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

So the answer is that both A and B are knaves.

1.4. Equivalent Propositions 等价命题

Two propositions are equivalent if they always have the same truth value.

How many rows are there in a truth table with npropositional variables?

$2^n$

With n propositional variables, we can construct ( ) distinct (i.e., not equivalent) propositions

$2^{2^n}$

稍加解释一下，有n个命题变量时，真值表就有了 $2^n$ 种情况，而每一个命题对于每一种情况，它都可以有T和F两个值（注意，如果两个命题在这 $2^n$ 个情况之下真值完全相同，则它们被视为完全等价的两个命题，即在这里被算为一个）那么此时，就有了 $2^{2^n}$ 种不同的真值组合，对应 $2^{2^n}$ 种不同的命题

1.5. Bit Operations 位运算

Bit: a symbol with two possible values , namely, 0 and 1.
Boolean variable: one whose value is either true or false.
A bit string is a sequence of zero or more bits
Bitwise operations are bit operations extended to bit strings. （按位X）

2. Propositional Equivalences 命题等价式

2.1. Tautologies, Contradictions, and Contingencies 永真、永假、可能式

2.1.1. Tautologies 永真（重言式）

A tautology is a proposition which is always true.

e.g. p ∨ ¬p

2.1.2. Contradictions 永假（矛盾式）

A contradiction is a proposition which is always false.

e.g. p ∧ ¬p

2.1.3. Contingencies 可能式

A contingency is a proposition which is neither a tautology nor a contradiction, such as p

2.2. Logical Equivalences 逻辑等价式

The compound propositions p and q are called logically equivalent if p ↔ q is a tautology.

2.2.1. Notation 记号

p ⇔ q or p ≡ q

Remark

The symbol ≡ is not a logical connective, and p ≡ q is not a compound proposition but rather is the statement that p ↔ q is a tautology.

2.3. Laws 一些等价定律

2.3.1. De Morgan’s Laws 德·摩根律

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

The Extended Version of De Morgan’s Laws 德·摩根律拓展形式

$\neg(p_1\wedge p_2\wedge ...\wedge p_n)\equiv \neg p_1\vee \neg p_2\vee ...\vee \neg p_n$

$\neg(p_1\vee p_2\vee ...\vee p_n)\equiv \neg p_1\wedge \neg p_2 \wedge ...\wedge \neg p_n$

We will sometimes use the notation $\bigvee_{j = 1}^{n} p_j$ for $p_1 \vee p_2 \vee ... \vee p_n$ and $\bigwedge_{j = 1}^n p_j$ for $p_1 \wedge p_2 \wedge ... \wedge p_n$ . Using this notation, the extended version of De Morgan's laws can be written concisely as $\lnot (\bigvee_{j = 1}^n p_j) \equiv \bigwedge_{j = 1}^n p_j$ and $\lnot (\bigwedge_{j = 1}^n p_j) \equiv \bigvee_{j = 1}^n \lnot p_j$ . (Methods for proving these identities will be given in Section 5.1)

2.3.2. Key Logical Equivalences 重要的逻辑等价式

Name	Equivalences
Identity laws	$p \wedge T \equiv p, p \vee F \equiv p$
Domination laws	$p \vee T \equiv T, p \wedge F \equiv F$
Idempotent laws	$p \vee p \equiv p, p \wedge p \equiv p$
Double negation law	$\lnot \lnot p \equiv p$
Commutative laws	$p \vee q \equiv q \vee p, p \wedge q \equiv q \wedge p$
Associative laws	$(p \vee q) \vee r \equiv p \vee (q \vee r), (p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$
Distributive laws	$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r), p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$
De Morgan's laws	$\lnot (p \wedge q) \equiv \lnot p \vee \lnot q, \lnot (p \vee q) \equiv \lnot p \wedge \lnot q$

2.4. Constructing New Logical Equivalences 构建新的逻辑等价式

2.4.1. Using Truth Tables

Easy but time-consuming when the number of variables is large

2.4.2. Using already-proved equivalences

Just like what we do in Algebra

推理逻辑的基础——传递性

$A_1\equiv A_2$

$A_2\equiv A_3$

……

$A_{n-1}\equiv A_n$

Samples of Equivalence Proofs

2.5. Propositional Satisfiability 命题的可满足性

A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true. (成真赋值)

When no such assignments exist, the compound proposition is unsatisfiable.

Application

Sudoku 数独详见书本

2.6. Others 其他

2.6.1. Other Logical Operators

Sheffer stroke | （Sheffer 竖）

p | q ≡ ¬(p ∧ q) NAND 与非

Peirce arrow ↓ （Peirce 箭头）

p ↓ q ≡ ¬(p ∨ q) NOR 或非

p ↓ p ≡ ¬p

(p ↓ q) ↓ (p ↓ q) ≡ p ∨ q

2.6.2. The Dual of a Compound Proposition 对偶

2.6.3. Functionally Complete Collection of Logical Operators 功能完备的逻辑连接词集合

A collection of logical operators is called functionally complete if every compound proposition is logically equivalent to a compound proposition involving only these logical operators.

e.g. {¬, ∧, ∨, →, ↔}, {¬, ∧, ∨}, {¬, ∧}, {¬, ∨}, {|}, {↓} are all functionally complete operators