1 Lgica Proposicional1.1 Introduo

A Lgica fundamenta os raciocnios (inferncias) e as aes. Um dos objetivos da Lgica estabelecer uma linguagem formal, onde se pode expressar com clareza, preciso e emitir juzo de verdadeiro ou falso para determinadas frases. A Lgica de fundamental importncia para o entendimento das linguagens lgicas (PROLOG, etc). Constitui-se, tambm, como pr-requisito para a disciplina de Inteligncia Artificial. 1.2 Proposies

Frase o elemento de comunicao que relaciona palavras entre si de modo a estabelecer uma mensagem com sentido completo. Existem vrios tipos de frases: Declarativas Exemplos: a) Uberaba fica em Minas Gerais. b) Maria mdica. c) 3+5=8 Interrogativas Exemplos: a) Onde Pedro mora? b) Ser que Joana estuda Engenharia? Exclamativas Exemplos: a) Parabns! b) Feliz Natal! c) Que mulher bonita!... Imperativas Exemplos: a) Feche a porta. b) V embora.

Proposio uma frase declarativa (com sujeito e predicado), qual pode ser atribudo, sem ambigidade, um dos valores lgicos: Verdadeiro ou Falso. Alguns exemplos de frases que no so proposies: a) 4+9 (No tem predicado) b) Qual a marca do carro da Maria? (Sentena interrogativa) c) Os estudantes gostam de estudar. (A sentena no pode ser classificada em Verdadeiro ou Falso) d) Que festa boa! (Sentena exclamativa) As proposies podem ser simples ou compostas. Proposio simples no contm nenhuma outra proposio como parte integrantes de si mesma. Exemplos: O Brasil fica na Amrica do Sul 2+3=5 Conectivos lgicos (ou operadores lgicos) so palavras ou frases que em Lgica so utilizadas para formarem proposies compostas. Os conectivos usuais so: A negao no, cujo smbolo A conjuno e, cujo smbolo ^ A disjuno ou, cujo smbolo v O condicional se ... ento, cujo smbolo O bicondicional se, e somente se, cujo smbolo Proposio composta formada por duas ou mais proposies relacionadas pelos conectivos lgicos. Exemplos: 1+7=10 e 3>6 Pedro gordo e inteligente O Brasil o maior produtor de soja ou o menor produtor de milho 1.3 Valor Lgico

O valor lgico de uma proposio P a verdade (ou verdadeiro) se P verdadeira. O valor lgico de uma proposio Q a falsidade (ou falso) se Q for falsa. 1 designa o valor-verdade verdadeiro 0 designa o valor-verdade falso

Exemplos: Considere a proposio P: A Terra gira em torno do Sol. O valor lgico de P Verdadeiro. Escreve-se V(P)=1 ou I(P)=1 Seja a proposio Q: A neve preta. O valor lgico de Q Falso. Escreve-se V(Q)=0 ou I(Q)=0 Exerccios propostos 1 1) Determine o valor lgico de cada uma das seguintes proposies: a) b) c) d) e) O nmero 7 primo. 7 > 9. Curitiba a capital de Minas Gerais. O cachorro um mamfero. A Terra um planeta.

-

Interpretao Interpretao

2) Escrever trs proposies de valor lgico 1. 3) Escrever trs proposies de valor lgico 0. 1.4 Princpios Fundamentais da Lgica

Princpio da No-Contradio Uma proposio no pode se simultaneamente verdadeira e falsa. Princpio do Terceiro Excludo Toda proposio ou s verdadeira ou s falsa, nunca ocorrendo um terceiro caso, ou seja, toda proposio s admite os valores lgicos 1 ou 0. 1.5 Tabela-Verdade

Tabela-verdade uma forma prtica de representar os valores lgicos envolvidos em uma proposio composta. Para uma proposio simples P, temos: 1 P 0 Diagrama da rvore

P 1 0 Tabela-Verdade de P (2 linhas) Para uma proposio simples P, o nmero de linhas da tabela-verdade 21 = 2. Para duas proposies P e Q, o nmero de linhas da tabela-verdade 22 = 4 P Q 1 1 1 0 0 1 0 0 Tabela-Verdade de P e Q (4 linhas) Para trs proposies P, Q e R, o nmero de linhas da tabela-verdade 23 = 8 P 1 1 1 1 0 0 0 0 Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0

Teorema: O nmero de linhas distintas de uma tabela verdade dado por 2n, onde n o nmero de proposies simples componentes e 2 representa o nmero de valores lgicos possveis para uma proposio (1 ou 0). 1.6 Operaes Lgicas sobre Proposies

1.6.1 Negao Definio: Se P uma proposio, a negao da proposio P denotada por P A tabela-verdade da operao negao P P 1 0 0 1 Exemplos:

l-se: no P

P: O Sol um planeta. P: O Sol no um planeta. Q: Maria estudiosa. Q: Maria no estudiosa Supondo que sim.

V(P)=0 ou I(P)=0 V(P)=1 ou I(P)=1 V(Q)=1 V(Q)=0 V(R)=1 V(R)=0 V(S)=0 V(S)=1

R: Os cachorros tm plos. R: No verdade que os cachorros tm plos. S: Joana inteligente. Suponde que no. S: falso que Joana inteligente.

