Boolean_Logic.md

Boolean Logic

Table of Contents

1. Booleans
2. The AND Operator
3. The OR Operator
4. The XOR Operator
5. Binary Full-Adder
6. The NOT Operator
7. The NAND Operator
8. The NOR Operator
9. De Morgan's Theorems
10. Python Logical Operator Precedence
11. Logic Gate Symbols

Python exercises:   PY1   PY2   PY3   PY4   PY5   PY6   PY7   PY8   PY9

Booleans

Boolean values, logic and algebra are named after the British mathematician George Boole (1815-1864).

Booleans can take on only two binary values:

• 0 and 1
• False and True
• FALSE and TRUE
• No and Yes
• Off and On

Boolean logic can easily be implemented by electronic circuits using transistors and thus forms the basis for all electronic computers.

Python 1: Booleans are represented either by the integers 0 and 1:

>>> x = 0
>>> y = 1
>>> print('x:', x, 'y:', y, 'and:', x and y, 'or:', x or y, 'xor:', x ^ y)
x: 0 y: 1 and: 0 or: 1 xor: 1

or by the keywords False and True:

>>> x = False
>>> y = True
>>> print('x:', x, 'y:', y, 'and:', x and y, 'or:', x or y, 'xor:', x != y, 'not:', not x)
x: False y: True and: False or: True xor: True not: True

The AND Operator

The Boolean AND operator z = x AND y has the following truth table:

x	y	z
0	0	0
0	1	0
1	0	0
1	1	1

Rule: The output z is 1 (TRUE) only if both inputs x and y are 1 (TRUE).

The AND operation can also be interpreted as the binary multiplication z = x * y.

Python 2: Using the & operator, the AND operation can be applied to two bit arrays x = 0b0011 and y = 0b0101 both having a size of 4 bits to compute the output array z = 0b0001 in the following bit for bit or bitwise manner:

x:  0   0   1   1
   AND AND AND AND
y:  0   1   0   1
   ---------------
z:  0   0   0   1

The single python command below computes this bitwise AND of the two input bit arrays

>>> x = 0b0011
>>> y = 0b0101
>>> format(x & y, '#06b')
'0b0001'

and actually generates all four possible states of the AND truth table listed above.

The auxiliary format parameter#06b controls the output of a minimum of 6 characters, starting with the 0b base-2 prefix (activated by #) and followed by 4 binary bits with leading zeroes (activated by 0).

The following example shows how the AND operator can be used to test the flags at positions 0 and 5 in a bit array by applying a corresponding bit mask:

        7   6   5   4   3   2   1   0
      +---+---+---+---+---+---+---+---+
flags | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
      +---+---+---+---+---+---+---+---+
mask0 |   |   |   |   |   |   |   | 1 |
      +---+---+---+---+---+---+---+---+
mask5 |   |   | 1 |   |   |   |   |   |
      +---+---+---+---+---+---+---+---+

>>> flags = 0b00100110
>>> (flags & 1) != 0          # test flag at position 0
False
>>> (flags & (1 << 5)) != 0   # test flag at position 5
True

The OR Operator

The Boolean OR operator z = x OR y has the following truth table:

x	y	z
0	0	0
0	1	1
1	0	1
1	1	1

Rule: The output z is 1 (TRUE) if at least one of the inputs x and y are 1 (TRUE).

Python 3: Using the | operator, the OR operation can be applied in a bitwise manner to the two bit arrays represented by the integers 0b0011 and 0b0101

>>> x = 0b0011
>>> y = 0b0101
>>> format(x | y, '#06b')
'0b0111'

The following example shows how the OR operator can be used to set the flags at positions 0, 2 and 7 in a bit array by applying a corresponding bit mask:

        7   6   5   4   3   2   1   0
      +---+---+---+---+---+---+---+---+
flags | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
      +---+---+---+---+---+---+---+---+
mask  | 1  |  |   |   |   | 1 |   | 1 |
      +---+---+---+---+---+---+---+---+

>>> flags = 0b00100110
>>> format(flags, '#010b')
'0b00100110'
>>> mask = 1 | (1 << 2) | (1 << 7)
>>> format(mask, '#010b')
'0b10000101'
>>> flags |= mask
>>> format(flags, '#010b')
'0b10100111'

The XOR Operator

The Boolean XOR operator z = x XOR y has the following truth table:

x	y	z
0	0	0
0	1	1
1	0	1
1	1	0

Rule: The output z is 1 (TRUE) if the values of the inputs x and y are differing.

The XOR operation can thus be interpreted as the inequality operation z = x != y.

Therefore x XOR x = 0 and it follows that x XOR y XOR x = y XOR x XOR x = y XOR 0 = y, i.e. y can always be retrieved after XOR-ing it with x, by XOR-ing the result with x again. This property is used e.g. by stream ciphers in crypto devices and data scramblers in communication systems.

Python 4: Using the ^ operator, the XOR operation can be applied in a bitwise manner to the two bit arrays represented by the integers 0b0011 and 0b0101

>>> x = 0b0011
>>> y = 0b0101
>>> format(x ^ y, '#06b')
'0b0110'

A bit array XOR-ed with itself always results in an all-zeroes array

>>> x = 0b0011
>>> format(x ^ x, '#06b')
'0b0000'

