Minimum number of checks to validate a truth table

StackOverflow https://stackoverflow.com/questions/4065539

  •  27-09-2019
  •  | 
  •  

Question


I have a java program where I want to validate if any of 3 booleans is false. I want to figure out the smallest expression I can write to check against the permutations.

if(!(needsWork && (needsApproval || isAdmin) ))

I think this is enough to make sure that if any of the 3 booleans is false I want to stop processing. However, I have the sneaking suspicion I am missing something.

Was it helpful?

Solution

Would if (!needsWork || !needsApproval || !isAdmin) not work? Java supports short-circuit evaluation.

OTHER TIPS

Since

`any 3 booleans are false` (i.e. `!a || !b || !c`)

and

`(! (needsWork && (needsApproval || isAdmin))` (i.e. (! (a && ( b || c))`

have different truth tables, are you sure that the cases that are different don't matter?

a b c   (!a || !b || !c)    (! (a && (b || c)))
T T T          F                    F          
T T F          T                    F
T F T          T                    F
T F F          T                    T
F T T          T                    T
F T F          T                    T
F F T          T                    T
F F F          T                    T

Transformations

I will often play around with boolean expressions to try to clarify or simplify them and I use these logic transformations to help me:

// You can push (distribute) `!` into parenthesis if you reverse the `||` or `&&` operator inside:
! (a || b)             <=> (! a && ! b)
! (a || b || c || ...) <=> (! a && ! b && ! c && ...)

! (a && b)             <=> (! a || ! b)
! (a && b && c && ...) <=> (! a || ! b || ! c || ...)

// You can drop parens when the boolean operator outside the parens is the same as inside:
(a || (b || c || ...)) <=> (a || b || c)
(a && (b && c && ...)) <=> (a && b && c)

// You can push (distribute) a boolean op into parenthesis by applying it to each term inside:
(a || (b && c)         <=> ((a || b) && (a || c)
(a || (b && c && ...)  <=> ((a || b) && (a || c) && (a || ...) ...

(a && (b || c)         <=> ((a && b) || (a && c))
(a && (b || c || ...)  <=> ((a && b) || (a && c) || (a || ...) ...

// XOR means the term values have to be different:
(a ^ b)                <=> ((a && !b) || (!a && b))

// XOR means the same as OR unless both terms are true:
(a ^ b)                <=> ((a || b) && ! (a && b))

There are of course many others, but these are ones I use most often. It may look complicated, but they are easy to get to know by heart once you start by practicing them.

In your case, if you wanted to see what some possible equivalent statements for:

(! (needsWork && (needsApproval || isAdmin) ))

here are some transformations:

(! (needsWork && (needsApproval || isAdmin) ))   => [push the '!' through the `()`]
(! needsWork || ! (needsApproval || isAdmin) )   => [push the 2nd '!' through the `()`]
(! needsWork || (! needsApproval && ! isAdmin))

but I don't see any real simplification of what you have.

Of course, if checking that any of 3 booleans are false is fine, then your choices are simple

(! needsWork || ! needsApproval || ! isAdmin) => [or pull the `!` outside the `()`]
(! (needsWork  && needsApproval && isAdmin))

if(!(needsWork & needsApproval & isAdmin))
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top