BOOLEAN FUNCTION PROPERTIES - ppt video online download

$ 21.00 · 5 (237) · In stock

Three Special Functions The “Boolean Difference” (or Boolean Derivative) indicates under what conditions f is sensitive to changes in the value of xi and is defined as: The “Smoothing Function” of a Boolean function represents the component of f that is independent of xi and is defined as: The “Consensus” of a Boolean function represents f when all appearances of xi are deleted and is defined as: Smoothing is also called MAX, Consensus is also called MIN. This is different consensus than one discussed before
BOOLEAN FUNCTION PROPERTIES
The Boolean Difference (or Boolean Derivative) indicates under what conditions f is sensitive to changes in the value of xi and is defined as: The Smoothing Function of a Boolean function represents the component of f that is independent of xi and is defined as: The Consensus of a Boolean function represents f when all appearances of xi are deleted and is defined as: Smoothing is also called MAX, Consensus is also called MIN. This is different consensus than one discussed before.
Note: fi(1) means that function f is evaluated with xi = 1. This is the xi –residue , also written as fxi . The xi –residue sets xi = 0, also written as fxi. Example. f(w,x,y,z) = wx + w z , find values of x and z to sensitize circuit to changes in w. fw = x , fw = z z=x=1 or z=x=0 will sensitize circuit to changes in w.
Consensus Function. The Consensus of a Boolean function represents f when all appearances of xi are deleted and is defined as: This is an Instance of Universal Quantification,  Cf  f. EXAMPLE f={10-, -10, 111} f0={1--} f1={--0, 1-1} Cf={1-0, 1-1} (we calculate cofactors about x2)
This is an Instance of Existential Quantification,  EXAMPLE f={10-, -10, 111} f0={1--} f1={--0, 1-1} Sf={1--, --0, 1-1} (about x2)
Single-Rail Logic to Minimize Pins and Interconnect. f is positive unate in a dependent variable xi if xi does not appear in the sum-of-products representation. f is negative unate in a dependent variable xi if xi does not appear in the sum-of-products representation. f is vacuous in a dependent variable xi if neither xi nor xi appears in the sum-of-products representation (otherwise it is essential ) f is mixed or binate in variable xi if it is not possible to write a sum-of-products representation in which xi or x do not appear.
Variable Classification. Essential wxy. Vacuous z. Positive yz. Negative z. Binate wx.
If f = f d, f is said to be a self-dual function. EXAMPLE of self-dual function. f=x y y z  z x f d= x y y z  z x. f d=(x  y) (y  z)(z  x)= x y  y z  z x.  f is a self-dual function. Theorem: There are different self-dual functions of n variables.
Note the Symmetry about the Middle Line for f(x,y,z) and f(x,y,z) Symmetry is an Important Property. Theorem: A function obtained by assigning a self-dual function to a variable of a self-dual function is also self-dual. f (x,y,z ) g(a,b,c) xg( a,b,c ) f ( g( a,b,c ),y,z ) If f ( x1, x2, …, xn ) = f ( x1, x2, …, xn ), then f is self-anti-dual EXAMPLE of self-anti-dual function f ( x, y ) = x  y. ^
A Monotone Increasing function is one that can be Represented with AND and OR gates ONLY - (no inverters) Monotone Increasing functions can be Represented in SOP form with NO Complemented Literals. Monotone Increasing functions are also known as Positive Functions A Monotone Decreasing function is one that can be Represented in SOP form with ALL Complemented literals – Negative Function. A function is Unate if it can be Represented in SOP form with each literal being Complemented OR uncomplemented, but NOT both. EXAMPLES of monotone and unate functions. f(x,y,z)=x y + y z - Monotone Increasing (Unate) g(a,b,c)= ac +b c - Monotone Decreasing (Unate) k(A, B, C)= A B + A C - Unate Function. h(X, Y, Z)= X Y + Y Z - Unate in variables X and Z. - Binate in variable Y.
2n+1 symmetric functions of n variables. If a function does not change when any possible pair of a SUBSET of variables are exchanged, it is said to be partially symmetric Symmetric functions can be synthesized with fewer logic elements. Detection of symmetry is an important and HARD problem in CAD. There are several other types of symmetry – we will examine these in more detail later in class. EXAMPLES of totally symmetric and partially symmetric functions. f(x,y,z) = xy z + xy z  + x yz  - Totally Symmetric. f(x,y,z) = x y z + x yz  + xyz - Partially Symmetric (y,z)
Theorem: (Necessary and Sufficient) If f can be specified by a set of integers {a1, a2, , ak} where 0 ai n such that f = 1, when and only when ai of the variables have a value of 1, then f is totally symmetric. Definition: {a1, a2, , ak} are a-numbers. Definition: A totally symmetric function can be denoted as Sa1a2,,ak (x1, x2, , xn) where S denotes symmetry and. the subscripts, a1, a2, , ak, designate a-numbers and (x1, x2, , xn) are the variables of symmetry.
Then this function has a single a-number = 1. The truth table is:
Consider the function: S0,2(x,y,z) Then this function has two a-numbers, 0 and 2. The truth table is:
Let: M  a set of a-numbers. N  a set of a-numbers. A  the universal set of a-numbers. SM(x1, x2, , xn) + SN(x1, x2, , xn) = SMN(x1, x2, , xn) SM(x1, x2, , xn)  SN(x1, x2, , xn) = SM  N(x1, x2, , xn) SM(x1, x2, , xn) = SA-M(x1, x2, , xn) SN(x1, x2, , xn) = x1 SŇ(0, x2, , xn) + x1 SŇ (1, x2, , xn) where each aiN is replaced by ai-1Ň. SN(x1, x2, , xn) = S N (x1, x2, , xn) where each a-number in N is replaced by n-1.
Examples: S3(x1, x2, x3) + S2,3(x1, x2, x3) = S2.3 (x1, x2, x3) S3(x1, x2, x3)  S2,3(x1, x2, x3) = S3 (x1, x2, x3) S3(x1, x2, x3)  S2,3(x1, x2, x3) = S3(x1, x2, x3)  [S2,3(x1, x2, x3)] + [S3 (x1, x2, x3)]   S2,3(x1, x2, x3) = S3(x1, x2, x3)  S0,1(x1, x2, x3) + S0,1,2 (x1, x2, x3)  S2,3(x1, x2, x3) = S2(x1, x2, x3) x1 S2(x2 , x3) + x1 S1(x2 , x3 ) = x1 S2(x2 , x3) + x1 S2-1(x2, x3) = x1 S2(x2 , x3) + x1 S1(x2, x3) = S2 (x1, x2, x3)
Let: f(x1, x2, x3) = x1 x2  x3  + x1x2  x3 + x1  x2x3. This function is symmetric with respect to: {x1, x2, x3 } OR. {x1 , x2 , x3}
Identification of Symmetry
Naive Way: If all variables are uncomplemented (complemented): Expand to Canonical Form and Count Minterms for Each Possible a-number. If f = 1 all minterms corresponding to an a-number, then that a-number is included in the set. Question: What is the total number of minterms that can exist for an a-number to exist for a function of n variables
f=(1, 2, 4, 7) - Canonical Form – Sum of Minterms - Symmetric. g=(1, 2, 4, 5) - Canonical Form – Sum of Minterms – NOT Symmetric.
f(w,x,y,z)=(0,1,3,5,8,10,11,12,13,15) Column Sums are not Equal. Not Totally Symmetric. What about the function: f(w, x, y, z)
f(w,x,y,z)=(3,5,6,7,9,10,11,12,13,14) S2,3(w, x, y, z) ALSO. S1,2 (w, x, y, z)
The Equality of All Column Sums is NOT a Sufficient Condition for Detection of Total Symmetry. PROOF: We prove this by contradiction. Consider the following function: f(w, x, y, z) = (0,3,5,10,12,15) Clearly, it is NOT symmetric since a=2 is not satisfied, however, all column sums are the same. NOT Totally Symmetric!!!
All co-factors of a symmetric function are also symmetric. When column sums are equal, expand about any variable. Consider fw and fw’ Cofactors NOT symmetric since column sums are unequal. However, can complement variables to obtain symmetry. {x, y} OR {z}
Compute Column Sums. if >2 column sum values  NOT SYMMETRIC. if =2 compare the total with # rows. if same complement columns with smaller column sum. else NOT SYMMETRIC. if =1, compare to ½ # of rows. if equal, go to step 2. if not equal, go to step 3. Compute Row Sums (a-numbers), check for correct values. if values are correct, then SYMMETRY detected. if values are incorrect, then NOT SYMMETRIC.
Compute Row Sums, check for correct numbers. if they are correct  SYMMETRIC. else, expand f about any variable and go to step 1 for each cofactor.
Let (w1, w2, …, wn) be an n-tuple of real-numbered weights and t be a real number called the threshold. Then a threshold function, f, is defined as: x1. w1. x2. w2. f. t. wn. xn.
A 3-input majority function has a value of 1 iff 2 or more variables are 1. Of the 16 Switching Functions of 2 variables, 14 are threshold functions (but not necessarily majority functions) w1 = w2 = -1 t = -0.5 f = x1  x2 All threshold functions are unate. Majority functions are threshold functions where n = 2m+1, t = m+1, w1 = w2 =…= wn = 1, majority functions equal 1 iff more variables are 1 than 0. Majority functions are totally symmetric, monotone increasing and self-dual.
No, since no solution to this set of inequalities. However, two threshold functions could be used to achieve the same result.
All Functions. Unate. Monotone. Threshold. Self-Dual. Majority.
Universal Set of Functions
If an arbitrary logic function is represented by a given set of logic functions, the set is Universal or Complete , Def: Let F = {f1, f2 , , fm } be a set of logic functions. If an arbitrary logic function is realized by a loop-free combinational network using the logic elements that realize function fi (i = 1, 2, . . .,m), then F is universal. Theorem: Let M0 be the set of 0-preserving functions, M1 be the set of 1-preserving functions, M2 be the set of self-dual functions, M3 be the set of monotone increasing functions, and. M4 be the set of linear functions. Then, the set of functions F is universal iff. F  Mi (i = 0,1, 2, 3, 4).
Definitions: 0-Preserving – a function such that f (0, 0, ,0) = 0. 1-Preserving – a function such that f (1, 1, ,1) = 1. Self-Dual – a function f such that f = f d = f  (x1, x 2, …, x  n) Monotone Increasing – a function that can be represented with AND and OR gates ONLY - (no inverters) Linear Function – a function represented by. = a0  a1x1  a2x 2  …  anxn. where ai = 0 or 1. EXAMPLES. Single function examples F = {(xy) } and F = {x y }
f 8= x  y  z, f 9= x , f 10= xy, f 11= x. Examples of Minimal Universal Sets: {f 1}, {f 2, f 3}, {f 2, f 5}, {f 3, f 4}, {f 3, f 6}, {f 4, f 5 , f 7}, {f 5, f 6 , f 7, f 8}, and {f 9, f 10},
22n logic functions of n variables. Much fewer unique functions required when the following operations are allowed: (1) Negation of some variables – complementation of inputs. (2) Permutation – interchanging inputs. (3) Negation of function – complementing the entire function. If an logic function g is derived from a function f by the combination of the above operations, then the function g is NPN Equivalent to f. The set of functions that are NPN-equivalent to the given function f forms an NPN-equivalence class . Also possible to have NP-equivalence by operations (1) and (2) P-equivalence by (2) alone, and N-equivalence by (1), alone.
Classification of Two-Variable Functions
NP-equivalence useful for double rail input logic. NPN-equivalence useful for double rail input logic, where each logic element realizes both a function and its complement.
Consensus function. Unateness of Boolean Functions. Self-Dual Functions. Identification of Symmetry. Threshold Functions. Universal Set of Functions. NPN classification. Classification of 2 variable functions. Classification of 3 variable functions. The concept of equivalence classes. Invent regular symmetric structures for symmetric and threshold functions.