Observao: Negar uma proposio P no apenas afirmar algo diferente do que P afirma. Exemplo1: A proposio O Sol uma estrela, que verdadeira, no uma negao da proposio O Sol um planeta, que falsa. A proposio A neve branca, que verdadeira, no uma negao da proposio A neve preta, que falsa. Exerccios propostos 2 1) Determine a negao das frases a seguir: a) Estou feliz. b) Todos os tomates so vermelhos. c) O Sol est brilhando. d) No vou viajar. e) Esta sala est muito quente. f) H sempre algum feliz. g) Estou certo. 1.6.2 Conjuno Definio: Duas proposies P e Q podem ser combinadas pelo conectivo e para formar uma proposio composta denominada conjuno das proposies originais. Notao: P ^ Q (l-se: P e Q) A tabela-verdade da operao conjunao :

P 1 1 0 0

Q 1 0 1 0

P^Q 1 0 0 0

A conjuno de duas proposies (P ^ Q) verdadeira se, e somente se, cada proposio componente for verdadeira. O smbolo ^ pode ser usado, tambm, para definir a interseo de dois conjuntos. Exemplos: P: Ana estuda geografia. Q: Ana joga xadrez. P ^ Q: Ana estuda geografia e joga xadrez. P: 5>3 Q: 9 um nmero primo P ^ Q: 5>3 e 9 um nmero primo 1.6.3 Disjuno Definio: Duas proposies P e Q podem ser combinadas pelo conectivo ou para formar uma proposio composta denominada disjuno das proposies originais. Notao: P v Q (l-se: P ou Q) Observao: Na linguagem natural, o conectivo ou pode traduzir tanto a idia de hipteses mutuamente exclusivas (ou ocorre isto ou ocorre aquilo) quanto a de que pelo menos uma das hipteses ocorre. Exemplos: 1) A proposio composta chove ou faz frio verdadeira nos seguintes casos: s chove; s faz frio; chove e faz frio. 2) O mesmo no acontece com a proposio composta Pedro passar nos exames ou repetir de ano, que s verdadeira nos seguintes casos: Pedro passar nos exames; Pedro repetir de ano. Mas falsa a hiptese: Pedro passar nos exames e repetir de ano

No primeiro exemplo, a disjuno inclusiva e, no segundo, a disjuno exclusiva. Estudaremos apenas a disjuno inclusiva. A tabela-verdade da operao disjuno inclusiva : P 1 1 0 0 Q 1 0 1 0 PvQ 1 1 1 0

A disjuno inclusiva de duas proposies (P v Q) falsa se, e somente se, todas as proposies componentes forem falsas. Exemplos: 1) P: Maria estudante. Q: Maria enfermeira. P v Q: Maria estudante ou enfermeira. 2) R: 20 um nmero primo. V(R)=0 S: 15 um nmero impar. V(S)=1 R v S: 20 um nmero primo ou 15 um nmero impar. V(R v S)=1 3) Sejam as proposies: P: Ana jogadora de basquete. Q: Ana bonita. Escrever em linguagem natural as seguintes proposies: a) P b) P ^ Q c) P v Q Ana no jogadora de basquete. Ana jogadora de basquete e Ana bonita. Ana jogadora de basquete ou Ana no bonita.

Tabela-verdade para a proposio composta P v Q. P 1 1 0 0 Q 1 0 1 0 Q 0 1 0 1 P v Q 1 1 0 1

Exerccios propostos 3: 1) Considere as seguintes proposies simples: P: 5> 2 Q: 4>3 D o valor lgico de cada uma das seguintes proposies, construindo a tabela-verdade: a) P b) Q c) P d) Q e) P ^ Q f) P v Q g) P ^ Q h) P v Q i) ( P ^ Q ) 2) Considere as proposies: P: Carla saiu. Q: Joana est aqui. Forme sentenas na linguagem natural que correspondam s seguintes proposies: a) b) c) d) e) f) g) h) i) j) P Q P^Q PvQ P ^ Q P v Q ( P ^ Q) ( P v Q) P v Q P ^ Q

3) Considere as proposies: P: Viviane estudante. Q: Viviane atriz. Escreva na forma simblica cada uma das proposies a seguir: a) b) c) d) e) Viviane no estudante. Viviane estudante e atriz. Viviane estudante e no atriz. Viviane no estudante e atriz. Viviane estudante ou atriz.

f) g) h) i) j) k)

Viviane estudante ou no atriz. Viviane no estudante ou atriz. Viviane no estudante ou atriz. No verdade que Viviane estudante ou atriz. No verdade que Viviane no estudante ou no atriz. Viviane no estudante nem atriz.

1.6.4 Condicional ou Implicao Definio: Duas proposies P e Q podem ser combinadas pelo conectivo lgico se ..., ento ... para formar uma nova proposio denominada condicional. Notao: P Q (l-se: se P, ento Q) Outras formas de se ler o condicional P Q: Q, se P. P condio suficiente para Q. Q condio necessria para P.

