Apostila Logica para Computacao 20200206-1238

2020
Apostila de Lógica
para Computação
Lógica Matemática
Professor Erlon Pinheiro

Lógica para computação 1
Linguagem Natural x Linguagem Lógica
Linguagem natural é qualquer linguagem que os seres humanos aprendem em seu ambiente
de vida e comunicação com outros seres humanos, como é o caso do português.
Cabe não nos esquecermos de que a linguagem natural é vaga, ambígua e imprecisa,
sendo adequada para a poesia, literatura e folclore, mas não para a ciência e a tecnologia.
Linguagem artificial/formal/simbólica é a linguagem construída para fins específicos, como

as linguagens de programação e os diversos cálculos da Lógica e da Matemática.
Linguagens artificiais exprimem com correção e exatidão o pensamento e os resultados do

conhecimento científico, de forma sintética.
Exemplo:
O produto de um número pela soma de dois outros é igual ao produto do primeiro pelo segundo
somado ao produto do primeiro pelo terceiro.
Simbolicamente temos:
Se X,Y,Z são números arbitrários,

x . (y + z) = x .y + x . z
Proposições
Conjunto de palavras ou símbolos que exprimem um pensamento de sentido completo. São

expressões a respeito das quais tem sentido dizer que são verdadeiras ou falsas.
Exemplo:
(a) A Lua é um satélite da Terra
(b) Recife é a capital de Pernambuco
(c) 4 > 3
A lógica matemática adota como regras fundamentais do pensamento os dois seguintes

axiomas:
(I) Princípio da não contradição: uma proposição não pode ser verdadeira e falsa ao
mesmo tempo.
(II) Princípio do terceiro excluído: toda a proposição ou é verdadeira ou é falsa, isto é,
verifica-se sempre um destes casos e nunca um terceiro.
Valores lógicos das proposições: Chama-se valor lógico de uma proposição a verdade (V)
se ela é verdadeira e a falsidade (F) se ela é falsa.
Classificação das proposições:
a) Simples ou atômica: é aquela proposição que não contem nenhuma outra proposição
como parte integrante de si. São designadas por letras minúsculas.
p: Carlos é careca
q: Pedro é estudante
r: Mônica é jovem
b) Composta ou molecular: é aquela formada pela combinação de duas ou mais

proposições. São designadas por letras maiúsculas.
P: Carlos é careca e Pedro é estudante

Q: Carlos é careca ou Pedro é estudante
R: Se Carlos é careca, então é infeliz.
Conectivos:
São palavras (e, ou, não, se... então, se e somente se...) que possibilitam formar novas
proposições a partir de outras proposições.
Tabela-verdade:
Segundo do Princípio do terceiro excluído, toda proposição simples p é verdadeira ou falsa.
Em se tratando de uma proposição composta, a determinação do seu valor se faz com base no
seguinte princípio:
O valor lógico de qualquer proposição composta depende unicamente dos valores

lógicos das proposições simples componentes, ficando por eles univocamente
determinado.
Exemplo: Considere uma proposição composta cujas proposições simples são p e q. Os

valores lógicos possíveis são:
p q
V V
V F
F V
F F
Exemplo: Considere uma proposição composta cujas proposições simples são p, q e r. Os

valores lógicos possíveis são:
p q r
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F
Notação:
V(p) = V assim p é verdadeira

V(p) = F assim p é falsa
Operações lógicas sobre proposições:
a) Negação: Chame-se a negação de uma proposição p a proposição representada por “não

p”, cujo valor lógico é verdade quando p é falsa e é falsidade quando p é verdadeira. Assim
“não p” tem o valor oposto de p.
p ~p
V F
F V
Ou seja:
~V = F
~F = V
V(~p) = ~V(p)
Exemplos:
p: O Sol é uma estrela

~p: O Sol não é uma estrela
q: Carlos é mecânico
~q: Carlos não é mecânico
~q: Não é verdade que Carlos é mecânico
~q: É falso que Carlos é mecânico
r: 2 + 3 = 5
~r: 2 + 3  5
b) Conjunção: Chame-se conjunção de duas proposições p e q a proposição representada

por “p e q”, cujo valor lógico é verdade quando p e q são verdadeiras e é falsidade nos
demais casos.
p q pq
V V V
V F F
F V F
F F F
Ou seja:
VV=V
VF=F
FV=F
FF=F
V(p  q) = V(p)  V(q)
Exemplos:
1.
p: A neve é branca
q: 2 < 5
p  q: A neve é branca e 2 < 5

V(p  q) = V(p)  V(q) = V  V = V
2.
p: O enxofre é verde
q: 7 é um número primo
p  q: O enxofre é verde e 7 é um número primo

V(p  q) = V(p)  V(q) = F  V = F
c) Disjunção: Chame-se disjunção de duas proposições p e q a proposição representada por

“p ou q”, cujo valor lógico é verdade quando ao menos uma das proposições p e q é
verdadeira e é falsidade quando p e q são falsas.
p q pq
V V V
V F V
F V V
F F F
Ou seja:
VV=V
VF=V
FV=V
FF=F
V(p  q) = V(p)  V(q)
Exemplos:
1.
p: A neve é branca
q: 2 < 5
p  q: A neve é branca ou 2 < 5

V(p  q) = V(p)  V(q) = V  V = V
2.
p  q: O enxofre é verde ou 7 é um número primo

V(p  q) = V(p)  V(q) = F  V = V
d) Disjunção exclusiva: Chame-se disjunção exclusiva de duas proposições p e q a

proposição representada por “ou p ou q”, cujo valor lógico é verdade quando p é verdadeira
ou q é verdadeira, mas não ambas; e é falsidade quando p e q são ambas verdadeiras ou
ambas falsas.
p q pq
V V F
V F V
F V V
F F F
Ou seja:
VV=F
VF=V
FV=V
FF=F
V(p  q) = V(p)  V(q)
Exemplos:
P: Carlos é médico ou professor (disjunção inclusiva)
Q: Mário é alagoano ou Gaúcho (disjunção exclusiva)
e) Condicional: Chame-se condicional uma proposição representada por “se p então q”, cujo
valor lógico é falsidade quando p é verdadeira e q é falsa; e é verdade nos demais casos.
p q pq
V V V
V F F
F V V
F F V
Ou seja:
VV=V
VF=F
FV=V
FF=V
V(p  q) = V(p)  V(q)
Uma condicional p  q não afirma que o conseqüente q se deduz ou é conseqüência do

antecedente p, o que uma condicional afirma é unicamente uma relação entre os valores
lógicos do antecedente e do conseqüente de acordo com uma tabela-verdade.
Exemplos:
1.
p: A neve é branca
q: 2 < 5
p  q: Se a neve é branca, então 2 < 5

V(p  q) = V(p)  V(q) = V  V = V
2.
p  q: Se o enxofre é verde, então 7 é um número primo

V(p  q) = V(p)  V(q) = F  V = V
f) Bicondicional: Chame-se bicondicional uma proposição representada por “p se e somente

se q”, cujo valor lógico é verdade quando p e q são ambas verdadeiras ou ambas falsa, e é
falsidade nos demais casos.
p q pq
V V V
V F F
F V F
F F V
Ou seja:
VV=V
VF=F
FV=F
FF=V
V(p  q) = V(p)  V(q)
Exemplos:
1.
p: A neve é branca
q: 2 < 5
p  q: A neve é branca se e somente se 2 < 5

V(p  q) = V(p)  V(q) = V  V = V
2.
p  q: O enxofre é verde se e somente se 7 é um número primo

V(p  q) = V(p)  V(q) = F  V = F
Construção de Tabelas-Verdade
Dadas várias proposições simples, podemos combiná-las pelos conectivos e construir

proposições compostas.
Com o emprego das tabelas-verdade das operações lógicas fundamentais é possível

construir a tabela-verdade correspondente a qualquer proposição composta.
Número de linhas de uma tabela-verdade: A tabela-verdade de uma proposição

composta com n proposições simples contém 2n linhas.
Exemplo:
Construir a tabela-verdade da proposição: P(p, q) = ~(p  ~q)
1a Solução
1. Forma-se o par de colunas correspondente às duas proposições simples;

2. Forma-se a coluna para o ~q;
3. Forma-se a coluna para p  ~q;
4. Forma-se a coluna para ~(p  ~q).
p q ~q p  ~q ~(p  ~q)
V V F F V
V F V V F
F V F F V
F F V F V
2a Solução (Não utilizaremos nesta disciplina)
1. Forma-se o par de colunas correspondente às duas proposições simples;

2. Traça-se uma coluna para cada uma das proposições e conectivos.
3. Completam-se essas colunas numa certa ordem;
4. O resultado está na coluna completada em último lugar.
p q ~ (p  ~ q)
V V V V F F V
V F F V V V F
F V V F F F V
F F V F F V F
4 1 3 2 1
3a Solução
1. Traça-se uma coluna para cada uma das proposições e conectivos.

