Conteudo1 RELAC OES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.1 RELAC OES SOBRE UM CONJUNTO . . . . . . . . . . . 31.2 APLICAC OES E FUNC OES . . . . . . . . . . . . . . . . 41.3 LEIS DE COMPOSIC AO INTERNAS. . . . . . . . . . . 51.4 TABUA DE UMA OPERAC AO . . . . . . . . . . . . . . 111.5 Tabua das opera coes no conjunto Zm . . . . . . . . . . . . 131.6 HOMOMORFISMOS E ISOMORFISMOS . . . . . . . . . 13UNIVERSIDADE DA REGIAO DE JOINVILLEDEPARTAMENTO DE SISTEMAS DE INFORMAC AOMATEMATICA DISCRETAProfessor: ENORI CARELLIAluno:..........................................................................Joinville, 201121. RELAC OES1.1. RELAC OES SOBRE UM CONJUNTODeni cao 1.1. Sejam E e F dois conjuntos nao vazios. Denominamos produtocartesiano de E por F ao conjunto formado por todos os pares ordenados (x, y)tal que x E e y F.O produto cartesiano de E por F e denotado por E F e le-se E cartresianoF. Assim, temosE F = {(x, y) / x E e y F }.Exemplo 1.2. Dados os conjuntos E = {1, 2, 3} e F = {a, b} temos :E F = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}Deni cao 1.3. Sejam E e F dois conjuntos nao vazios. Denominamos rela caobinaria de E em F a qualquer subconjunto do produto cartesiano de E por F.Se x E e y F para indicar que x esta relacionado com y escrevemos xRy.Exemplo 1.4. Sejam E= {1, 2, 3, 4} e F= {1, 2, 3, 4} dois conjuntos. Saorela coes de E em F. R1 = {(1, 3), (3, 4)}; R2 = {(1, 1), (1, 2), (1, 3), (1, 4)}; R3 = {(1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3), (4, 2), (4, 3)}; R4 = {(x, y) E F / y x}.Observa cao 1. Apresentamos, aqui, quatro rela coes de E em F. Sendo queE F possui 16 elementos e uma rela cao de E em F e qualquer subconjunto doproduto cartesiano de E por F, o n umero de rela coes de E em F que podemosescrever, para o exemplo 1.4, e n = 216= 65 536.Deni cao 1.5. Sejam E e Fdois conjuntos nao vazio e seja R uma rela caobinaria de E em F. Denominamos domnio de R ao subconjuto de E constitudopelos elementos x E tal que xRy para algum y F.3Simbolicamente denotamos por DR = {x E / xRy para algum y F}.Exemplo 1.6. Consideremos as rela coes de E em F descritas no exemplo 1.4.Entao teremos: DR1 = {1, 3}; DR2 = {1}; DR3 = {1, 2, 3, 4}; DR4 = {x E / x < y, y F}.Deni cao 1.7. Sejam E e Fdois conjuntos nao vazio e seja R uma rela caobinaria de E em F. Denominamos imagem de R ao subconjuto de F constitudopelos elementos y F tal que xRy para algum x E.Simbolicamente denotamos por IR = {y F / xRy para algum x E}.Exemplo 1.8. Consideremos as rela coes de E em F descritas no exemplo 1.4.Entao teremos: IR1 = {3, 4}; IR2 = {1, 2, 3, 4}; IR3 = {2, 3}; IR4 = {y F / y x, x E}.Deni cao 1.9. Quando E = F e R e uma rela cao de E em F, diz-se que R euma rela cao sobre E, ou ainda, R e uma rela cao em E.1.2. APLICAC OES E FUNC OESDeni cao 1.10. Sejam E e F dois conjuntos e seja f uma rela cao de E em F,dizemos que f e uma aplica cao de E em F se satisfaz as seguintes condi coes:i) Para todo x E existe y F tal que y = f(x), isto e (x, y) f;ii) Se x E e y, z F sao tais que y = f(x) e z = f(x) entao y = z, isto e(x, y) = (x, z).4Observa cao 2. Simbolicamente representamos a aplica cao f de E em Fporf : E F. Alem disso, para indicar que f(x) e imagem de x podemos usar osmbolo x f(x). Caso tenhamos f : E F e g : E F entao f = g se, esomente se, f(x) = g(x) para todo x E.Observa cao 3. Se a imagem de f for um conjunto numerico entao f sera chamadafun cao.1.3. LEIS DE COMPOSIC AO INTERNASDeni cao 1.11. Seja E um conjunto. Denominamos opera cao sobre E, ou lei decomposi cao interna sobre E, `a qualquer aplica cao : E E E.Uma lei de composi cao interna sobre E, associa a cada par ordenado (x, y) E E o elemento denido por x y e denotamos por (x, y) x y.Exemplo 1.12. Sejam E = R e a opera cao () denida por x y = x + y paratodo (x, y) R R. Entao: Se (x, y) = (1, 2), teremos 1 2 = 1 + 2 ou 1 2 = 3. Se (x, y) = (3, 2), teremos 3 2 = 3 + 2 ou 3 2 = 5. Se (x, y) = (5, 8), teremos 5 8 = 5 + 8 ou 5 8 = 13.Deni cao 1.13. Seja E um conjunto e : E E E uma lei de composi caointerna sobre E. Seja A E um subconjunto nao vazio de E. Dizemos que A efechado em rela cao `a lei () se dados (x, y) AA entao x y A.Exemplo 1.14. Sejam E = Z = {..., 3, 2, 1, 0, 1, 2, 3, ...} eA = {.. 4, 2, 0, 2, 4, ..}. Note que Ae o conjunto dos n umeros pares e A efechado em rela cao `as leis de composi cao internas adi cao e multiplica cao sobre Z.Prova: Sejam x, y A. Entao, como A e o conjunto dos n umeros pares,podemos escrever x = 2k e y = 2h, sendo que h, k Z, alem disso, t = (k+h) Ze r = k2h Z. Agora vamos mostrar que x +y e xy tambem sao n umeros pares.Temos entao:5 x + y = 2k + 2h = 2(k + h) = 2t A. xy = 2k2h = 2(k2h) = 2r A.Portanto, pela deni cao 1.13, A e um subconjunto de Z fechado em rela cao `asopera coes adi cao e multiplica cao.PROPRIEDADES DE UMA LEI DE COMPOSIC AO INTERNAAs propriedades de uma lei de composi cao interna sao:a) Associativa: Seja E um conjunto e : EE E uma lei de composi caointerna sobre E.Dizemos que () e associativa se dados x, y, z E vale aigualdade (x y) z = x (y z).Exemplo 1.15. Seja E = R um conjunto e : RR R uma lei de composi caointerna sobre R, denida por a b = a + b ab para todo par (a, b) R R.Vamos mostrar que (), assim denida, e associativa.Solu cao: sejam x, y, z R. Entao:I - (x y) z= (x + y xy) z = (x + y xy) + z (x + y xy)z= x + y xy + z xz yz + xyz .II - x (y z) = x (y + z yz) = x + (y + z yz) x(y + z yz)= x + y + z yz xy xz + xyz.Sendo que x, y, z R, comparando os resultados de (I) e (II) vemos que(x y) z = x (y z). Logo, () e associativa.b) Comutativa: Seja E um conjunto e : EE E uma lei de composi caointerna sobre E. Dizemos que () e comutativa se dados x, y E vale aigualdade x y = y x.Exemplo 1.16. Seja E = R um conjunto e : RR R uma lei de composi caointerna sobre R, denida por a b = a + b ab para todo par (a, b) R R.Vamos mostrar que (), assim denida, e comutativa.Solu cao: sejam x, y R. Entao devemos ter6x y = y xx + y xy = y + x yxSendo que x, y R, comparando o resultado `a esquerda com o resultado `adireita do sinal de igual vemos que x y = y x. Logo, () e comutativa.c) Elemento neutro: Seja E um conjunto e : E E E uma lei decomposi cao interna sobre E.Um elemento e E e denominado elementoneutro `a esquerda, em rela cao `a opera cao (), se para todo x E vale aigualdade e x = x. Por outro lado, um elemento e E e denominadoelemento neutro `a direita, em rela cao `a opera cao (), se para todo x Evale a igualdade x e = x.Se e E for o elemento neutro `a esquerda e `a direita em rela cao `a opera cao() dizemos que e e o elemento neutro em rela cao `a lei de composi cao interna ()sobre E.Exemplo 1.17. Seja E = R um conjunto e : RR R uma lei de composi caointerna sobre R, denida por a b = a + b ab para todo par (a, b) R R.Vamos mostrar que (), assim denida, possui elemento neutro e.Solu cao:Sejam x R. Entao devemos ter:e x = x e x e = xe + x ex = x x + e xe = xComo e, x R, para que e + x ex = xseja verdadeira, obrigatoriamente,devemos ter e = 0, de modo que o elemento neutro a esquerda para a opera cao ()e e = 0. Por outro lado, x + e xe = x e verdadeira se e = 0, ou seja,o elementoneutro `a direita para a opera cao () e e = 0. Desse modo, conclumos que e = 0e o elemento neutro em rela cao `a opera cao ().Teorema 1.18. Seja E um conjunto e : E E E uma lei de composi caointerna sobre E que possui elemento neutro e. Entao o elemento neutro, emrela cao a essa opera cao, e unico.Demonstrac ao: Suponhamos que a opera cao () possua dois elementosneutros. Sejam e e e os elementos neutros de (). Entao podemos escrever:7i) e e = e e e e = e, pois e e elemento neutro de ().ii) e e = e e e e = e, pois e e elemento neutro de ().Assim, por i) temos e = e e e por ii) temos e e = e. Logo, e = e e,portanto, o elemento neutro, se existir, e unico.d) Elemento simetrizavel: Seja E um conjunto e : E E E uma leide composi cao interna sobre E que possui elemento neutro e. Um elementoa E e dito simetrizavel se existir a E tal que a a = e e a a = e. Nocaso de a existir, e denominado simetrico de a.Exemplo 1.19. Seja E = R um conjunto e : RR R uma lei de composi caointerna sobre R, denida por a b = a + b ab para todo par (a, b) R R.Vamos encontrar todos os elementos a R que sao simetrizaveis.Soluc ao: No exemplo 1.17, vimos que a opera cao () possui elemento neutroe = 0.Portanto, para a a = e temos a a = 0 e, para a a = e, a a = 0. Assim,camos coma a = 0 e a a = 0a + a aa = 0 a + a aa = 0a + a(1 a) = 0 a(1 a) + a = 0Em ambos os casos obteremos a = a1a.R. Como a existe sempre que 1a =0, conclumos que todo a = 1 e simetrizavel.Teorema 1.20. Seja E um conjunto e : E E E uma lei de composi caointerna associativa sobre E e que possui elemento neutro e. Se existir a e talque a a = e = a a entao ele e unico.Demonstrac ao: Vamos supor que existam dois elementos simetricos paraa E. Sejam a e a esses elementos. Entao podemos escrever:i) a a = e e a a = e, pois a e simetricode a;ii) a a = e e a a = e, ja que a e simetrico de a.8Agora,a = a e= a (a a), pela condi cao (ii)= (a a) a, pois () e associativa= e a = a.Teorema 1.21. Seja E um conjunto e : E E E uma lei de composi caointerna sobre E que possui elemento neutro e. Entao valem as arma coes:i) Se a E e simetrizavel, entao a tambem o e.Alem disso, o simetrico dea E e o proprio a, isto e, (a) = a;ii) Se () for associativa e a, b E, entao (a b) = b a.e) Elementos regulares: Seja E um conjunto e : EE E uma lei decomposi cao interna sobre E. Um elemento a E e dito regular em rela cao`a () se para todo x, y E com a x = a y e x a = y a se temx = y.Exemplo 1.22. Seja E = R um conjunto e : RR R uma lei de composi caointerna sobre R, denida por a b = a + b ab para todo par (a, b) R R.Vamos pesquisar os elementos regulares.Solu cao: Sejam a, x, y E tais que a x = a y e x a = y a. Vimosno exemplo 1.19 que todo a = 1 possui simetrico.Assim, para a = 1, podemosescrever:a x = a y e x a = y aa + x ax = a + y ay x + a xa = y + a ya-a + a + x ax = a + a + y ay x a + a xa = y a + a yax ax = y ay a ax = y ayx(1 a) = y(1 a) x(1 a) = y(1 a)x = y x = yNote que foi possvel cancelar o termo (1 a) porque a = 1. Logo, todo a = 1e regular.Teorema 1.23. Seja E um conjunto e : E E E uma lei de composi caointerna associativa sobre E e que possui elemento neutro e. Entao todo elementoa E, simetrizavel, e regular.9f) Propriedade distributiva: Seja E um conjunto e : E E E e : E E E duas leis de composi cao interna sobre E.Dizemos edistributiva `a direita em rela cao `a se:(y z)x = yx zxe que e distributiva `a esquerda em rela cao `a se:x(y z) = xy xz.Caso seja distributiva `a direita e `a esquerda em rela cao `a entao edistributiva em rela cao a opera cao .Exemplo 1.24. Seja E = R um conjunto e : R R R e : R R Rduas leis de composi cao interna sobre R denidas por xy = x+y3 e xy = xy.Vamos vericar se e distributiva em rela cao `a .Soluc ao: Distributiva `a direita. Sejam x, y, z R, entao devemos ter:(y z)x = yx zx(y + z 3)x = yx zx(y + z 3)x = yx + zx 3yx + zx 3x = yx + zx 3Como o resultado ocorrido no lado esquerdo do sinal de igual e diferente doresultado ocorrido no lado direito segue que nao e distributiva `a direita emrela cao `a .Distributiva `a esquerda. Sejam x, y, z R, entao devemos ter:x(y z) = xy xzx(y + z 3) = xy xzx(y + z 3) = xy + xz 3xy + xz x3 = xy + xz 3Como o resultado ocorrido no lado esquerdo do sinal de igual e diferente doresultado ocorrido no lado direito segue que nao e distributiva `a esquerda emrela cao `a . Logo, nao e distributiva em rela cao `a .101.4. TABUA DE UMA OPERAC AOQuando o conjunto E e nito uma opera cao pode ser dada atraves de uma tabua,denominada tabua da opera cao.A constru cao da tabua de uma opera cao sobreE e feita como segue.Seja E = {a1, a2, a3, ..., an}, n 1, um conjunto de elementos seja umaopera cao sobre E. Entao a tabua da opera cao sobre E e dada por: a1a2a3..... ana1a1 a1a1 a2a1 a3..... a1 ana2a2 a1a2 a2a2 a3..... a2 ana3a3 a1a3 a2a3 a3..... a3 an..............................anan a1an a2an a3.... an anNote que os elementos a1a1, a2a2, ......, anan formam a diagonal principalda tabua. A linha e a coluna em que estao distribudos os elementos de E saodenominadas linha fundamental e coluna fundamental, respectivamente. Sao elas,a primeira linha e a primeira coluna da tabua.Exemplo 1.25. Seja E = {1, 3, 5, 15, 30} e seja = mdc{x, y}, para todo x, y E. A tabua dessa opera cao e dada pormdc 1 3 5 15 301 1 1 1 1 13 1 3 1 3 35 1 1 5 5 515 1 3 5 15 1530 1 3 5 15 30PROPRIEDADESVejamos como algumas propriedades de uma opera cao sobre um conjunto nitoE = {a1, a2, a3, ..., an}, n 1,podem ser estudadas quando a opera cao e dada pormeio de uma tabua.11a) Associativa: E aquela cuja verica cao exige maior esfor co, pois exige quese fa ca o calculo de todas as composi coes (a b) c = a (b c) possveis.Um segundo metodo para vericar se uma opera cao e associativa, atravesde sua tabua, e vericar se a tabua e isomorfa a uma tabua que ja se sabeser associativa. Esse metodo sera estudado posteriormente.b) Comutativa: Uma opera cao sobre um conjunto nito E = {a1, a2, a3, ..., an},n 1, dada por meio de uma tabua e comutativa se a tabua for simetricaem rela cao a diagonal principal.Exemplo 1.26. Consideremos a opera cao dada pela tabua abaixo. a b c ea c a e ab a e c bc e c b ce a b c eA diagonal principal e formada pelos elementos c, e, b, e, nessa ordem.Comopodemos observar, a tabua e simetrica em rela cao a diagonal principal e, portanto,comutativa.c) Elemento neutro: Para encontrar o elemento neutro para a opera cao procura-se o elemento que pertence `a interse cao da linha com a coluna emque estao repetidas a linha e coluna fundamentais.Exemplo 1.27. Consideremos a tabua do exemplo 1.26. Notamos que a ultimalinha e a ultima coluna repetem a linha e a coluna fundamental. O elementopertencente a interse cao e e. Logo, e e o elemento neutro da opera cao dada pelatabua.d) Elementos simetricos: Para determinar a, simetrico de um elementoa E, basta vericar se estao satisfeitas as rela coes a a = e e a a = e.No caso da tabua do exemplo 1.26, a e c sao simetricos e b e simetrico delemesmo.121.5. Tabua das opera c oes no conjunto ZmConsiste em fazer a tabua das opra coes adi cao e multipica cao dos restos den umeros inteiros divididos por m.Exemplo 1.28. Considere o conjunto Z7, os elementos desse conjunto sao osrestos da divisao de qualquer inteiro por m = 7, isto e Z7 = {0, 1, 2, 3, 4, 5, 6}.O calendario mensal segue esta regra, pois a semana tem sete dias.Ja o relogioanalogico e (Z12, +)As tabuas abaixo representam (Z7, +) e (Z7, )A)+ 0 1 2 3 4 5 60 0 1 2 3 4 5 61 1 2 3 4 5 6 02 2 3 4 5 6 0 13 3 4 5 6 0 1 24 4 5 6 0 1 2 35 5 6 0 1 2 3 46 6 0 1 2 3 4 5B)+ 0 1 2 3 4 5 60 0 0 0 0 0 0 01 0 1 2 3 4 5 62 0 2 4 6 1 3 53 0 3 3 2 5 1 44 0 4 1 5 2 6 35 0 5 3 1 6 4 26 0 6 5 4 3 2 11.6. HOMOMORFISMOS E ISOMORFISMOSDeni cao 1.29. Sejam E e F dois conjuntos e () um opera cao em E e () umaopera cao em F. f : E E uma aplica cao que satisfaz a propriedade: Para todo x, y E se temf(x y) = f(x)f(y)Entao f e denominada homomorsmo de E em F.Exemplo 1.30. Seja f : Z R denida por denida por f(n) = an, a > 0 ea = 1, para todo n Z. Entao f e um homomorfosmo. De fato, sejam m, n Z.Entao, f(m + n) = am+n= aman= f(m)f(n). Logo, f e um homomorsmo.131. Sejam E = Z = {..., 3, 2, 1, 0, 1, 2, 3, ...} e A = {.. 3, 1, 1, 3, ..}.Mostre que A nao e fechado em rela cao `as leis de composi cao internas adi cao,mas e fechado em rela cao multiplica cao.2. Sejam E = Z = {..., 3, 2, 1, 0, 1, 2, 3, ...} e A = {.. 6, 3, 0, 3, 6, ..}.Mostre que A e fechado em rela cao `as leis de composi cao internas adi cao emultiplica cao sobre Z.3. Sejam E = Z = {..., 3, 2, 1, 0, 1, 2, 3, ...} e A = {.. 8, 4, 0, 4, 8..}.Verique se A e fechado em rela cao `as leis de composi cao internas adi cao,mas e fechado em rela cao multiplica cao.Em cada caso abaixo, considere aopera cao sobre E e verique se e associativa, se e comutativa, se pos-sui elemento neutro, determine os elementos simetrizaveis e os elementosregulares.1. E = R e x y = x+y2 ;2. E = R e x y = x;3. E = R e x y = xy;4. E = Z e x y = x + y xy;5. E = Z e x y = xy + 2x;6. E = Q e x y = x + xy;7. E = R e x y = 2x 3yx y;8. E = R e x y = y2+ x;9. E = R e x y = x 2y + xy 3;10. E = R e x y = x + y 2xy;11. E = R e x y = xy + 2x + 2;12. E = R e x y = y2+ xy;4. Seja E = Q munido com as opera coes () e () denidas por xy = x+y3e xy = x + y xy.Verique se () e distributiva em rela cao a ().5. Seja E = Q munido com as opera coes () e () denidas por xy = x+y1e xy = x + y xy.Verique se () e distributiva em rela cao a ().6. fazer a tabua das opra coes adi cao e multipica cao de Z4, Z5, Z8.147. Verique se as fun coes abaixo sao homomorsmos.1. f : (R, +) (R, +) dada por f (x) = ax, a > 0;2. f : (R, .) (R, .) dada por f (x) = |x| ;3. f : (R, +) (R, +) dada por f (x) = ax + b, a, b = 0;4. f : (R R, +) (R R, +)dada por f (x, y) = (2x + 3y, x y) ;5. f : (R R, +) (R, +)dada por f (x, y) = 2x + 3y;6. f : 0, 2

