Purchase Solution

NOR and NAND Connectives Proof

Not what you're looking for?

Ask Custom Question

""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

Purchase this Solution
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.
...

Purchase this Solution
Free BrainMass Quizzes
Solving quadratic inequalities

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

Know Your Linear Equations

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.

View More Free Quizzes
Related BrainMass Solutions

  • Binary Connections

    Further from NOR table, we can conclude that: f(0, 1) = 0 f(1, 0) = 0 f(1, 1) = 0 i.e., fro NOR, any combination of true and false gives a false So we can safely conclude that NAND and NOR give complete single binary connectives.

  • Simplifying a Circuit Diagram

    Find the simplified circuit diagram: Line A enters a NOR Gate, exits, and enters a final NAND Gate. Likewise, Line B enters the same NOR Gate, exits, and enters the same final NAND Gate.

  • Electronics - Logic gates

    So in our case the NAND gate inputs are "0" and "1" so the output of the NAND gate is "1" The NOR gate truth table is: 00 1 01 0 10 0 11 0 The NOR (NOT OR) gate is the conjugate of the OR operation, so it will be "1" only if the two inputs

  • Simplifying Circuits and Expressions for Logic Circuits

    Simplify the circuit: Line A enters a NOR Gate, exits, and enters a final AND Gate. Likewise, Line B enters the same NOR Gate, exits, and enters the same final NAND Gate. Line C goes directly to the final NAND Gate.

  • Proofs

    . - M AND - J [ De Morgan's Law (3)] 5. - M [ Conjunction elimination (4)] Logical connectives are translated. The propositional variables are used to complete an argument proof.

  • Simplifying a Circuit

    Line A goes into an INVERTER, then into a NAND Gate, then into an OR Gate, then travels into another NOR Gate. Line B travels into the same NAND Gate, then into the same OR Gate, then into the same NOR Gate.

  • Boolean Algebra and Digital Logic

    Draw circuits that implement the following Boolean expressions using some combination of AND, OR, NOT, NAND, and NOR gates... See the attached file. Boolean algebra and digital logic are discussed.

  • 7-segment Display

    Can only use standard logic gates to complete this: AND, OR, NOT, NAND, NOR, XOR, XNOR. I can design the actual circuit in my program, I just need to know how to configure it and the analysis behind it; such as how it is actually working.

  • Important information about Symbolize and prove the arguments provided

    Finally, circle your connectives so you can see how the compound statements are built, and further what symbols go with what connectives. In different logic systems you'll get different symbols for the same connective.

View More Related Solutions