Logical Connectives - Common Logical Connectives - Redundancy

Redundancy

Such logical connective as converse implication ← is actually the same as material conditional with swapped arguments, so the symbol for converse implication is redundant. In some logical calculi (notably, in classical logic) certain essentially different compound statements are logically equivalent. Less trivial example of a redundancy is a classical equivalence between ¬P ∨ Q and P → Q. Therefore, a classical-based logical system does not need the conditional operator "→" if "¬" (not) and "∨" (or) are already in use, or may use the "→" only as a syntactic sugar for a compound having one negation and one disjunction.

There are sixteen Boolean functions associating the input truth values P and Q with four-digit binary outputs. These correspond to possible choices of binary logical connectives for classical logic. Different implementation of classical logic can choose different functionally complete subsets of connectives.

One approach is to choose a minimal set, and define other connectives by some logical form, like in the example with material conditional above. The following are the minimal functionally complete sets of operators in classical logic whose arities do not exceed 2:

One element

{↑}, {↓}.

Two elements

{, ¬}, {, ¬}, {→, ¬}, {←, ¬}, {→, }, {←, }, {→, }, {←, }, {→, }, {→, }, {←, }, {←, }, {, ¬}, {, ¬}, {, }, {, }, {, }, {, }.

Three elements

{, }, {, }, {, }, {, }, {, }, {, }.

See more details about functional completeness in classical logic at Truth function#Functional completeness.

Another approach is to use on equal rights connectives of a certain convenient and functionally complete, but not minimal set. This approach requires more propositional axioms and each equivalence between logical forms must be either an axiom or provable as a theorem.

But intuitionistic logic has the situation more complicated. Of its five connectives {∧, ∨, →, ¬, ⊥} only negation ¬ has to be reduced to other connectives (see details). Neither of conjunction, disjunction and material conditional has an equivalent form constructed of other four logical connectives.