Determining the Functional Completeness of the Set {⇔, ∧, 0}

51 Views Asked by At

I am seeking assistance in determining whether the set {⇔, ∧, 0} is functionally complete in propositional logic. To do so, I have attempted to represent logical operators using this set {!, ∧, ∨}. Specifically, I have already managed to express the negation operator (!) as p ⇔ 0 and the conjunction operator is in both sets, so I'm assuming I don't need to prove this one. However, I'm currently struggling to represent the disjunction operator (∨) using these symbols. I know that {!, ∧} is functionally complete by itself, but still want to know how to show it works for (∨).

Could someone provide insight or guidance on how to represent the disjunction operator (∨) using only the symbols {⇔, ∧, 0}? Additionally, if there are any insights into the functional completeness of this set, please share them.

1

There are 1 best solutions below

0
On BEST ANSWER

You have essentially already solved the question: you proved that you can construct negation from your given set of connectives, and you know that $\{!, \wedge\}$ is functionally complete. So you can build any other connective from $\{\Leftrightarrow, \wedge, 0\}$ in the same way that you build them from $\{!, \wedge\}$, only you replace any use of $!$ by its construction from $\{\Leftrightarrow, \wedge, 0\}$.

This immediately gives a recipe how to build $\vee$ from $\{\Leftrightarrow, \wedge, 0\}$. You say you know how to do it from $\{!, \wedge\}$, so I assume you know that $p \vee q = !(!p \wedge !q)$. Now replace all occurrences of $!X$ by $X \Leftrightarrow 0$ to find $$ p \vee q = ((p \Leftrightarrow 0) \wedge (q \Leftrightarrow 0)) \Leftrightarrow 0. $$