DeMorgan's theorem, What does it logically mean? I missed it on a test

In summary, DeMorgan's law can be stated in several ways and it is the same thing as your statement, the first one almost the same.
  • #1
mr_coffee
1,629
1
Hello everyone, this problem is bothering me!
The problem states:
Note: 'x means x is complemented, or a bar is over it.
One of DeMorgan's theorems states that 'x+'y = 'x'y; Sipmly stated, this means that logically there is no difference between:
(a) a NOR gate and an AND gate with inverted inputs.
b. a NAND gate and an OR gate with inveted inputs.
c. an AND gate and a nor gate with inverted iputs.
d. a nor gate and a NAND gate with inverted inputs.

I said, d, which was wrong.
 
Physics news on Phys.org
  • #2
I know two different versions of DeMorgan's theorem and neither one is stated like that!

Yes, that is DeMorgan's "law"- my point is that there are several ways of stating it. One is in terms of logic: (NOT)(a OR b) is the same as (NOT a) AND (NOT b), the other is in terms of sets: the complement of the union of sets A and B is the intersection of the complements of A and B.

Both are exactly the same thing as your statement, the first one ALMOST the same- but not given in terms of "gates"!

Looking precisely at 'x+ 'y= '(xy) I would interpret that as (NOT a OR NOT b) is the same as NOT (a AND b) and if I have my "gates" right, that would be saying that NAND gate {NOT (a AND b)} is the same as an OR gate with inverted inputs (NOT a OR NOT b), choice (b).

Frankly, I don't consider that a very good question because DeMorgan's law can also be phrased the other way around: ('x'y)= '(x+y). That would be (NOT x and NOT y) is the same as NOT(x or y), or "a NOR gate is the same as two AND gates with inverted inputs", choice (a).

In any case, it would not be (d) because there is no " a NAND gate with inverted inputs."- no "double negatives".
 
  • #4
thanks for the explanation! I know how to apply DeMorgan's theorem but this one screwed me!
 

FAQ: DeMorgan's theorem, What does it logically mean? I missed it on a test

What is DeMorgan's theorem?

DeMorgan's theorem is a fundamental law in Boolean algebra that describes the relationship between logical AND and OR operations. It states that the negation of a conjunction (AND) is logically equivalent to the disjunction (OR) of the negations of the individual statements.

What does it mean in logical terms?

In logical terms, DeMorgan's theorem means that the negation of a compound statement (A and B) is equivalent to the disjunction of the negations of the individual statements (¬A or ¬B). This can also be extended to multiple statements.

How is DeMorgan's theorem used in logic?

DeMorgan's theorem is used in logic to simplify complex logical expressions. By applying this theorem, we can rewrite a statement in a different form, making it easier to understand and evaluate.

Can you provide an example of DeMorgan's theorem?

Sure, let's say we have the statement "It is not raining and it is not sunny" (¬A and ¬B). By applying DeMorgan's theorem, we can rewrite it as "It is neither raining nor sunny" (¬A or ¬B).

How is DeMorgan's theorem related to the laws of logic?

DeMorgan's theorem is closely related to the laws of logic, specifically the distributive law. This theorem helps us understand and manipulate logical expressions, which is essential in solving complex logic problems.

Back
Top