逻辑是一切思考的基础。

# Propositional logic(zeroth order logic)

Propositional logic does NOT deal with non-logical objects, predicates or quantifiers.

For example, the following simple axiom system is an instance of propositional logic:

$\mathcal{L}(A,\Omega,Z,I)$:

• $A=\{p,q,r,s,t,...\}$ serves to represent logic propositions.

• $\Omega=\{\neg,\rightarrow\}$ is the set of logic operators.

• $Z$ is the set of transformation rule. Here it contains only one rule named modus ponens:

  $$p\rightarrow q,p\vdash q$$

• $I$ is the set of axioms. The axioms are all substitution instances of:

  $$\begin{aligned} &\vdash p\rightarrow(q\rightarrow p)\\ &\vdash (p\rightarrow(q\rightarrow r))\rightarrow((p\rightarrow q)\rightarrow(p\rightarrow r))\\ &\vdash (\neg p\rightarrow\neg q)\rightarrow(q\rightarrow p) \end{aligned}$$

Example: the proof of $\neg\neg p\vdash p$:

• Lemma 1. $\vdash p\rightarrow p$.

  Proof.

  (1) By axiom 1, substitute $q$ with $p\rightarrow p$, we have

  $$p\rightarrow((p\rightarrow p)\rightarrow p)$$

  (2) By axiom 2, substitute $q$ with $p\rightarrow p$ and substitute $r$ with $p$:

  $$(p\rightarrow((p\rightarrow p)\rightarrow p)\rightarrow((p\rightarrow(p\rightarrow p))\rightarrow (p\rightarrow p))$$

  (3) By Modus ponens and (1), (2):

  $$(p\rightarrow(p\rightarrow p))\rightarrow(p\rightarrow p)$$

  (4) By axiom 1, substitute $q$ with $p$:

  $$p\rightarrow(p\rightarrow p)$$

  (5) By Modus ponens and (3), (4):

  $$p\rightarrow p$$

• Lemma 2. $p\rightarrow q,q\rightarrow r\vdash p\rightarrow r$.

  Proof.

  (1) $p\rightarrow q$ premise

  (2) $q\rightarrow r$ premise

  (3) By axiom 1,

  $$(q\rightarrow r)\rightarrow(p\rightarrow(q\rightarrow r))$$

  (4) By Modus ponens and (2), (3):

  $$p\rightarrow (q\rightarrow r)$$

  (5) By axiom 2,

  $$(p\rightarrow(q\rightarrow r))\rightarrow((p\rightarrow q)\rightarrow(p\rightarrow r))$$

  (6) By Modus ponens and (4), (5):

  $$(p\rightarrow q)\rightarrow(p\rightarrow r)$$

  (7) By Modus ponens and (1), (6):

  $$p\rightarrow r$$

• Lemma 3. $(q\rightarrow r)\rightarrow((p\rightarrow q)\rightarrow(p\rightarrow r))$.

  Proof.

  (1) By axiom 1, substitute $p$ with $(p\rightarrow (q\rightarrow r))\rightarrow ((p\rightarrow q)\rightarrow (p\rightarrow r))$,

  $$((p\rightarrow (q\rightarrow r))\rightarrow ((p\rightarrow q)\rightarrow (p\rightarrow r)))\rightarrow ([q\rightarrow r]\rightarrow ((p\rightarrow (q\rightarrow r))\rightarrow ((p\rightarrow q)\rightarrow (p\rightarrow r))))$$

  (2) By axiom 2,

  $$(p\rightarrow (q\rightarrow r))\rightarrow ((p\rightarrow q)\rightarrow (p\rightarrow r))$$

  (3) By Modus ponens and (1), (2),

  $$(q\rightarrow r)\rightarrow ((p\rightarrow (q\rightarrow r))\rightarrow ((p\rightarrow q)\rightarrow (p\rightarrow r)))$$

  (4) By axiom 2,

  $$[(q\rightarrow r)\rightarrow ((p\rightarrow (q\rightarrow r))\rightarrow ((p\rightarrow q)\rightarrow (p\rightarrow r)))]\rightarrow[(q\rightarrow r)\rightarrow(p\rightarrow(q\rightarrow r))\rightarrow ((q\rightarrow r)\rightarrow ((p\rightarrow q)\rightarrow(p\rightarrow r)))]$$

  (5) By Modus ponens and (3) (4),

  $$[(q\rightarrow r)\rightarrow (p\rightarrow(q\rightarrow r))]\rightarrow ((q\rightarrow r)\rightarrow((p\rightarrow q)\rightarrow(p\rightarrow r)))$$

  (6) By axiom 1,

  $$(q\rightarrow r)\rightarrow(p\rightarrow(q\rightarrow r))$$

  (7) By Modus ponens and (5), (6),

  $$(q\rightarrow r)\rightarrow((p\rightarrow q)\rightarrow(p\rightarrow r))$$

• Lemma 4. $\vdash p\rightarrow((p\rightarrow q)\rightarrow q)$.

  Proof.

  (1) By axiom 3,

  $$((p\rightarrow q)\rightarrow(p\rightarrow q))\rightarrow(((p\rightarrow q)\rightarrow p)\rightarrow((p\rightarrow q)\rightarrow q))$$

  (2) By Lemma 1,

  $$(p\rightarrow q)\rightarrow(p\rightarrow q)$$

  (3) By Modus ponens and (1) (2),

  $$((p\rightarrow q)\rightarrow p)\rightarrow((p\rightarrow q)\rightarrow q)$$

  (4) By Lemma 3,

  $$(((p\rightarrow q)\rightarrow p)\rightarrow((p\rightarrow q)\rightarrow q))\rightarrow ((p\rightarrow ((p\rightarrow q)\rightarrow p))\rightarrow (p\rightarrow ((p\rightarrow q)\rightarrow q)))$$

  (5) By Modus ponens and (3) (4),

  $$(p\rightarrow((p\rightarrow q)\rightarrow p))\rightarrow (p\rightarrow ((p\rightarrow q)\rightarrow q))$$

  (6) By axiom 1,

  $$p\rightarrow ((p\rightarrow q)\rightarrow p)$$

  (7) By Modus ponens, (5) (6),

  $$p\rightarrow((p\rightarrow q)\rightarrow q)$$

• Proposition $\vdash \neg\neg p\rightarrow p$.

  Proof.

  (1) By axiom 1, $\phi::=(r\rightarrow (s\rightarrow t))$.

  (2) By axiom 3,

  $$(\neg\neg\phi\rightarrow \neg\neg p)\rightarrow(\neg p\rightarrow \neg \phi)$$

  (3) By axiom 3,

  $$(\neg p\rightarrow\neg \phi)\rightarrow(\phi\rightarrow p)$$

  (4) By axiom 1,

  $$\neg\neg p\rightarrow(\neg\neg\phi\rightarrow\neg\neg p)$$

  (5) By Modus ponens, (3)(4),

  $$\neg\neg p\rightarrow(\phi\rightarrow p)$$

  (6) By Lemma 4,

  $$\phi\rightarrow((\phi\rightarrow p)\rightarrow p)$$

  (7) By axiom 1,

  $$\phi$$

  (8) By Modus ponens, (6), (7),

  $$(\phi\rightarrow p)\rightarrow p$$

  (9) By Lemma 2, (5), (8),

  $$\neg\neg p\rightarrow p$$

$\square$.

# First-order logic

Consider such an example, there are two propositions:

1. John is male.
2. Mike is male.

In propositional logic, we could only to describe with two symbols, that is:

$$p=\text{John is male}\\ q=\text{Mike is male}$$

But “is male” seems to be duplicated part, so we develop a new logic system with predicate and variables.

Let $P(x)=\text{x is male}$, and the two propositions could be interpreted as $P(\text{John})$ and $P(\text{Mike})$.

---

First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as “Socrates is a man”, one can have expressions in the form “there exists x such that x is Socrates and x is a man”, where “there exists*”* is a quantifier, while x is a variable.[1] This distinguishes it from propositional logic, which does not use quantifiers or relations;[2] in this sense, propositional logic is the foundation of first-order logic.

For example, the following formula is a proposition of first order logic

$$\forall x\forall y(P(f(x)))\rightarrow\neg(P(x)\rightarrow Q(f(x),x,z)))$$

# Second/Higher order logic

First-order logic can quantify over individuals, but not over properties. But in Higher order logic, the following proposition is legitimate:

$$\forall x\forall P(P(x))$$

while it’s forbidden in first order logic to $\forall P$ since $P$ is a predicate.

In higher order logic, you could almost quantifier over any thing, that is

$$\forall f,\exists f$$

where $f$ is a function, or predicate, or variables…