The associativity and commutativity properties of the XOR operator are used in the following stream cipher example:

>>> x = 0b0011
>>> y = 0b0101
>>> format(x ^ y ^ x, '#06b')
'0b0101'

The plaintext bits 0b0101 are encrypted on the transmitting side by the secret cipher stream bits 0b0011 and decrypted on the receiving side by applying the same cipher stream sequence 0b0011 again.

Binary Full-Adder

The binary full-adder digital circuit shown below adds the binary bits A and B plus the carry bit Cin from the previous adder stage. The output is the sum S and the carry bit Cout to be considered by the next adder stage.

The sum is computed as S = Z XOR Cin, using the intermediate sum Z = A XOR B. Apparently the XOR operator is equivalent to the binary addition z = (x + y) mod 2. The output carry is computed as Cout = (Z AND Cin) OR (A AND B) and uses the intermediate sum as well.

The full-adder has the following truth table:

A	B	Cin	Cout	S
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Python 5: We test all states of the full-adder's truth table:

>>> a = 0b00001111
>>> b = 0b00110011
>>> z = a ^ b
>>> cin = 0b01010101
>>> s = z ^ cin
>>> cout = (z & cin) | (a & b)
>>> format(a, '08b')
'00001111'
>>> format(b, '08b')
'00110011'
>>> format(z, '08b')
'00111100'
>>> format(cin, '08b')
'01010101'
>>> format(cout, '08b')
'00010111'
>>> format(s, '08b')
'01101001'

The NOT Operator

The Boolean NOT operator z = NOT x has the following truth table:

x	z
0	1
1	0

Rule: The output z is the inverse or complement of the input x.

Python 6: Using the ~ operator, the NOT operation can be applied in a bitwise manner to the bit array represented by the integer 0b0011

>>> x = 0b0011
>>> format(~x & 0b1111, '#06b')
'0b1100'

Since Python treats the bit array as a signed integer, a bit mask 0b1111 corresponding to the number of elements in the bit array must be applied after the inversion in order to convert the result into an unsigned integer.

The NAND Operator

The Boolean NAND operator z = x NAND y = NOT (x AND y) has the following truth table:

x	y	z
0	0	1
0	1	1
1	0	1
1	1	0

Rule: The output z is 0 (FALSE) only if both inputs x and y are 1 (TRUE).

The NAND operation is equivalent to an inverted AND operation and is implemented by transitor-based NAND gates used in electronic circuitry.

Python 7: Using the ~ and & operators, the NAND operation can be applied in a bitwise manner to the two bit arrays represented by the integers 0b0011 and 0b0101

>>> x = 0b0011
>>> y = 0b0101
>>> format(~(x & y) & 0b1111, '#06b')
'0b1110'

Since Python treats the bit array as a signed integer, a bit mask 0b1111 corresponding to the number of elements in the bit array must be applied after the inversion in order to convert the result into an unsigned integer.

The NOR Operator

The Boolean NOR operator z = x NOR y = NOT (x OR y) has the following truth table:

x	y	z
0	0	1
0	1	0
1	0	0
1	1	0

Rule: The output z is 0 (FALSE) if at least one of the inputs x and y are 1 (TRUE).

The NOR operation is equivalent to an inverted OR operation and is implemented by transitor-based NOR gates used in electronic circuitry.

Python 8: Using the ~ and | operators, the NOR operation can be applied in a bitwise manner to the two bit arrays represented by the integers 0b0011 and 0b0101

>>> x = 0b0011
>>> y = 0b0101
>>> format(~(x | y) & 0b1111, '#06b')
'0b1000'

Since Python treats the bit array as a signed integer, a bit mask 0b1111 corresponding to the number of elements in the bit array must be applied after the inversion in order to convert the result into an unsigned integer.

De Morgan's Theorems

Two theorems formulated by Augustus de Morgan (1806-1871) sometimes allow the simplification of complex Boolean expressions:

• The first DeMorgan theorem states the relationship NOT (x AND y) = (NOT x) OR (NOT y), i.e. the NAND operation is equivalent to the OR operation with inverted inputs.

• The second DeMorgan theorem states the dual relationship NOT (x OR y) = (NOT x) AND (NOT y), i.e. the NOR operation is equivalent to the AND operation with inverted inputs.

Python 9: We implement these two relationships using the bitwise operators &, | and ~ and verify the equality of the left and right side of the expressions using the bitwise inequality operator ^:

>>> x = 0b0011
>>> y = 0b0101
>>> format(~(x & y) ^ (~x | ~y), '#06b')
'0b0000'
>>> format(~(x | y) ^ (~x & ~y), '#06b')
'0b0000'

Python Logical Operator Precedence

The precedence (priority) of the Python logical operators is as follows:

1. () - Parentheses
2. ~ - Bitwise NOT
3. <<, >> - Bitwise shifts
4. & - Bitwise AND
5. ^ - Bitwise XOR
6. | - Bitwise OR
7. ==, != - Comparisons
8. not - Boolean NOT
9. and - Boolean AND
10. or - Boolean OR

If in doubt add additional parentheses!

Logic Gate Symbols

Logic Function	Gate Symbol
NOT
AND
OR
XOR
NAND
NOR

Author: Andreas Steffen CC BY 4.0