L%f3gica Matem%e1tica - 1 Parte

SABE Sistema Aberto de EducaoAv. Cel. Jos Alves, 256 - Vila Pinto Varginha - MG - 37010-540 Tele: (35) 3219-5204 - Fax - (35) 3219-5223

Instituio Credenciada pelo MEC Portaria 4.385/05Centro Universitrio do Sul de Minas - UNIS/MG Unidade de Gesto da Educao a Distncia GEaD Mantida pela Fundao de Ensino e Pesquisa do Sul de Minas - FEPESMIG

Varginha/MG

1Guia de Estudo LGICA MATEMTICA

511.3 A474g

ALVES, Alessandro Ferreira. Guia de Estudo Lgica Matemtica. Alessandro Ferreira Alves Varginha: GEaDUNIS/MG, 2007. 56p. 1. Lgica Matemtica. 2. Operaes Lgicas. 3. Tabelas-verdade. I. Ttulo.


REITOR Prof. Ms. Stefano Barra Gazzola GESTOR Prof. Ms. Toms Dias Sant Ana Supervisor Tcnico Prof. Ms. Wanderson Gomes de Souza Coord. do Ncleo de Recursos Tecnolgicos Prof. Simone de Paula Teodoro Moreira Coord. do Ncleo de Desenvolvimento Pedaggico Prof. Vera Lcia Oliveira Pereira Reviso ortogrfica / gramatical Prof. Maria Jos Dias Lopes Grandchamp Design/diagramao Prof. Csar dos Santos Pereira Equipe de Tecnologia Educacional Prof. Carina Carvalho Tavares Prof. Dbora Cristina Francisco Barbosa Prof. Lzaro Eduardo da Silva

O Autor ALESSANDRO FERREIRA ALVESLicenciado em Matemtica pela Universidade Federal de Uberlndia, mestre em Matemtica pela UNICAMP e doutor em Engenharia Eltrica tambm pela UNICAMP, no UNIS/MG ministra Matemtica, Estatstica e Computao em cursos de graduao e ps-graduao, alm de j ter coordenado cursos de ps-graduao e a Pesquisa e Extenso do curso de Matemtica.


TABELA DE CONESREALIZE. Determina a existncia de atividade a ser realizada. Este cone indica que h um exerccio, uma tarefa ou uma prtica para ser realizada. Fique atento a ele. PESQUISE. Indica a exigncia de pesquisa a ser realizada na busca por mais informao. PENSE. Indica que voc deve refletir sobre o assunto abordado para responder a um questionamento. CONCLUSO. Todas as concluses, sejam de idias, partes ou unidades do curso viro precedidas desse cone. IMPORTANTE. Aponta uma observao significativa. Pode ser encarado como um sinal de alerta que o orienta para prestar ateno informao indicada. HIPERLINK. Indica um link (ligao), seja ele para outra pgina do mdulo impresso ou endereo de Internet. EXEMPLO. Esse cone ser usado sempre que houver necessidade de exemplificar um caso, uma situao ou conceito que est sendo descrito ou estudado. SUGESTO DE LEITURA. Indica textos de referncia utilizados no curso e tambm faz sugestes para leitura complementar.

APLICAO PROFISSIONAL. Indica uma aplicao prtica de uso profissional ligada ao que est sendo estudado. CHECKLIST ou PROCEDIMENTO. Indica um conjunto de aes para fins de verificao de uma rotina ou um procedimento (passo a passo) para a realizao de uma tarefa. SAIBA MAIS. Apresenta informaes adicionais sobre o tema abordado de forma a possibilitar a obteno de novas informaes ao que j foi referenciado. REVENDO. Indica anteriormente. a necessidade de rever conceitos estudados


SUMRIO

INTRODUO ........................................................................................................... 7 UNIDADE 01 PROPOSIES E CONECTIVOS .................................................... 9 1. 2. 3. 4. 5. 6. 7. 8. A Lgica como Cincia e sua relao com a Filosofia......................................... 9 Introduo a Lgica Proposicional..................................................................... 10 Proposio e Princpios Bsicos ....................................................................... 11 Valores Lgicos das Proposies...................................................................... 12 Proposies Simples e Proposies Compostas .............................................. 12 Conectivos......................................................................................................... 13 Tabela-Verdade ................................................................................................. 14 Notao ............................................................................................................. 15

UNIDADE 02 OPERAES LGICAS SOBRE PROPOSIES ....................... 18 9. 10. 11. 12. 13. 14. 15. Introduo.......................................................................................................... 18 Negao (~) ................................................................................................... 18 Conjuno ( ) ............................................................................................... 19 Disjuno ( )................................................................................................. 21 Disjuno Exclusiva ( )................................................................................. 22 Condicional ( ) ............................................................................................ 23 Bicondicional ( ).......................................................................................... 25

UNIDADE 03 CONSTRUO DE TABELAS-VERDADE .................................... 31 16. 17. 18. 19. 20. 21. 22. Tabela-verdade de uma Proposio Composta ............................................. 31 Nmero de Linhas de uma Tabela-verdade................................................... 31 Construo da Tabela-verdade de uma Proposio Composta..................... 32 Exemplificao ............................................................................................... 32 Valor Lgico de uma Proposio Composta .................................................. 38 Uso de Parnteses......................................................................................... 40 Outros Smbolos para os Conectivos............................................................. 41


UNIDADE 04 TAUTOLOGIAS, CONTRADIES E CONTINGNCIAS. ............ 44 23. 24. 25. 26. Tautologia ...................................................................................................... 44 Princpio de Substituio para as Tautologias ............................................... 46 Contradio.................................................................................................... 47 Contingncias ................................................................................................ 48

UNIDADE 05 IMPLICAO LGICA ................................................................... 51 27. 28. 29. Definio de Implicao Lgica...................................................................... 51 Propriedades da Implicao Lgica ............................................................... 51 Tautologias e Implicao Lgica .................................................................... 53

REFERNCIAS ........................................................................................................ 56


INTRODUO

Ol pessoal, tudo bem? Estamos iniciando mais um semestre, e espero que, tenhamos uma relao harmoniosa, transparente, bastante amigvel e que acima de tudo, relevante para os nossos objetivos. Meu nome Alessandro Ferreira Alves e trabalharemos na disciplina de Lgica Matemtica com uma carga horria de 40 horas. um assunto bastante simples e s vezes no incio um pouco repetitivo, mas tenho convico que servir de um alicerce considervel para disciplinas mais especificas que sero estudadas num futuro bem prximo. Gostaria de dizer ainda, que sempre que ocorrerem dvidas, por mais simples que sejam procurem sempre perguntar ao professor, a minha tarefa tentar solucionar tais problemas. O nosso contedo est dividido em nove unidades como segue: Unidade 01: Proposies e Conectivos Unidade 02: Operaes Lgicas sobre Proposies Unidade 03: Construo de Tabelas-verdade Unidade 04: Tautologias, Contradies e Contingncias. Unidade 05: Implicao Lgica Unidade 06: Equivalncia Lgica Unidade 07: lgebra das Proposies Unidade 08: Aspectos Computacionais Unidade 09: Verificao de Programas


No incio de cada unidade est a descrio dos objetivos propostos em cada unidade, bem como, uma srie de exemplos e exerccios resolvidos. As atividades propostas no guia so para que voc faa a aplicao da teoria e enriquea com novos conhecimentos adquiridos. A partir do momento que for proposta uma atividade avaliativa e entregue o gabarito estar disponvel na MIDIATECA. Se estiver ainda com dvidas? Fale comigo por e-mail ou na sala de bate-papo. No deixe de fazer as atividades; elas so importantes mecanismos para o desenvolvimento de habilidades com clculos escritos e mentais. A compreenso total dos contedos ser efetivada mediante o seu empenho em realizar as atividades propostas e compreend-las. comigo! No deixe dvidas sem respostas. Comunique-se com colegas ou fale

Tambm encontram-se, na MIDIATECA e nas prprias avaliaes propostas, a distribuio dos pontos relativos s atividades propostas e avaliaes; e ainda endereos eletrnicos para voc enriquecer suas aulas ou pesquisar mais detalhadamente contedos. Novamente devo ressaltar que, no incio, talvez, vocs sintam certa dificuldade nas justificativas de alguns resultados, nas demonstraes (que so poucas verdade); porm, esta dificuldade vai aparecendo com o passar do tempo. Tenho certeza que com a experincia adquirida ao longo desses anos, tenho muita coisa para passar para vocs e provavelmente existe algo que devo aprender com vocs. Um bom trabalho a todos! Agora, mos a obra! Desde j os meus sinceros agradecimentos.

No existe Matemtica sem entusiasmo. Alessandro Ferreira Alves.


UNIDADE 01 PROPOSIES E CONECTIVOS

