First-Order Logic

Quantifiers

Important

Predicates are propositions with variables

e.g. $P (x, y) = x + 2 = y$

When there is a variable, we need to specify the domain

Important

Domain of a variable is the set of all values that may be substituted in place of the variable

The truth of quantified statement depends on the domain

Universal quantifier: $\forall x \in A$ means for all $x$ in $A$
- $\forall x \in Z^{+}, P (x) : P (1) \land P (2) \land \dots$
Existential quantifier: $\exists x \in A$ means there exists some $x$ in $A$
- $\exists x \in Z^{+}, P (x) : P (1) \lor P (2) \lor \dots$

If an integer $n$ is greater than 2, then the equation $a^{n} + b^{n} = c^{n}$ has no solution in positive integers $a, b, c$

Find domain: $\forall a, b, c \in Z^{+}, (n \in Z) \land (n > 2)$
Find condition: $a^{n} + b^{n} \neq c^{n}$
Convert to $p \to q$ format: $\forall a, b, c \in Z^{+} . (n \in Z) \land (n > 2) \to a^{n} + b^{n} \neq c^{n}$
Simplify: $\forall a, b, c \in Z^{+} . (n \leq 2) \lor (n \notin Z) \lor (a^{n} + b^{n} \neq c^{n})$

Every positive even number at least 6 is a sum of two primes
Suppose given predicates $prime (x), even (x)$

Find domain: $\forall n \in Z^{+} . [even (n) \land (n \geq 6)]$
Find condition: $\exists p, q \in Z . prime (p) \land prime (q) \land (p + q = n)$
Convert to $p \to q$ format: $\forall n \in Z^{+} . [even (n) \land (n \geq 6)] \to [\exists p, q \in Z . prime (p) \land prime (q) \land (p + q = n)]$
Simplify: $\forall n \in Z^{+} . odd (n) \lor (n < 6) \lor [\exists p, q \in Z . prime (p) \land prime (q) \land (p + q = n)]$

\begin{aligned} \forall n \in Z^{+} . [even (n) \land (n \geq 6)] \to [\exists p, q \in Z . prime (p) \land prime (q) \land (p + q = n)] \\ \equiv & \forall n \in Z^{+} . \neg [even (n) \land (n \geq 6)] \lor [\exists p, q \in Z . \dots] \\ \equiv & \forall n \in Z^{+} . [odd (n) \lor (n < 6)] \lor [\exists p, q \in Z . prime (p) \land prime (q) \land (p + q = n)] \\ \equiv & \forall n \in Z^{+} . odd (n) \lor (n < 6) \lor [\exists p, q \in Z . prime (p) \land prime (q) \land (p + q = n)] \end{aligned}

\neg \forall x P (x) \equiv \exists x \neg P (x)

e.g. Not everyone likes football = There exists someone who doesn’t like football.

Proof

Assume the domain is ${1, 2, 3}$

\begin{aligned} \neg \forall x P (x) & = \neg (P (1) \land P (2) \land P (3)) \\ = \neg P (1) \lor \neg P (2) \lor \neg P (3) \\ = \exists x \neg P (x) \\ = R . H . S . \end{aligned}

\neg \exists x P (x) \equiv \forall x \neg P (x)

e.g. Not exists a plant that can fly = every plant cannot fly

维度	命题 A (普遍量化优先)	命题 B (存在量化优先)
自然语言	“防病毒软件杀所有计算机病毒” (Each virus has a killer)	“存在一个杀软能干掉所有病毒” (One killer kills everything)
逻辑公式	$\forall v \cdot \exists a \cdot kills (a, v)$	$\exists a \cdot \forall v \cdot kills (a, v)$
约束范围	弱约束。 ( $\exists$ 在外层受 $\forall$ 支配) 只要对当前 $v$ 能找到 $a$ 就行。	强约束。 ( $\forall$ 在内层被 $\exists$ 锁死) 选定后的 $a$ 必须对所有 $v$ 有效。

Hence, order of quantifiers is important.

Propositional logic: A technology is no matter what the truth value of $A$ and $B$ are.
- 对 $A, B$ 的所有真假组合都为真
First-order logic: A tautology is no matter what the domain of $x, y, z$ or $P, Q$ are
- 对任意论域 domain + 任意谓词含义 predicate 都为真

Important

A quantified argument is valid if the conclusion is true whenever the assumptions are true

\begin{array}{r} \forall x, P (x) \\ ∴ P (a) \end{array}

如果所有 $x$ 都满足 $P$ ，那么随便挑一个具体的 $a$ ，它当然也满足 $P$ 。

\begin{array}{r} \forall x, P (x) \to Q (x) \\ P (a) \\ ∴ Q (a) \end{array}

如果所有 $x ： P (x) \Rightarrow Q (x)$ ，而某个 $a$ 满足 $P$ ，那么 $a$ 一定满足 $Q$ 。

\begin{array}{r} \forall x, P (x) \to Q (x) \\ \neg Q (a) \\ \neg P (a) \end{array}

如果所有 $x ： P (x) \Rightarrow Q (x)$ ，而某个 $a$ 不满足 $Q$ ，那么 $a$ 一定不满足 $P$ 。

When $c$ is independent of $A$ ,

\begin{array}{r} A \to R (c) \\ ∴ A \to \forall x . R (x) \end{array}

If $R (c)$ is true for an arbitrary $c$ , then the statement is true for all values.