A proposio P chamada de antecedente e a proposio Q de conseqente. Exemplo: A proposio condicional Se chove, ento a rua fica molhada, tambm pode ser lida das seguintes formas: Chover uma condio suficiente para a rua ficar molhada. A rua ficar molhada uma condio necessria quando chove. Uma proposio condicional afirma que seu antecedente implica seu conseqente. No afirma que seu antecedente seja verdadeiro, mas to somente que, se seu antecedente for verdadeiro, ento seu conseqente ser, tambm, verdadeiro. Exemplos: Dadas as proposies: P: Chove. Q: Faz frio. PQ: Se chove, ento faz frio. A proposio condicional P Q s falsa quando P verdadeira e Q falsa. Caso isto no ocorra, a proposio condicional ser verdadeira. A tabela-verdade da operao condicional : P 1 1 0 0 Q 1 0 1 0 PQ 1 0 1 1

A tabela-verdade positivamente obscura no uso ordinrio. Exemplos: P: O ms de Maio tem 31 dias. (1) Q: A Terra plana. (0) PQ: Se o ms de Maio tem 31 dias, ento a Terra plana (0) V(PQ) = V(P)V(Q) = 1 0 = 0 de acordo com a tabela-verdade -------------------------------------------------------------------------------------------------------------R: A neve branca (1) S: Paris a capital da Frana (1) RS: Se a neve branca, ento Paris a capital da Frana. V(RS) = V( R) V(Q) = 1 1 = 1 de acordo com a tabela-verdade -------------------------------------------------------------------------------------------------------------T: 2+2=4 (1) U: 1>2 (0) TU: Se 2+2=4, ento 1>2 V(TU) = V(T) V(U) = 1 0 = 0 de acordo com a tabela-verdade Observao: O que uma condicional afirma unicamente uma relao entre os valores lgicos do antecedente e do conseqente de acordo com a tabela-verdade. Exerccios propostos 4: 1) Sejam as proposies: P: Est frio. Q: inverno. Traduzir para a linguagem natural as seguintes proposies: a) b) c) d) e) f) g) h) i) 2) a) b) c) d) PQ QP P Q P Q (P ^ Q) P (P ^ Q) Q (P^Q)P Q(P^Q) ( P Q) ^ ( Q P ) Determine o valor lgico de cada uma das proposies a seguir: Se 4+7 = 9, ento 4+8=12. No verdade que se 3+4=9, ento 5+5=11. Se 6+6=8, ento 3+3=6 ou 6+3>10. Se 7>4 e 615 ou 2+8=10.

3) Dadas as proposies: P: Gosto de laranja. Q: Gosto de uva. R: Gosto de abacaxi. Traduzir para a linguagem natural as seguintes proposies compostas: a) b) c) d) e) f) g) h) QP (P^Q)R P(QR) ( P v R) ( P Q ) ( P v Q ) R (Q v R ) P P ( Q ^ R ) P(R^Q)

4) Dadas as proposies: P: Ana alta. Q: Ana elegante. Escreva cada uma das proposies na forma simblica usando as proposies P e Q. a) b) c) d) e) f) g) h) Ana alta e elegante. Ana alta mas no elegante. falso que Ana no alta ou elegante. Ana no alta nem elegante. Ana alta, ou Ana no alta e elegante. No verdade que Ana no alta ou no elegante. Se Ana alta, ento Ana elegante. Ana no alta, se no elegante.

5) Construir a tabela-verdade das proposies compostas, a seguir: a) b) c) d) e) f) (P Q) (P^Q)(PvQ) P ( Q P ) (PQ)(P^Q) (P ^ R ) ( Q v R ) ((PQ)^(QR))(PR)

6) Admitindo falso o condicional P Q, que valor lgico pode ter: a) (P Q ) ^ R b) ( Q v R ) ( P Q )

1.6.5 Bicondicional ou bi-implicao Definio: Duas proposies P e Q podem ser combinadas pelo conectivo lgico ... se, e somente se ... para formar uma nova proposio denominada bicondicional. Notao: P Q (l-se: P se, e somente se Q) Outras formas de se ler o bcondicional P Q: P condio necessria e suficiente para Q. Q condio necessria e suficiente para P.

A proposio (P Q) verdadeira se, e somente se as proposies P e Q possurem o mesmo valor-verdade. A proposio (P Q) falsa se, e somente se as proposies P e Q tiverem valores-verdade trocados. Exemplo: A proposio bicondicional A rua fica molhada se, e somente se chove, tambm pode ser lida das seguintes formas: A rua ficar molhada uma condio necessria e suficiente para chover. Chover uma condio necessria e suficiente para a rua ficar molhada. A tabela-verdade da operao bicondicional : P 1 1 0 0 Q 1 0 1 0 PQ 1 0 0 1

