# # 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…