Functionally Incomplete Logical Connectives/Conjunction and Disjunction

From ProofWiki
Jump to navigation Jump to search


The set of logical connectives:

$\set {\land, \lor}$: And and Or

is not functionally complete.


Let $v_T$ be the boolean interpretation that assigns $T$ to each propositional symbol.

Then it follows by the nature of the truth functions for $\land$ and $\lor$ that:

$\map {v_T} {\mathbf A} = T$

for each WFF $\mathbf A$ comprising only $\land$ and $\lor$.

On the other hand:

$\map {v_T} {\neg p} = F$

Therefore, $\neg p$ cannot be expressed in terms of $\land$ and $\lor$.

Hence, $\set {\land, \lor}$ is not functionally complete.