Objetivos da Unidade Apresentar uma breve introduo histrica da Lgica como Cincia; Apresentar a relevncia de se estudar a Lgica Matemtica e Computacional; Apresentar as principais definies e notaes usadas no dia-a-dia da Lgica Matemtica Clssica; Apresentar alguns exemplos introdutrios envolvendo os tpicos discutidos anteriormente.

1. A Lgica como Cincia e sua relao com a Filosofia

A lgica uma cincia de ndole Matemtica e fortemente ligada Filosofia. J que o pensamento a manifestao do conhecimento, e que o conhecimento busca a verdade, preciso estabelecer algumas regras para que essa meta possa ser atingida. Desta forma, a Lgica o ramo da Filosofia que cuida das regras do bem pensar, ou do pensar correto, sendo, portanto, um instrumento do pensar. A aprendizagem da Lgica no constitui um fim em si. Ela s tem sentido enquanto meio de garantir que nosso pensamento proceda corretamente a fim de chegar a conhecimentos verdadeiros. Podemos, ento, dizer que a Lgica trata dos argumentos, isto , das concluses a que chegamos atravs da apresentao de evidncias que a sustentam. O principal organizador da lgica clssica foi Aristteles, com sua obra chamada Organon. Ele divide a lgica em formal e material. Um sistema lgico um conjunto de axiomas e regras de inferncia que visam representar formalmente o raciocnio vlido. Diferentes sistemas de lgica formal foram construdos ao longo do tempo quer no mbito estrito da Lgica Terica, quer em aplicaes prticas na computao e em Inteligncia artificial. Tradicionalmente, Lgica tambm a designao para o estudo de sistemas prescritivos de raciocnio, ou seja, sistemas que definem como se "deveria" realmente pensar para no errar, usando a razo, dedutivamente e indutivamente. A forma como as pessoas realmente raciocinam estudado nas outras reas, como na psicologia cognitiva. Como cincia, a Lgica define a estrutura de declarao e argumento e elabora frmulas atravs das quais estes podem ser codificados. Implcita no estudo da lgica est a compreenso do que gera um bom argumento e de quais os argumentos que so falaciosos.


A Lgica filosfica lida com descries formais da linguagem natural. A maior parte dos filsofos assumem que a maior parte do raciocnio "normal" pode ser capturada pela lgica, desde que se seja capaz de encontrar o mtodo certo para traduzir a linguagem corrente para essa lgica.

2. Introduo a Lgica Proposicional

A linguagem natural, com a qual nos expressamos diariamente, muito suscetvel a ambigidades e imprecises. Existem frases no-gramaticais que possuem sentido (por exemplo, anncios de classificados no jornal) e frases perfeitamente gramaticais sem sentido ou com sentido mltiplo. Isso faz com que a linguagem no seja apropriada para o estudo das relaes lgicas entre suas sentenas. Portanto, no estudo da Lgica Matemtica e Computacional, utilizamos de uma linguagem formal. Linguagens Formais so objetos matemticos, cujas regras de formao so precisamente definidas e s quais podemos atribuir um nico sentido, sem ambigidade. Linguagem formais podem ter diversos nveis de expressividade. Geralmente, quanto maior a expressividade, maior tambm a complexidade de se manipular essas linguagens. Iniciaremos nosso estudo da lgica a partir de uma linguagem proposicional, que tem uma expressividade limitada, mas j permite expressar uma srie de relaes lgicas interessantes. Nesse contexto, uma proposio um enunciado ao qual podemos atribuir um valor verdade (verdadeiro ou falso). necessrio lembrar que nem toda sentena pode possuir um valor verdade. Por exemplo, no podemos atribuir valor verdade a sentenas que se referem ao seu prprio valor verdade, com a sentena esta sentena falsa. Esse tipo de sentena chamado de auto-referente e deve ser excludo da linguagem em questo, pois, se a sentena verdadeira, ento ela falsa; por outro lado, se ela for falsa, ento verdadeira. A linguagem proposicional exclui sentenas auto-referentes. Dessa forma, a Lgica Proposicional Clssica nos permite tratar de enunciados aos quais podemos atribuir valor verdade (as proposies) e as operaes que permite compor proposies complexas a partir de proposies mais simples, como a conjuno e , a disjuno ou , a implicao se...ento... e a negao no. A linguagem proposicional no nos permite expressar relaes sobre elementos de um conjunto, como as noes de todos, algum ou nenhum. Tais relaes so chamadas de quantificadoras.


3. Proposio e Princpios Bsicos

Definimos proposio como sendo todo o conjunto de palavras ou smbolos que exprimem um pensamento no sentido completo. As proposies transmitem pensamentos, isto , afirmam fatos ou exprimem juzos que formamos a respeito de determinados entes. Vejamos alguns exemplos de proposies como segue: a) A Lua um satlite da Terra. b) Recife a capital de Pernambuco. c) > d) sen( 5

2

)=1

A Lgica Matemtica adota como regras fundamentais do pensamento os dois seguintes princpios1 ou axiomas: (I) (II) PRINCPIO DA NO CONTRADIO: Uma proposio no pode ser verdadeira e falsa ao mesmo tempo. PRINCPIO DO TERCEIRO EXCLUDO: Toda a proposio ou verdadeira ou falsa, isto , verifica-se sempre um destes casos e nunca um terceiro. Por virtude deste princpio dizemos que a Lgica Matemtica uma Lgica

Bivalente.

Por exemplo, as proposies (a), (b), (c) e (d) citadas anteriormente so todas verdadeiras, contrariamente as cinco seguintes proposies: (a) Vasco da Gama descobriu o Brasil (b) Dante escreveu os Lusadas 3 um nmero inteiro (c) 5 (d) O nmero racional (e) tg(

4

)=2

Desta forma, percebemos que as proposies so expresses a respeito das quais tem sentido dizer que so verdadeiras ou falsas.1

Axioma uma afirmao aceita como verdadeira sem demonstrao.


4. Valores Lgicos das Proposies

Chamamos de valor lgico de uma proposio a verdade se a proposio verdadeira e a falsidade se a proposio falsa.

Os valores lgicos verdade e falsidade de uma proposio designam-se abreviadamente pelas letras V e F, respectivamente. Desta maneira, o que os princpios da no contradio e do terceiro excludo afirmam que: Toda a proposio tem um, e um s, dos valores V, F. Consideremos por exemplo as seguintes proposies: a) O mercrio mais pesado que a gua b) O Sol gira em torno da Terra O valor lgico da proposio (a) a verdade (V) enquanto que o valor lgico da proposio (b) a falsidade (F).

5. Proposies Simples e Proposies CompostasChamamos de proposio simples ou proposio atmica aquela que no contm nenhuma outra proposio como parte integrante de si mesma.

e

As proposies podem ser classificadas em: Simples ou Atmicas Compostas ou Moleculares

As proposies simples so geralmente designadas pelas letras latinas minsculas p, q, r, s,..., chamadas letras proposicionais. Vejamos alguns exemplos de proposies simples: p: Carlos careca q: Pedro estudante r: O nmero 25 quadrado perfeito


Chamamos de proposio composta ou proposio molecular aquela formada pela combinao de duas ou mais proposies.

As proposies compostas so geralmente designadas pelas letras latinas maisculas P, Q, R, S,..., tambm chamadas letras proposicionais. Vejamos alguns exemplos de proposies compostas: P: Carlos careca e Pedro estudante Q: Carlos careca ou Pedro estudante R: Se Carlos careca ento infeliz Note que cada uma delas formada por duas proposies simples. As proposies compostas tambm costumam ser chamadas frmulas proposicionais ou apenas frmulas. Quando interessa destacar ou explicar que uma proposio composta P formada pela combinao das proposies simples p, q, r, ..., escrevemos: P(p, , r, ...) As proposies simples e as proposies compostas tambm so chamadas respectivamente tomos e molculas. Devemos salientar ainda que as proposies componentes de uma proposio composta podem ser, elas mesmas, proposies compostas.

6. ConectivosDenominamos de conectivos as palavras que usamos para formar novas proposies a partir de outras.

Assim, por exemplo, nas seguintes proposies compostas: P: O nmero 6 par e o nmero 8 cubo perfeito Q: O tringulo ABC retngulo ou issceles R: No2 est chovendo

2

Geralmente o no tambm chamado de modificador.


S: Se Jorge engenheiro, ento sabe Matemtica T: O tringulo ABC eqiltero se e somente se eqingulo so conectivos usuais da Lgica Matemtica as palavras que esto em negrito, isto : e , ou , no , se ... ento , ... se e somente se ...

7. Tabela-Verdade

Segundo o Princpio do terceiro excludo, toda proposio simples p verdadeira ou falsa, isto , tem valor lgico V(verdade) ou o valor lgico F(falsidade).

Figura 01: Valores lgicos possveis.

