1.4 TAUTOLOGIA

Os conectivos lógicos, do mesmo modo que servem para construir proposições compostas a partir de proposições simples, também são utilizados para obter esquemas lógicos muito mas complexos a partir de proposições compostas.

Em geral  é o conectivo de menor hierarquia, logo seguem  e , esses conectivos tem a mesma hierarquia; logo  é o de maior hierarquia. Porem, cada conectivo pode ser de maior hierarquia, quando o indica o parênteses de coleção.

Lembre que os parênteses ( ) servem para denotar o “alcance” dos conectivos.

Exemplo 1.17

Se a lua é quadrada e a neve é branca então a lua não é quadrada. Na linguagem simbólica escrevemos: p  q   p .

A lua não é quadrada se, e somente se, a neve é branca. Na linguagem simbólica escrevemos:  p  q

Dada uma proposição composta, os valores-verdade de esta proposição são os que correspondem aos valores do conectivo de maior hierarquia presente na proposição.

Exemplo 1.18

A fórmula p  q   r  p   q deve ser entendida como: ((p  q)  ( r))  ( p  ( q))

Definição 1.8 Tautologia.

Chama-se tautologia toda proposição composta quando, depois de procurar a última coluna de sua tabela-verdade achamos somente a letra ( v ).

De outro modo, tautologia é toda proposição composta P(p, q, r, . . . ) cujo valor lógico sempre é verdade ( v ), quaisquer que sejam os valores lógicos das proposições simples p, q, r, . . .

Exemplo 1.19

Determine a tabela-verdade para proposição: P(p, q) : ((p  q)   q)  p.

Solução

p q ((p  q)   q)  p

v v v f f v v

v f v v v v v

f v v f f v f

f f f f v v f

1o 3o 2o 5o 4o

Para obter a tabela-verdade seguimos o seguinte roteiro:

1º. Aplicamos o valor-verdade da disjunção para as proposições p e q.

2º. Aplicamos a negação à proposição q.

3º. Aplicamos a valor-verdade às colunas 1º e 2º.

4º. Escrevemos novamente valor-verdade para a proposição p.

5º. Aplicamos o valor-verdade da implicação às colunas 3º e 4º.

Observe-se nesta proposição composta que o conectivo da implicação é o de maior hierarquia e na 5ª coluna todas as linhas tem o valor-verdade ( v ), logo a proposição é uma tautologia.

Exemplo 1.20

A proposição p   p é tautologia.

p  p p   p

v f ( v )

f v ( v )

Definição 1.9 Contradição.

Chama-se contradição toda proposição composta quando, depois de procurar a última coluna de sua tabela-verdade achamos somente a letra ( f ).

De outro modo, contradição é toda proposição composta P(p, q, r, . . . ) cujo valor lógico sempre é falso ( f ), quaisquer que sejam os valores lógicos das proposições simples p, q, r, . . . .

Portanto, P(p, q, r, . . .) é uma tautologia se, e somente se,  P(p, q, r, . . .) é uma contradição.

Definição 1.10 Contingência.

Chama-se contingência toda proposição composta quando, depois de procurar a última coluna de sua tabela-verdade achamos uma mistura de linhas com a letra ( v ) ou ( f ).

De outro modo, uma contingência é toda proposição composta que não é tautologia nem contradição. As contingências também são chamadas de proposições contingentes ou proposições indeterminadas.

Exemplo 1.21

A proposição p   p é uma contradição.

p  p p   p

v f ( f )

f v ( f )

Exemplo 1.22

Determine a tabela-verdade para a proposição: P(p) :  ((p  p )  p )

Solução

p  ((p  p )  p )

v ( f ) v v v v v

f ( f ) f f f f f

6º 1º 3º 2º 5º 4º

Portanto, a proposição: P(p) :  ((p  p )  p) é uma contradição.

Exemplo 1.23

Determine a tabela-verdade para a proposição: P(p, q,r):  ((p  q )   r)

Solução

