Propositional Logic

Introduction 引入

Turing's Halting Problem 停机问题

所有计算机程序只有两个结局——

停止：程序顺利执行完毕
死循环

graph LR
a("program(input)") --> c(Halt)
a --> b(Infinite loop)

这里有两个程序：

def countdown(n):
	while n > 0:
		n -= 1

这个程序 countdown 很容易看出最终是会 halt 的，因为它不断减少 $n$ 的值，直到 $n <= 0$ 便停止。

def mystep(n):
	while n != 1:
		if n%2 == 0:
			n = n//2 # 偶数整除2
		else:
			n = 3*n + 1 # 奇数乘 3 加 1

第二个程序 mystep 便无法直接判断是否会 halt，因为 $n$ 不一定会出现 1 的值。

问题： 世界上是否存在一个程序可以检测所输入的程序是 Halt 还是 Infinite loop

Proof

假如这个程序 LoopChecker 真的存在

def LoopChecker(program, inputs):
	if ...:
		return "Halt"
	else:
		return "Infinite loop"

那我们可以创建一个程序 trouble ，把 LoopChecker 的结果反过来，即如果程序是 halt 的，我就让它死循环，如果是 infinite loop 的，我就中断它。这个就是 proof by contradiction。

def trouble(program, inputs):
	if LoopChecker(program, inputs) == "Halt":
		while True: # 死循环
			... 
	else: 
		return # 中断
trouble(trouble, trouble) # 自相矛盾

Logic and Basic Operators

Statement / Proposition

Definition

A statement is a sentence that is either True or False.

Examples:

$2 + 2 = 4$ is a statement
$x + y > 0$ is not a statement
$x^{2} + y^{2} = z^{2}$ is not a statement

Tip

不提供 $x, y$ 则无法判断 True or False

Logic Operators

Logic operators are used to construct new statements from old statements

NOT ( $\neg$ )
AND ( $\land$ )
OR ( $\lor$ )

P	Q	P $\land$ Q	P $\lor$ Q
True	True	True	True
True	False	False	True
False	True	False	True
False	False	False	False

We can define logic operators on three or more statements, e.g.

\overset{―}{p \land q} \lor r

Note

$\overset{―}{}$ 是 NOT 的另外一种写法

\overset{―}{p \land q} \lor r \equiv \neg (p \land q) \lor r

Logic Operators Construction

We can construct new operator from AND, OR, NOT

Exclusive-or (XOR) 异或

When $p = q$ , return False
When $p \neq q$ , return True

p \oplus q \equiv (p \lor q) \land \neg (p \land q)

$p$	$q$	$p \lor q$	$\neg (p \land q)$	$p \oplus q \equiv (p \lor q) \land \neg (p \land q)$
True	True	True	False	False
True	False	True	True	True
False	True	True	True	True
False	False	False	True	False

$(p \lor q) \land \neg (p \land q)$ 只是其中一种定义，只要你所写的定义返回的值跟 $\oplus$ 一致 (logical equivalence)，便是 $\oplus$ 的定义。

Important

Logical equivalence: Two statement have the same truth table

\begin{aligned} p \oplus q & \equiv (p \land \neg q) \lor (\neg p \land q) \\ \equiv \neg (p \land q) \land \neg (\neg p \land \neg q) \end{aligned}

Writing Logical Formula for a Truth Table

看 True 的行，撰写 logic statement，之后用 OR 连接
看 False 的行，撰写 logic statement 后用 AND 连接

Idea 1: Focus on True Row (DNF)

p	q	r	output	Logic statement
T	T	T	F
T	T	F	T	$(p \land q \land \neg r)$
T	F	T	T	$\lor (p \land \neg q \land r)$
T	F	F	F
F	T	T	T	$\lor (\neg p \land q \land r)$
F	T	F	T	$\lor (\neg p \land q \land \neg r)$
F	F	T	T	$\lor (\neg p \land \neg q \land r)$
F	F	F	F

Hence, the logic statement is

(p \land q \land \neg r) \lor (p \land \neg q \land r) \lor (\neg p \land q \land r) \lor (\neg p \land q \land \neg r) \lor (\neg p \land \neg q \land r)

Idea 2: Focus on False Row (CNF)

For each False row, the logic statement must be False only for that specific inputs.

p	q	r	output	Logic statement
T	T	T	F	$\neg (p \land q \land r)$
T	T	F	T
T	F	T	T
T	F	F	F	$\land \neg (p \land \neg q \land \neg r)$
F	T	T	T
F	T	F	T
F	F	T	T
F	F	F	F	$\land \neg (\neg p \land \neg q \land \neg r)$

The logic statement is

\neg (p \land q \land r) \land \neg (p \land \neg q \land \neg r) \land \neg (\neg p \land \neg q \land \neg r)

The logic statement of #Idea 1 Focus on True Row and #Idea 2 Focus on False Row are logically equivalent.

Logical Rules

$t$ 指 tautology 永真，即 TRUE
$c$ 指 contradiction 永假，即 FALSE