Exemplos: P: O ms de Maio tem 31 dias. (1) Q: A Terra plana. (0) PQ: O ms de Maio tem 31 dias se, e somente se a Terra plana. (0) V(PQ) = V(P) V(Q) = 10 = 0 de acordo com a tabela-verdade -------------------------------------------------------------------------------------------------------------R: A neve branca (1) S: Paris a capital da Frana (1) RS: A neve branca se, e somente se Paris a capital da Frana. V(RS) = V( R) V(Q) = 1 1 = 1 de acordo com a tabela-verdade -------------------------------------------------------------------------------------------------------------T: 2+2=5 (0) U: 1>2 (0) TU: 2+2=5 se, e somente se 1>2. V(TU) = V(T) V(U) = 0 0 = 1 de acordo com a tabela-verdade Exerccios propostos 5: 1) Dadas as proposies: P: O nmero 596 divisvel por 2. Q: O nmero 596 divisvel por 4. R: O nmero 596 divisvel por 3. Passe para a linguagem simblica as proposies compostas abaixo: a) falso que o nmero 596 divisvel por 2 e por 3, ou o nmero 596 no divisvel por 4. b) O nmero 596 divisvel por 2 ou por 4, mas divisvel por 3. c) O nmero 596 divisvel por 2 se, e somente se divisvel por 4 e no divisvel por 3. d) falso que o nmero 596 no divisvel por 2 e por 4, mas divisvel por 3 e por 2. e) Se no verdade que o nmero 596 divisvel por 3, ento divisvel por 2 e no por 4. f) Se no verdade que o nmero 596 divisvel por 3, ento divisvel por 2 e no por 4. 2) Determine o valor lgico de cada uma das proposies compostas do exerccio 1.

3) Sabendo-se que V(P)=V(Q)=1 seguintes proposies compostas: a) b) c) d) e) f) g) h) i) j) k) l)

e

V(R)=V(S)=0, determinar os valores lgicos das

( P ^ ( Q v R) ) ( P ( R v Q ) ) ( Q R ) ( Q v R ) (P v (R ^ S ) ) ( Q (P ^ S ) ) ( P Q ) v ( Q P ) ( P Q ) ^ (R S ) (Q ^ ( P ^ S ) ) P v ( Q ^ ( R S ) ) (P v R ) ( Q S ) (P v ( Q ^ S ) ) ( R S ) Q ^ ( (R v S ) ( P Q ) ) (P(QR))S

4) Considerando as proposies: P: 2 nmero inteiro. Q: 2 nmero par. R: 2 nmero primo. Traduza para a linguagem natural: a) b) c) d) e) f) PQ ( P v Q ) R ( P v Q ) R (P Q ) Q (Q ^ R ) ( P Q ) ( P v Q )

5) Determine o valor lgico das proposies P, Q e R, da questo 4. Em seguida construa tabelas-verdade para os itens de a a f.

1.7

Uso de Parnteses

Deve-se usar parnteses na simbolizao das proposies para evitar qualquer tipo de ambigidade. Por outro lado, em muitos casos, parnteses podem ser suprimidos, a fim de simplificar as proposies simbolizadas, desde que, naturalmente, ambigidade alguma venha a aparecer. A supresso de parnteses nas proposies se faz mediante algumas convenes: A ordem de precedncia para os conectivos : Conectivo ^ v Prioridade 1 2 3 4 5

Portanto, o conectivo mais fraco e o conectivo mais forte . Exemplo: A proposio composta P Q S ^ R uma bicondicional e nunca uma condicional ou uma conjuno. Para convert-la numa condicional seria necessrio usar parnteses: P (QS^R)

1.8

Tautologia

Definio: Chama-se tautologia toda a proposio composta cujo valor lgico da ltima coluna da sua tabela-verdade sempre Verdade (1). As tautologias so tambm chamadas denominadas proposies tautolgicas ou proposies logicamente verdadeiras. Exemplo: P: Chove ou no chove. A tabela-verdade : P 1 0 P 0 1 P v P 1 1 ( P v P )

Logo, ( P v P ) uma tautologia.

1.9

Contradio

Definio: Chama-se contradio toda a proposio composta cujo valor lgico da ltima coluna da sua tabela-verdade sempre Falso (0). As contradies so tambm denominadas proposies contravlidas ou proposies logicamente falsas. Exemplo: P: Chove e no chove. A tabela-verdade : P 1 0 P 0 1 P ^ P 0 0 ( P ^ P )

Logo, ( P ^ P ) uma contradio. 1.10 Indeterminao ou Contingncia Definio: Chama-se contingncia toda a proposio composta cujo valor lgico da ltima coluna da sua tabela-verdade figuram verdade (1) e falso (0). Uma proposio indeterminada (ou contingente) quando no uma tautologia e no uma contradio. As contingncias so tambm denominadas proposies contingentes ou proposies indeterminadas. Exemplo: A proposio P P uma contingncia. A tabela-verdade : P 1 0 P 0 1 P P 0 1

Exerccios propostos 6: 1) Determinar quais das seguintes proposies compostas so tautolgicas, contravlidas (indeterminadas) ou contingentes (indeterminadas): a) P (P Q ) b) ( ( P v Q ) P ) ( Q ^ P ) c) ( P Q ) v R d) R v ( P Q ) e) ( ( P Q ) R ) ( P ( Q R ) ) f) ( ( ( P ^ Q ) ) ) ^ (P ^ R ) g) ( ( P v Q ) ( Q ^ P ) ) ( ( R ^ P ) v Q ) h) ( P ( Q R ) ) ( ( P ^ ( Q ^ R ) ) ( P ^ ( P v R ) ) ) 2) Quais das seguintes frmulas logicamente equivalente frmula ( P Q ) ? a) Q ^ P b) Q v ( R v P ) c) Q P