2. Completam-se essas colunas numa certa ordem;
3. O resultado está na coluna completada em último lugar.
~ (p  ~ q)
V V F F V
F V V V F
V F F F V
V F F V F
4 1 3 2 1
Logo: P(VV,VF,FV,FF) = VFVV
Uso de parênteses: É necessário o uso de parênteses na simbolização das proposições para

evitar qualquer tipo de ambigüidade.
Exemplo: p  q  r
(i) Disjunção: (p  q)  r
(ii) Conjunção: p  (q  r)
A ordem de precedência do os conectivos, do mais fraco para o mais forte é:

(i) ~
(ii) e
(iii) 
(iv) 
Valor lógico de uma proposição composta: Dada uma proposição composta P(p, q, r, ...),
pode-se sempre determinar o seu valo lógico quando são dados ou conhecidos os valores
lógicos respectivos das proposições simples.
Exemplos:
1. Sabendo que os valores lógicos das proposições p e q são respectivamente V e F,
determinar o valor lógico da proposição: P( p, q ) = ~(p  q)  ~p  ~q
V(P) = ~(V  F)  ~V  ~F = ~V  F  V = F  F = V
2. Sejam as proposições p:  = 3 e q: sen (/2) = 0, determine o valor lógico da proposição:

P(q,p) = (p  q)  (p  p  q)
V(p) = F e V(q) = F
V(P) = (F  F)  (F  F  F) = V  (F  F) = V  V = V
Tautologia
Chama-se tautologia toda a proposição composta cujo o valor lógico é sempre V (verdade).
Exemplos:
A proposição p  p é tautológica ?
p p pp
V V V
F F V
A proposição p  p é tautológica ???
p p p p
V V V
F F V
A proposição ~(p  ~p) é tautológica ?
p ~p p  ~p ~(p  ~p)
V F F V
F V F V
Contradição
Chama-se contradição toda a proposição composta cujo valor lógico é sempre F (falsidade).
Logo, P( p, q, r,..) é uma tautologia se e somente se ~P( p, q, r,..) é uma contradição.
Exemplos:
A proposição p  ~p é uma contradição?
p ~p p  ~p
V F F
F V F
A proposição p  ~p é uma contradição?
p ~p p  ~p
V F F
F V F
A proposição (p  q)  ~(p  q) é uma contradição?
p q pq pq ~(p  q) (p  q)  ~(p  q)

V V V V F F
V F F V F F
F V F V F F
F F F F V F
A proposição ~p  (p  ~q) é uma contradição ???
p q ~p ~q (p  ~q) ~p  (p  ~q)
V V F F F F
V F F V V F
F V V F F F
F F V V F F
Contingência
Chama-se contingência toda a proposição composta que não é tautologia nem contradição.
Exemplos:
A proposição p  ~p é uma contingência?
p ~p p  ~p
V F F
F V V
A proposição p  q  p é uma contingência?
p q pq pq p
V V V V
V F V V
F V V F
F F F V
A proposição x = 3  (x  y  x  3) é uma contingência? Primeiro será obrigatório a

conversão para linguagem simbólica da seguinte forma: p: x = 3; q: x = y; note que o deve ser
traduzido de forma que x  y = ~q!
p q ~p ~q ~q  ~p p  (~q  ~p)
V V F F V V
V F F V F F
F V V F V F
F F V V V F
Princípio da Substituição para as Tautologias
Seja P( p, q, r, ...) uma tautologia e sejam P0(p,q,r,...) , Q0(p,q,r,...) , R0(p,q,r,...) , ... proposições
quaisquer.
Se P( p, q, r, ...) é uma tautologia, então P(P0, Q0, R0, ...) também é uma tautologia, quaisquer
que sejam as proposições P0, Q0, R0,...
Isto significa que se trocarmos uma proposição simples de em uma tautologia a mesma
continuará sendo tautológica. Exemplo: P(p): p  ~p é tautológica. Se substituirmos o p por
qualquer proposição composta, digamos: p  q, a proposição composta resultante
P( p, q): (p  q ) ~(p  q) continua sendo uma tautologia. Fica como exercício verificar tal
fato.
Implicação Lógica
Diz-se que uma proposição P( p, q, r,...) implica logicamente (ou abreviadamente, implica) uma
proposição Q( p, q, r, ...), se Q é verdadeira todas as vezes que P é verdadeira.
Notação:
P( p, q, r, ...)  Q( p, q, r, ...)
Exemplos:
1) p  q  p  q
p q pq pq
V V V V
V F F V
F V F V
F F F F
Podemos também afirmar:
(i) p  p  q e q  p  q (Adição)
(ii) p  q  p e p  q  q (Simplificação)
2) (p  q)  ~p  q (Silogismo disjuntivo)
p q pq ~p (p  q)  ~p
V V V F F
V F V F F
F V V V V
F F F V F
3) (p  q)  p  q (Modus ponens)
p q pq (p  q)  p
V V V V
V F F F
F V V F
F F V F
4) (p  q)  ~q  ~p (Modus tollens)
p q ~q ~p pq (p  q)  ~q
V V F F V F
V F V F F F
F V F V V F
F F V V V V
Tautologias e Implicação Lógica
P( p, q, r, ...)  Q( p, q, r, ...) se e somente se a condicional P( p, q, r, ...)  Q( p, q, r, ...) é

uma tautologia.
Demonstração:
Se P( p, q, r, ...)  Q( p, q, r, ...) então não ocorre em nenhum momento que V(P) = V e V(Q) =
F simultaneamente, portanto a condicional P( p, q, r, ...) Q( p, q, r, ...) é uma tautologia.
Se P( p, q, r, ...) Q( p, q, r, ...) é uma tautologia não ocorre em nenhum momento V(P) = V e

V(Q) = F simultaneamente, e portanto P( p, q, r, ...)  Q( p, q, r, ...).
Exemplos:
1) p  ~p  q
p q ~p p  ~p p  ~p  q
V V F F V
V F F F V
F V V F V
F F V F V
Podemos afirmar que p  ~p  q é tautológica, logo subsiste a implicação lógica p  ~p  q.
2) (p  q)  p  q
p q pq (p  q)  p (p  q)  p  q
V V V V V
V F F F V
F V F F V
F F V F V
Podemos afirmar que (p  q)  p  q é tautológica, logo subsiste a implicação lógica (p  q)

 p  q.
Propriedades da Implicação Lógica
 Reflexiva:
P( p, q, r, ...)  P( p, q, r, ...)
 Transitiva:
Se P( p, q, r, ...)  Q( p, q, r, ...) e Q( p, q, r, ...)  R( p, q, r, ...) então P( p, q, r, ...)  R( p,

q, r, ...)
Equivalência Lógica
Diz-se que uma proposição P( p, q, r, ...) é logicamente equivalente (ou abreviadamente,

equivalente) a proposição Q( p, q, r, ...), se a tabela verdade dessas duas proposições são
idênticas.
Notação:
P( p, q, r, ...)  Q( p, q, r, ...)
Ficará claro mais tarde que, em certas circunstâncias, é necessário “transformar” uma
proposição composta em outra proposição. Isto é feito substituindo uma proposição composta
(em uma proposição composta) por outra proposição composta equivalente. Este processo é
repetido até que a forma desejada para a proposição composta seja obtida.
Exemplo:
1) p  (p  q)  p
p q pq p  (p  q)
V V V V
V F V V
F V V F
F F F F
2) (p  q)  p  p  q?
p q pq (p  q)  p
V V V V
V F F F
F V F F
F F V F
Tautologias e Equivalência Lógica
P( p, q, r, ...)  Q( p, q, r, ...) se e somente se a bicondicional P( p, q, r, ...)  Q( p, q, r, ...) é

uma tautologia.
Demonstração:
Se P( p, q, r, ...) e Q( p, q, r, ...) são equivalentes suas tabelas verdades são idênticas, portanto
o valor lógico da bicondicional é sempre verdade (tautológico).
Se a bicondicional é tautológica (somente verdade) os valores lógicos de P( p, q, r, ...) e Q( p,

q, r, ...) são sempre idênticos, isto é, P( p, q, r, ...) e Q( p, q, r, ...) são equivalentes.
Exemplos:
1) (p  q  r)  (p  (q  r))
(p  q  r)  (p  (q  r))
V V V V V V V V V V V
V V V F F V V F V F F
V F F V V V V V F V V
V F F V F V V V F V F
F F V V V V F V V V V
F F V V F V F V V F F
F F F V V V F V F V V
F F F V F V F V F V F
1 2 1 3 1 4 1 3 1 2 1
2) (x = 1  x < 3)  ~(x < 3  x = 1) É falso !!!
(x = 1  x < 3)  ~ (x < 3  x = 1)
V V F F F V V V
V V V V V F F V
F F F F V V F F
F V V V V F F F
1 3 2 5 4 2 3 1
Propriedades da Equivalência Lógica
 Reflexiva:
P( p, q, r, ...)  P( p, q, r, ...)
 Transitiva:
Se P( p, q, r, ...)  Q( p, q, r, ...) e Q( p, q, r, ...)  R( p, q, r, ...) então P( p, q, r, ...)  R( p,

q, r, ...)
 Simétrica:
