19Boolean-algbra.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * 化简三个变量的布尔表达式 x z y00110011f(x,y,z)表达式: (x’?y’?z’)? (x’?y?z’)? (x?y’?z’)? (x?y?z’)? (x?y?z) x’ x yz y’z yz’ y’z’ 1 1 1 1 1 0 0 0 z’ So, z’?(x?y) 回到举重裁判的问题 x z y00110011f(x,y,z)x’ x yz y’z yz’ y’z’ 0 0 1 0 1 0 1 1 z’ 简化后的表达式: (y?z)? (x?z)? (x?y) 改进后的电路设计 相应的布尔表达式: (y?z)? (x?z)? (x?y) x y z f(x,y,z) x y z x’ y’ z’ 作业 p.262 12 13 14 16 19 Boole, George (1815-1864) British mathematician and logician. Largely self-educated, Boole in 1849 was appointed Professor of Mathematics at Queens College (now University College), Cork, in Ireland. In 1854, in An Investigation of the Laws of Thought, Boole described an algebraic system that later became known as Boolean algebra, which is of prime importance in the study of pure mathematics and in the design of modern computers. From Microsoft Encatra 2000 “纯数学是布尔在一部他称之为《思维规律》的著 作中发现的” - Bertrand Russell 这样说可能是夸大其词，但是它表明了数学逻辑 及其分支在今天具有的重要程度。布尔以前的其 他人，特别是莱布尼兹和德.摩根，曾经梦想要把 逻辑本身加进代数的领域；布尔把它变成了现实。 - 摘自 贝尔：数学精英 Topological sorting Given poset A with partial order ?,define linear order ? for A: If a?b, then a ?b a b d c g e f a b d e c g f Algorithm for topological sorting step1 choose a minimal element a of A step2 Make a the next entry of SORT and replace A with A-{a} step3 repeat steps 1 and 2 until A={} a b d c g e f a d b c e g f a c g d b e f Hasse Diagrams of Isomorphic Lattices {a,b,c} {a,b} {c} {b,c} {a,c} {b} {a} ? {2,3,5} {2,3} {5} {3,5} {2,5} {3} {2} ? 111 110 001 011 101 010 100 000 Lattice Bn Each element is labeled by a sequence of 0’s and 1’s of length n. For any elements x=a1a2...an, y= b1b2...bn, in Bn (each ai,bi is 0 or 1): x?y iff. ak?bk for k=1,2,...,n. x∧y = c1c2...cn, where ck=min{ ak,bk } x?y = d1d2...dn, where dk=max{ ak,bk } x has a complement x’ = z1z2...zn, where zk=1 if xk=0, and