Functionally Complete Set of Connectives

In this class, We discuss a Functionally Complete Set of Connectives.

The reader should have prior knowledge of connectives. Click Here.

{¬, ∧} and {¬, ∨} are functionally complete set of connectives.

A functionally complete set of connectives means we can write any proposition using this set of connectives.

{¬, ∧} is a functionally complete set.

(p ∨ q) can be written as ¬(¬p ∧¬q)

(p -> q) can be written as (¬p ∨ q)

We can change to conjunction once changed to this junction by using the above formula.

(p <-> q) can be written as (p -> q) ∧ (q -> p)

Finally, any proposition can be converted to an equivalent proposition containing {¬, ∧}

{¬, ∨} is a functionally complete set.

(p ∧ q) can be written as ¬(¬p ∨¬q)

(p -> q) can be written as (¬p ∨ q)

(p <-> q) can be written as (p -> q) ∧ (q -> p)