Se P( p, q, r, ...)  Q( p, q, r, ...) então Q( p, q, r, ...)  P( p, q, r, ...)
Proposições associadas a uma condicional
Dada a condicional p  q, chama-se proposições associadas a p  q as três seguintes

proposições condicionais que contêm p e q:
 Proposição recíproca de p  q : q  p
 Proposição contrária de p  q : ~p  ~q
 Proposição contrapositiva de p  q : ~q  ~p
p q pq qp ~p  ~q ~q  ~p
V V V V V V
V F F V V F
F V V F F V
F F V V V V
Podemos afirmar que:
(i) A condicional p  q e sua contrapositiva ~q  ~p são equivalentes;

(ii) A recíproca q  p e a contrária ~p  ~q da condicional p  q são equivalentes.
Negação conjunta de duas proposições
Chama-se negação conjunta de duas proposições p e q a proposição “não p e não q”, isto é,
simbolicamente ~p ~q.
A negação conjunta de duas preposições pode ser indicada por p  q.
Logo: p  q  ~p ~q
p q pq
V V F
V F F
F V F
F F V
Negação disjunta de duas proposições
Chama-se negação disjunta de duas proposições p e q a proposição “não p ou não q”, isto é,
simbolicamente ~p ~q.
A negação disjunta de duas preposições pode ser indicada por p  q.
Logo: p  q  ~p ~q
p q pq
V V F
V F V
F V V
F F V
Álgebra das proposições
Propriedades da conjunção:
(a) Idempotente: p  p  p
p pp ppp
V V V
F F V
Exemplo: x  1  x  1  x  1
(b) Comutativa: p  q  q  p
p q pq qp pqqp

V V V V V
V F F F V
F V F F V
F F F F V
Exemplo: x  1  x  0  x  0  x  1
(c) Associativa: (p  q)  r  p  (q  r)
p q r pq qr (p  q)  r p  (q  r)
V V V V V V V
V V F V F F F
V F V F F F F
V F F F F F F
F V V F V F F
F V F F F F F
F F V F F F F
F F F F F F F
Exemplo: (x  1  x  0)  y  1  x  1  (x  0  y  1)
(d) Identidade: p  t  p e p  c  c, para t elemento neutro e c elemento absorvente.
p t c pt pc pt  p pc  c

V V F V F V V
F V F F F V V
Exemplo: x  1  |x|  0  x  1
x  1  |x|  0  |x|  0
Propriedades da disjunção:
(a) Idempotente: p  p  p
p pp ppp
V V V
F F V
Exemplo: x  1  x  1  x  1
(b) Comutativa: p  q  q  p
p q pq qp pqqp

V V V V V
V F V V V
F V V V V
F F F F V
Exemplo: x  1  x  0  x  0  x  1
(c) Associativa: (p  q)  r  p  (q  r)
p q r pq qr (p  q)  r p  (q  r)
V V V V V V V
V V F V V V V
V F V V V V V
V F F V F V V
F V V V V V V
F V F V V V V
F F V F V V V
F F F F F F F
Exemplo: (x  1  x  0)  y  1  x  1  (x  0  y  1)
(d) Identidade: p  t  t e p  c  p, para t elemento absorvente e c elemento neutro.
p t c p t p c p t  t p c  p
V V F V V V V
F V F V F V V
Exemplo: x  1  |x|  0  |x|  0

x  1  |x|  0  x  1
Propriedades da conjunção e da disjunção:
(a) Distributivas:
(i) p  (q  r)  (p  q)  (p  r)
p q r pq qr pr p  (q  r) (p  q)  (p  r)

V V V V V V V V
V V F V V F V V
V F V F V V V V
V F F F F F F F
F V V F V F F F
F V F F V F F F
F F V F V F F F
F F F F F F F F
(ii) p  (q  r)  (p  q)  (p  r)
p q r qr pq pr p  (q  r) (p  q)  (p  r)

V V V V V V V V
V V F F V V V V
V F V F V V V V
V F F F V V V V
F V V V V V V V
F V F F V F F F
F F V F F V F F
F F F F F F F F
Exemplo:
(i) “Carlos estuda e Jorge ouve música ou lê”, é equivalente à seguinte proposição:
“Carlos estuda e Jorge ouve música ou Carlos estuda e Jorge lê”.
(ii) “Chove ou faz vento e frio”, é equivalente a seguinte proposição: “Chove ou faz
vento e Chove ou faz frio”.
(b) Absorção:
(i) p  (p  q)  p
p q pq p  (p  q) p  (p  q)  p
V V V V V
V F V V V
F V V F V
F F F F V
(ii) p  (p  q)  p
p q pq p  (p  q) p  (p  q)  p
V V V V V
V F F V V
F V F F V
F F F F V
(c) Regras de Morgan:

(i) ~(p  q)  ~p  ~q
p q pq ~(p  q) ~p  ~q
V V V F F
V F F V V
F V F V V
F F F V V
(ii) ~(p  q)  ~p  ~q
p q pq ~(p  q) ~p  ~q
V V V F F
V F V F F
F V V F F
F F F V V
Negação da condicional:
(a) ~(p  q)  p  ~q
p q pq ~(p  q) p  ~q
V V V F F
V F F V V
F V V F F
F F V F F
Nota: A condicional p  q não é idempotente, comutativa e associativa, pois, as tabelas das
proposições p  p e p, p  q e q  p, (p  q)  r e p  (q  r) não são idênticas.
Negação da bicondicional:
(a) ~(p  q)  (p  ~q)  (~p  q)
p q ~(p  q) (p  ~q) (~p  q) (p  ~q)  (~p  q)

V V F F F F
V F V V F V
F V V F V V
F F F F F F
(b) ~(p  q)  p  ~q  ~p  q
p q ~(p  q) p  ~q ~p  q
V V F F F
V F V V V
F V V V V
F F F F F
Nota: A bicondicional p  p não é idempotente, pois, é imediato que não são idênticas as
tabelas de p  p e p, mas é comutativa e associativa.
Resumo das equivalências mais usadas:
No Equivalência
1 p  q  (p  q)  (q  p)
2 p  q  ~p  q
3 pqqp
4 pqqp
5 (p  q)  r  p  (q  r)
6 (p  q)  r  p  (q  r)
7 p  (q  r)  (p  q)  (p  r)
8 p  (q  r)  (p  q)  (p  r)
9 pt  p t=Tautologia
10 p c  p c=Contradição
11 pc  c c=Contradição
12 p t  t t=Tautologia
13 p  ~p  t t=Tautologia
14 p  ~p  c c=Contradição
15 ~~p  p
16 ~(p  q)  ~p  ~q
17 ~(p  q)  ~p  ~q
18 p  (p  q)  p
19 p  (p  q)  p
20 ~(p  q)  p  ~q
21 ~(p  q)  (p  ~q)  (~p  q)
22 ~(p  q)  p  ~q  ~p  q
23 ppp Idempotência do e
24 ppp Idempotência do ou
25 p ↓ q  ~p  ~q Negação conjunta
26 p ↑ q  ~p  ~q Negação disjunta
27 ~pp↑p
28 ~pp↓p
29 p  q  ~q ~p Contrapositiva
30 p  q  ~(p  q)
31 ~t  c Negação da Tautologia
32 ~c  t Negação da Contradição
Método dedutivo
Todas as implicações e equivalências foram demonstradas até então por tabelas verdades.
Vamos usar um método mais eficiente chamado método dedutivo, que utiliza as equivalências
lógicas apresentadas anteriormente.
Exemplos:
Demonstre as implicações usando o método dedutivo e o teorema das implicações x tautologia.
1) c  p, onde c é uma proposição cujo valor lógico é sempre falsidade.
Sabemos que c  p se somente se c  p é uma tautologia, portanto, temos que provar que c
 p é uma tautologia. Considere t uma proposição cujo valor lógico é sempre verdade.
c  p  ~c  p  t  p  t Passos 2, 12
2) p  t, onde t é uma proposição cujo valor lógico é sempre verdade.
Sabemos que p  t se somente se p  t é uma tautologia, portanto, temos que provar que p 
t é uma tautologia.
p  t  ~p  t  t Passos 2, 12
3) p  q  p
Sabemos que p  q  p se somente se (p  q)  p é uma tautologia, portanto, temos que

provar que (p  q)  p é uma tautologia. Considere t uma proposição cujo valor lógico é
sempre verdade.
(p  q)  p  ~(p  q)  p  (~p  ~q)  p  Passos 2, 16, 6, 4, 6

~p  (~q  p)  ~p  (p  ~q)  (~p  p)  ~q
 t  ~q  t
4) (p  q)  p  q
Sabemos que (p  q)  p  q se somente se ((p  q)  p)  q é uma tautologia, portanto,

temos que provar que ((p  q)  p)  q é uma tautologia. Considere t uma proposição cujo
valor lógico é sempre verdade e c uma proposição cujo valor lógico é sempre falsidade.
((p  q)  p)  q  ~((p  q)  p)  q  Passos 2, 2, 7, 10, 16,