Em se tratando de uma proposio composta, a determinao do seu valor lgico, conhecidos os valores lgicos das proposies simples componentes, se faz com base no seguinte princpio: O valor lgico de qualquer proposio composta depende unicamente dos valores lgicos das proposies simples componentes, ficando por eles univocamente determinado. Admitindo este princpio, para aplic-lo na prtica determinao do valor lgico de uma proposio composta dada, recorremos quase sempre a um dispositivo denominado tabela-verdade, na qual figuram todos os possveis valores lgicos da proposio composta correspondentes a todas as possveis atribuies de valores lgicos s proposies simples componentes. Desta forma, por exemplo, no caso de uma proposio composta cujas proposies simples componentes so p e q, as nicas possveis atribuies de valores lgicos a p e a q so:


Figura 02: Combinaes das atribuies dos valores lgicos de duas proposies p e q.

Observe que os valores lgicos V e F se alternam dois em dois para a primeira proposio p e de um em um para a segunda proposio q, e que, alm disso, VV, VF, FV e FF so os arranjos binrios com repetio dos dois elementos V e F. Para uma proposio composta cujas proposies simples componentes so p, q e r, as nicas possveis atribuies de valores lgicos a p, a q e a r so:

Figura 02: Combinaes das atribuies dos valores lgicos de trs proposies p, q e r.

Similarmente, observamos que os valores lgicos V e F se alternam de quatro em quatro para a primeira proposio p, de dois em dois para a segunda proposio q e de um em um para a terceira proposio r, e que, alm disso, VVV, VVF, VFV, VFF, FVV, FVF, FFV e FFF so os arranjos ternrios com repetio dos dois elementos V e F.

8. NotaoO valor lgico de uma proposio simples p ser indicado por V(P). Assim, exprimimos que p verdadeira (V), escrevendo V(p) = V. Analogamente, exprimimos que p falsa (F), escrevendo V(p) = F. Consideremos por exemplo, as proposies simples: 15Guia de Estudo LGICA MATEMTICA

p: O Sol verde q: Um hexgono tem 9 diagonais r: 2 raiz da equao x 2 + 3.x 4 = 0 Temos: V(p) = F, V(q) = V, V(r) = F

Do mesmo modo, o valor lgico de uma proposio composta P indicado por V(P).

Exerccios de Aprendizagem

1) Determinar o valor lgico (V ou F) de cada uma das seguintes proposies: a) O nmero 17 primo. b) Fortaleza a capital do Maranho. c) TIRADENTES morreu afogado. d) (3 + 5) 2 = 3 2 + 5 2 e) O valor archimediano de f) -1 < -7 g) 0,13131313... uma dzima peridica simples. h) As diagoanis de um paralelogramo so iguais. i) Todo polgono regular convexo inscritvel. j) O hexaedro regular tem 8 arestas. k) A expresso n 2 - n + 41 (n Z) s produz nmeros primos. l) Todo nmero divisvel por 5 termina com 5. m) O produto de dois nmeros mpares um nmero mpar. n) sen 2 30 0 + cos 2 30 0 = 2. o) 1 + 3 + 5 + ... + (2.n 1) 2 = n 2 . 16Guia de Estudo LGICA MATEMTICA

22 . 7

p) As razes da equao x 3 1 = 0 so todas reais. q) O nmero 125 cubo perfeito. r) 0,4 e -4 so as razes da equao x 3 16x = 0. s) O cubo um polgono regular. t) Se a par ento a 2 tambm par. u) Se a 2 par ento a par. v) A constante de Euler e um nmero irracional. w) a 2 + b 2 + a + b par para quaisquer naturais a e b. x) O nmero 234567 divisvel por 3. y) O nmero 13 no primo. z) O inverso aditivo de 2 1 . 2


UNIDADE 02 OPERAES LGICAS SOBRE PROPOSIES

Objetivos da Unidade Apresentar as principais operaes envolvendo as proposies, como por exemplo, negao, conjuno, etc; Resolver diversas aplicaes envolvendo os tpicos discutidos anteriormente.

9. IntroduoQuando pensamos, efetuamos muitas vezes certas operaes sobre proposies, chamadas operaes lgicas. Estas obedecem a regras de um clculo, denominado clculo proposicional; semelhante ao da aritmtica sobre nmeros. Estudaremos a seguir as operaes lgicas fundamentais3.

10.

Negao (~)Chamamos negao de uma proposio p proposio representada por no p, cujo valor lgico a verdade (V) quando p falsa e a falsidade (F) quando p verdadeira.

Assim, no p tem o valor lgico oposto daquele de p. Simbolicamente, a negao de p indicada com a notao ~ p, onde lemos: no p. O valor lgico da negao de uma proposio , portanto, definido pela seguinte tabela-verdade muito simples: p V V Ou seja, pelas igualdades: e ~V = F, ~p F V ~F = V

V(~ p) = ~ V(p)

3

As operaes lgicas fundamentais so: negao, conjuno, disjuno, disjuno exclusiva, condicional e bicondicional.


: a) p: 2 + 3 = 5 b) q: 7 < 3 (V) (F) e e (F) ~ p: 2 + 3 5 ~ q: 7 > 3 e (F) (V)

c) r: Roma a capital da Frana (V)

~ q: Roma no a capital da Frana

Na linguagem comum a negao efetua-se, nos casos mais simples, antepondo o advrbio no ao verbo da proposio dada. Assim, por exemplo, a negao da proposio: p: O Sol uma estrela ~ p: O Sol no uma estrela Outra maneira de efetuar a negao consiste em antepor proposio dada expresses tais como no verdade que, falso que. Desta forma, por exemplo, a negao da proposio: q: Carlos engenheiro ~ q: No verdade que Carlos engenheiro ou ~ q: falso que Carlos engenheiro Devemos notar ainda, que a negao de Todos os homens so elegantes Nem todos os homens so elegantes e a de Nenhum homem elegante Algum homem elegante.

11.

Conjuno ( )Chamamos conjuno de duas proposies p e q a proposio representada por p e q, cujo valor lgico a verdade (V) quando as proposies p e q so ambas verdadeiras e a falsidade (F) nos demais casos.

Simbolicamente, a conjuno de duas proposies p e q indicada pela notao: p q, que se l: p e q. O valor lgico da conjuno de duas proposies , portanto, definido pela seguinte tabela-verdade:


p V V F F

q V F V F

p q V F F F

Ou seja, pelas igualdades: V V = V, V F = F, F V = F, F F = F e V(p q) = V(p) V(q)

: p : A neve branca (V ) a) q : 2 < 5 (V ) p q: A neve branca e 2 < 5 (V) V(p q) = V(p) V(q) = V V = V p : O enxofre verde ( F ) b) q : 7 um nmero primo (V ) p q: O enxofre verde e 7 um nmero primo V(p q) = V(p) V(q) = F V = F p : CANTOR nasceu na Rssia (V ) c) q : FERMAT era mdico ( F ) p q: CANTOR nasceu na Rssia e FERMAT era mdico V(p q) = V(p) V(q) = V F = F p : > 4 (F ) d) q : sen 2 = 0

(F)

(F)

(F )

= 0 (F) 2 V(p q) = V(p) V(q) = F F = F

p q: > 4 e sen


12.

Disjuno ( )Chamamos disjuno de duas proposies p e q a proposio representada por p ou q, cujo valor lgico a verdade (V) quando ao menos uma das proposies p e q verdadeira e a falsidade (F) quando as proposies p e q so ambas falsas.

Simbolicamente, a disjuno de duas proposies p e q indicada pela notao: p q, que se l: p ou q. O valor lgico da disjuno de duas proposies , portanto, definido pela seguinte tabela-verdade: p V V F F q V F V F p q V V V F

Ou seja, pelas igualdades: V V = V, V F = V, F V = V, F F = F e V(p q) = V(p) V(q)

: p : Paris a capital da Frana (V ) a) q : 9 4 = 5 (V ) p q: Paris a capital da Frana ou 9 4 = 5 V(p q) = V(p) V(q) = V V = V (V)

p : CAMES escreveu os Lusadas (V ) b) q : = 3 ( F )p q: CAMES escreveu os Lusadas ou = 3 V(p q) = V(p) V(q) = V F = V (V)

p : Roma a capital da Rssia ( F ) c) q : 5 / 7 uma frao prpria (V )p q: Roma a capital da Rssia e 5/7 uma frao prpria (V) 21Guia de Estudo LGICA MATEMTICA

V(p q) = V(p) V(q) = F V = V p : CARLOS GOMES nasceu na Bahia ( F ) d) q : 1 = 1 ( F )

p q: CARLOS GOMES nasceu na Bahia ou V(p q) = V(p) V(q) = F F = F

1 = 1

(F)

13.

Disjuno Exclusiva ( )

