[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.