Observe que o conectivo de maior hierarquia é  .

P q r  ((p  q)   r)

v v v v v ( f ) f

v v f f v ( v ) v

v f v v f ( f ) f

v f f v f ( f ) v

f v v v f ( f ) f

f v f v f ( f ) v

f f v v f ( f ) f

f f f v f ( f ) v

Portanto, a proposição: P(p, q, r):  ((p  q )  r) é uma contingência.

1.4.1 Tautologias elementares.

1. Leis da equivalência.

(a) p  p . . . reflexiva.

(b) (p  q)  (q  p) . . . simetria.

(c) ((p  q)  (q  r))  (p  r) . . . transitividade.

2. Lei do terceiro excluído.

p   p

3. Lei do silogismo hipotético.

((p  q)  (q  r))  (p  r)

4. Lei do silogismo disjuntivo.

((p  q)   p)  q

5. Lei do absurdo.

(a) ( q  (p   p))  q (b) ( q  (p   p))  q

(c) (( q  p)  ( q   p))  q

6. Lei de não contradição.

 (p   p)

7. Lei comutativa.

(a) Para a conjunção: (p  q)  (q  p)

(b) Para a disjunção: (p  q)  (q  p)

(c) Para a bicondicional: (p  q)  (q  p)

8. Lei associativa.

(a) Para a conjunção: (p  (q  r))  (p  q)  r)

(b) Para a disjunção: (p  (q  r))  (p  q)  r)

9. Lei distributiva.

(a) (p  (q  r))  ((p  q)  (p  r) )

(b) (p  (q  r))  ((p  q)  (p  r) )

10. Leis de Morgan.

(a)  (p  q)  ( p   q) (b) (p  q)  ( p   q)

11. Dupla negação.

 ( p)  p

12. Adição.

p  (p  q)

13. Simplificação.

(a) (p  q)  p (b) (p  q)  p

14. Modus Ponens.

((p  q)  p)  q

15. Modus Tollens.

(( q   p)  p)  q

16. Idempotente.

(a) (p  p)  p (b) (p  p)  p

17. Transposição (ou de contraposição).

(p  q)  ( q   p)

18. Implicação material.

(p  q)  ( p  q )

19. Equivalência material.

(a) (p  q )  ((p  q )  (q p))

(b) (p  q )  ((p  q )  ( p   q))

20. Dilema construtivo.

((p  q)  (r  s)  (p  r))  (q  s)

21. Dilema destrutivo.

((p  q)  (r  s)  ( q   s))  ( p   r)

22. Exportação.

(a) ((p  q)  r)  (p  (q  r))

(b) ((p1  p2  . . .  pn)  r)  (p1  p2  . . .  pn-1)  (pn  r))

1.4.2 Implicação lógica.

Definição 1.11

Dizemos que uma proposição P(p, q, r, . . . ) implica, logicamente outra proposição Q(p, q, r, . . . ) se, sempre que P(p, q, r, . . . ) seja verdadeira ( v ), então Q(p, q, r, . . . ) também é verdadeira ( v ) .

Exemplo 1.24

Sejam P(p, q):  p  q e Q(p, q): p  q, temos que:

p q  p  q p  q p q P(p, q)  Q(p. q)

v v v v v v v

v f v f

f v v v f v v

f f v v f f v

Logo a proposição P(p, q) implica logicamente a Q(p, q).

Exemplo 1.25

Mostre que a proposição P(p, q): p  (p  q) implica logicamente à proposição Q(p, q): p  q.

Solução

p q p  (p  q) p  q p q P(p, q)  Q(p. q)

v v v v v v v

v f v f

f v v v f v v

f f v v f f v

Exemplo 1.26

Determine se a proposição R(p, q): p  q implica logicamente a proposição S(p, q): p   q.

Solução

p q p  q p   q p q P(p, q)  Q(p. q)

v v v v v v v

v f v f

f v v f f v f

f f v v f f v

Observe a terceira linha da tabela-verdade, a verdade de R(p,q) não implica a verdade de S(p,q).