Na linguagem comum a palavra ou tem dois sentidos. Assim, por exemplo, consideremos as duas seguintes proposies compostas: P: Carlos mdico ou professor Q: Mrio alagoano ou gacho Na proposio P se est a indicar que uma pelo menos das proposies Carlos mdico, Carlos professor verdadeira, podendo ser ambas verdadeiras: Carlos mdico e professor. Porm, na proposio Q, se est a precisar que uma e somente uma das proposies Mrio alagoano, Mrio gacho verdadeira, pois, no possvel ocorrer Mrio alagoano e gacho. Na proposio P dizemos que ou inclusivo, enquanto que, na proposio Q, dizemos que ou exclusivo. Em Lgica Matemtica usamos habitualmente o smbolo para ou inclusivo e o smbolo para ou exclusivo. Desta forma, a proposio P a disjuno inclusiva ou apenas disjuno das proposies simples Carlos mdico, Carlos professor, isto : P: Carlos mdico Carlos professor Ao passo que a proposio Q a disjuno exclusiva das proposies simples Mrio alagoano, Mrio gacho, isto : Q: Mrio alagoano Mrio gacho De um modo geral, chamamos de disjuno exclusiva de duas proposies p e q a proposio representada simbolicamente por p q, que se l: ou p ou q ou p ou q, mas no ambos, cujo valor lgico a verdade (V) somente 22Guia de Estudo LGICA MATEMTICA

quando p verdadeira ou q verdadeira, mas no quando p e q so ambas verdadeiras, e a falsidade (F) quando p e q so ambas verdadeiras ou ambas falsas. Sendo assim, o valor lgico da disjuno exclusiva de duas proposies definido pela seguinte tabela-verdade: p V V F F q V F V F p q F V V F

Ou seja, pelas igualdades: V V = F, V F = V, F V = V, F F = V e V(p q) = V(p) V(q) Nota: A lngua latina tem duas palavras diferentes correspondentes aos dois sentidos distintos da palavra ou na linguagem comum. A palavra latina vel exprime a disjuno no seu sentido dbil ou inclusivo, ao passo que a palavra latina aut exprime a disjuno no seu sentido forte ou exclusivo.

14.

Condicional ( )Chamamos proposio condicional ou apenas condicional uma proposio representada por se p ento q, cujo valor lgico a falsidade (F) no caso em que p verdadeira e q falsa e a verdade (V) nos demais casos.

Simbolicamente, a condicional de duas proposies p e q indicada pela notao: p q, que tambm de uma de duas maneiras: (i) p condio suficiente para q (ii) q condio necessria para p Na condicional p q, dizemos que p o antecedente e q o conseqente. O smbolo denominado smbolo de implicao . O valor lgico da condicional de duas proposies , portanto, definido pela seguinte tabela-verdade: p V V F F q V F V F p q V F V V 23Guia de Estudo LGICA MATEMTICA

Ou seja, pelas igualdades: V V = V, V F = F, F V = V, F F = V e V(p q) = V(p) V(q) Portanto, vemos que uma condicional verdadeira todas as vezes que o seu antecedente uma proposio falsa.

:

p : GALOIS morreu em duelo (V ) a) q : um nmero real (V )p q: Se GALOIS morreu em duelo, ento um nmero real V(p q) = V(p) V(q) = V V = V (V)

p : O ms de maio tem 31 dias (V ) b) q : A Terra plana ( F )p q: Se o ms de Maio tem 31 dias, ento a Terra plana V(p q) = V(p) V(q) = V F = V (F)

p : DANTE escreveu os Lusadas ( F ) c) q : CANTOR criou a Teoria dos Conjuntos

(V )

p q: Se DANTE escreveu os Lusadas, ento CANTOR criou a Teoria dos Conjuntos (V) V(p q) = V(p) V(q) = F V = V

p : SANTOS DUMONT nasceu no Cear ( F ) d) q : O ano tem 9 meses ( F )p q: Se SANTOS DUMONT nasceu no Cear, ento o ano tem 9 meses (V) V(p q) = V(p) V(q) = F F = V


Nota: Uma condicional p q no afirma que o conseqente q se deduz ou conseqncia do antecedente p. Assim, por exemplo, as condicionais: 7 um nmero mpar Braslia uma cidade 3 + 5 = 9 SANTOS DUMONT nasceu no Cear no esto a afirmar, de modo nenhum, que o fato de Braslia ser uma cidade se deduz do fato de 7 ser um nmero mpar ou que a proposio SANTOS DUMONT nasceu no Cear conseqncia da proposio 3 + 5 = 9. O que uma condicional afirma unicamente uma relao entre os valores lgicos do antecedente e do conseqente de acordo com a tabela-verdade anterior.

15.

Bicondicional ( )Chamamos proposio bicondicional ou apenas bicondicional uma proposio representada por p se e somente se q, cujo valor lgico a verdade (V) quando p e q so ambas verdadeiras ou ambas falsas, e a falsidade (F) nos demais casos.

Simbolicamente, a bicondicional de duas proposies p e q indicada pela notao: p q, que tambm de uma de duas maneiras: d) p condio necessria e suficiente para q (ii) q condio necessria e suficiente para p O valor lgico da bicondicional de duas proposies portanto, definido pela seguinte tabela-verdade: p V V F F q V F V F p q V F F V

Ou seja, pelas igualdades: V V = V, V F = F, F V = F, F F = V e V(p q) = V(p) V(q) Portanto, vemos que uma bicondicional verdadeira somente quando tambm o so as duas condicionais: p q e q p. 25Guia de Estudo LGICA MATEMTICA

:

p : Roma fica na Europa (V ) a) q : A neve branca (V )p q: Roma fica na Europa se e somente se a neve branca V(p q) = V(p) V(q) = V V = V p : Lisboa a capital de Portugal (V ) b) q : tg 4 = 3 ( F )

(V)

p q: Lisboa a capital de Portugal se e somente se tg V(p q) = V(p) V(q) = V F = F

4

=3

(F)

p : VASCO DA GAMA descobriu o Brasil ( F ) c) q : TIRADENTES foi enforcado (V )p q: VASCO DA GAMA descobriu o Brasil se e somente se TIRADENTES enforcado (F) V(p q) = V(p) V(q) = F V = F p : A Terra plana ( F ) d) q : 2 um nmero racional ( F )

p q: A Terra plana se e somente se V(p q) = V(p) V(q) = F F = V

2 um nmero racional (V)



1) Sejam as proposies p: Est frio e q: Est chovendo. Traduzir para a linguagem corrente as seguintes proposies: a) ~ p b) p q c) p q d) q p e) p ~ q f) p ~ q g) ~ p ~ q h) p ~q i) p ~ q p 2) Sejam as proposies p: Jorge rico e q: Carlos feliz. Traduzir para a linguagem corrente as seguintes proposies: a) q p b) p ~q c) q ~p d) ~p ~q e) ~ ~p f) ~(~p ~q) 3) Sejam as proposies p: Cludio fala ingls e q: Cludio fala alemo. Traduzir para a linguagem corrente as seguintes proposies: a) p q b) p q c) p ~q d) ~ p ~q e) ~ ~p f) ~(~p ~ q) 4) Sejam as proposies p: Joo gacho e q: Jaime paulista. Traduzir para a linguagem corrente as seguintes proposies: a) ~(p ~q) b) ~ ~p c) ~(~p ~q) d) p ~q e) ~p ~q f) ~(~q p)


5) Sejam as proposies p: Marcos alto e q: Marcos elegante. Traduzir para a linguagem corrente as seguintes proposies: a) Marcos alto e elegante b) Marcos alto, mas no elegante c) No verdade que Marcos baixo ou elegante d) Marcos no nem alto e nem elegante e) Marcos alto ou baixo e elegante f) falso que Marcos baixo ou que no elegante 6) Sejam as proposies p: Suely rica e q: Suely feliz. Traduzir para a linguagem simblica as seguintes proposies: a) Suely pobre, mas feliz b) Suely rica ou infeliz c) Suely pobre e infeliz d) Suely pobre ou rica, mas infeliz 7) Sejam as proposies p: Carlos fala francs, q: Carlos fala ingls e r: Carlos fala alemo. Traduzir para a linguagem simblica as seguintes proposies: a) Carlos fala francs ou ingls, mas no fala alemo b) Carlos fala francs e ingls, ou no fala francs e alemo c) falso que Carlos fala francs mas que no fala alemo d) falso que Carlos fala ingls ou alemo mas que no fala francs 8) Traduzir para a linguagem simblica as seguintes proposies matemticas: a) x = 0 ou x > 0 b) x 0 e y 0 c) x > 1 ou x + y = 0 d) x 2 = x.x e x 0 = 1 9) Traduzir a linguagem simblica as seguintes proposies matemticas: a) (x + y = 0 e z > 0) ou z = 0 b) x = 0 e (y + z > x ou z = 0) c) x 0 ou (x = 0 e y < 0) d) (x = y e z = t) ou (x < y e z = 0) 10) Traduzir a linguagem simblica as seguintes proposies matemticas: a) Se x > 0 ento y = 2 b) Se x + y = 2 ento z > 0 c) Se x = 1 ou z = 2 ento y > 1 d) Se z > 5 ento x 1 e x 2 e) Se x y ento x + z > 5 e y + z < 5


