,*apt} #ai ,lattices & ,bool1n ,algebras ,! axioms ( a r+ give /ructure to ! op}a;ns ( addi;n & multiplica;n on a set4 ,h{"e1 we c 3/ruct algebraic /ructures1 "kn z lattices & ,bool1n algebras1 t g5}alize o!r types ( op}a;ns4 ,= example1 ! important op}a;ns on sets >e 9clu.n1 union1 & 9t}sec;n4 ,lattices >e g5}aliza;ns ( ord} rela;ns on algebraic spaces1 s* z set 9clu.n 9 set !ory & 9equal;y 9 ! famili> numb} sy/ems _% `;,n _:1 _% `;,z _:1 _% `;,q _:1 & _% `;,r _:4 ,bool1n algebras g5}alize ! op}a;ns ( 9t}sec;n & union4 ,lattices & ,bool1n algebras h f.d applica;ns 9 logic1 circuit !ory1 & probabil;y4 ,sec;n #ai4a ,lattices ,subsec;n ,"pially ,ord}$ ,sets ,we 2g9 ! /udy ( lattices & ,bool1n algebras by g5}aliz+ ! idea ( 9equal;y4 ,recall t a ~1rela;n on a set #hff .2;,x is a subset ( _% ,x`*,x _:4 ,a rela;n .2;,p on .2;,x is call$ a ~1"pial ~1ord} ( .2;,x if x satisfies ! foll{+ axioms4 #a4 ,! rela;n is ~1reflexive~'3 _% (a, a) `e ,p _: = all _% a `e ,x _:4 #b4 ,! rela;n is ~1antisymmetric~'3 if _% (a, b) `e ,p _: & _% (b, a) `e ,p _:1 !n _% a .k b _:4 #c4 ,! rela;n is ~1transitive~'3 if _% (a, b) `e ,p _: & _% (b, c) `e ,p _:1 !n _% (a, c) `e ,p _:4 ,we w usually write _% a ."k: b _: to m1n _% (a, b) `e ,p _: un.s "s symbol is naturally associat$ ) a "picul> "pial ord}1 s* z _% a "k: b _: ) 9teg}s .2a & .2;b1 or _% ,a _"k ,b _: ) sets .2,a & .2;,b4 ,a set .2;,x tgr ) a "pial ord} _% ."k: _: is call$ a ~1"pially ~1ord}$ ~1set~'1 or ~1poset~'4 #hfg 7777777777777777777777777777777777777777 ,example #ai4a 4 ,! set ( 9teg}s " is a poset ": _% a "k: b _: has ! usual m1n+ = two 9teg}s .2a & .2;b 9 _% `;,z _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,example #ai4b 4 ,let .2;,x 2 any set4 ,we w def9e ! ~1p{} ~1set ( .2;,x to 2 ! set ( all subsets ( .2;,x4 ,we d5ote ! p{} set ( .2;,x by _% `;,p(,x) _:4 ,= example1 let _% ,x .k .(a, b, c.) _:4 ,!n _% `;,p(,x) _: is ! set ( all subsets ( ! set _% .(a, b, c.) _:3 _% _0 .(a.) .(b.) .(c.) .(a, b.) .(a, c.) .(b, c.) .(a, b, c.). _: ,on any p{} set ( a set .2;,x1 set 9clu.n1 _% _"k _:1 is a "pial ord}4 ,we c repres5t ! ord} on #hfh _% .(a, b, c.) _: s*ematically by a diagram s* z ! "o 9 ,figure #ai4c4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,image ,,id3 bool1n-ord}-abc ,descrip;n3 ,a graph ) ! set 3si/+ ( a1 ;b1 ;c at ! top level2 ,! sets "1 "1 & "<;b1 ;c"> at ! second level2 ! ?reee sets 3si/+ ( a1 ;b1 & ;c at ! ?ird level2 & ! empty set at ! f|r? level4 ,figure #ai4c 4 ,"pial ord} on _% `;,p(.(a, b, c.)) _: gggggggggggggggggggggggggggggggggggggggg #hfi ,transcrib} note3 ! image ) ,,id bool1n-ord}-abc 2l;gs "h4 ,replace ? page ) ! 9dep5d5tly g5}at$ tactile image4 #hgj 7777777777777777777777777777777777777777 ,example #ai4d 4 ,let .2;,g 2 a gr|p4 ,! set ( subgr|ps ( .2;,g is a poset1 ": ! "pial ord} is set 9clu.n4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,example #ai4e 4 ,"! c 2 m ?an "o "pial ord} on a "picul> set4 ,we c =m a "pial ord} on _% `;,n _: by _% a ."k: b _: if _% a|b _:4 ,! rela;n is c}ta9ly reflexive s9ce _% a|a _: = all _% a `e `;,n _:4 ,if _% m|n _: & _% n|m _:1 !n _% m .k n _:2 h;e1 ! rela;n is al antisymmetric4 ,! rela;n is transitive1 2c if _% m|n _: & _% n|p _:1 !n _% m|p _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,example #ai4f 4 ,let _% ,x .k .(1, 2, 3, 4, 6, 8, 12, 24.) #hga _: 2 ! set ( divisors ( #bd ) ! "pial ord} def9$ 9 ,example #ai4e4 ,figure #ai4g %{s ! "pial ord} on .2;,x4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,image ,,id3 bool1n-ord}-#bd ,descrip;n3 ,a graph ) #bd at ! top level11 #h & #ab at ! second level1 #d "<3nect$ to #h & #ab"> & #f "<3nect$ to #ab"> at ! ?ird level1 #b "<3nect$ to #d & #f"> & #c "<3nect$ to #f"> at ! f|r? level1 & #a at ! bottom level4 ,figure #ai4g 4 ,a "pial ord} on ! divisors ( #bd gggggggggggggggggggggggggggggggggggggggg #hgb ,transcrib} note3 ! image ) ,,id bool1n-ord}-#bd 2l;gs "h4 ,replace ? page ) ! 9dep5d5tly g5}at$ tactile image4 #hgc ,let .2;,y 2 a subset ( a poset .2;,x4 ,an ele;t .2;u 9 .2;,x is an ~1upp} ~1b.d ( .2;,y if _% a ."k: u _: = e ele;t _% a `e ,y _:4 ,if .2;u is an upp} b.d ( .2;,y s* t _% u ."k: v _: = e o!r upp} b.d .2;v ( .2;,y1 !n .2;u is call$ a ~7l1/ upp} b.d~' or ~1supremum ( .2;,y4 ,an ele;t .2;l 9 .2;,x is sd to 2 a ~1l{} ~1b.d ( .2;,y if _% l ."k: a _: = all _% a `e ,y _:4 ,if .2;l is a l{} b.d ( .2;,y s* t _% k ."k: l _: = e o!r l{} b.d .2;k ( .2;,y1 !n .2;l is call$ a ~7grte/ l{} b.d~' or ~19fimum ( .2;,y4 7777777777777777777777777777777777777777 ,example #ai4h 4 ,let _% ,y .k .(2, 3, 4, 6.) _: 2 3ta9$ 9 ! set .2;,x ( ,example #ai4f4 ,!n .2;,y has upp} b.ds #ab & #bd1 ) #ab z a l1/ upp} b.d4 ,! only l{} b.d is #a2 h;e1 x m/ 2 a grte/ l{} b.d4 gggggggggggggggggggggggggggggggggggggggg ,z x turns |1 l1/ upp} b.ds & grte/ l{} b.ds >e unique if !y exi/4 #hgd 7777777777777777777777777777777777777777 ,!orem #ai4i 4 ,let .2;,y 2 a nonempty subset ( a poset .2;,x4 ,if .2;,y has a l1/ upp} b.d1 !n .2;,y has a unique l1/ upp} b.d4 ,if .2;,y has a grte/ l{} b.d1 !n .2;,y has a unique grte/ l{} b.d4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,let _% u1 _: & _% u2 _: 2 l1/ upp} b.ds = .2;,y4 ,by ! def9i;n ( ! l1/ upp} b.d1 _% u1 ."k: u _: = all upp} b.ds .2;u ( .2;,y4 ,9 "picul>1 _% u1 ."k: u2 _:4 ,simil>ly1 _% u2 ."k: u1 _:4 ,"!=e1 _% u1 .k u2 _: by antisymmetry4 ,a simil> >gu;t %{ t ! grte/ l{} b.d is unique4 gggggggggggggggggggggggggggggggggggggggg ,on _m posets x is possible to def9e b9>y op}a;ns by us+ ! grte/ l{} b.d & ! l1/ upp} b.d ( two ele;ts4 ,a ~1lattice is a poset .2;,l s* t e pair ( #hge ele;ts 9 .2;,l has a l1/ upp} b.d & a grte/ l{} b.d4 ,! l1/ upp} b.d ( _% a, b `e ,l _: is call$ ! ~1jo9 ( .2a & .2;b & is d5ot$ by _% a`+b _:4 ,! grte/ l{} b.d ( _% a, b `e ,l _: is call$ ! ~1meet ( .2a & .2;b & is d5ot$ by _% a`%b _:4 7777777777777777777777777777777777777777 ,example #ai4aj 4 ,let .2;,x 2 a set4 ,!n ! p{} set ( .2;,x1 _% `;,p(,x) _:1 is a lattice4 ,= two sets .2,a & .2;,b 9 _% `;,p(,x) _:1 ! l1/ upp} b.d ( .2,a & .2;,b is _% ,a.+,b _:4 ,c}ta9ly _% ,a.+,b _: is an upp} b.d ( .2,a & .2;,b1 s9ce _% ,a _"k ,a.+,b _: & _% ,b _"k ,a.+,b _:4 ,if .2;,c is "s o!r set 3ta9+ bo? .2,a & .2;,b1 !n .2;,c m/ 3ta9 _% ,a.+,b _:2 h;e1 _% ,a.+,b _: is ! l1/ upp} b.d ( .2,a & .2;,b4 ,simil>ly1 ! grte/ l{} b.d ( .2,a & .2;,b is _% ,a.%,b _:4 gggggggggggggggggggggggggggggggggggggggg #hgf 7777777777777777777777777777777777777777 ,example #ai4aa 4 ,let .2;,g 2 a gr|p & suppose t .2;,x is ! set ( subgr|ps ( .2;,g4 ,!n .2;,x is a poset ord}$ by set-!oretic 9clu.n1 _% _"k _:4 ,! set ( subgr|ps ( .2;,g is al a lattice4 ,if .2;,h & .2;,k >e subgr|ps ( .2;,g1 ! grte/ l{} b.d ( .2;,h & .2;,k is _% ,h.%,k _:4 ,! set _% ,h.+,k _: may n 2 a subgr|p ( .2;,g4 ,we l1ve x z an ex}cise to %{ t ! l1/ upp} b.d ( .2;,h & .2;,k is ! subgr|p g5}at$ by _% ,h.+,k _:4 gggggggggggggggggggggggggggggggggggggggg ,9 set !ory we h c}ta9 dual;y 3di;ns4 ,= example1 by ,de ,morgan's laws1 any /ate;t ab sets t is true ab _% (,a.+,b)' _: m/ al 2 true ab _% ,a~'".%,b' _:4 ,we al h a dual;y pr9ciple = lattices4 7777777777777777777777777777777777777777 ,axiom #ai4ab 4 ,pr9ciple ( ,dual;y4 ,any /ate;t t is true = all lattices rema9s true :5 _% ."k: _: is #hgg replac$ by _% ..1: _: & _% `+ _: & _% `% _: >e 9t}*ang$ "?|t ! /ate;t4 gggggggggggggggggggggggggggggggggggggggg ,! foll{+ !orem tells u t a lattice is an algebraic /ructure ) two b9>y op}a;ns t satisfy c}ta9 axioms4 7777777777777777777777777777777777777777 ,!orem #ai4ac 4 ,if .2;,l is a lattice1 !n ! b9>y op}a;ns _% `+ _: & _% `% _: satisfy ! foll{+ prop}ties = _% a, b, c `e ,l _:4 #a4 ,commutative laws3 _% a`+b .k b`+a _: & _% a`%b .k b`%a _:4 #b4 ,associative laws3 _% a`+(b`+c) .k (a`+b)`+c _: & _% a`%(b`%c) .k (a`%b)`%c _:4 #c4 ,idempot5t laws3 _% a`+a .k a _: & _% a`%a .k a _:4 #d4 ,absorp;n laws3 _% a`+(a`%b) .k a _: & _% a`%(a`+b) .k a _:4 #hgh gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,by ! ,pr9ciple ( ,dual;y1 we ne$ only prove ! f/ /ate;t 9 ea* "p4 "<#a"> ,by def9i;n _% a`+b _: is ! l1/ upp} b.d ( _% .(a, b.) _:1 & _% b`+a _: is ! l1/ upp} b.d ( _% .(b, a.) _:2 h{"e1 _% .(a, b.) .k .(b, a.) _:4 "<#b"> ,we w %{ t _% a`+(b`+c) _: & _% (a`+b)`+c _: >e bo? l1/ upp} b.ds ( _% .(a, b, c.) _:4 ,let _% d .k a`+b _:4 ,!n _% c ."k: d`+c .k (a`+b)`+c _:4 ,we al "k t _% a ."k: a`+b .k d ."k: d`+c .k (a`+b)`+c _: 4 ,a simil> >gu;t demon/rates t _% b ."k: (a`+b)`+c _:4 ,"!=e1 _% (a`+b)`+c _: is an upp} b.d ( _% .(a, b, c.) _:4 ,we n{ ne$ to %{ t _% (a`+b)`+c _: is ! l1/ upp} b.d ( _% .(a, b, c.) _:4 ,let .2;u 2 "s o!r upp} b.d ( _% .(a, b, c.) _:4 ,!n _% a ."k: u _: & _% b ."k: u _:2 #hgi h;e1 _% d .k a`+b ."k: u _:4 ,s9ce _% c ."k: u _:1 x foll{s t _% (a`+b)`+c .k d`+c ."k: u _:4 ,"!=e1 _% (a`+b)`+c _: m/ 2 ! l1/ upp} b.d ( _% .(a, b, c.) _:4 ,! >gu;t t %{s _% a`+(b`+c) _: is ! l1/ upp} b.d ( _% .(a, b, c.) _: is ! same4 ,3sequ5tly1 _% a`+(b`+c) .k (a`+b)`+c _:4 "<#c"> ,! jo9 ( .2a & .2a is ! l1/ upp} b.d ( _% .(a.) _:2 h;e1 _% a`+a .k a _:4 "<#d"> ,let _% d .k a`%b _:4 ,!n _% a ."k: a`+d _:4 ,on ! o!r h&1 _% d .k a`%b ."k: a _:1 & s _% a`+d ."k: a _:4 ,"!=e1 _% a`+(a`%b) .k a _:4 gggggggggggggggggggggggggggggggggggggggg ,giv5 any >bitr>y set .2;,l ) op}a;ns _% `+ _: & _% `% _:1 satisfy+ ! 3di;ns ( ! previ|s !orem1 x is natural to ask :e!r or n ? set comes f "s lattice4 ,! foll{+ !orem says t ? is alw ! case4 7777777777777777777777777777777777777777 ,!orem #ai4ad 4 #hhj ,let .2;,l 2 a nonempty set ) two b9>y op}a;ns _% `+ _: & _% `% _: satisfy+ ! commutative1 associative1 idempot5t1 & absorp;n laws4 ,we c def9e a "pial ord} on .2;,l by _% a ."k: b _: if _% a`+b .k b _:4 ,fur!rmore1 .2;,l is a lattice ) respect to _% ."k: _: if = all _% a, b `e ,l _:1 we def9e ! l1/ upp} b.d & grte/ l{} b.d ( .2a & .2;b by _% a`+b _: & _% a`%b _:1 respectively4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,we f/ %{ t .2;,l is a poset "u _% ."k: _:4 ,s9ce _% a`+a .k a _:1 _% a ."k: a _: & _% ."k: _: is reflexive4 ,to %{ t _% ."k: _: is antisymmetric1 let _% a ."k: b _: & _% b ."k: a _:4 ,!n _% a`+b .k b _: & _% b`+a .k a _:4 ,by ! commutative law1 _% b .k a`+b .k b`+a .k a _:4 ,f9ally1 we m/ %{ t _% ."k: _: is transitive4 ,let _% a ."k: b _: & _% b ."k: c _:4 ,!n _% a`+b .k b _: & #hha _% b`+c .k c _:4 ,?us1 _% a`+c .k a`+(b`+c) .k (a`+b)`+c .k b`+c .k c _: 1 or _% a ."k: c _:4 ,to %{ t .2;,l is a lattice1 we m/ prove t _% a`+b _: & _% a`%b _: >e1 respectively1 ! l1/ upp} & grte/ l{} b.ds ( .2a & .2;b4 ,s9ce _% a .k (a`+b)`%a .k a`%(a`+b) _:1 x foll{s t _% a ."k: a`+b _:4 ,simil>ly1 _% b ."k: a`+b _:4 ,"!=e1 _% a`+b _: is an upp} b.d = .2a & .2;b4 ,let .2;u 2 any o!r upp} b.d ( bo? .2a & .2;b4 ,!n _% a ."k: u _: & _% b ."k: u _:4 ,b _% a`+b ."k: u _: s9ce _% (a`+b)`+u .k a`+(b`+u) .k a`+u .k u _: 4 ,! pro( t _% a`%b _: is ! grte/ l{} b.d ( .2a & .2;b is left z an ex}cise4 gggggggggggggggggggggggggggggggggggggggg ,sec;n #ai4b ,bool1n ,algebras ,let u 9ve/igate ! example ( ! p{} set1 _% `;,p(,x) _:1 ( a set .2;,x m closely4 ,! p{} set is a lattice t #hhb is ord}$ by 9clu.n4 ,by ! def9i;n ( ! p{} set1 ! l>ge/ ele;t 9 _% `;,p(,x) _: is .2;,x xf & ! smalle/ ele;t is _% _0 _:1 ! empty set4 ,= any set .2,a 9 _% `;,p(,x) _:1 we "k t _% ,a.%,x .k ,a _: & _% ,a.+_0 .k ,a _:4 ,? su7e/s ! foll{+ def9i;n = lattices4 ,an ele;t .2,i 9 a poset .2;,x is a ~1l>ge/ ~1ele;t if _% a ."k: ,i _: = all _% a `e ,x _:4 ,an ele;t .2,o is a ~1smalle/ ~1ele;t ( .2;,x if _% ,o ."k: a _: = all _% a `e ,x _:4 ,let .2,a 2 9 _% `;,p(,x) _:4 ,recall t ! comple;t ( .2,a is _% ,a' .k ,x_*,a .k .(x_3x `e ,x and x /`e ,a.) _: 4 ,we "k t _% ,a.+,a' .k ,x _: & _% ,a.%,a' .k _0 _:4 ,we c g5}alize ? example = lattices4 ,a lattice .2;,l ) a l>ge/ ele;t .2,i & a smalle/ ele;t .2,o is ~1comple;t$ if = ea* _% a `e ,l _:1 "! exi/s an _% a' _: s* t _% a`+a' .k ,i _: & _% a`%a' .k ,o _:4 ,9 a lattice .2;,l1 ! b9>y op}a;ns _% `+ _: & _% `% _: satisfy #hhc commutative & associative laws2 h{"e1 !y ne$ n satisfy ! 4tributive law _% a`%(b`+c) .k (a`%b)`+(a`%c)2 _: h{"e1 9 _% `;,p(,x) _: ! 4tributive law is satisfi$ s9ce _% ,a.%(,b.+,c) .k (,a.%,b).+(,a.%,c) _: = _% ,a, ,b, ,c `e `;,p(,x) _:4 ,we w say t a lattice .2;,l is ~14tributive if ! foll{+ 4tributive law holds3 _% a`%(b`+c) .k (a`%b)`+(a`%c) _: = all _% a, b, c `e ,l _:4 7777777777777777777777777777777777777777 ,!orem #ai4ae 4 ,a lattice .2;,l is 4tributive if & only if _% a`+(b`%c) .k (a`+b)`%(a`+c) _: = all _% a, b, c `e ,l _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,let u assume t .2;,l is a 4tributive lattice4 #hhd _% a`+(b`%c) .k `(a`+(a`%c)`)`+(b`%c) .k a`+`((a`%c)`+(b`%c)`) .k a`+`((c`%a)`+(c`%b)`) .k a`+`(c`%(a`+b)`) .k a`+`((a`+b)`%c`) .k `((a`+b)`%a`)`+`((a`+b)`%c`) .k (a`+b)`%(a`+c) _: 4 ,! 3v}se foll{s directly f ! ,dual;y ,pr9ciple4 gggggggggggggggggggggggggggggggggggggggg ,a ~1,bool1n ~1algebra is a lattice .2;,b ) a grte/ ele;t .2,i & a smalle/ ele;t .2,o s* t .2;,b is bo? 4tributive & comple;t$4 ,! p{} set ( .2;,x1 _% `;,p(,x) _:1 is |r prototype = a ,bool1n algebra4 ,z x turns |1 x is al "o ( ! mo/ important ,bool1n algebras4 ,! foll{+ !orem all{s u to "*ize ,bool1n algebras 9 t}ms ( ! b9>y rela;ns _% `+ _: & _% `% _: )|t m5;n ( ! fact t a ,bool1n algebra is a poset4 #hhe 7777777777777777777777777777777777777777 ,!orem #ai4af 4 ,a set .2;,b is a ,bool1n algebra if & only if "! exi/ b9>y op}a;ns _% `+ _: & _% `% _: on .2;,b satisfy+ ! foll{+ axioms4 #a4 _% a`+b .k b`+a _: & _% a`%b .k b`%a _: = _% a, b `e ,b _:4 #b4 _% a`+(b`+c) .k (a`+b)`+c _: & _% a`%(b`%c) .k (a`%b)`%c _: = _% a, b, c `e ,b _:4 #c4 _% a`%(b`+c) .k (a`%b)`+(a`%c) _: & _% a`+(b`%c) .k (a`+b)`%(a`+c) _: = _% a, b, c `e ,b _:4 #d4 ,"! exi/ ele;ts .2,i & .2,o s* t _% a`+,o .k a _: & _% a`%,i .k a _: = all _% a `e ,b _:4 #e4 ,= e _% a `e ,b _: "! exi/s an _% a~'" `e ,b _: s* t _% a`+a' .k ,i _: & _% a`%a' .k ,o _:4 gggggggggggggggggggggggggggggggggggggggg #hhf 7777777777777777777777777777777777777777 ,pro( 4 ,let .2;,b 2 a set satisfy+ "<#a">,-"<#e"> 9 ! !orem4 ,"o ( ! idempot5t laws is satisfi$ s9ce _% a .k a`+,o .k a`+(a`%a~'") .k (a`+a)`%(a`+a~'") .k (a`+a)`%,i .k a`+a _: 4 ,obs}ve t _% ,i`+b .k (b`+b~'")`+b .k (b~'"`+b)`+b .k b~'"`+(b`+b) .k b~'"`+b .k ,i _: 4 ,3sequ5tly1 ! f/ ( ! two absorp;n laws holds1 s9ce _% a`+(a`%b) .k (a`%,i)`+(a`%b) .k a`%(,i`+b) .k a`%,i .k a _: 4 ,! o!r idempot5t & absorp;n laws >e prov5 simil>ly4 ,s9ce .2;,b al #hhg satisfies "<#a">,-"<#c">1 ! 3di;ns ( ,!orem #ai4ad >e met2 "!=e1 .2;,b m/ 2 a lattice4 ,3di;n "<#d"> tells u t .2;,b is a 4tributive lattice4 ,= _% a `e ,b _:1 _% ,o`+a .k a _:2 h;e1 _% ,o ."k: a _: & .2,o is ! smalle/ ele;t 9 .2;,b4 ,to %{ t .2,i is ! l>ge/ ele;t 9 .2;,b1 we w f/ %{ t _% a`+b .k b _: is equival5t to _% a`%b .k a _:4 ,s9ce _% a`+,i .k a _: = all _% a `e ,b _:1 us+ ! absorp;n laws we c det}m9e t _% a`+,i .k (a`%,i)`+,i .k ,i`+(,i`%a) .k ,i _: or _% a ."k: ,i _: = all .2a 9 .2;,b4 ,f9ally1 s9ce we "k t .2;,b is comple;t$ by "<#e">1 .2;,b m/ 2 a ,bool1n algebra4 ,3v}sely1 suppose t .2;,b is a ,bool1n algebra4 ,let .2,i & .2,o 2 ! grte/ & l1/ ele;ts 9 .2;,b1 respectively4 ,if we def9e _% a`+b _: & _% a`%b _: z l1/ upp} & grte/ l{} b.ds ( _% .(a, b.) _:1 !n .2;,b is a ,bool1n algebra by ,!orem #ai4ad1 ,!orem #ai4ae1 & |r hypo!sis4 #hhh gggggggggggggggggggggggggggggggggggggggg ,_m o!r id5tities hold 9 ,bool1n algebras4 ,"s ( ~! id5tities >e li/$ 9 ! foll{+ !orem4 7777777777777777777777777777777777777777 ,!orem #ai4ag 4 ,let .2;,b 2 a ,bool1n algebra4 ,!n #a4 _% a`+,i .k ,i _: & _% a`%,o .k ,o _: = all _% a `e ,b _:4 #b4 ,if _% a`+b .k a`+c _: & _% a`%b .k a`%c _: = _% a, b, c `e ,b _:1 !n _% b .k c _:4 #c4 ,if _% a`+b .k ,i _: & _% a`%b .k ,o _:1 !n _% b .k a' _:4 #d4 _% (a')' .k a _: = all _% a `e ,b _:4 #e4 _% ,i' .k ,o _: & _% ,o' .k ,i _:4 #f4 _% (a`+b)' .k a~'"`%b' _: & _% (a`%b)' .k a~'"`+b' _: "<,de ,morgan's ,laws">4 gggggggggggggggggggggggggggggggggggggggg #hhi 7777777777777777777777777777777777777777 ,pro( 4 ,we w prove only "<#b">4 ,! re/ ( ! id5tities >e left z ex}cises4 ,= _% a`+b .k a`+c _: & _% a`%b .k a`%c _:1 we h _% b .k b`+(b`%a) .k b`+(a`%b) .k b`+(a`%c) .k (b`+a)`%(b`+c) .k (a`+b)`%(b`+c) .k (a`+c)`%(b`+c) .k (c`+a)`%(c`+b) .k c`+(a`%b) .k c`+(a`%c) .k c`+(c`%a) .k c _: 4 gggggggggggggggggggggggggggggggggggggggg ,subsec;n ,f9ite ,bool1n ,algebras ,a ,bool1n algebra is a ~7f9ite ,bool1n algebra~' if x 3ta9s a #hij f9ite numb} ( ele;ts z a set4 ,f9ite ,bool1n algebras >e "picul>ly nice s9ce we c classify !m up to isomorphism4 ,let .2;,b & .2;,c 2 ,bool1n algebras4 ,a bijective map _% .f_3 ,b $o ,c _: is an ~1isomorphism ( ,bool1n algebras if _% f(a`+b) .k f(a)`+f(b) f(a`%b) .k f(a)`%f(b) _: = all .2a & .2;b 9 .2;,b4 ,we w %{ t any f9ite ,bool1n algebra is isomorphic to ! ,bool1n algebra obta9$ by tak+ ! p{} set ( "s f9ite set .2;,x4 ,we w ne$ a few lemmas & def9i;ns 2f we prove ? result4 ,let .2;,b 2 a f9ite ,bool1n algebra4 ,an ele;t _% a `e ,b _: is an ~1atom ( .2;,b if _% a /.k ,o _: & _% a`%b .k a _: = all _% b `e ,b _: ) _% b /.k ,o _:4 ,equival5tly1 .2a is an atom ( .2;,b if "! is no _% b `e ,b _: ) _% b /.k ,o _: 4t9ct f .2a s* t _% ,o ."k: b ."k: a _:4 7777777777777777777777777777777777777777 ,lemma #ai4ah 4 #hia ,let .2;,b 2 a f9ite ,bool1n algebra4 ,if .2;b is a ele;t ( .2;,b ) _% b /.k ,o _:1 !n "! is an atom .2a 9 .2;,b s* t _% a ."k: b _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,if .2;b is an atom1 let _% a .k b _:4 ,o!rwise1 *oose an ele;t _% b1 _:1 n equal to .2,o or .2;b1 s* t _% b1 ."k: b _:4 ,we >e gu>ante$ t ? is possible s9ce .2;b is n an atom4 ,if _% b1 _: is an atom1 !n we >e d"o4 ,if n1 *oose _% b2 _:1 n equal to .2,o or _% b1 _:1 s* t _% b2 ."k: b1 _:4 ,ag1 if _% b2 _: is an atom1 let _% a .k b2 _:4 ,3t9u+ ? process1 we c obta9 a *a9 _% ,o ."k: ''' ."k: b3 ."k: b2 ."k: b1 ."k: b _: 4 ,s9ce .2;,b is a f9ite ,bool1n algebra1 ? *a9 m/ 2 f9ite4 ,t is1 = "s .2;k1 _% b;k _: is an atom4 ,let _% a .k b;k _:4 #hib gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,lemma #ai4ai 4 ,let .2a & .2;b 2 atoms 9 a f9ite ,bool1n algebra .2;,b s* t _% a /.k b _:4 ,!n _% a`%b .k ,o _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,s9ce _% a`%b _: is ! grte/ l{} b.d ( .2a & .2;b1 we "k t _% a`%b ."k: a _:4 ,h;e1 ei _% a`%b .k a _: or _% a`%b .k ,o _:4 ,h{"e1 if _% a`%b .k a _:1 !n ei _% a ."k: b _: or _% a .k ,o _:4 ,9 ei case we h a 3tradic;n 2c .2a & .2;b >e bo? atoms2 "!=e1 _% a`%b .k ,o _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,lemma #ai4bj 4 ,let .2;,b 2 a ,bool1n algebra & _% a, b `e ,b _:4 ,! foll{+ #hic /ate;ts >e equival5t4 #a4 _% a ."k: b _:4 #b4 _% a`%b' .k ,o _:4 #c4 _% a~'"`+b .k ,i _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 "<#a"> _% $33oo _: "<#b">4 ,if _% a ."k: b _:1 !n _% a`+b .k b _:4 ,"!=e1 _% a`%b~'" .k a`%(a`+b)~'" .k a`%(a~'"`%b~'") .k (a`%a~'")`%b~'" .k ,o`%b~'" .k ,o _: 4 "<#b"> _% $33oo _: "<#c">4 ,if _% a`%b' .k ,o _:1 !n _% a~'"`+b .k (a`%b')' .k ,o' .k ,i _:4 "<#c"> _% $33oo _: "<#a">4 ,if #hid _% a~'"`+b .k ,i _:1 !n _% a .k a`%(a~'"`+b) .k (a`%a~'")`+(a`%b) .k ,o`+(a`%b) .k a`%b _: 4 ,?us1 _% a ."k: b _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,lemma #ai4ba 4 ,let .2;,b 2 a ,bool1n algebra & .2;b & .2;c 2 ele;ts 9 .2;,b s* t _% b."k:'\xjcch'c _:4 ,!n "! exi/s an atom _% a `e ,b _: s* t _% a ."k: b _: & _% a."k:'\xjcch'c _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,by ,lemma #ai4bj1 _% b`%c' /.k ,o _:4 ,h;e1 "! exi/s an atom .2a s* t _% a ."k: b`%c' _:4 ,3sequ5tly1 _% a ."k: b _: & #hie _% a."k:'\xjcch'c _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,lemma #ai4bb 4 ,let _% b `e ,b _: & _% a1, ''', a;n _: 2 ! atoms ( .2;,b s* t _% a;i ."k: b _:4 ,!n _% b .k a1`+''' `+a;n _:4 ,fur!rmore1 if _% a, a1, ''', a;n _: >e atoms ( .2;,b s* t _% a ."k: b _:1 _% a;i ."k: b _:1 & _% b .k a`+a1`+''' `+a;n _:1 !n _% a .k a;i _: = "s _% i .k #1, ''', n _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 ,let _% b1 .k a1`+''' `+a;n _:4 ,s9ce _% a;i ."k: b _: = ea* .2i1 we "k t _% b1 ."k: b _:4 ,if we c %{ t _% b ."k: b1 _:1 !n ! lemma is true by antisymmetry4 ,assume _% b."k:'\xjcch'b1 _:4 ,!n "! exi/s an atom .2a s* t _% a ."k: b _: & #hif _% a."k:'\xjcch'b1 _:4 ,s9ce .2a is an atom & _% a ."k: b _:1 we c d$uce t _% a .k a;i _: = "s _% a;i _:4 ,h{"e1 ? is impossible s9ce _% a ."k: b1 _:4 ,"!=e1 _% b ."k: b1 _:4 ,n{ suppose t _% b .k a1`+''' `+a;n _:4 ,if .2a is an atom less ?an .2;b1 _% a .k a`%b .k a`%(a1`+''' `+a;n") .k (a`%a1)`+''' `+(a`%a;n") _: 4 ,b ea* t}m is .2,o or .2a ) _% a`%a;i _: o3urr+ = only "o _% a;i _:4 ,h;e1 by ,lemma #ai4ai1 _% a .k a;i _: = "s .2i4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,!orem #ai4bc 4 ,let .2;,b 2 a f9ite ,bool1n algebra4 ,!n "! exi/s a set .2;,x s* t .2;,b is isomorphic to _% `;,p(,x) _:4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,pro( 4 #hig ,we w %{ t .2;,b is isomorphic to _% `;,p(,x) _:1 ": .2;,x is ! set ( atoms ( .2;,b4 ,let _% a `e ,b _:4 ,by ,lemma #ai4bb1 we c write .2a uniquely z _% a .k a1`+''' `+a;n _: = _% a1, ''', a;n" `e ,x _:4 ,3sequ5tly1 we c def9e a map _% .f_3 ,b $o `;,p(,x) _: by _% f(a) .k f(a1`+''' `+a;n") .k .(a1, ''', a;n".) _: 4 ,cle>ly1 _% .f _: is onto4 ,n{ let _% a .k a1`+''' `+a;n _: & _% b .k b1`+''' `+b;m _: 2 ele;ts 9 .2;,b1 ": ea* _% a;i _: & ea* _% b;i _: is an atom4 ,if _% f(a) .k f(b) _:1 !n _% .(a1, ''', a;n".) .k .(b1, ''', b;m".) _: & _% a .k b _:4 ,3sequ5tly1 _% .f _: is 9jective4 ,! jo9 ( .2a & .2;b is pres}v$ by _% .f _: s9ce #hih _% f(a`+b) .k f(a1`+''' `+a;n"`+b1`+''' `+b;m") .k .(a1, ''', a;n, b1, ''', b;m".) .k .(a1, ''', a;n".).+.(b1, ''', b;m".) .k f(a1`+''' `+a;n").+f(b1`% '''`+b;m") .k f(a).+f(b) _: 4 ,simil>ly1 _% f(a`%b) .k f(a).%f(b) _:4 gggggggggggggggggggggggggggggggggggggggg ,we l1ve ! pro( ( ! foll{+ coroll>y z an ex}cise4 7777777777777777777777777777777777777777 ,coroll>y #ai4bd 4 ,! ord} ( any f9ite ,bool1n algebra m/ 2 _% #2~n _: = "s positive 9teg} .2;n4 gggggggggggggggggggggggggggggggggggggggg ,sec;n #ai4c ,! ,algebra ( ,electrical ,circuits ,! use;l;s ( ,bool1n algebras has 2come 9cr1s+ly app>5t ov} ! pa/ s"eal decades ) ! develop;t ( ! mod}n #hii comput}4 ,! circuit design ( comput} *ips c 2 express$ 9 t}ms ( ,bool1n algebras4 ,9 ? sec;n we w develop ! ,bool1n algebra ( electrical circuits & swit*es2 h{"e1 ~! results c easily 2 g5}aliz$ to ! design ( 9tegrat$ comput} circuitry4 ,a ~1swit* is a device1 locat$ at "s po9t 9 an electrical circuit1 t 3trols ! fl{ ( curr5t "? ! circuit4 ,ea* swit* has two possible /ates3 x c 2 ~1op5~'1 & n all{ ! passage ( curr5t "? ! circuit1 or a x c 2 ~1clos$~'1 & all{ ! passage ( curr5t4 ,~! /ates >e mutually exclusive4 ,we require t e swit* 2 9 "o /ate or ! o!r,-a swit* _c 2 op5 & clos$ at ! same "t4 ,al1 if "o swit* is alw 9 ! same /ate z ano!r1 we w d5ote bo? by ! same lr2 t is1 two swit*es t >e bo? label$ ) ! same lr .2a w alw 2 op5 at ! same "t & clos$ at ! same "t4 ,giv5 two swit*es1 we c 3/ruct two funda;tal types ( circuits4 ,two swit*es .2a & .2;b >e 9 ~1s}ies if !y make up a circuit ( ! type t is illu/rat$ 9 #ijj ,figure #ai4be4 ,curr5t c pass 2t ! t}m9als .2,a & .2;,b 9 a s}ies circuit only if bo? ( ! swit*es .2a & .2;b >e clos$4 ,we w d5ote ? comb9a;n ( swit*es by _% a`%b _:4 ,two swit*es .2a & .2;b >e 9 ~1p>allel if !y =m a circuit ( ! type t appe>s 9 ,figure #ai4bf4 ,9 ! case ( a p>allel circuit1 curr5t c pass 2t .2,a & .2;,b if ei "o ( ! swit*es is clos$4 ,we d5ote a p>allel comb9a;n ( circuits .2a & .2;b by _% a`+b _:4 7777777777777777777777777777777777777777 ,image ,,id3 bool1n-w$ge ,descrip;n3 ,a graph ) a pa? f left to "r t 3nect ,a1 a1 ;b1 & ;,b 9 t ord}4 ,figure #ai4be 4 _% a`%b _: gggggggggggggggggggggggggggggggggggggggg #ija ,transcrib} note3 ! image ) ,,id bool1n-w$ge 2l;gs "h4 ,replace ? page ) ! 9dep5d5tly g5}at$ tactile image4 #ijb 7777777777777777777777777777777777777777 ,image ,,id3 bool1n-p>allel ,descrip;n3 ,a graph f left ot "r t has two pa?s4 ,/>t+ on ! left ,a goes to a on ! top pa? & a goes to ;,b4 ,! second pa? />ts on ! left at ,a & !n goes to ;b on ! bottom pa? & ;b goes to ;,b4 ,figure #ai4bf 4 _% a`+b _: gggggggggggggggggggggggggggggggggggggggg #ijc ,transcrib} note3 ! image ) ,,id bool1n-p>allel 2l;gs "h4 ,replace ? page ) ! 9dep5d5tly g5}at$ tactile image4 #ijd ,we c build m complicat$ electrical circuits | ( s}ies & p>allel circuits by replac+ any swit* 9 ! circuit ) "o ( ~! two funda;tal types ( circuits4 ,circuits 3/ruct$ 9 ? mann} >e call$ ~1s}ies-p>allel ~1circuits~'4 ,we w 3sid} two circuits equival5t if !y act ! same4 ,t is1 if we set ! swit*es 9 equival5t circuits exactly ! same we w obta9 ! same result4 ,= example1 9 a s}ies circuit _% a`%b _: is exactly ! same z _% b`%a _:4 ,notice t ? is exactly ! commutative law = ,bool1n algebras4 ,9 fact1 ! set ( all s}ies-p>allel circuits =ms a ,bool1n algebra "u ! op}a;ns ( _% `+ _: & _% `% _:4 ,we c use diagrams to v}ify ! di6}5t axioms ( a ,bool1n algebra4 ,! 4tributive law1 _% a`%(b`+c) .k (a`%b)`+(a`%c) _:1 is illu/rat$ 9 ,figure #ai4bg4 ,if .2a is a swit*1 !n _% a' _: is ! swit* t is alw op5 :5 .2a is clos$ & alw clos$ :5 .2a is op54 ,a circuit t is alw clos$ is .2,i 9 |r algebra2 a circuit t is #ije alw op5 is .2,o4 ,! laws = _% a`%a' .k ,o _: & _% a`+a' .k ,i _: >e %{n 9 ,figure #ai4bh & ,figure #ai4bi1 respectively4 7777777777777777777777777777777777777777 ,image ,,id3 bool1n-4tributive ,descrip;n3 ,two graphs4 ,! graph on ! left has two pa?s4 a goes to ;b on ! top pa? & a goes to ;c on ! bottom pa?1 af : ! two pa?s rejo94 ,! graph on ! "r al has two pa?s4 ,a s+le pa? splits to two pa?s4 ,on ! top pa? a goes to ;b4 ,on ! bottom pa? a goes to ;c4 ,!n ! two pa?s rejo94 ,figure #ai4bg 4 _% a`%(b`+c) .k (a`%b)`+(a`%c) _: gggggggggggggggggggggggggggggggggggggggg #ijf ,transcrib} note3 ! image ) ,,id bool1n-4tributive 2l;gs "h4 ,replace ? page ) ! 9dep5d5tly g5}at$ tactile image4 #ijg 7777777777777777777777777777777777777777 ,image ,,id3 bool1n-"o-z}o-a ,descrip;n3 ,9 ! graph1 a is goes to to a'4 ,figure #ai4bh 4 _% a`%a' .k ,o _: gggggggggggggggggggggggggggggggggggggggg #ijh ,transcrib} note3 ! image ) ,,id bool1n-"o-z}o-a 2l;gs "h4 ,replace ? page ) ! 9dep5d5tly g5}at$ tactile image4 #iji 7777777777777777777777777777777777777777 ,image ,,id3 bool1n-"o-z}o-;b ,descrip;n3 ,! graph splits 9to two pa?s4 ,! top pa? is a & ! bottom pa? is a' af : ! pa?s rejo94 ,figure #ai4bi 4 _% a`+a' .k ,i _: gggggggggggggggggggggggggggggggggggggggg #iaj ,transcrib} note3 ! image ) ,,id bool1n-"o-z}o-;b 2l;gs "h4 ,replace ? page ) ! 9dep5d5tly g5}at$ tactile image4 #iaa 7777777777777777777777777777777777777777 ,example #ai4cj 4 ,e ,bool1n expres.n repres5ts a swit*+ circuit4 ,= example1 giv5 ! expres.n _% (a`+b)`%(a`+b~'")`%(a`+b) _:1 we c 3/ruct ! circuit 9 ,figure #ai4cc4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,!orem #ai4ca 4 ,! set ( all circuits is a ,bool1n algebra4 gggggggggggggggggggggggggggggggggggggggg ,we l1ve z an ex}cise ! pro( ( ? !orem = ! ,bool1n algebra axioms n yet v}ifi$4 ,we c n{ apply ! te*niques ( ,bool1n algebras to swit*+ !ory4 7777777777777777777777777777777777777777 ,example #ai4cb 4 ,giv5 a complex circuit1 we c n{ apply ! te*niques ( ,bool1n algebra to r$uce x to a simpl} "o4 ,3sid} ! circuit 9 ,figure #ai4cc4 ,s9ce #iab _% (a`+b)`%(a`+b~'")`%(a`+b) .k (a`+b)`%(a`+b)`%(a`+b~'") .k (a`+b)`%(a`+b~'") .k a`+(b`%b~'") .k a`+,o .k a _: 1 we c replace ! m complicat$ circuit ) a circuit 3ta9+ ! s+le swit* .2a & a*ieve ! same func;n4 gggggggggggggggggggggggggggggggggggggggg 7777777777777777777777777777777777777777 ,image ,,id3 bool1n-swit*+ ,descrip;n3 ,a graph f left to "r t splits 9to a top pa? a & bottom pa? ;b & !n rejo9s4 ,! graph 3t9ues & splits 9to a top pa? a & a bottom pa? ;b'1 rejo9s & splits 9to two pa?s1 a & ;b1 & f9ally rejo9s4 ,figure #ai4cc 4 _% (a`+b)`%(a`+b~'")`%(a`+b) _: gggggggggggggggggggggggggggggggggggggggg #iac ,transcrib} note3 ! image ) ,,id bool1n-swit*+ 2l;gs "h4 ,replace ? page ) ! 9dep5d5tly g5}at$ tactile image4 #iad ,sage4 ,sage has a full suite ( func;nal;y = bo? posets & lattices1 all z "p ( xs excell5t support = comb9atorics4 ,"! is ll 9 ? *apt} t _c 2 9ve/igat$ ) ,sage4 ,subsec;n ,hi/orical ,note ,george ,boole "<#ahae,-#ahfd"> 0 ! f/ p}son to /udy lattices4 ,9 #ahdg1 he publi%$ .7,! ,9ve/iga;n ( ! ,laws (.' .1,?"|.'1 a book 9 : he us$ lattices to =malize logic & ! calculus ( proposi;ns4 ,boole 2liev$ t ma!matics 0 ! /udy ( =m r ?an ( 3t5t2 t is1 he 0 n s m* 3c}n$ ) :at he 0 calculat+ z ) h{ he 0 calculat+ x4 ,boole's "w 0 c>ri$ on by 8 fr ,augu/us ,de ,morgan "<#ahjf,-#ahga">4 ,de ,morgan obs}v$ t ! pr9ciple ( dual;y (t5 held 9 set !ory1 z is illu/rat$ by ,de ,morgan's laws = set !ory4 ,he 2liev$1 z did ,boole1 t ma!matics 0 ! /udy ( symbols & ab/ract op}a;ns4 ,set !ory & logic 7 fur!r adv.ed by s* ma!maticians z ,alfr$ ,nor? ,:iteh1d "<#ahfa,-#aidg">1 ,b}tr& ,russell #iae "<#ahgb,-#aigj">1 & ,david ,hilb}t "<#ahfb,-#aidc">4 ,9 .1,pr9cipia .1,ma!matica.'1 ,:iteh1d & ,russell attempt$ to %{ ! 3nec;n 2t ma!matics & logic by ! d$uc;n ( ! natural numb} sy/em f ! rules ( =mal logic4 ,if ! natural numb}s cd 2 det}m9$ f logic xf1 !n s cd m* ( ! re/ ( exi/+ ma!matics4 ,hilb}t attempt$ to build up ma!matics by us+ symbolic logic 9 a way t wd prove ! 3si/5cy ( ma!matics4 ,8 approa* 0 d1lt a mortal bl{ by ,kurt ,g~3odel "<#aijf,-#aigh">1 :o prov$ t "! w alw 2 8undecidable0 problems 9 any su6ici5tly ri* axiomatic sy/em2 t is1 t 9 any ma!matical sy/em ( any 3sequ;e1 "! w alw 2 /ate;ts t c n"e 2 prov5 ei true or false4 ,z (t5 o3urs1 ? basic rese>* 9 pure ma!matics lat} 2came 9disp5sable 9 a wide v>iety ( applica;ns4 ,bool1n algebras & logic h 2come ess5tial 9 ! design ( ! l>ge-scale 9tegrat$ circuitry f.d on td's comput} *ips4 ,sociologi/s h us$ lattices & ,bool1n algebras to #iaf model social hi}>*ies2 biologi/s h us$ !m to describe biosy/ems4 ,r1d+ ,"qs #ai4d ,r1d+ ,"qs #a 4 ,describe su39ctly :at a poset is4 ,d n j li/ ! def9+ prop}ties1 b give a descrip;n t ano!r /ud5t ( algebra :o has n"e se5 a poset mi r1sons :y any 4cus.n ( f9ite ,bool1n algebras mie divisors ( #cj4 ,is ? poset a ,bool1n algebra8 #c 4 ,draw a diagram ( ! lattice ( subgr|ps ( _% `;,z12 _:4 #d 4 ,let .2;,b 2 ! set ( positive 9teg}s t >e divisors ( #baj4 ,def9e an ord} on .2;,b by _% a ."k: b _: if _% a|b _:4 ,prove t .2;,b is a ,bool1n algebra4 ,f9d a set .2;,x s* t .2;,b is isomorphic to _% `;,p(,x) _:4 #e 4 ,prove or 4prove3 _% `;,z _: is a poset "u ! rela;n _% a ."k: b _: if _% a|b _:4 #f 4 #iah ,draw ! swit*+ circuit = ea* ( ! foll{+ ,bool1n expres.ns4 a4 _% (a`+b`+a~'")`%a _: ;b4 _% (a`+b)~'"`%(a`+b) _: ;c4 _% a`+(a`%b) _: ;d4 _% (c`+a`+b)`%c~'"`%(a`+b)' _: #g 4 ,draw a circuit t w 2 clos$ exactly :5 only "o ( ?ree swit*es .2a1 .2;b1 & .2;c >e clos$4 #h 4 ,prove or 4prove t ! two circuits %{n >e equival5t4 ,image ,,id3 ex}cise-equival5t-circuits ,descrip;n3 ,two graphs4 ,! graph on ! left splits 9to ?ree pa?s1 a-;b-;c1 a'-;b1 & a-;c'1 & !n rejo9s4 ,! graph on ! "r splits 9to two pa?s1 a-;b & a-;c'1 & !n rejo9s4 #i 4 ,let .2;,x 2 a f9ite set 3ta9+ .2;n ele;ts4 ,prove t _% |`;,p(,x)| .k #2~n _:4 ,3clude #iai t ! ord} ( any f9ite ,bool1n algebra m/ 2 _% #2~n _: = "s _% n `e `;,n _:4 #aj 4 ,= ea* ( ! foll{+ circuits1 write a ,bool1n expres.n4 ,if ! circuit c 2 replac$ by "o ) few} swit*es1 give ! ,bool1n expres.n & draw a diagram = ! new circuit4 ,image ,,id3 ex}cise-bool1n-circuit ,descrip;n3 ,?ree graphs4 ,! top graph f left to "r is a'1 !n splits 9to a top pa? a-;b' & a on ! bottom & !n rejo9s4 ,! middle graph f left to "r splits 9to two pa?s ) a on ! top pa? & ;b on ! bottom pa?4 ,! graph !n rejo9s & splits 9to ?ree pa?s ) ! top pa? a-;b1 ! middle pa? a'1 & ! bottom pa? a'-;b4 ,! graph !n rejo9s4 ,! bottom graph splits 9to ?ree pa?s ) top pa? a-;b-;c1 middle pa? a'-;b'-;c1 & ! bottom pa? a-;b'-;c'4 ,! pa?s !n rejo94 #aa 4 ,prove or 4prove3 ,! set ( all nonz}o 9teg}s is a lattice1 ": _% a ."k: b _: is def9$ by _% a|b _:4 #ibj #ab 4 ,let .2;,l 2 a nonempty set ) two b9>y op}a;ns _% `+ _: & _% `% _: satisfy+ ! commutative1 associative1 idempot5t1 & absorp;n laws4 ,we c def9e a "pial ord} on .2;,l1 z 9 ,!orem #ai4ad1 by _% a ."k: b _: if _% a`+b .k b _:4 ,prove t ! grte/ l{} b.d ( .2a & .2;b is _% a`%b _:4 #ac 4 ,let .2;,g 2 a gr|p & .2;,x 2 ! set ( subgr|ps ( .2;,g ord}$ by set-!oretic 9clu.n4 ,if .2;,h & .2;,k >e subgr|ps ( .2;,g1 %{ t ! l1/ upp} b.d ( .2;,h & .2;,k is ! subgr|p g5}at$ by _% ,h.+,k _:4 #ad 4 ,let .2;,r 2 a r+ & suppose t .2;,x is ! set ( id1ls ( .2;,r4 ,%{ t .2;,x is a poset ord}$ by set-!oretic 9clu.n1 _% _"k _:4 ,def9e ! meet ( two id1ls .2,i & .2;,j 9 .2;,x by _% ,i.%,j _: & ! jo9 ( .2,i & .2;,j by _% ,i+,j _:4 ,prove t ! set ( id1ls ( .2;,r is a lattice "u ~! op}a;ns4 #iba #ae 4 ,let .2;,b 2 a ,bool1n algebra4 ,prove ea* ( ! foll{+ id5tities4 a4 _% a`+,i .k ,i _: & _% a`%,o .k ,o _: = all _% a `e ,b _:4 ;b4 ,if _% a`+b .k ,i _: & _% a`%b .k ,o _:1 !n _% b .k a' _:4 ;c4 _% (a')' .k a _: = all _% a `e ,b _:4 ;d4 _% ,i' .k ,o _: & _% ,o' .k ,i _:4 ;e4 _% (a`+b)' .k a~'"`%b' _: & _% (a`%b)' .k a~'"`+b' _: "<,de ,morgan's laws">4 #af 4 ,by draw+ ! appropriate diagrams1 complete ! pro( ( ,!orem #ai4ca to %{ t ! swit*+ func;ns =m a ,bool1n algebra4 #ag 4 ,let .2;,b 2 a ,bool1n algebra4 ,def9e b9>y op}a;ns _% + _: & _% * _: on .2;,b by #ibb _% a+b .k (a`%b~'")`+(a~'"`%b) a*b .k a`%b _: 4 ,prove t .2;,b is a commutative r+ "u ~! op}a;ns satisfy+ _% a~2 .k a _: = all _% a `e ,b _:4 #ah 4 ,let .2;,x 2 a poset s* t = e .2a & .2;b 9 .2;,x1 ei _% a ."k: b _: or _% b ."k: a _:4 ,!n .2;,x is sd to 2 a ~1totally ~1ord}$ ~1set~'4 a4 ,is _% a|b _: a total ord} on _% `;,n _:;8 ;b4 ,prove t _% `;,n _:1 _% `;,z _:1 _% `;,q _:1 & _% `;,r _: >e totally ord}$ sets "u ! usual ord}+ _% "k: _:4 #ai 4 ,let .2;,x & .2;,y 2 posets4 ,a map _% .f_3 ,x $o ,y _: is ~1ord}-pres}v+ if _% a ."k: b _: implies t _% f(a) ."k: f(b) _:4 ,let .2;,l & .2;,m 2 lattices4 ,a map #ibc _% .y_3 ,l $o ,m _: is a ~1lattice ~1homomorphism if _% .y(a`+b) .k .y(a)`+.y(b) _: & _% .y(a`%b) .k .y(a)`%.y(b) _:4 ,%{ t e lattice homomorphism is ord}-pres}v+1 b t x is n ! case t e ord}-pres}v+ homomorphism is a lattice homomorphism4 #bj 4 ,let .2;,b 2 a ,bool1n algebra4 ,prove t _% a .k b _: if & only if _% (a`%b~'")`+(a~'"`%b) .k ,o _: = _% a, b `e ,b _:4 #ba 4 ,let .2;,b 2 a ,bool1n algebra4 ,prove t _% a .k ,o _: if & only if _% (a`%b~'")`+(a~'"`%b) .k b _: = all _% b `e ,b _:4 #bb 4 ,let .2;,l & .2;,m 2 lattices4 ,def9e an ord} rela;n on _% ,l`*,m _: by _% (a, b) ."k: (c, d) _: if _% a ."k: c _: & _% b ."k: d _:4 ,%{ t _% ,l`*,m _: is a lattice "u ? "pial ord}4 ,ex}cises #ai4f ,programm+ #ibd ,ex}cises #a 4 ,a ~1,bool1n or ~7swit*+ func;n on~' .2;n ~1v>iables is a map _% f_3 .(,o, ,i.)~n $o .(0, ,i.) _:4 ,a ,bool1n polynomial is a special type ( ,bool1n func;n3 x is any type ( ,bool1n expres.n =m$ f a f9ite comb9a;n ( v>iables _% x1, ''', x;n _: tgr ) .2,o & .2,i1 us+ ! op}a;ns _% `+ _:1 _% `% _:1 & _% ' _:4 ,! values ( ! func;ns >e def9$ 9 ,table #ai4cd4 ,write a program to evaluate ,bool1n polynomials4 7777777777777777777777777777777777777777 ,table #ai4cd 4 ,bool1n polynomials .2;x2 .2;y2 _% x' _:2 _% x`+y _:2 _% x`%y _:4 #j2 #j2 #a2 #j2 #j4 #j2 #a2 #a2 #a2 #j4 #a2 #j2 #j2 #a2 #j4 #a2 #a2 #j2 #a2 #a4 gggggggggggggggggggggggggggggggggggggggg ,ref};es #ai4g ,ref};es & ,su7e/$ ,r1d+s .<#a.> ,donnellan1 ;,t4 ,lattice ,!ory 4 ,p}gamon ,press1 ,ox=d1 #ibe #aifh4 .<#b.> ,halmos1 ;,p4 ;,r4 8,! ,basic ,3cepts ( ,algebraic ,logic10 ,am}ican ,ma!matical ,mon?ly ~1#ec "<#aief">1 #cfc,-#hg4 .<#c.> ,hohn1 ;,f4 8,"s ,ma!matical ,aspects ( ,swit*+10 ,am}ican ,ma!matical ,mon?ly ~1#fb "<#aiee">1 #ge,-#ij4 .<#d.> ,hohn1 ;,f4 ,appli$ ,bool1n ,algebra4 #bnd $4 ,macmillan1 ,new ,york1 #aiff4 .<#e.> ,lidl1 ;,r4 & ,pilz1 ;,g4 ,appli$ ,ab/ract ,algebra4 #bnd $4 ,spr+}1 ,new ,york1 #aiih4 .<#f.> ,:itesitt1 ;,j4 ,bool1n ,algebra & ,xs ,applica;ns4 ,dov}1 ,m9eola1 ,,ny1 #bjaj4 #ibf