Given this logic gate :
A AND B OR B AND C AND (B OR C)
it can be shorten as :
B AND (A OR C)
How do we do this ? I tried to aplly the De Morgan law but without success?
Any help is greatly appreciated !
Asked
Active
Viewed 85 times
1
-
1your parenthesis are still ambiguous do you mean (A & B) or (B & C & (B or C)), or do you mean A & (B or B & C & (B or C)), or do you mean etc... – Sidharth Ghoshal Aug 15 '14 at 07:46
-
"AND" has precedence (in electrical engineering), thus the formula in logic would be: $(A\land B)\lor (B\land C\land (B\lor C))$ – Charles Gillingham Aug 15 '14 at 07:55
-
Rather than try to apply equivalence laws to the expression, I'd probably either use a truth table or formally prove each expression from the other. – user2357112 Aug 15 '14 at 08:36
2 Answers
2
If $BC$ is true, then both $B$ and $C$ are true, and so it is clear that $B+C$ is also true. Thus, $BC(B+C)=BC$.
Then, $AB+BC(B+C)=AB+BC=B(A+C)$, as required.
Joel Bosveld
- 728
- 5
- 10
-
BC(B+C) = BC, is that a law like de morgan or something you just prove recently (i know you are right, i'm just curious) – f855a864 Aug 15 '14 at 08:10
-
It depends what you mean by law? I'm not sure if it has a name, but after a quick glance at the Wikipedia article, I would say it follows from the associativity and commutivity of AND, the distributivity of AND over OR and the idempotence of AND and OR. So $BC(B+C)=BCB + BCC=BBC+BCC=BC+BC=BC$. – Joel Bosveld Aug 15 '14 at 08:33
-
A further look here, suggests that the usual axiom is the one called absorption B(B+C)=B, which Charles mentions. – Joel Bosveld Aug 15 '14 at 08:37
-
0
Use the rule that (X AND (X OR Y)) <=> (X)
You can apply this to transform
B AND C AND (B OR C)
into
B AND C
Can you solve the rest?
-
I'm assuming in my answer that you are expected to use transformation rules to derive the new expression, and that the rule X AND (X OR Y) -> X AND Y is one of the rules. There are many other ways to prove this. – Charles Gillingham Aug 15 '14 at 08:05
-
"(X AND (X OR Y)) <=> (X AND Y)" - what? No. (X AND (X OR Y)) <=> X. – user2357112 Aug 15 '14 at 08:11
-
@user2357112 thanks, it makes sense now, is this a law ( (X AND (X OR Y)) <=> X ) ? – f855a864 Aug 15 '14 at 08:13
-
-
@CharlesGillingham thanks but can you tell me where did you get that rule ? – f855a864 Aug 15 '14 at 08:18
-
Perhaps it would quicker to tell me the list of rules you have available for the problem, and I can help you derive this rule from those. – Charles Gillingham Aug 15 '14 at 08:38
-
-
but i don't have any rule available, i just can't figure out how you guys can come up with (X AND (X OR Y)) <=> X for fast ? – f855a864 Aug 15 '14 at 08:53
-
The "cognitive psychology" answer is that we are both familiar with logic and you can see that this rule is true by the kind of reasoning that Joel gives at the top of his post. If X is true then X || Y is also true, so there's no reason to say that X || Y is true if you already said that X is true. If X isn't true, then X && anything is false, so if X is true there's no reason to say that X || Y is true. – Charles Gillingham Aug 15 '14 at 19:00
-
In other words, it's obvious from the semantics of "AND" and "OR" – Charles Gillingham Aug 15 '14 at 19:08
-
The "foundations"/"philosophy of mathematics" answer is that you can prove the rule using a valid method: use a truth table, or derive it from a small set of axioms. This is not obvious, but there are actually many different possible sets of axioms that can be used, because you can derive one set from another and vice versa, so you have a choice about what axioms you are going use. In a classroom setting, the professor will typical give you the set of axioms you are permitted to use and you derive theorems using only those axioms. – Charles Gillingham Aug 15 '14 at 19:09