C Programming Language: Reducing Boolean Expressions?

How do you reduce the following Boolean expressions? To those who answer, please explain how you got to each step to get to the final solution.








1) (a%26lt;b||c%26gt;=d)%26amp;%26amp;(e==f%26amp;%26amp;!(a %26gt;= b))





2) A %26amp;%26amp; B %26amp;%26amp; C || A %26amp;%26amp; C





3) (A%26lt;B||C!=D)%26amp;%26amp;(A%26gt;=B%26amp;%26amp;C==D)

C Programming Language: Reducing Boolean Expressions?
The following answers were tested with the


program at:





http://www.hotlinkfiles.com/files/102925...











Problem #1


------------------





Given:


(a%26lt;b||c%26gt;=d)%26amp;%26amp;(e==f%26amp;%26amp;!(a %26gt;= b))





Notice that "!(a%26gt;=b)" is equivalent to "a%26lt;b".





The second part of the condition:





(e==f%26amp;%26amp;!(a %26gt;= b))





requires that "!(a %26gt;= b)". However, if that


condition is true, then obviously "a%26lt;b" is also


true. This in turn forces the full left hand


side to evaluate to be true:





(a%26lt;b||c%26gt;=d)





Note that this follows *regardless* of the values


of "c" and "d".








Therefore, this entire logical expression reduces


to:





(e==f%26amp;%26amp;!(a %26gt;= b))








Problem #2


------------------





Given:


A %26amp;%26amp; B %26amp;%26amp; C || A %26amp;%26amp; C








This condition can be separated into the two


subexpressions on each side of the "||".





If "A %26amp;%26amp; C" is true, then "A %26amp;%26amp; B %26amp;%26amp; C" is


guaranteed to be true.





Conversely, if "A %26amp;%26amp; C" is false, then either


A is false or C is false, which necessarily


requires that "A %26amp;%26amp; B %26amp;%26amp; C" must be false.





Thus, the entire expression can be reduced


to:





A %26amp;%26amp; C





In this case, we can fully test this


with the following "truth table". For


inputs A, B, and C, the output of


either the original or reduced expression


follows:





0 0 0 ==%26gt; 0


0 0 1 ==%26gt; 0


0 1 0 ==%26gt; 0


0 1 1 ==%26gt; 0


1 0 0 ==%26gt; 0


1 0 1 ==%26gt; 1


1 1 0 ==%26gt; 0


1 1 1 ==%26gt; 1








Problem #3


------------------





Given


(A%26lt;B||C!=D) %26amp;%26amp; (A%26gt;=B%26amp;%26amp;C==D)








For the left side to be true, either


A%26lt;B or C!=D. However, if *either*


condition is true, then the right


side evaluates to be false.





Thus, if the left is true, then the


right is false. If the left is false,


then the right is true. This leaves


us with either:





1 %26amp;%26amp; 0





or





0 %26amp;%26amp; 1





In either case, the final outcome is


always 0 (false).





Thus, the expression can be reduced


to:





(0)
Reply:I will not just give you the answers but I will lead you through the first one. The two main things to consider are order or precedence and negation of two (or more) expressions using the same variables. Precedence is mainly given by parenthesis and then by compiler. I'll assume your instructor/book told you whether to treat an '%26amp;%26amp;' before an '||'.





Using the parenthesis as guidance, examine the first expression. It says (for the whole expression to be true) either a must be less than b OR c must be greater than or equal to d. Furthermore, e must always equal f and a must never be greater than or equal to b.





Now, look at the two relations with common variables:


a %26lt; b !(a %26gt;= b)





One says a must be less than b; the other says a must not be greater than or equal to b. Essentially, they say the same thing. So, you can get rid of one. But which? Well, the one on right '!(a %26gt;= b)' must always occur (given the %26amp;%26amp;) and the other on the left may occur, drop the may. If the one on the right doesn't hold true, the whole expression is false. If it does hold true, this means the one on the left 'a %26lt; b' is also true which also means we no longer care if 'c %26gt;= d' or not.





So, you can simply reduce the expression to read (e == f) %26amp;%26amp; !(a %26gt;= b). Or, if you want to make the second part read more clearly....


(e == f) %26amp;%26amp; (a %26lt; b)

parts of a flower