~((~p  q)  p)  q  ~(p  (~p  q))  q  6
~((p  ~p)  (p  q))  q  ~(c  (p  q))  q 
~(p  q)  q  (~p  ~q)  q  ~p  (~q  q) 
~p  t  t
5) (p  q)  ~q  ~p
Sabemos que (p  q)  p  q se somente se ((p  q)  ~q)  ~p é uma tautologia, portanto,

temos que provar que ((p  q)  ~q)  ~p é uma tautologia. Considere t uma proposição cujo
((p  q)  ~q)  ~p  ((~p  q)  ~q)  ~p  Passos 2, 2, 7, 10,

~((~p  q)  ~q)  ~p  ~(~q  (~p  q))  ~p  ~((~q ~p)  (~q  16, 15, 6
q))  ~p  ~((~q ~p)  c)  ~p  ~(~q ~p)  ~p  (~~q  ~~p) 
~p  (q  p)  ~p  q  (p  ~p)  q  t  t
6) (p  q)  ~p  q
Sabemos que (p  q)  ~p  q se somente se ((p  q)  ~p)  q é uma tautologia, portanto,

temos que provar que ((p  q)  ~p)  q é uma tautologia. Considere t uma proposição cujo
((p  q)  ~p)  q  ~((p  q)  ~p)  q  Passos 2, 7, 10, 16,

~(~p  (p  q))  q  ~((~p  p)  (~p  q))  q  6
~(c  (~p  q))  q  ~(~p  q)  q 
(~~p  ~q)  q  (p  ~q)  q  p  (~q  q) 
ptt
Exemplos:
Demonstre as equivalências usando o método dedutivo e o teorema das equivalências x
tautologia.
1) p  q  p  ~q  c
Sabemos que p  q  p  ~q  c se somente se (p  q)  (p  ~q  c) é uma tautologia,

portanto, temos que provar que (p  q)  (p  ~q  c) é uma tautologia. Considere t uma
proposição cujo valor lógico é sempre verdade e c uma proposição cujo valor lógico é sempre
falsidade.
(p  q)  (p  ~q  c)  (~p  q)  (~(p  ~q)  c)  (~p  q)  ~(p Passos 2,10, 16, 15

 ~q)  (~p  q)  (~p  ~~q) 
(~p  q)  (~p  q)  t
2) p  q  p  q  q
Sabemos que p  q  p  q  q se somente se (p  q)  (p  q  q) é uma tautologia,

portanto, temos que provar que (p  q)  (p  q  q) é uma tautologia. Considere t uma
proposição cujo valor lógico é sempre verdade e c uma proposição cujo valor lógico é sempre
falsidade.
(p  q)  (p  q  q)  (~p  q)  (~(p  q)  q)  (~p  q)  ((~p  Passos 2, 17, 8,

~q)  q) (~p  q)  (q  (~p  ~q))  (~p  q)  ((q  ~p)  (q  ~q)) 13, 9

(~p  q)  ((q  ~p)  t)  (~p  q)  (q  ~p) 
(~p  q)  (~p  q)  t
Redução do número de conectivos
Entre os 5 conectivos fundamentais (~, , , , ), 3 exprimem-se em termos de apenas 2:

(i) , ,  exprimem-se em termos de ~, 
(ii) , ,  exprimem-se em termos de ~, 
(iii) , ,  exprimem-se em termos de ~, 
Exemplos:
(i)
p  q  ~~p  ~~q  ~(~p  ~q)
p  q  ~p  q
p  q  (p  q)  (q  p)  ~(~(~p  q)  ~(~q  p))
(ii)
p  q  ~~p  ~~q  ~(~p  ~q)
p  q  ~p  q  ~(p  ~q)
p  q  (p  q)  (q  p)  ~(p  ~q)  ~(~p  q)
(iii)
p  q  ~(~p  ~q)  ~(p  ~q)
p  q  ~~p  ~~q  ~p  q
p  q  (p  q)  (q  p)  ~((p  q)  ~(q  p))
Forma Normal das Proposições
Diz-se que uma proposição está na forma normal (FN) se e somente se, quando muito, contém
os conectivos ~,  e .
Exemplos:
(i) ~p  ~q
(ii) ~(~p  ~q)
(iii) (p  q)  (~q  r)
Forma normal conjuntiva
Diz-se que uma proposição está na forma normal conjuntiva (FNC) se e somente se são
verificadas as seguintes condições:
1. Contém, quando muito, os conectivos ~,  e ;

2. ~ não aparece repetido (como ~~p) e não tem alcance sobre  e  (como ~(p  q) ou ~(p
 q));
3.  não tem alcance sobre  (isto é, não há componentes do tipo p  (q  r)).
Exemplos:
(i) ~p  ~q
(ii) ~p  q  r
(iii) (~p  q)  (~q  ~r)
Para toda proposição pode-se determinar a FNC equivalente, mediante as seguintes

transformações:
1. Eliminando os conectivos  e  mediante a substituição de p  q por ~p  q e de p 

q por (~p  q)  (p  ~q);
2. Eliminando ~~ e parêntesis precedidos de ~ pelas regras da “Dupla negação” e “Morgan”;
4. Substituindo p  (q  r) pela a sua equivalente pela regra de “Distribuição”.
Exemplos:
Determinar a FNC da proposição ~(((p  q)  ~q)  (q  r))
~((p  q)  ~q)  ~(q  r))  (~(p  q)  ~~q)  (~q  ~r)) 

(~p  ~q)  q)  (~q  ~r))  (~p  q)  (~q  q)  (~q  ~r) 
(~p  q)  (~q  ~r)
Faça você:
1. Determinar a FNC da proposição (p  q)  (~q  ~p).
2. Determinar a FNC da proposição p  q  ~r.
Forma normal disjuntiva
Diz-se que uma proposição está na forma normal disjuntiva (FND) se e somente se são
verificadas as seguintes condições:
1. Contém, quando muito, os conectivos ~,  e ;

2. ~ não aparece repetido (como ~~p) e não tem alcance sobre  e  (como ~(p  q) ou ~(p
 q));
3.  não tem alcance sobre  (isto é, não há componentes do tipo p  (q  r)).
Exemplos:
(i) ~p  q
(ii) p  (q  r)
(iii) (p  ~q)  (~p  ~q  r)
Para toda proposição pode-se determinar a FND equivalente, mediante as seguintes

transformações:
1. Eliminando os conectivos  e  mediante a substituição de p  q por ~p  q e de p 

q por (~p  q)  (p  ~q);
2. Eliminando ~~ e parêntesis precedidos de ~ pelas regras da “Dupla negação” e “Morgan”;
3. Substituindo p  (q  r) pela a sua equivalente pela regra de “Distribuição”.
Exemplos:
Determinar a FND da proposição (p  q)  (q  p).
(~p  q)  (~q  p)  ((~p  q)  ~q)  ((~p  q)  p) 

(~p  ~q)  (q  ~q)  (~p  p)  (q  p)  (~p  ~q)  c  c  (q  p)
 (~p  ~q)  (q  p) - Onde c é uma contradição
Faça você:
1. Determinar a FND da proposição ~(((p  q)  ~q)  (q  r))
Princípio de Dualidade
Seja P uma proposição que só contém os conectivos ~,  e . A proposição que resulta de P

trocando cada símbolo  por  e cada símbolo  por  chama-se dual.
Teorema: Se P e Q são proposições equivalentes que só contêm conectivos ~,  e , então as

suas duais P1 e Q1 também são equivalentes.
Exercícios de fixação: Pág. 86 do livro texto – Exercícios 7 e 8
Argumentos
Sejam P1, P2,..., Pn (n >= 1) e Q proposições quaisquer, simples ou composta.
Chama-se argumento toda a afirmação de que uma dada seqüência finita de proposições P1,
P2,..., Pn (n >= 1) tem como conseqüência uma proposição final Q.
Notação: P1, P2,..., Pn | Q
As proposições P1, P2,..., Pn são ditas premissas do argumento.

A proposição Q é dita conclusão do argumento.
Podemos ler o argumento de uma das formas abaixo:
(i) P1, P2,..., Pn tem como conseqüência Q

(ii) P1, P2,..., Pn acarretam Q
(iii) Q decorre de P1, P2,..., Pn
(iv) Q se deduz de P1, P2,..., Pn
(v) Q se infere de P1, P2,..., Pn
Um argumento P1, P2,..., Pn | Q é válido se e somente se a conclusão Q é verdadeira todas

as vezes que as premissas P1, P2,..., Pn são verdadeiras. Afirmar que um dado argumento é
válido significa afirmar que as premissas estão de tal modo relacionadas com a conclusão que
não é possível ter uma conclusão falsa se as premissas são verdadeiras.
Um argumento não válido é dito um SOFISMA.
Teorema: Um argumento P1, P2,..., Pn | Q é válido se somente se a condicional associada

