18 Rules of Inference in SL

Eight Implication Rules

The $\rightarrow$ rules: Modus Ponens and Modus Tollens

MP:

\begin{align*} x→y, x : y \end{align*}

MT:

\begin{align*} x→y, \neg y: \neg x \end{align*}

 

The $\wedge$ rules: Conjunction and Simplification

Conj:

\begin{align*} x, y : x \wedge y \end{align*}

Simp:

\begin{align*} x \wedge y: x \\ x \wedge y: y \end{align*}

 

The $\vee$ rules: Addition and Disjunctive Syllogism

Add:

\begin{align*} x : x \vee y \end{align*}

DS:

\begin{align*} x \vee y , \neg x : y \\ x \vee y , \neg y : x \end{align*}

 

The double $\rightarrow$ rules: Hypothetical Syllogism and Constructive Dilemma

HS:

\begin{align*} x→y, y→z : x→z \end{align*}

CD:

\begin{align*} w \vee x, w→y, x→z : y \vee z \end{align*}

 

Ten Valid Equivalences

The double-colon symbol ::, when placed between two statements, this symbol means that the two statements are equivalent — that is, you can substitute one for the other whenever needed.

 

Double Negation (DN)

\begin{align*} x :: \neg \neg x \end{align*}

Contraposition (Contra)

\begin{align*} x \rightarrow y :: \neg y \rightarrow \neg x \end{align*}

Implication (Impl)

When you know that the statement x → y is true, you know that either x is false (that is, $\neg x$ is true) or that y is true. In other words, you know that the statement $\neg x \vee y$ is true.

\begin{align*} x \rightarrow y :: \neg x \vee y \end{align*}

 

x	y	$x \rightarrow y$	$\neg x \vee y$
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

Example:

\begin{align*} P \rightarrow Q, P \vee R: Q \vee R \end{align*}

Proof:

\begin{align*} &1 \quad P \rightarrow Q \tag P \\ &2 \quad P \vee R \tag P \\ &3 \quad \neg P \vee Q \tag{1 Impl} \\ &4 \quad \neg Q \rightarrow \neg P \tag{1 Contra} \\ &5 \quad \neg P \rightarrow R \tag{2 Impl} \\ &6 \quad \neg R \rightarrow P \tag{2 Contra} \\ &7 \quad \neg Q \rightarrow R \tag{4,5 HS} \\ &8 \quad Q \vee R \tag{7 Impl} \end{align*}

Exportation (Exp)

\begin{align*} x\rightarrow (y\rightarrow z)::(x\wedge y)\rightarrow z \end{align*}

Example:

$(P\wedge Q)\rightarrow R,\neg R \vee S,P:Q \rightarrow S$

Proof:

\begin{align*} &1 \quad (P\wedge Q)\rightarrow R \tag P \\ &2 \quad \neg R \vee S \tag P \\ &3 \quad p \tag{1 Impl} \\ &4 \quad P \rightarrow (Q \rightarrow R) \tag{1 Exp} \\ &5\quad Q \rightarrow R \tag{3,4 MP} \\ &6\quad R \rightarrow S \tag{2 Impl} \\ &7\quad Q \rightarrow S \tag{5,6 HS} \end{align*}

Commutation (Comm)

\begin{align*} x \wedge y ::y \wedge x \\ x \vee y::y \vee x \end{align*}

Example:

\begin{align*} P \wedge ( \neg Q \rightarrow R):(R \vee Q) \wedge P \end{align*}

Proof:

\begin{align*} &1 \quad P \wedge ( \neg Q \rightarrow R) \tag P \\ &2 \quad P \tag {1 Simp} \\ &3 \quad \neg Q \rightarrow R \tag{1 Simp} \\ &4 \quad Q \vee R \tag{3 Impl} \\ &5\quad R \vee Q \tag{4 Comm} \\ &6\quad (R \vee Q ) \wedge P \tag{5 Conj} \end{align*}

 

Association (Assoc)

\begin{align*} (x \wedge y ) \wedge z:: x \wedge ( y\wedge z) \\ (x \vee y )\vee z:: x \vee ( y\vee z) \end{align*}

Example:

\begin{align*} (P \rightarrow Q) \vee R : Q\vee (R \vee \neg P) \end{align*}

Proof:

\begin{align*} &1 \quad (P \rightarrow Q) \tag P \\ &2 \quad ( \neg P \vee Q) \vee R \tag { 1 Impl } \\ &3 \quad (Q \vee \neg P) \vee R \tag{ 2 Comm } \\ &4 \quad Q \vee ( \neg P \vee R) \tag{ 3 Assoc } \\ &5\quad Q \vee (R \vee \neg P) \tag{ 4 Comm } \end{align*}

 

Distribution (Dist)

I have a pet and it’s either a cat or a dog. $x \wedge ( y \vee z)$

Either I have a pet and it’s a cat or I have a pet and it’s a dog. $(x \wedge y) \vee( x \wedge z)$

I have to take either organic chemistry or both botany and zoology. $x \vee ( y \wedge z)$

