Skip to main content
Engineering LibreTexts

2.1.I 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 → is logically equivalent to ¬∨ q. (Just make a truth table for ¬∨ q.) Similarly, ↔ can be expressed as (¬∨ 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 ∧ is logically equivalent to ¬(¬∨ ¬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.