Propositional Logic

Definition: Propositional Logic

Propositional logic / Sentential calculus / Sentential logic / Statement logic / Zeroth-order logic is the study of zeroth-order formal languages.

Definition: Zeroth-Order Language

A zeroth-order language is a formal language ${\mathcal{L}}_0$ whose alphabet $\Sigma$ consists of:

• a set of symbols $S_1,S_2,\dots$ known as atomic formulas / primitive symbols / atomic sentences / propositional variables;
• a set of symbols $\{\neg ,\wedge ,\vee ,⟹,⟺\}$ known as (logical) connectives / propositional connectives / logical operators. These are called negation ($\neg$), conjunction / (logical) and ($\wedge$), disjunction / (logical) or ($\vee$), implication $(⟹)$ and equivalence ($⟺$).
• a set of symbols $\{(,)\}$ called parentheses.

The words of ${\mathcal{L}}_0$ are called well-formed formulas.

We define the formula-building operations for any two well-formed formulas $\alpha ,\beta \in {\mathcal{L}}_0$:

• ${\mathcal{E}}_{\neg }(\alpha )=(\neg \alpha )$;
• ${\mathcal{E}}_{\wedge }(\alpha ,\beta )=(\alpha \wedge \beta )$;
• ${\mathcal{E}}_{\vee }(\alpha ,\beta )=(\alpha \vee \beta )$;
• ${\mathcal{E}}_{⟹}(\alpha ,\beta )=\alpha ⟹\beta$;
• ${\mathcal{E}}_{⟺}(\alpha ,\beta )=\alpha ⟺\beta$;

We define the well-formed formulas of ${\mathcal{L}}_0$ to be precisely:

• All propositional variables $S_1,S_2,\dots$.
• All expressions $\epsilon$ for which there exists a finite sequence of expressions ${\epsilon }_1,\dots ,{\epsilon }_n$ such that for each $i\le n$ we have at least one of the following:
  • ${\epsilon }_i$ is a propositional variable;
  • ${\epsilon }_i={\mathcal{E}}_{\neg }({\epsilon }_j)$ for some $j<i$;
  • ${\epsilon }_i={\mathcal{E}}_{\square }({\epsilon }_j,{\epsilon }_k)$ for some $j<i$ and $k<i$, where $\square$ is one of the logical connectives $\wedge$, $\vee$, $⟹$, $⟺$.

Binary Logic

Given a zeroth-order language, we are most commonly interested in binary truth assignments $v:{\mathcal{L}}_0\to \{T,F\}$. We call $T$ truth and $F$ falsity. We further impose the following conditions on $v$. Given any well-formed formulas $\alpha ,\beta$:

• parentheses extraction:

$$v((\alpha ))=v(\alpha )$$

$(\alpha )$	$\alpha$
$T$	$T$
$F$	$F$

• truth assignment of negation:

$$v(\neg \alpha )=\{\begin{array}{l}T\text{if }v(\alpha )=F\\ F\text{otherwise}\end{array}$$

$\alpha$	$\neg \alpha$
$T$	$F$
$F$	$T$

• truth assignment of conjunction:

$$v(\alpha \wedge \beta )=\{\begin{array}{l}T\text{if }v(\alpha )=T\text{ and }v(\beta )=T\\ F\text{otherwise}\end{array}$$

$\alpha$	$\beta$	$\alpha \wedge \beta$
$F$	$F$	$F$
$T$	$F$	$F$
$F$	$T$	$F$
$T$	$T$	$T$

• truth assignment of disjunction:

$$v(\alpha \vee \beta )=\{\begin{array}{l}T\text{if }v(\alpha )=T\text{ or }v(\beta )=T\text{ or both}\\ F\text{otherwise}\end{array}$$

$\alpha$	$\beta$	$\alpha \vee \beta$
$F$	$F$	$F$
$T$	$F$	$T$
$F$	$T$	$T$
$T$	$T$	$T$

• truth assignment of implication:

$$v(\alpha ⟹\beta )=\{\begin{array}{l}F\text{if }v(\alpha )=T\text{ and }v(\beta )=F\\ T\text{otherwise}\end{array}$$

$\alpha$	$\beta$	$\alpha ⟹\beta$
$F$	$F$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$T$	$T$	$T$

• truth assignment of equivalence:

$$v(\alpha ⟹\beta )=\{\begin{array}{l}T\text{if }v(\alpha )=v(\beta )\\ F\text{otherwise}\end{array}$$

$\alpha$	$\beta$	$\alpha ⟹\beta$
$F$	$F$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$T$	$T$	$T$

Theorem: Equivalent Statements of Implication

Given any two well-formed formulas $A$ and $B$, we have:

$$v(A⟹B)=v(\neg B⟹\neg A)=v(\neg A\vee B)$$

PROOF

TODO