I have to take either organic chemistry or botany, and I also have to take either organic chemistry or zoology. $(x \vee y) \wedge( x \vee z)$

\begin{align*} x \wedge ( y \vee z) :: (x \wedge y) \vee( x \wedge z) \\ x \vee ( y \wedge z) :: (x \vee y) \wedge( x \vee z) \end{align*}

 

Example:

\begin{align*} Q \vee R, \neg ( P \wedge Q), P: R \end{align*}

Proof:

\begin{align*} &1 \quad Q \vee R \tag P \\ &2 \quad \neg ( P \wedge Q) \tag { P } \\ &3 \quad P \tag{ P } \\ &4 \quad P \wedge (Q \vee R ) \tag{ 1,3 Conj } \\ &5\quad (P \wedge Q)\vee ( P \wedge R) \tag{ 4 Dist } \\ &6\quad P \wedge R \tag{ 2,5 DS } \\ &7\quad R \tag{6 Simp} \end{align*}

DeMorgan’s Theorem (DeM)

\begin{align*} \neg (x\wedge y) :: \neg x \vee \neg y \\ \neg (x\vee y) :: \neg x \wedge \neg y \end{align*}

 

It’s not true that I’m both rich and famous. $\neg (x\wedge y)$

Either I’m not rich or I’m not famous. $\neg x \vee \neg y$

Jack is neither a doctor nor a lawyer. $\neg (x\vee y) $

Jack isn’t a doctor and he isn’t a lawyer. $\neg x \wedge \neg y$

 

Example:

\begin{align*} Q \vee R, \neg (P\wedge Q), P:R \end{align*}

Proof:

\begin{align*} &1 \quad Q \vee R \tag p \\ &2 \quad \neg (P\wedge Q) \tag { p } \\ &3 \quad P \tag{ p } \\ &4 \quad \neg P \vee \neg Q \tag{2 DeM } \\ &5\quad \neg Q \tag{3,4 DS} \\ &6\quad R \tag{ 1,5 DS } \end{align*}

Tautology (Taut)

\begin{align*} x\wedge x ::x \\ x \vee x::x \end{align*}

Example:

\begin{align*} P \rightarrow \neg P: \neg P \end{align*}

Proof:

\begin{align*} &1 \quad P \rightarrow \neg P \tag P \\ &2 \quad \neg P \vee \neg P \tag {1 Impl } \\ &3 \quad \neg P \tag{ 2 Taut } \end{align*}

Equivalence (Equiv)

\begin{align*} x \leftrightarrow y &::(x \rightarrow y ) \wedge (y\rightarrow x) \\ x \leftrightarrow y &::(x\wedge y)\vee ( \neg x \wedge \neg y) \end{align*}

Example 1:

\begin{align*} P \leftrightarrow (Q\wedge R), Q: P\vee \neg R \end{align*}

Proof:

\begin{align*} &1 \quad P \leftrightarrow (Q\wedge R) \tag P \\ &2 \quad Q \tag { P } \\ &3 \quad (P \rightarrow (Q \wedge R)) \wedge ((Q \wedge R)\rightarrow P) \tag{ 1 Equiv } \\ &4 \quad (P \wedge (Q \wedge R)) \vee ( \neg P \wedge \neg (Q \wedge R)) \tag{ 1 Equiv } \\ &5\quad P \rightarrow (Q \wedge R) \tag{ 3 Simp } \\ &6\quad (Q \wedge R)\rightarrow P \tag{ 3 Simp } \\ &7 \quad Q \rightarrow ( R\rightarrow P) \tag {6 Exp} \\ &8 \quad R \rightarrow P \tag {2,7 MP } \\ &9 \quad \neg R \vee P \tag{ 8 Impl } \\ &10 \quad P \vee \neg R \tag{9 Comm } \end{align*}

 

Example 2:

\begin{align*} P \leftrightarrow Q, R\rightarrow (P \vee Q):R\rightarrow (P \wedge Q) \end{align*}

Proof:

\begin{align*} &1 \quad P \leftrightarrow Q \tag {P} \\ &2 \quad R\rightarrow (P \vee Q) \tag { P } \\ &3 \quad (P \rightarrow Q) \wedge (Q \rightarrow P) \tag{ 1 Equiv } \\ &4 \quad (P \wedge Q) \vee (\neg P \rightarrow \neg Q) \tag{ 1 Equiv } \\ &5\quad P \rightarrow Q \tag{3 Simp} \\ &6\quad Q \rightarrow P \tag{3 Simp } \\ &7 \quad \neg (P \wedge Q) \rightarrow ( \neg P \wedge \neg Q) \tag {4 Impl} \\ &8 \quad \neg (\neg P \wedge \neg Q) \rightarrow (P \wedge Q) \tag { 7 Contra } \\ &9 \quad (P\vee Q) \rightarrow (P \wedge Q) \tag{ 8 DeM } \\ &10 \quad R \rightarrow (P \wedge Q) \tag{ 2,9 HS } \end{align*}