CODEWITHSUNDEEP
javalogictruthtable
Woot4Moo
Woot4Moo

Reputation: 24326

Minimum number of checks to validate a truth table


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.

Upvotes: 1

Views: 468

Answers (3)

Bert F
Bert F

Reputation: 87543

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))

Upvotes: 6

Phil Hunt
Phil Hunt

Reputation: 8541

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

Upvotes: 7

fabmilo
fabmilo

Reputation: 48330

if(!(needsWork & needsApproval & isAdmin))

Upvotes: 2

Related Questions