1
$\begingroup$

(a || b) || (c && d))

Given the above, how do I derive the table below:

a b c d output
T - - - TRUE
F T - - TRUE
F F T T TRUE
F F T F FALSE
F F F - FALSE

I'm told that this is short circuit evaluation, basically, we take away some branches/paths that always lead to false or true so we don't waste time going through them. As a result we have lowered the number of conditions here greatly.

However, my brain just can't figure out how to do this. Apparently this is done via a decision tree.

Can somebody help me figure out the process?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Looking at your question again, I think you really may only need two simple rules. After reviewing these rules, then we can see how to build a table. Note that I will write

$$(a || b) = (a \lor b)$$ $$(a \&\& b) = (a \land b)$$


When you have logical or equations:

$$\tag{1}(a \lor b)$$

You should know that if one of these is true, then the whole function is true. So your table would be:

a b output
T - TRUE
F T TRUE
F F FALSE

...In other words, you start with a value that leads to something true. So start with $a$ being true, and that gives the first line. Then, for the second line, assume $a$ is now false, and then $b$ must be true to give a true output. Finally, if both of these are false, then the output must be false since neither $a$ nor $b$ are true.


$$\tag{2}(a \land b)$$

You should know that this can be true only if both are true.

a b output
T T TRUE
F T FALSE
F F FALSE

I left that one go for you to figure out. Essentially, if either of the outputs is false, then $(a \land b)$ is false.


Now to combine the results...

Start with the outermost parenthesis. If you have your function, which is $((a \lor b) \lor (c \land d))$, you look at the parenthesis. You have $f \lor g$, with

$$f = (a \lor b)$$ $$g = (c \land d)$$

Now you know that the function can be true if either $f$ is true or $g$ is true. We don't have to fill anything in the table yet, but this gives us the order of things and what we need. In other words, start with making $f$ true. Then $f$ false and $g$ true. Then finally both false.

So your table groups $a$ and $b$ together as $f$, and $c$ and $d$ together as $g$. Then the table will look like:

a b c d output parenthesis group
T - - - TRUE f TRUE
F T - - TRUE f TRUE
F F T T TRUE f FALSE, g TRUE
F F T F FALSE f FALSE, g FALSE
F F F - FALSE f FALSE, g FALSE

So what I've tried to show is that after you've figured out what the outermost parenthesis does, you go through that in order. Then you break apart the innermost functions and go through them in order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.