f) Se x + y > z e z = 1 ento x + y > 1 g) Se x < 2 ento x = 1 ou x = 0 h) y = 4 e se x < y ento x < 5 11) Determinar o valor lgico (V ou F) de cada uma das seguintes proposies: a) x maior que 5 e menor que 7 ou x no igual a 6 b) Se x menor que 5 e maior que 3, ento x igual a 4 c) x maior que 1 ou x menor que 1 e maior que 0 12) Determinar o valor lgico (V ou F) de cada uma das seguintes proposies: a) 3 + 2 = 7 e 5 + 5 = 10 b) 2 + 7 = 9 e 4 + 8 = 12 c) sen = 0 e cos = 0 d) 1 > 0 2 + 2 = 4 e) 0 > 1 3 irracional f) ( 1 ) 2 = -1 racional g) 2 < 1 5 racional 13) Determinar o valor lgico (V ou F) de cada uma das seguintes proposies: a) Roma a capital da Frana e tg45 0 = 1 b) FLEMING descobriu a penicilina ou sen30 0 = 1/5 c) 5 < 0 ou Londres a capital da Itlia d) 2 > 5 ou Recife a capital do Cear e) 3 > 1 no um nmero real f) 2 = 2 sen90 0 tg45 0 g) 5 2 = 10 racional h) 3 3 5 5 i) 4 = 2. 1 13 um nmero primo j) -5 < -7 2 = -2 k) 5 < 0 tg

4

1 ento -1 < -2 d) Se 1 = 0 ento sen30 0 = e) tg60 0 = 3 2 = 2 f) 3 > 2 20 = 2 g) 1 = -1 25 = 5 h) > 4 3 > 5


15) Determinar o valor lgico (V ou F) de cada uma das seguintes proposies: a) 3 + 4 = 7 se e somente se 5 3 = 125 b) 0 2 = 1 se e somente se (1 + 5) 0 = 3 c) 2 . 8 = 4 se e somente se 2 = 0 d) tg = 1 se e somente se sen = 0 e) -1 > -2 2 < 20 f) -2 > 0 2 < 0 g) 3 2 + 4 2 = 5 2 irracional 1 2 = -2 h) 1 > sen

cos


UNIDADE 03 CONSTRUO DE TABELAS-VERDADE

Objetivos da Unidade

Apresentar um procedimento para a construo de tabelas-verdade; Resolver diversas aplicaes envolvendo os tpicos discutidos anteriormente.

16.

Tabela-verdade de uma Proposio Composta

Dadas vrias proposies simples p, q, r, s,..., podemos combin-las pelos conectivos lgicos: ~, , , , E construir proposies compostas, tais como: P(p, q) = ~ p (p q) Q(p, q) = (p ~q) q R(p, q, r) = (p ~q r) ~(q (p ~ r)) Ento, com o emprego das tabelas-verdade das operaes lgicas fundamentais: ~ p, p q, p q, p q, p q possvel construir uma tabela-verdade correspondente a qualquer proposio composta dada, tabela-verdade esta que mostrar exatamente os casos em que a proposio composta ser verdadeira (V) ou falsa (F), admitindo-se, como sabido, que o seu valor lgico s depende dos valores lgicos das proposies simples componentes.

17.

Nmero de Linhas de uma Tabela-verdade

O nmero de linhas da tabela-verdade de uma proposio composta depende do nmero de proposies simples que a integram, sendo dado pelo seguinte Teorema: Teorema 01: A tabela-verdade de uma proposio composta com n proposies simples componentes contm 2 n linhas.


Prova: Com efeito, toda proposio simples tem dois valores lgicos: V e F, que se excluem. Portanto, para uma proposio composta P(p 1 , p 2 , p 3 ,..., p n ) com n proposies simples componentes p 1 , p 2 , p 3 ,..., p n h tantas possibilidades de atribuio dos valores lgicos V e F a tais componentes quantos so os arranjos com repetio n a n dos dois elementos de V e F, isto , A 2, n = 2 n , segundo ensina a Anlise Combinatria.

18.

Construo da Tabela-verdade de uma Proposio Composta

Para a construo prtica da tabela-verdade de uma proposio composta comea-se por contar o nmero de proposies simples que a integram. Se h n proposies simples componentes: p 1 , p 2 , p 3 ,..., p n , ento a tabelaverdade contm 2 n linhas. Para isto, 1 a proposio simples p 1 atribuem-se 2 n1 valores V seguidos de 2 n1 valores F; 2 a proposio simples p 2

2n = 2 atribuem-se

2n = 2 n 2 valores V, seguidos de 2 n 2 valores F, seguidos de 2 n 2 valores V, 4 seguidos, finalmente, de 2 n 2 valores F; e assim por diante. Genericamente, a k2n sima proposio simples p k (k n) atribuem-se alternadamente k = 2 n k valores 2 V seguidos de igual nmero de valores F.No caso, por exemplo, de uma proposio composta com cinco (5) proposies simples componentes, a tabela-verdade contm 2 5 linhas, e os grupos de valores V e F se alternam de 16 em 16 para a 1 a proposio simples p 1 , de 8 em 8 para a 2 a proposio simples p 2 , de 4 em 4 para a 3 a proposio simples p 3 , de 2 em 2 para a 4 a proposio simples p 4 , e, enfim de 1 em 1 para a 5 a proposio simples p 5 .

19.

Exemplificao01: Construir a tabela-verdade da proposio: P(p, q) = ~(p ~q)

1 a Resoluo: Formamos em primeiro lugar, o par de colunas correspondentes s duas proposies simples componentes p e q. Em seguida, formamos a coluna para ~q. Depois, formamos a coluna para (p ~q). E, por fim, formamos a coluna relativa aos valores lgicos da proposio composta dada.


p V V F F

q V F V F

~q F V F V

p ~q F V F F

~(p ~q) V F V V

2 a Resoluo: Formamos em primeiro lugar as colunas correspondentes s duas proposies simples p e q. Em seguida, direita, traamos uma coluna para cada uma dessas proposies e para cada um dos conectivos que figuram na proposio composta dada. p V V F F q V F V F ~ (p

~

q)

Depois, numa certa ordem, completamos essas colunas, escrevendo em cada uma delas os valores lgicos convenientes, no modo abaixo indicado: p V V F F q V F V F ~ V F V V 4 (p V V F F 1 F V F F

~ F V F V 2

q) F F V F 1

3

Os valores lgicos da proposio composta dada encontram-se na coluna completada em ltimo lugar (Coluna 4). Portanto, os valores lgicos da proposio composta dada correspondentes a todas as possveis atribuies dos valores lgicos V e F s proposies simples componentes p e q (VV, VF, FV e FF) so V, F, V e V, isto , simbolicamente: P(VV) = V, P(VF) = F, P(FV) = V, P(FF) = V Ou seja, abreviadamente: P(VV, VF, FV, FF) = VFVV

Note que a proposio P(p, q) associa a cada um dos elementos do conjunto U = {VV, VF, FV, FF} um nico elemento do conjunto {V, F}, isto , P(p, q) outra coisa no que uma funo de U em {V, F}: P(p, q): U {V, F} 33Guia de Estudo LGICA MATEMTICA

Cuja representao grfica por um diagrama sagital a seguinte:

Figura 04: A funo de U em {V, F}.

3 a Resoluo: Resulta de suprimir na tabela-verdade anterior as duas primeiras colunas da esquerda relativas s proposies simples componentes p e q, o que d a seguinte tabela-verdade simplificada para a proposio composta dada: ~ V F V V 4 (p V V F F 1 F V F F

~ F V F V 2

q) F F V F 1

3

02: Construir a tabela-verdade da proposio: P(p, q) = ~(p q) ~(q p) 1 a Resoluo: p V V F F q V F V F pq V F F F qp V F F V ~(p q) F V V V ~(q p) F V V F ~(p q) ~(q p) F V V V

2 a Resoluo: p V V F F q V F V F ~ F V V V 3 (p V V F F 1 V F F F

q) V F V F 1

F V V V

~ F V V F 3

(q V F V F 1

V F F V 2

p) V V F F 1

2

4


Portanto, simbolicamente: P(VV) = F, P(VF) = V, P(FV) = V, P(FF) = V Ou seja, abreviadamente: P(VV, VF, FV, FF) = FVVV

Observe que P(p, q) outra coisa no que uma funo de U = {VV, VF, FV, FF} em {V, F}, cuja representao grfica por um diagrama sagital a seguinte:


3 a Resoluo: ~ F V V V 3 (p V V F F 1 V F F F

q) V F V F 1

F V V V

~ F V V F 3

(q V F V F 1

V F F V 2

p) V V F F 1

2

4

03: Construir a tabela-verdade da proposio: P(p, q, r) = p ~ r q ~ r 1 a Resoluo: p V V V V F F F F q V V F F V V F F r V F V F V F V F ~r F V F V F V F V p~ r V V V V F V F V q ~ r F V F F F V F F p~ r q ~ r F V F F V V V F


