By Crama Y., Hammer P.

ISBN-10: 0521847516

ISBN-13: 9780521847513

Show description

Read Online or Download Boolean functions. Theory, algorithms, and applications PDF

Best mathematics books

The Magic of Mathematics: Discovering the Spell of - download pdf or read online

"The Magic of Mathematics" delves into the area of rules, explores the spell that arithmetic casts on our lives, and is helping you find arithmetic the place you least count on it.

Whatever Happened to the Metric System?: How America Kept by John Bemelmans Marciano PDF

The yank commonplace procedure of size is a distinct and strange factor to behold with its esoteric, inconsistent criteria: twelve inches in a foot, 3 toes in a backyard, 16 oz in a pound, 100 pennies to the greenback. For anything as elemental as counting and estimating the area round us, it sort of feels like a complicated device to take advantage of.

Download e-book for iPad: Injecting Illicit Drugs by

Injecting drug use is of significant predicament to either Western and constructing international locations, inflicting wide linked damage at either person and public future health degrees. This ebook presents readers with authoritative and sensible info on injecting drug use and the wellbeing and fitness results of this behaviour. contains topical matters corresponding to needle fixation, transitions to and from injecting, and illicit drug use in criminal settings.

Additional info for Boolean functions. Theory, algorithms, and applications

Sample text

Fm ) (X ∗ ) = ψ(f1 (X ∗ ), f2 (X ∗ ), . . 2) simply boils down to function composition). 3 Duality 13 Boolean functions on B n , then the functions f ∨ g, f ∧ g, and f are defined, for all X∗ ∈ Bn , by (f ∨ g)(X∗ ) = f (X ∗ ) ∨ g(X∗ ), (f ∧ g)(X∗ ) = f (X ∗ ) ∧ g(X∗ ), f (X ∗ ) = f (X ∗ ). 8. The dual of a Boolean function f is the function f d defined by f d (X) = f (X) for all X = (x1 , x2 , . . , xn ) ∈ Bn , where X = (x 1 , x 2 , . . , x n ). 6. Let f be the 2-variable function defined by f (0, 0) = f (0, 1) = f (1, 1) = 1 and f (1, 0) = 0.

5, in particular, may initially seem confusing, since it equates a function with a formal expression, but this notational convention is actually innocuous: It is akin to the convention for real-valued functions of real variables, where it is usual to assimilate a function with its analytical expression and to write, for instance, equalities like f (x, y) = x 2 + 2xy + y 2 = (x + y)2 . 1)), it also naturally leads to the next notion. 6. We say that two Boolean expressions ψ and φ are equivalent if they represent the same Boolean function.

Let f be a Boolean function on Bn , and let k ∈ {1, 2, . . , n}. Then, f (x1 , x2 , . . 15) for all (x1 , x2 , . . , xn ) ∈ Bn . Proof. 15). 15) is often called the Shannon expansion of the function f with respect to xk , by reference to its use by Shannon in [827], although this identity was already well-known to Boole [103]. 11). More interestingly, by applying the Shannon expansion to a function and to its successive restrictions until these restrictions become either 0, or 1, or a literal, we obtain an orthogonal DNF of the function (this is easily proved by induction on n).

Download PDF sample

Boolean functions. Theory, algorithms, and applications by Crama Y., Hammer P.


by Michael
4.4

Rated 4.05 of 5 – based on 6 votes