1. Getting started with propositional logic

Getting started with prop. logic

Covered in FC1:

• Proposition
• 2. Logical connectives

Well-formed formulae

The set of all well-formed formulae is inductively defined as: ?

• All propositional symbols are atomic formulae.
• If $A$ is a formula, so is $\neg A$.
• If $A$ and $B$ are formulae, then do is any combination of: $(A\wedge B),(A\vee B),(A\to B),(A⟺B)$
• Nothing else is a formula.

Link to original

Link to original

2. Reading and evaluating formulae

Precendence of propositional symbols: $\neg ,\wedge ,\vee ,\to ,⟺$

Interpretation

An interpretation or valuation $v$ is a function that assigns a truth-value to every propositional symbol $P$, hence $v(P) \in \{ 0, 1 \}$.

• If $v(P)=1$, then $P$ is true under the interpretation $v$.
• If $v(P)=0$, then $P$ is false under the interpretation $v$. An interpretation is extended to all well-formed formula using truth-tables.

As oppossed to FC1, we include an extra column for for interpretation. For example, take $p\wedge q$, we generate the following truth table:

interpretation	$p$	$q$	$p\wedge q$
$v_0$	F	F	F
$v_1$	F	T	F
$v_2$	T	F	F
$v_3$	T	T	T

Link to original

Link to original

3. Types of formula and logical equivalence

Types of formula

• Tautology
• Contradiction
• Contingency

Logical equivalence

Covered in FC1, Logically equivalent.

Logic Puzzle

Island of TuFa has two tribes, the Tu’s who always tell the truth, and the Fa’s who always lie.

A traveller encountered three resident of TuFa, $P$, $Q$, and $R$, and each made a statement:

• $P$ says ”$Q$ and $R$ tell the truth $⟺$ $R$ tells the truth”
• $Q$ says “If $P$ and $R$ tell the truth, then it is not the case that if $Q$ and $R$ tell the truth, then $P$ tells the truth.”
• $R$ says ”$Q$ is lying $⟺$ $P$ or $Q$ is telling the truth.”

Determine to which tribe each of $P$, $Q$, and $R$ belongs.

Let $p$, $q$ and $r$ be whether $P$, $Q$ and $R$ are telling the truth, respectively.

Formalising these statements:

• $P$: $q\wedge r⟺r$
• $Q$: $p\wedge r\to \neg (q\wedge r\to p)$
• $R$: $\neg q⟺(p\vee q)$

We know that:

• $A:p⟺(q\wedge r⟺r)$
• $B:q⟺(p\wedge r\to \neg (q\wedge r\to p))$
• $C:r⟺(\neg q⟺(p\vee q))$

We can consider all of these in a truth table:

interpretation	$p$	$q$	$r$	$A$	$B$	$C$	$A\wedge B\wedge C$
$v_0$	0	0	0	0	0	1	0
$v_1$	0	0	1	1	0	0	0
$v_2$	0	1	0	0	1	1	0
$v_3$	0	1	1	0	1	0	0
$v_4$	1	0	0	1	0	0	0
$v_5$	1	0	1	0	1	1	0
$v_6$	1	1	0	1	1	1	1
$v_7$	1	1	1	1	0	0	0

$v_6$ is the only interpretation that makes the three statements, $A$, $B$, and $C$ true. Hence $P$ and $Q$ must belong to Tu, and $R$ to Fa.

Link to original