Portanto a proposição R(p, q), não implica logicamente a proposição S(p, q).

Propriedade 1.1

A proposição P(p1, p2, . . . , pn) implica logicamente a proposição Q(p1, p2, . . . , pn), se e somente se a condicional P(p1, p2, . . . , pn)  Q(p1, p2, . . . , pn) é tautologia.

Demonstração

Condição necessária. (  )

Se P(p1, p2, . . . , pn) implica logicamente a proposição Q(p1, p2, . . . , pn), então não ocorre que os valores na mesma linha da tabela verdade sejam simultaneamente ( v ) e ( f ) nessa ordem; logo a valor verdade na coluna da tabela da proposição P(p1, p2, . . . , pn)  Q(p1, p2, . . . , pn) somente é ( v ), assim esta condicional é tautologia.

Condição suficiente. (  )

Se a condicional P(p1, p2, . . . , pn)  Q(p1, p2, . . . , pn) é tautologia, isto é na última coluna de sua tabela-verdade temos somente a letra ( v ), então não ocorre que os valores simultâneos correspondentes à mesma linha sejam ( v ) e ( f ) nessa ordem. Portanto a proposição P(p1, p2, . . . , pn) implica logicamente Q(p1, p2, . . . , pn).

Exemplo 1.27

Mostre que a proposição p implica logicamente a proposição q em cada um dos seguintes casos:

a) p:  > 2; q: tan =

b) p: sen = q: >

c) p:12 é múltiplo de 4; q :6 é divisível por 2.

Solução (a), (b), (c)

A proposição p é verdadeira; q verdadeira; logo p  q é verdadeira; assim p implica logicamente a proposição q.

1.4.3 Equivalência lógica.

Definição 1.12

Dizemos que uma proposição P(p, q, r, . . . ) é logicamente equivalente a outra proposição Q(p, q, r, . . . ), se a tabela-verdade destas duas proposições são idênticas.

Indica-se que a proposição P(p, q, r, . . . ) é equivalente à proposição Q(p, q, r, . . . ) com a notação P(p, q, r, . . . )  Q(p, q, r, . . . )

Observe que, no caso das proposições P(p, q, r, . . . ) e Q(p, q, r, . . . ) ambas serem tautologias ou contradições, então são equivalentes.

Exemplo 1.28

As proposições P(p,q): p  p  q e Q(p,q): p  q são equivalentes.

Com efeito, observe a tabela-verdade.

p q p  p  q p  q

v v v v

v f f f

f v v f

f f v v

Exemplo 1.29

As proposições R(p,q): p  q e S(p,q): (p  q)  (q  p) são equivalentes.

Observe a tabela-verdade.

p q p  q (p  q)  (q  p)

v v v v

v f f f

f v f f

f f v v

Logo as proposições R(p,q) e S(p,q) são logicamente equivalentes.

Exemplo 1.30

Consideremos a proposição p  q assim como sua recíproca q  p, sua inversa  p   q e sua contra-recíproca  q  .

Da seguinte tabela-verdade:

p q p p  q   p q  p  p   q

v v v v v v

v f f f v v

f v v v f f

f f v v v v

Podemos observar que as proposições p  e  q   p são logicamente equivalentes, assim como as proposições q  p e  p   q.

Exemplo 1.31

Suponha estamos a demonstrar que:

“Se x2 é número ímpar, então x é número ímpar”.

Podemos considerar a proposição p: x2 é número ímpar, e q: x é número ímpar então temos que verificar a validade da proposição p  q. De o fato serem as proposições p  q e  q   p logicamente equivalentes será suficiente mostrar que:

“Se x não é número ímpar, então x^2 não é número ímpar”.

Definição 1.13

a) Chama-se negação conjunta das proposições p e q à proposição  p   q, e denotamos p  q.

b) Chama-se negação disjunta das proposições p e q à proposição  p   q, e denotamos p  q.