(P1P2...Pn  Q) é tautológica.
Prova: O argumento P1, P2,..., Pn | Q é válido se somente se Q é verdade sempre que P1,
P2,..., Pn sejam verdadeiras.
Tomando P1, P2,..., Pn como verdadeiras temos que P1P2...Pn é verdadeira.
Logo, podemos dizer que o argumento é válido se somente se Q é verdade sempre que
P1P2...Pn é verdadeira, ou seja, P1P2...Pn  Q.
Sabemos que r  s se e somente se r  s é tautológica. Portanto, P1, P2,..., Pn | Q se

somente se P1P2...Pn  Q é tautológica.
De acordo com o teorema acima, a todo argumento P1, P2,..., Pn | Q corresponde uma
condicional com a estrutura P1P2...Pn  Q. Reciprocamente, a toda condicional
P1P2...Pn  Q corresponde um argumento com a estrutura P1, P2,..., Pn | Q.
Exemplos:
Argumento: p  ~q , p  ~r, q  ~s | ~(r  s)
Condicional associada: (p  ~q)  (p  ~r)  (q  ~s)  ~(r  s)
Condicional associada: (p  q  r)  ~s  (q  r  s)  (s  p  ~q)

Argumento: (p  q  r) , ~s , (q  r  s) | (s  p  ~q)
Exercícios de fixação: Pág. 96 do livro texto – Exercícios 1 e 2
Argumentos válidos e fundamentais
1. Adição (AD):
(i) p | (p  q)
p q pq p  (p  q)
V V V V
V F V V
F V V V
F F F V
(ii) q | (q  p)
2. Simplificação (SIMP):
(i) p  q | p
(ii) p  q | q
3. Conjunção (CONJ):
(i) p , q | p  q
(ii) p , q | q  p
4. Absorção (ABS):
(i) p  q | p  (p  q)
5. Modus Ponens (MP):
(i) (p  q) , p | q
6. Modus Tollens (MT):
(i) (p  q) , ~q | ~p
7. Silogismo Disjuntivo (SD):
(i) (p  q) , ~p | q
(ii) (p  q) , ~q | p
8. Silogismo Hipotético (SH):
(i) (p  q) , (q  r) | (p  r)
9. Dilema Construtivo (DC):
(i) (p  q) , (r  s) , (p  r) | (q  s)
10. Dilema Destrutivo (DD):
(i) (p  q) , (r  s) , (~q  ~s) | (~p  ~r)
Regras de Inferência
Os argumentos fundamentais da lista anterior são usados para fazer inferências, isto é, efetuar
os passos de uma dedução ou demonstração, e por isso são também chamados de Regras de
Inferência. É habitual escreve-los na forma abaixo indicada:
Premissa 1
Premissa 2
...
Premissa n
Conclusão
Exemplos:
1. Adição (AD):
(i) p | (p  q) (ii) q | (q  p)
p____ q____
(p  q) (q  p)
2. Simplificação (SIMP):
(i) p  q | p (ii) p  q | q
pq pq
p q
3. Conjunção (CONJ):
(i) p , q | p  q (ii) p, q | q  p
p p
q___ q___
pq qp
4. Absorção (ABS):
(i) p  q | p  (p  q)
p  q____
p  (p  q)
5. Modus Ponens (MP):

(i) (p  q) , p | q
(p  q)
p_____
q
Exercícios:
Sabendo que um argumento P1, P2,..., Pn | Q é válido se somente se a condicional associada
P1P2...Pn  Q é tautológica, verifique se são válidos os argumentos abaixo:
a) p  q, q | p
p q pq (p  q)  q ((p  q)  q)  p
V V V V V
V F F F V
F V V V F
F F V F V
Logo, o argumento acima não é válido. É um SOFISMA.
b) p  q, q | p
p q pq (p  q)  q ((p  q)  q)  p
V V V V V
V F F F V
F V F F V
F F V F V
Logo, o argumento acima é válido.
c) Se (x = 0) e (y = z) então y > 1, y <= 1 | x  z
Representando os fatos através de proposições temos:

p: x = 0 q: y = z r: y > 1
(p  q)  r, ~r | ~q
p q r (p  q)  r ((p  q)  r) ~r (((p  q)  r) ~r) ~q

V V V V F V
V V F F F V
V F V V F V
V F F V V V
F V V V F V
F V F V V F
F F V V F V
F F F V V V
Logo, o argumento acima não é válido. É um SOFISMA.
Prova de Não-Validade
Para testar a não validade de um argumento, devemos encontrar valores lógicos para cada
uma das proposições simples, que tornem as premissas Verdadeiras e a conclusão Falsa.
Exemplo:
Demonstrar a Não-Validade do argumento:

(p  q)  ~(r  s), p  s | r  q
Demonstração:
Basta encontrar uma interpretação onde as premissas são V e a conclusão F. Sugestão: Inicie
com a conclusão:
Conclusão: V(r  q) = V  F = F
1a Premissa: V( (p  q)  ~(r  s)) = (F  F)  ~(V  V) = V  (F  F) = V

2a Premissa: V(p  s) = F  V = V
Assim, com a seguinte atribuição de valores lógicos às proposições simples, os valores lógicos
das duas premissas são V e o valor lógico da conclusão é F:
V F
r p
s q
Exercícios de fixação: Pág. 110 do livro texto – Exercícios 1 a 5

Validade mediante regras de Inferência
O método de tabelas verdades permite demonstrar a validade de qualquer argumento, mas o

seu emprego torna-se trabalhoso a medida que aumenta o número de proposições simples
componentes do argumento.
Um método mais eficiente neste caso consiste em deduzir a conclusão do argumento a partir
das premissas, usando as regras de inferência.
Exemplos:
1. Verificar que é válido o argumento: (p  q), p  r | q
(1) pq P1
(2) pr P2
----------------
(3) p 2 - SIMP
(4) q 1,3 - MP
2. Verificar que é válido o argumento: p  q, p  r  s | p  s
(1) pq P1
(2) prs P2
----------------
(3) p 1 - SIMP
(4) pr 3 - AD
(5) s 2,4 - MP
(6) ps 3,5 - CONJ
3. Verificar que é válido o argumento: p  (q  r), p  q, p | r
(1) p  (q  r) P1
(2) pq P2
(3) p P3
----------------
(4) qr 1,3 - MP
(5) q 2,3 - MP
(6) r 4,5 - MP
Exercícios de fixação: Pág. 118 do livro texto – Exercícios 5, 6, 8, 10, 15 e 17.
Validade mediante regras de Inferência e Equivalência
Há muitos argumentos cuja validade não se pode demonstrar com o uso exclusivo das dez
regras de inferência dadas anteriormente. Neste caso é necessário recorrer ao princípio da
“Regra de Substituição”.
Regra de Substituição: Uma proposição qualquer P ou apenas parte de P pode ser

substituída por uma proposição equivalente, e a proposição Q que assim se obtém é
equivalente à P.
Exemplos:
1. Demonstrar que é válido o argumento: p  ~q, q | ~p
(1) p  ~q P1
(2) q P2
----------------
(3) ~~q  ~p 1 - CP
(4) q  ~p 3 - DN
(5) ~p 2,4 - MP
2. Demonstrar que é válido o argumento: p  q, r  ~q | p  ~r
(1) pq P1
(2) r  ~q P2
----------------
(3) ~~q  ~r 2 - CP
(4) q  ~r 3 - DN
(5) p  ~r 1,4 - SH
3. Demonstrar que é válido o argumento:

p  (q  r),p  q  s | p  s
(1) p  (q  r) P1
(2) pqs P2
----------------
(3) (p  q)  (p  r) 1 - DIST
(4) (p  q) 3 - SIMP
(5) s 2,4 - MP
(6) ps 5 - AD
Exercícios de fixação: Pág. 141 do livro texto – Exercícios 1 e 3.
Inconsistência
Um argumento se diz inconsistente se as suas premissas não podem ser simultaneamente

verdadeiras.
Exemplo:
1. Demonstrar que as proposições ~(p  ~q), p  ~r e q  r são inconsistentes:
p q r ~q ~r p  ~q ~(p  ~q) p  ~r qr

V V V F F V F V V
V V F F V V F V F
V F V V F V F V V
V F F V V V F V V
F V V F F F V F V
F V F F V F V V F
F F V V F V F F V
F F F V V V F V V
È impossível encontrar uma atribuição de valores Verdade simultâneos às proposições, logo as

proposições são inconsistentes entre si.
Também se pode demonstrar que as 3 proposições são inconsistentes deduzindo de seu

conjunto uma contradição qualquer:
(1) ~(p  ~q) P1

(2) p  ~r P2
(3) qr P3
----------------
(4) ~p  ~~q 1 - DM
(5) ~p  q 4 - DN
(6) q 5 - SIMPL
(7) r 3,6 - MP
(8) ~p 5 - SIMPL
(9) ~r 2,8 - SD
(10) r  ~r 7,9 - CONJ

