Classical Propositional Logic

Overview

A classical propositional system is one in which proposition symbols are assigned either truth or falsity.

A truth assignment $v$ for a set $\mathcal{S}$ of proposition symbols is a function $v:\mathcal{S}\to \{F,T\}$ assigning either $T$ or $F$ to each symbol in $\mathcal{S}$.

Let $\bar{\mathcal{S}}$ denote the set of WFFs that can be built up from $\mathcal{S}$ by the five formula-building operations. Let $A\in \mathcal{S}$ and $\alpha ,\beta \in \bar{\mathcal{S}}$. Then the unique extension of $v$ is $\bar{v}:\bar{\mathcal{S}}\to \{F,T\}$ given by the following rules:

1. $\bar{v}(A)=v(A)$.
2. Negation. $\bar{v}((\mathrm{\neg }\alpha ))=\mathrm{\neg }\bar{v}(\alpha )$.
3. Conjunction. $\bar{v}((\alpha \wedge \beta ))=(\bar{v}(\alpha )\wedge \bar{v}(\beta ))$.
4. Disjunction. $\bar{v}((\alpha \vee \beta ))=(\bar{v}(\alpha )\vee \bar{v}(\beta ))$.
5. Material Implication. $\bar{v}((\alpha ⟹\beta ))=(\bar{v}(\alpha )⟹\bar{v}(\beta ))$.
6. Material Equivalence. $\bar{v}((\alpha ⟺\beta ))=(\bar{v}(\alpha )⟺\bar{v}(\beta ))$

We say $v$ satisfies a WFF $\alpha$ if $\bar{v}(\alpha )=T$.

Truth Tables

A truth table is a systematic representation of all possible values a Boolean variable can take on in a proposition.

For example, proposition $\mathrm{\neg }(a⟹b)⟺c$ has the following truth table:

Satisfiability

A WFF $\varphi$ is satisfiable, denoted $\text{Sat}(\varphi )$, if some assignment of $T$s and $F$s make the formula evaluate to $T$. For example, assignment $x=F$, $y=T$, and $z=F$ satisfies Boolean formula $\varphi =(\mathrm{\neg }x\vee y)\vee (x\wedge \mathrm{\neg }z)$.

We say two formulas $\varphi$ and $\psi$ are equisatisfiable if the first is satisfiable if and only if the second is satisfiable. Two equisatisfiable formulas are not necessarily logically equivalent - they may disagree for a particular assignment of variables.

Clause-Splitting

The act of breaking up larger clauses in DNF or CNF into smaller, equisatisfiable clauses is called clause-splitting. It is done by iteratively introducing additional variables that allow "choosing" which collection of literals is satisfied.

Entailment

Let $\mathrm{\Sigma }$ be a set of WFFs and $\tau$ be another WFF. Then $\mathrm{\Sigma }$ entails (or tautologically implies) $\tau$, denoted $\mathrm{\Sigma }\models \tau$, if and only if every truth assignment for the proposition symbols in $\mathrm{\Sigma }$ and $\tau$ that satisfies every member of $\mathrm{\Sigma }$ also satisfies $\tau$.

• If $\mathrm{\Sigma }$ is a singleton $\{\sigma \}$, we simply write $\sigma \models \tau$.
• $\mathrm{\Sigma };\sigma \models \tau$ is understood to be equivalent to $\mathrm{\Sigma }\cup \{\sigma \}\models \tau$.
• If $\varnothing \models \tau$, we call $\tau$ a tautology. This is denoted $\models \tau$.
• If $\sigma \models \tau$ and $\tau \models \sigma$, then $\sigma$ and $\tau$ are tautologically equivalent. This is denoted $\sigma \models =\mid \tau$.

$\mathrm{\Sigma }$ is said to be independent if no member of $\mathrm{\Sigma }$ is entailed by the remaining members of $\mathrm{\Sigma }$. $\mathrm{\Sigma }$ is said to be equivalent to a set of WFFs $\mathrm{\Gamma }$ if for any WFF $\alpha$, $\mathrm{\Sigma }\models \alpha$ if and only if $\mathrm{\Gamma }\models \alpha$.

Deduction Theorem

Let $\mathrm{\Sigma }$ be a set of WFFs. Also let $\alpha$ and $\beta$ be WFFs. Then

Monotonicity

Let $\mathrm{\Sigma }$ be a set of WFFs. Also let $\alpha$ and $\beta$ be WFFs. Then

That is, one can weaken the antecedent without affecting the consequent.

Disjunctive Normal Form

A proposition is in disjunctive normal form (DNF) if written as a collection of conjunctions separated by $\vee$. Each conjunct is called a literal. Each disjunct is called a clause.

A Boolean formula in disjunctive normal form is called a dnf-formula. A $k$dnf-formula is a dnf-formula such that each conjunct has $k$ disjuncts.

To write a proposition in DNF, write its corresponding truth table and $\vee$ each row that evaluates to $T$.

Conjunctive Normal Form

A proposition is in conjunctive normal form (CNF) if written as a collection of disjunctions separated by $\wedge$. Each disjunct is called a literal. Each conjunct is called a clause.

A Boolean formula in conjunctive normal form is called a cnf-formula. A $k$cnf-formula is a cnf-formula such that each conjunct has $k$ disjuncts.

To write a proposition in CNF, apply $\vee$ to each row that evaluates to $F$ and negate it.