Logical Rules	Explanation	Case 1	Case 2
Commutative laws（交换律）	两边可互换	$p \land q \equiv q \land p$	$p \lor q \equiv q \lor p$
Associative laws（结合律）	只用同一种运算符时，括号不影响结果	$(p \land q) \land r \equiv p \land (q \land r)$	$(p \lor q) \lor r \equiv p \lor (q \lor r)$
Distributive laws（分配律）	等同于乘法分配律 $a (b + c) = a b + a c$	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$	$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
Identity laws（同一律）	当 $t$ 在 AND、 $c$ 在 OR 时，结果保持不变	$p \land t \equiv p$	$p \lor c \equiv p$
Negation laws（否定律）	自己和自己取反：OR 必真、AND 必假	$p \lor \neg p \equiv t$	$p \land \neg p \equiv c$
Double negative law（双重否定律）	负负得正	$\neg (\neg p) \equiv p$
Idempotent laws（幂等律）	重复不改变结果	$p \land p \equiv p$	$p \lor p \equiv p$
Universal bound laws（domination／范围律）	OR 遇到 $t$ 为恒真； AND 遇到 $c$ 为恒假	$p \lor t \equiv t$	$p \land c \equiv c$
De Morgan's laws（德摩根律）	展开后 OR、AND 调转	$\neg (p \land q) \equiv \neg p \lor \neg q$	$\neg (p \lor q) \equiv \neg p \land \neg q$
Absorption laws（吸收律）	括号内的结果无关大雅	$p \lor (p \land q) \equiv p$	$p \land (p \lor q) \equiv p$
Negations of t and c（永真／永假的否定）	$t$ 和 $c$ 是相反的	$\neg t \equiv c$	$\neg c \equiv t$

Proof of Absorption law

\begin{aligned} L . H . S . & \equiv p \lor (p \land q) \\ \equiv (p \land t) \lor (p \land q) \\ \equiv p \land (t \lor q) \\ \equiv p \land t \\ \equiv p \\ \equiv R . H . S . \end{aligned}

Simplify Statement

Exercise generated by AI

Simplify $(q \land p) \land \neg p$

\begin{aligned} (q \land p) \land \neg p & \equiv q \land (p \land \neg p) \\ \equiv q \land c \\ \equiv c \end{aligned}

Simplify $(p \land q) \lor (p \land \neg q)$

\begin{aligned} (p \land q) \lor (p \land \neg q) & \equiv p \land (q \lor \neg q) \\ \equiv p \land t \\ \equiv p \end{aligned}

Simplify $(p \land q) \lor (p \land q \land r)$

\begin{aligned} (p \land q) \lor (p \land q \land r) & \equiv (p \land q) \lor [(p \land q) \land r] \\ \equiv (p \land q) \end{aligned}

Simplify $\neg (\neg p \lor q) \land (p \lor q)$

\begin{aligned} \neg (\neg p \lor q) \land (p \lor q) & \equiv (p \land \neg q) \land (p \lor q) \\ \equiv \neg q \land [p \land (p \lor q)] \\ \equiv \neg q \land p \end{aligned}

Simplify $\neg (\neg (p \lor q) \land \neg q)$

\begin{aligned} \neg (\neg (p \lor q) \land \neg q) & \equiv (p \lor q) \lor q \\ \equiv (p \lor q) \lor (q \lor q) \\ \equiv (p \lor q) \lor q \\ \equiv p \lor q \end{aligned}

Simplify $(p \land q) \lor (p \land \neg q) \lor (\neg p \land q)$

\begin{aligned} (p \land q) \lor (p \land \neg q) \lor (\neg p \land q) & \equiv p \land (q \lor \neg q) \lor (\neg p \land q) \\ \equiv p \land t \lor (\neg p \land q) \\ \equiv p \lor (\neg p \land q) \\ \equiv (p \lor \neg p) \land (p \lor q) \\ \equiv t \land (p \lor q) \\ \equiv p \lor q \end{aligned}

Conditional Statement

IF-Then

\underset{hypothesis}{\underset{⏟}{p}} \to \underset{conclusion}{\underset{⏟}{q}}

It means

If $p$ , then $q$ ; OR
$p$ implies $q$

$P$	$Q$	$P \to Q$
T	T	T
T	F	F
F	T	T
F	F	T

只有当前提 hypothesis $P$ 为 TRUE ，且结论 $Q$ 是 FALSE 时， $P \to Q$ 才会是 FALSE
如果前提 $P$ 本身为 FALSE 时，无论结论 $Q$ 如何，都是 TRUE

Logical Formula for If-Then

我们可以用 #Writing Logical Formula for a Truth Table 的方式推导 If 的 logical formula

Idea 1: Focus on TRUE

$P$	$Q$	$P \to Q$	Logical statement
T	T	T	$(P \land Q)$
T	F	F
F	T	T	$\lor (\neg P \land Q)$
F	F	T	$\lor (\neg P \land \neg Q)$

The logical formula is