10 regras de equivalência:
Idempotente (ID) ppp
ppp
Comutativa (COM) pqqp
pqqp
Associativa (ASSOC) (p  q)  r  p  (q  r)
(p  q)  r  p  (q  r)
Distributivas (DIST) p  (q  r)  (p  q)  (p  r)
p  (q  r)  (p  q)  (p  r)
Dupla negação (DN) p  ~~p
Regras de Morgan (DM) ~(p  q)  ~p  ~q
~(p  q)  ~p  ~q
Condicional (COND) p  q  ~p  q
Bicondicional (BICOND) p  q  (p  q)  (q  p)
p  q  (p  q)  (~p  ~q)
Contraposição (CP) p  q  ~q  ~p
Exportação-Importação (EI) p  q  r  p  (q  r)
10 regras de inferência:
Adição (AD) p | (p  q)
p | (q  p)
Simplificação (SIMP) p  q | p
p  q | q
Conjunção (CONJ) p  q | p  q
p  q | q  p
Absorção (ABS) p  q | p  (p  q)
Modus Ponens (MP) (p  q)  p | q
Modus Tollens (MT) (p  q)  ~q | ~p
Silogismo Disjuntivo (SD) (p  q)  ~p | q
(p  q)  ~q | p
Silogismo Hipotético (SH) (p  q)  (q  r) | (p  r)
Dilema Construtivo (DC) (p  q)  (r  s)  (p  r) | (q  s)
Dilema Destrutivo (DD) (p  q)  (r  s)  (~q  ~s) | (~p  ~r)
Demonstração Condicional
Outro método muito útil para demonstrar a validade de um argumento é a “demonstração

condicional”. Esta demonstração só pode ser usada se a conclusão do argumento tem a forma
de uma condicional.
Seja o argumento: P1, P2, P3, ..., Pn | A  B
Sabemos que este argumento é valido se sua condicional associada, (P1  P2  P3  ...  Pn) 
(A  B) é tautológica.
Pela regra de importação, p  q  r  p  (q  r), a condicional associada é equivalente à

(P1  P2  P3  ...  Pn)  A)  B.
Assim, o argumento P1, P2, P3, ..., Pn | A  B é válido se e somente se também é válido o
argumento P1, P2, P3, ..., Pn, A | B.
Exemplo: Usando DC:

Se tivermos o argumento p  q, q  s, t  (r  ~s) | p  t podemos transformá-lo em
p  q, q  s, t  (r  ~s) ,p | t
Dem.:
(1) pq P1
(2) qs P2
(3) t  (r  ~s) P3
(4) p PA-DC
-----------------------
(5) q 1, 4 - MP
(6) (q s) ( s  q) 2 – BICOND
(7) q s 6 - SIMP
(8) s 5, 7 - MP
(9) (t  r)  (t ~s) 3 – DIST
(10) (t ~s) 9 – SIMP
(11) t 10, 8 - SD
Demonstração Indireta
Outro método muito útil para demonstrar a validade de um argumento é a “demonstração

indireta ou demonstração por absurdo”.
Seja o argumento: P1, P2, P3, ..., Pn | Q
Considerando a proposição C uma contradição, podemos substituir Q por ~Q  C, pois

sabemos que:
~Q  C  ~~Q  C  Q  C  Q
Temos então: P1, P2, P3, ..., Pn | ~Q  C
Logo: P1, P2, P3, ..., Pn, ~Q | C
Assim, o argumento P1, P2, P3, ..., Pn | Q é válido se e somente se o argumento P1, P2, P3, ...,
Pn, ~Q | C deduze-se uma contradição.
Exemplos:
1. Demonstrar a validade do argumento p  (q  r), ~r | q  p, usando Demonstração

Condicional.
p  (q  r), ~r, q | p
(1) p  (q  r) P1
(2) ~r P2
(3) q PA – DC
----------------
(4) p  (~q  r) 1 - COND
(5) (p  ~q)  r 4 - ASSOC
(6) p  ~q 2,5 – SD
(7) ~~q 3 – DN
(8) p 6,7 – SD
2. Demonstrar a validade do argumento p  ~q, r  q | ~(p  r), usando Demonstração

Indireta.
p  ~q, r  q, ~~(p  r) | C
(1) p  ~q P1
(2) rq P2
(3) pr PA-DI
----------------
(4) p 3 – SIMP
(5) r 3 – SIMP
(6) ~q 1,4 – MP
(7) q 2,5 – MP
(8) q  ~q 6,7 - CONJ
Exercício Extra: Verificar a validade do argumento:

p  ~qr, r  q~s, ~p v ~tu, ~q~v, ~r ~p | ~(p  r) ((q  v)  x)
Dica: Tente primeiro verificar se o argumento é um sofisma.
Sentenças abertas
Sentenças abertas com uma variável
Chama-se sentença aberta com uma variável em um conjunto A, uma expressão p(x), que
é falsa ou verdadeira todas as vezes que se substitui a variável ”x” por qualquer elemento ”a”
do conjunto A (a  A).
O conjunto A recebe o nome de conjunto universo ou universo ou domínio.
Se a  A é tal que p(a) é uma proposição verdadeira, diz-se que a satisfaz ou verifica p(x).
Uma sentença aberta com uma variável em A também se chama função proposicional com
uma variável em A.
Chama-se conjunto verdade de uma sentença aberta p(x) em um conjunto A, o conjunto de

todos os elementos a  A tais que p(a) é uma proposição verdadeira.
Este conjunto representa-se por Vp. Portanto, simbolicamente temos:
Vp = { x / x  A  p(x) é V} ou
Vp = { x / x  A  p(x)} ou
Vp = { x  A / p(x)}
Obviamente, o conjunto verdade Vp de uma sentença aberta p(x) em A é sempre um

subconjunto do conjunto A(Vp  A).
Exemplos:
1. Seja a sentença aberta “x + 1 > 8” em N (conjunto dos números naturais), o conjunto

verdade é:
Vp = { x / x  N  x + 1 > 8} = {8,9,10,...}  N
p(x) exprime uma condição possível no conjunto N, pois x(Vp  N}

Note que neste caso temos Vp ≠ .
2. Seja a sentença aberta “x + 7 < 5” em N (conjunto dos números naturais), o conjunto

verdade é:
Vp = { x / x  N  x + 7 < 5} =   N
p(x) exprime uma condição impossível no conjunto N, pois x(Vp = }
3. Seja a sentença aberta “x + 5 > 3” em N (conjunto dos números naturais), o conjunto

verdade é:
Vp = { x / x  N  x + 5 > 3} = N  N
p(x) exprime uma condição universal no conjunto N, pois x(Vp = N}
Sentenças abertas com duas variáveis
Chama-se sentença aberta com duas variáveis em A x B, uma expressão p(x,y), que é falsa
ou verdadeira todas as vezes que se substitui as variáveis ”x” e “y”, pelos elementos ”a” e
“b” de qualquer par ordenado do produto cartesiano A x B dos conjuntos A e B ((a,b)  A x B),
respectivamente.
O conjunto A x B recebe o nome de conjunto universo ou universo ou domínio.
Se (a,b)  A x B é tal que p(a,b) é uma proposição verdadeira, diz-se que (a,b) satisfaz ou
verifica p(x,y).
Uma sentença aberta com duas variáveis em A x B também se chama função proposicional
com duas variáveis em A x B.
Chama-se conjunto verdade de uma sentença aberta p(x,y) em um conjunto A x B, o conjunto

de todos os elementos (a,b)  A x B tais que p(a,b) é uma proposição verdadeira.
Vp = { (x,y) / x  A  y  B  p(x,y) é V} ou
Vp = { (x,y)  A x B / p(x,y)}
Obviamente, o conjunto verdade Vp de uma sentença aberta p(x,y) em A x B é sempre um

subconjunto do conjunto A x B(Vp  A x B).
Exemplos:
1. Sejam os conjuntos A={1,2,3,4} e B={1,3,5}, o conjunto verdade da sentença aberta “x < y”

em A x B é:
Vp = { (x,y) / x  A  y  B  x < y} = {(1,3), (1,5), (2,3), (2,5), (3,5), (4,5)}  A x B

p(x,y) exprime uma condição possível em AxB
2. Sejam os conjuntos A={2,3,4,5} e B={3,6,7,10}, o conjunto verdade de inteiros da sentença

aberta “x divide y” em A x B é:
Vp = { (x,y) / x  A  y  B  x | y} = {(2,6), (2,10), (3,3), (3,6), (5,10)}  A x B

p(x,y) exprime uma condição possível em AxB
Sentenças abertas com n variáveis
Chama-se sentença aberta com n variáveis em A1 x A2 x ... An, uma expressão

p(x1,x2,...,xn), que é falsa ou verdadeira todas as vezes que se substitui as variáveis x1, x2, ...,
xn, pelos elementos a1, a2, ..., an pertencentes ao produto cartesiano A1 x A2 x ... An dos
conjuntos A1, A2, ..., An ((a1,a2,...,an)  A1 x A2 x ... An), respectivamente.
O conjunto A1 x A2 x ... An recebe o nome de conjunto universo ou universo ou domínio.
Se (a1,a2,...,an)  A1 x A2 x ... x An é tal que p(a1,a2,...,an) é uma proposição verdadeira, diz-se

que a satisfaz ou verifica p(x1,x2,..,xn).
Uma sentença aberta com n variáveis em A 1 x A2 x ... x An também se chama função

