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

 

Hello,

The following pages contain a lot of links with information on digital circuits / logics:
Arithmetic circuits
CMOS technology
Codes & decoders
Converters
Counters & registers
DAC/ADC types
Digital logic
Digital theory
Flip flops
FPGA Design
Memory
Number systems
Sigma Delta Conversion
Technology
Timers & oscillators
TTL technology


Bertus

 

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

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?

 

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.

 

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?

yes

 

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?

 

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?

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!

 

if there is a specific rules for, then would be nice and appreciated to inform me with them

 

Anyone?!!

 

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!

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?

 

if there is a specific rules for, then would be nice and appreciated to inform me with them

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.

 

Anyone?!!

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.

 

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?

Ah got you, you would have said that from the beginning
they are : {OR,AND,NOT}

 

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.

Sorry for...

 

Ah got you, you would have said that from the beginning
they are : {OR,AND,NOT}

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?

 

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?

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?

 

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

 

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?

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.

 

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

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.

 

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.

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?