# Computer Digital logics

Discussion in 'Homework Help' started by Ryan2, May 29, 2015.

1. ### Ryan2 Thread Starter Member

May 29, 2015
31
0
I'm new here and I need a help for how to verify or prove if a function is a complement system or its not a complement system? like operators (Or,not) are a complement system...

Apr 5, 2008
15,806
2,389
3. ### WBahn Moderator

Mar 31, 2012
18,088
4,917
What is a "complement" system?

Do you mean whether they form a complete set such that, given only an unlimited supply of the gates in the set, you can implement any digital logic function?

4. ### WBahn Moderator

Mar 31, 2012
18,088
4,917
Also, this sounds like it belongs in Homework Help. You'll probably get more of the kind of attention you need over there if that's the case. I'll go ahead and move it over there and if you can explain why it should be in Project (and if that's where you want it), just reply with that explanation/request and I'll move it back.

May 29, 2015
31
0
yes

6. ### WBahn Moderator

Mar 31, 2012
18,088
4,917
Okay, so first you need to understand, with some rigor, what is required in order to have a complete set. The starting point for that is to be able to list the required operations for Boolean algebra. What are they?

7. ### Ryan2 Thread Starter Member

May 29, 2015
31
0
the required operations I know them which are like OR AND XOR NAND...etc but the problem is not here actually, the problem is how to prove or refute the function of being a completion set or not!

8. ### Ryan2 Thread Starter Member

May 29, 2015
31
0
if there is a specific rules for, then would be nice and appreciated to inform me with them

May 29, 2015
31
0
Anyone?!!

10. ### WBahn Moderator

Mar 31, 2012
18,088
4,917
You are going to have a hard time proving that something is a complete set when you don't know what is required of a complete set.

Think of a Boolean expression. What symbolic operators do you have? Do you have an operator for NAND? No. It is not part of fundamental Boolean algebra.

You have three fundamental operations in Boolean algebra. What are they?

Ryan2 likes this.
11. ### WBahn Moderator

Mar 31, 2012
18,088
4,917
I am willing to help you learn the concepts. I'm not interested in just giving you a recipe so that you can mimic a monkey.

12. ### WBahn Moderator

Mar 31, 2012
18,088
4,917
People have lives apart from jumping to and answering your every question. Don't get impatient and demanding just because thirteen minutes have past without a response. It REALLY turns people off, especially when you aren't making much of an effort to work things out for yourself.

13. ### Ryan2 Thread Starter Member

May 29, 2015
31
0
Ah got you, you would have said that from the beginning
they are : {OR,AND,NOT}

May 29, 2015
31
0
Sorry for...

15. ### WBahn Moderator

Mar 31, 2012
18,088
4,917
The idea was to get you to think and ponder about it.

Okay, so our Boolean algebra requires that we have to be able to perform those three specific operations.

If we have a set of gates that allows us to perform those three operations (one is unary and two are binary), then what do we have?

We can prove that we don't have to show all three, but rather it is sufficient to show that we can perform a subset. What do you think that subset might be?

Ryan2 likes this.
16. ### Ryan2 Thread Starter Member

May 29, 2015
31
0
Aha, we can handle it by just two operations which is {Not, Or} which we can get by "demorgan" the AND operation, and vise versa also correct by (And, Not)

ye?

17. ### Ryan2 Thread Starter Member

May 29, 2015
31
0
The idea has already known for me, but how to prove/disprove exactly is a semi hard for me because there's no standard way for, but there must be thumb rules for disproving....

18. ### WBahn Moderator

Mar 31, 2012
18,088
4,917
Exactly.

Because you can write AND in terms of OR and NOT, you only need to show that your set can implement OR and NOT.

Similarly, you can write OR in terms of AND and NOT so you only need to show that your set can implement AND and NOT.

Combining these, a set is complete if it can implement unary-NOT and either binary-OR or binary-AND.

Ryan2 likes this.
19. ### WBahn Moderator

Mar 31, 2012
18,088
4,917
Other than showing that you either can or cannot implement the required functions, I know of no "standard" way. The possibilities are usually sufficiently constrained that you can usually resort to exhaustive search (i.e., a truth table) to prove/disprove the claim.

20. ### Ryan2 Thread Starter Member

May 29, 2015
31
0
LOL, it wasn't my problem of, my problem how to disprove that a specific function isn't a complete set at all? isn't there any other quick steps for verifying it's a complete set or not?

and lets say I have an operators {XOR,NAND} and asking me if it's a complete set or not? how would I even get started? can you solve it for me to know just how the things go behind of this logic?