1.11 Frmulas Atravs dos conectivos lgicos pode-se construir sentenas mais complexas a partir de outras sentenas mais simples. As sentenas simples (proposies simples) denominadas de frmulas atmicas (P, Q, R, ...) desempenham o papel de sentenas bsicas ou atmicas da linguagem proposicional. As sentenas, que daqui em diante recebero o nome de frmulas, em geral so obtidas pela seguinte definio: 1) Todas as frmula atmicas so frmulas. 2) Se A e B so frmulas, ento: (A) (A ^ B) (A v B) (A B) (A B) So frmulas. 3) Uma dada expresso constitui uma frmula se, e somente se foi obtida pela aplicao de uma das regras 1 ou 2, acima. Usaremos a seguinte terminologia: (A) (A ^ B) (A v B) (A B) (A B) uma frmula do tipo no / negao. uma frmula do tipo e / conjunao. uma frmula do tipo ou / disjunao. uma frmula do tipo condicional / implicao. uma frmula do tipo bicondicional / bi-implicao.

1.12 rvore de decomposio de uma frmula Seja a frmula: F : ( ( A ^ B ) ( ( A v C ) ) ) Sua rvore de decomposio :

(( A ^ B ) ( ( A v C ) ) )

A^B A B A

(AvC) AvC C

importante ter em mente que uma frmula definida passo a passo e nica a sua construo. Desta forma, pode-se dizer qual conectivo foi aplicado inicialmente, o segundo, etc., at chegarmos ao ltimo. Exerccios propostos 7: 1) Construa as rvores de decomposio das seguintes frmulas: a) F : ( A ( A v B ) ) b) G : ( ( ( A ^ B ) ( ( A B ) ) ) ) c) H : ( ( A ( B C ) ) ( ( A C ) ( A D ) ) ) 2) Observando a rvore de decomposio apresentada a seguir, podemos afirmar que tal rvore equivale a qual frmula? ^

A

B B

A

3) Exerccios de reviso 3.1) Qual das frases a seguir uma proposio? a) b) c) d) e) Que cavalo bravo! Joana, onde ests tu? 3+6=45 4*3=x e 2+z=8 n.d.a.

3.2) Indique qual das frases abaixo contraditria: a) b) c) d) e) PP P v P P ^ P P P n.d.a. G: (Q P) e os valores lgicos V(H)=1 e

3.3) Seja as frmulas H: ( P Q ), V(G)=0, logo, podemos afirmar que: a) b) c) d) e) V(P)=1 e V(Q) = 1 V(P)=1 e V(Q) = 0 V(P)=0 e V(Q) = 1 V(P)=V(Q) n.d.a.

1.13 rvore de refutao As tautologias constituem uma classe importante de frmulas, pois so sentenas verdadeiras. Em Cincia, a busca do conhecimento implica na busca da verdade. Na linguagem da lgica clssica, a verdade se reflete, de modo particular, nas tautologias. Na lgica proposicional, h um mtodo efetivo para testar se uma frmula tautologia ou no, valendo-se das tabelas-verdade. Veremos um outro mtodo ou algoritmo, denominado rvore de refutao de frmulas para verificar se uma dada frmula tautologia ou no. Passos da rvore de refutao: Vamos verificar se a frmula F: ( (A ^ B ) A ) tautologia. 1) Traa-se linhas em nmero suficiente e colunas para cada frmula atmica ou conectivo componente. ( (A ^ B) A)

2) Suponha-se que a frmula F seja 0 (falsa). Escreve-se o valor-verdade 0 (falso) abaixo do ltimo conectivo da frmula em questo. ( (A ^ B) 0 A)

No caso desta frmula o ltimo conectivo o da implicao ou condicional. Colocamos 0 (falso) na linha imediatamente abaixo e na coluna correspondente. Observe que o valor atribudo o valor da frmula (A ^ B ) A, ou seja, ela falsa. 3) Atravs da tabela-verdade do conectivo condicional, observamos que o condicional 0 (falso) se e somente se o antecedente (A ^ B ) 1 (verdadeiro) e o conseqente A 0 (falso). Anotaremos estes valores na linha imediatamente seguinte, nas respectivas colunas. ( (A ^ 1 B) 0 A) 0

4) Atravs da tabela-verdade da conjuno, verificamos que uma conjuno 1 (verdadeira) se e somente se ambas frmulas A e B forem verdadeiras, ou seja, o valorverdade de A 1 e de B 1. No caso da frmula da direita, no necessrio repetir o processo, pois ela j atmica. ((A ^ 1 1 1 B) 0 A) 0

5) Se olharmos para a tabela resultante, observamos que a sentena A 1 (verdadeira) na primeira coluna, e 0 (falsa) na ltima coluna, ou seja, a sentena A est sendo verdadeira e falsa ao mesmo tempo, constituindo uma inconsistncia ou contradio. Como em lgica clssica, consideramos que no existem inconsistncias, algum passo que realizamos est errado, ou seja, falso. O nico elo fraco acima justamente o primeiro passo, quando consideramos que a frmula F era falsa. Portanto, conclui-se que a frmula F sempre 1 (verdadeira). Se a frmula F sempre verdadeira, ela tautologia, como queramos provar. Outros exemplos: 1) Frmula G: (( A ^ B) ( (A ^ B ) ) ) Nos exerccios e exemplos a seguir, os passos descritos anteriormente, sero feitos em uma nica tabela. A tabela baseada na rvore de decomposio de uma frmula (j visto anteriormente). ( (A ^ 1 1 1 B) 0 ( 0 1 1 1 Concluso: Supondo que a frmula G falsa, chegamos a valores-lgicos nocontraditrios. Sendo assim, conclumos que a frmula G no uma tautologia. 2) Frmula H: ( ( ( A ^ B) C ) ( A ( B C ) ) ) 1 caso: (((A ^ B) 1 1 1 1 1 1 1 C) 0 (A 0 0 0 ( B C))) (A ^ B) ) )

