Talk:Functionally Complete Logical Connectives

Proof is not done

Here is the first sentence in the proof: "It suffices to consider binary operators." Why? How do we know that there is not some 342-place truth function that cannot be created by composing the 16 binary boolean functions? Even if the proof is obvious (I don't know it, by the way), it should be included here or on another page. JamesMazur2 (talk) 12:33, 3 June 2011 (CDT)

Good call.--prime mover 15:11, 3 June 2011 (CDT)

A proof is contained in this document. What are the rules for citing/using sources here on ProofWiki? JamesMazur2 (talk) 15:50, 7 June 2011 (CDT)

The rule is: we document the proof in full. We may then include a link to the cited document.

But in this case we have no need to, as we already have the CNF and DNF definitions on the db, both of which tread the same ground as this. --prime mover 16:04, 7 June 2011 (CDT)

The proof that $\left\{{\neg, \land, \lor}\right\}$ is functionally complete is fairly trivial.

• First, consider the constant functions:

• $( p \lor \neg p ) = T$
• $( p \land \neg p ) = F$

• For any other function, any input can be expressed as a conjunction of literals (or a single literal) equal in number to the arity of the function. Then the function is expressed using negation, conjunction, and disjunction as a disjunction of exactly those inputs that make the function true.

The proof is easy. I just don't know how to formalize it! Please help! JamesMazur2 (talk) 14:58, 24 June 2011 (CDT)

I don't understand, the proof is already done, on the page this talk page is attached to. --prime mover 16:03, 24 June 2011 (CDT)

Oh I meant the part about it sufficing to consider binary operators. And that's most easily done by showing, and, or, not is functionally complete. JamesMazur2 (talk) 20:12, 24 June 2011 (CDT)

Right okay I get you, I'll bend a brain cell in that direction in due course - thx. --prime mover 02:21, 25 June 2011 (CDT)