itc2004cap1, Notas de estudo de Matemática

Baixe itc2004cap1 e outras Notas de estudo em PDF para Matemática, somente na Docsity! 1 L¶ogica Elementar Neste cap¶³tulo, apresentamos uma introdu»c~ao µa l¶ogica, que nos ser¶a su¯ciente como ferramenta de trabalho nos cap¶³tulos posteriores. 1.1 Proposi»c~oes e seus conectivos O estudo da l¶ogica ¶e o estudo dos princ¶³pios e m¶etodos usados para distinguir argumentos v¶alidos dos n~ao v¶alidos. O prop¶osito deste cap¶³tulo preliminar em l¶ogica ¶e ajudar o leitor a entender os princ¶³pios e m¶etodos usados em cada passo de uma demonstra»c~ao. O ponto de partida em l¶ogica ¶e o termo \proposi»c~ao", que ¶e usado num sentido t¶ecnico. Por uma proposi»c~ao queremos dizer uma declara»c~ao que ¶e verdadeira ou falsa, mas n~ao ambos. N~ao ¶e necess¶ario que saibamos se a proposi»c~ao ¶e verdadeira ou falsa; a ¶unica quali¯ca»c~ao exigida ¶e que ela deve ser de¯nitivamente uma coisa ou outra. Habitualmente, podemos determinar imediatamente se uma proposi»c~ao ¶e verdadeira ou falsa, mas em alguns casos um pouco de esfor»co ¶e preciso, e em outros casos pode ser imposs¶³vel chegar a uma conclus~ao. Os seguintes exemplos dever~ao ilustrar o que queremos dizer. Exemplo 1.1 Cada uma das seguintes frases ¶e uma proposi»c~ao. (a) Londrina ¶e uma cidade no estado do Paran¶a. (b) 2 + 1 ¶e 5. (c) O d¶³gito na 105a casa decimal, na expans~ao decimal de p 3, ¶e 7. (d) A lua ¶e feita de queijo mineiro. (e) N~ao h¶a vida inteligente em Marte. (f) Est¶a chovendo. Claramente, (a) ¶e verdadeira, enquanto (b) e (d) s~ao falsas. Podemos ter d¶uvidas quanto ao status (verdadeiro ou falso) de (c) e (e). A veracidade ou falsidade da senten»ca (f) depende das condi»c~oes meteorol¶ogicas no instante em que essa declara»c~ao ¶e feita. 1 2 L¶ogica Elementar Exemplo 1.2 Nenhuma das frases seguintes ¶e uma proposi»c~ao, porque n~ao faz sentido questionar se alguma delas ¶e verdadeira ou falsa. (a) Venha µa nossa festa! (b) Tudo bem com você? (c) Tiau, benzinho. As proposi»c~oes do Exemplo 1.1 s~ao todas proposi»c~oes simples. Uma combina»c~ao de duas ou mais proposi»c~oes ¶e uma proposi»c~ao composta. Por exemplo, \2 + 1 ¶e 5 e o d¶³gito na 105a casa decimal na expans~ao decimal de p 3 ¶e 7" ¶e uma proposi»c~ao composta. Estamos familiarizados com o uso de letras para representar n¶umeros na ¶algebra. No estudo da l¶ogica usamos letras, tais como p, q, r, : : : para representar proposi»c~oes. Uma letra, tal como p, pode representar uma proposi»c~ao simples ou composta. A menos que digamos em contr¶ario, usaremos letras mai¶usculas P , Q, R, : : : para representar proposi»c~oes compostas. Existem muitos modos de se ligar proposi»c~oes tais como p, q, r, : : : para formar proposi»c~oes compostas, mas apenas cinco modos s~ao usados freqÄuentemente. Estes cinco conectivos comuns s~ao (a) \n~ao", simbolizado por »; (b) \e", simbolizado por ^; (c) \ou", simbolizado por _; (d) \se : : : ent~ao : : : ", simbolizado por !; e (e) \ : : : se e somente se : : : ", simbolizado por $. Nesta se»c~ao discutiremos os conectivos » e ^, adiando os demais conectivos, _, !, e $, at¶e a pr¶oxima se»c~ao. Seja p uma proposi»c~ao. A proposi»c~ao » p, lida \n~ao p" ou \a nega»c~ao de p", ¶e verdadeira quando a proposi»c~ao p ¶e falsa, e ¶e falsa quando p ¶e verdadeira. Por exemplo, seja p a proposi»c~ao \Este ¶e um curso f¶acil". Ent~ao sua nega»c~ao » p representa \Este n~ao ¶e um curso f¶acil". A verdade de » p depende da verdade de p. ¶E conveniente anotar essa dependência em uma tabela verdade: Tabela 1.1: p » p V F F V na qual as letras V e F signi¯cam \verdadeiro" e \falso", respectivamente. Na primeira coluna da tabela 1.1, listamos os dois poss¶³veis valores l¶ogicos da proposi»c~ao p, sendo eles V e F . Cada linha em uma tabela verdade representa um caso que deve ser considerado, e claramente, nesta situa»c~ao bastante simples, h¶a apenas dois casos. Usando as linhas da Tabela 1.1 vemos que se p ¶e verdadeira ent~ao » p ¶e falsa, e se p ¶e falsa, ent~ao » p ¶e verdadeira. ConseqÄuentemente, a Tabela 1.1 nos diz o valor verdade1 de » p em cada caso. 1ou valor l¶ogico (N. do T.) L¶ogica Elementar 5 Nos problemas 12 a 19 encontre as tabelas verdade das proposi»c~oes dadas. Use o formato da Tabela 1.1 ou da Tabela 1.2 para os dois ou quatro casos respectivamente. 12. » (» p) 13. » [» (» p)] 14. p ^ p 15. » (p^ » p) 16. p^ » q 17. » p ^ q 18. (p ^ p)^ » p 19. » (p ^ q) 20. Numa proposi»c~ao composta, envolvendo três componentes distintas p, q e r, quantos casos s~ao necess¶arios para cobrir todas as possibilidades l¶ogicas? Quantos casos s~ao necess¶arios se houver quatro componentes distintas? Quantos casos s~ao necess¶arios se houver n componentes distintas? 21. O seguinte ¶e uma tentativa de arranjar todos os casos em uma tabela verdade, para uma proposi»c~ao envolvendo três componentes p, q, e r. Complete o trabalho inacabado. p q r ¢ V V V V F V V V F V V V F F F F F Nos problemas 22 a 25, encontre as tabelas verdade para as proposi»c~oes dadas. Use o padr~ao desenvolvido no problema 21 para os v¶arios casos. 22. (p ^ q) ^ r 23. p ^ (q ^ r) 24. (p^ » q) ^ r 25. » q ^ (r ^ p) 1.2 Três conectivos mais Na l¶³ngua portuguesa h¶a uma ambigÄuidade envolvida no uso do \ou". A proposi»c~ao \Obterei grau de mestre ou grau de doutor" indica que quem o a¯rma pode obter ambos, o grau de mestre e o de doutor. Mas em outra proposi»c~ao, \Me casarei com L¶³via ou L¶ucia", a palavra \ou" signi¯ca que apenas uma das duas mo»cas ser¶a escolhida. Na matem¶atica e na l¶ogica, n~ao podemos permitir ambigÄuidades. Portanto, devemos nos decidir sobre o signi¯cado da palavra \ou". 6 L¶ogica Elementar De¯ni»c~ao 1.2 O conectivo _ pode ser colocado entre duas proposi»c~oes quaisquer p e q para formar a proposi»c~ao composta p _ q. Os valores verdade de p _ q s~ao de¯nidos na Tabela 1.4. Portanto _ ¶e de¯nido como sendo o \ou" inclusivo, tal como usado na primeira proposi»c~ao acima. Tabela 1.4: p q p _ q V V V V F V F V V F F F O s¶³mbolo p_q ¶e lido \p ou q" ou a \disjun»c~ao de p e q". Repare que a conjun»c~ao de p e q ¶e verdadeira apenas quando as duas componentes s~ao ambas verdadeiras (Tabela 1.2), enquanto que a disjun»c~ao ¶e falsa quando e apenas quando as duas componentes s~ao falsas (Tabela 1.4). Comparemos as tabelas verdade de p _ q e » (» p^ » q), nas Tabelas 1.3 e 1.4. Notamos que em cada caso a ¶ultima coluna ¶e V V V F , de modo que estas duas proposi»c~oes tem os mesmos valores verdade em cada uma das quatro possibilidades l¶ogicas. Mostrar que certas proposi»c~oes tem os mesmos valores verdade em cada caso ¶e uma parte importante da l¶ogica. Na verdade, a l¶ogica trata duas tais proposi»c~oes como sendo uma s¶o. De¯ni»c~ao 1.3 Quando duas proposi»c~oes P e Q, simples ou compostas, tem os mes- mos valores verdade em cada uma de todas as possibilidades l¶ogicas, dizemos que P ¶e logicamente equivalente ou simplesmente equivalente a Q, e escrevemos P ´ Q. Resumidamente, duas proposi»c~oes s~ao logicamente equivalentes desde que tenham a mesma tabela verdade. Portanto, temos p _ q ´» (» p^ » q) Embora duas proposi»c~oes equivalentes sejam consideradas como a mesma, do ponto de vista da l¶ogica, preferimos a proposi»c~ao mais simples \p ou q" em vez da proposi»c~ao equivalente mais complicada \N~ao ¶e verdade que nem p e nem q". De¯ni»c~ao 1.4 O conectivo ! ¶e chamado condicional e pode ser colocado entre duas proposi»c~oes p e q para formar a proposi»c~ao composta p ! q (lida: \se p ent~ao q"). Por de¯ni»c~ao, a proposi»c~ao p! q ¶e equivalente µa proposi»c~ao » (p^ » q), e os valores verdade de p! q s~ao dados na Tabela 1.5. L¶ogica Elementar 7 Tabela 1.5: Caso p q » q p^ » q p! q [´» (p^ » q)] 1 V V F F V 2 V F V V F 3 F V F F V 4 F F V F V A motiva»c~ao da De¯ni»c~ao 1.4 ¶e a seguinte. Sejam p a proposi»c~ao \O sol est¶a brilhando" e q a proposi»c~ao \Eu estou jogando tênis". Ent~ao a proposi»c~ao composta p ! q ¶e \Se o sol est¶a brilhando ent~ao eu estou jogando tênis". Agora, quando ¶e que uma tal proposi»c~ao 'considerada falsa? Claramente p! q ¶e falsa se o sol est¶a brilhando mas eu n~ao estou jogando tênis, e apenas neste caso. Em outras palavras p! q ¶e falsa se p^ » q ¶e verdadeira, a apenas neste caso. Mas isto ¶e precisamente a De¯ni»c~ao 1.4. Estudaremos agora a tabela verdade de p! q, isto ¶e, de » (p^ » q). Conforme a De¯ni»c~ao 1.4, o signi¯cado da proposi»c~ao condicional p! q afasta-se radicalmente do nosso uso ordin¶ario de \Se p ent~ao q". Na nossa linguagem ordin¶aria,2 uma senten»c~ao da forma \Se p ent~ao q" ¶e considerada como querendo dizer que q ¶e verdadeira sempre que p ¶e verdadeira. Portanto os casos em que p ¶e falsa n~ao precisam ser considerados. Por exemplo, a proposi»c~ao \Se Collor atirou em Figueiredo, ent~ao Itamar foi o primeiro presidente" ¶e considerada sem sentido, pois ambas as componentes s~ao falsas. ConseqÄuentemente, no uso ordin¶ario n~ao se questiona se uma proposi»c~ao componente ¶e verdadeira. Ao criar a linguagem formal, o l¶ogico deseja designar um valor verdade a p ! q para cada uma das quatro possibilidades l¶ogicas, muito embora dois dos casos pare»cam ser sem sentido em nossa linguagem ordin¶aria. Por v¶arias raz~oes, que aparecer~ao no tempo devido, os l¶ogicos decidiram-se pela de¯ni»c~ao adotada aqui. Portanto, em nossa linguagem formal, p! q ¶e verdadeira em todos os casos exceto no caso 2 (veja Tabela 1.5). Como conseqÄuência desse acerto, seremos capazes de demonstrar alguns teoremas ¶uteis bastante simples, cujas demonstra»c~oes, sem tal acerto, seriam desajeitadas ou muito dif¶³ceis. Introduzimos agora o ¶ultimo dos cinco conectivos mais comuns, um que aparece freqÄuentemente nos enunciados (proposi»c~oes) de teoremas matem¶aticos. De¯ni»c~ao 1.5 O conectivo $ ¶e chamado o bicondicional e pode ser colocado entre duas proposi»c~oes p e q para formar a proposi»c~ao composta p$ q (lida: \p se e somente se q"). A proposi»c~ao p$ q ¶e equivalente µa proposi»c~ao (p! q) ^ (q ! p), e os valores verdade de p$ q s~ao dados na Tabela 1.6. 2Em oposi»c~ao µa \linguagem ordin¶aria", l¶ogica ¶e chamada uma linguagem formal. 10 L¶ogica Elementar Tabela 1.8: (p _ q) ^ » p ! q V V V F F V V V V F F F V F F V V V V V V F F F F V V F Passo 1 2 1 3 2 4 1 pelos n¶umeros que aparecem na ¶ultima linha da tabela. Em uma tabela verdade sim- pli¯cada, escrevemos os valores verdade diretamente, primeiro sob cada componente e ent~ao sob os conectivos. Isto poupa espa»co e tempo. Agora, retornando µa demonstra»c~ao do teorema, como o passo ¯nal (passo 4) na Tabela 1.8 consiste s¶o de V 's, a proposi»c~ao condicional (p _ q)^ » p ! q ¶e de fato uma implica»c~ao. Se a proposi»c~ao bicondicional P $ Q for uma tautologia, ela ¶e chamada uma equivalência e ¶e denotada por P , Q (leia-se: P ¶e equivalente a Q). Da de¯ni»c~ao 1.5 e da Tabela 1.6, P , Q se P e Q tem os mesmos valores verdade em cada uma de todas as possibilidades l¶ogicas, e reciprocamente, P e Q tem os mesmos valores verdade em cada uma de todas as possibilidades l¶ogicas se P , Q. Portanto, pela de¯ni»c~ao 1.3, P , Q e P ´ Q tem o mesmo signi¯cado, e portanto podemos trocar , por ´ e vice-versa. Teorema 1.2 Sejam p e q duas proposi»c~oes quaisquer. Ent~ao (a) Lei da Dupla Nega»c~ao (D.N.): » (» p) ´ p. (b) Leis Comutativas (Com.): p ^ q ´ q ^ p, p _ q ´ q _ p, (c) Leis de Idempotência (Idemp.): p ^ p ´ p, p _ p ´ p, (d) Lei Contrapositiva (Contrap.): (p! q) ´ (» q !» p). Demonstra»c~ao. Deixaremos as demonstra»c~oes das partes (a), (b) e (c) para o leitor, como exerc¶³cios, e delinearemos a demonstra»c~ao de (d). Temos a seguinte tabela verdade simpli¯cada para a proposi»c~ao bicondicional (p! q)$ (» q !» p): L¶ogica Elementar 11 Tabela 1.9: (p ! q) $ (» q ! » p) V V V V F V V V F F V V F F F V V V F V V F V F V V V V Passo 1 2 1 4 2 3 2 Logo, a Tabela 1.9 mostra que p$ q ¶e equivalente a » q !» p. O seguinte teorema, creditado a Augustus De Morgan (1806{1871), ¶e uma das ferramentas mais convenientes da l¶ogica. Teorema 1.3 (Leis de De Morgan (De M.)) Sejam p e q duas proposi»c~oes quais- quer. Ent~ao » (p ^ q) ´ » p_ » q; e » (p _ q) ´ » p^ » q: Demonstra»c~ao. Demonstraremos a primeira parte deste teorema e deixaremos a outra parte ao leitor, como exerc¶³cio. Constru¶³mos uma tabela verdade simpli¯cada para a bicondicional » (p ^ q)$ (» p_ » q): Tabela 1.10: » (p ^ q) $ (» p _ » q) F V V V V F F F V V F F V F V V V F F V V V V F V F F F V V V V Passo 3 1 2 1 4 2 3 2 A tabela verdade acima mostra que » (p ^ q) ¶e equivalente a » p_ » q. Teorema 1.4 Sejam p, q e r proposi»c~oes quaisquer. Ent~ao (a) Leis Associativas (Assoc.): (p ^ q) ^ r ´ p ^ (q ^ r) (p _ q) _ r ´ p _ (q _ r) (b) Leis Distributivas (Dist.): p ^ (q _ r) ´ (p ^ q) _ (p ^ r) p _ (q ^ r) ´ (p _ q) ^ (p _ r) (c) Lei Transitiva (Trans.): (p! q) ^ (q ! r)) (p! r). 12 L¶ogica Elementar Demonstra»c~ao. Deixaremos as demonstra»c~oes das Leis Associativas e da segunda Lei Distributiva para o leitor, como exerc¶³cios. Demonstremos que p ^ (q _ r) ´ (p ^ q) _ (p ^ r). Como isto envolve três componentes, existem 23 = 8 possibilidades l¶ogicas a considerar. A seguinte tabela verdade mostra que p ^ (q _ r) e (p ^ q) _ (p ^ r) tem os mesmos valores verdade em cada uma das oito possibilidades l¶ogicas. Portanto, p ^ (q _ r) e (p ^ q) _ (p ^ r) s~ao equivalentes. Tabela 1.11: p q r q _ r p ^ q p ^ r p ^ (q _ r) (p ^ q) _ (p ^ r) V V V V V V V V V V F V V F V V V F V V F V V V V F F F F F F F F V V V F F F F F V F V F F F F F F V V F F F F F F F F F F F F Por simplicidade e por economia de espa»co, constru¶³mos uma tabela verdade sim- pli¯cada, como apresentado na Tabela 1.8, para (p! q) ^ (p! r)! (p! r). Tabela 1.12: (p ! q) ^ (q ! r) ! (p ! r) V V V V V V V V V V V V V V F V F F V V F F V F F F F V V V V V V V F F F F V F V V F F F V V V V V V V F V V F V V F V F F V F V F F V F V F V V V F V V F V F V F V F V F V F Passo 1 2 1 3 1 2 1 4 1 2 1 Como o ¶ultimo passo (passo 4) consiste inteiramente de valores V , a Lei Transitiva est¶a demonstrada. Por causa das Leis Associativas, os parênteses em (p ^ q) ^ r ´ p ^ (q ^ r) e L¶ogica Elementar 15 (c) As tabelas verdade de c ! p e p ! t mostram que as duas proposi»c~oes s~ao tautologias, logo c) p e p) t. Tabela 1.15: c ! p F V V F V F p ! t V V V F V V No restante deste livro, o s¶³mbolo c, com ou sem¶³ndice, denotar¶a uma contradi»c~ao; e o s¶³mbolo t, com ou sem ¶³ndice, denotar¶a uma tautologia. 1.4.1 Exerc¶³cios 1. Demonstre que p _ t, t e p ^ c, c. 2. Demonstre que » t, c e » c, t. 3. Demonstre a seguinte Reductio ad Absurdum. (p^ » q ! c), (p! q) 4. Demonstre que p ^ (p! q) ^ (p!» q), c. 5. Demonstre que (p! q)) (p _ r ! q _ r), para qualquer proposi»c~ao r. 1.5 Racioc¶³nio dedutivo As 17 leis sumarizadas nos Teoremas de 1.1 a 1.6 s~ao ferramentas muito ¶uteis para justi¯car equivalências l¶ogicas e implica»c~oes, como ilustrado nos Exemplos de 1.5 a 1.7. Chamaremos estas 17 leis de regras de inferência. Chamamos a aten»c~ao para o fato de que estas regras foram selecionadas como referências convenientes e n~ao precisam ser independentes entre si. Por exemplo, a Lei Contrapositiva pode ser estabelecida \dedutivamente" pelo uso de outras leis e de de¯ni»c~oes relevantes, como mostra o pr¶oximo exemplo. Exemplo 1.5 Demonstre a Lei Contrapositiva, (p ! q) ´ (» q !» p), usando de¯ni»c~oes relevantes e outras regras de inferência. Solu»c~ao. (p! q) ´ » (p^ » q) Def. 1.4 ´ » (» q ^ p) Com. ´ » [» q^ » (» p)] D.N. ´ (» q !» p) Def. 1.4 16 L¶ogica Elementar Portanto, (p! q) ´ (» q !» p), pela Lei Transitiva. O m¶etodo de demonstra»c~ao usado no Exemplo 1.5 ¶e chamado racioc¶³nio dedutivo4 ou m¶etodo dedutivo, e difere do m¶etodo de demonstra»c~ao por tabelas verdade. Em geral, no racioc¶³nio dedutivo, quaisquer axiomas, de¯ni»c~oes, teoremas e regras de inferência, previamente enunciados, podem ser usados. Exemplo 1.6 Prove o Silogismo Disjuntivo por racioc¶³nio dedutivo. Solu»c~ao. (p _ q)^ » p ´ » p ^ (p _ q) Com. ´ (» p ^ p) _ (» p ^ q) Dist. ´ c _ (» p ^ q) » p ^ p ´ c ´ (» p ^ q) _ c Com. ´ » p ^ q Teorema 1.7(b) )q Simp. Finalmente, pela Lei Transitiva, (p _ q)^ » p) q. Exemplo 1.7 Demonstre a seguinte Lei de Exporta»c~ao: (p ^ q ! r) ´ [p! (q ! r)] por racioc¶³nio dedutivo. Solu»c~ao. p! (q ! r) ´ [p!» (q^ » r) De¯ni»c~ao 1.4 ´ » [p ^ (q^ » r)] Def. 1.4, D.N. ´ » [(p ^ q)^ » r] Assoc. ´ (p ^ q ! r) De¯ni»c~ao 1.4 Portanto, (p ^ q)! r ´ [p! (q ! r)]. Exemplo 1.8 Demonstre que (p ! r) _ (q ! s) ´ (p ^ q ! r _ s) por racioc¶³cio dedutivo. Solu»c~ao. (p! r) _ (q ! s) ´ » (p^ » r)_ » (q^ » s) De¯ni»c~ao 1.4 ´ (» p _ r) _ (» q _ s) De M., D.N. ´ (» p_ » q) _ (r _ s) Com., Assoc. ´ » [(p ^ q)^ » (r _ s)] De M., D.N. ´ (p ^ q ! r _ s) De¯ni»c~ao 1.4 4ou argumenta»c~ao dedutiva (N. do T.) L¶ogica Elementar 17 O porquê de querermos usar racioc¶³cio dedutivo, em oposi»c~ao a tabelas verdade, pode ser visto da seguinte compara»c~ao: Para veri¯car a equivalência no Exemplo 1.8, pelo m¶etodo das tabelas verdade, ter¶³amos que construir uma grande tabela verdade com 16 (= 24) casos (veja Problema 20 dos Exerc¶³cios 1.1.1 ou Problema 12 dos Exerc¶³cios 1.3.1); por outro lado, na solu»c~ao do Exemplo 1.8, acima, estabelecemos tal equivalência em apenas cinco passos. 1.5.1 Exerc¶³cios Demonstre as seguintes tautologias pelo m¶etodo dedutivo. 1. Modus Ponens: p ^ (p! q)) q 2. Modus Tollens: » q ^ (p! q))» p 3. Reductio ad Absurdum: (p! q), (p^ » q ! c) 4. Silogismo Disjuntivo: (p _ q)^ » p) q 5. Teorema 1.7(c): c) p 6. (p! q), (p! p ^ q) 7. (p! q), (p _ q ! q) 8. (p! q),» p _ q 9. (p! r) ^ (q ! r), (p _ q ! r) 10. (p! q) ^ (p! r), (p! q ^ r) 11. (p! q) ^ (p!» q),» p 12. (p! q) _ (p! r), (p! q _ r) 13. (p! r) _ (q ! r), (p ^ q ! r) 1.6 Regras de quanti¯ca»c~ao Em qualquer discuss~ao geral, temos em mente um universo particular ou dom¶³nio do discurso, isto ¶e, uma cole»c~ao de objetos cujas propriedades est~ao sob considera»c~ao. Por exemplo, na a¯rma»c~ao \Todos os humanos s~ao mortais", o universo ¶e a cole»c~ao de todos os humanos. Com este entendimento do universo, a a¯rma»c~ao \Todos os humanos s~ao mortais" poder ser expressada alternativamente como: Para todo x no universo, x ¶e mortal. A frase \Para todo x no universo" ¶e chamada um quanti¯cador universal, e ¶e simbolizada por (8x). A senten»ca \x ¶e mortal" diz algo sobre x; simbolizaremos isto por p(x). Usando estes novos s¶³mbolos, podemos agora escrever a a¯rma»c~ao geral \Todos os homens s~ao mortais" como (8x)(p(x)) Agora considere a a¯rma»c~ao \Alguns homens s~ao mortais". Aqui o universo (ou dom¶³nio de discurso) ¶e ainda o mesmo da a¯rma»c~ao pr¶evia. Com este universo em mente, podemos refazer a a¯rma»c~ao \Alguns homens s~ao mortais" sucessivamente como: 20 L¶ogica Elementar 3. Encontre o dom¶³nio de discurso de cada uma das proposi»c~oes do Problema 2. 4. Deduza » [(9x)(p(x))] ´ (8x)(» p(x)) a partir de » [(8x)(q(x))] ´ (9x)(» q(x)): 5. Deduza » [(8x)(p(x))] ´ (9x)(» p(x)) a partir de » [(9x)(q(x))] ´ (8x)(» q(x)): 6. Demonstre que » [(8x)(» q(x))] ´ (9x)(q(x)) e » [(9x)(» q(x))] ´ (8x)(q(x)): [Sugest~ao: Use N.Q.] 1.7 Demonstra»c~ao de validade Uma das mais importantes tarefas de um l¶ogico est¶a em testar argumentos. Um ar- gumento ¶e a asser»c~ao de que uma proposi»c~ao, chamada a conclus~ao, ¶e conseqÄuência de outras proposi»c~oes, chamadas hip¶oteses ou premissas. Um argumento ¶e considerado v¶alido se a conjun»c~ao das hip¶oteses implica a conclus~ao. Como exemplo, o seguinte ¶e um argumento no qual as primeiras quatro proposi»c~oes s~ao hip¶oteses, e a ¶ultima proposi»c~ao ¶e a conclus~ao. Se ele estuda medicina, ent~ao prepara-se para ganhar uma boa renda. Se ele estuda artes, ent~ao prepara-se para viver bem. Se ele prepara-se para ganhar uma boa renda ou para viver bem, ent~ao suas des- pesas de estudos n~ao s~ao desperdi»cadas. Suas despesas de estudos s~ao desperdi»cadas. Portanto, ele n~ao estuda nem medicina e nem artes. Este argumento pode ser simbolizado como: H1. M ! R H2. A! B H3. (R _B)!» D H4. D C. : . : »M ^ » A Para estabelecer a validade deste argumento por meio de uma tabela verdade, precisar¶³amos de uma tabela com 32 (= 25) linhas. Mas podemos demonstrar que este argumento ¶e v¶alido deduzindo a conclus~ao a partir das hip¶oteses em poucos passos usando as regras de inferência. Das hip¶oteses H3 e H4, (R _ B) !» D e D, inferimos » (R _ B), ou equiva- lentemente, » R^ » B, por Modus Tollens e Lei de De Morgan. De » R^ » B, inferimos, de maneira v¶alida, » R (e tamb¶em » B), pelas Leis de Simpli¯ca»c~ao. De H1, M ! R; com » R inferimos »M . L¶ogica Elementar 21 Analogamente, A ! B (de H2), e » B, nos faz inferir » A. Finalmente a conjun»c~ao de » M e » A nos d¶a a conclus~ao » M ^ » A. Nesta demonstra»c~ao, as regras de inferência Modus Tollens (M.T.), Leis de De Morgan (D.M.), e Leis de Simpli¯ca»c~ao (Simp.) s~ao usadas. Um modo mais formal e conciso de expressar esta demonstra»c~ao de validade, ¶e listar as hip¶oteses e as proposi»c~oes deduzidas a partir delas em uma coluna, com a justi¯ca»c~ao de cada passo numa coluna ao lado. Em cada passo, a \justi¯ca»c~ao" indica as a¯rma»c~oes precedentes das quais, e as regras de inferência pelas quais, a a¯rma»c~ao dada naquele passo foi obtida. Para f¶acil inferência, ¶e conveniente enumerar as hip¶oteses e as a¯rma»c~oes deduzidas a partir delas e colocar a conclus~ao µa direita da ¶ultima premissa, separada desta por uma barra = que indica que todas as proposi»c~oes acima s~ao hip¶oteses. A demonstra»c~ao de validade formal para o argumento acima pode ent~ao ser escrita como 1. M ! R (Hip.) 2. A! B (Hip.) 3. (R _B)!» D (Hip.) 4. D=: . : »M ^ » A (Hip./ Concl.) 5. » (R _B) 3, 4, M.T. 6. » R^ » B 5, De M. 7. » R 6, Simp. 8. » B 6, Simp. 9. »M 1, 7, M.T. 10. » A 2, 8, M.T. 11. »M ^ » A 9, 10, Conj. Uma demonstra»c~ao formal de validade para um dado argumento ¶e uma seqÄuência de proposi»c~oes, cada uma das quais ¶e ou uma premissa do argumento ou segue de proposi»c~oes precedentes por um argumento v¶alido conhecido, terminando com a con- clus~ao do argumento. Exemplo 1.10 Construir uma demonstra»c~ao formal de validade para o seguinte argu- mento, usando os s¶³mbolos sugeridos: Wilson ser¶a eleito presidente do Centro Acadêmico ou ambos, H¶elio e L¶ucio ser~ao eleitos vice-presidentes do Centro Acadêmico. Se Wilson for eleito presidente ou H¶elio for eleito vice, ent~ao David encaminhar¶a um protesto. Portanto, ou Wilson ser¶a eleito presidente do Centro Acadêmico ou David encaminhar¶a um protesto. (W;H;L;D). Demonstra»c~ao. 1. W _ (H ^ L) 2. W _H ! D=:.: W _D 3. (W _H) ^ (W _ L) 1, Dist. 4. W _H (Hip./ Concl.) 5. D 2, 4, M.P. 6. D _W 5, Ad. 7. W _D 6, Com. 22 L¶ogica Elementar Existe um outro m¶etodo de demonstra»c~ao chamado demonstra»c~ao indireta, ou m¶etodo de demonstra»c~ao por redu»c~ao ao absurdo. Uma demonstra»c~ao indireta de vali- dade, para um dado argumento, ¶e feita incluindo-se, como premissa adicional, a nega»c~ao de sua conclus~ao, e ent~ao derivando uma contradi»c~ao; assim que uma contradi»c~ao ¶e obtida, a demonstra»c~ao est¶a completa. Exemplo 1.11 Dê uma demonstra»c~ao indireta de validade para o seguinte argumento: p _ q ! r s! p ^ u q _ s =:.: r Demonstra»c~ao. 1. p _ q ! r 2. s! p ^ u 3. q _ s =:.: r 4. » r P.I. (Demonstra»c~ao Indireta) 5. » (p _ q) 1, 4, M.T. 6. » p^ » q 5, De M. 7. » p 6, Simp. 8. » q 6, Simp. 9. s 3, 8, S.D. 10. p ^ u 2, 9, M.P. 11. p 10, Simp. 12. p^ » p 7, 11, Conj. A proposi»c~ao p^ » p, no passo 12, ¶e uma contradi»c~ao; portanto a demonstra»c~ao indireta de validade est¶a completa. Em contraste a uma \demonstra»c~ao indireta", a demonstra»c~ao formal de validade introduzida anteriormente pode ser chamada \demonstra»c~ao direta". Numa demons- tra»c~ao matem¶atica, pode ser usada uma demonstra»c~ao direta ou uma demonstra»c~ao indireta. A escolha do m¶etodo de demonstra»c~ao, para um argumento matem¶atico dado, depende da preferência e da conveniência. 1.7.1 Exerc¶³cios Para cada um dos seguintes argumentos, dê uma demonstra»c~ao direta e uma demons- tra»c~ao indireta de validade, e compare seus tamanhos. L¶ogica Elementar 25 As duas equa»c~oes acima indicam que x1 = x, x2 = x ¢ x, x3 = x2 ¢ x, : : : e assim por diante. Como outra aplica»c~ao, daremos a seguinte de¯ni»c~ao indutiva do s¶³mbolo C(n; r). De¯ni»c~ao 1.7 Sejam n um n¶umero natural e r um inteiro. O s¶³mbolo C(n; r) ¶e de¯nido por C(0; 0) = 1, C(0; r) = 0 para cada r6= 0, e C(n+ 1; r) = C(n; r) + C(n; r ¡ 1) Teorema 1.8 Se n e r s~ao inteiros, tais que 0 6 r 6 n, ent~ao C(n; r) = n! r!(n¡ r)! sendo n! o produto n ¢ (n¡1) ¢ ¢ ¢ 3 ¢2 ¢1, dos primeiros n n¶umeros naturais consecutivos, se n > 0 e 0! = 1 por conven»c~ao. Demonstra»c~ao. Exerc¶³cio. Teorema 1.9 (O Teorema Binomial) Se x e y s~ao dois n¶umeros reais e n ¶e um n¶umero natural, ent~ao (x+ y)n = C(n; 0)xn + C(n; 1)xn¡1y + ¢ ¢ ¢+ C(n; r)xn¡ryr + ¢ ¢ ¢+ C(n; n)yn Demonstra»c~ao. Demonstraremos a validade deste teorema por indu»c~ao matem¶atica. Primeiramente, o teorema ¶e claramente verdadeiro para n = 1. Para completar a demonstra»c~ao, assumiremos a validade do teorema para n = k; isto ¶e, assumiremos que (x+ y)k = C(k; 0)xk + C(k; 1)xk¡1y + ¢ ¢ ¢+ C(k; r)xk¡ryr + ¢ ¢ ¢+ C(k; k)yk Ent~ao, multiplicando ambos os membros da igualdade acima por (x+ y), temos (x+ y)k+1 = (x+ y)[xk + C(k; 1)xk¡1y + ¢ ¢ ¢+ C(k; r)xk¡ryr + ¢ ¢ ¢+ yk] = xk+1 + [C(k; 0) + C(k; 1)]xky + ¢ ¢ ¢ + [C(k; r ¡ 1) + C(k; r)]x(k+1)¡ryr + ¢ ¢ ¢+ yk+1 = C(k + 1; 0)xk+1 + C(k + 1; 1)xky + ¢ ¢ ¢ + C(k + 1; r)xk+1¡ryr + ¢ ¢ ¢+ C(k + 1; k + 1)yk+1 que mostra que o teorema ¶e v¶alido para n = k + 1 se for v¶alido para n = k. Assim, por indu»c~ao matem¶atica, o teorema binomial ¶e verdadeiro para todos os n¶umeros naturais n. 26 L¶ogica Elementar 1.8.1 Exerc¶³cios 1. Demonstre o teorema 1.8 por indu»c~ao matem¶atica. 2. Mostre que C(n; 0) = 1 = C(n; n) para todo n¶umero natural n. 3. Demonstre por indu»c~ao matem¶atica que, para todo n¶umero natural n, 1 ¢ 2 + 2 ¢ 3 + ¢ ¢ ¢+ r ¢ (r + 1) + ¢ ¢ ¢+ n ¢ (n+ 1) = 1 3 n(n+ 1)(n+ 2): 4. Demonstre por indu»c~ao matem¶atica que, para todo n¶umero natural n, 12 + 22 + 32 + ¢ ¢ ¢+ n2 = 1 6 n(n+ 1)(2n+ 1): 5. Demonstre que para todo n¶umero natural n, 13 + 23 + 33 + ¢ ¢ ¢+ n3 = 1 4 n2(n+ 1)2: 6. Demonstre que para todo n¶umero natural n, 1 + 3 + 5 + ¢ ¢ ¢+ (2n¡ 1) = n2. 7. Demonstre que para todo n¶umero natural n, 1 1 ¢ 2 + 1 2 ¢ 3 + 1 3 ¢ 4 + ¢ ¢ ¢+ 1 n ¢ (n+ 1) = n n+ 1 : 8. Demonstre as seguintes Leis de De Morgan Generalizadas, (a) » (p1 ^ p2 ^ ¢ ¢ ¢ ^ pn),» p1 _ » p2 _ ¢ ¢ ¢ _ » pn (b) » (p1 _ p2 _ ¢ ¢ ¢ _ pn),» p1 ^ » p2 ^ ¢ ¢ ¢ ^ » pn 9. Demonstre as seguintes Leis Distributivas Generalizadas. (a) p ^ (q1 _ q2 _ ¢ ¢ ¢ _ qn), (p ^ q1) _ (p ^ q2) _ ¢ ¢ ¢ _ (p ^ qn) (b) p _ (q1 ^ q2 ^ ¢ ¢ ¢ ^ qn), (p _ q1) ^ (p _ q2) ^ ¢ ¢ ¢ ^ (p _ qn)