Baixe o app para aproveitar ainda mais
Prévia do material em texto
L o´ g ic a e T eo ri a d o s C o n ju n to s F . M ir ag li a Z ar a I. A b u d 1 J u lh o, 19 99 1 P ro fe ss or es d o In st it u to d e M a te m a´t ic a d a U S P , S a˜o P au lo V am os u ti li za r, m u it as ve ze s, a ex p re ss a˜o “s e e so m en te se ”, ab re v ia d a p or “s se ”. E la si gn ifi ca q u e o q u e ve m an te s d el a p o d e se r su b st it u id o p el o q u e es ta´ d ep oi s; q u e to d a ve z q u e u m la d o ac on te ce , o ou tr o ta m b e´m ; e v ic e- ve rs a. T em u n s m oc¸ o m et id o a sa bi do Q u e u sa u m ta r de “s e e so m en te se ” P ’r a di zeˆ co m o as co is a de vi a seˆ . D ep o is de m u it a ex pl ic ac¸ a˜o N ’u m se i p’ ra qu e ta n ta co n fu sa˜ o : E ra so´ fa la´ qu e po de bo ta´ u m n o lu ga´ do ou tr o, O u o ou tr o n o lu ga´ do u m , C on fo rm e go st o ou pr ec is a˜o . C o n te u´ d o P re fa´ ci o 4 I In tr o d u c¸ a˜ o a` T e o ri a d o s C o n ju n to s e a o C a´ lc u lo P ro p o si ci o n a l 5 1 U m P o u co d e T e o ri a d o s C o n ju n to s 6 2 O C a´ lc u lo P ro p o si ci o n a l 1 4 2. 1 A E st ru tu ra P ro p os ic io n al d e u m E n u n ci ad o . . . . . . . . . . . . . . . . . . . 14 2. 2 L in gu ag em F or m al . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2. 3 In te rp re ta c¸o˜ es . L ei s L o´g ic as . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2. 4 F or m as G er ai s d as L ei s L o´g ic as . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2. 5 In te rp re ta c¸o˜ es co m D oi s V al or es . . . . . . . . . . . . . . . . . . . . . . . . . . 43 II R e la c¸ o˜ e s e F u n c¸ o˜ e s 4 8 3 R e la c¸o˜ e s 4 9 3. 1 P ar es O rd en ad os . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3. 2 P ro d u to C ar te si an o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3. 3 R el ac¸ o˜e s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4 F u n c¸ o˜ e s 6 1 4. 1 A D efi n ic¸ a˜o d e F u n c¸a˜ o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4. 2 O p er ac¸ o˜e s co m F am ı´l ia s d e C on ju n to s . . . . . . . . . . . . . . . . . . . . . . . 71 4. 3 Im ag em e Im ag em In ve rs a co m o F u n c¸o˜ es . . . . . . . . . . . . . . . . . . . . . 73 4. 4 P on to s F ix os . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 2 3 4. 5 In fl ac¸ a˜o e D efl ac¸ a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4. 6 P ro d u to s e U n io˜ es D is ju n ta s . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4. 7 F ec h o p or O p er ac¸ o˜e s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4. 8 S u b ob je to s e O b je to s Q u o ci en te s . . . . . . . . . . . . . . . . . . . . . . . . . 10 0 4. 9 F u n c¸o˜ es C ar ac te r´ı st ic as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 4. 10 In d u c¸a˜ o n os N at u ra is . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 0 4. 11 In d u c¸a˜ o n a C om p le x id ad e d e P ro p os ic¸ o˜e s . . . . . . . . . . . . . . . . . . . . . 11 7 4. 12 Q u an ti fi ca d or es em T reˆ s D im en so˜ es . . . . . . . . . . . . . . . . . . . . . . . . 12 5 4. 13 S eq u¨ eˆn ci as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 9 4. 14 O rd en s P ar ci ai s e P ri n c´ı p io s G er ai s d e In d u c¸a˜ o . . . . . . . . . . . . . . . . . . 13 4 4. 15 B oa s O rd en s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6 4. 16 O rd in ai s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 4. 17 B or el ia n os . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6 5 T o p o lo g ia s 1 7 3 5. 1 N oc¸ o˜e s B a´s ic as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3 5. 2 S u p re m os e I´n fi m os . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 8 5. 3 C om p le m en to T op ol o´g ic o e D en si d ad e . . . . . . . . . . . . . . . . . . . . . . . 17 9 5. 4 Im p li ca c¸a˜ o T op ol o´g ic a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 5. 5 L ei s D is tr ib u ti va s . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 5. 6 F u n c¸o˜ es C on t´ı n u as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 6 P re fa´ ci o E st e e´ li v ro e´ u m a te n ta ti va d e co n st ru ir u m ca m in h o q u e le va d a T eo ri a E le m en ta r d os C on ju n to s p ar a as in te rp re ta c¸o˜ es d o In tu ic io n is m o em p re fe ix es so b re to p ol og ia s. N a l´ı n gu a p or tu gu es a. N a˜o p o d em os d iz er q u e te n h a p re re q u is it os , al e´m e´ cl ar o, d e al gu m a m at u ri d ad e in te le ct u al . M es m o as si m , al gu m a fa m il ia ri d ad e co m o co n te u´ d o u su al m en te in cl u´ ıd o n os cu rr´ ıc u lo s d os p ri m ei ro s d oi s an os d a gr ad u ac¸ a˜o em M at ea´ ti ca p o d em a ju d ar . A le it u ra e p ri n ci p al m en te o ap re n d iz ad o ex ig e p a rt ic ip a c¸a˜ o . Id ea lm en te o te x to se rv ir ia co m o ro te ir o d e d es co b er ta p ar a o le it or . H a´ u m a b oa q u an ti d ad e d e in fo rm ac¸ a˜o , co n ce it os e id e´i as es p al h ad as em q u as e to d o lu ga r. A s p ri m ei ra s d u as p ar te s fo ra m ex p er im en ta d as em u m a d is ci p li n a d e T eo ri a d os C on ju n to s m in is tr ad a p or u m d os au to re s n a L ic en ci at u ra n ot u rn a em M at em a´t ic a n a U S P . N os so s m ai s si n ce ro s ag ra d ec im en to s ao s al u n os , q u e fi ze ra m su ge st o˜e s e a ju d ar am n a co rr ec¸ a˜o d e es ti lo e gr afi a. 4 P a rt e I In tr o d u c¸a˜ o a` T e o ri a d o s C o n ju n to s e a o C a´ lc u lo P ro p o si ci o n a l 5 C a p´ ıt u lo 1 U m P o u co d e T e o ri a d o s C o n ju n to s V am os as su m ir q u e o le it or te n h a fa m il ia ri d ad e co m a te or ia el em en ta r d os co n ju n to s, co m o e´ ap re se n ta d a, p or ex em p lo , n o en si n o m e´d io . M es m o as si m , d es en vo lv er em os u m p ou co d es sa te or ia , re gi st ra n d o al gu n s fa to s im p or ta n te s q u e se ra˜ o u ti li za d os co m fr eq u¨ en ci a. A re la c¸a˜ o d e p er ti n eˆn ci a e´ in d ic ad a p or ∈ (e´ p si lo n , o “e ”m in u´ sc u lo cu rt o d o gr eg o1 ). A ex p re ss a˜o “x ∈ A ”s ig n ifi ca “x e´ el em en to d e A ”o u “x p er te n ce a A ”. C om o d e h a´b it o, “x 6∈ A ”q u er d iz er q u e x n a˜o e´ el em en to d e A ou q u e x n a˜o p er te n ce a A . S e A e B sa˜ o co n ju n to s, d iz em os q u e A es ta´ co n ti d o em B ou q u e A e´ su b co n ju n to d e B – e es cr ev em os A ⊆ B – se to d o el em en to d e A e´ el em en to d e B . E m s´ı m b ol os : A ⊆ B ⇐⇒ ︸ ︷︷︸ def ∀ x (x ∈ A −→ x ∈ B ). L em b re -s e q u e d oi s co n ju n to s sa˜ o ig u ai s se , e so m en te se , p os su em os m es m os el em en to s. T al afi rm ac¸ a˜o eq u iv al e a d iz er q u e A = B ⇐⇒ A ⊆ B e B ⊆ A ; es ta p ro p ri ed ad e e´ co n h ec id a co m o A x io m a d a E x te n si on al id ad e. S e P e´ u m a ce rt a p ro p ri ed ad e e A e´ u m co n ju n to , e´ co m u m in d ic ar m os p or {x ∈ A : x sa ti sf az P } o su b co n ju n to d e A fo rm ad o p el os el em en to s q u e ve ri fi ca m a p ro p ri ed ad e P . S e U e´ u m co n ju n to , d en ot am os p or P( U ) o co n ju n to d as p ar te s d e U , is to e´, o co n ju n to cu jo s el em en to s sa˜ o ex at am en te os su b co n ju n to s d e U : P( U ) = {A : A ⊆ U }. A ss im , p ar a to d o co n ju n to A , A ∈ P( U ) ⇐⇒ A ⊆ U , d e m an ei ra q u e A ∈ P( U ) e A ⊆ U sa˜ o afi rm ac¸ o˜e s si n oˆn im as . E n tr e os el em en to s d e P( U ), h a´ d oi s q u e m er ec em d es ta q u e : o co n ju n to va zi o – in d ic ad o p or ∅– e o p ro´ p ri o U ; ∅e´ o m en or 1 O “e ” m in u´ sc u lo lo n go d o gr eg o e´ in d ic ad o p or η , a le tr a “e ta ” 6 7 su b co n ju n to d e U , en q u an to q u e U e´ o m ai or , is to e´ : P ar a to d o A ∈ P( U ), ∅⊆ A ⊆ U . E x e m p lo 1 .1 : a) S ej a U = {0 ,1 ,2 }. Q u em e´ P( U ) ? O s su b co n ju n to s d e U p o d em se r d es cr it os d a se gu in te fo rm a : – S u b co n ju n to s co m 0 (z er o) el em en to s : so´ h a´ u m : o co n ju n to va zi o ∅; – S u b co n ju n to s co m 1 el em en to : {0 }, {1 }, {2 }; – S u b co n ju n to s co m d oi s el em en to s : {0 , 1} , {0 , 2} , {1 , 2} ; – S u b co n ju n to s co m tr eˆs el em en to s : so´ h a´ u m d es te s : o p ro´ p ri o U = {0 ,1 ,2 }. P or ta n to , P( U ) e´ u m co n ju n to co m 8 = 23 el em en to s, d ad o p or : P( U )= {∅ , {0 }, {1 }, {2 }, {0 , 1} , {0 , 2} , {1 , 2} , U }. b ) E se U = ∅? Q u em e´ P( U ) ? A go ra , ∅e´ o u´ n ic o su b co n ju n to d e U . P or ta n to , e´ o u´ n ic o el em en to d e P( U ). A ss im , P( U ) = {∅ }. 3 A s op er ac¸ o˜e s fu n d am en ta is en tr e su b co n ju n to s d e U sa˜ o : – a u n ia˜ o, in d ic ad a p or ∪ : d ad os A , B ⊆ U , A ∪ B = {x ∈ U : x ∈ A ou x ∈ B }; – a in te rs ec¸ a˜o , in d ic ad a p or ∩ : p ar a A , B ⊆ U , A ∩ B = {x ∈ U : x ∈ A e x ∈ B }; – o co m p le m en to : se A ⊆ U , o co m p le m en to d e A em U se es cr ev e co m o U − A , se n d o d efi n id o p or U − A = {x ∈ U : x 6∈ A }. Q u an d o n a˜o h ou ve r p er ig o d e co n fu sa˜ o e o co n ju n to U es ti ve r cl ar o n o co n te x to , es cr ev em os si m p le sm en te A c p ar a in d ic ar U − A . A s tr eˆs op er ac¸ o˜e s so b re co n ju n to s p o d em se r re p re se n ta d as gr afi ca m en te : U & % ' $ A B A a´r ea m ai s es cu ra e´ A ∪ B U & % ' $ A B A a´r ea m ai s es cu ra e´ A ∩ B U & % ' $ A A a´r ea m ai s es cu ra e´ A c D ad o u m co n ju n to U , P( U ) e´ o co n ju n to q u e co n te´ m su b co n ju n to s d e U co m o el em en to s. E q u e d iz er so b re u m co n ju n to q u e co n te n h a to d os os co n ju n to s ? 8 P oi s b em : a ex is teˆ n ci a d e u m ta l co n ju n to or ig in a u m a co n tr ad ic¸ a˜o . E st a ob se rv ac¸ a˜o e´ d ev id a a B er tr an d R u ss el , n o in´ ıc io d es te se´ cu lo , q u an d o tr ab al h av a em C am b ri d ge , n a In gl at er ra , se n d o or ig in a´r ia d e se u es tu d o cr´ ıt ic o d os es cr it os d e G ot tl ob F re ge (u m lo´ gi co al em a˜o m u it o im p or ta n te d o fi n al d o se´ cu lo 19 ). O ar gu m en to e´ u m a b el ez a : T e o re m a 1 .2 : N a˜o ex is te o co n ju n to de to do s os co n ju n to s. P ro v a : S u p on h am os q u e ex is ta o co n ju n to V d e to d os os co n ju n to s. C on si d er e en ta˜ o o se gu in te su b co n ju n to d e V : B = {x ∈ V : x 6∈ x }. A ss im , B e´ u m co n ju n to d efi n id o p el a p ro p ri ed ad e ”x 6∈ x ”. C om o B e´ u m co n ju n to , el e p ro´ p ri o e´ u m el em en to d e V . E x is te m , p oi s, ap en as d u as p os si b il id ad es : ou B ∈ B ou B 6∈ B . Q u al q u er u m a d es sa s h ip o´t es es d a´ or ig em a u m a co n tr ad ic¸ a˜o . S en a˜o , ve ja m os : 1. S e B ∈ B en ta˜ o B sa ti sf a z a p ro p ri ed ad e q u e d efi n e B . C om o es sa p ro p ri ed ad e e´ (x 6∈ x ), co n cl u im os q u e B 6∈ B ! 2. S e B 6∈ B en ta˜ o B n a˜ o sa ti sf a z a p ro p ri ed ad e q u e d efi n e B . L og o, n a˜o e´ ve rd ad e q u e (B 6∈ B ), is to e´, B ∈ B ! Q u al e´ a or ig em d a co n tr ad ic¸ a˜o ? E´ a h ip o´t es e d a ex is teˆ n ci a d o co n ju n to d e to d os os co n ju n to s ! S om os fo rc¸ ad os a co n cl u ir q u e es se ob je to n a˜o p o d e ex is ti r. 3 N o ar gu m en to ac im a, e´ m u it o im p or ta n te q u e B ∈ V ; ca so co n tr a´r io , n a˜o ob te m os co n - tr ad ic¸ a˜o al gu m a : se B 6∈ V , en ta˜ o, co m o B ⊆ V , e´ cl ar o q u e B 6∈ B (s e B n a˜o es ta´ em V , n a˜o p o d e es ta r em n en h u m su b co n ju n to d e V !) ; m as es se ar gu m en to te rm in a a´ı , n a˜o le va n d o a q u al q u er co n cl u sa˜ o in co n si st en te . A id e´i a d a p ro va d o T eo re m a 1. 2 p o d e se r ad ap ta d a p ar a p ro va r ou tr o re su lt ad o in te re ss an te . T e o re m a 1 .3 : S e A e´ u m co n ju n to e B = {x ∈ A : x 6∈ x }e n ta˜ o B ⊆ A e B 6∈ A . P ro v a : P or d efi n ic¸ a˜o , te m os B ⊆ A . S u p on h a ag or a q u e B ∈ A . E n ta˜ o, ou B ∈ B ou B 6∈ B . A d is cu ss a˜o d os ca so s (1 ) e (2 ) n a p ro va d o T eo re m a 1. 2 se ap li ca , ip si s li tt er is , m os tr an d o q u e sa˜ o am b os im p os s´ı ve is . A “b ob ag em ”s o´ ap ar ec eu p or q u e su p u se m os q u e B er a el em en to d e A . L og o, is to d ev e se r fa ls o, o q u e co m p le ta a p ro va . 3 C on si d er e, p or ex em p lo , o co n ju n to A = {2 , {2 }, 3} . T em os q u e {2 }⊆ A (p oi s 2 ∈ A ) e {2 } ∈ A , o q u e si gn ifi ca q u e p o d em ex is ti r su b co n ju n to s d e A q u e sa˜ o ta m b e´m el em en to s d e A . P or su a ve z, {2 , {2 }} ⊆ A , m as {2 , {2 }} 6∈ A . O T eo re m a 1. 3 m os tr a q u e o u´ lt im o fa to q u e ac ab am os d e ci ta r ac on te ce se m p re : d ad o q u al q u er co n ju n to A , se m p re ex is te u m su b co n ju n to d e A q u e n a˜o e´ seu el em en to . S ab en d o d is so , e´ fa´ ci l co n cl u ir q u e n a˜o ex is te o co n ju n to d e to d os os co n ju n to s. S e ex is ti ss e o co n ju n to A d e to d os os co n ju n to s, p ar a el e ta m b e´m va le ri a o T eo re m a 1. 3, e p or ta n to ex is ti ri a B ⊆ A ta l q u e B 6∈ A ; n o en ta n to , co m o A co n te´ m to d os os co n ju n to s, ta m b e´m d ev em os te r B ∈ A . E st a co n tr ad ic¸ a˜o m os tr a q u e o co n ju n to em q u es ta˜ o n a˜o p o d e ex is ti r. O ra ci o c´ı n io q u e ac ab am os d e fa ze r im p li ca q u e o T eo re m a 1. 2 e´ co n se q u¨ eˆn ci a d e 1. 3 : co st u m am os d iz er q u e 1. 3 e´ m ai s fo rt e d o q u e 1. 2, ja´ q u e es te e´ d ec or re n te d aq u el e. A lg u m as p ro p ri ed ad es d e co n ju n to s q u e p re ci sa re m os m ai s ta rd e ap ar ec em n a se gu in te p ro p os ic¸ a˜o . 9 P ro p o si c¸a˜ o 1 .4 : S ej am A , B e C co n ju n to s. a) S e A ⊆ B e B ⊆ C en ta˜ o A ⊆ C . b) A ∩ B ⊆ A e A ∩ B ⊆ B . c) A ⊆ A ∪ B e B ⊆ A ∪ B . d) S e A ⊆ C e B ⊆ C , en ta˜ o A ∪ B ⊆ C . e) S e C ⊆ A e C ⊆ B , en ta˜ o C ⊆ A ∩ B . f) S e A ⊆ B en ta˜ o A ∩ C ⊆ B ∩ C e A ∪ C ⊆ B ∪ C . g) A ⊆ B se e so m en te se A ∩ B = A se e so m en te se A ∪ B = B . P ro v a : a) S u p on h a q u e x e´ u m el em en to d e A . A p ri m ei ra h ip o´t es e (A ⊆ B ) ga ra n te q u e x e´ el em en to d e B , en q u an to q u e a se gu n d a (B ⊆ C ) n os d iz q u e x ∈ C . M os tr am os q u e to d o el em en to d e A ta m b e´m e´ d e C , is to e´, A ⊆ C , co m o d es ej ad o. O s it en s (b ) e (c ) ve m d ir et am en te d a d efi n ic¸ a˜o d e in te rs ec¸ a˜o e u n ia˜ o. d ) S ej a x u m el em en to d e A ∪ B . P el a d efi n ic¸ a˜o d e u n ia˜ o, te m os q u e x ∈ A e / o u x ∈ B . S e x ∈ A en ta˜ o a p ri m ei ra h ip o´t es e (A ⊆ C ) ga ra n te q u e x ∈ C ; se x ∈ B , e´ a se gu n d a h ip o´t es e (B ⊆ C ) q u e ga ra n te q u e x ∈ C . D e to d o m o d o, x d ev e es ta r em C , p ro va n d o q u e A ∪ B ⊆ C . e) S ej a x u m el em en to d e C . A p ri m ei ra h ip o´t es e (C ⊆ A ) ga ra n te q u e x es ta´ em A , en q u an to q u e a se gu n d a (C ⊆ B ) n os d iz q u e x ∈ B . A ss im , x ∈ A ∩ B , co m o q u er´ ıa m os p ro va r. f) V am os fa ze r o ca so d a u n ia˜ o, d ei x an d o a in te rs ec¸ a˜o p ar a o le it or . S u p on h a q u e x ∈ A ∪ C . E n ta˜ o, sa b em os q u e va le x ∈ A e / o u x ∈ C . – S e x ∈ A en ta˜ o A ⊆ B ga ra n te q u e x ∈ B . C om o B ⊆ B ∪ C , ob te m os x ∈ B ∪ C . – S e x ∈ C , co m o C ⊆ B ∪ C , co n cl u´ ım os , ta m b e´m n es te ca so , q u e x ∈ B ∪ C . g) S u p on h a q u e A = A ∩ B . P el o ı´t em b ), A ∩ B ⊆ B . P or ta n to , ob te m os A ⊆ B . A go ra su p on h a B = A ∪ B . D o ı´t em c) , A ⊆ A ∪ B . R es u lt a en ta˜ o q u e A ⊆ B . P ar a te rm in ar a p ro va , fa lt a m os tr ar q u e A ⊆ B im p li ca A = A ∩ B e B = A ∪ B . D ev id o a (b ) e (c ), e´ su fi ci en te m os tr ar q u e A ⊆ A ∩ B e A ∪ B ⊆ B . (I ) P o d em os p ro va r (I ) d ir et am en te ; n o en ta n to , p re fe ri m os u sa r o ı´t em (f ), d an d o u m ex em p lo d e su a u ti li d ad e. C om o A ⊆ B , o ı´t em (f ) ga ra n te q u e, ao to m ar m os a in te rs ec¸ a˜o co m A d os d oi s la d os d es ta re la c¸a˜ o, ob te m os A = A ∩ A ⊆ A ∩ B , ex at am en te a p ri m ei ra re la c¸a˜ o em (I ). D o m es m o m o d o, se to m ar m os a u n ia˜ o co m B d os d oi s la d os d e A ⊆ B e u sa rm os (f ), ob te m os A ∪ B ⊆ B ∪ B = B , 10 q u e e´ a se gu n d a re la c¸a˜ o em (I ). Is to en ce rr a a p ro va . 3 A p ro´ x im a p ro p os ic¸ a˜o n os d iz q u e as op er ac¸ o˜e s d e u n ia˜ o e in te rs ec¸ a˜o sa˜ o co m u ta ti va s e, al e´m d is so , u m a e´ d is tr ib u ti va em re la c¸a˜ o a` ou tr a. P ro p o si c¸a˜ o 1 .5 : S ej am A , B e C co n ju n to s. E n ta˜ o a) A ∩ B = B ∩ A ; A ∪ B = B ∪ A . b) A ∩ (B ∩ C ) = (A ∩ B ) ∩ C ; A ∪ (B ∪ C ) = (A ∪ B ) ∪ C . c) A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C ). d) A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ). e) A ∩ ∅= ∅; A ∪ ∅= A . P ro v a : V am os fa ze r so´ (c ). O s ou tr os ı´t en s sa˜ o se m el h an te s. O q u e p re ci sa m os m os tr ar ? P el a d efi n ic¸ a˜o d e ig u al d ad e, d ev em os p ro va r d u as co is as : i) A ∩ (B ∪ C ) ⊆ (A ∩ B ) ∪ (A ∩ C ); ii ) (A ∩ B ) ∪ (A ∩ C ) ⊆ A ∩ (B ∪ C ). P ro va d e (i ) : S u p on h a q u e x ∈ A ∩ (B ∪ C ); en ta˜ o x es ta´ em A ex es ta´ em B ∪ C . T em os , p or ta n to , d oi s su b -c as os : C as o 1 : x es ta´ em A e x es ta´ em B . Is to si gn ifi ca q u e x ∈ A ∩ B , q u e e´ su b co n ju n to d e (A ∩ B ) ∪ (A ∩ C ); C as o 2 : x es ta´ em A e x ∈ C . N es te ca so , te m os x ∈ A ∩ C , q u e ta m b e´m e´ su b co n ju n to d e (A ∩ B ) ∪ (A ∩ C ). A ss im , em q u al q u er ca so , se x ∈ A ∩ (B ∪ C ), en ta˜ o x e´ el em en to d e (A ∩ B ) ∪ (A ∩ C ), co m p le ta n d o a p ro va d e (i ). P ro va d e (i i) : V am os u ti li za r al gu n s d os re su lt ad os an te ri or es . O b se rv e q u e os ı´t en s (b ) e (c ) d a a P ro p os ic¸ a˜o 1. 4 fo rn ec em A ∩ B ⊆ A e A ∩ B ⊆ B ⊆ B ∪ C . A ss im , p el o ı´t em (e ) d a P ro p os ic¸ a˜o 1. 4, te m os A ∩ B ⊆ A ∩ (B ∪ C ). (I ) D e fo rm a an a´l og a, (b ) e (c ) d a P ro p os ic¸ a˜o 1. 4 n os fo rn ec em A ∩ C ⊆ A e A ∩ C ⊆ C ⊆ B ∪ C . O u tr a ve z, o ı´t em (e ) d a P ro p os ic¸ a˜o 1. 4 ga ra n te q u e A ∩ C ⊆ A ∩ (B ∪ C ). (I I) A go ra , ap li ca n d o o ı´t em (d ) d a P ro p os ic¸ a˜o 1. 4 a`s re la c¸o˜ es (I ) e (I I) , ob te m os (A ∩ B ) ∪ (A ∩ C ) ⊆ A ∩ (B ∪ C ), co m o q u er´ ıa m os p ro va r. 3 11 A lg u m as p ro p ri ed ad es d a co m p le m en ta c¸a˜ o es ta˜ o d es cr it as n a P ro p o si c¸a˜ o 1 .6 : S ej am A e B su bc on ju n to s de u m co n ju n to U . E n ta˜ o a) A ∩ A c = ∅; A ∪ A c = U . b) (A c )c = A . (O co m pl em en to do co m pl em en to de A e´ o pr o´p ri o A .) c) A ⊆ B se e so m en te se A ∩ B c = ∅ se e so m en te se B c ⊆ A c . d) (A ∪ B )c = A c ∩ B c . (O co m pl em en to da u n ia˜ o e´ a in te rs ec¸ a˜o do s co m pl em en to s. ) e) (A ∩ B )c = A c ∪ B c . (O co m pl em en to da in te rs ec¸ a˜o e´ a u n ia˜ o do s co m pl em en to s. ) f) A c ∪ (A ∩ B ) = A c ∪ B . P ro v a : a) P or d efi n ic¸ a˜o , n a˜o p o d e h av er el em en to co m u m a A e ao se u co m p le m en to . L og o, A ∩ A c d ev e se r va zi o. S e x e´ u m el em en to d e U , en ta˜ o ou es ta´ em A ou es ta´ fo ra d e A . N ot e q u e es ta r fo ra d e A (e em U ) si gn ifi ca pe rt en ce r a A c . A ss im , to d o el em en to d e U es ta´ em A ou em A c , o q u e p ro va A ∪ A c = U . b ) Q u em es ta´ fo ra d o co m p le m en to d e A ? E x at am en te os el em en to s d e A . P ro n to ! c) S e A es ta´ co n ti d o em B , to d o el em en to d e A es ta´ em B . P or ta n to , u m el em en to d e A n a˜o p o d e p er te n ce r a B c , e A ∩ B c d ev e se r o co n ju n to va zi o. R ec ip ro ca m en te : su p on h a q u e A ∩ B c = ∅. Is to si gn ifi ca q u e n a˜o h a´ el em en to d e A fo ra d e B ; m as en ta˜ o, d ev em es ta r to d o s em B , is to e´, A ⊆ B . A ou tr a eq u iv al eˆn ci a e´ co n se q u¨ eˆn ci a d a q u e fo i p ro va d a e d o ı´t em (b ) (d es cu b ra co m o) . d ) E st a´ fo ra d a u n ia˜ o d e A co m B ex at am en te q u em es ti ve r fo ra d e A e fo ra d e B ! e) E st a´ fo ra d a in te rs ec¸ a˜o d e A co m B ex at am en te q u em ou n a˜o es ta´ em A ou n a˜o es ta´ em B . f) E´ p os s´ı ve l fa ze r a p ro va m os tr an d o q u e u m la d o es ta´ co n ti d o n o ou tr o e v ic e- ve rs a. V am os se gu ir ou tr o ca m in h o, so´ p ar a va ri ar . P ri m ei ro ob se rv e q u e A c ∪ (A c ∩ B ) = A c , (1 ) p oi s A c ∩ B ⊆ A c (P ro p os ic¸ a˜o 1. 4. (g )) . D e (a ) te m os q u e U = A c ∪ A . (2 ) S e to m am os a in te rs ec¸ a˜o d os d oi s la d os d e (2 ) co m B , a le i d is tr ib u ti va (P ro p os ic¸ a˜o 1. 5. (c )) fo rn ec e B = B ∩ U = B ∩ (A c ∪ A ) = (B ∩ A c ) ∪ (B ∩ A ). (3 ) T om an d o a u n ia˜ o co m A c d os d oi s la d os d e (3 ) e u sa n d o (1 ) ve m A c ∪ B = A c ∪ (A c ∩ B ) ∪ (A ∩ B ) = A c ∪ (A ∩ B ), co m o q u er´ ıa m os m os tr ar . 3 A s P ro p os ic¸ o˜e s 1. 4, 1. 5 e 1. 6 co n te´ m to d a a in fo rm ac¸ a˜o so b re co n ju n to s q u e p re ci sa re m os p ar a d es co b ri r as le is d a L o´g ic a C la´ ss ic a. N o en ta n to , go st ar´ ıa m os d e en ce rr ar es ta se c¸a˜ o m en ci on an d o d u as ou tr as op er ac¸ o˜e s en tr e co n ju n to s, d en om in ad as d if e re n c¸a si m e´ tr ic a e im p li ca c¸a˜ o . 12 P ri m ei ro a d if er en c¸a si m e´t ri ca . D e fi n ic¸ a˜ o 1 .7 : S e A e B sa˜ o su bc on ju n to s de u m co n ju n to U , a di fe re n c¸a si m e´t ri ca en tr e A e B , e´ da da po r “o qu e es ta´ em A e n a˜o es ta´ em B , ju n to co m o qu e es ta´ em B e n a˜o es ta´ em A ”. E m s´ı m bo lo s e di ag ra m as A △ B = (A ∩ B c ) ∪ (B∩ A c ) U & % ' $ A B A a´r ea m ai s es cu ra e´ A △ B Q u al e´ a d is ti n c¸a˜ o en tr e a d if er en c¸a si m e´t ri ca e a u n ia˜ o ? E´ a in te rs ec¸ a˜o ! A in te rs ec¸ a˜o d e d oi s co n ju n to s e´ p ar te d a su a u n ia˜ o m as n a˜o d a su a d if er en c¸a si m e´t ri ca . O b se rv e q u e te m os A ∪ B = (A △ B ) ∪ (A ∩ B ). A d if er en c¸a si m e´t ri ca co rr es p on d e a u m a a lt e rn a ti v a e x cl u si v a , ta m b e´m ch am ad a d e “ ou ex cl u si ve ”. A u n ia˜ o co rr es p on d e a u m a al te rn at iv a q u e in cl u i am b as as p os si b il id ad es , ch am ad a “o u in cl u si ve ”, q u e in d ic am os p el o tr ad ic io n al “e /o u ”d as co n ta s b an ca´ ri as . A lg u m as d as p ro p ri ed ad es fu n d am en ta is d a d if er en c¸a si m e´t ri ca sa˜ o d es cr it as p el a p ro p os ic¸ a˜o ab ai x o, cu ja d em on st ra c¸a˜ o d ei x am os p ar a o le it or . P ro p o si c¸ a˜ o 1 .8 : S ej am A , B e C su bc on ju n to s de u m co n ju n to U . E n ta˜ o : a) A △ (B △ C ) = (A △ B ) △ C ; A △ B = B △ A b) A △ ∅= A ; A △ U = A c . c) A △ A c = U ; A △ A = ∅. d) A ∩ (B △ C ) = (A ∩ B ) △ (A ∩ C ). e) A △ B ⊆ A ∪ B ; A △ B = A ∪ B se e so m en te se A ∩ B = ∅. f) A c △ B c = A △ B . g) S e A △ C = B △ C , en ta˜ o A = B . 3 A go ra in tr o d u zi m os a n oc¸ a˜o d e im pl ic ac¸ a˜o . D e fi n ic¸ a˜ o 1 .9 : S e S , T sa˜ o su bc on ju n to s de u m co n ju n to U , de fi n im os S → T = S c ∪ T , li da co m o “S im pl ic a T ” (e m U ). 13 E x e rc´ ıc io 1 .1 0 : P ro ve q u e, p ar a A , S , T , R ⊆ U : (1 ) A ⊆ (S → T ) ss e A ∩ S ⊆ T . (2 ) S → ∅= S c . (3 ) A ⊆ S im p li ca { (S → T ) ⊆ (A → T ); (T → A ) ⊆ (T → S ). (4 ) S → (T → R ) = (S ∩ T ) → R = (S → T ) → (S → R ). (5 ) S → (T ∩ R ) = (S → T ) ∩ (S → R ). (6 ) S → (T ∪ R ) = (S → T ) ∪ (S → R ). 3 E x e rc´ ıc io 1 .1 1 : S ej a U u m co n ju n to e se ja O = {∩ , ∪, (·) c , → , △ }o co n ju n to d as op er ac¸ o˜e s st an d ar d en tr e su b co n ju n to s d e U . M os tr e q u e to d as as op er ac¸ o˜e s em O p o d em se r d efi n id as a p ar ti r d e a) In te rs ec¸ a˜o e co m p le m en ta c¸a˜ o (( ·)c ); b ) U , d if er en c¸a si m e´t ri ca (△ ) e in te rs ec¸ a˜o ; c) ∅e im p li ca c¸a˜ o (→ ). 3 O b se rv a c¸a˜ o 1 .1 2 : S e U e´ u m co n ju n to , as op er ac¸ o˜e s d e u n ia˜ o e in te rs ec¸ a˜o p o d em se r fe it as co m q u al q u er su b co n ju n to d e P( U )2 . P ar a S ⊆ P( U ), te m os ∗⋃ S = {x ∈ U : x p er te n ce a al gu m el em en to d e S }. (U n ia˜ o d e S ) ∗⋂ S = {x ∈ U : x p er te n ce a to d os os el em en to s d e S }. (A in te rs ec¸ a˜o d e S ). A s p ro p ri ed ad es fu n d am en ta is d es ta s op er ac¸ o˜e s sa˜ o p ar ec id as co m as d a u n ia˜ o e in te rs ec¸ a˜o fi n it as . E la s ap ar ec em , p ar a fa m ı´l ia s, n a P ro p os ic¸ a˜o 4. 28 e n a˜o va m os re p et´ ı- la s aq u i, em p ar ti cu la r, p or q u e n a˜o p re ci sa re m os d el as n a P ar te I. 3 E x e rc´ ıc io 1 .1 3 : S ej am A e B su b co n ju n to s d e u m co n ju n to U . a) P ro ve q u e as se gu in te s co n d ic¸ o˜e s sa˜ o eq u iv al en te s : (1 ) B = A c ; (2 ) B ve ri fi ca as eq u ac¸ o˜e s { A ∩ B = ∅ A ∪ B = U . b ) U ti li za n d o (a ), d es cu b ra u m a p ro va d os ı´t en s (d ) e (e ) d e 1. 6. 3 2 N a˜o ap en a s p a ra su b co n ju n to s d a fo rm a {A , B }.. . C a p´ ıt u lo 2 O C a´ lc u lo P ro p o si ci o n a l 2 .1 A E st ru tu ra P ro p o si ci o n a l d e u m E n u n ci a d o O es b oc¸ o d e te or ia d os co n ju n to s q u e ac ab am os d e ap re se n ta r, em b or a “t el eg ra´ fi co ”, co n te´ m al gu n s d os in gr ed ie n te s fu n d am en ta is d a li n gu ag em fo rm al m at em a´t ic a. D is cu ti re m os aq u i a p ar te d a L o´g ic a q u e li d a co m a ch am ad a e st ru tu ra p ro p o si ci o n a l d os en u n ci ad os , is to e´, aq u el a q u e d ep en d e d a ar ti cu la c¸a˜ o d e se n te n c¸a s d ec la ra ti va s, at ra v e´s d e ex p re ss o˜e s co m o “o u ”, “e ”, “n a˜o ” e “s e ·· ·e n ta˜ o ·· ·, ch am ad as d e co n e ct iv o s lo´ g ic o s. N a˜o va m os tr at ar d as re gr as p ar a os q u an ti fi ca d or es – aq u el es m es m os q u e vo ceˆ co n h ec e – o ex is te n ci al (∃ ) e o u n iv er sa l (∀ ). F al ar em os so b re el es m ai s ta rd e, n o C ap´ ıt u lo ? ? . A lg u n s ex em p lo s p o d em ac la ra r a si tu ac¸ a˜o . C on si d er e o T eo re m a 1. 2 : n a˜o ex is te o co n ju n to d e tod os os co n ju n to s. O se u en u n ci ad o e´ a n eg ac¸ a˜o d a se n te n c¸a P : “E x is te u m co n ju n to ta l q u e to d o co n ju n to e´ se u el em en to ”. E m s´ı m b ol os : (∃ x ∀ y (y ∈ x )) . A su a es tr u tu ra p ro p os ic io n al e´ “n a˜o P ”. S e te n ta rm os ir ad ia n te e fa ze r u m a an a´l is e m ai s ap ro fu n d ad a d e su a es tr u tu ra , te re m os q u e le va r em co n ta a co n fi gu ra c¸a˜ o d a se n te n c¸a P , a q u al en vo lv e os q u an ti fi ca d or es ∃ e ∀. R et om em os o T eo re m a 1. 3 : “S e A e´ u m co n ju n to e B = {x ∈ A : x 6∈ x }, en ta˜ o B ⊆ A e B 6∈ A ”. S e d en ot ar m os p or P (A ) a p ro p ri ed ad e “A e´ u m co n ju n to ”; Q (A , B ) a afi rm ac¸ a˜o “B = {x ∈ A ; x 6∈ x }” q u e d ep en d e d e A e d e B ; R (A , B ) n o lu ga r d e “B ⊆ A ”; e S (A , B ) n o lu ga r d e “B 6∈ A en ta˜ o o en u n ci ad o 1. 3 p o d e se r en te n d id o co m o u m re su lt ad o d a fo rm a ∀ A ∀ B (s e P (A ) e Q (A , B ) en ta˜ o R (A , B ) e S (A , B )) . “T ir an d o fo ra ” os A ’s e os B ’s , ob te m os a es tr u tu ra p ro p os ic io n al d o T eo re m a 1. 3, d ad a p or “S e P e Q , en ta˜ o R e S ”, 14 15 q u e e´ a p ar te q u e p o d e se r co n st ru´ ıd a so´ co m co n ec ti vo s lo´ gi co s. A s P ro p os ic¸ o˜e s 1. 4, 1. 5 e 1. 6 p o d em se r an al is ad as d e m o d o se m el h an te . V ej am os m ai s u m ex em p lo . C on si d er e o se gu in te re su lt ad o : T e o re m a 2 .1 : S e u m n u´ m er o n at u ra l e´ di vi s´ı ve l po r 2 e po r 3, en ta˜ o e´ di vi s´ı ve l po r 6. C om o d es cr ev er a a es tr u tu ra p ro p os ic io n al d es te en u n ci ad o ? S e d efi n im os – P (x ) p or “x e´ u m n u´ m er o n at u ra l – ”Q (x ) co m o “x e´ d iv is´ ıv el p or 2” , – R (x ) se n d o “x e´ d iv is´ ıv el p or 3” – e S (x ) a fr as e “x e´ d iv is´ ıv el p or 6” en ta˜ o o en u n ci ad o 2. 1 p o d e se r es cr it o co m o “∀ x (S e P e Q e R en ta˜ o S )” . A ss im , su a es tr u tu ra p ro p os ic io n al e´ : “S e P e Q e R en ta˜ o S ”. P or u´ lt im o, co n si d er e o en u n ci ad o : T e o re m a 2 .2 : T od o n u´ m er o ra ci on al di st in to de ze ro te m in ve rs o m u lt ip li ca ti vo . V am os id en ti fi ca r P (x ) = “x e´ u m n u´ m er o ra ci on al ”, Q (x ) = “x 6= 0” e R (x ) = ∃y (x ·y = 1) . E m p ar ti cu la r, R (x ) d iz q u e “x te m u m in ve rs o” , is to e´, ex is te u m n u´ m er o y q u e, q u an d o m u lt ip li ca d o p or x , d a´ 1. O T eo re m a 2. 2 se es cr ev e en ta˜ o co m o “∀ x (s e P e Q en ta˜ o R )” . O b se rv e q u e, d o p on to d e v is ta p ro p os ic io n al , n a˜o p o d em os d iv id ir ∃y (x ·y = 1) em p ro p os ic¸ o˜e s m ai s el em en ta re s, p oi s en co n tr am os o q u an ti fi ca d or ex is te n ci al . A es tr u tu ra p ro p os ic io n al d o T eo re m a 2. 2 e´, p oi s, “S e P e Q , en ta˜ o R ”. E st u d ar as re gr as d a L o´g ic a p ar a os co n ec ti vo s co n st it u i u m p as so im p or ta n te p ar a en te n - d er co m o fu n ci on am as p ro va s em M at em a´t ic a. E st e es tu d o d en om in a- se C a´ lc u lo P ro p o si - ci o n a l. A d is ci p li n a q u e, al e´m d as re gr as p ro p os ic io n ai s, d is cu te os q u an ti fi ca d or es , d en om in a- se C a´ lc u lo d e P re d ic a d o s. E m u m a p ro va m at em a´t ic a, se m p re u ti li za m os as le is d a L o´g ic a e m ai s p ro p ri ed ad es es p ec´ ıfi ca s d os ob je to s q u e es ta m os es tu d an d o. S e fo re m co n ju n to s, se ra˜ o as p ro p ri ed ad es ou ca ra ct er´ ıs ti ca s p ro´ p ri as d e co n ju n to s; se fo re m n u´ m er os , as p ro p ri ed ad es d es te s, e as si m p or d ia n te . D e q u al q u er fo rm a, o ar ca b ou c¸o co m u m q u e h a´ em to d as es ta s p ro va s e´ fo rm ad o ju st am en te p el as re gr as d a L o´g ic a. O q u e va m os es tu d ar sa˜ o, p oi s, as re gr as q u e p o d em se r u ti li za d as em q u a lq u e r co n te x to e e m q u a lq u e r p ro v a . E´ cl ar o q u e es te es tu d o e´ ab st ra to . M as ab st ra to n a˜ o e´ si n oˆn im o d e in co m pr ee n s´ı ve l ! C ad a as su n to q u e es tu d am os re q u er u m a li n gu ag em q u e lh e e´ p ro´ p ri a. P or su a ve z, as le is d a L o´g ic a p re te n d em es ta b el ec er p ro ce d im en to s, co n cl u so˜ es e “g ra u s d e ve rd ad e” em q u al q u er m at e´r ia q u e es te ja se n d o ab or d ad a. E´ ra zo a´v el , p oi s, es p er ar q u e to d as es sa s li n gu agen s, em b or a es p ec´ ıfi ca s, te n h am u m a b as e co m u m fo rm al e ob je ti va – “u m a li n gu ag em b a´s ic a” – on d e as se n te n c¸a s n a˜o d eˆe m m ar ge m a in te rp re ta c¸o˜ es ar b it ra´ ri as . D ep oi s d e es ta b el ec er ta l li n gu ag em , d efi n ir em os o si gn ifi ca d o d e “i n te rp re ta c¸a˜ o” , fo rn ec en d o u m cr it e´r io u n if or m e p ar a a in te rp re ta c¸ a˜ o m a te m a´ ti ca d e u m a fr as e. E sp er am os te r co n ve n ci d o o le it or d e q u e se ra´ n ec es sa´ ri o es ta b el ec er u m a li n gu ag em fo rm al e d ep oi s d efi n ir , m at em at ic am en te , o si gn ifi ca d o d e in te rp re ta c¸a˜ o. E´ d es sa in te ra c¸a˜ o q u e su rg ir a˜o as le is d a L o´g ic a C la´ ss ic a. T al m e´t o d o se ap li ca ta n to p ar a o C a´l cu lo d e P re d ic ad os q u an to ao n os so ca so aq u i, o d o C a´l cu lo P ro p os ic io n al . E st e d es en vo lv im en to se ra´ o te m a d o q u e ve m a se gu ir . 16 2 .2 L in g u a g e m F o rm a l A n te s d e co n st ru ir u m a li n gu ag em fo rm al co m a q u al d es cr ev er as le is d a L o´g ic a, fa c¸a m os u m b re ve co m en ta´ ri o so b re o as su n to ac er ca d o q u al es sa li n gu ag em d ev e tr at ar . Q u er em os d is cu ti r as le is d o ra ci o c´ı n io q u e en vo lv em se n te n c¸a s d ec la ra ti va s, ch am ad as d e p ro p o si c¸o˜ e s. S er a´ n ec es sa´ ri o, e´ cl ar o, in d ic a´- la s d e al gu m m o d o. E m ge ra l, u sa re m os le tr as la ti n as m ai u´ sc u la s co m o P , Q , R , et c. E ve n tu al m en te p o d er em os u ti li za r ı´n d ic es e fa la r so b re a p ro p os ic¸ a˜o P 1 , ou a p ro p os ic¸ a˜o Q 2 , et c. C om o n a l´ı n gu a p or tu gu es a, p ro p os ic¸ o˜e s p o d em se r co m b in ad as p ar a fo rm ar ou tr as . S e P e Q sa˜ o p ro p os ic¸ o˜e s, en ta˜ o p o d em os fa la r d e “n a˜o P ”, “P e Q ”, “P ou Q ”, “s e P , en ta˜ o Q ”. (I ) E v id en te m en te , h a´ ou tr as co n st ru c¸o˜ es p er fe it am en te le g´ı ti m as . U m ex em p lo e´ a p ro p os ic¸ a˜o “n em P , n em Q ”. V o ceˆ p o d er a´ ce rt am en te p en sa r em al gu m as m ai s. T om ar em os co m o b a´s ic as as op er ac¸ o˜e s q u e ap ar ec em em (I ), d en om in ad as re sp ec ti va m en te d e n eg ac¸ a˜o , co n ju n c¸a˜ o, d is ju n c¸a˜ o e im p li ca c¸a˜ o. P ar a ca d a u m a d es sa s, p re ci sa m os d e u m si n al li n gu´ ıs ti co fo rm al : – A n e g a c¸ a˜ o se ra´ in d ic ad a p or ¬; as si m , ¬P e´ a ex p re ss a˜o fo rm al d a n eg ac¸ a˜o d a p ro p os ic¸ a˜o P ; – A co n ju n c¸ a˜ o se ra´ in d ic ad a p or ∧; P ∧ Q re p re se n ta a fr as e “P e Q ”, ch am ad a d e co n ju n c¸a˜ o d e P e Q . – A d is ju n c¸a˜ o se ra´ in d ic ad a p or ∨; P ∨ Q re p re se n ta a d ec la ra c¸a˜ o “o u P , ou Q ”; – A im p li ca c¸a˜ o se ra´ in d ic ad a p or → ; P → Q re p re se n ta fo rm al m en te “s e P , en ta˜ o Q ”. O s s´ı m b ol os ¬, ∧, ∨ e → sa˜ o ch am ad os co n ec ti vo s lo´ gi co s. C om el es , p o d em os p ro - d u zi r n ov as p ro p os ic¸ o˜e s a p ar ti r d e ou tr as . V al e a p en a ch am ar a at en c¸a˜ o d e q u e, n es se p ro - ce ss o, al gu n s cu id ad os d ev em se r to m ad os co m o q u e re al m en te se q u er d iz er . P or ex em p lo : P → (Q ∨ R ) n a˜o e´ a m es m a co is a q u e (P → Q ) ∨ R . C om o se m p re , u ti li za m os p ar eˆn te se s p ar a ex p li ci ta r q u e p ro p os ic¸ a˜o es ta m os , d e fa to , co n si d er an d o. U m in st ru m en to b a´s ic o p ar a co n st ru ir u m a li n gu ag em e´ u m a lf a b e to . V am os a el e, es p ec ifi ca n d o os s´ı m b ol os q u e o co n st it u em . S´ ım b o lo s d o a lf a b e to : 1. U m co n ju n to n a˜o va zi o A t d e s´ı m b ol os , ch am ad os p ro p o si c¸o˜ e s a toˆ m ic a s, in d ic ad as p or le tr as co m o p, q, r, s .. . C om o ja´ co m en ta m os an te s, p o d em os u sa r ı´n d ic es e fa la r so b re a p ro p os ic¸ a˜o at oˆm ic a p 1 ou q 3 , et c. 2. S´ ım b ol os p ar a os co n ec ti vo s lo´ gi co s : ¬, ∧, ∨, → ; 3. P ar eˆn te se s a` d ir ei ta e a` es q u er d a. A ri go r, p re ci sa r´ı am os in cl u ir , n a n os sa li st a d e s´ı m b ol os fo rm ai s, o es p ac¸ o em b ra n co . J a´ im ag in ou se n a˜o ex is ti ss e o si n al li n gu´ ıs ti co “e sp ac¸ o em b ra n co ”e m p or tu gu eˆs (o u em q u al q u er 17 ou tr a l´ı n gu a v iv a) ? M as n a˜o p en se q u e fo i se m p re as si m ! H a´ fo rm as d e gr eg o an ti go q u e er am es cr it as se m es p ac¸ o em b ran co en tr e as p al av ra s. N a˜o va m os n os p re o cu p ar co m ta n ta p re ci sa˜ o. A es ta al tu ra vo ceˆ d ev e es ta r ac h an d o es ta es to´ ri a d e “p ro p os ic¸ a˜o at oˆm ic a” m ei o es tr an h a. M as el a e´ ra zo a´v el . V ej a p or q u eˆ : Q u er em os es tu d ar as le is d a L o´g ic a, aq u el as q u e p o d em se r u ti li za d as n o tr at o d e q u al q u er co n te x to co n cr et o. Q u an d o an al is am os a es tr u tu ra p ro p os ic io n al d e u m en u n ci ad o m at em a´t ic o, co m o fe it o n a se c¸a˜ o an te ri or , d ep ar am o- n os co m u m co n ju n to d e p ro p os ic¸ o˜e s, re la ci on ad as en tr e si p el os co n ec ti vo s. P oi s b em : p ar a ef ei to d e n os so es tu d o, a p ar ti r d e ce rt o p on to , n a˜o n os in te re ss a m ai s o q u e “t em d en tr o” d e u m a p ro p os ic¸ a˜o : u m a ve z co n h ec id as as re gr as p er m it id as , q u e sa˜ o, n a ve rd ad e, re gr as d e si n ta x e d a li n gu ag em , fi ca d et er m in ad a a es tr u tu ra q u e ta l en u n ci ad o p os su i. O re st an te d a an a´l is e – q u e ta m b e´m e´ m u it o im p or ta n te – d ep en d e d o si gn ifi ca d o es p ec´ ıfi co d os te rm os e d a p ar ti cu la r te or ia q u e es ta m os es tu d an d o. D e m o d o ge ra l, as p ro p os ic¸ o˜e s el em en ta re s a p ar ti r d as q u ai s u m p ar ti cu la r en u n ci ad o e´ co m p os to p o d em se r co n si d er ad as co m o a toˆ m ic a s (i n d iv is´ ıv e is ) p ar a aq u el a si tu ac¸ a˜o . V ol ta n d o ao s ex em p lo s d a se c¸a˜ o an te ri or : – T eo re m a 1. 2 : N a˜o ex is te o co n ju n to d e to d os os co n ju n to s. T ra ta -s e d e u m en u n ci ad o d a fo rm a ¬ P . – T eo re m a 2. 1 : S e u m n u´ m er o e´ d iv is´ ıv el p or 2 e p or 3 en ta˜ o e´ d iv is´ ıv el p or 6. S ej am P = n e´ u m n u´ m er o Q = n e´ d iv is´ ıv el p or 2 R = n e´ d iv is´ ıv el p or 3 S = n e´ d iv is´ ıv el p or 6 E n ta˜ o p o d em os d iz er q u e 2. 1 p os su i u m a es tr u tu ra d o ti p o (P ∧ Q ∧ R ) → S . P ar a an al is ar a es tr u tu ra d o T eo re m a 1. 2 e´ su fi ci en te u m al fa b et o co m ap en as u m a p ro p os ic¸ a˜o at oˆm ic a. P ar a o ou tr o T eo re m a, se ri am n ec es sa´ ri as q u at ro p ro p os ic¸ o˜e s at oˆm ic as . S e al gu e´m p er gu n ta r- n os o q u e, d e fa to , e´ o co n ju n to A t d as p ro p os ic¸ o˜e s at oˆm ic as , d ev em os re sp on d er q u e p o d e se r q u a lq u e r co n ju n to n a˜o va zi o. A fi n al , p o d em os es co lh er o al fa b et o q u e d es ej ar m os p ar a fa ze r a n os sa te or ia d a L o´g ic a ! V am os ag or a d efi n ir o q u e co n si d er am os se n te n c¸a s ou p ro p os ic¸ o˜e s n a n os sa li n gu ag em : D e fi n ic¸ a˜ o 2 .3 : S ej a A t u m co n ju n to de pr op os ic¸ o˜e s at oˆm ic as . O co n ju n to d a s p ro p o si c¸ o˜ e s co n st ru´ ıd as a pa rt ir de A t, in di ca do po r L( A t) , e´ de fi n id o da se gu in te fo rm a : [P 1] : T od a pr op os ic¸ a˜o at oˆm ic a es ta´ em L( A t) . [P 2] : S e P e Q es ta˜ o em L( A t) , en ta˜ o ¬P , P ∧ Q , P ∨ Q e P → Q pe rt en ce m a L( A t) . [P 3] : U m a su ce ss a˜o de s´ı m bo lo s do al fa be to so´ es ta´ em L( A t) se pu de r se r co n st ru´ ıd o a pa rt ir 18 da s pr op os ic¸ o˜e s at oˆm ic as , at ra ve´ s de ap li ca c¸o˜ es su ce ss iv a s da re gr a [P 2] . C om o em u m a l´ı n gu a u su al , n em to d a se q u¨ eˆn ci a d e s´ı m b ol os e´ u m a p al av ra . A se q u¨ eˆn ci a “a ab b k lm ew y p ” n a˜o e´ u m a p al av ra d a l´ı n gu a p or tu gu es a. N a n os sa li n gu ag em fo rm al , a ex p re ss a˜o ∧ p q → n a˜o e´ u m a p ro p os ic¸ a˜o p oi s, d ev id o a [P 2] e [P 3] , o co n ec ti vo ∧ so´ p o d e ap ar ec er en tr e p ro p os ic¸ o˜e s ! A D efi n ic¸ a˜o 2. 3 es ta b el ec e ex at am en te q u ai s sa˜ o as p ro p os ic¸ o˜e s em L( A t) . E x e m p lo 2 .4 : a) S u p on h a q u e A t = {p }, ou se ja , so´ te m os u m a p ro p os ic¸ a˜o at oˆm ic a. A s se gu in te s se q u¨ eˆn ci as sa˜ o ex em p lo s d e p ro p os ic¸ o˜e s, is to e´, d e el em en to s d e L( A t) : p, ¬p , ¬¬ ¬p , p → p, p → (p ∧ p) , (p ∨ p) → ¬p . N ot e q u e p → q n a˜ o e´ u m a p ro p os ic¸ a˜o d e L( A t) , p oi s q n a˜o es ta´ em A t. b ) S u p on h a q u e A t = {p , q, r} . A s se gu in te s se q u¨ eˆn ci as sa˜ o p ro p os ic¸ o˜e s d e L( A t) : p → (q ∧ r) , q → (p → p) , (( p → q) ∧ (p → ¬q )) → ¬p . (I ) C om o p o d em os p ro va r is to ? E´ si m p le s : b as ta “m on ta r”a a´r vo re d e fo rm ac¸ a˜o d e ca d a u m a, a p ar ti r d as p ro p os ic¸ o˜e s at oˆm ic as , u ti li za n d o [P 2] . V am os fa ze r a u´ lt im a (e m ai s co m p ri d a) d a li st a (I ) ac im a. 1. p e q sa˜ o p ro p os ic¸ o˜e s, p oi s sa˜ o at oˆm ic as ; 2. D e [P 2] , ve m q u e ¬p e ¬q sa˜ o p ro p os ic¸ o˜e s; 3. D e [P 2] , ve m q u e p → q e p → ¬q sa˜ o p ro p os ic¸ o˜e s. 4. P or ta n to , (p → q) ∧ (p → ¬q ) e´ u m a p ro p os ic¸ a˜o . 5. L og o, (( p → q) ∧ (p → ¬q )) → ¬p e´ u m a p ro p os ic¸ a˜o . F a´c il , n e´ ? 3 L o´g ic os ch am am L( A t) d e li n g u a g e m p ro p o si ci o n a l co n st ru´ ıd a a p ar ti r d e A t. N ot e q u e L( A t) d ep en d e so´ d e A t, p oi s os s´ı m b ol os re st an te s – co n ec ti vo s e p ar eˆn te se s – sa˜ o co m u n s a to d a li n gu ag em p ro p os ic io n al . E´ cl ar o q u e al fa b et os d is ti n to s d a˜o li n gu ag en s d if er en te s. A go ra q u e te m os li n gu ag en s fo rm ai s, d ev em os d is cu ti r a su a in te rp re ta c¸a˜ o, is to e´, o q u e es ta s ex p re ss o˜e s fo rm ai s q u er em d iz er . E st a e´ a ta re fa d a se m aˆ n ti ca , a te or ia d o si gn ifi ca d o. F ar em os is to n a p o´x im a se c¸a˜ o. Q u er em os te rm in ar es ta se c¸a˜ o in tr o d u zi n d o u m s´ı m b ol o fo rm al p ar a a “e q u iv al eˆn ci a” ou o fa m os o “s e e so m en te se ”. S e P e Q sa˜ o p ro p os ic¸ o˜e s, d efi n im os P ↔ Q co m o ab re v ia c¸a˜ o d e (P → Q ) ∧ (Q → P ). A ss im , a eq u iv al eˆn ci a e´ d efi n id a co m o a co n ju n c¸a˜ o d e (P im p li ca Q ) e (Q im p li ca P ). N a p ro´ x im a se c¸a˜ o d ar em os ex em p lo s im p or ta n te s d es te ti p o d e p ro p os ic¸ a˜o . 2 .3 In te rp re ta c¸ o˜ e s. L e is L o´ g ic a s T ra ta re m os aq u i d a in te rp re ta c¸a˜ o d e u m a li n gu ag em p ro p os ic io n al . C om o en te n d em os u m a afi rm ac¸ a˜o es cr it a em L( A t) ? E q u ai s as le is lo´ gi ca s q u e re ge m ta l in te rp re ta c¸a˜ o ? 19 F ix em os , p oi s, u m a li n gu ag em p ro p os ic io n al L( A t) . Q u an d o n a˜o h ou ve r p os si b il id ad e d e co n fu sa˜ o, va m os in d ic a´- la si m p le sm en te p or L (a s p ro p os ic¸ o˜e s at oˆm ic as fi ca ra˜ o su b en te n d id as ). P ar a ex p li ca rm os o q u e u m a ex p re ss a˜o d e L si gn ifi ca e´ n ec es sa´ ri o in te rp re ta´ -l a em al gu m co n te x to . In te rp re ta r u m a ex p re ss a˜o d e L e´ u m m o d o d e m ed ir o “g ra u d e ve ra ci d ad e” d es ta ex p re ss a˜o n u m ce rt o co n te x to . C om o es ta m os co n st ru in d o u m a te or ia m a te m a´ ti ca d a L o´g ic a, e´ n at u ra l q u e u ti li ze m os ob je to s m at em a´t ic os p ar a es te p ro p o´s it o. O m o d o m at em a´t ic o d e fa ze r is so e´ u sa n d o co n ju n to s : fi x am os u m co n ju n to U e as so ci - am os , a ca d a se n te n c¸a , u m su b co n ju n to d e U , q u e d a´ ju st am en te o se u “g ra u d e co n fi ab il id ad e” . F or m al m en te , te m os a se gu in te D e fi n ic¸ a˜ o 2 .5 : S ej a L u m a li n gu ag em pr op os ic io n al e U u m co n ju n to . U m a in te rp re ta c¸ a˜ o de L e m U e´ u m a fu n c¸a˜ o [· ] U : L −→ P( U ), P 7→ [P ] U , sa ti sf az en do a`s se gu in te s pr op ri ed ad es , pa ra qu ai sq u er p ro po si c¸o˜ es P e Q em L: 1. [P ∧ Q ] U = [P ] U ∩ [Q ] U ; 2. [P ∨ Q ] U = [P ] U ∪ [Q ] U ; 3. [¬ P ] U = ([ P ] U )c ; 4. [P → Q ] U = ([ P ] U )c ∪ [Q ] U . O su bc on ju n to [P ] U de n om in a- se a in te rp re ta c¸ a˜ o d a p ro p o si c¸ a˜ o PP P e m UU U . Q u an do o co n ju n to U es ti ve r cl ar o n o co n te xt o, de ix ar em os de u sa´ -l o n a n ot ac¸ a˜o , es cr ev en do [P ] pa ra a in te rp re ta c¸a˜ o da pr op os ic¸ a˜o P em U . A ss im , d ad a u m a p ro p os ic¸ a˜o P em L, p o d em os p en sa r em [P ] U ⊆ U co m o u m a m ed id a d e q u an to P e´ ve rd ad ei ra . E m p ar ti cu la r, ∗[ P ] U = U si gn ifi ca – e´ cl ar o ! – q u e P e´ ve rd ad ei ra n es ta in te rp re ta c¸a˜ o, en q u an to q u e ∗[ P ] U = ∅q u er d iz er q u e e´ fa ls a, n es ta in te rp re ta c¸a˜ o. M as ta m b e´m e´ cl ar o q u e o va lo r [P ] U p o d e, em ge ra l, se r u m su b co n ju n to p ro´ p ri o e n a˜o va zi o d e U . N es te ca so , P n em e´ fa ls a n em ve rd ad ei ra , m as co n ti n ge n te re la ti va m en te a` in te rp re ta c¸a˜ o co n si d er ad a. A ex p er ieˆ n ci a co n cr et a es ta´ re p le ta d e ex em p lo s d e afi rm ac¸ o˜e s d es te ti p o. 20 U m a ve z q u e te m os os va lo re
Compartilhar