\begin{aligned} (P \land Q) \lor (\neg P \land Q) \lor (\neg P \land \neg Q) & \equiv Q \land \underset{t}{\underset{⏟}{(P \lor \neg P)}} \lor (\neg P \land \neg Q) \\ \equiv Q \lor (\neg P \land \neg Q) \\ \equiv (Q \lor \neg P) \land \underset{t}{\underset{⏟}{(Q \lor \neg Q)}} \\ \equiv \neg P \lor Q \end{aligned}

这个 logical formula 可以很明白的说出 if 的关系，即只要 $Q$ 是 TRUE， $P \to Q$ 必然为 TRUE。

Negation of If-Then

如果要否定 $P \to Q$ ，即 $\neg (P \to Q)$ ，我们要给出 $P$ 为 TRUE，而 $Q$ 为 FALSE 的例子
Proof

\begin{aligned} \neg (P \to Q) & \equiv \neg (\neg P \lor Q) \\ \equiv P \land \neg Q \end{aligned}

Note

$\neg (P \to Q)$ 表示 $P \to Q$ 为 False。
要证明 $P \to Q$ 不成立，必须给出一个情况： $P$ 为 True，但 $Q$ 为 False。

Contrapositive 逆否命题

The contrapositive of $p \to q$ is $\neg q \to \neg p$
Proof

\begin{aligned} p \to q & \equiv \neg p \lor q \\ \equiv q \lor \neg p \\ \equiv \neg q \to \neg p \end{aligned}

有时候直接证 $p \to q$ 比较难，但证 $\neg q \to \neg p$ 反而容易。

If and Only If (IFF)

\begin{aligned} p ⟺ q & \equiv (p \to q) \land (q \to p) \\ \equiv (p \to q) \land (\neg p \to \neg q) \end{aligned}

$P$	$Q$	$P \leftrightarrow Q$	$P \to Q$	$\neg Q \to \neg P$
T	T	T	T	T
T	F	F	F	F
F	T	F	T	T
F	F	T	T	T

Arguments

Argument is a sequence of statements
用数学符号表示为：

\underset{Assumptions / Premises}{\underset{⏟}{P_{1} \land P_{2} \land \dots \land P_{n}}} \to \underset{Conclusion}{\underset{⏟}{Q}}

Argument is valid if whenever all the assumption are true, then the conclusion is true.

Example

If it is raining, then I need an umbrella.

It is raining.
$∴$ I need an umbrella

Note

Argument 只关心当假设 assumption 为 TRUE 时，结论 conclusion 是否为 TRUE
而并不关心事件 / statement 是 TRUE 还是 FALSE，即 assumption 可以为 False 且 conclusion 也变成 False。

Modus Ponens 肯定前件

If $p$ then $q$ , and $p$ is true, then $q$ is true.
用数学公式写：

\begin{array}{r} p \to q \\ p \\ ∴ q \end{array}

Equivalently, $(p \to q) \land p \to q$

Note

单独一个字母出现在代表为 TRUE，如 $p, \neg q$ 是指 $p, \neg q$ 是 TRUE.

在拉丁文中，Modus Ponens 意思是 method of affirming 肯定法

Modus Tollens

\begin{array}{r} p \to q \\ \neg q \\ ∴ \neg p \end{array}

Equivalently, $(p \to q) \land \neg q \to \neg p$

Example

If typhoon, then class cancels.

Class does not cancel
$∴$ No typhoon

在拉丁文中，Modus Tollens 意思是 method of denying 拒绝法

Invalid Arguments

\begin{array}{r} p \to q \\ q \\ ∴ p \end{array}

这个例子就是弄混了 #IF-Then 的关系， $p \to q$ 并不代表 $q \to p$ 。

\begin{array}{r} p \to q \\ \neg p \\ ∴ \neg q \end{array}

这个在 #IF-Then 中有详细说明（参见 #^b05206）

如果要证明 argument 是 invalid，只需要提出一个反例即可。

Valid argument 并不代表是 true conclusion，例如如果 argument 的 assumption 是 FALSE 的，那 conclusion 就不一定是 TRUE。

Contradiction

\begin{array}{r} \neg p \to c \\ ∴ p \end{array}

If assumption is true, then the conclusion is true.

Generalization

\begin{array}{r} p \\ ∴ p \lor q \\ q \\ ∴ p \lor q \end{array}

Specialization

\begin{array}{r} p \land q \\ ∴ p \\ p \land q \\ ∴ q \end{array}

Elimination

\begin{array}{r} p \lor q \\ \neg q \\ ∴ p \\ p \lor q \\ \neg p \\ ∴ q \end{array}

Transitivity

\begin{aligned} p & \to q \\ q & \to r \\ ∴ p & \to r \end{aligned}

Caution

如果第二行 $q$ 和 $r$ 交换，即 $r \to q$ ， argument 便不成立

Proof by Division into Cases

\begin{aligned} p & \lor q \\ p & \to r \\ q & \to r \\ ∴ & r \end{aligned}