Propositional Logic - Examples and Constructions

Propositional logic provides powerful tools for translating natural language reasoning into precise mathematical form and for constructing normal forms that simplify logical analysis.

ExampleNatural Language Translation

Consider the statement: "If it rains or snows, then the game is cancelled unless the field is covered."

Let $r$ = "it rains", $s$ = "it snows", $g$ = "the game is cancelled", $c$ = "the field is covered".

This translates to: $(r \lor s) \to (c \lor g)$ , or equivalently using the definition of "unless": $(r \lor s) \land \neg c \to g$ .

The translation process requires careful attention to the logical structure of compound statements and the precise meaning of connectives like "unless" ( $\neg c \lor g$ ), "only if" ( $p \to q$ ), and "if and only if" ( $p \leftrightarrow q$ ).

DefinitionLiteral and Clause

A literal is either a propositional variable (positive literal) or its negation (negative literal). A clause is a disjunction of literals: $l_1 \lor l_2 \lor \cdots \lor l_k$ where each $l_i$ is a literal.

DefinitionConjunctive Normal Form (CNF)

A formula is in conjunctive normal form if it is a conjunction of clauses:

\phi = (l_{1,1} \lor \cdots \lor l_{1,k_1}) \land (l_{2,1} \lor \cdots \lor l_{2,k_2}) \land \cdots \land (l_{m,1} \lor \cdots \lor l_{m,k_m})

Every propositional formula is logically equivalent to a formula in CNF.

DefinitionDisjunctive Normal Form (DNF)

A formula is in disjunctive normal form if it is a disjunction of conjunctions of literals:

\phi = (l_{1,1} \land \cdots \land l_{1,k_1}) \lor (l_{2,1} \land \cdots \land l_{2,k_2}) \lor \cdots \lor (l_{m,1} \land \cdots \land l_{m,k_m})

Every propositional formula is logically equivalent to a formula in DNF.

ExampleCNF Conversion

Convert $\phi = (p \to q) \land r$ to CNF:

Eliminate implication: $(\neg p \lor q) \land r$
Already in CNF: conjunction of two clauses $(\neg p \lor q)$ and $r$

For $\psi = \neg((p \land q) \lor r)$ :

Apply De Morgan: $\neg(p \land q) \land \neg r$
Apply De Morgan again: $(\neg p \lor \neg q) \land \neg r$
CNF: $(\neg p \lor \neg q) \land \neg r$

Remark

CNF and DNF are particularly useful in automated theorem proving and satisfiability testing. The SAT problem (determining if a CNF formula is satisfiable) is the canonical NP-complete problem, making propositional logic central to computational complexity theory.

Normal forms provide canonical representations that facilitate both theoretical analysis and practical applications in computer science, from circuit design to formal verification.