(3) Tõestame, et +1 on tõene (induktsiooni samm). Matemaatilise induktsiooni meetodi põhjal järeldame, et iga on tõene. Hulga karakteristlik funktsioon Olgu universaalne hulk ja vaatleme tema osahulki . Hulga karakteristlikuks funktsiooniks nimetatakse funktsiooni (): {0,1}, kus ()={1, , 0, . Karakteristlikul funktsioonil on hulgateoreetiliste operatsioonide suhtes järgmised omadused: 1) ()()() 2) ()()1- () 3) ()()()((),()) 4) ()()+()-()()((),()) 5) ()()-()() 6) ()()+()-2()() 7) ×(,)()() Lõplikud ja lõpmatud hulgad Hulkade ekvivalentsus Hulka nimetatakse lõplikuks, kui on tühi või leidub selline 1, et saab seada üksühesesse vastavusse naturaalarvude hulga osahulgaga {1,...,}. Hulka nimetatakse lõpmatuks, kui ta ei ole lõplik.
Meie kursuses käsitletakse lõplikke hulki, mõnikord ka lõpmatuid loenduvaid hulki. Hulgateoreetilised operatsioonid · Hulkade ühend AB={x |(xA)V (xB)} · Hulkade ühisosa (lõige) AB={x |(xA)& (xB) · Hulga täiend A = { x | ( x I ) & ( x A ) }, kus I on nn. universaalhulk. · Hulkade vahe AB={x |(xA)& (xB)} · Hulkade sümmeetriline vahe A B = { x | (( x A ) & ( x B )) V (( x A ) & ( x B )) } Hulga A astmehulgaks 2A nimetatakse hulga A kõigi alamhulkade hulka. Hulgateoreetiliste operatsioonide omadused · Kommutatiivsusseadused AB=B A B = B · Assotsiatiivsusseadused A(BC)=(AB)C 1 A(BC)=(AB)C · Distributiivsusseadused A(BC)=(AB)(AC) A(BC)=(AB)(AC) · De Morgani seadus seadused A B = A B AB = AB · Idempotentsusseadus A=AA=A · Välistatud kolmanda seadused A A = I A A = · Topelttäiendi seadus A =A · = AI=A A=A AI=I · Neeldumisseadused A(AB)=A A( A B)=AB
Hulgateoreetilised operatsioonid Hulkade ühend A B = { x ( x A) V ( x B ) } Hulkade ühisosa (lõige) A B = { x ( x A) & ( x B ) Hulga täiend A = { x ( x I ) & ( x A ) }, kus I on nn. universaalhulk. Hulkade vahe A B = { x ( x A) & ( x B ) } Hulkade sümmeetriline vahe A B = { x (( x A ) & ( x B )) V (( x A ) & ( x B )) } Hulga A astmehulgaks 2A nimetatakse hulga A kõigi alamhulkade hulka. Hulgateoreetiliste operatsioonide omadused Kommutatiivsusseadused A B = B A B = B Assotsiatiivsusseadused A ( B C ) = ( A B ) C A ( B C ) = ( A B ) C Distributiivsusseadused A ( B C ) = ( A B ) ( A C ) A ( B C ) = ( A B ) ( A C ) De Morgani seadus seadused A B A B A B A B Idempotentsusseadus A= A A= A Välistatud kolmanda seadused A A = I A A =
A (x )=0 ja B ( x)=0, A (x)=0 ja B ( x )=1, A ( x )=1 ja B ( x )=0, A ( x)=1 ja B ( x )=1. Siit järeldub, et A ( x )· B (x)=1 A ( x )=1 B ( x)=1 x A x B x A B A B (x )=1, millest omakorda saame, et A (x )· B (x)=0 A B ( x)=0 . Kuna hulgad ja nende karakteristlikud funktsioonid on üksüheses vastavuses, siis saame eeltoodud valemeid kasutada ka hulgateoreetiliste samasuste tõestamiseks. Näide: Olgu U universaalne hulk ja A , B U . Tõestada, et ( A B) '= A ' B' . TÕESTUS Tõestuseks piisab näidata, et (AB)'(x) = A'B'(x) iga x U korral. Fikseerime x U. Rakendades eelmise lause omadusi täiendi, ühisosa ja ühendi kohta saame, (AB)'(x) = 1 - AB(x) = 1 - A(x) · B(x) = (1 - A(x)) + (1 - B(x)) - (1 - A(x)) · (1 - B(x)) = A'(x) + B'(x) - A'B'(x)
annaabi.ee 
