
2.3 Discrete mathematics2.3.1 Boolean algebras
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) Unary Special elements 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
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 algebra2.3.1.2 DualsAll 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

