2.3 Discrete mathematics

2.3.1 Boolean algebras

Source: Perkal

The power set of a set X. Let X b a set and let Ã(X) be the collection of all subsets of X. If X = {x, y}, then Ã(X) = {  Æ, {x}, {y}, {x, y} }.

Perkal: "If we form a subset of X = { x1, x2, ..., xn }, we either include or exclude x1, and then include or exclude x2, and so on. Thus there are 2 choices associated with x1, and then 2 choices associated with x2, and so on. Thus, by the Multiplication Rule, there are 2 x 2 ... x 2 = 2^n subsets of X. Hence |Ã(X)| = 2^|X|. (This is why Ã(X) is called a power set of X.)"

Operations on Ã(X)
Binary
È - union
Ç - intersection

Unary
' - complementation

Special elements
Æ - the empty set
X - the whole or universal set

The structure < Ã(X); È; Ç; ' ; Æ; X > is a Boolean algebra.

Truth tables

(If you know Norwegian, you might want to compare the OR (+) - table to this table in "Logikk og argumentasjon".)

If you let S = { 0, 1 }, define two unary operators + and * on S, where x + y = max{ x, y }, and x * y = min{ x,  y }, then

x y x + y (or) x * y (and)
0 0 0 0
0 1 1 0
1 0 1 0
1 1 1 1

This definition of + and * may seem a bit artificial.  Note that + is the same as OR, and also the same as UNION, and that * is the same as AND, and the same as INTERSECTION. Thinking of + and * in these terms may be a bit more intuitive.   

If you think of 0 as 'false', and 1 as 'true', is "0 AND 1" true? No, something in there is false, so "0 AND 1" is false. But is "0 OR 1" true? Yes, "0 OR 1" is true.

In the Standard True/False Model, the ' is often replaced by a bar over the variable. Hence, when x = 0, x = 1, and when x = 1, x = 0. This is equivalent of writing x = 0, x' = 1, and x = 1, x' = 0.

2.3.1.1 The axioms for Boolean algebra

(a) x + y = y + x + is commutative
(b) x * y = y * x * is commutative
(c) (x + y) + z = x + (y + z) + is associative
(d) (  * y) * z = x * (y * z) * is associative
(e) x + ( y * z ) = (x + y) * (x + z) + distributes over *
(f) x * (y + z) = (x * y) + (x * z) * distributes over +
(g) 0 + x = x 0 is an identity for +
(h) 1 * x = x  1 is an identity for *
(i) x + x = 1 x is a + complement of x
(j) x * x = 0 x is a * complement of x
(k) x + x = x idempotent law for +
(l) x * x = x idempotent law for *
(m) x * (x + y) = x absorption law
(n) x + (x * y) = x absorption law
(o) 0 * x = 0  
(p) 1 + x = 1   
(q) x + y =  x * y  de Morgan's law
(r) x * y = x + y de Morgan's law
(s) x' = x double complement law
(t) (x * y) + (x * y) = x  
(u) (x + y) * (x + y) = x  

2.3.1.2 Duals

All Boolean expressions and equations has a dual, obtained by interchanging + and *, and interchanging 0 and 1. Hence, (k) and (l), (m) and (n), (o) and (p) are duals.

2.3.1.3 Disjunctive Normal Form (DNF)

If you have a variable x, then x and x are called literals. A minterm in the variables x1, x2,...,xn is a Boolean product which contains exactly one of the literals xi and xi for each i = 1,...,n. A minterm is also called an atom or a standard product term. (-Perkal, p. 87)

"A Boolean sum of distinct minterms in the variables x1, x2,..., xn is called a Disjunctive Normal Form (DNF) in the variables x1, x2,..., xn.(...) (A DNF is often referred to as canonical form.)" (-Perkal, p. 87)

2.3.1.4 Karnaugh maps
Sources: Perkal and Tocci

Karnaugh maps provides a visual way of finding a minimal Boolean expression.

Adjacent terms
Remember that xy + xy = x
xy and xy are adjacent terms, because they differ in only one literal, and the differing literal is t in one term and t in the other term.

 

Next: Discrete Maths Logic
Other suggested links: Logic, Logikk og argumentasjon (Norwegian).

Home

 P a b c d e f g h l m p q ³ £Ã
Î Ï Ç È É Ê Ë Ì Í ® ± Û Ü Ý Þ ß å ò ¥Æ

 

 

Maths

Home