Da Definição(1.13) resulta que: a) p  q   p   q , e b) p  q   p   q.

Exemplo 1.32

Determine a tabela-verdade da proposição: (p  q )  (p  q).

Solução

p q p  q  (p  q)

v v f ( v ) f

v f f ( v ) v

f v f ( v ) v

f f v ( f ) v

Exercícios 1-2

1. Analisar os seguintes enunciados e:

1. Determine quais são proposições.

2. Determine quais são enunciados abertos.

3. Determine quais não são nem proposições nem enunciados abertos.

4. Determine o valor verdade das proposições.

(a) 7 + 12 = 19

(b) Você é estudante de matemática?

(c) 15 < 4

(d) x + 4 = 10

(e) Cantor revolucionou o pensamento matemático.

(f) x - 2 < 8

(g) Cantor, Burali Forti e B. Russell estudaram o problema dos paradoxos na matemática.

(h) x + y  2

(i) x é engenheiro.

(j) Pedro é engenheiro ou Pedro é matemático,

(k) x + 2 = 5 se, e somente se, x = 4

(l) Escute com atenção.

(m) Todo retângulo é um quadrado.

2. Sejam as seguintes proposições: p: 3+5 = 5 e q: 8-3 = 5 . Traduzir para a linguagem do dia-a-dia as seguintes proposições:

1.  p 2. p  q 3. p  q

4. q  q 5. p   q 6. p   q

7.  p   q 8. p   q 9. p   q  p

3. Considere as seguintes proposições: p: Jorge é médico, q: Jorge é dentista, r: Pedro é engenheiro.

1. Escrever cada uma das seguintes proposições em forma simbólica:

(a) Jorge é médico e Pedro é engenheiro.

(b) Se Jorge é médico ou Pedro é engenheiro, então Jorge não é dentista.

(c) Jorge não é médico, porem Pedro não é engenheiro.

(d) Se Pedro é engenheiro e Jorge não é dentista, então Jorge não é médico.

2. Escrever em forma de oração o significado das seguintes proposições:

1. p   q 2. ( p  q)  r 3. p   q

4. r  (p  q) 5. ( p  q)  (p   q) 6. p  p  q)

4. Para cada uma das seguintes proposições, elimine os parênteses segundo as convenções:

1. (p  q)  (( p )  r ) 2. p  ((( q)  (r  s))  (p  q))

3. ( p )  (q  (( r)  s)) 4. ((p  ( q)  r )  s)  (( p )  r)

5. Verificar quais as fórmulas é: tautologia, contradição ou contingência.

1.  p  p  q 2. (p  q)  (q  r)  (p  r)

3. (p  q)  (q  p) 4. p  ( p  q)

5. (p  q)  ( p   q) 6. (p  p  q)

6. Sejam as proposições p: Pedro é rico e q: Fredy é feliz. Traduzir para a linguagem corrente as seguintes proposições:

1. p  q 2. p   q 3. p   q

4.  q  p 5.   q 6. ( p   q)

7. p  (p  q)  p 8. (p  q)  p 9. (p   q)   p   q

7. Verificar as seguintes tautologias:

1. p  p  p 2. ( p)  p 3. (p  q)  r  p  (q  r)

4. (p  q)  q 5. p  p  p 6. (p  q)  r  p  (q  r)

7. (p  q)  p 8. p  (p  q)  p 9.  (p  q)   p   q

10. p  p  r 11. p  (p  q)  p 12  (p  q)   p   q

13. p  ( q  r)  (p  q)  (p  r) 14. ( q  p   p )  q

15. p  ( q  r)  (p  q)  (p  r)

8. Verificar se o conjunto de proposições da cada item é tautologia:

1. Pedro é bom e Pedro é ruim acarreta que Paris é a capital de Chile. Brasília é a capital do Brasil ou Brasília não é a capital de Brasil.

2. Se Alberto é materialista, Alberto é ateu. Se Alberto é ateu, então Alberto é materialista.

