2.1 Introduction to Boolean Algebras Definition: A bmay operation is an entity which takes two elements (as inputs) and produces a new element. Example: On Z, + , X, etc. are all binary operations. On sets , . are binary operations. On propositions, V, are binary operations. Definition : A unary is an entity which takes one element (as inputs) and produces a new element. Example: On Z, _- )_is a unary operation. On sets , complement is a unary operation. On propositions, is a unary operation. The idea behind "Boolean Algebras" is that we want to get at the heart of the rules that are governing things like "The algebra of sets" or "propositional logic". It turns out that we can see both of these "spaces" as specific examples of a more general construct...2) Given a set S, the power set P(S) forms a Boolean Algebra, where: Definition: Suppose that B is a set containing 2 special elements, which we will denote "_ " and "_O ". Further, suppose that we define two binary + =0 * =1 1= 2 0= 0 c operations "_+ " and "_X ", and one unary operation denoted "_ Then B is said to be a _ Boolean Algebra if the following hold Vx, y, Z E B: e.g. Convince yourself that B4 holds for all sets in P(S). Bl: a ) xty = y+x a ) TUB= T b ) x xy = yx x 6) TAU = T B2: a ) (x ty)+z= x+ (y+z) 3) B = [0,1) forms a Boolean algebra, where: b ) ( x x y ) xz= xx (y xz) max + = MARA X = min 1 = 1 0 = 0 x = 1-> B 3 : a ) x + (y x z) = (x+y) x(x+z) e.g. Convince yourself that B5 holds for this set. b) x x ( y + z ) = (x xy) + (xxz) a ) max El, os = 1 B4: a) x + 0 = x 6 ) min 81, 03 = 0 b) x x 1 = x Remark: For aesthetic purposes, we will often write xy instead of x x y. B5: a) x x' =1 Anything that we can prove using axioms B1-B5, we call a Theorem. For b ) x xx' = 0 example... Theorem: Let B be a Boolean algebra. Then x + x = x Proof: Examples: 1) The set of all propositions form a Boolean Algebra, where: ( B42 ) + = v X = 1 1 = T 0 = F 1= 7 = act XX ( B56) e.g. Convince yourself that B5 holds for all propositions. = Qctic ) (set)(') (B3a) 85 : al pv ( p) = T = (octoc ) ( 1 ) ( B5 a ) 6) pn( p ) = F 7 ( B46)What does the above theorem mean for the three example Boolean Algebras discussed above? 1) TUT = T 2 ) pup = P 3) max 20, 03 = 0 max $1 , 13 = 1 Remark: Boolean "Theorems" correspond to Tautologies_in propositional logic. Definition: Given any formula in a Boolean Algebra, the dual of that formula is given by interchanging _+ and _x , and interchanging _and Q Example: State the dual of x = x + 0. X = JCXI Principle of Duality: The dual of every Theorem is also a Theorem. Example: We proved on the previous page that x = x + x is a Theorem. By the Principle of Duality, we can conclude _X = XXX is also a Theorem. Practice: 3.1 #1, 13, 14, 19 9Math 1271 - Assignment 2 Please submit your assignment at the beginning of class (12:30) on Monday, October 03\". Show all steps in your arguments 1. In class, we introduced the notion ofthe contra/positive. In propositional logic notation, this states: (20 > (1) H (Hi) > HUD Prove that this is a tautology, using a truth table. Hint: Whenever you have a biconditional \"p q", it is often useful to rewrite it as (p > q) A (q > p). 2. Prove the following by contraposition (i.e. State and prove the contrapositive of the following statement): If (3x + 4y) # Q, then x & Qory & Q. 3. Let B be a Boolean Algebra. The following expression is a well-known theorem (i.e. It is true for all x, y E B): x' ty' = (xy)' a) Using the above, prove that x'y' = (x +y)'. (Hint: Your answer should be fairly short, and should not require citing any Boolean Axioms.) b) Recall from Lecture 2.1 that the set of propositions forms a Boolean Algebra. Rewrite the two theorems above using the notation of propositions.c) Let S be a set. Recall from Lecture 2.1 that the power set ?(5) forms a Boolean Algebra. Rewrite the two theorems above using the notation of sets. . Consider the Boolean expression: III III xy'z't' + xy'z't + x y Z t + x y Z t' + x'y'zt' + x'yzt' + x'yz't' a) Find a minimal form for this expression by using a Karnaugh map. b) Draw a circuit to implement this expression, using the fewest number of gates possible. Hint for b): Before drawing you circuit, take your answer in (a), and apply (one of) the theorems from 03, above, to create an equivalent expression that uses less gates. . Prove the following, by contradiction: There does not exist a right triangle where all three side lengths are odd integers