2 a Resoluo: p V V V V F F F F q V V F F V V F F r V F V F V F V F p V V V V F F F F 1 Portanto, simbolicamente: P(VVV) = F, P(VVF) = V, P(VFV) = F, P(VFF) = F P(FVV) = V, P(FVF) = V, P(FFV) = V, P(FFF) = F Ou seja, abreviadamente: P(VVV, VVF, VFV, VFF, FVV, FVF, FFV, FFF) = FVFFVVVF Observe que a proposio P(p, q, r) outra coisa no que uma funo de U = {VVV, VVF, VFV, VFF, FVV, FVF, FFV, FFF} em {V, F}, cuja representao grfica por um diagrama sagital a seguinte: V V V V F V F V

~ F V F V F V F V 2

r V F V F V F V F 1

F V F F V V V F 4

q V V F F V V F F 1

F V F F F V F F

~ F V F V F V F V 2

r V F V F V F V F 1

3

3



3 a Resoluo: p V V V V F F F F 1 V V V V F V F V

~ F V F V F V F V 2

r V F V F V F V F 1

F V F F V V V F 4

q V V F F V V F F 1

F V F F F V F F

~ F V F V F V F V 2

r V F V F V F V F 1

3

3

04: Construir a tabela-verdade da proposio: P(p, q, r) = (p q) (q r) (p r) Resoluo: p V V V V F F F F q V V F F V V F F r V F V F V F V F (p V V V V F F F F 1

V V F F V V V V 2

q) V V F F V V F F 1

V F F F V F V V

(q V V F F V V F F 1

V F V V V F V V 2

r) V F V F V F V F 1

V V V V V V V V 4

(p V V V V F F F F 1

V F V F V V V V 2


3

Portanto, simbolicamente: P(VVV) = V, P(VVF) = V, P(VFV) = V, P(VFF) = V P(FVV) = V, P(FVF) = V, P(FFV) = V, P(FFF) = V Ou seja, abreviadamente: P(VVV, VVF, VFV, VFF, FVV, FVF, FFV, FFF) = VVVVVVVV Observe que a ltima coluna (Coluna 4) da tabela-verdade da proposio P(p, q, r) s encerra a letra V(verdade), isto , o valor lgico desta proposio sempre V quaisquer que sejam os valores lgicos das proposies componentes p, q e r.


05: Construir a tabela-verdade da proposio: P(p, q, r) = (p (~ q r)) ~ (q (p ~ r)) Resoluo: (p V V V V F F F F

V F V V V V V V 4

(~ F F V V F F V V 2

q V V F F V V F F 1

V F V V V F V V

r)) V F V F V F V F 1

F F V F F F F V

~ F F V F F F F V 5


V V F V V V V F


F V F V V F V F 3

~ F V F V F V F V 2


3

6

4

Portanto, simbolicamente: P(VVV) = F, P(VVF) = F, P(VFV) = V, P(VFF) = F P(FVV) = F, P(FVF) = F, P(FFV) = F, P(FFF) = V Ou seja, abreviadamente: P(VVV, VVF, VFV, VFF, FVV, FVF, FFV, FFF) = FFVFFFFV

20.

Valor Lgico de uma Proposio Composta

Dada uma proposio composta P(p, q, r,...), podemos sempre determinar o seu valor lgico (V ou F) quando so dados ou conhecidos os valores lgicos respectivos das proposies componentes p, q, r,....

: a) Sabendo que os valores lgicos das proposies p e q so respectivamente V e F, determinar o valor lgico (V ou F) da proposio: P(p, q) = ~(p q) ~ p ~ q Soluo: Temos, sucessivamente: V(P) = ~(V F) ~ V ~ F = ~V F V = F F = V


b) Sejam as proposies p: = 3 e q: sen F) da proposio: e

2

= 0. Determinar o valor lgico (V ou

P(p, q) = (p q) (p p q) Soluo: As proposies componentes p e q so ambas falsas, isto , V(p) = F V(q) = F. Portanto: V(P) = (F F) (F F F) = V (F F) = V V = V c) Sabendo que V(p) = V, V(q) = F e V = F, determinar o valor lgico (V ou F) da proposio: P(p, q, r) = (q (r ~ p)) ((~ q p) r) Soluo: Temos, sucessivamente: V(P) = (F (F ~ V)) ((~ F V) F) V(P) = (F (F F)) ((V V) F) V(P) = (F V) (V F) V(P) = F F V(P) = F d) Sabendo que V(r) = V, determinar o valor lgico (V ou F) da proposio: p~ q r

Soluo: Como r verdadeira (V), a disjuno ~ q r verdadeira (V). Logo, a condicional dada verdadeira (V), pois, o seu conseqente verdadeiro (V). e) Sabendo que V(q) = V, determinar o valor lgico (V ou F) da proposio: (p q) (~ q ~ p) q Soluo: Como q verdadeira (V), ento ~q falsa (F). Logo, a condicional ~

~ p verdadeira (V), pois, o seu antecedente falso (F). Por conseqncia, a condicional dada verdadeira (V), pois, o seu conseqente verdadeiro (V).f) Sabendo que as proposies x = 0 e x = y so verdadeiras e que a proposio y = z falsa, determinar o valor lgico (V ou F) da proposio: x 0 x yy z Soluo: Temos sucessivamente: ~V ~V ~ F = F F V = F V = V


21.

Uso de Parnteses

bvia a necessidade de usarmos parntesis na simbolizao das proposies, que devem ser colocados para evitar qualquer tipo de ambigidade. Desta maneira, por exemplo, a expresso p q r d lugar, colocando parntesis, s duas seguintes proposies: (i) (p q) r e (ii) p (q r) que logicamente no tem o mesmo significado, pois, na (i), o conectivo principal , e na (ii), o conectivo principal , isto , a (i) uma disjuno e a (ii) uma conjuno. Similarmente, a expresso p q r s d lugar, colocando parntesis, s seguintes proposies: (p q) r) s, p ((q r) s), (p (q r) s), p (q (r s)), (p q) (r s) tais que, duas quaisquer delas, no tm o mesmo significado. De uma outra forma, em muitos casos, parntesis podem ser suprimidos, a fim de simplificar as proposies simbolizadas, desde que, de modo natural, ambigidade alguma venha aparecer. A supresso de parntesis nas proposies simbolizadas se faz mediante algumas convenes, das quais so particularmente importantes as duas seguintes: (I) A ordem de precedncia para os conectivos : (1) ~; (2) e ; (3) ; (4)

Portanto, o conectivo mais fraco ~ e o conectivo mais forte . Assim, por exemplo, a proposio: pqs r uma bicondicional e nunca uma condicional ou uma conjuno. Para convert-la numa condicional h que usar parntesis: p (q s r) e, analogamente, para convert-la numa conjuno: (p q s) r O conseqente da condicional uma bicondicional. Se desejarmos converter este conseqente numa conjuno devemos escrever: p ((q s) r)


Tambm so bicondicionais as trs seguintes proposies: p q s r; p q~ rs p q s r; (II) Quando um mesmo conectivo aparece sucessivamente repetido, suprimem-se os parntesis, fazendo-se a associao a partir da esquerda.

Segundo estas duas convenes, as quatro seguintes proposies: ((p (~q)) (r (~p))) ((~(~(p q))) (~p)); (((p (~q)) r) (~p)); ((~p) (q (~(p r)))) escrevem-se mais simplesmente da seguinte forma: ~~(p q) ~p; (p ~q) (r (~p) (p ~q) r ~p; ~p) (q ~(p r)

22.

Outros Smbolos para os Conectivos

Na literatura sobre Lgica Matemtica, usam-se diferentes smbolos para os conectivos. Assim, por exemplo, so frequentemente bvia a necessidade usados os smbolos: para a negao (~) e & para a conjuno ( ) (ferradura) para a condicional ( )


Exerccios de Aprendizagem 1) a) b) c) d) e) f) g) h) 2) a) b) c) d) 3) a) b) c) d) e) f) g) Construir as tabelas-verdade das seguintes proposies: ~(p ~ q) ~(p ~ q) p qp q ~p (q p) (p q) p q q~ qp (p ~q) q p (p ~ q) ~ p q Construir as tabelas-verdade das seguintes proposies: ~ p rq ~ r prq ~ r p (p ~ r) q r (p q r) (~ p q ~ r) Determinar P(VV, VF, FV, FF) em cada um dos seguintes casos: P(p, q) = ~ (~ p q) P(p, q) = ~ p q p P(p, q) = (p q) ~ (p q) P(p, q) = (p ~ q) (~ p q) P(p, q) = ~ ((p q) (~ p ~ q)) P(p, q) = ~ q p q ~ p P(p, q) = (p q) ~ p (q p)

