MD-Assunto01-Lógica

Prévia do material em texto

MATEMÁTICA DISCRETA
Prof. Salvador Ramos
ssilva@uea.edu.br
996-08-4591 (Whats)
Classroom: wkztscs
Apresentação do professor
• Nome: Salvador Ramos Bernardino da Silva
ssilva@uea.edu.br – 996-08-4591 (Whats)
• Graduação em Estatística, Ênfase Informática pela 
UNICAP.
• Especialização em Desenvolvimento de Sistemas, 
pela UFAM
• Mestrado em Sistemas Digitais, pela EPUSP.
• Atualmente: coordenador do curso de Eng. Comp.
Apresentação da disciplina
• Aprovação: 
Média Parcial – MP = (AP1 + AP2 + AP3 + AP4)/4
• Depois de obtida a MP, segue como nas demais disciplinas:
• Se MP >= 8,0, então aluno aprovado.
• Senão
• Se 4 <= MP < 8,0, aluno fará prova final (PF).
Média final – MF:
MF = ((MP * 2) + PF) / 3 (como nas demais disciplinas)
• Se MF >= 6,0, aluno aprovado. 
Iniciando...
• Método de estudo
• Estudar é escrever
• Aula dada, aula estudada NO DIA
• Após estudar, dormir.
• INTELIGÊNCIA como o cérebro aprende.
Prof. Pierluigi Piazzi
Completa (1h 50min):
https://www.youtube.com/watch?v=ai4VPDdOHUo&t=206s
Trechos :
https://www.youtube.com/watch?v=Uc4foy84MGc
Assunto 1: Lógica Matemática
• O que é lógica?
• Por que estudar lógica?
• Ramos da Lógica: proposicional, de predicados, 
deôntica, fuzzy, entre outros.
Assunto 1: Lógica Matemática
• O que é lógica?
• A lógica é um campo de estudo da Filosofia que se 
dedica a entender as relações linguísticas que tornam 
uma proposição válida ou inválida.
• Por que estudar lógica?
• Ramos da Lógica: proposicional, de predicados, 
deôntica, fuzzy, entre outros.
Assunto 1: Lógica Matemática
• O que é lógica?
• A lógica é um campo de estudo da Filosofia que se 
dedica a entender as relações linguísticas que tornam 
uma proposição válida ou inválida.
• Por que estudar lógica?
• É desafiador: necessita EXERCITAR A MENTE.
• Rapidez de raciocínio: prática da análise de fatos.
• Argumentação melhor fundamentada.
• Ramos da Lógica: proposicional, de predicados, 
deôntica, fuzzy, entre outros.
Assunto 1: Lógica Matemática
• Lógica Proposicional
Permite representar, de maneira formal, 
afirmações que fazermos usualmente, ou seja, 
PROPOSIÇÕES.
Permite determinar se proposições são falsas ou 
verdadeiras.
Sintaxe da Lógica
Sintaxe: escrever corretamente, de acordo com as regras da 
linguagem.
Elementos da sintaxe: alfabeto, proposições e fórmulas.
a) Alfabeto
constituído por:
símbolos de pontuação: () , .
símbolos de verdade: true, false. (Adotaremos: V e F).
símbolos proposicionais: P, Q, R, S, P1, Q1, S1, A, B, ...
conectivos proposicionais: ¬ ou (’) ou (~), ∧, ∨, →, ↔.
Sintaxe da Lógica
b) Proposição
É uma sentença declarativa afirmativa, a respeito da qual se pode 
afirmar que é falsa ou verdadeira. 
Exemplos:
Manaus é uma capital. - Proposição
Ela é muito inteligente. - Não é proposição pois “ela” não 
está especificada.
Que horas são? - É uma pergunta e não pode ser uma 
proposição.
Paris é uma cidade brasileira. - Proposição
Cinco é menor que oito. - Proposição 
Possivelmente choverá hoje - Não é proposição.
Faça o exercício agora - Não é proposição: verbo no imperativo. 
Sintaxe da Lógica
c) Fórmulas
Construídas a partir dos símbolos do alfabeto, conforme as seguintes regras:
a) Todo símbolo de verdade é uma fórmula (Verdadeiro, Falso);
b) Todo símbolo proposicional é uma fórmula;
c) Se H é uma fórmula então ~H é uma fórmula (negação)
d) Se H e G são fórmulas então: H ∨ G é uma fórmula (disjunção)
H ∧ G é uma fórmula (conjunção)
H → G é uma fórmula (condicional)
H ↔ G é uma fórmula (bicondicional)
Obs.: Não são válidas: ))A ↔∧ B C, A ∨∨ B ∨→, P∧↔
Sintaxe da Lógica
Uma cadeia válida é chamada de fórmula bem 
formulada (fbf).
Alguns autores mantêm a sigla inglesa wff (well
formed formula).
Fórmulas não válidas são chamadas de fórmulas mal 
formuladas.
Valor verdade
Uma proposição só admite um valor lógico (valor verdade): 
VERDADEIRO ou FALSO.
Exemplos:
Jéssica é inteligente.
A Lua é o satélite da Terra
O cachorro late
Vermelho é verde
O Sol gira em torno dos planetas
A Lua é feita de queijo.
Tipos de Proposições
Proposições podem ser simples e compostas
Exemplos de proposições simples:
- A Lua é feita de queijo.
- O mar é vermelho.
- A vida é um eterno aprendizado.
Exemplos de proposições compostas:
Está frio e não está chovendo.
- O carro é vermelho e é veloz mas não é bonito.
- Se chover e estiver frio, então não sairei de casa.
Formalizando uma proposição
Uma proposição simples pode ser representada por letras de proposição
Ex.: O lápis é preto – A
A moto é rápida – P
O leão é o rei dos animais – P1
Para formalizar uma proposição composta, deve-se representar cada uma 
das proposições simples por uma letra de proposição e uni-las por um 
concectivo.
Exemplo: Maria é alta e João é baixo
A ∧ B
Formalizando uma proposição
Expressão em Português Conectivo lógico
Expressão
Lógica
E, mas, também, além disso, ponto final
entre duas proposições
conjunção A ∧ B
Ou disjunção A ∨ B
Se A então B
A implica B
A logo B
A só se B, A somente se B
A é uma condição suficiente para B
Basta A para B
B é uma condição necessária para A
Condicional A  B
A se e somente se B
A é condição necessária e suficiente para B
Bicondiconal
(equivalência)
A ↔ B
Formalizando uma proposição
Exemplo
Considere a proposição abaixo:
Se João Gosta de Maria, então Maria é feliz. João não gosta de Maria.
Portanto, Maria não é feliz.
Proposições simples Representação
- João gosta de Maria P
- Maria é feliz Q
Representação na lógica proporcional: (P → Q) ∧ ~ P → ~Q
Obs: os parênteses são obrigatórios..
Formalizando uma proposição
Exemplos:
• Está frio mas não está chovendo.
• Está chovendo ou está quente.
• Se está frio então não está quente.
• Estar frio é condição suficiente para chover.
• Está chovendo, só se não estiver quente.
• Estar chovendo implica em estar frio.
• Estará frio se, e somente se, estiver chovendo. 
Exercício
Formalizar as proposições:
- Jorge irá a Maués se, e somente se, tiver barco.
- A casa é grande mas tem um quarto pequeno. Antônio 
gosta de quarto grande. Se a casa não tivesse um quarto 
pequeno, Antônio compraria a casa. Portanto, Antônio não 
comprará a casa.
- Se está chovendo, então a rua está molhada. Estará frio se, 
e somente se, estiver chovendo. Está frio ou a rua não está 
molhada. 
Escrever em linguagem corrente
Considerando 
A “José é atleta”
B “José gosta de correr”
C “José é magro” 
Obs.: Uma proposição, em linguagem corrente, pode ser escrita de mais de uma
maneira.
Escrever na linguagem corrente:
a) A → B
b) A ∧ B ∧ ~C
c) A ↔ B 
d) (A ∨ B) → C
e) A ↔ (B ∧ C) 
Semântica da Lógica Proposicional
A semântica dos elementos sintáticos da Lógica
Proposicional é uma função cujo domínio são as fbf
da lógica proposicional e cujo contradomínio é o
conjunto {V, F},
Ou seja, a interpretação de uma proposição resultará
em V ou F. Por esse motivo, ela é chamada lógica
bivalente.
Tabela verdade
O que é uma tabela verdade?
1) É uma tabela que apresenta todos os valores 
lógicos possíveis de uma fbf.
2) Número de linhas de uma tabela verdade: 2n, 
onde n é o número de proposições simples da 
fbf.
3) O valor da tabela verdade será o valor do último 
conectivo analisado.
Negação de uma proposição
Exemplos
Proposição Representação Valor verdade
simbólica (valor lógico)
Manaus está no Brasil. P V
Manaus não está no Brasil. ~P F
É falso que Manaus está no Brasil. ~P F
Não é verdade que Manaus não está ~(~P) V
no Brasil
Tabela verdade da negação:
P ~P
V F
F V
Negação de uma proposição
Proposição Negação correta Negação incorreta
O dia está quente
P
O dia não está quente.
É falso que o dia está quente.
Não é verdade que o dia está 
quente. 
~P
Paulo é baixo e gordo
P ∧ Q
É falso que Paulo seja baixo e 
gordo.
Paulo não é baixo ou não é gordo
Paulo é alto ou magro. 
~(P ∧ Q) ≡ ~P ∨ ~Q 
Paulo é alto e magro.
Obs.: Negaras 
proposições simples e o 
conectivo. 
O rio é raso ou não 
está poluído
P ∨ ~Q
É falso que o rio seja raso ou não 
esteja poluído.
Não é verdade que o rio é raso ou 
não está poluído
O rio é fundo e está poluído 
~(P ∨ ~Q) ≡ ~P ∧ Q
O rio não é raso ou está 
poluído
Negação de uma proposição
Proposição Negação correta
Se chover então a rua ficará 
molhada.
P → Q
Obs: P → Q ≡ ~P ∨ Q
Chove E a rua NÃO ficou molhada.
~(P → Q) ≡ ~(~P ∨ Q )
≡ P ∧ ~Q
Vou sair se e somente se estiver 
quente.
P ↔ Q ≡ (P → Q) ∧ (Q → P)
Vou sair e não está quente ou não vou 
sair e está quente.
~(P ↔ Q) ≡ ~((P → Q) ∧ (Q → P))
≡ ~(P → Q) ∨ ~(Q → P)
≡ (P ∧ ~Q) ∨ (Q ∧ ~P) 
Conjunção
• Quando duas proposições são unidas pelo 
conectivo “e”, acontece a conjunção
• Na Lógica Proposicional, a conjunção é 
representada por ∧
• “E” significa “um e outro”
Conjunção
• Tabela verdade da conjunção
P Q P ∧ Q
V V V
V F F
F V F
F F F
Disjunção
• Quando duas proposições (simples ou compostas) 
são unidas pelo conectivo “ou”, acontece a 
disjunção
• Na Lógica Proposicional, a disjunção é 
representada por ∨
• “Ou” significa “pelo menos um”
Disjunção
• Tabela verdade da disjunção
P Q P ∨ Q
V V V
V F V
F V V
F F F
Condicional
� Analisemos a frase:
Se eu passar no vestibular, então estudarei na universidade.
Proposições simples:
Eu passar no vestibular. - P - antecedente
Eu estudarei na universidade. - Q - consequente.
Formalização:
P → Q
Exercícios
Dê o antecedente e o conseqüente das seguintes proposições:
a) Se a chuva continuar, então o rio vai transbordar.
b) Uma condição suficiente para faltar energia, é que a 
chave central desligue.
c) Uma boa dieta é uma condição necessária para um gato 
ser saudável.
d) A definição ficará errada apenas se for alterada.
Condicional
Vamos às respostas:
a) Se a chuva continuar, então o rio vai transbordar.
Antecedente: A chuva continuar.
Consequente: O rio vai transbordar.
b) Uma condição suficiente para faltar energia, é que a 
chave central desligue.
Lembrar: em A → B, A é suficiente para B.
Reescrevendo: Se a chave central desligar então faltará 
energia.
Condicional
c) Uma boa dieta é uma condição necessária para um gato 
ser saudável.
Lembrar: em A → B, B é condição necessária para A.
antecedente: um gato saudável 
consequente: uma boa dieta
d) A definição ficará errada apenas se for alterada.
Proposição do tipo A somente se B.
Condicional
Convenção: se o antecedente de um condicional é falso, 
o valor lógico do condicional será VERDADEIRO.
Tabela verdade do condicional:
P Q P → Q
V V V
V F F
F V V
F F V
Bicondicional
• Analisemos a frase:
O Brasil vencerá o jogo se, e somente se, fizer mais gols 
que o adversário.
Vermelho será verde se, e somente se, branco for preto.
• Proposição do tipo “A se, e somente se B” ou 
“A é condição necessária e suficiente para B”
Bicondicional
Interpretação:
O bicondicional será verdadeiro quando ambas as 
proposições têm o mesmo valor e falso caso 
contrário.
Tabela verdade:
P Q P ↔ Q
V V V
V F F
F V F
F F V
CÁLCULO PROPOSICIONAL
Tem por objetivo avaliar o valor verdade de uma 
fórmula.
Ordem de precedência dos operadores
1. expressões entre parênteses, resolve-se a partir dos 
parênteses mais internos para os mais externos.
2. ~ (negação)
3. ∧ , ∨ (conjunção e disjunção têm a mesma precedência, 
operando-se o que ocorrer primeiro, da esquerda para a 
direita).
4. →
5. ↔
Interpretação
• Uma interpretação I, na Lógica Proposicional - LP, é uma 
função, tal que:
• O domínio de I são todas as fórmulas da LP.
• O contradomínio de I é o conjunto {V, F}.
• O valor dos símbolos de verdade I[true] = V e I[false] = F.
Consequentemente,
• Dado um símbolo proposicional P, I[P] ∈ {V, F}.
Interpretação
• Interpretar uma fórmula é dizer qual é o seu valor lógico, 
dados os valores das proposições simples.
• Uma interpretação de uma fbf corresponde a uma linha da 
tabela verdade dessa fórmula.
• Exemplo:
Qual a interpretação de H, se H = (P ∨ Q) → P, sabendo que 
I[P] = V e I[Q] = F?
(P ∨ Q) → P H
Interpretação
(P ∨ Q) → P H
V F V
Interpretação
(P ∨ Q) → P H
V F V
(P ∨ Q) → P H
V V F V
Interpretação
(P ∨ Q) → P H
V F V
(P ∨ Q) → P H
V V F V
(P ∨ Q) → P H
V V F V V V
• Outro exemplo:
Qual a interpretação da fórmula 
E = ( ~P ∧ Q) → (R ∧ P),
sabendo que I[P] = V e I[Q] = F
( ~ P ∧ Q) → (R ∧ P) E
V F V
Interpretação de uma fbf
Seja I uma interpretação tal que I[P → Q] = F. O que se pode
deduzir a respeito dos resultados das interpretações de
a) I[P] b) I[Q]
Solução:
Só há uma situação em que o condicional resulta em falso: quando 
o antecedente é verdadeiro e o consequente é falso.
Logo, a) I[P] = V b) I[Q] = F 
Interpretação de uma fbf
Seja I uma interpretação tal que I[P → Q] = V. O que se pode
deduzir a respeito dos resultados das interpretações de
a) I[P] b) I[Q]
Solução:
Uma sentença condicional resulta em verdadeiro quando o 
antecedente e consequente são ambos verdadeiros, ou 
quando o antecedente é falso.
Como há mais de uma possibilidade para os valores de P e Q, diz-
se que nada se pode afirmar a respeito de I[P] nem de I[Q].
Tabela verdade
Exercícios:
Construir a tabela verdade de cada fórmula abaixo:
• (A → B) ↔ ~A ∨ B
• (P → (~Q ∨ R)) ∧ ~(Q ∨ (P ↔ ~R))
Tabela verdade
(A → B) ↔ ~A ∨ B
Todos os valores possíveis de A e B
A B
Tabela verdade
(A → B) ↔ ~A ∨ B
Todos os valores possíveis de A e B
A B
V V
V F
F V
F F
Tabela verdade
(A → B) ↔ ~A ∨ B
1
A B A → B
V V V
V F F
F V V
F F V
Tabela verdade
(A → B) ↔ ~A ∨ B
1
A B A → B ~A
V V V F
V F F F
F V V V
F F V V
Tabela verdade
(A → B) ↔ ~A ∨ B
1 2
A B A → B ~A ~A ∨ B
V V V F V
V F F F F
F V V V V
F F V V V
Tabela verdade
(A → B) ↔ ~A ∨ B
1 2
A B A → B ~A ~A ∨ B 1 ↔ 2
V V V F V V
V F F F F V
F V V V V V
F F V V V V
Tabela verdade
Outra forma de construir a tabela verdade:
(A → B) ↔ ~A ∨ B
(A → B) ↔ ~ A ∨ B
Tabela verdade
Outra forma de construir a tabela verdade:
(A → B) ↔ ~A ∨ B
(A → B) ↔ ~ A ∨ B
V V
V V
F F
F F
Tabela verdade
Outra forma de construir a tabela verdade:
(A → B) ↔ ~A ∨ B
(A → B) ↔ ~ A ∨ B
V V V V
V F V F
F V F V
F F F F
Tabela verdade
Outra forma de construir a tabela verdade:
(A → B) ↔ ~A ∨ B
(A → B) ↔ ~ A ∨ B
V V V V V
V F F V F
F V V F V
F V F F F
Tabela verdade
Outra forma de construir a tabela verdade:
(A → B) ↔ ~A ∨ B
(A → B) ↔ ~ A ∨ B
V V V F V V
V F F F V F
F V V V F V
F V F V F F
Tabela verdade
Outra forma de construir a tabela verdade:
(A → B) ↔ ~A ∨ B
(A → B) ↔ ~ A ∨ B
V V V F V V V
V F F F V F F
F V V V F V V
F V F V F V F
Tabela verdade
Outra forma de construir a tabela verdade:
(A → B) ↔ ~A ∨ B
(A → B) ↔ ~ A ∨ B
V V V V F V V V
V F F V F V F F
F V V V V F V V
F V F V V F V F
Tabela verdade
(P → (~Q ∨ R)) ∧ ~(Q ∨ (P ↔ ~R))
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
Tabela verdade
(P → (~Q ∨ R)) ∧ ~(Q ∨ (P ↔ ~R))
P Q R ~Q
V V V F
V V F F
V F V V
V F F V
F V V F
F V F F
F F V V
F F F V
Tabela verdade
(P → (~Q ∨ R)) ∧ ~(Q ∨ (P ↔ ~R))
1
P Q R ~Q ~Q ∨ R
V V V F V
V V F F F
V F V V V
V F F V V
F V V F V
F V F F F
F F V V V
F F F V V
Tabela verdade
(P → (~Q ∨ R)) ∧ ~(Q ∨ (P ↔ ~R))
1 2
P Q R ~Q ~Q ∨ R P → 1
V V V F V V
V V F F F F
V F V V V V
V F F V V V
F V V F V V
F V F F F V
F F V V V V
F F F V V V
Tabela verdade
(P → (~Q ∨ R)) ∧ ~(Q ∨ (P ↔ ~R))
1 2 3
P Q R ~Q ~Q ∨ R P → 1 ~R
V V V F V V F
V V F F F F V
V F V V V V F
V F F V V V V
F V V F V V F
F V F F F V V
F F V V V V F
F F F V V V V
Tabela verdade
(P → (~Q ∨ R)) ∧ ~(Q ∨ (P ↔ ~R))
1 2 3 4
P Q R ~Q ~Q ∨ R P → 1 ~R P ↔ ~R
V V V F V V F F
V V F F F F V V
V F V V V V F F
V F F V V V V V
F V V F V V F V
F V F F F V V F
F F V V V V F V
F F F V V V V F
Tabela verdade
(P → (~Q ∨ R)) ∧ ~(Q ∨ (P ↔ ~R))
1 2 3 4 5
P Q R ~Q ~Q ∨ R P → 1 ~R P ↔ ~R Q ∨ 4
V VV F V V F F V
V V F F F F V V V
V F V V V V F F F
V F F V V V V V V
F V V F V V F V V
F V F F F V V F V
F F V V V V F V V
F F F V V V V F F
Tabela verdade
(P → (~Q ∨ R)) ∧ ~(Q ∨ (P ↔ ~R))
1 2 3 4 5 6
P Q R ~Q ~Q ∨ R P → 1 ~R P ↔ ~R Q ∨ 4 ~5
V V V F V V F F V F
V V F F F F V V V F
V F V V V V F F F V
V F F V V V V V V F
F V V F V V F V V F
F V F F F V V F V F
F F V V V V F V V F
F F F V V V V F F V
Tabela verdade
(P → (~Q ∨ R)) ∧ ~(Q ∨ (P ↔ ~R))
1 2 3 4 5 6
P Q R ~Q ~Q ∨ R P → 1 ~R P ↔ ~R Q ∨ 4 ~5 2 ∧ 6
V V V F V V F F V F F
V V F F F F V V V F F
V F V V V V F F F V V
V F F V V V V V V F F
F V V F V V F V V F F
F V F F F V V F V F F
F F V V V V F V V F F
F F F V V V V F F V V
Tautologia
• O que é uma tautologia?
• Uma fbf que é uma tautologia também é 
chamada de fórmula válida.
• Exemplo:
A → (A ∨ B)
Tautologia
Exercício:
Se João for à festa, então Maria ficará triste. João foi à 
festa. Logo, Maria ficou triste.
Formalizar a sentença dada e fazer a respectiva tabela 
verdade.
Verificando a solução:
Formalizando
(J → T) ∧ J → T.
Tabela verdade
Contradição
• Conceito: 
Se, para toda interpretação I, de uma fórmula G, I[G] = F, 
então G é uma contradição (ou contraditória).
Contradição
Exemplo:
~(P → Q) ∧ Q
Solução:
P Q P → Q ~(P → Q) ~(P → Q) ∧ Q
V V V F F
V F F V F
F V V F F
F F V F F
Fórmula satisfatível
• Quando uma fórmula é satisfatível (ou contingência)?
Formalmente:
Dada uma fórmula H, se existe pelo menos uma 
interpretação I, tal que I[H] = V, então H é satisfatível.
Contingência ou indeterminação são outras 
denominações para fórmulas satisfatíveis.
Exemplo:
H = (P ↔ Q) ∨ Q 
Equivalência Lógica
Dadas duas fórmulas H e G, H equivale a G (H ⇔ G), se e 
somente se, para toda interpretação I, I[H] = I[G] .
Exemplo:
Seja G = A ↔ B e H = (A → B) ∧ (B → A).
Uma forma de verificar quais são todas as interpretações 
de uma fbf é construir sua tabela verdade.
Assim, construam as tabelas verdade de G e H! 
Implicação lógica
Sejam as fórmulas G e H. 
Se G → H é uma tautologia.
Então, G implica logicamente em fórmula H (G  H) 
Exemplo: 
Sejam K = (P ∧ Q) ∨ Q, L = P ∧ Q e M = P ∨ Q 
Verificar se 
a) L  M b) M  K c) L  K d) K  M
Implicação lógica
Outra maneira de verificar se uma fbf implica logicamente 
em outra:
• Dadas duas fórmulas G e H, G implica H (G  H) se, e 
somente se, para toda interpretação I, 
se I[G] = V, então I[H] = V
Exercício:
Analisar o exemplo anterior através desse segunda forma.
Avaliação de um argumento
O que é avaliar um argumento?
É buscar determinar seu valor lógico.
Como se avalia um argumento?
Utilizando os métodos de prova da Lógica Proposicional
Avaliação de um argumento
Métodos para determinar o valor lógico (Verdadeiro ou Falso) 
de uma proposição:
Método da tabela verdade. (já visto)
Método da árvore semântica. 
Método da negação ou absurdo.
Esses três primeiros são gerais.
Método da dedução lógica.  o argumento precisa 
obedecer a um determinado formato.
Árvore
O que é uma árvore?
• Exemplos de árvore:
Árvore binária
Árvore binária
• Nó: raiz, pai, filho, avô, folha
Método da árvore semântica
Em que consiste o método da árvore semântica?
Verificar se a fórmulas abaixo é válida:
A → ((B ∨ C) ∧ A)
Pelo método da árvore semântica, uma fórmula será 
válida se todos os nós folha tiverem valor lógico 
VERDADEIRO. 
Método da árvore semântica
1
A → ((B ∨ C) ∧ A) I[A] = V I[A] = F
Nó 2 V ? ? V 2 3
Nó 3 F V F F ? V
Método da árvore semântica
1
A → ((B ∨ C) ∧ A) I[A] = V I[A] = F
Nó 2 V ? ? V 2 3 
Nó 3 F V F F I[B] = V I[B] = F V 
Nó 4 V V V V V V 4 5 
Nó 5 V ? F ? ? V V ? 
Método da árvore semântica
1
A → ((B ∨ C) ∧ A) I[A] = V I[A] = F
Nó 2 V ? ? V 2 3
Nó 3 F V F F I[B] = V I[B] = F V 
Nó 4 V V V V V V 4 V 5 
Nó 5 V ? F ? ? V I[C] = V I[C] = F 
Nó 6 V V F V V F F 6 7
Nó 7 V F F F F F V V F
Conclusão: A fórmula dada não é válida, uma vez que um nó folha tem valor lógico 
FALSO.
Pode-se dizer que a fórmula não é válida para a interpretação 
I[A]=V, I[B]=F, I[C] = F
Método da árvore semântica
Exercício: Verificar, usando o método da árvore 
semântica, se a fbf a seguir é válida:
(S → (~C ∧ ~Q)) ∧ (~C ∧ Q) → ~S
(~A → ~B) ∧ (A → C) → (B → C) 
Método da negação ou absurdo
O objetivo é provar que o argumento é válido.
Procura-se provar que a fbf H, p. ex.,é falsa (negação).
Na busca dessa prova há duas possibilidades:
1 – prova-se que a fórmula não é válida.
2 – não se consegue provar que a fbf não é válida, chegando-se a 
um absurdo.
Conclusão para a possibilidade 2: Se, ao tentar mostrar que H não é 
válida, chega-se a um absurdo, então H é válida.
Método da negação ou absurdo
• Exemplo: verificar se fórmula é válida:
Primeiro identificar o conectivo que será analisado por 
último e atribuir o valor F. No caso, o condicional.
Seguir com a prova, atribuindo os valores que tornam a 
fórmula falsa.
A → ((B ∨ C) ∧ A)
Método da negação ou absurdo
• Exemplo
A → ((B ∨ C) ∧ A)
F
Método da negação ou absurdo
• Exemplo
A → ((B ∨ C) ∧ A)
F
V F F V
Método da negação ou absurdo
• Exemplo
A → ((B ∨ C) ∧ A)
F
V F F V
V F F F V
Método da negação ou absurdo
• Exemplo
Conclusão: a fórmula não é válida, pois chegou-se a uma 
interpretação que demonstra a não validade da mesma.
A → ((B ∨ C) ∧ A)
F
V F F V
V F F F V
V F F F F F V
Método da negação ou absurdo
Outro exemplo:
Provar que G = (A → B) ∧ (B → C) → (A → C) é válida, 
usando o método na negação (ou absurdo)
Solução:
(A → B) ∧ (B → C) → (A → C)
F
Solução
(A → B) ∧ (B → C) → (A → C)
V V V F F
(A → B) ∧ (B → C) → (A → C)
V F F
(A → B) ∧ (B → C) → (A → C)
V V V F V F F
(A → B) ∧ (B → C) → (A → C)
V V V V F F V F F
(A → B) ∧ (B → C) → (A → C)
V V V V F V F F V F F
ABSURDO☹ ☹
Conclusão: Ao tentar mostrar que a fórmula não é válida, chega-se a um absurdo. 
Logo, a mesma é válida.
Exercícios
• Provar por absurdo os argumentos abaixo:
1 – Refazer os exercícios feitos por árvore 
semântica.
2 – (P ∨ Q) ∨ (~P ∧ Q)
3 – (A → B) → ((A  C) → (B ∨ C))
Dedução lógica
Considere um argumento do tipo:
P1 ∧ P2 ∧ P3 ∧ P4 ∧ ... ∧ Pn → Q 
A prova por dedução é feita através de
uma sequência de dedução
O desenvolvimento de uma sequência de dedução é realizado 
obedecendo às regras de dedução.
Regras de dedução são de dois tipos:
Regras de equivalência e
Regras de inferência.
Dedução lógica
Regras de equivalência:
Fórmula Equivale a Nome/abreviação da regra
P ∧ Q
P ∨ Q
Q ∧ P
Q ∨ P Comutativa – com
(P ∧ Q) ∧ R
(P ∨ Q) ∨ R
P ∧ (Q ∧ R)
P ∨ (Q ∨ R) Associatividade - ass
~(P ∧ Q)
~(P ∨ Q)
~P ∨ ~Q
~P ∧ ~Q Leis de De Morgan
P→ Q ~P ∨ Q Condicional – cond
P ~(~P) Dupla negação – dn
P ↔ Q (P→ Q) ∧ (Q→ P) Definição de Equivalência - equi
Dedução lógica
Regras de inferência:
De Podemos deduzir Nome da regra
P 
P→ Q Q Modus ponens – mp
P → Q
~Q
~P Modus tollens – mt
P, Q P ∧ Q Conjunção – conj
P ∧ Q P, Q Simplificação - simp
P P ∨ Q Adição – ad
Dedução lógica
Provar que o argumento é verdadeiro:
P ∧ (P → Q ) → Q
1. P hip.
2. P → Q hip.
3. Q 1, 2, m.p.
Dedução lógica
Outro exemplo:
~A ∧ (A ∨ ~B) → ~B
Solução:
1. ~A hip.
2. A ∨ ~B hip.
3. ~(~A) ∨ ~B 2, dn
4. ~A → ~B 2,cond
5. ~B 1,4 mp
Dedução lógica
Mais um exemplo
Provar o argumento:
A ∧ (~A ∨ B) ∧ ((B ∨ C) → C) ∧ (C → D) → D
1. A hip
2. ~A ∨ B hip
3. (B ∨ C) → C hip
4. C → D hip
5. A → B 2, cond
6. B 1, 5, mp
7. B ∨ C 6, ad
8. C 3, 7 mp
9. D 4, 8 mp
Exercícios
• Provar por dedução lógica:
a) A ∧ (B → C) ∧ [(A ∧ B) → (D ∨ ~C)] ∧ B → D
b) [(A ∨ ~B) → C] ∧ (C → D) ∧ A → D
Outras regras de dedução
• Suponha que o argumento que queremos provar tem a forma:
P1 ∧ P2 ∧ P3 ∧ ... ∧ Pn → (R → S)
a) Como queremos inferir R → S, o método
dedutivo nos permite adicionar R como hipótese 
adicional de depois inferir S. 
Exemplo:
(~A → ~B) ∧ (A → C) → (B → C) 
b) Silogismo hipotético (sh)
A regra de inferência silogismo 
hipotético (sh) que diz:
De A → B e B → C pode-se concluir que A → C
Escrevendo o silogismo hipotético como uma fbf temos:
(A → B) ∧ (B → C) → (A → C)
Exercício: provar (P → (~Q ∨ R)) ∧ (R → S) ∧ P → (Q → S) 
Justifique cada passo de indução, na prova da fórmula:
~P ∧ Q ∧ (Q → (P ∨ R)) → R
1. ~P
2. Q
3. Q → (P ∨ R)
4. P ∨ R
5. ~P → R
6. R
Usando dedução lógica, prove que os argumentos abaixo 
são válidos:
(A ∨ B) ∧ ~A → B
(A → B) ∧ (A → (B → C)) → (A → C)
Exercício
• Considere o argumento do advogado de defesa, em um processo onde você 
é jurado:
Se meu cliente fosse culpado, a faca estaria na gaveta. Ou a faca não estava
na gaveta ou Jason Pritchard viu a faca. Se a faca não estava lá no dia 10 de
outubro, segue que Jason Pritchard não viu a faca. Além disso, se a faca
estava lá no dia 10 de outubro, então a faca estava na gaveta e o martelo
estava no celeiro. Mas todos sabemos que o martelo não estava no celeiro.
Portanto, senhoras e senhores do júri, meu cliente é inocente.
Esse argumento é válido? Como você votaria?
(Livro Fundamentos Matemáticos para a Ciência da Computação – Judith Gersting)
LÓGICA DE PREDICADOS
Quantificadores
Uma propriedade dos elementos de um conjunto pode ser 
representada, genericamente, por p(x).
Com frequência, é desejável quantificar os valores de x que 
possuem uma propriedade p(x).
Exemplo: Os números inteiros positivos podem ser expressos 
assim: “para todo x, x>0”.
Nessa sentença, “para todo” é um quantificador e “x>0” 
representa uma propriedade de x – p(x).
Uma propriedade, também é denominada predicado.
Quantificadores
O o quantificador “qualquer que seja” ou “para 
todo” é representado pelo símbolo ∀.
∀ é chamado de QUANTIFICADOR UNIVERSAL
Quando associado a uma proposição p(x), é 
denotado, alternativamente, por
(∀x ∈A)(p(x)) ou (∀x ∈A)p(x) ou (∀x)p(x) 
Quantificadores
Considerando o conjuntos dos inteiros e a expressão “existe x, 
tal que (x/2) é inteiro”, nota-se o surgimento de outro 
quantificador.
O quantificador EXISTENCIAL significa “para algum” ou “para 
pelo menos um” ou, ainda, “existe algum”.
É simbolizado por ∃
Quando associado a uma proposição p(x), é denotado, 
alternativamente, por:
(∃x ∈ A)(p(x)) ou (∃x ∈ A)p(x) ou (∃x)p(x)
• Quando uma propriedade se aplica a uma variável, o predicado é 
dito unário e quando se aplica a duas variáveis, binário.
Ex.: P(x,y) = x < y ∃x∃y,P(x,y)
• Predicados são, de modo geral, n-ários.
• Parênteses determinam o escopo do quantificador. 
• Quando uma variável aparece em uma fórmula e não está 
quantificada, é chamada de variável livre. 
• Na expressão (∀x)(Q(x,y) → (∃y)(R(x,y))) o escopo de x é toda a 
fórmula e y é uma variável livre em Qxy, pois não está quantificada.
Valor lógico
• O valor lógico de uma proposição quantificada depende do 
domínio dos objetos sobre os quais estamos nos referindo, 
ou seja, depende do conjunto universo (que é o domínio da 
aplicação).
∀x∈A, Px é verdadeira, se p(x) for verdadeira para todos os 
elementos de A.
∃x∈A, Px é verdadeira se p(x) for verdadeira para pelo 
menos um elemento de A.
Valor lógico
Considerando o conjunto universo como sendo o 
conjunto de todas as pessoas que moram no 
Estado do Amazonas e a propriedade P(x) = “x é do 
sexo feminino”, determinar o valor lógico das 
expressões:
a) (∀x)Px b) (∃x)Px
Valor Lógico
Considere o conjunto universo o conjunto dos 
números inteiros naturais e a propriedade P(x,y) = x 
< y.
Qual o valor lógico das expressões abaixo?
a) (∀x)(∃y) x < y
b) (∃y)(∀x) x < y 
Valor Lógico
a) (∀x)(∃y) x < y
- Verdadeira. Para qualquer inteiro x, existirá um valor 
y maior.
b) (∃y)(∀x) x < y 
- Falsa. Não existe um valor y que seja maior que todos 
os valores x do conjunto universo.
Valor lógico
• Considere a proposição
(∃x)(A(x) ∧ (∀y)(B(x,y) → C(y)))
com a interpretação de que o conjunto universo é o dos inteiros, A(x) é 
“x>0”, B(x,y) é “x > y” e C(y) é “y <= 0”.
Valor lógico da proposição:
Fazendo x = 1, qualquer y < x será <= 0. Logo tem valor V.
Aponte uma interpretação onde o valor lógico é o oposto do acima.
Fazendo A(x) é “x é par”, B(x,y) é “x < y” e C(y) é “y é ímpar”.
Nesse caso, terá valor lógico F (falso), pois não existe um inteiro par com a 
propriedade de que todos os inteiros maiores são ímpares.
Formalização
• A declaração em português “Todo papagaio é feio”, 
pode ser reescrita como: “dada uma coisa, se é um 
papagaio, então é feio’.
• Denotando por P(x) “x é um papagaio” e por F(x) “x 
é feio”, a proposição pode ser simbolizada por:
(∀x)(P(x) → F(x))
Formalização
• Proposições com o quantificador universal 
geralmente são escritas como proposições 
condicionais.
• Assim, é incorreta a tradução da fórmula anterior 
como 
(∀x)(P(x) ∧ F(x))
pois diz que todo x, onde x é qualquer coisa, é um 
papagaio feio.
Formalização
• Da mesma forma, a frase “Existe um papagaio feio”, 
pode ser reescrita como “existe alguma coisa que é, 
ao mesmo tempo, um papagaio e é feio”.
(∃x)(P(x) ∧ F(x))
Outras variações: “Alguns papagaios são feios”, 
“Existem papagaios feios”.
∃ e ∧ estão, geralmente, juntos.
Exercício
• Usando os símbolos predicados E(x) para “x é um estudante”, I(x) 
“x é inteligente e M(x) “x gosta de música”, escreva uma fbf para 
cada uma das expressões em língua corrente a seguir:
a) Todos os estudantes são inteligentes.
b) Alguns estudantes inteligentes gostam de música.
c) Todo mundo que gosta de música não é estudante não 
inteligente.
d) Apenas estudantes inteligentes gostam de música.
Solução do exercício
• a) (∀x) (E(x) → I(x))
• b) (∃x) (E(x) ∧ I(x) ∧ M(x)) 
• c) (∀x) (M(x) → E(x) ∧ ~I(x))
• d) (∀x) (M(x) → E(x) ∧ I(x))
;
• Considere F(x) “x é uma fruta”, L(x) “x é um legume”, D(x,y) 
“x é mais doce que y”. Formalize:
a) Alguns legumes são mais doces que todas as frutas.
b) Todas as frutas são mais doces que todos os legumes.
c) Todas as frutas são mais doces que alguns legumes.
d) Apenas frutas são mais doces do que legumes.
• Solução:
a) (∃x) (L(x) ∧ (∀y) (F(y) → D(x,y))) 
b) (∀x) (F(x) → (∀y) (L(y) → D(x,y))) 
c) (∀x) (F(x) → (∃ y) (L(y) ∧ D(x,y)))
d) (∀x) (∀y)(L(y) ∧ D(x,y) → F(x))
• Negação de uma proposição quantificada
Uma proposição do tipo (∀x ∈ A) p(x) é verdadeira se p(x) se 
verificar para todos os valores de A.
Assim, a negação dessa proposição acontece quando p(x) não 
se verifica para pelo menos um elemento de A, ou seja, (∃x ∈
A) ~p(x).
Assim: ~( (∀x)p(x) ) ⇔ (∃x) ~p(x).
• Negar a sentença:
Todo o mundo ama alguém alguma vez.
Formalizando: (∀x)(∃y)(∃t)A(x,y,t)
Negação: ~((∀x)(∃y)(∃t)A(x,y,t))
⇔ (∃ x)~((∃y)(∃t)A(x,y,t))
⇔ (∃ x)(∀y)~(∃t)A(x,y,t))
⇔ (∃ x)(∀ y)(∀ t)~(A(x,y,t))
• Procure justificar as seguintes equivalências:
~( (∀n ∈ N)(n < 1) ) ⇔ (∃n ∈ N) (n ≥ 1) ⇔ V
~( (∃n ∈ N)(n < 1) ) ⇔ (∀n ∈ N) (n ≥ 1) ⇔ F
~( (∀n ∈ N)(n! < 10) ) ⇔ (∃n ∈ N) (n! ≥ 10) ⇔ V
~( (∃ n ∈ N)(n! < 10) ) ⇔ (∀n ∈ N) (n! ≥ 10) ⇔ F