, +

(R, +) dada por f (x) = senx;7. f : (R, +) (R, +) dada por f (x) = x8. f : (Z, +) (Z, +) denido por f(x) = kx, k Z.9. f : (R, +) (R, +) denido por f(x) = kx + 1, k Z.10. f : (Z, +) (R, ) denido por f(x) = 3x.151. GRUPOSOBJETIVOS DO CAPITULOAo nal deste captulo o aluno devera saber:1. Denir e reconhecer grupos e subgrupos;2. Identicar os elementos neutro e identidade de um grupo;3. Identicar elementos inversos em um grupo;4. Denir e determinar grupo das permuta coes D6, R4, D8, D10, A4;5. Identicar homomorsmos e isomorsmos de grupos;6. Identicar grupos cclicos e seus geradores bem como os subgrupos;7. Determinar classes laterais de grupos cclicos;Deni cao 1.1. Seja G um conjunto nao vazio e () uma lei de composi cao interna emG que satisfaz as seguintes propriedades:i) (a b) c = a (b c) para todo a, b, c G.ii) Existe e G tal que para todo a G a e = a e e a = a. Isto e, ()posuielemento neutro.iii) Se a G entao existe a G tal que a a = e e a a = e.Nessas condi coes, o par (G, ) e denominado grupo em rela cao a opera cao().Caso () seja comutativa, entao o par (G, ) sera deominado grupo comu-taivo ou abeliano.Exemplo 1.2. Sejam G = R, e () denida por xy = x+y 3 para todo x, y G.Entao(G, ) e um grupo. De fato, vamos mostrar que () possui as propriedades dadeni cao 1.1.Sejam a,b,c G. Entao,i) (a b) c = (a +b 3) c a (b c) = a (b +c 3)= a +b 3 +c 3 = a +b +c 3 3Logo,() e associativa.ii) Sejam a G. Entao teremos, conforme a deni cao 1.1,a e = a e e a = aa +e 3 = a e +a 3 = ae = 3 e = 3.Assim, () possui elemento neutro e = 3.iii) Sejam a G, como () possui elemento neutro e = 3, podemos vericar se todoelemento de G possui simetrico conforme deni cao 1.1. Assim,2a a = e e a a = ea +a 3 = 3 a +a 3 = 3a = 6 a a = 6 aConclusao: (G, ) e um grupo em rela cao `a opera cao ().Vamos vericar se (G, ) e um grupo abeliano.Sejam a, b G, entaoa b = b aa +b 3 = b +a 3Logo, () e comutativa e, portanto, pela deni cao 1.1, (G, ) e um grupoabeliano.Deni cao 1.3. Seja (G, ) um grupo. Seja H um subconjunto nao vazio de G.Dizemos que H e subgrupo de G se, e somente se, satisfaz as seguintes propriedades:i) Para todo a, b H a b H. Isto e, H e fechado em rela cao a opera cao ().ii) (H, ) tambem e grupo em rela cao a opera cao ().1.1. GRUPO DAS PERMUTAC OESObtemos os grupo das permuta coes atraves da composi cao de fun coes seguindo o exem-plo abaixo:Sejamf = _ 1 2 3 4i1i2i3i4_ e g = _ i2i1i4i3j1j2j3j4_ duas fun coes.Suponhamos que atraves da composi cao obtivemos as seguintes rela coes:a) Se 1 i1 j2 entao 1 j2;b) Se 2 i2 j1 entao 2 j1;c) Se 3 i3 j4 entao 3 j4;d)Se 4 i4 j3 entao 4 j3.Quando escrito formalmente temos:g f = _ i2i1i4i3j1j2j3j4__ 1 2 3 4i1i2i3i4_ = _ 1 2 3 4j2j1j4j3_Exemplo 1.4. Sejam dadas as permuta coesf = _ 1 2 3 42 4 1 3_ e g = _ 1 2 3 44 3 2 1_3A composi cao das permuta coes sera dada porg f = _ 1 2 3 44 3 2 1__ 1 2 3 42 4 1 3_ = _ 1 2 3 43 1 4 2_Consideremos os elementos gerado pela rota cao e reexao de um trianguloequilatero, cujos vertices estao numerados na ordem 1, 2 e 3, primeiro no sentidohorario e apos sobre um dos seus eixos de simetria. Veja a gura abaixo.12 331 213 2RepousoApos 120 grausEixo de simetriaMOVIMENTOS DE UM TRIANGULOb

e = _ 1 2 31 2 3_ quando o triangulo esta em repouso,a = _ 1 2 32 3 1_ quando o triangulo faz um movimento rota cao de 120sobre seu eixo central.b = _ 1 2 31 3 2_ quando o triangulo faz um movimento reexao de 180sobre o vertice de n umero b=1.Fazendo as composi coes construa a tabua referente o grupo formado pelasrota coes e reexoes, denominado grupo diedral. Representaremos por D2n onde n e on umero de vertices e 2n o n umero de elementos do grupo. Assim,D6 = { e, a, a2, b, ba, ba2, ,em que ab = ba2}.1.2. GRUPOS CICLICOSDeni cao 1.5. Um grupo e cclico se possuir um gerador. Gerador e o elemento dogrupo que operado com ele mesmo gera todos os elementos do grupo.Exemplo 1.6. E elemento a = 1 gera todos os elementos de _Z, +_ = {0, 1, 2, 3, 4, 5, 6}4EXERCICIOS1. Construir a tabua do grupo das rota coes do pentagono - R5.2. Seja G = {e, a, b, c, d} um grupo em rela cao a opera cao (). Complete a tabuaabaixo sabendo que e e o elemento neutro: e a b c dea c eb ac ed b3. Construir a tabua de um grupo sobre o conjunto G ={e, a, b, c, d, f} satisfazendoa seguintes condi coes:a)G eabeliano. b)e e o neutro. c) a f = b d = ed) a d = b c = f e) a c = b b = d. f) c d = a.4. Seja G = {e, a, b, c, d, f} munido com as opera cao () e () dada pelas tabuasabaixoA) e a b c d fe e a b c d fa a b c d f eb b c d f e ac c d f e a bd d f e a b cf f e a b c dB) e a b c d fe e a b c d fa a b e f c db b e a d f cc c d f e a bd d f c b e af f c d a b ea) Encontrar todos os subgrupos de (G, ) e de (G, ).c) Mostrar que (G, ) e um grupo nao comutativo.5. Encontre todos os subgrupos nao triviais de (Z, +), (Z, +) e, em cada caso,construir os grupos quocientes e suas respectivas tabuas.51.3. HOMOMORFISMOS E ISOMORFISMOS DE GRUPOSDeni cao 1.7. Sejam (G, ) e (J, ) dois grupos. Seja f : (G, ) (J, ) umaaplica cao que satisfaz a condi caoi) f(x y) = f(x)f(y) para todo x, y G.Entao f e denominada homomorsmo do grupo (G, ) sobre o grupo (J, )Exemplo 1.8. Sejam (G, ) = (Z, +) , (J, ) = (R, ) e f : (Z, +) (R, ) denidapor f(n) = an, sendo a > 0 e a = 1. Entao f e um homomorsmo de (Z, +) em (R, ).De fato, dados m, n Z temos f(m+n) = am+n= am an= f(m) f(n),conforme def. 1.7Teorema 1.9. Seja f : (G, ) (J, ) um homomorsmo do grupo (G, ) sobre ogrupo (J, ). Entao:i) Se e G e u J forem os elementos neutros de (G, ) e (J, ), respectivamente,se temf(e) = u.ii) Se a G e a G for o simetrico de a entao f(a) = [f(a)].[f(a)] = f(a).Deni cao 1.10. : Sejam (G, ) e (J, ) dois grupos e seja f : (G, ) (J, )um homomorsmo de (G, ) em (J, ). Denominamos n ucleo do homomrsmo f aoconjunto Nf = {x G tais que f(x) = u}.Deni cao 1.11. Sejam (G, ) e (J, ) dois grupos.Seja f : (G, ) (J, ) umaaplica cao que satisfaz as condi coesi) f(x y) = f(x)f(y) para todo x, y G;ii) f e bijetora.Entao f e denominada isomorsmo do grupo (G, ) sobre o grupo (J, ).Exemplo 1.12. Considere os conjuntos Z7 = {-, ', =, , _, _, } e G = {a, b, c, d, e, f, g}juntamente com as tabuasabaixo, que representam os grupos (Z7, +) e (G, )A)+ 0 1 2 3 4 5 60 0 1 2 3 4 5 61 1 2 3 4 5 6 02 2 3 4 5 6 0 13 3 4 5 6 0 1 24 4 5 6 0 1 2 35 5 6 0 1 2 3 46 6 0 1 2 3 4 5B) e a b c d f ge e a b c d f ga a b c d f g eb b c d f g e ac c d f g e a bd d f g e a b cf f g e a b c dg g e a b c d f6Construir um isomorsmo f de (Z7, +) sobre (G, ).Soluc ao: Primeiro devemos identicar os elementos neutros de cada grupo.Vemos que 0 e o elemento neutro de (Z7, +) e e e o elemento neutro de G. Logo, peloteorema 1.9 devemos ter f(0) = e.O passo seguinte e tomar um elemento de (Z7, +) e relacionar com um ele-mento de (G, ). Por exemplo, f(1) = a.Pelo teorema 1.9 devemos ter f(1) = [f(1)] = [a] = a, ou seja,f(1) =f(6) = g .Repete-se o processo para os outros elementos de (Z7, +). Vamos escreverf(2) = b. Pelo teorema 1.9 devemos ter f(2) = [f(2)] = [b] = f, ou seja,f(2) = f(5) =f. Agora, fazendo f(3) = c devemos ter f(4) = d. Portanto, um dos isomorsmos f :(Z7, +) (G, ) e dado por :0fe, 1fa, 2fb, 3fc, 4fd, 5ff, 6fg.EXERCICIOS:1. Sabendo que G = {a, b, c, e, d, f, g, h, i} e um grupo grupo (G, ) isomorfo aogrupo (Z, +), construir a tabua referente a (G, ).2. Sabendo que G = {a, b, c, e, d, f, g, h, i, j, l, m} e um grupo grupo (G, ) isomorfoao grupo (Z'=, +), construir a tabua referente a (G, ).3. Construa os seguintes subgrupos: a) [1, ] em Z. b) [3, ] em (Z, ). c) [3, +]em (Z, +)..4. Escreva um grupo cclico de ordem quatro e um nao cclico.5. As tabuas abaixo referen-se aos conjuntos E = {a, b, c, d, e, f} e G = {a, b, c, d, e, f, g, h}uma estrutura de grupo. Encontre em cada grupo:a) Todos os geradores do grupo (E, ) e do grupo (G, );b) Todos os subgrupos de (E, ) e de (G, ) bem como os seus geradores;c) O perode de cada elemento de (E, ) e de (G, );d) Encontre x E tal que b x c = d;e) Encontre x G tal que a x b = d;f) Construa um isomorsmos de (Z, +) sobre cada um dos grupos se existirem.Tabua referente ao grupo (E, ): e a b c d fe e a b c d fa a b c d f eb b c d f e ac c d f e a bd d f e a b cf f e a b c d7Tabua referente ao grupo (G, ) e a b c d f g he e a b c d f g ha a d c g f e h bb b h d a g c e fc c b f d h g a ed d f g h e a b cf f e h b a d c gg g c e f b h d ah h g a e c b f d1.4. CLASSES LATERAIS - TEOREMA DE LAGRANGEDeni cao 1.13. Seja (H, ) subgrupo de (G). Dado a G denimos classe lateral `aesquerda modulo H como sendo o subconjunto de G dado por a H = {a x tal quex H, a G} e classe `a direita modulo H como sendo o subconjunto de G dado porH a = {x a tal que x H, a G}.Exemplo 1.14. Seja (G, ) = (Z, +) e H= {0, 3}. Encontre todas as classeslaterais modulo H.Soluc ao: Para determinar aH devemo fazer a opera cao de cada elementoa G com todos os elementos x H. Da mesma forma para determinar H a devemofazer a opera cao de todo x H com cada elemento a G . Assim, temos0 +H = {0 + 0, 0 + 3} = {0, 3} assim como H + 0 = {0 + 0, 3 + 0} = {0, 3};1 +H = {1 + 0, 1 + 3} = {1, 4} assim como H + 1 = {0 + 1, 3 + 1} = {1, 4};2 +H = {2 + 0, 2 + 3} = {2, 5} assim como H + 2 = {0 + 2, 3 + 2} = {2, 5};3 +H = {3 + 0, 3 + 3} = {3, 0} assim como H + 3 = {0 + 3, 3 + 3} = {3, 0};4 +H = {4 + 0, 4 + 3} = {4, 1} assim como H + 4 = {0 + 4, 3 + 4} = {4, 1};5 +H = {5 + 0, 5 + 3} = {5, 2} assim como H + 5 = {0 + 5, 3 + 5} = {5, 2};Observe que0 +H = 3 +H, tambem H + 0 = H + 3, alem disso, como (Z, +) e comutativo,temos 0 +H = H + 0;1 +H = 4 +H, tambem H + 1 = H + 4, alem disso, como (Z, +) e comutativo,temos 1 +H = H + 1;2 +H = 5 +H, tambem H + 2 = H + 5, alem disso, como (Z, +) e comutativo,temos 2 +H = H + 2.Exemplo 1.15. Considerando o grupo diedral D6 = {e, a, a2, b, ba, ba2, onde ab = ba2}e o subgrupo de D6 dado por H = {e, b} encontre todas as classes laterais modulo H.Soluc ao: Procedendo como no exemplo anterior temos:eH = {ee, eb} = {e, b} da mesma forma He = {e, b};aH = {ae, ab} = {a, ba2} da mesma forma Ha = {a, ba};a2H = {a2e, a2b} = {a2, a2b} = {a2, ba} da mesma forma Ha2= {a2, ba2};bH = {be, bb} = {b, e} da mesma forma Hb = {b, e};baH = {bae, bab} = {ba, a2} da mesma forma Hba = {ba, a};ba2H = {ba2e, ba2b} = {ba2, a} da mesma forma Hba2= {ba2, a2};Observe que, neste exemplo, aH = Ha, a2H = Ha2, baH = Hba e ba2H =Hba2. Isso ocorre porque D6 nao e comutativo.81.5. PRINCIPIO DE INDUC AO MATEMATICAUsamos o princpio da indu cao matematica para provar que uma proposi caoP(n) e verdadeira para todo n N. Sem isso, poderiamos armar que P(n) e verdadeiraapenas para os valores de n testados. Em 1640 Fermat armou que os n umeros obtidospela fun cao F(n) = 2(2n)+ 1 eram primos.Para fazer essa arma cao Fermat analisouapenas F(0) = 3, F(1) = 5, F(2) = 17, F(3) = 257 e F(4) = 65537.Porem, 99 anosapos, em 1739, Euler mostrou que F(5) = 2(25)+ 1 = 4294967297 = (6700417)(641) e,portanto, F(5) nao e primo.O processo evolve tres etapas a saber:i) Provar que P(n) e verdadeira para n = 1;ii) Formular a hipotese da indu cao supondo que P(n) e verdadeira para n = s;iii) Provar que P(n) e verdadeira para n = s + 1.Exemplo 1.16. Vamos considerar os primeiros n-termos da PAan = 3n+1, {4, 7, 10, ....3n+1} Sabemos que a somos dos primeiros n-termos de uma PA e dada por Sn =(a1+an)n2.Portanto, podemos escrever4 + 7 + 10 +...... + (3n + 1) = (5+3n)n2Usando a indu cao nita vamos provar que essa expressao e verdadeira paratodo n N.Prova: Para melhor entendimento vamos escrever P(n) = 4 + 7 + 10 +... +(3n + 1) e F(n) = (5+3n)n2e vamos mostrar que P(n) = F(n) para todo n N.Na primeira etapa devemos mostrar que P(1) = F(1). Isso signica admitirque a PA possui apenas um termo. Assim, temos P(1) = 3 1+1 = 4 e F(1) = (5+31)12=82 = 4. Logo, P(1) = F(1).Segunda etapa. Formulamos a hipotese de indu cao tomando n = s. Obtemos,entaoP(s) = 4 + 7 + 10 +... + (3s + 1) e F(s) = (5+3s)s2Vamos admitir que P(s) = F(s) seja verdadeiro.Terceira etapa. Vamos provar que P(s + 1) = F(s + 1). Temos, portanto,P(s + 1) = .. 4 + 7 + 10 +... + (3s + 1) +[3(s + 1) + 1]Note que o termo sob a chave e exatamente P(s), de modo que obtemos9P(s + 1) = P(s) + 3s + 4.Agora vamos analisar F(s + 1).F(s + 1) = [5+3(s+1)](s+1)2= [(5+3s)+3](s+1)2= (5+3s)s+(5+3s)+3(s+1)2= (5+3s)s2+ 8+6s2F(s + 1) = .. (5 + 3s)s2+8+6s2= F(s) + 4 + 3sObserve que o termo sob a chave e exatamente F(s).Como, por hipotese,P(s) = F(s) podemos concluir que P(s + 1) = F(s + 1). PoisP(s + 1) = F(s + 1)P(s) + 3s + 4 = F(s) + 4 + 3s3s + 4 = 3s + 4Conlusao 4 + 7 + 10 +... + (3n + 1) = (5+3n)n2para todo n N.EXERCICIOSUsasndo o processo de indu cao verique se sao verdadeiras as arma coesabaixo para todo n N.1. 3 + 5 + 7 +... + (2n + 1) = n2+ 2n.2. 1 + 3 + 5 + 7 +... + (2n 1) = n23. 1 + 3 + 5 + 7 +... + (2n + 1) = n2+ 2n + 1 = (n + 1)24. 3 + 6 + 9 +... + 3n = (3+3n)n2.5. 2 + 5 + 8 +.... + (3n 1) = (3n+1)2.6. 12+ 22+ 32+.... +n2= n(n+1)(2n+1)6.7. 5 + 6 + 11 +.... + (5n 4) = (5n+2)n2.8. 13+ 23+ 33+.... +n3= n2(n+1)24.9.112 +123 +134 +.... +1n(n+1) =nn+1.10. 20+ 21+ 22+ 23+... + 2n= 2n+11.102. PROPRIEDADE DOS NUMEROS INTEIROSNeste captulo estudaremos algumas propriedades dos n umeros inteiros tais como com-bina coes lineares, equa coes diofantinas, congruencia lineares e veremos algumas aplica coes.Iniciaremos com o conceito de divisor em Z.OBJETIVOS DO CAPITULOAo nal deste captulo o aluno devera saber:1. Denir divisao sobre os n umeros inteiros;2. Denir n umeros primos;3. Denir e encontrar maximos divisor comum;4. Resolver problemas valendo-se da propriedade d = am+bn;5. Resolver equa coes diofantinas;6. Resolver problemas envolvendo classes residuais modulo m;7. Resolver congurencias lineares;2.1. DIVISAO NOS INTEIROSDeni cao 2.1. Sejam a = 0 e b dois elementos pertencentes a Z, dizemos que a edivisor de b se existir k Z tal que b = ak.Nesse caso, denotamos por a|b e le-se adivide b .A restri cao a = 0 e necessaria. De fato, seja b = 0 e suponhamos que 0|b.Entao, pela deni cao 2.1, existe k Z tal que b = 0k donde vem que b = 0. Mas issocontraria a hipotese de que b = 0.Logo, a = 0 nao e divisor de b.No caso de b = 0,teremos 0 = 0k verdadeiro para todo k Z.Deni cao 2.2. Sejam a, b = 0 Z, denimos o algoritmo da divisao por a = bq+r,q, r Z e 0 r < |b|.Este algoritmo tambem e conhecido como algoritmo de Euclides.Deni cao 2.3. Sejam b, c, x, y Z, denominamos combina cao linear de b e c ao inetiroz = bx +cy.Teorema 2.4. Sejam a, b, c, x, y Z tais que a|b e a|c, entao a|(bx +cy).Deni cao 2.5. Sejam p Z. Dizemos que p e primo se seus unicos divisores sao 1 ep.Teorema 2.6. O n umero de n umeros primos e innito.112.2. MAXIMO DIVISOR COMUMDeni cao 2.7. Sejam a, b, c Z tais que a|b e a|c, entao a e denominado divisorcomum?? de b e c.Deni cao 2.8. Seja d um divisor comum de b e c, se todo divisor comum de b e c fortambem divisor de d dizemos que d e o maximo divisor comum, mdc, entre b e c.Caso d seja o maximo divisor comum entre b e c sera denotado por d = max(b, c).Exemplo 2.9. Sejam d=10,b =20 e c=30,entao os divisores de d,b e csao, respectivamente, os conjuntos Dd = {1, 2, 5, 10}, Db = {1, 2, 4, 5, 10, 20} e Dc ={1, 2, 3, 5, 6, 10, 15, 30}. Ja os divisores comus entre b e c sao elementos do conjuntoDb Dc = {1, 2, 5, 10} = Dd. Logo, d = 10 e o maximo divisor comum entre b = 20 ec = 30 e, portanto, denotaremos por 10 = max(20, 30).Nota c ao 1. Para facilitar nosso trabalho de agora em diante, a menos que se digao contrario, consideraremos apenas maximo divisor comum positivo de dois n umerosinteiros a e b. Usaremos a letra d para indicar o mdc da a e b, ou seja, d = max(a, b).Exemplo 2.10. Encontrar o mdc entre os n umeros 36 e 420.Soluc ao:Processo das divisoes sucessivas.Esse processo consiste em:I - Dividir 420 por 36, que produz um quociente q e um resto 0 r < 36. Ser = 0 entao 36 e o mdc. Caso contrario, passamos ao item II.II - Dividir 36 por r, que produz um quociente q1 e um resto 0 s < r. Ses = 0 entao r e o mdc. Caso contrario, passamos ao item III.III - Dividir r por s, que produz um quociente q3 e um resto 0 t < s. Set = 0 entao s e o mdc. Caso contrario, passamos ao item IV.IV - Repete-se o processo ate encontrar um quociente qn e o resto zero.Quando o ultimo resto for zero o pen ultimo resto sera o mdc procurado.Para facilitar o trabalho os resultados serao dispostos como abaixo:q q1q2 qn420 36 r s t dr s t . 0Para esta congura cao, temos d = (420, 36).Completando o quadro com o valores numericos temos11 1 2420 36 24 1224 12 0Portanto, 12 = max(420, 36).Teorema 2.11. Sejam a, b Z tais que d = max(a, b), entao existem m, n Z taisque d = am +b n.12Exemplo 2.12. Dados a = 726 e b = 275 encontre m, n Z tais que se d = max(726, 275)entao d = m726 +n275.Soluc ao: Primeiro vamos determinar d usando o processo das divisoessucessvas.2 1 1 1 3 2726 275 176 99 77 22 11176 99 77 22 11 0Como podemos ver d = 11 e, portanto, temos 11 = m726 +n275.Agora, na coluna da esquerda, vamos escrever as divisoes sucessivas necessariaspara determinar d e na coluna da direita a equa cao de cada resto.726 = 275 2 + 176 176 = 726 275 2 equa cao(1)275 = 176 1 + 99 99 = 275 176 1 equa cao(2)176 = 99 1 + 77 77 = 176 99 1 equacao(3)99 = 77 1 + 22 22 = 99 77 1 equacao(4)77 = 22 3 + 11 11 = 77 22 3 equa cao(5)Vemos que na equa cao(5) da segunda coluna, esta presente o n umero 22 querepresentado pela equa cao(4). Substitumos o 22 equa cao(5) pelo seu valor represetadopela equa cao(4) e efetuamos apenas as opera coes algebricas.11 = 77 22 3Substituimos o resto 22 pelo seu valor na equa cao (4) temos11 = 77 (99 77 1 ) 3Distribuindo o n umero 3 vem11 = 77 99 3 + 77 3Adicionando o termos semelhantes vem11 = (3) 99 + 77 4Note que o n umero 77, obtido na linha anterior,e o resto representado pelaequa cao (3). Substituimos o resto 77 pelo valor na equ cao (3) temos11 = (3) 99 + (176 99 1 ) 4Distribuindo o 4 vem11 = (3) 99 + 176 4 + (4) 99Adicionando o termos semelhantes vem11 = (7) 99 + 176 4Substituimosoresto 99 pelo seu valor na equ cao (2) temos11 = (275 176 1) 7 + 176 4Distribuindo o 7 vem1311 = (7) 275 + 176 7 + 176 4Adicionando o termos semelhantes vem11 = (7) 275 + 176 11Substituimosoresto 176 pelo seu valor na equ cao (1) temos11 = (7) 275 + (726 275 2) 11Distribuindo o 11 vem11 = (7) 275 + 726 11 + (22) 275Adicionando o termos semelhantes vem11 = (29) 275 + 726 11.Finalmente, podemos escrever 11 = 726 11 + 275 (29), que comparadacom a equa cao d = m726 +n275 conclumos que m = 11 e n = 29.Teorema 2.13. Sejam a, b Z e d = max(a, b), entao os n umeros m, n Z tais qued = ma +nb nao sao unicos.Demonstrac ao: Sejam a, b, m, n Z e d = max(a, b) tais que d =ma +nb. Entao, podemos escrever:d = ma + 0 +nbd = ma + (kba +kba) +nbd = (mkb)a + (ka +n)b.Portanto, (mkb) e (ka +n) tambem satisfazem a equa cao d = ma +nb.Deni cao 2.14. Sejam a, b Z tais que 1 = max(a, b), entao a e b sao denominadosprimos entre si.Exemplo 2.15. Os n umeros 5 e 7 sao tais que 1 = max(5, 7), logo, sao primos entre si.2.3. EQUAC OES DIOFANTINASDeni cao 2.16. Sejam a, b, c, x, y Z tais que c = ax + by. A combina cao linearc = ax +by e denominada equa cao diofantina a duas variaveis do primeiro grau.Veremos a seguir alguns resultados que permitem solucionar tais equa coes.Teorema 2.17. A equa cao c = ax+by tem solu cao se, e somente se, d = max(a, b) fordivisor de c.Exemplo 2.18. Resover a equa cao diofantina 12740x + 7260y = 60.Soluc ao: primeiro determinamos d = max(12740, 7260).1 1 3 12 1 2 212740 7260 5480 1780 140 100 40 205480 1780 140 100 40 20 014Como 20 = max(12740, 7260) e 20|60, pelo teorema 2.17, a equa cao dio-fantina 12740x + 7260y = 60 tem solu cao.Para facilitar o trabalho, podemos dividir toda a equa cao por d = 20 obtendo,assim, a equa cao 637x + 363y = 3. Resolvendo esta, estaremos resovendo a primeira.Usando o processo das divisoes sucessivas obtemos637 = 363 1 + 274 274 = 637 363 1363 = 274 1 + 89 89 = 363 274 1274 = 89 3 + 7 7 = 274 89 389 = 7 12 + 5 5 = 89 7 127 = 5 1 + 2 2 = 7 5 15 = 2 2 + 1 1 = 5 2 2Procedendo como no exemplo 2.12, obtemos1 = 5 2 2 ou 1 = 5 ( 7 5 1) 21 = 3 5 2 7 ou 1 = 3 ( 89 7 12) 2 71 = 3 89 38 7 ou 1 = 3 89 38 (274 89 3)1 = 117 89 38 274 ou 1 = 117 (363 274 1) 38 2741 = 117 363 155 274 ou 1 = 117 363 155 (637 363 1)1 = 272 363 155 637Portanto, obtemos 1 = 637(155) + 272 363.Mas a equa cao inicial e 3 = 637x + 363y. Logo, devemos multiplicar oresultado obtido por 3, isto e, 3 = 637(465) + 816 363.Multiplicando por 20 o termos a, b e c obtemos a equa cao original 60 =12740(465) + 7260(816).Comparando com a equa cao c = am + bn temos como solu cao m = 465 en = 816.Teorema 2.19. Seja (x0, y0) ZXZ uma solu cao de ax+by = c em que 1 = max(a, b).Entao o par (x1, y1) ZXZ e outra solu cao de ax+by = c se, e somente se, xt = x0+bt eyt = y0at.Exemplo 2.20. Consideremos o resultado do exemplo 2.18. Entao o conjunto solu caoda equa cao diofantina 12740x+7260y = 60 e S = { x1 = 465+7260t e y1=81612740t,t Z}.Deni cao 2.21. Seja mum inteiro positivo. A rela cao , le-se rela cao de equivalenciamodulo m, e denida para todo par de elementos a, b Z por a b(modm) se, e somentese, m|(a b).Exemplo 2.22. Como exemplos podemos escrevera)10 2(mod4) pois 4|(10 2).b)17 3(mod7) pois 7|(17 3).c)100 19(mod9) pois 9|(100 19).15A rela cao divide Z em classes de equivalencia dadas por:0 = [0] = {x Z tal que x = tm, t Z}; ou todos os inteiros que divididospor m tem resto 0.1 = [1] = {x Z tal que x = tm + 1, t Z}; ou todos os inteiros quedivididos por m tem resto 1.2 = [2] = {x Z tal que x = tm + 2, t Z}; ou todos os inteiros quedivididos por m tem resto 2.3 = [3] = {x Z tal que x = tm + 3, t Z}; ou todos os inteiros quedivididos por m tem resto 3...........................................................................m1 = [m 1] = {x Z tal que x = tm + (m 1), t Z}; ou todos osinteiros que divididos por m tem resto m1.Exemplo 2.23. Escreva as classes de equivalencia para a b(mod7) .Solu cao: Temos as classes:0 = [0] = {x Z tal que x = 7t, t Z}; ou todos os inteiros que divididospor 7 tem resto 0.1 = [1] = {x Z tal que x = 7t+1, t Z}; ou todos os inteiros que divididospor 7 tem resto 1.2 = [2] = {x Z tal que x = 7t+2, t Z}; ou todos os inteiros que divididospor 7 tem resto 2.3 = [3] = {x Z tal que x = 7t+3, t Z}; ou todos os inteiros que divididospor 7 tem resto 3.4 = [4] = {x Z tal que x = 7t+4, t Z}; ou todos os inteiros que divididospor 7 tem resto 4.5 = [5] = {x Z tal que x = 7t+5, t Z}; ou todos os inteiros que divididospor 7 tem resto 5.6 = [6] = {x Z tal que x = 7t+6, t Z}; ou todos os inteiros que divididospor 7 tem resto 6.Como o leitor pode observar, a rela cao a b(mod7) dividiu Z em sete classesde equivalencia.Deni cao 2.24. Sejam a b(modm) e c d(modm). Denimos as opera coes adi caoe multiplica cao por:i) a +c b +d(modm);ii) ac bd(modm).Como conseq uencia da deni cao 2.24, podemos escrever:i) a +c = a +c;ii) ac = ac.Teorema 2.25. Sejam a, b Z tal que a b(modm) entao an bn(modm).Demonstrac ao: Execcio demonstre usando o princpio da indu cao nita.16Exemplo 2.26. Fazer a tabua da adi cao e multiplica cao para a congruencia a b(mod7).Solu cao: Temos a tabuas+ 0 1 2 3 4 5 60 0 1 2 3 4 5 61 1 2 3 4 5 6 02 2 3 4 5 6 0 13 3 4 5 6 0 1 24 4 5 6 0 1 2 35 5 6 0 1 2 3 46 6 0 1 2 3 4 5 0 1 2 3 4 5 60 0 0 0 0 0 0 01 0 1 2 3 4 5 62 0 2 4 6 1 3 53 0 3 6 2 5 1 44 0 4 1 5 2 6 35 0 5 3 1 6 4 26 0 6 5 4 3 2 1Exemplo 2.27. Muitas vezes o leitor ja deparou-se com um exemplar do calendarioperpetuo e vericou as facilidades que ele apresenta para encontrar um determinado diada semana num deterninado mes e ano. Para elaborar o calendario pepetuo fazemos usoda congruencia a b(mod7), pois a semana tem sete dias. Vamos elaborar uma fra caodesse calendario.Inicialmente estabelecemos uma rela cao entre os dias da semana e o conjuntosde restos congruencia a b(mod7)1 = {dias dos mes que sao domingos};2 = {dias dos mes que sao segundas feiras};3 = {dias dos mes que sao ter cas feiras};4 = {dias dos mes que sao quartas feiras};5 = {dias dos mes que sao quintas feiras};6 = {dias dos mes que sao sextas feiras};7 = {dias dos mes que sao sabados};O calendario perpetuo e uma tabua de restos congruencia a b(mod7). Nacoluna `a esquerda distribumos os anos e nas demais os meses .ano J F M A M J J A S O N D99 b Para encontrar o valor de b que devera ocupar cada celula da tabua docalendario resolvemos a equa cao(dia da semana procurado) +b = (classe do dia da semana).Por exemplo, o dia quatro de fevereiro de de 1999 caiu numa quinta feira.Entao fazemos4 +b = 5, implica em b = 1.17Logo, b = 1 e o n umero que ocupa a celula (99, F). Ou sejaano J F M A M J J A S O N D99 1 Para que o resultado da equa cao (dia da semana procurado)+b = (classe do dia da semanao seja negativo toma-se um valor da classe do dia da semama adequado e se ocorrerr > 7 resolve-se a congruencia x b(mod7).Repete-se o processo para as demais celulas dessa linha.Vamos construir a tabua do calendario perpetuo para o perodo 1998 - 2006.Procedendo como descrito acima,determinamos os restos modulo 7 quecompoe a linha referente a 1998.Composta primeira linha podemos obeter o valor de cada celula da segundalinha adicionando uma unidade `a celula imediatamente superior. Por exemplo,a celula(99, F) e igual a celula (98, F)+1 e, assim por diante. Portanto, para faciltar o trabalho,pode-se usar esse recurso tendo o cuidado de, nos anos bisextos, adicionar 2 `a ceulaimediatamente superior do mes de mar co do ano em curso ate fevereiro do ano seguinte.Esse procedimento pode ser observado nas linhas dos anos 2000 e 2006. Para 2007,novamente adiciona-se 1.ano J F MA MJun Jul Ago S O N D98 4 0 0 3 5 1 3 6 2 4 0 299 5 1 1 4 6 2 4 0 3 5 1 300 6 2 3 6 1 4 6 2 5 0 3 501 1 4 4 0 2 5 0 3 6 1 4 602 2 5 5 1 3 6 1 4 0 2 5 003 3 6 6 2 4 0 2 5 1 3 6 104 4 0 1 4 6 2 4 0 3 5 1 305 6 2 2 5 0 3 5 1 4 6 2 406 0 3 3 6 1 4 6 2 5 0 3 507 1 4 4 0 2 5 0 3 6 1 4 608 2 5 5 1 3 6 1 4 0 2 5 0Como usar a t abuaSuponhamos que desejamos saber qual do dia da semana que caiu 31 dedezembro de 2001. Na celula (01, D) econtramos r = 6. Substituimos na equa cao(dia da semana procurado) +b = (x). Assim, obteremos31 + 6 = x, ou x = 37.18Como 37 b(mod7) implica em b = 2, segue que 31 de dezembro de 2001caiu numa segunda feira.Teorema 2.28. Sejam a, b Z.Entao a b(modm) se, e somente se, tem o mesmoresto quando divididos por m.Demonstrac ao: Exerccio.Corolario 2.29. Todo n umero inteiro modm e congruente a um, e somente um, dosinteiros 0, 1, 2, 3, ....., m1.Demonstra cao: Exerccio.No exemplo abaixo apresentamos uma aplica cao do corolario 2.29.Exemplo 2.30. Determine o resto de divisao de 3739por 17.Soluc ao: Uma forma de resolver problemas desse tipo e iniciar procurandoa menor potencia de 37 que seja maior ou igual a 17. Como podemos ver 371satisfaz.Como segundo passo escrevemos o algoritmo de Euclides para 371e 17.Temos entao,371= 17 2 + 3. Logo, 17|(3713), ou seja, 371 3(mod17).O terceiro passo consiste em procurar uma potencia do resto r = 3 que sejamaior ou igual a 17.Como podemos observar 33> 17.Na seq uencia, escrevemos os n umeros 33e 17 usamdo o algortmo de Euclides. Isto e, 33= 27 = 17 1 + 10, de modo que33 10(mod17). Pelo teorema 2.25, podemos escrever(371)3 33(mod17) donde vem que (371)3 10(mod17) ou 373 10(mod17)Daqui para frente repete-se os procedimentos de terceiro passo ate terminara opera cao.Assim, temos(373)2 102(mod17), que equivalele a 376 15(mod17).(376)2 152(mod17), que equivalele a 3712 4(mod17).(3712)3 43(mod17), que equivalele a 3736 13(mod17).Agora nao podemos mais elevar 3736a outra potencia, pois o problema pro-posto e a potencia 3739.Assim, usando a deni cao 2.24, podemos escrever3736 373 13 10(mod17), donde resulta 3739 11(mod17).Portanto, o resto da divisao de 3739por 17 e r = 11.Exemplo 2.31. Fermat imaginou ter descoberto uma formula para determinar n umerosprimos. Armou que todo n umero que fosse imagem da fun cao F(n) = 22n+ 1, n N,era primo. Vericou que F(1) = 5, F(2) = 17, F(3) = 257 e F(4) = 65 537 eramprimos. Porem, Euler mostrou que F(5) = 232+ 1 = 429 49 6 729 e m ultiplo de 641.19Mostre que 232+ 1 0(mod641).Teorema 2.32. Sejam a, b, c Z tais que ac bc(modm). Se d = max(m, c) entaoa b(modmd ).Corolario 2.33. Sejam a, b, c Z tais que ac bc(modm). Se 1 = max(m, c) entaoa b(modm).Corolario 2.34. Sejam a, b, c Z e p um n umero primo. Se p|c e ac bc(modm),entao a b(modm).Teorema 2.35. (Pequeno teorema de Fermat) Sejam p Z um n umero primo e a Ztais que (a, p) = 1, entao vale a congruencia ap1 1 (modp).Teorema 2.36. ( Generaliza cao do pequeno teorema de Fermat). Sejam p Z umn umero primo, entao para qualquer a Z vale a congruencia ap a (modp).2.4. CONGRUENCIAS LINEARESVamos considerar o seguinte problema.Sejam a, b, m = 0 Z. Determinar todos os valores de x Z tais queax b(modm).Tal problema e conhecido como congruencia lienar do primeiro graumodulo m.Deni cao 2.37. Seja ax b(modm) uma congruencia lienar do primeiro grau modulom. Dizemos que x0 e solu cao de ax b(modm) se, e somente se, ax0 b(modm).Exemplo 2.38. Seja 8x 3(mod5) uma congruencia lienar do primeiro grau modulom.Entao x0 = 1 e solu cao, pois 8 1 3(mod5) implica em 5|( 8 1 3).O inteirox0 = 6 tambem e solu cao. O leitor podera vericar que o conjunto solu cao da equa cao8x 3(mod5) eS = {....., 14, 9, 4, 1, 6, 11, 16, .........5n + 1, n Z}Note que S = [x0] = x0.Teorema 2.39. Sejam a, b, m = 0 Z e seja d = (a, m), entao a congruecia linearax b(modm) tem solu cao se, e somente se, d|b.Demonstrac ao: Exerccio.Teorema 2.40. Seja ax b(modm) uma congruencia linear que tem solu cao x0. Entaoxi = x0 +imd , i = 1, 2, ..., (d 1) sao as outras solu coes de ax b(modm).O conjunto solu cao sera dado por S = {x0, x1, x2, ........, x(d1)}Exemplo 2.41. Resolver a congruencia linear 315x 12(mod501).Soluc ao: A congruencia linear 315x 12(mod501) pode se representadacomo se fosse uma equa cao diofantina, isto e 315x +501y = 12. Assim, primeiro vamosdeterminar d = (315, 501).Temos20. 1 1 1 2 3 1 4501 315 186 129 57 15 12 3186 129 57 15 12 3 0 .Como 3 = (315, 501) e 3|12, pelo teorma 2.39, segue que 315x 12(mod501).Agora, escrevemos as divisoes sucessvas usando o algoritmo de Euclides eprocedemos como na resolu cao das equa coes diofantinas. Temos501 = 315 1 + 186 o que implica em 186 = 501 315 1;315 = 186 1 + 129 o que implica em 129 = 315 186 1;186 = 129 1 + 57o que implica em57 = 186 129 1;129 = 57 2 + 15 o que implica em 15 = 129 57 2;57 = 15 3 + 12 o que implica em 12 = 57 15 3;15 = 12 1 + 3 o que implica em 3 = 15 12 3;Agora, substituindo cada resto pelo seu valor encontrado na coluna `a direitatemos:3 = 15 12 3 = 15 (57 15 3) = 4 15 57 13 = 4 15 57 1 = 4 (129 57 2) 57 1 = 4 129 9 573 = 4 129 9 57 = 4 129 9 (186 129 1) = 13 129 9 1863 = 13 129 9 186 = 13 (315 186 1) 9 186 = 13 315 22 1863 = 13 315 22 186 = 13 315 22 (501 315 1) = 22 501 + 35 315Portanto, 3 = 22 501 + 35 315. Multiplicando tudo por 4 obtemos12 = 501(88) + 140 315Desse modo 501|(31514012). Logo, 315140 12(mod501) e, uma solu caoe x0 = 140.Para determinar as demais solu coes usamos a formula do teorema 2.40. Comod = 3 segue que i {1, 2}. Assim, como xi = x0+imd , cada solu cao e imagem da fun caoxi = 140 +i5013 , ou xi = 140 +167i, donde x1 = 140 +167 1 = 307, x2 = 140 +167 2 =474. Consequentemente, o conjunto solu cao e dado por S = {140, 307, 474}.212.5. APLICAC OES: C odigos e Corretores de errosUm codigo detector de erros e um conjunto de regras que uma mensagem tem queobedecer para estar correta.Se a mensagem recebida nao obedecer tais regras, houveum erro na comunica cao. Nesse caso diz-se que o codigo detectou o erro.Exemplos: de codicos1. Codigos de barras;2. Dgito no n umero de cheque, da conta ou da agencia;3. Codigos ISBN usados para identicar lvros. ISBN - International StandardNook Number. O codigo ISBN de um livro e um n umero de 10 dgitos. Oprimeiro digito identica a lngua em que foi escrito ou o pas onde foi publicado,conforme o caso, os tres dgitos seguintes a editora, os cinco seguintes o livro e ultimo o controle para detec cao de erros.4. N umero da carteira de de Identidade;5. N umero de serie das cedulas do dinheiro;6. Controle de remessas e outras opera coes de transferencia de dinheiros;7. N umero de cartao credito;8. Controles remotos: televisao, leitor de DVD, portao da garagem. O comandoemite uma mensagem numerica e o receptor transforma essa mensagem numaa cao (mudar de canal, abrir a garagem,...).Neste caso a possibilidade de erro ebastante elevada.Nesses exemplos o codigo permite detectar erros mas nao os corrige. Emcertos casos, existe a necessidade de corrigir os erros. O exemplo mais usual de umasitua cao onde sao usados codigos de identica cao e corre cao de erros e no sistema detransmissao de dados (imagem, som ou texto). Neste tipo de sistemas sao usados ampli-cadores de sinal que permitem corrigir um certo n umero de erros. A possibilidade decorrigir erros e uma das vantagens dos sistemas digitais: internet, TV digital, grava caode CDs.2.6. O caso geralOs sistemas de detec cao de erros, EAN - codigos de barras e ISBN - identicadores delvros, sao dois exemplos de codigos que pertencentes `a classe dos codigos modulares.Deni cao 2.42. Um codigo modular de comprimento n e modulo m e constitudo porn n umeros naturais, (p1, p2, ......, pn), inferiores a k.Um n umer x1x2...xn pertence a este codigo se verica a seguinte regra:p1x1 +p2x2 +p3x3 +......pnxn (modm)Nota: Os n umeros naturais, (p1, p2, ......, pn) sao pesos associados ao respec-tivo xi.Os dgitos x1, x2,..., xn podem nao ser algarismos.Apenas e necessario que sefa ca a identica cao do valor numerico com a letra correspondente. No codigo ISBN Xesta associado ao n umero 10.22Exemplo 2.43. O codigo ISBN e um codigo modular de comprimento 10 e modulo 11.Ja o codigo de barras e um codigo modular de comprimento 10 e modulo 10.Teorema 2.44. Um codigo modular (p1, p2, ......, pn) de modulo m detecta:1. erros singulares, substitui cao de um digito por outro na posi cao i se, e somente se,mdc(pi, m) = 1;2. a troca dos dgitos nas posi coes i e j e somente se, mdc(pipj; m) = 1.Nota c ao 2. Como m e um n umero primo, entao um codigo modulo m detecta todosos erros singulares.Deni cao 2.45. Seja m, a, b N tais que 0 a < b < m, dizemos que a e b saosimetricos aditivos modulo m se (a +b) 0 (modm).Exemplo 2.46. (2 + 8) 0 (mod10), (3 + 8) 0 (mod11)Deni cao 2.47. Sejam m, a, b N tais que 0 a < b < m, dizemos que a e b saoinversos multiplicativos modulo m se ab 1 (modm).Exemplo 2.48. 2 8 1 (mod15), 3 2 1 (mod5)Numera cao dos CPF1. Distribua os 9 primeiros dgitos do CPF em um quadro colocando os pesos 10,9, 8, 7, 6, 5, 4, 3, 2 abaixo da esquerda para a direita, conforme representa caoabaixo:a b c d e f g h i cont1 cont2N umerodoCPF 1 9 4 7 5 5 5 1 9 X YPeso 10 9 8 7 6 5 4 3 22. Multiplique os valores de cada coluna:a b c d e f g h i cont1 cont2N umerodoCPF 1 9 4 7 5 5 5 1 9Peso 10 9 8 7 6 5 4 3 2 X YNumXpeso 10 81 32 49 30 25 20 3 183. Calcule o somatorio dos resultados Numpeso

Numpeso = 10 + 81 + 32 + 49 + 30 + 25 + 20 + 3 + 18 = 268Fazemos 268 4 (mod11), porque o sistema e decimal e 11 e o primeiro n umeroprimo maior do que 10.4. Caso o resto da divisao seja menor que 2, o primeiro dgito vericador e o 0 (zero),caso contrario subtrai-se o valor obtido de 11, que e esse caso. Sendo assim, odgito vericador e 11 4, ou seja, 7. Ja temos portanto parte do CPF, isto e,194.755.519-4Y.5. Para calcular o Segundo Dgito Vericador, repetimos os passos 2 e 3 e 4 usandoo dgito ja calculado come cando a linha dos pesos com 11a b c d e f g h i cont1 cont2N umerodoCPF 1 9 4 7 5 5 5 1 9 7 YPeso 11 10 9 8 7 6 5 4 3 2NumXpeso 11 90 36 56 35 30 25 4 27 14236. Calcule o somatorio dos resultados Numpeso

Numpeso = 11 +90 +36 +56 +35 +30 +25 +4 +27 +14 = 328. Fazemos328 9 (mod11) 328mod11 = 97. Caso o resto da divisao seja menor que 2, o segundo dgito vericador se torna0 (zero), caso contrario subtrai-se o valor obtido de 11, que e nosso caso.Sendoassim o dgito vericador e 11-9, ou seja, 2. Ja temos portanto segundo dgitoidenticador do CPF, isto e, 194.755.519-72Codigos de barrasO que e um codigo de barras UPCUPCsignica codigo universal de produtos. Os codigos de barrasUPC foram originalmente criados para ajudar os mercados a aumentar a velocidadedo processo de verica cao na sada e melhorar o controle de estoques, porem por sereciente, o sistema estendeu-se rapidamente a todos os outros produtos de varejoOs codigos UPC originaram-se em uma empresa chamada Uniform CodeCouncil ,UCC (em ingles). Um fabricante solicita permiss ao para a UCC para entrar nosistema UPC. Para isso o fabricante paga uma taxa anual. Em troca, a UCC emite aofabricante um n umero de identica cao de fabrica cao de seis dgitos e fornece diretrizesde como usa-lo. Voce pode ver o n umero de identica cao do fabricante em todos oscodigos UPC padrao de 12 dgitos, como este mostrado na parte de tras do livro TheTeenagers Guide to the Real World,(em ingles) publicado pela BYG Publishing (emingles)Voce pode ver que este smbolo UPC impresso em uma embalagem tem duaspartes:1. O codigo de barras legvel por maquinas;2. O n umero UPC de 12 dgitos legvel por humanos.O n umero de identica cao de fabrica cao da BYG Publishing sao os seisprimeiros dgitos do n umero UPC - 639382. Os cinco n umeros seguintes - 00039 -sao os n umeros de tem. Um funcionario da empresa, chamado coordenador UPC, e re-sponsavel pela aloca cao do n umero de item em produtos, garantindo que o mesmo codigonao seja utilizado em mais de um produto, retirando codigos `a medida que produtos saoretirados de linha, etc. Geralmente, cada item que um fabricante vende, assim comotodos os tamanhos de embalagens e todas as novas embalagens deste item, necessitamde um codigo diferente. Entao uma lata de Coca-Cola de 354ml necessita de um codigode item diferente do que uma garrafa de Coca-Cola de 473ml, assim como um pacotede 6 latas de 354ml, um pacote com 12, uma caixa de 24 latas, e assim por diante.Etarefa do coordenador UPC manter todos estes n umeros corretos.O ultimo dgito de um codigo UPC e chamado de dgito de verica cao. Estedgito permite que o scanner determine se este n umero foi escaneado corretamente ounao. Aqui esta como e calculado o dgito de verica cao para os outros 11 dgitos docodigo, usando o codigo 63938200039, conforme do The Teenagers Guide to the RealWorldexemplicado acima:1. some o valor de todos os dgitos em posi coes mpares (dgitos 1, 3, 5, 7 e 9). 6 +9 + 8 + 0 + 0 + 9 = 322. multiplique esse n umero por 3. 32 x 3 = 96243. some o valor de todos os dgitos em posi coes pares (dgitos 2, 4, 6, 8 e 10).3 + 3+ 2 + 0 + 3 = 114. some este valor ao valor no passo 2.96 + 11 = 1075. para criar o codigo vericador, determine o n umero que, quando adicionado aon umero do passo 4, seja m ultiplo de 10. 107 + 3 = 110Dessa forma, o dgito vericador e 3.Cada vez que o scanner le o codigo de barras de um item, ele executa estecalculo. Se o dgito de verica cao calculado for diferente do dgito de verica cao lido, oscanner sabe que algo saiu errado e que este item deve ser escaneado novamente.25EXEERCICIOS1. Um vendedor de joias possui 112 aneis, 80 colares e 48 pulseiras. Para impressionaros clientes deseja distribulos em mostruarios de modo a conterem o mesmo emenor n umero de pe cas tanto no total como na natureza. Determine on umero demostruarios e o n umero de pe cas de cada natureza que comporao o mostruario.2. Um terreno retangular de 114m de comprimento e 112m de lagura e cercado porarvores plantadas em igual distancia uma das outras. Havendo maior distanciapossvel entre as arvoresconsecutivas, determine o n umero de arvores existentes,se plantarmos uma arvore em cada canto.3. Um quitandeiro distribuiu 36 laranjas,60 abacaxis e 84 ma cas. entre variasfamlias modo cada famlia recebesse mesmo e menor n umero possvel de cadaespecie. Determine o n umero de famlias aquinhoadas, e o n umero de frutas decada especie recebidas por famlia.4. Tre rolos de bras otica tem respectivamente 168m, 26m e 312m. Deseja-se corta-los em parte iguais, de modo que as partes tenham o maior comprimento posssvel.Determine, o n umero de partes e o comprimento de cada parte.5. Tenho mais de R$ 150,00 e menos de R$ 360. Contando-os de 8 em 8, 10 em 10ou 12 em 12 sempre sobram 5. Determine o n umero de reais em meu poder.6. Numa corrida de carros, tres carros cruzam a linha de chegada emparelhados naterceira volta . A partir dai passam a completar as voltas em 4, 5 e 6 minutos. De-termine apos quanto tempo os tres carros cruzarao novamente a linha de chegadajuntos.7. Reolver as equa coes diofantinas:1. 134x + 163y = 61,2. 1343x + 763y = 20,3. 637x + 363y = 3,4. 1360x + 636y = 16.5. 252x 312(mod1325);6. 3640x 91(mod7293);8. Obtenha os restos das divisoes:a) 3253por 5. b)47512por 23, c) 71027por 11, d) 271563por 41.9. Moste que 7|(23n1) e 8|(32n+ 7).1. Introdu cao1.1. Por que estudar l ogica?Estuda-se logica para tomar conhecimento dos metodos e princpios usados para distin-guir o raciocnio correto do incorreto.Uma pessoa com conhecimento desses metodostem maior probabilidade de raciocinar corretamente do que aquele que nao estudou talassunto.Na informatica, o trabalho de programa cao exige um raciocnio especial depensamento no qual se realizam inferencias ou resultam conclusoes a partir de premissas.A inferencia e um processo que permite chegar a uma proposi cao com base em uma oumais proposi coes tomadas com ponto de partida do processo.FraseFrase e um elemento da comunica cao que relaciona palavras entre si por meio doselementos gramaticais com objetivo de formular uma mensagem com sentido completo.As frases podem ser:1. Declarativas: O Brasil ca na America do Sul.2. Imperativa: Estude logica.3. Interrogativa: Quem fez o trabalho de logica?4. Exclamativa: Que beleza!1.2. Proposi c aoProposi cao e uma frase declarativa, com sujeito e predicado, que admite apenas umdos valores logicos verdadeiro ou falso, nisso diferem das perguntas, ordens ouexclama coes.Exemplo 1.1. Por exemplo:1. Joinville ca em Santa Catarina. O valor logico e verdadeiro.2. Curitiba ca em Sao Paulo. O valor logico e falso.3. 3+8= 11 O valor logico e verdadeiro.4. 3+8=10 . O valor logico e falsoExemplo 1.2. Nao sao proposi cao as frases que nao admite apenas os valores logicosV ou F.1. Ele e um jogador de futebol. Nao e proposi cao porque o sujeito e indenido.2. Que beleza! Nao e proposi cao porque e uma exclama c ao.3. Quando o professor vai corrigir a prova? Nao e proposi cao porque e uma pergunta.4. Fa ca os exerccios de logica. Nao e proposi cao porque e uma ordem.2Classica cao das proposi c oesAs proposi coes podem se simples ou compostas.1. Simples quando e formada por apenas uma frase declarativa e;2. composta quando formada por duas ou mais frases.Exemplo 1.3. Sao proposi coes:1. Maria e analista de sistemas. (proposi cao simples).2. Maria e analista de sistemas e Maria e programadora. (proposi cao composta).1.3. ArgumentoArgumento e um conjunto de proposi coes tal que se arme ser uma delas derivadas dasoutras, ou seja uma e a conclusao do argumento e as outras s ao premissas.A conclusao de um argumento e aquela proposi cao que se arma com basenas outras proposi coes desse mesmo argumento.Exemplo 1.4.E um argumentoTodas as baleias sao mamferos. (premissa)Todas os mamferos tem pulmoes. (premissa)Portanto, todas baleias tem pulmoes. (conclusao).Em geral as palavras indicadoras de conclusoes sao: portanto, logo, da,assim, consequentemente, segue-se que, podemos inferir, podemos concluir. Entra aspalavras indicadoras de premissas estao: porque, desde que, como, dado que, etc.Exemplo 1.5. Sao exemplos de novas proposi coes mediante o uso de conectivos logicos1. Joinville nao ca em Santa Catarina.2. Todas as baleias sao mamferos e tem pulmoes.3. Se as baleias sao mamferos entao elas tem pulmoes.4. As baleias sao mamferos se, e somente se, elas tem pulm oes.1.4. Conectivos l ogicosConectivos logicos ou operadores logicos sao palavras usadas para forma cao de novasproposi coes a partir de outras.Os conectivos logicos sao: nao, e, ou, se ... entao, ... se, e somente se,....A simbologia para os conetivos logicos sao:1. Conjun cao: e = ;2. Disjun cao nao exclusiva: ou = ;3. Disjun cao exclusiva: ou = ;4. Condicional: ...se entao = ;5. Bicondicional: .... se, e somente se ;Para negar uma proposi cao usa-se o smbolo.3Outras formas de ler as proposi c oes condicionais e bicondicionais.1. Na proposi cao se p entao q, a proposi cao e denominada antecedente, hipoteseou premissa, ou ainda condi cao suciente para q.A proposi cao q e denominadaconsequente, tese, conclusao ou condi cao necessaria para p.2. Na proposi cao bicondicional p se, e somente se q, p e denominada condi caonecessaria suciente para q. A proposi cao q e denominada condi cao necessariasuciente para p.Muitas pessoas usam condi cao Sine qua non, ou condi cao sine qua none uma expressao que originou-se do termo legal em latim que pode ser traduzido comosem o qual nao pode ser.Linguagem simb olicaToda proposi cao pode ser escrita na forma de linguagem simbolica.Exemplo 1.6. A proposi cao Se Valeria for alta e bonita entao ela pode ser modelo efazer sucesso.Esta proposi cao e um perodo composto por quatro ora c oes, a saber:1. p: Valeria for alta;2. q: Valeria for bonita;3. r: Valeria pode ser modelo;4. s: Valeria pode fazer sucesso.Na forma simbolica escreveremosSe p q r sExemplo 1.7. A proposi cao Se Valeria nao for alta e Valeria for bonita entao ela naopode ser modelo e pode fazer sucesso.Esta proposi cao e um perodo composto por quatro ora c oes, a saber:1. p: Valeria for alta;2. q: Valeria for bonita;3. r: Valeria pode ser modelo;4. s: Valeria pode fazer sucesso.Na forma simbolica escreveremosSe p q r sExerccio 1.8. Escreva na forma simbolica as proposi coes:41. Se os juros continuarem altos entao a ina cao caira e o crescimento economicosera reduzido.2. Pedro e alto e elegante.3. Pedro nao e alto, mas e elegante.4. A raiz quadrada de quatro e um n umero par e primo.5. A raiz quadrada de dezesseis e um n umero par nao primo.6. Se a raiz quadrada de quatro e um n umero primo, entao ele so tem dois divisores.7. Um triangulo e retangulo se, e somente se o quadrado da hipotenusa for igual asoma dos quadrados dos catetos.8. Nao e verdade que o n umero 236 e divisvel por 2 e por 3, ou o n umero 236 edivisvel por 6.9. O n umero 236 e divisvel por 2 e por 3, mas e divisvel por 4.10. O n umero 236 e divisvel por 2 e por 3 se, e somente se e divisvel por 6.11. Escreva a nega cao de: Um triangulo e retangulo se, e somente se o quadrado dahipotenusa for igual a soma dos quadrados dos catetos.Exerccio 1.9. Considerando as proposi coes simples - p:chove; q:faz frio e r:jogocancelado, escreva na linguagem natural as proposi coes compostas.a) p q b) p q c) p qd) se p q r e) se p q r f) se p q rg) se p q r h) se p q r i) p q1.5. Valor l ogico de uma proposi caoO valor logico de uma proposi cao e a verdade V se ela for verdadeira e a falsidadeF se ela for falsa.Exemplo 1.10. Sejam a proposi coes:1. p: Todas as baleias sao mamferos. Entao, o valor logico de p e V(p)=V.2. q: O hexagono tem sete lados. Entao, o valor logico de q e V(q)=F.3. r: 2 e raiz da equa cao x-2=0. Entao, o valor logico de r e V(p)=V.Princpios fundamentais da l ogica1. Principio da nao contradi caoUma proposi cao nao pode ser simultaneamente verdadeira e falsa.2. Principio do terceiro excludoToda proposi cao ou e so verdadeira ou e so falsa.Portanto, toda proposi cao admite um e apenas um dos valores logicos V ouF.51.6. Tabela verdadeTabela verdade e uma maneira pratica de dispor de forma organizada os valores logicosrelativos a uma proposi cao.Para a proposi cao simples p:Todas as baleias sao mamferos a tabelaverdade e dada porpVFe pFVPara a proposi cao composta: Todas as baleias sao mamferos

petodas as baleias tem pulmoes

qa tabela verdade e um arranjos dos valores logicos dasproposi coes p e q.p qV VV FF VF F1.7. Resultados l ogicos em tabelas verdade.Considere as proposi coes compostas:a) Conjun c ao: Dois e um n umero par e dois e um n umero primo. Sejamp: dois e um n umero par;q: dois e um n umero primo.Usando conetivos logicos escrevemos p q.Essa proposi cao so e verdadeira se p e q forem verdadeiras. A tabela verdadesera.p q p qV V VV F FF V FF F Fb) Disjun c ao: Valeria e medica ou professora. Temos o caso da disjun cao naoexclusiva. Sejam:6p: Valeria e medica;q: Valeria e professora.Como Valeria pode exercer simultaneamente essas prossoes, a proposi cao e verdadeiraquando:1. p e q forem verdadeiras, isto e, Valeria e medica e professora;2. p for verdadeira e q falsa , isto e, Valeria e medica mas nao e professora;3. p for falsa e q verdadeira, isto e, Valeria nao e medica mas e professora;se p e q forem falsas, isto e, Valeria nao e medica e nao e professora, entao aproposi cao e falsa.A tabela verdade sera.p q p qV V VV F VF V VF F Fc) Disjun c ao exclusina: Valeria nasceu em Joinville ou Curitiba. Temos o caso dadisjun cao nao exclusiva. Sejam:p: Valeria nasceu em Joinville;q: Valeria nasceu em Curitiba.Como Valeria pode nao pode ter nascido simultaneamente em municpiosdiferentes a proposi cao e verdadeira quando:1. p for verdadeira e q falsa , isto e, nasceu em Joinville;2. p for falsa e q verdadeira, isto e, nasceu em Curitiba;A proposi cao e falsa nos demais casos.A tabela verdade sera.p q p qV V FV F VF V VF F Fd) Condicional: Se Valeria nasceu em Rio Negro entao ela e brasileira. Sejamp: Valeria nasceu em Rio Negro;q: Valeria e brasileira;Cidades com o nome de Rio Negro existem no Brasil e na Argentina. Essa proposi caoe verdadeira nos seguintes casos.71. p e q forem verdadeiras, isto e, Valeria nasceu em Rio Negro do Brasil;2. p for falsa e q for verdadeira, Valeria nao nasceu em Rio Negro mas em outracidade do Brasil;3. p for falsa e q falsa , isto e, Valeria nao nasceu em Rio Negro e nem em outracidade do Brasil;A proposi cao falsa se p for verdadeira e q for falsa, isto Valeria nasceu emRio Negro da Argentina entao ela nao e brasileira.A tabela verdade sera.p q p qV V VV F FF V VF F Ve) Bicondicional: Um triangulo e retangulo se, e somente se o quadrado da hipotenusafor igual a soma dos quadrados dos catetos. Sejam:p: o triangulo e retangulo;q: o quadrado da hipotenusa for igual a soma dos quadrados dos catetos.Essa proposi cao e verdadeira nos seguintes casos.1. p e q forem verdadeiras, isto e, o triangulo e retangulo e o quadrado da hipotenusafor igual a soma dos quadrados dos catetos;2. p e q forem ambas falsas, isto e, o triangulo nao e retangulo e o quadrado dahipotenusa nao e igual a soma dos quadrados dos catetos.A proposi cao falsa nos demais casos.A tabela verdade sera.p q p qV V VV F FF V FF F VPor que usar tabelas verdade?Usamos tabelas verdade com objetivo vericar se duas proposi coes sao equivalentes.Exemplo 1.11. Considere a proposi cao: Valeria e medica ou Marcelo n ao e professorequivale a dizer que:1. Valeria e medica se e somente se Marcelo nao e professor;82. Se Valeria e medica, entao Marcelo nao e professor;3. Se Valeria medica entao Marcelo nao e professor;4. Valeria nao e medica e Marcelo nao e professor;5. Se Marcelo e professor, entao Valeria e medica.Solu cao: Para responder a questao faremos a tabela verdade da proposi caoValeria e medica ou Marcelo n ao e professor, apos de cada uma das arma coes.A arma cao cuja tabela verdade for idenctica `a da proposi cao sera equvalente a esta.Sejam p: Valeria e medica e q: Marcelo e professor, entao;p q q p qV V F VV F V VF V F FF F V V, 1)p q p qV F FV V VF F VF V F, 2)p q p qV F FV V VF F VF V V,3)p q p qF V VF F VV V VV F F, 4)p q p qV V VV F FF V VF F V, 5)p q q pV V VV F VF V FF F VVericamos que a tabela verdade p q e equivalente `a tabela verdadeq p. Logo, falar Valeria e medica ou Marcelo nao e professor equivale a dizer que seSe Marcelo e professor, entao Valeria e medica.Exemplo 1.12. Fazer a tabela verdade para a proposi cao: se n umero 36 e divisvel por2 e por 3, entao o n umero 36 nao e divisvel por 9.Solu cao: Sejam: p: o n umero 36 e divisvel por 2; q: o n umero 36 edivisvel por 3 e r: o n umero 36 e divisvel por 9. Entao,p q r pqr pqrV V V V F FV V F F V VV F V F F VV F F F V VF V V F F VF V F F V VF F V F F VF F F F V VExerccio 1.13. Fazer a tabela verdade para cada uma das proposi coes;1. (p (q r)) (p q) ;2. (p (q r)) (p q) ;3. ((p (q r)) (p q) );94. (p (q r)) (p q) ;5. (p (q r)) (p q) ;6. (p (q r)) (p q).1.8. TautologiaUma proposi cao composta e uma tautologia quando seu valor logico e sempre a verdadeindependente dos valores logicos da proposi coes componentes .Exemplo 1.14. A proposi cao Nao e verdade que Valeria e medica ou Marcelo e profes-sor se e somente se Valeria nao e medica e Marcelo nao e professor e uma tautologia,De fato, sejam as proposi coes: p: Valeria e medica e q: Marcelo nao eprofessor. A tabela verdade sera:p qpq p q (p q) p q (p q) ( p q)V V F F V F F VV F F V V F F VF V V F V F F VF F V V F V V V1.9. Contradi caoUma proposi cao composta e uma contradi cao quando seu valor logico e sempre a falsi-dade independente dos valores logicos da proposi coes componentes .Exemplo 1.15. A proposi cao: Valeria e medica ou Marcelo e professor se e somente seValeria nao e medica e Marcelo nao e professor e uma tautologia,De fato, sejam as proposi coes: p: Valeria e medica e q: Marcelo nao eprofessor. A tabela verdade sera:p qpq p q p q (p q) ( p q)V V F F V F FV F F V V F FF V V F V F FF F V V F V F1.10. Indetermina c aoUma proposi cao composta e uma indetermina cao nao e tautologia e nem contradi cao.Exemplo 1.16. A proposi cao: se Valeria e medica ou Marcelo e professor, entao Valerianao e medica e Marcelo nao e professor e uma tautologia,De fato, sejam as proposi coes: p: Valeria e medica e q: Marcelo nao eprofessor. A tabela verdade sera:p qpq p q p q (p q) ( p q)V V F F V F FV F F V V F FF V V F V F FF F V V F V V101.11. Implica cao l ogicaA proposi cao composta A implica na proposi cao composta B quando a proposi cao condi-cional AB resultar numa tautologia. Nesse caso denotamos por A = B e le-se Aimplica B.Exemplo 1.17. Sjam as proposi coes:A: Valeria e medica se e somente se Marcelo nao e professor;B: Se Valeria e medica, entao Marcelo nao e professor;Sejam p:Valeria e medica e q: Marcelo e professor, entao as tabelasverdade sao;A:p q p qV F FV V VF F VF V F, B:p q p qV F FV V VF F VF V VeA B A BF F VV V VV V VF V VLogo, A =B ou seja A implica B1.12. Equivalencia l ogicaDuas proposi coes compostas A e B sao equivalentes se a tabelas verdade de A foi identica`a tabela verdade de B. Nesse caso, denotamos por A B ou A B e le-se A eequivalente a B.Exemplo 1.18. O exemplo 1.11 apresenta uma eqivalencia logica ao armar: Valeria emedica ou Marcelo nao e professor equivale a dizer que se Se Marcelo e professor, entaoValeria e medica, visto que as tabalas verdade sao identicas.Exemplo 1.19. As proposi coes A: (p q) (q p) e B: p q sao equivalentes.De fato, as tabelas verdade sao:A:p q pq qp (p q) (q p)V V V V VV F F V FF V V F FF F V V Ve B:p q pqV V VV F FF V FF F VOs valores logicos da proposi cao A sao identocos aos da proposi cao B.Exerccio 1.20. Verique se sao tautologias, contradi coes ou indetermina coes:1. (p q) r;2. p (q r);3. ( (p q)) ( q q);4. (p q)) ( q q);11Exerccio 1.21. Verique se sao verdadeiras as proposi coes:1. (p (p q)) =q;2. (p q) (q r) =(q r);3. ((p q) r) (p (q r));4. (p q) =(p r) (q r);1.13. Nega cao das opera c oes l ogicasNega cao da nega caoConsidere a proposi cao: Valeria e professora, sua nega cao e Valeria nao e professora ea nega cao da nega cao e Valeria e professora, isto e, ( p) p. Vejamos a tabelaverdade,.p p ( p)V F VF V FLogo, ( p) p. Ha uma propaganda do jornal A Folha de S ao Pauloque usa a nega cao da nega cao para dizer que seu jornal deve ser lido quando arma: na da para nao ler.Nese caso, a proposi cao e p: da para ler, p: nao da para ler e ( p): nao da par nao ler.Nega cao da conjun caoDada a conjun cao (p q) a nega cao (p q) e ( p q).Considere a proposi cao composta A: o SFC e o campeao paulista elibertadores de 2011A nega cao de A e o SFC nao e o campeao paulista ou nao e o campeaoda libertadores de 2011.De fato, sejamp: o SFC e o campeao paulista de 2011;q: o SFC e o campeao da libertadores de 2011;As tabelas verdade de A e B sao:A:p q p q (p q)V V V FV F F VF V F VF F F V, B:p q p qF F FF V VV F VF V VLogo, A B ou seja (p q) p q.12Nega cao da disjun caoDada a disjun cao (p q) a nega cao (p q) e ( p q).Considere a proposi cao composta A: o Corinthians e o campeao paulistaou libertadores de 2011A nega cao de A e o Corinthians n ao e o campeao paulista e nao e ocampeao da libertadores de 2011.De fato, sejamp: o Corinthians e o campeao paulista de 2011;q: o Corinthians e o campeao da libertadores de 2011;As tabelas verdade de A e B sao:A:p q p q (p q)V V V FV F V FF V V FF F F V, B:p q p qF F FF V FV F FF V FLogo, A B ou seja (p q) p q.Nega cao da condicionalDada a proposi cao condicional (p q) a nega cao (p q) e p q.Considere a proposi cao composta A: o SFC e o campeao libertadoresde 2011, entao e o campeao mundial de 2011.A nega cao de A e se o SFC e o campeao libertadores de 2011 e o SFCnao e o campeao mundial de 2011.De fato, sejamp: o SFC e o campeao libertadores de 2011;q: o SFC e o campeao mundial de 2011;As tabelas verdade de A e B sao:A:p q p q (p q)V V V FV F F VF V V FF F F F, B:p q q p qV V F FV F V VF V F FF F V FLogo, A B ou seja (p q) p q.Exerccio 1.22. Dar a nega cao das proposi coes p: esta sol, q: esta frio e r: irei `a praiaescreva na linguagem natural as proposi cao composta abaixo e apos, as suas nega coesa) p q b) p q c) p ( q r)d) p q r e) ( p q) r f) se p (q r)g) se p q r h) se p q r i) p q1.14. Proposi c oes associadas a uma condi caoA proposi cao condiciona se p entao q esta associada a tres outras proposi coes tambemcondicionais, a saber:1. Recproca da condicional se q entao p;132. Contrapositiva se nao q entao nao p;3. Recproca da contrapositiva ou inversa se nao p entao nao q.Exemplo 1.23. Sejam p: Valeria sabe logica proposicional, q: Valeria e uma boa pro-gramadora.1. Se Valeria sabe logica proposicional, entao ela e uma boa programadora - p q;2. Se Valeria uma e boa programadora, entao ela sabe logica proposicional - q p;3. Se Valeria uma nao e boa programadora, entao ela nao sabe logica proposicional- q p;4. Se nao Valeria sabe logica proposicional, entao ela nao e uma boa programadora- p q.141.15. Resumo: Equvaencias l ogicas notaveis.Seja p,q, e r proposi coes, tautologias e contradi coes. As equivalencias logicas sao:Dupla nega cao ( p) pLeis idempontentesp q pp q pLeis comutativasp q q pp q q pLeis associativas( p q) r p (q r)( p q) r p (q r)Leis distributivas( p q) r ( p r) (q r)( p q) r ( p r) (q r)Leis de Morgan ( p q) q p ( p q) q pIdentidadesp pp p p pLeis complementaresp p p p Condicionalp q (p q) p qp q q p (p q) p q Bicondicional p q (p q) (q p) (p q) (p q) p q p q15ExercciosEntregar no dia da prova valendo 20% sobre a nota da prova para quem naotirar 10.1. Escreva em a nega cao de cada uma das proposi coes.1. Zeca e rico e nao precisa de bolsa de estudos;2. Zeca nao e rico e nem feliz;3. Se a economia desaquece, entao aumenta o desemprego;4. Nem A e nem B necessitam de bolsa de estudos;5. Se o aluno estuda e presta aten cao nas aulas entao e aprovado;6. Se Zeca ama as plantas e os animais entao ele ama a natureza;2. Escrever em linguagem simbolica cada proposi cao do exerccio 1 e suas nega coes.3. Por meio de tabelas verdade, mostrar as equivalencias l ogicas.Leis associativas ( p q) r p (q r)( p q) r p (q r)Leis distributivas ( p q) r ( p r) (q r)( p q) r ( p r) (q r)Leis de Morgan ( p q) q p ( p q) q p4. O presidente do Banco Central arma: Se a taxa de juros SELIC for alta, entaoa ina cao baixa. Usando tabela verdade encontre a(s) proposi cao(oes) logica-mente(s) equivalente `a declara cao do presidente do Banco Central.1. Se a ina cao e alta entao a taxa de juros SELIC nao e alta;2. Se a taxa de juros SELIC nao e alta, entao a ina cao nao e baixa;3. Se a ina cao nao e baixa, entao a taxa de juros SELIC n ao e alta;4. Ou a taxa de juros SELIC e baixa, ou a ina cao e baixa.5. Usando tabela verdade encontre a(s) proposi cao(oes) logicamente(s) equivalente `anega cao da arma cao se estudar, entao tiro notas boas.1. Se nao estudar, entao tiro notas boas;2. Nao estudei e eu tiro notas boas;3. Nao estudei e eu nao tiro notas boas;4. Se nao estudar, entao nao tiro notas boas;5. Estudei e nao tiro notas boas.1. Proposi c oes e classes categ oricasNesse captulo abordaremos um tipo de raciocino denominado raciocnio dedutivo.Todo argumento dedutivo pode ser valido ou invalido. E valido quando suaspremissas sao verdadeiras e a conclusao tambem e verdadeira e, invalido caso contrario.1.1. Proposi c oes categ oricas de forma tpica.As proposi coes categoricas sao arma coes simples compostas por sujeito e predicado.Por exemplo, todo poltico e mentiroso.Sao classicadas em:1. universal armativa denotada pela letra A;2. universal negativa denotada pela letra E;3. particular armativa denotada pela letra I;4. particular negativa denotada pela letra O;Supoe-se que a escolha dessa letras para representar a classe das proposi coesencontra-se nas palavras latinas AIrmo e nEgO.Proposi cao categ orica universal armativa,A forma logica e: Todo S e PExemplo 1.1. Sao exemplos de proposi coes categoricas universal armativas1. Todos os gatos sao mamferos;2. Todo animal tem sangue quente;3. Todo poltico e mentiroso;Proposi cao categ orica universal negativa.A forma logica e: Nenhum S e P ou Todo S e n ao P.Exemplo 1.2. Sao exemplos de proposi coes categoricas universal negativas:1. Nenhum gato e mamfero;2. Todos o gato e nao mamfero;Proposi cao categ orica particular armativa;A forma logica e: algum S e P.Exemplo 1.3. Sao exemplos de proposi coes categoricas particular armativas:1. Algum gato e mamfero;2. Algum poltico e mentiroso.2Proposi cao categ orica particular negativa.A forma logica e: Algum S n ao e P.Exemplo 1.4. Sao exemplos de proposi coes categoricas particular negativa:1. Algum gato nao e mamfero;2. Algum gato e nao mamfero;Os termos, todo, nenhum e algum sao denominados quanticadores.Nota c ao 1. Os quanticadores todo e nenhum nao admitem exce coes enquanto queo quanticador algum exige pelo menos um exemplar.Rela cao entre proposi c oes categ oricas conjuntos.1. Todo S e P corresponde aSe x S, entao x P , isto e S P ou S P = S.2. Nenhum S e P corresponde aSe x S, entao x / P, isto e S P = .3. Algum S e P corresponde aExiste pelo menos um x S, tal que x P, isto e S P = .4. Algum S nao e P corresponde aExiste algum x S mas esse x / P, isto e x S P.Exerccio 1.5. Escreva as proposi coes abaixo na lingagem de conjuntos.1. Todos os homens sao mortais.2. Alguns animais podem raciocinar3. Nenhum dentista e sadico.4. Todos os torturadores sao sadicos.5. Nenhum torturador e dentista.6. Algumas crian cas sao pobres.7. Algum pobre nao e feliz.8. Nenhum tubaroes nao sao capitalistas.9. Alguns tubaroes sao peixes.31.2. Qualidade quantidadeUma proposi cao categorica de forma tpica tem uma qualidade e uma quantidade.A qualidade de uma proposi cao e armativa ou negativa segundo a in-clusao na classe.A quantidade e universal ou particular.Exemplo 1.6. Todos os mamferos tem sangue quente.A qualidade e armativa, pois a proposi cao arma que os mamferos per-tencem `a classe dos animais de sangue quente.A quantidade universal pois arma que todos os mamferos pertencem `aclasse.Exemplo 1.7. Alguns mamferos nao tem pelos.A qualidade e negativa pois a proposi cao arma que ha mamferos perten-centes `a classe dos animais que nao tem pelos.A quantidade e particular, pois arma que alguns os mamferos pertencem `aclasse dos animais que nao tem pelos.Exemplo 1.8. Nenhum cavalo voa.A qualidade e negativa, ja que a proposi cao arma que cavalos nao pertencem`a classe dos animais que voam.A quantidade universal, ja que arma que nenhum cavalo pertence `a classedos animais voam.Exemplo 1.9. Alguns soldados nao sao herois.A qualidade e negativa, ja que a proposi cao arma que ha soldados que naopertencem `a classe dos herois.A quantidade particular, ja que arma que alguns soldados nao pertence `aclasse dos herois.1.3. Distribui caoPor meio do quanticador sabemos:1. se a proposi cao se refere a todos os membros da classe dos sujeitos ou apenas dealguns dos membros sujeitos, ou2. se a proposi cao se refere a todos os membros da classe predicado ou apenas dealguns dos membros.Exemplo 1.10. Todos os mamferos tem sangue quente.A proposi cao arma que todos os sujeitos de sangue quente sao mamferos.Porem, ha animais de sangue quente que nao sao mamferos, por exemplo ospassaros. Logo, mamferos nao e qualidade de todos os animais de sangue quente.Desse modo, a proposi cao distribui a qualidade sangue quente a todos osmamferos mas nao a qualidade mamfero a todos os animais de sangue quente.Portanto, a proposi cao: Todo S e P distribui o sujeito4Tabela 1.1: Qualidade, quantidade e distribui cao das proposi caoProposi cao Qualidade QuantidadeDistribui caodo SujeitoDistribui caodo predicadoTodo S e P Airmativa Universal Sim NaoAlgum S e P Airmativa Particular Nao NaoNenhum S e P Negativa Universal Sim SimAlgum S nao e P Negativa Particular Nao SimExemplo 1.11. Nenhum cavalo voa.A proposi cao arma que nenhum dos sujeitos cavalos tem a qualidade deser voador, ou seja, todos os cavalos nao sao voadores e que todos os animais voadoresnao tem a qualidade de ser cavalos.Portanto, a proposi cao: Nenhum S e P distribui o sujeito e predicado.Exemplo 1.12. Alguns soldados sao herois.A proposi cao nao fala de todos os soldados nem de todos os herois. Dessemodo, nao distribui nem sujeito nem predicado.Portanto, a proposi cao: Algum S e P distribui nem sujeito nem predicado.Exemplo 1.13. Alguns soldados nao sao herois.A proposi cao nao fala de todos os soldados, isto e, parte dos soldados estaexcluda da classe dos herois. Porem nenhum dos herois pertence `a classe dos soldadoscovardes. Desse modo distribui o termo predicado.Portanto, a proposi cao: Nenhum S e P distribui o predicado.Em rela cao a qualidade, quantidade e distribui cao podemos formar o quadroExerccio 1.14. Considerando as proposi coes do exercco 1.5 classique-as quanto aquantidade e a qualidade everique quais termos estao distribudos.1.4. Silogismos categ oricosDeni cao 1.15. Um silogismo categorico de forma tpica e um argumento que consistede tres proposi coes categoricas de forma tpica.Exemplo 1.16. Silogismos categoricos da forma tpicaA: Todo heroi e valente.I: Algum soldado e valente.I: Logo, algum soldado e heroi. (Conclusao)5Termos de um silogismo categ orico tpico.Analisando a conclusao identicamos os termos dos silogismos.1. O sujeito da conclusao e denominado termo menor;2. O termo do predicado e denominado termo maior;3. O termo que nao aparece na conclusao e denominado termo medio.Nota c ao 2. Em rel cao `as premissas1. A proposi cao que contem o termo menor e denominada premissa menor,2. A proposi cao que contem o termo maior e denominada premissa maior,3. A proposi cao que contem os termos maior e menor e denominada conclusao dosilogismos.Figuras dos silogismos categ oricos tpicosConsidere os silogismosA: Todo heroi e valente.I: Algum soldado e valente.I: Logo, algum soldado e heroi.eA: Todo estudante e valente.I: Algum estudante e vitorioso.I: Logo, algum vitorioso e valente.Ambos sao do tipo AII, mas tem formas diferente. Simbolicamente elespodem ser escritos nas formasTodo P e M.Algum S e M.Logo, algum S e P.eTodo M e P.Algum M e S.Logo, algum S e P.Na primeira forma o termo medio e o predicado de ambas as premissas e nasegunda forma, termo medio e o sujeito de ambas as premissas.Exerccio 1.17. Nos silogismos abaixo identique os termos maior menor e medio.1. Todos os homens sao mortais.Socrates e homemLogo, Socrates e mortal.2. Todos os homens sao catarinenses.Socrates e homemLogo, Socrates e catarinense.3. Alguns animais podem raciocinarTodo homem e um animal.Logo, todo homem pode raciocinar.4. Toda ave pode voar.Toda aviao pode voar.Logo, todo aviao e ave.65. Todo asiatico e brasileiro.Alguns jogadores sao asiaticos.Logo, alguns jogadores sao brasileiros.6. Todo sapo vira prncipe.Todo gato vira sapo.Logo, todo gato vira prncipe.7 Nenhum dentista e sadico.Todos os torturadores sao sadicos.Logo, nenhum torturador e dentista.8 Nenhum desonesto e conavel.Nenhum poltico e desonesto.Logo, poltico e conavel.9. Toda crian ca e feliz.Algumas crian cas sao pobres.Logo, algum pobre e feliz.10. Alguns tubaroes sao capitalistasAlguns tubaroes sao peixes.Logo alguns peixes sao tubaroes.1.5. Regras para um silogismo ser validoDeni cao 1.18. Um silogismo ou argumento e valido se, e somente se a conclusao forverdadeira sempre que as premissas forem simultaneamente verdadeiras. Um argumentonao valido e denominado falacia.As regras para vericar se um siligismo categorico e valido sao:1. Um silogismo categorico valido deve conter exatamente tres temos e cada um dosquais usados no mesmo sentido do raciocino.Exemplo 1.19. Considere o silogismo:Todos brasileiros sao felizes.Todos os catarinenses sao brasileiros.Logo, todos os catarinenses sao felizes.Os termos sao: brasileiros, felizes e catarinenses.2. Num silogismo categorico valido o termo medio deve estar distribudo em, pelomenos, uma das premissas.Exemplo 1.20. Considere o silogismo:7Todos os catarinenses sao felizes.Todos os brasileiros sao felizes.Logo, todos os brasileiros sao catarinenses.Este silogismos tem tres termos, logo satisfaz a primeira regra.O temo medio e felizes pois nao aparece na conclusao.Porem, sendo asduas premissas universais armativas, apenas os termos menor- sujeito da conclusao-e maior- predicado da conclusao - estao distribudos. Portanto, e uma falacia.3. Num silogismo categorico valido, qualquer termo distribudo na conclusao tambemdeve estar distribudo nas premissas.Exemplo 1.21. Considere o silogismo:Todos os catarinenses sao felizes.Nenhum paulista e catarinense.Logo, nenhum paulista e feliz.Este silogismos tem tres termos, o temo medio e catarinense e esta dis-tribudo nas duas premissas. Portanto, satisfaz a primeira e a segunda regra. Mas euma falacia. Pois o temo maior feliz esta distribudo na conclusao, mas nao estadistribudo em nenhuma das premissas.4. Num silogismo categorico valido, nao pode ter duas premissas negativas.5. Um silogismo categorico valido, que tem uma premissa negativa deve ter conclusaonegativa.6. Um silogismo categorico valido, que tem duas premissas universais deve ter con-clusao universal.Exerccio 1.22. Verique quais dos silogismos do exerccio 1.17 sao validos. Justiquecada conclusao.1. Analise de argumentosArgumentar e estabelecer uma rela cao entre um conjunto de proposi coes denominadaspremissas e uma proposi cao conclusao. Como ja vimos, a logica tem como um dos seusobjetivos o estudo de um conjunto de tecnicas que permitem analisar um argumento evericar se a conclusao e verdadeira sempre que as premissas forem simultaneamenteverdadeiras.Deni cao 1.1. Sejam P1,P2,....Pne C uma sequencia nita de proposi coes quaisquer,denominamos argumento a uma sequencia nita de proposi c oes P1,P2,....Pnque temcomo conclusao a proposi cao C.A nota cao usada e P1,P2,....Pn C .Le-se: P1,P2,....Pn logo Cou P1,P2,....Pn entao C.1.1. Tipos de argumentos.Silogismos disjuntivos e hipoteticosDeni cao 1.2. Um silogismo e disjuntivo quando a primeira premissa apresenta umadisjun cao.Exemplo 1.3. A premissa P1 e: Paulo estudou ou foi reprovado. P2 e Paulo naoestudou. Logo, C e Paulo foi reprovado.A forma simbolica e:p ou q pLogo, qA tabela verdade e dada por:p q p ou qp (p ou q) pqV V V F FV F V F FF V V V VF F F V FComo pode ser visto, este argumento e sempre valido se (p ou q) q e pforem verdadeiras.Exemplo 1.4. A premissa P1 e:Paulo estudou ou foi reprovado.P2 e Paulo nao foireprovado. Logo, C e Paulo estudou.A forma simbolica e:v2p ou q qLogo, pp q p ou qq (p ou q) qpV V V F FV F V v VF V V f FF F F V FEste argumento e sempre valido se (p ou q), qe p forem verdadeiras.Exemplo 1.5. A premissa P1 e:Paulo estudou ou foi reprovado. P2 e Paulo foi re-provado. Logo, C e Paulo nao estudou.A f