Purchase Solution

# NOR and NAND Connectives Proof

Not what you're looking for?

""PROVE that there are no other single binary connectives than NAND and NOR who are functionally complete""

I saw the same question on the library, but I didn't understand anything.

The professor explained it but I still don't get it, it seems that the key of the proof rely on the EVEN/ODDNESS of the occcurrence at which the truth function takes the FALSE and TRUE values on the truth table. (no idea why...)

PLEASE, i really need all the details of your explanation. don't forget the point of the proof : IT IS ABOUT the even/oddness of the occcurrences at which the truth function takes the FALSE and TRUE values on the truth table. (no idea why...)

I give it a 3 credits but I really hope you can provide the explanations followed by the formal proof.

Thank you

##### Solution Preview

It's easy to argue that both of NAND and NOR are functionally complete. Let's show how to do it.

To show that NAND is functionally complete, all you have to do is show how to use NAND to implement functions in a set you already know is functionally complete. It is known that set { AND, NOT} is complete.

You can implement { AND, NOT} using only NAND:
* NOT x can be implemented as NAND (x, x), which can also be written as x NAND x. This can be verified using a truth table. Note: x refers to an arbitrary Boolean expression, not just a variable.
* Once you have NOT implemented, then you can implement AND(x, y) as NOT( NAND(x, y)). Negating NAND gives you AND.

It is known that set { OR, NOT} is complete.

You can show that NOR is functionally complete by implementing OR and NOT:
* NOT x can be implemented as NOR (x, x), which can also be written as x NOR x. This can be verified using a truth table. Note: x refers to an arbitrary Boolean expression, not just a variable.
...

##### Free BrainMass Quizzes

This quiz test you on how well you are familiar with solving quadratic inequalities.

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

##### Probability Quiz

Some questions on probability

##### Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

##### Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.