# 1.1.9: Universal operators

- Page ID
- 9838

Now, any compound proposition that uses any of the operators →, ↔, and ⊕ can be rewritten as a logically equivalent proposition that uses only ∧, ∨, and ¬. It is easy to check that *p *→ *q *is logically equivalent to ¬*p *∨ *q*. (Just make a truth table for ¬*p *∨ *q*.) Similarly, *p *↔ *q *can be expressed as (¬*p *∨ *q*) ∧ (¬*q *∨ *p*), So, in a strict logical sense, →,↔, and ⊕ are unnecessary. (Nevertheless, they are useful and important, and we won’t give them up.)

Even more is true: In a strict logical sense, we could do without the conjunction operator ∧. It is easy to check that *p *∧ *q *is logically equivalent to ¬(¬*p *∨ ¬*q*), so any expression that uses ∧ can be rewritten as one that uses only ¬ and ∨. Alternatively, we could do without ∨ and write everything in terms of ¬ and ∧. We shall study some of these rewrite rules in more detail in Section 2.2.

We call a set of operators that can express all operations: **functionally complete**. More formally we would state the following:

Definition2.3.

A set of logical operators is functionally **complete** if and only if all formulas in propositional logic can be rewritten to an equivalent form that uses only operators from the set.

Consider for instance the set {¬, ∨}. As shown above the ∧, → and ↔-operators can be expressed using only these operators. In fact all possible operations can be expressed using only {¬, ∨}. To prove this you will show in one of the exercises that all possible formulas in propositional logic can be expressed using {¬, ∨, ∧, →, ↔}. So by showing that we do not need ∧, →, and ↔ we can prove that {¬, ∨} is also functionally complete.