2 caso: (((A ^ B) 0 1 1 1 0 1 1 C) 0 (A 1 1 1 ( B C)))

Como esta frmula do tipo bicondicional tivemos que analisar dois casos, de acordo com a tabela-verdade. Em qualquer um dos casos, camos em contradio. Concluso: A frmula G uma tautologia. Verificando atravs da tabela-verdade:A B C ( A ^ B) ( ( A ^ B) C ) ( BC) (A ( BC)) ( ( ( A ^ B) C ) ( A ( B C ) ) )

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 0 0 0 0 0 0

1 0 1 1 1 1 1 1

1 0 1 1 1 0 1 1

1 0 1 1 1 1 1 1

1 1 1 1 1 1 1 1

Concluso: Pela tabela-verdade, a frmula G realmente, uma tautologia.

Exerccios propostos 8: 1) Demonstrar, pelo mtodo da rvore de refutao, se as seguintes frmulas so tautologias. a) ( ( A B ) (A v B ) ) b) ( ( A B ) B ) c) ( ( A ^ B ) ^ ( ( A v B ) ) ) d) ( ( A ( A v B ) ) ) e) ( A v (A ) ) f) ( ( B ^ (B ) ) ) g) ( ( (A) ^ (B ) ) ( ( A v B ) ) ) h) ( ( ( A ^ B ) ) ( (A ) v (B ) ) ) i) P (P Q ) j) ( ( P v Q ) P ) ( Q ^ P ) k) ( P Q ) v R l) R v ( P Q ) m) ( ( P Q ) R ) ( P ( Q R ) ) n) ( ( ( P ^ Q ) ) ) ^ (P ^ R ) o) ( ( P v Q ) ( Q ^ P ) ) ( ( R ^ P ) v Q ) p) ( P ( Q R ) ) ( ( P ^ ( Q ^ R ) ) ( P ^ ( P v R ) ) )

1.14 Implicao Lgica Definio: Dadas duas frmulas A e B, diz-se que ocorre uma implicao lgica (ou relao de implicao) entre A e B quando a condicional A B uma tautologia. Notao: AB

L-se: A implica B ou se A, ento B Obs.: Os smbolos e tm significados diferentes. O smbolo realiza uma operao entre proposies. O smbolo indica uma relao, ou seja, a condicional associada uma tautologia.

Exemplo: Mostrar que (A ^ B ) A A 1 1 0 0 B 1 0 1 0 A^B 1 0 0 0 (A ^ B) A 1 1 1 1

Como (A ^ B) A uma tautologia, ento (A ^ B ) A, isto , ocorre a implicao lgica. 1.15 Equivalncia Lgica Definio: Dadas duas frmulas A e B, diz-se que ocorre uma equivalncia lgica entre A e B quando suas tabelas-verdade forem idnticas. Notao: AB ou A B

L-se: A equivalente a B Frmulas equivalentes transmitem a mesma informao.

Exemplo: Mostrar que (A B ) ^ ( B A) e A B so equivalentes. A 1 1 0 0 B 1 0 1 0 AB 1 0 1 1 BA 1 1 0 1 (A B ) ^ ( B A) 1 0 0 1 AB 1 0 0 1

Logo, (A B ) ^ ( B A) A B. Teorema: A frmula A logicamente equivalente formula B, ou seja, (A B), sempre que o bicondicional (A B) uma tautologia. Exemplo: Mostrar que (A ^ B) ( (A v B ) ). A 1 1 0 0 B 1 0 1 0 A^B 1 0 0 0 A 0 0 1 1 B 0 1 0 1 A v B 0 1 1 1 (A v B ) 1 0 0 0 (A ^ B) ( (A v B )) 1 1 1 1

Como (A ^ B) ( (A v B )) uma tautologia, ento (A ^ B) ( (A v B ) ), ou seja, ocorre a equivalncia lgica. Exerccios propostos 9: 1) Verificar se ocorrem implicaes e equivalncias nas seguintes frmulas: a) ( A ^ ( A B ) ) B b) ( ( A B ) ^ ( B C ) ) ( A C ) c) ( ( A ^ B ) C ) ( A ( B C ) ) d) ( A B ) ( ( A ^ C ) ( B ^ C ) ) e) ( ( A B ) ^ ( B C ) ) ( A C ) f) ( (A B ) ^ ( A C ) ) ( A ( B ^ C ) )

1.16 Equivalncias Notveis 1.16.1 Dupla Negao AA A 1 0 A 0 1 A 1 0

1.16.2 Leis idempotentes 1) A ^ A A A 1 0 A^A 1 0