3. Se João não encontrou Pedro ontem, então, ou Pedro é o assassino ou João morreu. Se Pedro não é o assassino, então João não encontrou Pedro ontem e o assassinato foi à meia noite. Se o assassinato foi à meia noite, então, Pedro é o assassino ou João morreu. Pedro é o assassino.

9. Mostre que, se p e p  q são tautologias, então q é tautologia. Sugestão: Supor que q não seja tautologia.

10. Mostre que:

1. q implica logicamente p  q.

2. q implica logicamente p  q  p.

3. p   q não implica logicamente p  q.

4. p não implica logicamente p  q.

5. p  q não implica logicamente p.

11. Mostrar que: ((x = y  x < 4 )  x  4 )  x = y

12. Mostrar que: ((x  0  x = y)  x  y)  x = 0

13. Mostre que as proposições p e q são equivalentes em cada um dos seguintes casos:

1. p: 2+6=8 q: (2+6) 2=64

2. p: sen = 1 q: cos = 0

3. p: 30 = 1 q:  < 4

4. p: x é ímpar q: x+2 é ímpar .

5. p: a  b q: b  a

6. p: a || b q: b || a

7. p: O triângulo ABC é retângulo em A q: 2 = 2 + 2

14. Exprimir a bicondicional p  q em função dos conectivos lógicos ,  e .

15. Mostre mediante tabela-verdade as seguintes equivalências lógicas:

1. p  (p  q)  p 2. p  (p  q)  p

3. (q  (p  q))  (p  q) 4. ((p  q)  (p  r))  (p  (q  r))

5. ((p  q)  (p  r))  (p  (q  r)) 6. (p  (p  q))  (p  q)

16. Mostre que as proposições: x = 5  x  3 e  (x < 3  x = 5) não são equivalentes.

17. Prove que os três conectivos ,  e  podemos escrever em função do conectivo  do seguinte modo:

1.  p  (p  p) 2. p  q  (p  q)  ( p  q)

3. p  q  (p  p)  (q  q)

18. Prove que os três conectivos ,  e  podemos escrever em função do conectivo  do seguinte modo:

1.  p  (p  p) 2. p  q  (p  p )  (q  q )

3. p  q  (p  q)  (p  q)

19. Determine a negação lógica das seguintes proposições:

1. Estudo lógica, ou esta prova é fácil.

2. Não estudo lógica, e esta prova não é fácil.

3. Se você se comportar bem então, levo você ao circo.

4. Se você não se comportar bem então, não levo você ao circo.

5. Se você se comportar bem então, não levo você ao circo.

6. Se comporte bem e não levo você ao circo.

7. 3 < x

8. “ser branco”

20. Resolva o seguinte enigma:

Um viajante pede a mão da filha do sultão. Para tê-la o sultão diz ao viajante:

“Destas cinco escravas, você tem que deduzir a cor dos olhos da segunda e da terceira. As cinco terão os olhos vendados de forma que você não seja capaz de vê-las. Três têm olhos verdes, duas têm olhos azuis”.

“As de olhos verdes sempre mentem, as de olhos azuis sempre dizem a verdade. Você pode fazer somente três perguntas para elas”.

“Ah! esqueci, se você comete um engano, você morrerá por sua insolência”.

Viajante : De que cor são seus olhos?

Escrava 1: bla, bla, bla . . . (responde em um idioma incompreensível para ele)

Viajante : Que falou tua companheira?

Escrava 2: Ela falou que tem olhos verdes.

Viajante : Que falhou a primeira e de que cor são os olhos da segunda?

Escrava 3: A primeira diz ter olho azul, e a segunda tem olho verde.

Conclusão : O viajante caso com a princesa.

21. Tenho três pares de sapatos: S1, S2 e S3; um par preto, um par é marrom e o outro é branco, não necessariamente nesta ordem. Somente uma das afirmações é verdadeira: i) S1 é preto; ii) S2 não é preto; iii) S3 não é branco.

Quais as cores dos sapatos S1, S2 e S3 nessa ordem?