4) Determinar P(VVV, VVF, VFV, VFF, FVV, FVF, FFV, FFF) em cada um dos seguintes casos: a) P(p, q, r) = p (q r) b) P(p, q, r) = (p ~ q) r c) P(p, q, r) = ~ p (q ~ r) d) P(p, q, r) = (p q) (p r) e) P(p, q, r) = (p ~ r) (q ~ r) f) P(p, q, r) = ~ (p ~ q) (~ p r) 5) a) b) c) d) e) f) Determinar P(VFV) em cada um dos seguintes casos: P(p, q, r) = p ~ r ~ q P(p, q, r) = ~ p (q ~ r) P(p, q, r) = ~ (p q) ~ (p ~ r) P(p, q, r) = (r (p ~ q)) ~ (~ r (p q)) P(p, q, r) = (p q r) q ~ r P(p, q, r) = (p (q r)) (~ p r ~ q)


6) Sabendo que os valores lgicos das proposies p e q so respectivamente F e V, determinar o valor lgico (V ou F) da proposio: (p (~ q p)) ~ ((p ~ q) q ~ p) 7) Sejam as proposies p: tg( x) = cotgx e q: < 2. Determinar o valor lgico (V ou F) de cada uma das seguintes proposies: a) (~ p q) (p ~ q) b) p q ~ p ~ q c) ~ (p q) ~ p ~ q d) (p (~ p q)) (~ p ~ q) 8) Sabendo que os valores lgicos das proposies p, q e r so respectivamente V, F e F, determinar o valor lgico (V ou F) de cada uma das seguintes proposies: a) (p p q) (p r) b) (p ~ q) ((p r) q) c) (p q r) (p (q r)) 9) Sabendo que as proposies p e q so verdadeiras e que as proposies r e s so falsas, determinar o valor lgico (V ou F) de cada uma das seguintes proposies: a) p q r b) r s q c) q p s d) p ~(r s) e) (q s) r f) ~ r p q g) (q r) (p s) h) (r s) (p q) i) (p ~ q) r j) ~ ((r p) (s q)) k) (s r) (p q) l) r q (~ p r) 10) Sabendo que os valores lgicos das proposies p, q, r e s so respectivamente V, V, F e F, determinar o valor lgico (V ou F) de cada uma das seguintes proposies: a) p q q p b) (r p) (p r) c) (p r) (~ p ~ r) d) ~(p q) ~ p ~ q e) ~(p s) ~ p ~ s f) ~((p s) (s r) 43Guia de Estudo LGICA MATEMTICA

UNIDADE 04 TAUTOLOGIAS, CONTRADIES E CONTINGNCIAS.Objetivos da Unidade Apresentar as definies referentes a Tautologias, Contradies e Contingncias; Estar plenamente familiarizado com as Tautologias, Contradies e Contingncias; Resolver diversas aplicaes envolvendo os tpicos discutidos anteriormente.

23.

TautologiaChamamos de tautologia toda a proposio composta cuja ltima coluna da sua tabela-verdade encerra somente a letra V (verdade).

Em outros termos, tautologia toda proposio composta P(p, q, r,...) cujo valor lgico sempre V (verdade), quaisquer que sejam os valores lgicos das proposies simples componentes p, q, r,.... As tautologias so tambm denominadas proposies tautolgicas ou proposies logicamente verdadeiras. imediato que as proposies p p e p p so tautolgicas (Princpio de Identidade para as proposies).

: a) A proposio ~ (p ~ p) (Princpio da No Contradio) tautolgica, conforme podemos verificar pela sua tabela-verdade abaixo: p V F e ~p F V p~ p F F ~ (p ~ p) V V

Portanto, dizer que uma proposio no pode ser simultaneamente verdadeira falsa sempre verdadeiro.


b) A proposio p ~ p (Princpio do Terceiro Excludo) tautolgica, como podemos verificar pela sua tabela-verdade abaixo: p V F ~p F V p~ p V V

Portanto, dizer que uma proposio ou verdadeira ou falsa sempre verdadeiro. c) A proposio p ~ (p q) tautolgica, conforme podemos ver na sua tabela-verdade abaixo: p V V F F q V F V F pq V F F F ~ (p q) F V V V p~ (p q) V V V V

d) A proposio p q (p q) tautolgica, conforme mostra a sua tabelaverdade abaixo: p V V F F q V F V F pq V F F F pq V F F V p q (p q) V V V V

e) A proposio p (q ~q) p tautolgica, conforme podemos visualizar pela sua tabela-verdade abaixo: p V V F F q V F V F ~q F V F V q ~q F F F F p (q ~q) V V F F p (q ~q) p V V V V


f) A proposio p r ~q r tautolgica, conforme podemos verificar pela sua tabela-verdade abaixo: p V V V V F F F F q V V F F V V F F r V F V F V F V F ~q F F V V F F V V p r V F V F F F F F ~q r V F V V V F V V p r ~q r V V V V V V V V

g) A proposio ((p q) r) (p (q r)) tautolgica, conforme podemos visualizar pela sua tabela-verdade abaixo: ((p V V V V F F F F 1

V V F F V V V V 2

q) V V F F V V F F 1

V F V V V F V F 3


V V V V V V V V 4


V F V V V V V V 3


V F V V V F V V 2


24.

Princpio de Substituio para as Tautologias

Consideremos P(p, q, r,...) uma tautologia e sejam P 0 (p, q, r,...), Q 0 (p, q, r,...), R 0 (p, q, r,...), ... proposies quaisquer. Como o valor lgico de P(p, q, r,...) sempre V (verdade), quaisquer que sejam os valores lgicos das proposies simples componentes p, q, r,..., bvio que, substituindo p por P 0 , q por Q 0 , r por R 0 ,... na tautologia P(p, q, r,...), a nova proposio P(P 0 , Q 0 , R 0 ,...) que assim obtemos tambm uma tautologia. Desta forma, podemos enunciar o seguinte princpio abaixo, denominado de Princpio de Substituio:


Princpio de Substituio para Tautologias Se P(p, q, r,...) uma tautologia, ento P(P 0 , Q 0 , R 0 ,...) tambm uma tautologia, quaisquer que sejam as proposies P 0 , Q 0 , R 0 ,....

25.

ContradioChamamos contradio toda proposio composta cuja ltima coluna da sua tabela-verdade encerra somente a letra F (falsidade).

Em outras palavras, contradio toda proposio composta P(p, q, r,...) cujo valor lgico sempre F (falsidade), quaisquer que sejam os valores lgicos das proposies simples componentes p, q, r,.... Como uma tautologia sempre verdadeira, a negao de uma tautologia uma contradio, e P(p, q, r,...) uma contradio se e somente se ~P(p, q, r,...) uma tautologia. As contradies so tambm denominadas proposies contravlidas ou proposies logicamente falsas. Para as contradies vale um Princpio de Substituio semelhante ao que enunciamos para o caso das tautologias. Princpio de Substituio para Contradies Se P(p, q, r,...) uma contradio, ento P(P 0 , Q 0 , R 0 ,...) tambm uma contradio, quaisquer que sejam as proposies P 0 , Q 0 , R 0 ,....

: a) A proposio p ~ p uma contradio, conforme podemos visualizar pela sua tabela-verdade abaixo: p V F ~p F V p~ p F F

Portanto, dizer que uma proposio pode ser simultaneamente verdadeira e falsa sempre falso. 47Guia de Estudo LGICA MATEMTICA

b) A proposio p ~ p uma contradio, como podemos verificar pela sua tabela-verdade abaixo: p V F ~p F V p~ p F F

c) A proposio (p q) ~(p q) uma contradio, conforme podemos ver na sua tabela-verdade abaixo: p V V F F q V F V F pq V F F F pq V V V F ~ (p q) F F F V (p q) ~(p q) F F F F

d) A proposio ~p (p ~ q) uma contradio, como podemos verificar pela sua tabela-verdade abaixo: p V V F F q V F V F ~p F F V V ~q F V F V p~ q F V F F ~p (p ~ q) F F F F

26.

ContingnciasChamamos contingncia toda proposio composta em cuja ltima coluna da sua tabela-verdade figuram as letras V e F cada uma pelo menos uma vez.

Em outras palavras, contingncia toda proposio composta que no tautologia nem contradio. As contingncias so tambm denominadas proposies contingentes ou proposies indeterminadas.


: a) A proposio p ~ p uma contingncia, conforme podemos visualizar pela sua tabela-verdade abaixo: p V F ~p F V p~ p F V

b) A proposio p q p uma contingncia, como podemos verificar pela sua tabela-verdade abaixo: p V V F F q V F V F p q V V V F p qp V V F V

c) A proposio x = 3 (x y x 3) uma contingncia, conforme podemos ver na sua tabela-verdade abaixo: x=3 V V F F x=y V F V F x 3 F F V V x y F V F V x yx 3 V F V V x = 3 (x y x 3) V F F F