proposicional com n variáveis em A1 x A2 x ... x An.
Chama-se conjunto verdade de uma sentença aberta p(x1,x2,..,xn) em um conjunto A1 x A2 x ...

x An, o conjunto de todos os elementos (a1,a2,...,an)  A1 x A2 x ... x An tais que p(a1,a2,...,an) é
uma proposição verdadeira.
Vp = { (x1,x2,..,xn) / x1  A1  x2  A2  ...  xn  An  p(x1,x2,..,xn) é V} ou

Vp = { (x1,x2,..,xn)  A1 x A2 x ... x An / p(x1,x2,..,xn)}
Exercícios de fixação: Pág. 163 do livro texto – Exercícios 1, 3 e de 5 até 11.
Operações lógicas com sentenças abertas
Conjunção
Considere as seguintes sentenças abertas:
“x é médico” , “x é professor”
Aplicando-se o conectivo de conjunção temos:
“x é médico”  “x é professor”
A expressão acima é verificada por todos os indivíduos que satisfaçam ao mesmo tempo as
duas sentenças. Portanto, o conjunto verdade Vp  q da sentença aberta p(x)  q(x) é a
interseção dos conjuntos Vp e Vq das sentenças p(x) e q(x) em A. Temos simbolicamente:
Vp  q = Vp Vq = { x  A / p(x)}  { x  A / q(x)}

Exemplo:
Sejam as sentenças abertas em Z (conjunto dos números inteiros):

p(x): x2 + x - 2 = 0
q(x): x2 - 4 = 0
Temos:
Vp  q = { x  Z / x2 + x - 2 = 0 }  { x  Z / x2 - 4 = 0} = {-2,1}  {-2,2} = {-2}
Disjunção
“x é médico”, “x é professor”
Aplicando-se o conectivo de disjunção temos:
“x é médico”  “x é professor”
A expressão acima é verificada por todos os indivíduos que satisfaçam pelo menos uma das
duas sentenças. Portanto, o conjunto verdade Vp  q da sentença aberta p(x)  q(x) é a
união dos conjuntos Vp e Vq das sentenças p(x) e q(x) em A. Temos simbolicamente:
Vp  q = Vp Vq = { x  A / p(x)}  { x  A / q(x)}
Exemplo:
Sejam as sentenças abertas em Z (conjunto dos números inteiros):

p(x): x2 + x - 2 = 0
q(x): x2 - 4 = 0
Temos:
Vp  q = { x  Z / x2 + x - 2 = 0 }  { x  Z / x2 - 4 = 0} = {-2,1}  {-2,2} = {-2,1,2}
Negação
Considere a seguinte sentença aberta:
“x tem menos de 21 anos”
Aplicando-se o conectivo de negação temos:
“~x tem menos de 21 anos”
ou
“x tem de 21 anos”  “x tem mais de 21 anos”
A 1a expressão é verificada por todos os indivíduos que não satisfaçam a ela. Temos
simbolicamente:
V~p = CAVP = A - VP = A - { x  A / p(x)}
Exemplo:
Seja a sentença abertas em Z (conjunto dos números inteiros)

p(x): x2 + x - 2 = 0
V~p = CAVP = A - VP = A - { x  A / p(x)}= Z – {-2,1}
Condicional
“x2 – 5x + 6 = 0”, “x2 – 9 =0”
Aplicando-se o conectivo da condicional temos:
“x2 – 5x + 6 = 0”  “x2 – 9 =0”
A expressão acima é verificada por todos os indivíduos que satisfaçam a tabela verdade da
condicional, resultando em Verdadeiro. Sendo p(x)  q(X)  ~p(x)  q(x), o conjunto
verdade Vp  q da sentença aberta p(x)  q(x) é a união dos conjuntos V~p e Vq das sentenças
p(x) e q(x) em A. Temos simbolicamente:
Vp  q = V~p  Vq = CAVP  Vq = (A - { x  A / p(x)})  { x  A / q(x)}
Exemplo:
Sejam as sentenças abertas em A = {1, 2, 3, 4, 5, 6, 7, 8, 9}

p(x): x2  A
q(x): x é impar
Temos:
Vp  q = (A - { x  A / x2  A })  { x  A / x é impar } =
({1, 2, 3, 4, 5, 6, 7, 8, 9} - {1, 2, 3})  {1, 3, 5, 7, 9} =
{4, 5, 6, 7, 8, 9}  {1, 3, 5, 7, 9} =
{1, 3, 4, 5, 6, 7, 8, 9}
Bicondicional
“x > -5”, “x < 0”
Aplicando-se o conectivo da bicondicional temos:
“x > -5”  “x < 0”
A expressão acima é verificada por todos os números inteiros maiores que –5 e menores que
zero.
Sendo p(x)  q(x)  (p(x)  q(x))  (q(x)  p(x)), daí temos:

(p(x)  q(x))  (q(x)  p(x))  (~p(x)  q(x))  (~q(x)  p(x)) o conjunto verdade Vp  q da
sentença aberta p(x)  q(x) é a interseção dos conjuntos Vp  q e Vq  p das sentenças p(x) 
q(x) e q(x)  p(x) em A. Temos simbolicamente:
Vp  q = ((A - { x  A / p(x)})  { x  A / q(x)})  ((A - { x  A / q(x)})  { x  A / p(x)})
Exemplo:
Sejam as sentenças abertas em A = {1, 2, 3, 4, 5, 6, 7, 8, 9}

p(x): x2  A
q(x): x é impar
Temos:
Vp  q = (A - { x  A / x2  A })  { x  A / x é impar } =
({1, 2, 3, 4, 5, 6, 7, 8, 9} - {1, 2, 3})  {1, 3, 5, 7, 9} =
{4, 5, 6, 7, 8, 9}  {1, 3, 5, 7, 9} =
{1, 3, 4, 5, 6, 7, 8, 9}
Vq  p = (A - { x  A / x é impar})  { x  A / x2  A } =
({1, 2, 3, 4, 5, 6, 7, 8, 9} - {1, 3, 5, 7, 9})  {1, 2, 3}=
{2, 4, 6, 8}  {1, 2, 3} =
{1, 2, 3, 4, 6, 8}
Vq  p = V p  q  Vq  p =
{1, 3, 4, 5, 6, 7, 8, 9}  {1, 2, 3, 4, 6, 8}
{1, 3, 4, 6, 8}
Exercícios de fixação: Pág. 172 a 174 do livro texto.

Quantificador Universal
Considere:
Vp = { x / x  A  p(x)}
Quando Vp = A podemos afirmar:
(i) Para todo elemento x de A, p(x) é verdadeira.

(ii) Qualquer que seja o elemento x de A, p(x) é verdadeira.
Na lógica matemática indica-se esse fato de uma das seguintes maneiras:
(i) ( x  A) (p(x))
(ii)  x  A, p(x)
(iii)  x  A : p(x)
(iv) ( x), (p(x))
(v)  x, p(x)
(vi)  x : p(x)
Logo, podemos afirmar: ( x  A) (p(x))  Vp = A.
Sendo A um conjunto finito, podemos ainda:

( x  A) (p(x))  (p(a1)  p(a2)  ...  p(an))
Exemplo:
No universo finito A = {3, 5, 7} e sendo p(x) a sentença aberta “x é primo”, temos:
( x  A) (x é primo)  (3 é primo  5 é primo  7 é primo)

Quantificador Existencial
Considere:
Vp = { x / x  A  p(x)}
Quando Vp   e pelo menos um elemento do conjunto A satisfaz a sentença aberta p(x),

podemos afirmar:
(i) Existe pelo menos um x  A, tal que p(x) é verdadeira.

(ii) Para algum x  A, p(x) é verdadeira.
Na lógica matemática indica-se esse fato de uma das seguintes maneiras:
(vii) ( x  A) (p(x))
(viii)  x  A, p(x)
(ix)  x  A : p(x)
(x) ( x), (p(x))
(xi)  x, p(x)
(xii)  x : p(x)
Logo, podemos afirmar: ( x  A) (p(x))  Vp  .
Sendo A um conjunto finito, podemos ainda:
( x  A) (p(x))  (p(a1)  p(a2)  ...  p(an))
Exemplo:
A proposição: ( n  N) (n + 4 < 8) é verdadeira, pois, o conjunto verdade da sentença aberta

p(n): n + 4 < 8 é:
Vp = { n / n  N  n + 4 < 8} = {1, 2, 3}  .
Quantificador de Existência e Unicidade
(i) Considere em R a sentença aberta “x2 = 16”.
42 = 16, (-4)2 = 16 e 4  -4
Temos dois valores que satisfazem a sentença acima, 4 e –4.
( x, y  R) (x2 = 16  y2 = 16  x  y)
(ii) Considere em R a sentença aberta “x3 = 27”.
Temos somente um valor que satisfaz a sentença acima, 3.
( ! x  R) (x3 = 27)
VARIÁVEL APARENTE E VARIÁVEL LIVRE
Quando há um quantificador a incidir sobre uma variável, esta diz-se aparente ou muda (ou
ligada); caso contrário, a variável diz-se livre.
Exemplos onde x é uma variável livre: 3x – 1 = 14, x + 1 > x;

