Propositional Logic

Propositional Logic is a Formal System – a Language (syntax) and a set of Deduction Rules (semantics) – capable of expressing “propositional logic”.

It is one of the more primitive / basic systems for logic.

Unlike First-order Logic, there is one fixed language¹ for propositional logic, i.e., authors do not generally define custom objects (in addition to those below) to use within formulas.

Syntax

Alphabet

See Formal Language & Grammar for the formal significance of an alphabet.

• Propositional Variables – atomic statements
  a countable set $\mathcal{P} = \{p, q, r, \dots\}$
• Logical Connectives – logical relations
  $\lnot$, $\land$, $\lor$, $\to$, $\leftrightarrow$
• Parentheses – syntactic grouping
  $($ and $)$

Well-Formed Formulas

Aka., Sentential Formulas, or the Language in Formal Language & Grammar

The set of Well-Formed Formulas (WFF)s, $\mathcal{L}$, is defined inductively:

1. Base: $\mathcal{P} \subset \mathcal{L}$.
2. Negation: $\varphi \in \mathcal{L} \implies \neg \varphi \in \mathcal{L}$.
3. Binary Connectives: $\varphi, \psi \in \mathcal{L} \implies (\varphi \land \psi), (\varphi \lor \psi), (\varphi \to \psi), (\varphi \leftrightarrow \psi) \in \mathcal{L}$
4. Closure: No other strings are in $\mathcal{L}$.

where $\varphi$ and $\psi$ represent strings, and everything else are strings of symbols as-is.

In actual writing, some parentheses are omitted for brevity.
To maintain unambiguity in how unparenthesized sub-formulas are parsed, the connectives are assigned precedence levels. In descending order:

1. $\lnot$ (highest)
2. $\land$ and $\lor$
3. $\to$ and $\leftrightarrow$ (lowest)

The binary connectives are left associative, while negation is right associative.

Semantics

Truth Assignment

Aka. Valuation

A truth assignment for a formula maps each proposition variable in the formula to a truth value, then evaluates the formula.

I.e., a truth assignment is a function
$$\rho: \mathcal{P} \to \{ \bot, \top \}$$

where $\top$ represents truth and $\bot$ represents falsity.

Then, $\rho$ is inductively defined for all sentential formula.
For $\varphi, \psi \in \mathcal{L}$,
$$\begin{align*} \rho(\lnot \varphi) &\iff \lnot \rho(\varphi) \\ \rho(\varphi \land \psi) &\iff \rho(\varphi) \land \rho(\psi) \\ \rho(\varphi \lor \psi) &\iff \rho(\varphi) \lor \rho(\psi) \\ \rho(\varphi \to \psi) &\iff \lnot \rho(\varphi) \lor \rho(\psi) \\ \rho(\varphi \leftrightarrow \psi) &\iff \rho(\varphi) \leftrightarrow \rho(\psi) \\ \end{align*}$$

where the following (very well-formatted) truth tables define the logical connectives. Note that IMPLIES, $\to$, is defined in terms of $\lnot$ and $\lor$.

NOT:

$\lnot$
$\top$	$\bot$
$\bot$	$\top$

AND:

$\land$	$\top$	$\bot$
$\top$	$\top$	$\bot$
$\bot$	$\bot$	$\bot$

OR:

$\lor$	$\top$	$\bot$
$\top$	$\top$	$\top$
$\bot$	$\top$	$\bot$

EQUIV:

$\leftrightarrow$	$\top$	$\bot$
$\top$	$\top$	$\bot$
$\bot$	$\bot$	$\top$

$\space$

Logical Classification:

• Tautology: $\varphi$ is a tautology if $\rho(\varphi)$ is true for every truth assignment $\rho$.
• Contradiction: $\varphi$ is a contradiction if $\rho(\varphi)$ is false for every truth assignment $\rho$.
• Contingency: $\varphi$ is contingent if it is neither a tautology nor a contradiction.

Rules of Inference

By defining the behavior of (a sufficient subset of)² the logical connectives like above, the logic is already complete.
Alternatively, Rules of Inference (axioms) are defined, from which the intuitive behavior of the logical connectives are inferred.

The minimal set as Rules of Inference is just Modus Ponens (plus some form of definition for negation or NOT).

Modus Ponens (MP):

$$\frac{\varphi,\quad \varphi \to \psi}{\psi}$$

I.e., “if $\varphi$ is true, and it is asserted $\varphi \to \psi$, then $\psi$ must be true”.

Other common Axioms

Hilbert-style:

1. $\varphi \to (\psi \to \varphi)$
2. $(\varphi \to (\psi \to \chi)) \to ((\varphi \to \psi) \to (\varphi \to \chi))$
3. $(\neg \varphi \to \neg \psi) \to ((\neg \varphi \to \psi) \to \varphi)$

There are many axiomatic systems for propositional logic. As long as they all establish propositional logic, they’re all equivalent (obviously?!).

Meta-Theoretical Properties

These aren’t specific to propositional logic, but rather of any logic in general.

• Soundness
  If $\vdash \varphi$ (i.e., $\varphi$ is derivable), then $\varphi$ is a tautology.
• Completeness
  If $\varphi$ is a tautology, then $\vdash \varphi$.
• Decidability
  A truth table construction provides an effective decision procedure for determining whether a given formula is a tautology.
• Compactness
  A set of formulas is satisfiable if and only if every finite subset is satisfiable.

While (all) these properties may seem trivial, e.g., how soundness would not imply completeness, they aren’t.

---

1. well, of course there are infinite languages that could express propositional logic. Non-trivial ones include those using a smaller subset of the logical connectives or just using NAND ($\uparrow$) or NOR ($\downarrow$) (since they themselves are functionally complete), and those that use different symbols to denote the same connectives, or those with completely different (not infix) syntaxes, blah blah.
   Point is, they’re all isomorphic to this, the “most standard”, one.

   A notable alternative langauge, however, are Boolean Algebras, functional equivalents in algebraic form. ↩︎

2. The following combinations are sufficient:
   $\lnot$ and $\land$
   $\lnot$ and $\lor$
   $\lnot$ and $\to$ ↩︎