11) Mostrar que as seguintes proposies so tautolgicas: i) (p p) (p ~ p) j) (p p ~p) ~p k) (p q) p q l) p (q ~p) m) (p q) ~q ~p n) (p q) ~p ~q o) p p (p q) p) ~(p ~p) (q ~q) q) ~(p ~p) (q ~q) r) p (p q) p s) ~(p q) (p q) t) (p q) p q 12) Mostrar que as seguintes proposies so tautolgicas: e) (p q) (p r q) f) (p q) (p q r) g) (p q) (p r q r) h) (p q) (p q q r) 13) Mostre que as seguintes proposies so contingentes: h) p q p q i) (q p) (p q) j) (p (p q)) q k) p (p q ~ q 14) Determinar quais das seguintes proposies so tautolgicas, contravlidas, ou contingentes: g) p (~p q) h) ~p q (p q) i) p (q (q p)) j) ((p q) q) p k) p ~q (p ~q) l) ~p ~q (p q) m) p (p q) r n) p q (p q r)


UNIDADE 05 IMPLICAO LGICA

Objetivos da Unidade

Definir o significado da Implicao Lgica envolvendo proposies; Verificar as propriedades da Implicao Lgica; Verificar a relao entre Tautologias e Implicao Lgica; Resolver diversas aplicaes envolvendo os tpicos discutidos anteriormente.

27.

Definio de Implicao LgicaDizemos que uma proposio P(p, q, r,...) implica logicamente ou apenas implica uma proposio Q(p, q, r,...) se Q(p, q, r,...) verdadeira (V) todas as vezes que P(p, q, r,...) verdadeira (V).

Em outros termos, uma proposio P(p, q, r,...) implica logicamente ou apenas implica uma proposio Q(p, q, r,...) todas as vezes que nas respectivas tabelas-verdade dessas duas proposies no aparece V na ltima coluna de P(p, q, r,...) e F na ltima coluna de Q(p, q, r,...), com V e F em uma mesma linha, isto , no ocorre P(p, q, r,...) e Q(p, q, r,...) com valores lgicos simultneos respectivamente V e F. Vamos indicar que a proposio P(p, q, r,...) implica a proposio Q(p, q, r,...) com a notao: P(p, q, r,...) Q(p, q, r,...) Em particular, toda proposio implica uma tautologia e somente uma contradio implica uma contradio.

28.

Propriedades da Implicao Lgica

imediato que a relao de implicao lgica entre proposies goza das propriedades reflexiva (R) e transitiva (T), isto , em smbolos temos: (R) P(p, q, r,...) P(p, q, r,...)

(T) Se P(p, q, r,...) Q(p, q, r,...) e Q(p, q, r,...) R(p, q, r,...), ento P(p, q, r,...) R(p, q, r,...)


1. Exemplificao a) As tabelas-verdade das proposies: p q, p q, p V V F F q V F V F pq V F F F pq pq V F F V

pq V V V F

A proposio p q verdadeira (V) somente na linha 1 e, nesta linha, as proposies p q e p q tambm so verdadeiras (V). Logo, a primeira proposio implica cada uma das outras duas proposies, isto : pq p q e pq pq As mesmas tabelas-verdade tambm demonstram as importantes Regras de Inferncia: (i) p p q e q p q (Adio) (ii) p q p e p q q (Simplificao) b) As tabelas-verdade das proposies: p q, p q, so: p V V F F q V F V F pq V F F V

qp qp V V F V

pq V F V V

A proposio p q verdadeira (V) nas linhas 1 e 4 e, nestas linhas, as proposies q p e q p tambm so verdadeiras. Logo, a primeira proposio implica cada uma das outras duas proposies, isto : pq pq e pq qp c) A tabela-verdade da proposio: (p q) ~p dada por: p V V F F q V F V F pq V V V F ~p F F V V (p q) ~p F F V F


Esta proposio verdadeira (V) somente na linha 3 e, nesta linha, a proposio q tambm verdadeira (V). Logo, temos a seguinte implicao lgica: p q) ~p q denominada Regra do Silogismo Disjuntivo. Outra forma desta importante Regra de Inferncia : (p q) ~q p d) A tabela-verdade da proposio (p q) p : p V V F F q V F V F pq V F V V (p q) p V F F F

Esta proposio verdadeira (V) somente na linha 1 e, nesta linha, a proposio q tambm verdadeira (V). Logo, temos a seguinte implicao lgica: (p q) p q denominada Regra Modus Ponens. e) As tabelas-verdade das proposies (p q) ~q e ~ p so: p V V F F q V F V F pq V F V V ~q F V F V (p q) ~q F F F V ~p F F V V

A proposio (p q) ~q verdadeira (V) somente na linha 4, e nesta linha, a proposio ~ p tambm verdadeira (V). Logo, temos a seguinte implicao lgica: (p q) ~ q ~ p denominada Regra Modus Tollens. As mesmas tabelas-verdade tambm mostram que ~ p implica p q, isto : ~ p p q.

29.

Tautologias e Implicao Lgica

Teorema 01: A proposio P(p, q, r,...) implica a proposio Q(p, q, r,...), isto , P(p, q, r,...) Q(p, q, r,...) se e somente se a condicional: (1) P(p, q, r,...) P(p, q, r,...) tautolgica.


Demonstrao: ( ) Suponhamos que a proposio P(p, q, r,...) implica a proposio Q(p, q, r,...), isto , P(p, q, r,...) Q(p, q, r,...), da neste sentido devemos mostrar que a condicional P(p, q, r,...) P(p, q, r,...) tautolgica. Ento, no ocorre que os valores lgicos simultneos destas duas proposies sejam respectivamente V e F, e por conseguinte a ltima coluna da tabela-verdade da condicional (1) encerra somente a letra V, isto , esta condicional tautolgica. ( ) Agora, temos por hiptese que a condicional P(p, q, r,...) P(p, q, r,...) tautolgica e devemos mostrar que a proposio P(p, q, r,...) implica a proposio Q(p, q, r,...). Como (1) tautolgica, isto , a ltima coluna da sua tabela-verdade encerra somente a letra (V), ento no ocorre que os valores lgicos simultneos das proposies P(p, q, r,...) e Q(p, q, r,...) sejam respectivamente V e F, e por conseguinte a primeira proposio implica a segunda. c.q.d. Desta maneira, percebemos que a toda implicao lgica corresponde uma condicional tautolgica, e vice-versa. Corolrio 01: Se P(p, q, r,...) Q(p, q, r,...), ento, temos: P(P 0 ,Q 0 , R 0 ,...) Q(P 0 ,Q 0 , R 0 ,...) quaisquer que sejam as proposies P 0 ,Q 0 , R 0 ,.... Nota: Os smbolos e so distintos, pois, o primeiro de operao lgica (aplicado, por exemplo, s proposies p e q d a nova proposio p q), enquanto que o segundo de relao (estabelece que a condicional P(p, q, r,...) Q(p, q, r,...) tautolgica.

:

a) A condicional (p q) (q r) (p r) tautolgica, pois, a ltima coluna da sua tabela-verdade encerra somente a letra (V), como j vimos anteriormente. Desta forma, existe a implicao lgica: (p q) (q r) (p r) p r denominada Regra do Silogismo Hipottico.


b) A condicional p ~ p q tautolgica, pois, a ltima coluna da sua tabelaverdade encerra somente a letra (V), como podemos verificar abaixo: p V V F F q V F V F ~p F F V V p ~p F F F F p ~ pq V V V V

Sendo assim, existe a implicao lgica: p ~ p q. Assim, de uma contradio p ~ p se deduz qualquer proposio (Princpio da Inconsistncia). c) A proposio (p q) p implica a proposio q, pois, a condicional p ~ p q tautolgica, pois, a ltima (p q) p q tautolgica conforme podemos verificar pela sua tabela-verdade abaixo: p V V F F q V F V F pq V F F V (p q) p V F F F (p q) p q V V V V

Portanto, simbologicamente podemos escrever: (p q) p q. Exerccios de Aprendizagem

1) Mostrar que a proposio p implica a proposio q (p q) em cada um dos seguintes casos: a) p: > 3; q: tg45 0 = 1 b) p: sen30 0 =1; q: 2 > 3 c) p: ABCD um losango; q: ABCD um paralelogramo 2) Mostrar: a) q p q b) q p q p 3) Mostrar que p no implica p q e que p q no implica p. 4) Mostrar: (x 0 x = y) x y x = 0.


REFERNCIAS

ALENCAR FILHO, Edgard de. Iniciao Lgica Matemtica. So Paulo: Nobel, 2002. BOUCH, J. Simbolismo Lgico. Eudeba, 1965. ERSHOV, Yu.; PALIUTIN, E. Lgica Matemtica. Moscou: Mir, 1990. GARRIDO, M. Lgica Simblica. Tecnos, 1973. SILVA, Corra Soares da.; FINGER, Marcelo.; MELO, Ana Cristina V. de. Lgica para Computao. So Paulo: Thomson Learning, 2006.


Documents

L%f3gica Matem%e1tica - 1 Parte