Functionally complete set of Connectives :
We know that there are five logical connectives ∨,∧,¬,→and ⇔. But some of these can be expressed in terms of the other & we get a smaller set of connectives.
The set containing minimum number of connectives which are sufficient to express any logical formula in symbolic form is called as the functionally complete set of connectives. There are following two functionally complete set of connectives.
(1) {¬,∨} is complete set connectives.
Here, the ∧ can be expressed using ¬ &∨ .
P∧Q ≡ (¬ ¬ P ∧Q)
≡ ¬ (¬ P ∧ ¬ Q)
The → can be expressed in terms of ¬ &∨ .
P→Q ≡ ¬ P ∧ Q
The ⇔ can be expressed in terms of ¬ ,∨ .
P⇔Q ≡ (P→Q) ∧ (Q→P)
≡ (¬ P ∨Q) ∧ (¬ Q ∨ P)
≡ ¬ [ ¬ ( ¬ P ∨ Q ) ∨ ¬ ( ¬ P ∨ Q) ]
{¬ ,∨} is a functionally complete set of connectives. Similarly, you can prove that {¬ ,∨} is complete set of connectives.
