Boolean operations using integers

Got it! This site "robinsnyder.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.

The Boolean values are true and false.

In many cases, the integer value 0 is used for false and the integer value 1 is used for true.

Here we look at how common logical operations can be accomplished using integers.

not: negation
and: conjunction
or: disjunction
xor: exclusive or, nonequivalence
eqv: equivalence

For each, an extended truth table will be used to prove that integer expression operations can be used to represent the Boolean operations.

The integer operations used are as follows.

addition using "+"
subtraction using "-"
multiplication using "*"
integer division using "/"
integer remainder using "%"

We need a way to do logical operations of x and y where x and y are integers.

negation: Boolean ! x is integer 1 - x
conjunction: Boolean x & y is integer x * y
disjunction: Boolean x | y is integer x + y - x*y
exclusive or: Boolean x ^ y is integer (x + y) % 2
equality: Boolean x = y is integer (x + y + 1) % 2

To verify the above, check every possible combination. This is done below with an extended truth table proof for each.

$Expression tree for (! X) = (1 - X)$

X | ( ! X ) = ( 1 - X ) ----------------------- 0 | ( 1 0 ) 1 ( 1 1 0 ) 1 | ( 0 1 ) 1 ( 1 0 1 )

$Expression tree for (X & Y) = (X * Y)$

X Y | ( X & Y ) = ( X * Y ) --------------------------- 0 0 | ( 0 0 0 ) 1 ( 0 0 0 ) 0 1 | ( 0 0 1 ) 1 ( 0 0 1 ) 1 0 | ( 1 0 0 ) 1 ( 1 0 0 ) 1 1 | ( 1 1 1 ) 1 ( 1 1 1 )

$Expression tree for (X | Y) = ((X + Y) - (X * Y))$

X Y | ( X | Y ) = ( ( X + Y ) - ( X * Y ) ) ------------------------------------------- 0 0 | ( 0 0 0 ) 1 ( ( 0 0 0 ) 0 ( 0 0 0 ) ) 0 1 | ( 0 1 1 ) 1 ( ( 0 1 1 ) 1 ( 0 0 1 ) ) 1 0 | ( 1 1 0 ) 1 ( ( 1 1 0 ) 1 ( 1 0 0 ) ) 1 1 | ( 1 1 1 ) 1 ( ( 1 2 1 ) 1 ( 1 1 1 ) )

$Expression tree for (X ^ Y) = ((X + Y) % 2)$

X Y | ( X Y ) = ( ( X + Y ) % 2 ) ----------------------------------- 0 0 | ( 0 0 0 ) 1 ( ( 0 0 0 ) 0 2 ) 0 1 | ( 0 1 1 ) 1 ( ( 0 1 1 ) 1 2 ) 1 0 | ( 1 1 0 ) 1 ( ( 1 1 0 ) 1 2 ) 1 1 | ( 1 0 1 ) 1 ( ( 1 2 1 ) 0 2 )

$Expression tree for (X = Y) = ((X + Y + 1) % 2)$

X Y | ( X = Y ) = ( ( ( X + Y ) + 1 ) % 2 ) ------------------------------------------- 0 0 | ( 0 1 0 ) 1 ( ( ( 0 0 0 ) 1 1 ) 1 2 ) 0 1 | ( 0 0 1 ) 1 ( ( ( 0 1 1 ) 2 1 ) 0 2 ) 1 0 | ( 1 0 0 ) 1 ( ( ( 1 1 0 ) 2 1 ) 0 2 ) 1 1 | ( 1 1 1 ) 1 ( ( ( 1 2 1 ) 3 1 ) 1 2 )