Propositional Formula

logic

Definition

Propositional Formula

A propositional formula is a formula built from atomic propositions using logical connectives such as $\neg$, $\wedge$, $\vee$, and $\to$.

Propositional formulas are the basic objects of propositional logic.

Equivalences

Idempotency

Idempotency

$$P\vee P\equiv P$$ $$P\wedge P\equiv P$$

Commutativity

Commutativity

$$P\vee Q\equiv Q\vee P$$ $$P\wedge Q\equiv Q\wedge P$$

Associativity

Associativity

$$(P\vee Q)\vee R\equiv P\vee (Q\vee R)$$ $$(P\wedge Q)\wedge R\equiv P\wedge (Q\wedge R)$$

Absorption

Absorption

$$P\vee (P\wedge Q)\equiv P$$ $$P\wedge (P\vee Q)\equiv P$$

Distributivity

Distributivity

$$P\vee (Q\wedge R)\equiv (P\vee Q)\wedge (P\vee R)$$ $$P\wedge (Q\vee R)\equiv (P\wedge Q)\vee (P\wedge R)$$

Normal Forms

Normal Form Existence

Every propositional formula has an equivalent CNF and an equivalent DNF.

They can be computed either by equivalence rewriting or by truth tables.