# Functionally Complete Logical Connectives/Negation and Disjunction

Jump to navigation
Jump to search

## Theorem

The set of logical connectives:

This article is complete as far as it goes, but it could do with expansion.In particular: to adopt the notion of Independent Set of StatementsYou can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Expand}}` from the code.If you would welcome a second opinion as to whether your work is correct, add a call to `{{Proofread}}` the page. |

## Proof

From Functionally Complete Logical Connectives: Negation and Conjunction, $\set {\neg, \land}$ is functionally complete.

That is: any expression can be expressed in terms of $\neg$ and $\land$.

From De Morgan's laws: Conjunction, we have that:

- $p \land q \dashv \vdash \neg \paren {\neg p \lor \neg q}$

Thus all occurrences of $\land$ can be replaced by $\lor$ and $\neg$.

Thus any expression can be expressed in terms of $\neg$ and $\lor$.

That is: $\set {\neg, \lor}$ is functionally complete.

$\blacksquare$

## Sources

- 1959: A.H. Basson and D.J. O'Connor:
*Introduction to Symbolic Logic*(3rd ed.) ... (previous) ... (next): $\S 2.5$: Further Logical Constants - 1965: E.J. Lemmon:
*Beginning Logic*... (previous) ... (next): Chapter $2$: The Propositional Calculus $2$: $3$ Truth-Tables: Exercise $2 \ \text{(i)}$ - 1972: A.G. Howson:
*A Handbook of Terms used in Algebra and Analysis*... (previous) ... (next): $\S 1$: Some mathematical language: Connectives - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic - 2012: M. Ben-Ari:
*Mathematical Logic for Computer Science*(3rd ed.) ... (previous) ... (next): $\S 2.4.2$: Theorem $2.36$