Transcript
overview
SWITCHING THEORY
you have read in “introduction to logic design”
Twan Basten Ralph H.J.M. Otten
chapter 1: introduction excluding number systems chapter 2: boolean algebra / combinational circuits
first part: information and digital abstraction combinational devices and networks implementation
Eindhoven University of Technology
second part: boolean algebra proof techniques switching algebra
course 5A050 september-november 2004
information
sensor
discrete level
how much information?
processor
information
actuator
information! for example: voltage (s)
continuous level
sensor
log 2 11 = discrete level 3.46 bits
processor
actuator
information! for example: voltage (s)
10 log = continuous 2 10
33.level 22 bits
0.6713456278 V
0.6713456278 V
between 0.23 and 0.28 becomes 0.25 V
between 0.23 and 0.28 becomes 0.25 V
either 0.0 or 2.5 V
definition: the amount of information is defined to be the base 2 logarithm of all (equally probable) possibilities
binary level
how much information?
either 0.0 or 2.5 V
definition: the amount of information is defined to be the base 2 logarithm of all (equally probable) possibilities
log binary 22 = 1level bit
representation of discrete variables
digital abstraction
example :
a combinational device is an element that has
to distinguish 128 characters for printing (ascii) we need log2128 = 7bits
one or more input terminals for binary valued signals
one output terminal for a binary valued signal
a functional specification,
measure 128 different voltages
send serially 7 binary levels + synchronisation
send parallel 7 binary levels + sync- line
detailing the value at the output for each possible combination of input values
containing at least an upper bound on the evaluation delay, that is, the maximum time needed by the device to produce a valid output for any combination of inputs
digital abstraction the reliable translation between a discrete variable and the approximate value of a continuous variable (voltages)
gates a gate is a combinational device
vin x
v out
V+
functional specification x 0 1
y 1 0
combinational devices more complex combinational devices can be built from simpler devices
but this is an abstraction!
y
logic 0 input voltage
a combinational composition :
v out
a network is a combinational device if it consists of interconnected devices such that
↑
transfer characteristic captures the static behavior of a circuit in response to input states, i.e. the output
logic 1 input voltage
after long enough waiting!
0 the dynamic behavior is the output over time in response to an input change
a timing specification,
→ vin
V+
each node is itself a combinational device
every arc (directed edge) either starts from a designated input or from exactly one output terminal of a device
the circuit contains no directed cycles
combinational devices
number of devices
more complex combinational devices can be built from simpler devices a combinational composition :
a network is a combinational device if it consists of interconnected devices such that
each node is itself a combinational device
every arc (directed edge) either starts from a designated input or from exactly one output terminal of a device
the circuit contains no directed cycles
combinational devices can be hierarchies
how many different combinational devices do exist with n input terminals?
for one input terminal: the truth table has 2 rows for 2 values each →
for two input terminals: the truth table has 4 rows for 2 values each → 16
for three input terminals: the truth table has 8 rows for 2 values each → 256
...........
...........
for n input terminals: n the truth table has 2n rows for 2 values each → 22 Ignores timing and implementation specifics
exponential growth
MOS transistors / switching networks
computer processing 1 billion lines per second (approximately today’s technology)
pMOS transistor gate
nMOS transistor gate
truth table for 64 variables (e.g., an adder for two 32 bit numbers)
4
drain
source
drain
complement
source
when voltage between gate and source exceeds threshold, switch! the transistor is open; otherwise it is closed
500+ years needed for processing the table !!!
switching networks combination is conducting if a AND b is high a
b
combination is conducting if a OR b is high a
b
combination is conducting if a is high AND b is low a
b
gate implementations
overview
vcc pull-up switching network
you have read in “introduction to logic design”
inputs
output pull-down switching network
(n)and-gate
pMOS
duals!
a
b
first part: information and digital abstraction combinational devices and networks implementation
a•b
nMOS a•b
a
second part: boolean algebra proof techniques switching algebra
gnd inverter-gate
chapter 1: introduction excluding number systems chapter 2: boolean algebra / combinational circuits
a
a'
b
George Boole and Claude E. Shannon
1854: G.Boole, "An investigation in the laws of thought"
1854: A. De Morgan, "Formal logic"
an algebraic structure is a set over which operations are defined
1847: G.Boole, "Mathematical analysis of logic"
George Boole (1815-1864)
1938: C.E. Shannon, "A symbolic analysis of relay and switching circuits"
properties are fixed by postulating axioms
the system of axioms should be preferably minimal, consistent and complete
axioms are assumed; theorems have to be proven
proof techniques
1904: E.V. Huntington, "Sets of independent postulates for the algebra of logic" 1910: P. Ehrenfest, "Review of L.Couturat's L'algèbre de la logique"
algebraic structures
producing a counterexample (direct) derivation – a sequence of steps that are (applications of) either axioms or already derived theorems
Claude E. Shannon
reduction to equality reduction to absurdity – assume the contrary and derive a contradiction
exhaustive enumeration induction
– prove a small case, and prove the case n by assuming the case n-1
boole algebra
boole algebra A set B with two operations + and • is a boole algebra iff :
A set B with two operations + and • is a boole algebra iff :
it has at least two distinct elements
the set B is closed under + and •
both operations have an identity element
both operations are commutative
each element has a complement
complement
each operation distributes over the other operation
distributivity
cardinality
∃x ,y∈B [x ≠ y]
closure
∀ x ,y∈B [x • y ∈ B ∧ x + y ∈ B]
closure
identity elements
∃1∈B∀x∈B [x • 1 = x = 1 • x ] ∃0∈B∀x∈B [x + 0 = x = 0 + x ]
identity elements
commutativity
∀ x ,y∈B [x • y = y • x ] ∀ x ,y∈B [x + y = y + x ]
to prove : x + x = x
∀ x ,y∈B [x • y ∈ B ∧ x + y ∈ B]
∃1∈B∀x∈B [x • 1 = x = 1 • x ] ∃0∈B∀x∈B [x + 0 = x = 0 + x ] ∀ x ,y∈B [x • y = y • x ] ∀ x ,y∈B [x + y = y + x ]
∀ x∈B ∃x '∈B [x + x' = 1 ∧ x • x' = 0] ∀ x ,y,z∈B [x • ( y + z ) = (x • y) + (x • z )] ∀ x ,y,z∈B [x + ( y • z ) = (x + y) • (x + z )]
proof : x = x + 0
= x + (x • x' ) = (x + x ) • (x + x' ) = (x + x ) • 1 =x+x
complement
∀ x ,y,z∈B [x • ( y + z ) = (x • y) + (x • z )] distributivity ∀ x ,y,z∈B [x + ( y • z ) = (x + y) • (x + z )] not-operation implicit; no associativity!
theorems x+x = x
axioms :
commutativity
∀ x∈B ∃x '∈B [x + x' = 1 ∧ x • x' = 0]
proof techniques: derivation ∃x ,y∈B [x ≠ y]
cardinality
axioms : ∃x ,y∈B [x ≠ y]
∀ x ,y,z∈B
∀ x ,y∈B [x • y ∈ B ∧ x + y ∈ B]
idempotency absorption
∃1∈B∀x∈B [x • 1 = x = 1 • x ] involution ∃0∈B∀x∈B [x + 0 = x = 0 + x ] associativity ∀ x ,y∈B [x • y = y • x ] ∀ x ,y∈B [x + y = y + x ] de morgan laws
∀ x∈B ∃x '∈B [x + x' = 1 ∧ x • x' = 0] ∀ x ,y,z∈B [x • ( y + z ) = (x • y) + (x • z )] ∀ x ,y,z∈B [x + ( y • z ) = (x + y) • (x + z )]
x+x = x x•x = x
x +1= 1 x•0 = 0 (y • x) + x = x (y + x) • x = x
(x' )' = x ( x + y) + z = x + ( y + z ) ( x • y) • z = x • ( y • z ) (x + y)' = (x' ) • ( y' ) (x • y)' = (x' ) + ( y' )
proof techniques: reduction to absurdity
proof techniques: reduction to absurdity
prove that each operand has exactly one identity
axioms : ∃x ,y∈B [x ≠ y] ∀ x ,y∈B [x • y ∈ B ∧ x + y ∈ B]
to prove : ∃ !1∈B ∀x∈B [x • 1 = x = 1 • x ] proof : suppose 11 and 12 are both identities for • and 11 ≠ 12 then
∃1∈B∀x∈B [x • 1 = x = 1 • x ] ∃0∈B∀x∈B [x + 0 = x = 0 + x ]
12 • 11 = 12 = 11 • 12 11 • 12 = 11 = 12 • 11
∀ x ,y∈B [x • y = y • x ] ∀ x ,y∈B [x + y = y + x ]
11 = 12
contradiction!!!!
∀ x∈B ∃x '∈B [x + x' = 1 ∧ x • x' = 0]
axioms : ∃x ,y∈B [x ≠ y] ∀ x ,y∈B [x • y ∈ B ∧ x + y ∈ B]
∀ x ,y∈B [x • y = y • x ] ∀ x ,y∈B [x + y = y + x ]
∀ x∈B ∃x '∈B [x + x' = 1 ∧ x • x' = 0]
∀ x∈B ∃ !x '∈B [x + x' = 1 ∧ x • x' = 0] ∀ x ,y,z∈B [x • ( y + z ) = (x • y) + (x • z )] ∀ x ,y,z∈B [x + ( y • z ) = (x + y) • (x + z )]
∀ x ,y,z∈B [x • ( y + z ) = (x • y) + (x • z )] ∀ x ,y,z∈B [x + ( y • z ) = (x + y) • (x + z )]
proof techniques: reduction to equality to prove : if x + y = 1 and x • y = 0 then identity complement distributivity
y + 0 = y x ' = x ' +0 y + (x • x' ) = = x'+ (x • y) ( y + x ) • ( y + x' ) =
commutativity ( x + y) • ( y + x' ) = hypothesis
1 • ( y + x' ) =
commutativity
( y + x' ) • 1 =
identity
y + x' =
duality
y = x' identity hypothesis
= (x + x' ) • ( x'+ y) distributivity = (x'+ x ) • ( x'+ y) commutativity = 1 • ( x '+ y) = ( x ' + y) • 1 = x '+ y
= y + x' y = x'
identity identity commutativity
each element in a boole algebra has a unique complement 0' = 1
and
1' = 0
the dual of a proposition concerning a boole algebra is the proposition obtained by exchanging the operators and exchanging the identity elements
x • 0 = 0 by derivation as follows : x • 0 = ( x • 0) + 0 = ( x • 0) + ( x • x ' ) = = ( x • x ' ) + ( x • 0) = x • ( x ' + 0 ) = x • x ' = 0 which gives us by duality : x + 1 = 1
we prove
commutativity
Q.E.D.
corollaries :
∃ !1∈B ∀x∈B [x • 1 = x = 1 • x ] ∃ !0∈B ∀x∈B [x + 0 = x = 0 + x ]
∃1∈B∀x∈B [x • 1 = x = 1 • x ] ∃0∈B∀x∈B [x + 0 = x = 0 + x ]
we prove one absorption law : to prove : x • ( x + y) = x proof : x • ( x + y) = ( x + 0) • ( x + y) = x + (0 • y) = x + 0 = x then, by duality, we also have : x + ( x • y) = x
is associativity an axiom? preferably not, because it can be derived from the other axioms! lemma :
∀a,b,c∈B [b • a = c • a ∧ b • a' = c • a' → b = c ]
b = b • 1 = b • (a + a' ) = (b • a) + (b • a' ) = = (c • a) + (c • a' ) = c • (a + a' ) = c
proof :
use the premisses
is associativity an axiom? lemma :
∀a,b,c∈B [b • a = c • a ∧ b • a' = c • a' → b = c ]
( x + ( y + z )) • x = x absorption
((x + y) + z ) • x
assume:
a=x b = x + ( y + z) c = ( x + y) + z
= x • ((x + y) + z ) = (x • (x + y)) + (x • z ) = x + (x • z) =x
(x + ( y + z )) • x' = ((x + y) + z ) • x' x'•(x + ( y + z )) = = x'•((x + y) + z ) (x'•x ) + ( x'•( y + z )) = = (x'•(x + y)) + (x'•z ) 0 + (x'•( y + z )) = = ((x'•x ) + (x'• y)) + (x'•z ) x'•( y + z )) (x + ( y + z )) • x' = ((x + y) + z ) • x' ( x + ( y + z )) • x = (( x + y ) + z) • x
switching algebra if |B|=2, then B has to be {0,1}, with of course 0' = 1 and 1' = 0
x + y = 1 ⇔ x = 1∨ y = 1 x • y = 1 ⇔ x = 1∧ y = 1
and further, by the identity axioms: note: x
u
y x 0 0 1 1
x
u
x
u
y y 0 1 0 1
u 0 0 0 1
u=x•y
x 0 0 1 1
y 0 1 0 1
u 0 1 1 1
u=x+y
x 0 1
u 1 0
u = x'
the operations • , + and ' of a 2-element boole algebra have to correspond to an AND, OR and NOT gate respectively
CHECK THE AXIOMS!!!
the boole algebra with set cardinality 2 is called switching algebra
= (0 + (x'• y)) + (x'•z ) = x'•( y + z )
x + ( y + z ) = ( x + y) + z
the model switching algebra is a boole algebra, because
0≠1
x ∈B y ∈B x 1 x y x y
x
∧ xy ∈∈BB x x ∧ 0 ≡ xy ≡ xy x 1∧
∈B
cardinality ∈B
closure
x
identity commutativity
0
complement
the model
switching algebra
switching algebra is a boole algebra, because
if |B|=2, then B has to be {0,1}, with of course 0' = 1 and 1' = 0 and further, by the identity axioms:
left 0 0 0 1 1 1 1 1
x+y 0 0 1 1 1 1 1 1
y x z x y z
x+z 0 1 0 1 1 1 1 1 x y z y x
≡ ≡
x 0 0 0 0 1 1 1 1
y 0 0 1 1 0 0 1 1
z 0 1 0 1 0 1 0 1
y•z 0 0 0 1 0 0 0 1
right 0 0 0 1 1 1 1 1
CAUTION: these two properties are only valid in a 2-element boole algebra
switching algebra is an adequate formal system for analyzing and manipulating combinational networks
the operations • , + and ' of a 2-element boole algebra have to correspond to an AND, OR and NOT gate respectively
distributivity
z
proof techniques: exhaustive enumeration proofs by exhaustive enumeration consist of checks for all cases e.g. the de morgan laws for switching algebra: ( x + y )' = x '• y ' x 0 0 1 1
x + y = 1 ⇔ x = 1∨ y = 1 x • y = 1 ⇔ x = 1∧ y = 1
y 0 1 0 1
x+y 0 1 1 1
(x+y)' 1 0 0 0
x' 1 1 0 0
x'•y' 1 0 0 0
y' 1 0 1 0
by duality we immediately have the other de morgan law !
and for many base cases for inductive proofs
shorthand for repeated application of the +-operator
e.g. generalization of the de morgan laws: '
'
n n ∑ xi = ∏ (xi )' i =1 i =1
and
we prove one of the de morgan laws (and obtain the other one by the duality principle) '
to prove :
n n ∑ xi = ∏ (xi )' i =1 i =1
already proven : (base case)
2 2 ∑ xi = ∏ (xi )' i =1 i =1
assume : (ind. hypothesis)
n −1 n −1 ∑ xi = ∏ (xi )' i =1 i =1
'
'
useful when there is a small number of cases to check shorthand for repeated application of the •-operator
proofs by induction
n n ∏ xi = ∑ (xi )' i =1 i =1
by definition '
proof :
base case '
'
induction hypothesis
by definition
n n −1 n −1 n n −1 ∑ xi = ∑ xi + xn = ∑ xi • (xn )' = ∏ (xi )' • (xn )' = ∏ (xi )' i =1 i =1 i =1 i =1 i =1