2) A v A A A 1 0 AvA 1 0

1.16.3 Leis comutativas 1) A ^ B B ^ A A 1 1 0 0 B 1 0 1 0 A^B 1 0 0 0 B^A 1 0 0 0

2) A v B B v A A 1 1 0 B 1 0 1 AvB 1 1 1 BvA 1 1 1

0

0

0

0

1.16.4 Leis associativas 1) A ^ ( B ^ C ) ( A ^ B ) ^ C A 1 1 1 1 0 0 0 0 B 1 1 0 0 1 1 0 0 C 1 0 1 0 1 0 1 0 B^C 1 0 0 0 1 0 0 0 A^ (B^C) 1 0 0 0 0 0 0 0 A^B 1 1 0 0 0 0 0 0 (A^B)^C 1 0 0 0 0 0 0 0

2) A v ( B v C ) ( A v B ) v C A 1 1 1 1 0 0 0 0 B 1 1 0 0 1 1 0 0 C 1 0 1 0 1 0 1 0 BvC 1 1 1 0 1 1 1 0 Av (BvC) 1 1 1 1 1 1 1 0 AvB 1 1 1 1 1 1 0 0 (AvB)vC 1 1 1 1 1 1 1 0

1.16.5 Leis de Morgan 1) ( A ^ B ) A v B A 1 1 0 0 B 1 0 1 0 A^B 1 0 0 0 (A^B ) 0 1 1 1 A 0 0 1 1 B 0 1 0 1 A v B 0 1 1 1

2) ( A v B ) A ^ B A 1 B 1 AvB 1 (AvB) 0 A 0 B 0 A ^ B 0

1 0 0

0 1 0

1 1 0

0 0 1

0 1 1

1 0 1

0 0 1

1.16.6 Leis distributivas 1) A ^ ( B v C ) ( A ^ B ) v ( A ^ C ) A 1 1 1 1 0 0 0 0 B 1 1 0 0 1 1 0 0 C 1 0 1 0 1 0 1 0 BvC 1 1 1 0 1 1 1 0 A^ (BvC) 1 1 1 0 0 0 0 0 A^B 1 1 0 0 0 0 0 0 A^C 1 0 1 0 0 0 0 0 (A^B)v(A^C) 1 1 1 0 0 0 0 0

2) A v ( B ^ C ) ( A v B ) ^ ( A v C ) A 1 1 1 1 0 0 0 0 B 1 1 0 0 1 1 0 0 C 1 0 1 0 1 0 1 0 B^C 1 0 0 0 1 0 0 0 A v (B^C) 1 1 1 1 1 0 0 0 AvB 1 1 1 1 1 1 0 0 AvC 1 1 1 1 1 0 1 0 (AvB)^(AvC) 1 1 1 1 1 0 0 0

1.16.7 Negao do condicional A B (A ^ B ) A 1 1 0 0 B 1 0 1 0 AB 1 0 1 1 B 0 1 0 1 A v B A ^ B 0 1 0 0 (A ^ B ) 1 0 1 1

Concluso: ( A B ) A ^ B Exemplos:

(Negao do condicional)

1) So equivalentes as proposies: Se Ana alta, ento ela elegante. No verdade que Ana alta e no elegante. Ana no alta ou ela elegante 2) A negao de: Se Ana alta, ento ela elegante. Ana alta e no elegante.

e e

1.16.8 Proposies associadas a um condicional Das proposies: a) A B (condicional) b) B A (recproca do condicional) c) B A (contrapositiva) d) A B (recproca da contrapositiva ou inversa) Resultam as duas equivalncias notveis: 1) (A B) (B A ) A 1 1 0 0 B 1 0 1 0 AB 1 0 1 1 A 0 0 1 1 B 0 1 0 1 B A 1 0 1 1

2) (B A) (A B ) A 1 1 0 0 B 1 0 1 0 BA 1 1 0 1 A 0 0 1 1 B 0 1 0 1 A B 1 1 0 1

Exemplo: Dadas as proposies: A: O cu est nublado. B: Vai chover. Condicional

A B: Se o cu est nublado, ento vai chover.

Recproca B A: Se vai chover, ento o cu est nublado. Contrapositiva B A: Se no vai chover, ento o cu no est nublado. Inversa A B: Se o cu no est nublado, ento no vai chover.

1.16.9 Bicondicional A B (A B) ^ (B A) A 1 1 0 0 B 1 0 1 0 AB AB 1 1 0 0 0 1 1 1 BA 1 1 0 1 (A B) ^ (B A) 1 0 0 1

Exerccios propostos 10: 1) Aplicando as Leis de Morgan, dar a negao de cada uma das seguintes proposies: a) b) c) d) A ^ B A v B A ^ B A v B

2) Dar a negao em linguagem natural de cada uma das seguintes proposies: a) Pedro gosta de laranja e Maria gosta de pera. b) Ana bonita ou no baixa. c) noite e a cidade descansa.

3) Dar a negao, em linguagem simblica, das seguintes proposies: a) b) c) d) e) f) B A A B A (B ^ C ) (A^B)C (A(BC) A(BC)

4) Dar a negao, em linguagem natural, das seguintes proposies: a) b) c) d) Se est frio, ento est chovendo Se est sol, ento eu irei praia. Se Maria bonita e rica, ento ela feliz. O cinema fica lotado, se o filme bom.

