[Part 1] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles Quick review of propositional logic

In preparation for a series of posts in which I will discuss Raymond Smullyan's knights and knaves puzzles and how to solve them using logic, this post aims to review a few basics of propositional logic. Note that I will most likely not need first-order (predicate) logic in this series.

Propositional logic represents statements and logical arguments using:

• atomic propositions represented by (propositional) variables that are either true or false, and
• logical connectives, such as:
• AND: we'll use $\&$ to denote conjunction
• OR: we'll use $|$ for disjunction
• NOT: we'll use $-$ for negation
• IF-THEN: we'll use $\rightarrow$ for implication or conditional
• IF-AND-ONLY-IF: we'll use $\leftrightarrow$ for biconditional

If needed, you can review logical connectives and their truth tables.

When building proofs, we will use the following well-known logical equivalences (among others).

---

Logical equivalence #1

---

Given any two propositions $P_1$ and $P_2$, the following two formulas are equivalent:

$P_1 \leftrightarrow P_2$

$(P_1 \rightarrow P_2)\ \&\ (P_2 \rightarrow P_1)$

In other words, a biconditional is equivalent to the conjunction of two conditionals. 

Informal justification

The fact that 

$P_1$ if and only if $P_2$ 

holds is equivalent to the fact that both 

$P_1$ if $P_2$ 

and 

$P_1$ only if $P_2$ 

hold.

Note that:

$P_1$ only if $P_2$

is represented by

$P_1 \rightarrow P_2$

and

$P_1$ if $P_2$

is represented by

$P_2 \rightarrow P_1$

Formal justification

Build the truth tables for both formulas $P_1 \leftrightarrow P_2$ and $(P_1 \rightarrow P_2)\ \&\ (P_2 \rightarrow P_1)$ and check that they have the same truth value in each and every row.

---

Logical equivalence #2

---

Given any two propositions $P_1$ and $P_2$, the following two formulas are equivalent:

$P_1 \rightarrow P_2$

$- P_1\ |\ P_2$

In other words, a conditional is equivalent to a disjunction. 

Justification

The only way to make the formula

$P_1 \rightarrow P_2$

false, is to make $P_1$ true and $P_2$ false.

This is also true of the second formula

$-P_1\ |\ P_2$

Build the truth table for both formulas and check that they have the same truth value in each and every row.

In part 2 of this series, we will use the propositional logic formalism to represent and solve our first knights and knaves problem.