Exemplos de variáveis aparentes: ( x)(3x – 1 = 14), ( x)(x+1>x).
Escopo de um quantificador
Exemplo: ( x)(3x – 1 = 14) 2x + 3 = 9 é uma sentença aberta pois o x aparece ligado na
primeira parte mas está livre na segunda parte. Supondo que o domínio é A={3,4,5} teríamos
Vp = { 3 }.
NEGAÇÃO DE PROPOSIÇÕES COM QUANTIFICADOR
~( x)(p(x)) = ( x)(~p(x))

~( x)(p(x)) = ( x)(~p(x))
Exemplos:
a) Negar que todo homem foi à lua é o mesmo que existe pelo menos um homem que não foi à
lua;
b) Negar que existe uma pessoa que é trilhonária é o mesmo que todas as pessoas não são
trilhonárias.
CONTRA-EXEMPLO
Para demonstrar que uma proposição quantificada com para todo é Falsa, basta encontrar um
elemento no domínio que NÃO satisfaça a sentença aberta.
Exemplo:
( x  N)(x+1=2) é F pois existe pelo menos um numero natural que não satisfaz a
sentença aberta x+1=2, por exemplo quando x = 9.
Exercícios de fixação: Pág. 185 do livro texto – Exercícios 5, 8, 9 e 11.
Capítulo 17 - Quantificação de Senteças Abertas com Mais de Uma Variável
1. Quantificação Parcial
A quantificação parcial aparece quando apenas uma das variáveis da sentença aberta é
quantificada:
Exemplo:
( x  A) (5x - 3y = 12)
onde o conjunto universo das variáveis x e y é A = {1,2,3,4,5}
Visto que não se sabe o valor de y, não se pode afirmar se existe o valor de x para que se
tenha uma proposição falsa ou verdadeira.
Neste caso, a variável y é denominada de variável livre.
2. Quantificação Múltipla
Quando uma sentença aberta possui um quantificador para cada variável, pode-se então dizer
que a sentença em questão é uma proposição, pois poder-se-á verificar se ela é uma
declaração falsa ou verdadeira.
Note-se que os quantificadores podem ser diferentes para cada variável.

Exemplos (ALENCAR FILHO, 2002):
a. ( x  A)(  y  B)(p(x,y))
b. ( x  A)(  y  B)(p(x,y))
c. ~( x  A)(  y  B)(p(x,y))
d. ~( x  A)( ! y  B)(p(x,y))
e. ( x  A)(  y  B)(p(x,y))
3. Comutatividade dos Quantificadores

Os quantificadores de uma dada fórmula somente podem ser comutados, de acordo com
as seguintes regras:
(i) Quantificadores de mesmo tipo podem ser comutados.
Portanto a seguinte equivalência é válida:

(x) (y) (P(x,y))  (y) (x) (P(x,y))
e também é válida a equivalência:

(x) (y) (P(x,y))  (y) (x) (P(x,y))

e outras equivalências similares.
(ii) Quantificadores de tipos distintos não podem ser comutados.
4. Negação de Proposições com Quantificadores
Qualquer expressão ou fórmula lógica quantificada também pode ser precedida do operador de
negação (~). Por exemplo, considerando o domínio das pessoas atualmente vivas as
expressões formais:
(x) (x fala Inglês)

~ (x) (x fala Inglês)
(x) (x foi à Antártida)
~ (x) (x foi à Antártida)
poderiam ser enunciadas, respectivamente, como:
Todas as pessoas falam inglês.
Nem todas as pessoas falam inglês.
Alguém foi a Antártida.
Ninguém foi a Antártida.
Analisando estas expressões deve ficar claro algumas equivalências intuitivas. Em primeiro
lugar afirmar que nem todas as pessoas falam Inglês é claramente equivalente a afirmar que
existe alguém que não fala Inglês. Formalizando temos:
~ (x) (x fala Inglês)  (x) ~ (x fala Inglês)
E em segundo lugar afirmar que ninguém foi à Antártida é obviamente equivalente a afirmar
que para todas as pessoas vivas atualmente não é verdade que elas tenham ido à Antártida.
Formalizando este argumento temos:
~ (x) (x foi à Antártida)  (x) ~ (x foi à Antártida)
Esta análise pode ser generalizada pelas seguintes regras:
(i) A negação da fórmula (x)(P(x)) é equivalente a afirmação de que, pelo menos para
um xA, tem-se que P(x) é falsa, ou então que ~P(x) é verdadeira.
Portanto deve valer a seguinte equivalência:

~ (xA) (P(x))  (xA) ~ (P(x))
(ii) Da mesma forma negar a fórmula (x)(P(x)) equivale a afirmar que para todos os x∈ A, a
sentença P(x) deve ser falsa, ou então que a sentença ~P(x) deve ser verdadeira, o que nos
leva a seguinte equivalência:
~ (xA) (P(x))  (xA) ~ (P(x))
Exercícios da página 190 até a página 192.

Apostila Logica para Computacao 20200206-1238

Enviado por

Direitos autorais:

Formatos disponíveis

Apostila Logica para Computacao 20200206-1238

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Apostila Logica para Computacao 20200206-1238

Enviado por

Direitos autorais:

Formatos disponíveis

2020

Professor Erlon Pinheiro

Linguagem Natural x Linguagem Lógica

Linguagem artificial/formal/simbólica é a linguagem construída para fins específicos, como

Linguagens artificiais exprimem com correção e exatidão o pensamento e os resultados do

Se X,Y,Z são números arbitrários,

Conjunto de palavras ou símbolos que exprimem um pensamento de sentido completo. São

A lógica matemática adota como regras fundamentais do pensamento os dois seguintes

Classificação das proposições:

b) Composta ou molecular: é aquela formada pela combinação de duas ou mais

P: Carlos é careca e Pedro é estudante

Segundo do Princípio do terceiro excluído, toda proposição simples p é verdadeira ou falsa.

O valor lógico de qualquer proposição composta depende unicamente dos valores

Exemplo: Considere uma proposição composta cujas proposições simples são p e q. Os

Exemplo: Considere uma proposição composta cujas proposições simples são p, q e r. Os

V(p) = V assim p é verdadeira

Operações lógicas sobre proposições:

a) Negação: Chame-se a negação de uma proposição p a proposição representada por “não

p: O Sol é uma estrela

b) Conjunção: Chame-se conjunção de duas proposições p e q a proposição representada

p  q: A neve é branca e 2 < 5

p  q: O enxofre é verde e 7 é um número primo

c) Disjunção: Chame-se disjunção de duas proposições p e q a proposição representada por

p  q: A neve é branca ou 2 < 5

p  q: O enxofre é verde ou 7 é um número primo

d) Disjunção exclusiva: Chame-se disjunção exclusiva de duas proposições p e q a

Uma condicional p  q não afirma que o conseqüente q se deduz ou é conseqüência do

p  q: Se a neve é branca, então 2 < 5

p  q: Se o enxofre é verde, então 7 é um número primo

f) Bicondicional: Chame-se bicondicional uma proposição representada por “p se e somente

p  q: A neve é branca se e somente se 2 < 5

p  q: O enxofre é verde se e somente se 7 é um número primo

Dadas várias proposições simples, podemos combiná-las pelos conectivos e construir

Com o emprego das tabelas-verdade das operações lógicas fundamentais é possível

Número de linhas de uma tabela-verdade: A tabela-verdade de uma proposição

1. Forma-se o par de colunas correspondente às duas proposições simples;

2a Solução (Não utilizaremos nesta disciplina)

1. Forma-se o par de colunas correspondente às duas proposições simples;

1. Traça-se uma coluna para cada uma das proposições e conectivos.

Logo: P(VV,VF,FV,FF) = VFVV

Uso de parênteses: É necessário o uso de parênteses na simbolização das proposições para

A ordem de precedência do os conectivos, do mais fraco para o mais forte é:

2. Sejam as proposições p:  = 3 e q: sen (/2) = 0, determine o valor lógico da proposição:

A proposição p  p é tautológica ???

A proposição ~(p  ~p) é tautológica ?

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

A proposição p  ~p é uma contradição?

A proposição p  ~p é uma contradição?

A proposição (p  q)  ~(p  q) é uma contradição?

p q pq pq ~(p  q) (p  q)  ~(p  q)

A proposição ~p  (p  ~q) é uma contradição ???

A proposição p  ~p é uma contingência?

A proposição p  q  p é uma contingência?

A proposição x = 3  (x  y  x  3) é uma contingência? Primeiro será obrigatório a

Princípio da Substituição para as Tautologias

Podemos também afirmar:

Tautologias e Implicação Lógica

P( p, q, r, ...)  Q( p, q, r, ...) se e somente se a condicional P( p, q, r, ...)  Q( p, q, r, ...) é

Se P( p, q, r, ...) Q( p, q, r, ...) é uma tautologia não ocorre em nenhum momento V(P) = V e