5) Atravs de equivalncias, eliminar o conectivo nas proposies seguintes: a) ( A B ) C b) A ( A v B ) 6) Escreva a proposio recproca, a inversa e a contrapositiva de cada uma das proposies seguintes: a) b) c) d) Se Carlos est doente, ento ele precisa de um mdico Se x par, ento x2 par. Se x 7 , U=N V = { 6, 7, 8, 9, 10, ... } V={xN/x6} b) x divisvel por 2, V = { 0, 2, 4, 6, ... } V = { x N / x par } c) x + 2 < 4 , U=Z U=N

V = { 1, 0, -1, -2, -3, ... } V={xZ/x1} 1.17.2 Sentenas Abertas com Duas ou Mais Variveis A sentena aberta x + y = 6 cujo universo de discurso N, possui como conjunto-soluo todos os pares (x,y) que satisfaam a sentena: Vp(x,y) = { (x,y) N x N / x + y = 6 } Vp(x,y) = { (0,6), (1,5), (2,4), (3,3), (4,2), (5,1), (6,0) } Uma sentena aberta tambm pode estar definida por um sistema de equaes/inequaes. Neste caso, as sentenas encontram-se ligadas pelo conectivo e ( ^ ). Por exemplo: Qual o nmero inteiro positivo que somado 2, resulta num nmero maior que 9, e subtraindo 3, resulta num nmero menor que 8 ?

Simbolicamente temos: p(x): x + 2 > 9 ^ x 3 < 8, U=Z+

Neste caso, o conjunto-verdade dado pela interseo dos conjuntos-verdades das duas sentenas abertas que compem p(x). Isto : V1 = { x Z / x + 2 > 9 } V1 = { 8, 9, 10, 11, 12, ... } V2 = { x Z / x 3 < 8 } V2 = { 10, 9, 8, 7, 6, ... } Vp(x) = V1 V2 = { 8, 9, 10 } 1.17.3 Exerccios propostos 15: 1) Traduza as frases a seguir para sentenas abertas: a) Qual o nmero inteiro que, multiplicado por 3 e depois somado com 5, d 17. b) Determine um nmero inteiro tal que o dobro do seu quadrado somado com seu quntuplo, subtraindo 3, d um nmero maior que 10. 2) Traduza cada sentena aberta a seguir para a linguagem natural: a) b) c) d) 3x + 9 = 18 5x = 40 x + 7 > 13 2x + 3y = 9

3) Determine o conjunto verdade das seguintes sentenas: a) b) c) d) e) f) g) h) i) 2x + 5 = 13 e U = N 3x 7 5 e U = N x + y < 6, com x { 2,3,4,5,6,7} e y { 1,2,3,4} 2x + y = 10, com x e y N (x 4) com U = {0,1,2,3,4,5,6} (x par) com U = {0,1,2,3,4,5,6} x par x primo com U = {0,1,2, ... , 10} x divide 9 x > 4 com U = {0,1,2, ... , 10} x < 1 x divisor de 24 com U = {0,1,2, ... , 10}

1.18 Quantificadores Uma sentena aberta pode se tornar uma proposio atravs do uso de quantificadores, que so elementos que transmitem a idia de quantidade. 1.18.1 Quantificador Universal ( ) O smbolo (x) l-se: para todo x; para qualquer elemento x; qualquer que seja x; para qualquer x, etc.

Exemplo: Dada a proposio: Todos os homens so mortais. E considerando: H: conjunto dos homens. M: conjunto dos mortais. Podemos simboliz-la por: x H, x Msentena aberta proposio

ou

x, x H x M ou ainda, considerando:sentena aberta proposio

H(x): x homem. M(x): x mortal. Temos: (x) (H(x) M(x)) Sendo p(x) uma sentena aberta em um conjunto A, no vazio, e Vp(x) = {x A / p(x) } seu conjunto-verdade, temos que (x A, p(x)) uma proposio verdadeira se, e somente se, Vp(x) = A.

Exemplos: A proposio (n N, n+4>3) verdadeira, pois Vp = { n N / n+4 > 3} = { 0,1,2,3,4,...} = N A proposio (n N, n+2>8) falsa, pois Vp = { n N / n+2 > 8} = { 7,8,9,...} N

1.18.2 Quantificador Existencial ( ) O smblo (x) l-se: existe x tal que; para algum elemento x; para pelo menos um x; ao menos um x, etc.

Exemplo: Dada a proposio: Existem homens que so sbios. E considerando: H: Conjunto dos homens. F: Conjunto dos sbios. Podemos simboliz-la por: x H, x F ousentena aberta proposio

x, x H ^ x F ou ainda, considerando:sentena aberta proposio

H(x): x homem. F(x): x sbio. Temos: (x) (H(x) ^ F(x)) Sendo p(x) uma sentena aberta em um conjunto A, no vazio, e Vp(x) = {x A / p(x) } seu conjunto-verdade, temos que (x A, p(x)) uma proposio verdadeira se, e somente se, Vp(x) . Isto , pelo menos um x A satisfaz p(x).

Exemplos: A proposio (n N, n+4