#!/usr/bin/env python
# coding: utf-8
# # Boolean logic
# ## Sources
#
# * Hyde, Write Great Code, Volume 1: Understanding the Machine (2004), Chapter 3: Binary Arithmetic and Bit Operations
# * Nisan and Schocken, *The Elements of Computing Systems: Building a Modern Computer from First Principles* (2008), Chapter 1: Boolean Logic
# * Mims, *Workbook I: Basic Electronics, Transistors and Integrated Circuits*, second printing (2013)
# * Mims, *Workbook II: Digital Logic Projects*, second printing (2013)
# ## Boolean algebra
# ### Boolean expressions
#
# $ f(x, y, z) = (x + y) \cdot \overline{z} $
#
# `(x OR y) AND NOT z`
#
# ### Canonical representation
#
# $ f(x, y, z) = \overline{x}y\overline{z} + x\overline{y}\overline{z} + xy\overline{z} $
#
# `((NOT x) AND y AND (NOT z)) OR (x AND (NOT y) AND (NOT z)) OR (x AND y AND (NOT z))`
#
# ### Truth table representation
# In[2]:
def print_truth_table(f, arr):
for row in arr:
print(row, f(*row))
# Evaluate using bitwise operators:
# In[2]:
def foo(x, y, z):
return (~x & y & ~z) | (x & ~y & ~z) | (x & y & ~z);
vals = [ [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1],
[1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1] ]
print_truth_table(foo, vals)
# ## Logical operations on bits
# Four main logical operations are performed on bits:
#
# 1. AND
# 2. OR
# 3. XOR (exclusive or)
# 4. NOT
# ### AND truth table
# | AND | 0 | 1 |
# |-----|---|---|
# | 0 | 0 | 0 |
# | 1 | 0 | 1 |
# ### OR truth table
# | OR | 0 | 1 |
# |----|---|---|
# | 0 | 0 | 1 |
# | 1 | 1 | 1 |
# ### XOR truth table
# If the first or second value, but *not* both, is 1, the result is 1, otherwise the result is zero.
# | XOR | 0 | 1 |
# |-----|---|---|
# | 0 | 0 | 1 |
# | 1 | 1 | 0 |
# ### NOT truth table
# | NOT | 0 | 1 |
# |-----|---|---|
# | | 1 | 0 |
# ## Bitwise (bit-by-bit) operations
# Given two values, operate bitwise on bit zero of both operands, then bit one of both operands, and so on.
# Bitwise logical AND of two 8-bit numbers:
# ```
# 10110101 // Operand 1
# 11101110 // Operand 2
# 10100100 // Result
# ```
# In Python:
# In[18]:
bin(0b10110101 & 0b11101110)
# ### Uses for bitwise logical operations
# #### Check an integer value to see if it is even or odd
# If bit position zero of a binary integer value contains one, that integer is odd; if it contains zero, then that integer is even. Testing bit position zero:
# In[24]:
def bitwise_is_odd(i):
return (i & 1) != 0
# In[26]:
bitwise_is_odd(1)
# In[27]:
bitwise_is_odd(2)
#
# ## The `nand` gate
#
# $\overline{x \cdot y}$
#
# `NOT (x AND y)`
#
# ### Truth table representation: direct
#
# `if a = b = 1 then out = 0 else out = 1`
# In[4]:
def _nand(a, b):
if a == b == 1:
return 0
else:
return 1
vals = [ [0, 0], [0, 1], [1, 0], [1, 1] ]
print_truth_table(_nand, vals)
# ## Basic logic gates
#
# (See also https://en.wikipedia.org/wiki/NAND_logic)
#
# ### Summary
#
# `Not` built with `Nand` (`_n_` prefix refers to `Nand`):
# ```py
# def _n_not(a):
# return _nand(a, a)
# ```
#
# `And` built with `Nand` and `Not`:
# ```py
# def _n_and(a, b):
# return _n_not(_nand(a, b))
# ```
#
# `Or` built with `Nand`, `Not`, and `And`:
# ```py
# def _n_or(a, b):
# return _n_not(_n_and(_nand(a, a), _nand(b, b)))
# ```
# ### Basic logic gates: `not`
#
# $\overline{x}$
#
# `NOT (x)`
#
# Converts its input from 0 to 1 and from 1 to 0.
#
# #### Truth table representation: direct
#
# `if in = 0 then out = 1 else out = 0`
# In[5]:
def _not(a):
if a == 0:
return 1
else:
return 0
vals = [ [0], [1] ]
print_truth_table(_not, vals)
# #### Truth table representation: Nand logic
#
# Joining the inputs of a Nand gate leaves only the NOT gate:
#
# `Not(a) = Nand(a, a)`
# In[5]:
def _n_not(a):
return _nand(a, a)
vals = [ [0], [1] ]
print_truth_table(_n_not, vals)
# #### In HDL (using built-in primitive `Nand` chip)
#
# ```verilog
# /**
# * Not gate:
# * out = not in
# */
#
# CHIP Not {
# IN in;
# OUT out;
#
# PARTS:
#
# // Using built-in primitive Nand chip:
# // Not(a) = Nand(a, a)
# Nand(a = in, b = in, out = out);
# }
# ```
#
# ### Basic logic gates: `and`
#
# $ x \cdot y $
#
# `x AND y`
#
# Returns 1 when both its inputs are 1, else 0.
#
# #### Truth table representation: direct
#
# `if a = b = 1 then out = 1 else out = 0`
# In[7]:
def _and(a, b):
if a == b == 1:
return 1
else:
return 0
vals = [ [0, 0], [0, 1], [1, 0], [1, 1] ]
print_truth_table(_and, vals)
# #### Circuit representation
#
# Two switches connected in series. The LED will only be illuminated if both switches are closed.
# In[2]:
get_ipython().run_cell_magic('HTML', '', "\n")
# #### Truth table representation: Nand logic
#
# `AND = NOT NAND`
#
# `And(a, b) = Not(Nand(a, b))`
# In[6]:
def _n_and(a, b):
return _n_not(_nand(a, b))
vals = [ [0, 0], [0, 1], [1, 0], [1, 1] ]
print_truth_table(_n_and, vals)
# #### In HDL
#
# ```verilog
# /**
# * And gate:
# * out = 1 if (a == 1 and b == 1)
# * 0 otherwise
# */
#
# CHIP And {
# IN a, b;
# OUT out;
#
# PARTS:
#
# // Using built-in primitive Nand chip
# // and previously built Not chip:
# // And(a, b) = Not(Nand(a, b))
# Nand(a = a, b = b, out = c);
# Not(in = c, out = out);
# }
# ```
# ### Basic logic gates: `or`
#
# $ x + y $
#
# `x OR y`
#
# Returns 1 when at least one of its inputs is 1, and 0 otherwise.
#
# #### Truth table representation: direct
#
# `if a = b = 0 then out = 0 else out = 1`
# In[3]:
def _or(a, b):
if a == b == 0:
return 0
else:
return 1
vals = [ [0, 0], [0, 1], [1, 0], [1, 1] ]
print_truth_table(_or, vals)
# #### Circuit representation
#
# Two switches connected in parallel. The LED will be illuminated if either switch is open.
# In[3]:
get_ipython().run_cell_magic('HTML', '', "\n")
# #### Truth table representation: Nand logic
#
# `OR = NOT (NAND AND NAND)`
#
# `Or(a, b) = Not(And(Nand(a, a), Nand(b, b)))`
# In[7]:
def _n_or(a, b):
return _n_not(_n_and(_nand(a, a), _nand(b, b)))
vals = [ [0, 0], [0, 1], [1, 0], [1, 1] ]
print_truth_table(_n_or, vals)
# #### In HDL
#
# ```verilog
# /**
# * Or gate:
# * out = 1 if (a == 1 or b == 1)
# * 0 otherwise
# */
#
# CHIP Or {
# IN a, b;
# OUT out;
#
# PARTS:
#
# // Using built-in primitive Nand chip
# // and previously built Not and And chips:
# // Or(a, b) = Not(And(Nand(a, a), Nand(b, b)))
# Nand(a = a, b = a, out = c);
# Nand(a = b, b = b, out = d);
# And(a = c, b = d, out = e);
# Not(in = e, out = out);
# }
#
# ```
# ### Basic logic gates: `xor`
#
# WORKINGHERE