logica

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Lo´gica
Prof. Dr. Leandro Balby Marinho
Matema´tica Discreta
Prof. Dr. Leandro Balby Marinho 1 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Por que estudar Lo´gica?
I A lo´gica distingue argumentos va´lidos de inva´lidos.
I E´ a base para todo o racioc´ınio matema´tico e computacional.
I Exemplos: projeto de circuitos, linguagens de programac¸a˜o e
inteligeˆncia artificial.
Prof. Dr. Leandro Balby Marinho 2 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Roteiro
1. Lo´gica Proposicional
2. Exemplos de Aplicac¸o˜es da Lo´gica Proposicional
3. Equivaleˆncias Lo´gicas
4. Lo´gica de Predicados
5. Regras de Infereˆncia
Prof. Dr. Leandro Balby Marinho 3 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Proposic¸o˜es
Uma proposic¸a˜o e´ uma sentenc¸a declarativa que e´ verdadeira ou falsa.
Exemplo 1: As seguintes sentenc¸as sa˜o proposic¸o˜es:
I Campina Grande e´ a capital da Para´ıba.
I Los Angeles e´ a capital dos EUA.
I 1 + 1 = 2
I 2 + 2 = 3
Exemplo 2: As sentenc¸as seguintes sa˜o proposic¸o˜es?
I Que horas sa˜o?
I Estude com atenc¸a˜o.
I x + 1 = 2.
I x + y = z .
Prof. Dr. Leandro Balby Marinho 3 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Convenc¸o˜es
I Letras para denotar varia´veis proposicionais ou booleanas,
e.g., p, q, r , s, . . .
I T :=verdade e F :=falso.
Prof. Dr. Leandro Balby Marinho 4 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Operador de Negac¸a˜o
Definic¸a˜o 1
Seja p uma proposic¸a˜o. A negac¸a˜o de p, denotada por ¬p (ou p¯),
corresponde ao valor verdade oposto de p.
Exemplo 3: Seja a proposic¸a˜o p “Hoje e´ Quarta”. A negac¸a˜o ¬p e´
traduzida como “Hoje na˜o e´ Quarta”.
Tabela verdade
p ¬p
T F
F T
Prof. Dr. Leandro Balby Marinho 5 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Operador de Conjunc¸a˜o
Definic¸a˜o 2
Sejam p e q proposic¸o˜es. A conjunc¸a˜o de p e q, denotada por p ∧ q (ou
p · q), e´ verdadeira quando ambos p e q forem verdadeiras e falsa de
outra forma.
Exemplo 4: Seja p a proposic¸a˜o “Hoje e´ sexta” e q a proposic¸a˜o “Esta´
chovendo hoje”, a conjunc¸a˜o p ∧ q pode ser escrita como “Hoje e´ sexta e
esta´ chovendo hoje”.
Tabela verdade
p q p ∧ q
T T T
T F F
F T F
F F F
Prof. Dr. Leandro Balby Marinho 6 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Operador de Disjunc¸a˜o
Definic¸a˜o 3
Sejam p e q proposic¸o˜es. A disjunc¸a˜o de p e q, denotada por p ∨ q (ou
p + q), e´ falsa quando ambas p e q forem falsas e verdadeira de outra
forma.
Exemplo 5: Seja p a proposic¸a˜o “Ele cursara´ Ca´lculo” e q a proposic¸a˜o
“Ele cursara´ A´lgebra linear.” Enta˜o a disjunc¸a˜o p∨q pode ser escrita como
“Ele cursara´ Ca´lculo ou A´lgebra linear.”
Tabela verdade
p q p ∨ q
T T T
T F T
F T T
F F F
Prof. Dr. Leandro Balby Marinho 7 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Operador OU Exclusivo
Definic¸a˜o 4
Sejam p e q proposic¸o˜es. O ou exclusivo de p e q, denotado por
p ⊕ q, e´ a proposic¸a˜o que e´ verdadeira quando exatamente uma
das duas proposic¸o˜es forem verdadeiras e falsa de outra forma.
Exemplo 6: “O novo aluno nasceu no Uruguai ou Argentina.”
Tabela verdade
p q p ⊕ q
T T F
T F T
F T T
F F F
Prof. Dr. Leandro Balby Marinho 8 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Operador de Implicac¸a˜o
Definic¸a˜o 5
Sejam p e q proposic¸o˜es. A implicac¸a˜o p → q so´ e´ falsa quando q
e´ falsa e p e´ verdadeira.
Exemplo 7: “Se ele for eleito, aumentara´ o sala´rio m´ınimo.”
Tabela verdade
p q p → q
T T T
T F F
F T T
F F T
Diferente de if-then-else! Por que?
Prof. Dr. Leandro Balby Marinho 9 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Implicac¸a˜o: Converso, Contrapositivo e Inverso
Dada a implicac¸a˜o p → q:
I q → p e´ chamada de converso.
I ¬q → ¬p e´ chamada de contrapositivo.
I ¬p → ¬q e´ chamada de inverso.
Exerc´ıcio 1: Qual deles tem o mesmo valor lo´gico da implicac¸a˜o
original?
Prof. Dr. Leandro Balby Marinho 10 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Operadores: Implicac¸a˜o Bicondicional
Definic¸a˜o 6
Sejam p e q proposic¸o˜es. A implicac¸a˜o bicondicional p ↔ q e´
verdadeira quando p e q possuem o mesmo valor lo´gico e falsa de
outra forma.
Exemplo 8: “Voceˆ pode embarcar no avia˜o se e somente se comprou
a passagem.”
Tabela verdade
p q p ↔ q
T T T
T F F
F T F
F F T
Prof. Dr. Leandro Balby Marinho 11 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Precedeˆncia de Operadores
Quando a precedeˆncia na˜o estiver explicitada atrave´s de
pareˆnteses, a seguinte ordem de precedeˆncia deve ser utilizada:
Operador Precedeˆncia
¬ 1
∧ 2
∨ 3
→ 4
↔ 5
Exemplo 9: A expressa˜o p ∨ q ∧ r significa p ∨ (q ∧ r) e na˜o
(p ∨ q) ∧ r .
Prof. Dr. Leandro Balby Marinho 12 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Proposic¸o˜es Compostas
Podemos usar os operadores apresentados para construir proposic¸o˜es
complexas envolvendo qualquer nu´mero de proposic¸o˜es.
Exemplo 10: (p ∨ ¬q)→ (p ∧ q)
Tabela verdade
p q ¬q p ∨ ¬q p ∧ q (p ∨ ¬q)→ (p ∧ q)
T T F T T T
T F T T F F
F T F F F T
F F T T F F
Prof. Dr. Leandro Balby Marinho 13 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Roteiro
1. Lo´gica Proposicional
2. Exemplos de Aplicac¸o˜es da Lo´gica Proposicional
3. Equivaleˆncias Lo´gicas
4. Lo´gica de Predicados
5. Regras de Infereˆncia
Prof. Dr. Leandro Balby Marinho 14 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Operac¸o˜es Bit-a-Bit
I Valores lo´gicos podem tambe´m representar bits (1 = T e 0 = F ).
I Operac¸o˜es de bit correspondem aos operadores da lo´gica
proposicional.
Exemplo 11: Abaixo as operac¸o˜es bit-a-bit OR (∨), AND (∧) e XOR (⊕)
entre duas cadeias de bits.
01 1011 0110
11 0001 1101
−−−−−
11 1011 1111 (OR bit-a-bit)
01 0001 0100 (AND bit-a-bit)
10 1010 1011 (XOR bit-a-bit)
Prof. Dr. Leandro Balby Marinho 14 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Busca Booleana na Web
Exemplo 12: Quais pec¸as de Shakespeare conte´m Brutus ∧ Ce´sar ∧¬
Calpurnia?
Soluc¸a˜o: Dada a matriz de incideˆncia bina´ria termo-documento abaixo:
Antoˆnio e Cleo´patra Ju´lio Ce´sar A Tempestade Hamlet Othello Macbeth
Antoˆnio 1 1 0 0 0 1
Brutus 1 1 0 1 0 0
Ce´sar 1 1 0 1 1 1
Calpurnia 0 1 0 0 0 0
Cleo´patra 1 0 0 0 0 0
Realiza-se as operac¸o˜es lo´gicas na consulta
a n´ıvel de bits nos vetores
bina´rios representando os termos da consulta.
Prof. Dr. Leandro Balby Marinho 15 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Roteiro
1. Lo´gica Proposicional
2. Exemplos de Aplicac¸o˜es da Lo´gica Proposicional
3. Equivaleˆncias Lo´gicas
4. Lo´gica de Predicados
5. Regras de Infereˆncia
Prof. Dr. Leandro Balby Marinho 16 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Tautologias e Contradic¸o˜es
Definic¸a˜o 7
I Tautologia: Uma proposic¸a˜o composta que e´ sempre verdadeira.
I Contradic¸a˜o: Uma proposic¸a˜o composta que e´ sempre falsa.
I Contingeˆncia: Nem tautologia nem contradic¸a˜o.
Exemplo 12: Mostre que p ∨ ¬p e´ uma tautologia e p ∧ ¬p uma
contradic¸a˜o.
p ¬p p ∨ ¬p p ∧ ¬p
T F T F
F T T F
Prof. Dr. Leandro Balby Marinho 16 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Equivaleˆncias Lo´gicas
Definic¸a˜o 8
As proposic¸o˜es compostas p e q sa˜o logicamente equivalentes se p ↔ q
for uma tautologia. A notac¸a˜o p ≡ q denota que p e q sa˜o logicamente
equivalentes.
Exerc´ıcio 2: Use tabelas de verdade para determinar se as proposic¸o˜es
abaixo sa˜o logicamente equivalentes:
a) ¬(p ∨ q) e ¬p ∧ ¬q (uma das leis de De Morgan).
b) p → q e ¬p ∨ q.
c) p ∨ (q ∧ r) e (p ∨ q) ∧ (p ∨ r) (lei distributiva da disjunc¸a˜o).
Prof. Dr. Leandro Balby Marinho 17 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Algumas Equivaleˆncias Importantes
Equivaleˆncia Nome
p ∧ T ≡ p Leis de Identidade
p ∨ F ≡ p
p ∨ T ≡ T Leis de Dominac¸a˜o
p ∧ F ≡ F
p ∨ p ≡ p Leis de Idempoteˆncia
p ∧ p ≡ p
p ∨ q ≡ q ∨ p Leis Comutativas
p ∧ q ≡ q ∧ p
¬(¬p) ≡ p Negac¸a˜o Dupla
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Leis Distributivas
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Leis Associativas
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p ∨ p ∧ q ≡ p Leis de Absorc¸a˜o
p ∧ (p ∨ q) ≡ p
¬(p ∧ q) ≡ ¬p ∨ ¬q Leis de De Morgan
¬(p ∨ q) ≡ ¬p ∧ ¬q
p ∨ ¬p ≡ T Leis de Negac¸a˜o
p ∧ ¬p ≡ F
Prof. Dr. Leandro Balby Marinho 18 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Equivaleˆncias Envolvendo Implicac¸a˜o
Equivaleˆncia
p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p
p ∨ q ≡ ¬p → q
p ∧ q ≡ ¬(p → ¬q)
¬(p → q) ≡ p ∧ ¬q
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
(p → r) ∧ (q → r) ≡ (p ∨ q)→ r
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q)→ r
Prof. Dr. Leandro Balby Marinho 19 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Utilizando Equivaleˆncias Lo´gicas
Exemplo 13: Mostre que ¬(p → q) ≡ p ∧ ¬q utilizando equivaleˆncias
lo´gicas.
Soluc¸a˜o:
¬(p → q) ≡¬(¬p ∨ q) (pela letra (b) Exerc´ıcio 2)
≡¬(¬p) ∧ ¬q (pela segunda lei de De Morgan)
≡p ∧ ¬q (pela negac¸a˜o dupla)
Prof. Dr. Leandro Balby Marinho 20 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 14
Mostre que ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q utilizando equivaleˆncias lo´gicas.
Soluc¸a˜o:
¬(p ∨ (¬p ∧ q)) ≡¬p ∧ ¬(¬p ∧ q) (pela segunda lei de De Morgan)
≡¬p ∧ [¬(¬p) ∨ ¬q] (pela primeira lei de De Morgan)
≡¬p ∧ (p ∨ ¬q) (pela negac¸a˜o dupla)
≡(¬p ∧ p) ∨ (¬p ∧ ¬q) (pela segunda lei distributiva)
≡F ∨ (¬p ∧ ¬q) (pela segunda lei da negac¸a˜o)
≡(¬p ∧ ¬q) ∨ F (pelas leis comutativas)
≡¬p ∧ ¬q (pela segunda lei da identidade)
Prof. Dr. Leandro Balby Marinho 21 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 15
Mostre que (p ∧ q)→ (p ∨ q) e´ uma tautologia.
Soluc¸a˜o:
(p ∧ q)→ (p ∨ q) ≡¬(p ∧ q) ∨ (p ∨ q) (letra (b) Exerc´ıcio 2)
≡(¬p ∨ ¬q) ∨ (p ∨ q) (primeira lei de De Morgan)
≡(¬p ∨ p) ∨ (¬q ∨ q) (leis associativas e comutativas)
≡T ∨ T (leis da negac¸a˜o)
≡T (lei da dominac¸a˜o)
Prof. Dr. Leandro Balby Marinho 22 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exerc´ıcio 3
Mostre que (p → q) ∧ (p → r) ≡ p → (q ∧ r) usando tabelas de
verdade e outras equivaleˆncias lo´gicas.
Prof. Dr. Leandro Balby Marinho 23 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Roteiro
1. Lo´gica Proposicional
2. Exemplos de Aplicac¸o˜es da Lo´gica Proposicional
3. Equivaleˆncias Lo´gicas
4. Lo´gica de Predicados
5. Regras de Infereˆncia
Prof. Dr. Leandro Balby Marinho 24 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Lo´gica de Predicados
I A lo´gica proposicional possui expressividade limitada, por
exemplo, as sentenc¸as:
“x > 3”,“Ha´ pelo menos dois amigos nessa sala”
na˜o podem ser expressadas atrave´s da lo´gica proposicional.
I A lo´gica de predicados permite expressar propriedades e
relac¸o˜es entre objetos.
I A afirmac¸a˜o “x > 3” acima tem duas partes:
1. o sujeito, aqui a varia´vel x ;
2. o predicado “e´ maior que 3”, que se refere a uma propriedade
do sujeito.
Prof. Dr. Leandro Balby Marinho 24 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Lo´gica de Predicados
I A lo´gica proposicional possui expressividade limitada, por
exemplo, as sentenc¸as:
“x > 3”,“Ha´ pelo menos dois amigos nessa sala”
na˜o podem ser expressadas atrave´s da lo´gica proposicional.
I A lo´gica de predicados permite expressar propriedades e
relac¸o˜es entre objetos.
I A afirmac¸a˜o “x > 3” acima tem duas partes:
1. o sujeito, aqui a varia´vel x ;
2. o predicado “e´ maior que 3”, que se refere a uma propriedade
do sujeito.
Prof. Dr. Leandro Balby Marinho 24 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Lo´gica de Predicados
I A lo´gica proposicional possui expressividade limitada, por
exemplo, as sentenc¸as:
“x > 3”,“Ha´ pelo menos dois amigos nessa sala”
na˜o podem ser expressadas atrave´s da lo´gica proposicional.
I A lo´gica de predicados permite expressar propriedades e
relac¸o˜es entre objetos.
I A afirmac¸a˜o “x > 3” acima tem duas partes:
1. o sujeito, aqui a varia´vel x ;
2. o predicado “e´ maior que 3”, que se refere a uma propriedade
do sujeito.
Prof. Dr. Leandro Balby Marinho 24 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Lo´gica de Predicados
I A lo´gica proposicional possui expressividade limitada, por
exemplo, as sentenc¸as:
“x > 3”,“Ha´ pelo menos dois amigos nessa sala”
na˜o podem ser expressadas atrave´s da lo´gica proposicional.
I A lo´gica de predicados permite expressar propriedades e
relac¸o˜es entre objetos.
I A afirmac¸a˜o “x > 3” acima tem duas partes:
1. o sujeito, aqui a varia´vel x ;
2. o predicado “e´ maior que 3”, que se refere a uma propriedade
do sujeito.
Prof. Dr. Leandro Balby Marinho 24 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Lo´gica de Predicados
I A lo´gica proposicional possui expressividade limitada, por
exemplo, as sentenc¸as:
“x > 3”,“Ha´ pelo menos dois amigos nessa sala”
na˜o podem ser expressadas atrave´s da lo´gica proposicional.
I A lo´gica de predicados permite expressar propriedades e
relac¸o˜es entre objetos.
I A afirmac¸a˜o “x > 3” acima tem duas partes:
1. o sujeito, aqui a varia´vel x ;
2. o predicado “e´ maior que 3”, que se refere a uma propriedade
do sujeito.
Prof. Dr. Leandro Balby Marinho 24 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Predicados
I Representados por func¸o˜es proposicionais da forma P(x).
I Quando x toma um valor no seu dom´ınio, P(x) vira uma
proposic¸a˜o.
I Uma afirmac¸a˜o envolvendo n varia´veis x1, x2, . . . , xn pode ser
denotada por
P(x1, x2, . . . , xn)
onde n representa a aridade do predicado.
I Por exemplo: P(x , y) :=“x e´ pai de y” ou Q(x , y , z) :=“x , y
e z estudam na mesma universidade.”
Prof. Dr. Leandro Balby Marinho 25 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplos
Exemplo 16: Seja P(x) a sentenc¸a “x > 3”. Quais os valores ver-
dade de P(4) e P(2) para o dom´ınio dos nu´meros inteiros?
Soluc¸a˜o: Como P(4) corresponde a “4 > 3”, enta˜o P(4) e´ verda-
deira. Ja´ P(2) e´ falsa, pois “2 < 3”.
Exerc´ıcio 4: Seja Q(x , y) a sentenc¸a “x = y + 3”. Determine os
valores verdade de Q(1, 2) e Q(3, 0) para o dom´ınio dos nu´meros
inteiros.
Prof. Dr. Leandro Balby Marinho 26 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplos
Exemplo 16: Seja P(x) a sentenc¸a “x > 3”. Quais os valores ver-
dade de P(4) e P(2) para o dom´ınio dos nu´meros inteiros?
Soluc¸a˜o: Como P(4) corresponde a “4 > 3”, enta˜o P(4) e´ verda-
deira. Ja´ P(2) e´ falsa, pois “2 < 3”.
Exerc´ıcio 4: Seja Q(x , y) a sentenc¸a “x = y + 3”. Determine os
valores verdade de Q(1, 2) e Q(3, 0) para o dom´ınio dos nu´meros
inteiros.
Prof. Dr. Leandro Balby Marinho 26 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplos
Exemplo 16: Seja P(x) a sentenc¸a “x > 3”. Quais os valores ver-
dade de P(4) e P(2) para o dom´ınio dos nu´meros inteiros?
Soluc¸a˜o: Como P(4) corresponde a “4 > 3”, enta˜o P(4) e´ verda-
deira. Ja´ P(2) e´ falsa, pois “2 < 3”.
Exerc´ıcio 4: Seja Q(x , y) a sentenc¸a “x = y + 3”. Determine os
valores verdade de Q(1, 2) e Q(3, 0) para o dom´ınio dos nu´meros
inteiros.
Prof. Dr. Leandro Balby Marinho 26 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Interpretac¸a˜o
Definic¸a˜o 9
Uma interpretac¸a˜o na lo´gica de predicados consiste em:
a) Uma colec¸a˜o de objetos chamado de dom´ınio da interpretac¸a˜o.
b) A especificac¸a˜o de uma propriedade dos objetos no dom´ınio
para cada predicado na expressa˜o.
c) A atribuic¸a˜o de um objeto particular no dom´ınio para cada
s´ımbolo constante na expressa˜o.
O valor lo´gico de um predicado depende da interpretac¸a˜o!
Prof. Dr. Leandro Balby Marinho 27 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 17
Determine o valor verdade de P(x) para as seguintes interpretac¸o˜es:
a) “x > 1” para todo x ∈ Z+.
b) “x e´ amarela” para todo x no conjunto de todas as flores.
Soluc¸a˜o:
a) Falso pois 1 6> 1
b) Falso pois nem todas as flores sa˜o amarelas.
Prof. Dr. Leandro Balby Marinho 28 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 17
Determine o valor verdade de P(x) para as seguintes interpretac¸o˜es:
a) “x > 1” para todo x ∈ Z+.
b) “x e´ amarela” para todo x no conjunto de todas as flores.
Soluc¸a˜o:
a) Falso pois 1 6> 1
b) Falso pois nem todas as flores sa˜o amarelas.
Prof. Dr. Leandro Balby Marinho 28 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Quantificadores
Avaliam a extensa˜o que um predicado e´ verdadeiro num intervalo de
elementos.
Sentenc¸a Quando verdadeira? Quando falsa?
∀x P(x) P(x) e´ verdadeira para
todo x .
Existe um x tal que
P(x) e´ falsa
∃x P(x) Existe um x tal que
P(x) e´ verdadeira
P(x) e´ falsa para todo x
Quando os elementos do dom´ınio sa˜o finitos e enumera´veis – digamos
x1, x2, . . . , xn – ∀x P(x) e´ o mesmo que a conjunc¸a˜o
P(x1) ∧ P(x2) ∧ . . . ∧ P(xn)
e ∃x P(x) e´ o mesmo que
P(x1) ∨ P(x2) ∨ . . . ∨ P(xn)
Prof. Dr. Leandro Balby Marinho 29 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplos
Exemplo 18: Seja P(x) a sentenc¸a “x2 > 0”. Determine o valor verdade
de ∀x P(x) para o dom´ınio dos nu´meros inteiros.
Soluc¸a˜o: Para provar que a sentenc¸a e´ falsa basta encontrarmos um
contra-exemplo. Como x2 = 0 quando x = 0, enta˜o x2 na˜o e´ maior que
zero quando x = 0.
Exerc´ıcio 5: Seja Q(x) a sentenc¸a “x2 > 10”. Determine o valor verdade
de ∃x Q(x) para todos os inteiros positivos na˜o maiores que 4.
Prof. Dr. Leandro Balby Marinho 30 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplos
Exemplo 18: Seja P(x) a sentenc¸a “x2 > 0”. Determine o valor verdade
de ∀x P(x) para o dom´ınio dos nu´meros inteiros.
Soluc¸a˜o: Para provar que a sentenc¸a e´ falsa basta encontrarmos um
contra-exemplo. Como x2 = 0 quando x = 0, enta˜o x2 na˜o e´ maior que
zero quando x = 0.
Exerc´ıcio 5: Seja Q(x) a sentenc¸a “x2 > 10”. Determine o valor verdade
de ∃x Q(x) para todos os inteiros positivos na˜o maiores que 4.
Prof. Dr. Leandro Balby Marinho 30 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplos
Exemplo 18: Seja P(x) a sentenc¸a “x2 > 0”. Determine o valor verdade
de ∀x P(x) para o dom´ınio dos nu´meros inteiros.
Soluc¸a˜o: Para provar que a sentenc¸a e´ falsa basta encontrarmos um
contra-exemplo. Como x2 = 0 quando x = 0, enta˜o x2 na˜o e´ maior que
zero quando x = 0.
Exerc´ıcio 5: Seja Q(x) a sentenc¸a “x2 > 10”. Determine o valor verdade
de ∃x Q(x) para todos os inteiros positivos na˜o maiores que 4.
Prof. Dr. Leandro Balby Marinho 30 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Escopo de Quantificadores
I Pareˆnteses e colchetes definem o escopo de um quantificador.
Por exemplo,
(∀x)[P(x)→ Q(x)] (1)
∀x P(x) ∨ Q(x) (2)
I Em (1) o escopo de (∀x) e´ P(x)→ Q(x).
I Em (2) o escopo de ∀x e´ P(x).
I Quando na˜o ha´ pareˆnteses a ordem de precedeˆncia dos
quantificadores e´ maior que todos os outros operadores.
Prof. Dr. Leandro Balby Marinho 31 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Varia´veis Livres
Varia´vel Livre
Uma varia´vel que na˜o esta´ no escopo de um quantificador e na˜o
possui valor determinado e´ dita varia´vel livre.
Exemplo 19: A varia´vel y e´ livre em
(∀x)[Q(x , y)→ (∃y)R(x , y)] (na primeira ocorreˆncia)
e
∃x(x + y = 1)
Prof. Dr. Leandro Balby Marinho 32 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Quantificadores Aninhados
Dois quantificadores sa˜o ditos aninhados se um esta´ no escopo do
outro.
Exemplo 20: A lei da comutatividade para a soma de reais pode
ser dada como:
∀x∀y(x + y = y + x)
Exerc´ıcio 6: Traduza a seguinte expressa˜o para o portugueˆs:
∀x∀y((x > 0) ∧ (y < 0)→ (xy < 0))
onde o x , y ∈ R
Prof. Dr. Leandro Balby Marinho 33 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Leis de De Morgan para Quantificadores
Negac¸a˜o Equivalente
¬∃x P(x) ∀x¬P(x)
¬∀x P(x) ∃x¬P(x)
Exemplo 20: Seja ∀x P(x) a sentenc¸a “Todo aluno nessa turma
cursou ICC.” Expresse a negac¸a˜o dessa sentenc¸a em portugueˆs.
Soluc¸a˜o: “Na˜o e´ o caso que todo aluno nessa turma cursou ICC”,
o que e´ equivalente a dizer “Ha´ um aluno nessa turma que na˜o
cursou ICC” e portanto ¬∀xP(x) ≡ ∃x¬P(x).
Prof. Dr. Leandro Balby Marinho 34 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Leis de De Morgan para Quantificadores
Negac¸a˜o Equivalente
¬∃x P(x) ∀x¬P(x)
¬∀x P(x) ∃x¬P(x)
Exemplo 20: Seja ∀x P(x) a sentenc¸a “Todo aluno nessa turma
cursou ICC.” Expresse a negac¸a˜o dessa sentenc¸a em portugueˆs.
Soluc¸a˜o: “Na˜o e´ o caso que todo aluno nessa turma cursou ICC”,
o que e´ equivalente a dizer “Ha´ um aluno nessa turma que na˜o
cursou ICC” e portanto ¬∀xP(x) ≡ ∃x¬P(x).
Prof. Dr. Leandro Balby Marinho 34 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Ordem dos Quantificadores
A ordem dos quantificadores importa na avaliac¸a˜o da expressa˜o.
Exemplo 21: Seja Q(x , y) a expressa˜o “x + y = 0”. Determine os
valores verdade de ∃y∀x Q(x , y) e ∀x∃y Q(x , y) para R.
Soluc¸a˜o: ∃y∀x Q(x , y) e´ falsa, pois na˜o existe um nu´mero y tal
que Q(x , y) seja verdadeira para todo x . Ja´ ∀x∃y Q(x , y) e´
verdadeira, pois para todo x existe um y tal que Q(x , y) seja
verdade, ou seja, y = −x .
Exerc´ıcio 6: Seja Q(x , y , z) a expressa˜o “x + y = z”. Determine
os valores verdade de ∀x∀y∃z Q(x , y , z) e ∃z∀x∀y Q(x , y , z), para
R.
Prof. Dr. Leandro Balby Marinho 35 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Ordem dos Quantificadores
A ordem dos quantificadores importa na avaliac¸a˜o da expressa˜o.
Exemplo 21: Seja Q(x , y) a expressa˜o “x + y = 0”. Determine os
valores verdade de ∃y∀x Q(x , y) e ∀x∃y Q(x , y) para R.
Soluc¸a˜o: ∃y∀x Q(x , y) e´ falsa, pois na˜o existe um nu´mero y tal
que Q(x , y) seja verdadeira para todo x . Ja´ ∀x∃y Q(x , y) e´
verdadeira, pois para todo x existe um y tal que Q(x , y) seja
verdade, ou seja, y = −x .
Exerc´ıcio 6: Seja Q(x , y , z) a expressa˜o “x + y = z”. Determine
os valores verdade de ∀x∀y∃z Q(x , y , z) e ∃z∀x∀y Q(x , y , z), para
R.
Prof. Dr. Leandro Balby Marinho 35 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Ordem dos Quantificadores
A ordem dos quantificadores importa na avaliac¸a˜o da expressa˜o.
Exemplo 21: Seja Q(x , y) a expressa˜o “x + y = 0”. Determine os
valores verdade de ∃y∀x Q(x , y) e ∀x∃y Q(x , y) para R.
Soluc¸a˜o: ∃y∀x Q(x , y) e´ falsa, pois na˜o existe um nu´mero y tal
que Q(x , y) seja verdadeira para todo x . Ja´ ∀x∃y Q(x , y) e´
verdadeira, pois para todo x existe um y tal que Q(x , y) seja
verdade, ou seja, y = −x .
Exerc´ıcio 6: Seja Q(x , y , z) a expressa˜o “x + y = z”. Determine
os valores verdade de ∀x∀y∃z Q(x , y , z) e ∃z∀x∀y Q(x , y , z), para
R.
Prof. Dr. Leandro Balby Marinho 35 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Ordem dos Quantificadores
A ordem dos quantificadores importa na avaliac¸a˜o da expressa˜o.
Exemplo 21: Seja Q(x , y) a expressa˜o “x + y = 0”. Determine os
valores verdade de ∃y∀x Q(x , y) e ∀x∃y Q(x , y) para R.
Soluc¸a˜o: ∃y∀x Q(x , y) e´ falsa, pois na˜o existe um nu´mero y tal
que Q(x , y) seja verdadeira para todo x . Ja´ ∀x∃y Q(x , y) e´
verdadeira, pois para todo x existe um y tal que Q(x , y) seja
verdade, ou seja, y = −x .
Exerc´ıcio 6: Seja Q(x , y , z) a expressa˜o “x + y = z”. Determine
os valores verdade de ∀x∀y∃z Q(x , y , z) e ∃z∀x∀y Q(x , y , z), para
R.
Prof. Dr. Leandro Balby Marinho 35 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Traduc¸a˜o
I Muitas declarac¸o˜es em Portugueˆs podem ser expressas na
lo´gica de predicados.
I Depois da traduc¸a˜o a sentec¸a fica mais precisa e pode ser
avaliada.
I Importante para especificac¸a˜o de sistemas.
Prof. Dr. Leandro Balby Marinho 36 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 22
Traduza “Todos os cachorros sa˜o leais” para a lo´gica de predicados.
Soluc¸a˜o: Assumindo o dom´ınio composto de todas as coisas, a expressa˜o
acima significa “Dada uma coisa, se e´ cachorro, enta˜o e´ leal”. Denotando,
C (x) := “x e´ um cachorro”
L(x) := “x leal”
A expressa˜o pode ser escrita como
(∀x)(C (x)→ L(x))
Por que na˜o (∀x)(C (x) ∧ L(x))?
Prof. Dr. Leandro Balby Marinho 37 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 22
Traduza “Todos os cachorros sa˜o leais” para a lo´gica de predicados.
Soluc¸a˜o: Assumindo o dom´ınio composto de todas as coisas, a expressa˜o
acima significa “Dada uma coisa, se e´ cachorro, enta˜o e´ leal”. Denotando,
C (x) := “x e´ um cachorro”
L(x) := “x leal”
A expressa˜o pode ser escrita como
(∀x)(C (x)→ L(x))
Por que na˜o (∀x)(C (x) ∧ L(x))?
Prof. Dr. Leandro Balby Marinho 37 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 22 cont.
Alternativamente, podemos considerar que todo o dom´ınio e´
formado por cachorros. Denotando,
L(x) := “x e´ leal”
A expressa˜o pode ser traduzida simplesmente por ∀x L(x)
Prof. Dr. Leandro Balby Marinho 38 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 23
Traduza “Todo aluno nessa turma estudou ca´lculo”.
Soluc¸a˜o: Assumindo o dom´ınio composto de todas as coisas, a expressa˜o
acima significa “Dada uma coisa, se e´ aluno, enta˜o estudou ca´lculo”. De-
notando,
A(x) := “x e´ um aluno”
C (x) := “x estudou ca´lculo”
A expressa˜o pode ser escrita como
(∀x)(A(x)→ C (x))
Por que na˜o (∀x)(A(x) ∧ C (x))?
Prof. Dr. Leandro Balby Marinho 39 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exerc´ıcio 7
Expresse as sentenc¸as a seguir em lo´gica de predicados. Assuma o
dom´ınio de todas as coisas.
“Algum aluno nessa turma vai ao Parque do Povo”
“Todo aluno nessa turma vai ao Parque do Povo ou Vila do Forro´”
Prof. Dr. Leandro Balby Marinho 40 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exerc´ıcio 8
Expresse as sentenc¸as a seguir em lo´gica de predicados para o
dom´ınio de todas as criaturas:
“Todos os leo˜es sa˜o maus”
“Alguns leo˜es na˜o bebem cafe´”
“Algumas criaturas ma´s na˜o bebem cafe´”
Prof. Dr. Leandro Balby Marinho 41 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Lo´gica Proposicional vs Lo´gica de Predicados
Proposic¸a˜o Composta Predicado Composto
Valor lo´gico Verdadeiro ou falso, dependendo
da configurac¸a˜o de valores das le-
tras proposicionais.
Verdadeiro, falso ou talvez se a
expressa˜o tiver uma varia´vel livre
sem valor lo´gico.
Sempre verdade Tautologia - verdadeiro para todas
as atribuic¸o˜es de valores lo´gicos.
Validade - verdadeiro para todas as
interpretac¸o˜es.
Metodologia Tabela-verdade para determinar se
uma proposic¸a˜o e´ uma tautologia.
Na˜o existe metodologia para de-
terminar se um predicado e´ va´lido.
Prof. Dr. Leandro Balby Marinho 42 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Roteiro
1. Lo´gica Proposicional
2. Exemplos de Aplicac¸o˜es da Lo´gica Proposicional
3. Equivaleˆncias Lo´gicas
4. Lo´gica de Predicados
5. Regras de Infereˆncia
Prof. Dr. Leandro Balby Marinho 43 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Argumentos Va´lidos
Definic¸a˜o 10
Um argumento e´ uma sequeˆncia de afirmac¸o˜es (premissas ou hipo´teses)
que terminam com uma conclusa˜o. Um argumento e´ dito va´lido se a
verdade das premissas implica na verdade da conclusa˜o.
Um argumento com as premissas p1, p2, . . . , pn e conclusa˜o q e´ va´lido
quando (p1 ∧ p2 ∧ . . . ∧ pn)→ q for uma tautologia. O argumento
abaixo, por exemplo,
p → q
p
∴ q
e´ va´lido pois ((p → q) ∧ p)→ q e´ uma tautologia (verifique isso).
Prof. Dr. Leandro Balby Marinho 43 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Algumas Regras de Infereˆncia Importantes
Regra de Infereˆncia Nome
p → q
p
∴ q Modus ponens
p → q
¬q
∴ ¬p Modus tollens
p → q
q → r
∴ p → r Silogismo hipote´tico
p ∨ q
¬p
∴ q Silogismo disjuntivo
p
∴ p ∨ q Adic¸a˜o
p ∧ q
∴ p Simplificac¸a˜o
p
q
∴ p ∧ q Conjunc¸a˜o
Prof. Dr. Leandro Balby Marinho 44 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exerc´ıcio 8
Que regras de infereˆncia sa˜o usadas nos argumentos abaixo?
a) “Cangurus vivem na Austra´lia e sa˜o marsupiais. Portanto,
cangurus sa˜o marsupiais.”
b) “Linda e´ uma o´tima nadadora. Se Linda e´ uma o´tima nadadora,
enta˜o ela pode trabalhar como salva-vidas. Portanto, Linda
pode trabalhar como salva-vidas.”
c) “Se chover hoje a Universidade vai fechar. A Universidade na˜o
esta´ fechada hoje. Portanto, na˜o choveu hoje.”
Prof. Dr. Leandro Balby Marinho 45 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Seqeˆncias de Demonstrac¸a˜o
Podemos usar uma sequeˆncia de demonstrac¸a˜o para provar a
validade de argumentos. A sequeˆncia tem a seguinte forma:
Passo Justificativa
1. p1 Hipo´tese
2. p2 Hipo´tese
3. p3 Inferida de (1) e (2)
4. p4 Hipo´tese
5. p5 Inferida de (3) e (4)
6. p6 Equivaleˆncia Lo´gica de (5)
...
Prof. Dr. Leandro Balby Marinho 46 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 23
Mostre que a conclusa˜o t pode ser deduzida das seguints hipo´teses:
(¬p ∧ q) ∧ (r → p) ∧ (¬r → s) ∧ (s → t)
Soluc¸a˜o:
Passo Justificativa
1. ¬p ∧ q Hipo´tese
2. ¬p Simplificac¸a˜o em (1)
3. r → p Hipo´tese
4. ¬r Modus tollens em (2) e (3)
5. ¬r → s Hipo´tese
6. s Modus ponens em (4) e (5)
7. s → t Hipo´tese
8. t Modus ponens em (6) e (7)
Prof. Dr. Leandro Balby Marinho 47 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 24
Prove que o seguinte argumento e´ va´lido:
a ∧ (b → c) ∧ [(a ∧ b)→ (d ∨ ¬c)] ∧ b → d
Passo Justificativa
1. a Hipo´tese
2. b → c Hipo´tese
3. (a ∧ b)→ (d ∨ ¬c) Hipo´tese
4. b Hipo´tese
5. c Modus ponens em (2) e (4)
6. a ∧ b Conjunc¸a˜o em (1) e (4)
7. d ∨ ¬c Modus ponens em (3) e (6)
8. ¬c ∨ d Comutatividade em (7)
9. c → d Equivalente a (8)
10. d Modus ponens em (5) e (9)
Prof. Dr. Leandro Balby Marinho 48 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exerc´ıcio 9
Prove que o seguinte argumento e´ va´lido:
(¬q → ¬p) ∧ p ∧ (q → r)→ r
Prof. Dr. Leandro Balby Marinho 49 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Fala´cias Comuns
Fala´cias parecem regras de infereˆncia, mas sa˜o baseadas em
contingeˆncias e na˜o tautologias.
Fala´cia Nome
[(p → q) ∧ q]→ p Afirmac¸a˜o da conclusa˜o
[(p → q) ∧ ¬p]→ ¬q Negac¸a˜o da conclusa˜o
Prof. Dr. Leandro Balby Marinho 50 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplos de Fala´cias
Exemplo 24: O argumento a seguir e´ uma fala´cia. “Se voceˆ fizer
todos os exerc´ıcios do livro texto, voceˆ aprendera´ matema´tica dis-
creta. Voceˆ aprendeu matema´tica discreta. Enta˜o, voceˆ fez todos os
exerc´ıcios do livro texto.”
Exemplo 25: O argumento a seguir e´ uma fala´cia. “Se voceˆ fizer
todos os exerc´ıcios do livro texto, voceˆ aprendera´ matema´tica dis-
creta. Voceˆ na˜o fez todos os exerc´ıcios do livro texto. Enta˜o, voceˆ
na˜o aprendeu matema´tica discreta.”
Prof. Dr. Leandro Balby Marinho 51 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Regras de Infereˆncia na Lo´gica de Predicados
I Regras de infereˆncia tambe´m podem ser aplicadas na lo´gica
de predicados.
I A abordagem e´ retirar os quantificadores, manipular as
expresso˜es predicadas, e depois coloca´-las no lugar.
Prof. Dr. Leandro Balby Marinho 52 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Particularizac¸a˜o Universal
Se P(x) e´ verdadeira para todo x no dom´ınio, enta˜o podemos no-
mear um elemento do dom´ınio por uma constante a tal que P con-
tinuara´ sendo verdadeira para essa constante.
Regra de Infereˆncia Nome
∀x P(x)
∴ P(a)
Particularizac¸a˜o Universal
Prof. Dr. Leandro Balby Marinho 53 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 26
Mostre que o seguinte argumento e´ va´lido: “Todos os homens sa˜o
mortais. So´crates e´ homem. Portanto, So´crates e´ mortal.”
Soluc¸a˜o: Seja H(x) a sentenc¸a “x e´ homem”, M(x) “x e´ mortal” e
s um s´ımbolo constante para So´crates. Enta˜o o argumento fica
[(∀x) (H(x)→ M(x)) ∧ H(s)]→ M(s)
e uma sequeˆncia de demonstrac¸a˜o e´
Passo Justificativa
1. (∀x) (H(x)→ M(x)) Hipo´tese
2. H(s)→ M(s) Particularizac¸a˜o Universal em (1)
3. H(s) Hipo´tese
4. M(s) Modus ponens em (2) e (3)
Prof. Dr. Leandro Balby Marinho 54 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 26
Mostre que o seguinte argumento e´ va´lido: “Todos os homens sa˜o
mortais. So´crates e´ homem. Portanto, So´crates e´ mortal.”
Soluc¸a˜o: Seja H(x) a sentenc¸a “x e´ homem”, M(x) “x e´ mortal” e
s um s´ımbolo constante para So´crates. Enta˜o o argumento fica
[(∀x) (H(x)→ M(x)) ∧ H(s)]→ M(s)
e uma sequeˆncia de demonstrac¸a˜o e´
Passo Justificativa
1. (∀x) (H(x)→ M(x)) Hipo´tese
2. H(s)→ M(s) Particularizac¸a˜o Universal em (1)
3. H(s) Hipo´tese
4. M(s) Modus ponens em (2) e (3)
Prof. Dr. Leandro Balby Marinho 54 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Particularizac¸a˜o Existencial
Se P(x) e´ verdadeira para algum x no dom´ınio, enta˜o podemos nomear
esse elemento
espec´ıfico atrave´s de uma constante tal que P continuara´
sendo verdadeira para essa constante.
Regra de Infereˆncia Nome Restric¸o˜es
∃x P(x)
∴ P(a) Particularizac¸a˜o Existencial A constante a na˜o pode tersido utilizada anteriormente
por alguma outra regra ou
hipo´tese.
Prof. Dr. Leandro Balby Marinho 55 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 27
Os seguintes passos seriam va´lidos em uma sequencia de demons-
trac¸a˜o
Passo Justificativa
1. ∀x (P(x)→ Q(x)) Hipo´tese
2. ∃yP(y) Hipo´tese
3. P(a) Particularizac¸a˜o Existencial em (2)
4. P(a)→ Q(a) Particularizac¸a˜o Existencial em (1)
5. Q(a) Modus Ponens em (3) e (4)
Note que se os passos (3) e (4) fossem invertidos, na˜o haveria
raza˜o para supor que esse a espec´ıfico e´ o que tem a propriedade P
como na hipo´tese (2).
Prof. Dr. Leandro Balby Marinho 56 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 27
Os seguintes passos seriam va´lidos em uma sequencia de demons-
trac¸a˜o
Passo Justificativa
1. ∀x (P(x)→ Q(x)) Hipo´tese
2. ∃yP(y) Hipo´tese
3. P(a) Particularizac¸a˜o Existencial em (2)
4. P(a)→ Q(a) Particularizac¸a˜o Existencial em (1)
5. Q(a) Modus Ponens em (3) e (4)
Note que se os passos (3) e (4) fossem invertidos, na˜o haveria
raza˜o para supor que esse a espec´ıfico e´ o que tem a propriedade P
como na hipo´tese (2).
Prof. Dr. Leandro Balby Marinho 56 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Generalizac¸a˜o Universal
Se a representar um elemento arbitra´rio no dom´ınio que tem a propriedade
P, enta˜o podemos generalizar que todo elemento no conjunto universo tem
a propriedade P.
Regra de Infereˆncia Nome Restric¸o˜es
P(a) para um a arbitra´rio
∀x P(x) Generalizac¸a˜o Universal P(a) na˜o pode ter si-do deduzida de nenhuma
hipo´tese na qual x e´ uma
varia´vel livre.
Prof. Dr. Leandro Balby Marinho 57 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 28
Mostre que
(∀x) [P(x)→ Q(x)] ∧ ∀x P(x)→ ∀x Q(x)
Passo Justificativa
1. (∀x) (P(x)→ Q(x)) Hipo´tese
2. ∀x P(x) Hipo´tese
3. P(a)→ Q(a) Particularizac¸a˜o Universal em (1)
4. P(a) Particularizac¸a˜o Universal em (2)
5. Q(a) Modus Ponens em (3) e (4)
6. ∀x Q(x) Generalizac¸a˜o Universal em (5)
Prof. Dr. Leandro Balby Marinho 58 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Generalizac¸a˜o Existencial
A ideia e´ que se algo e´ nomeado como possuindo a propriedade P, enta˜o
exsite alguma coisa com a propriedade P.
Regra de Infereˆncia Nome Restric¸o˜es
P(a)
∃x P(x) Generalizac¸a˜o Existencial Para ir de P(a) a ∃x P(x), xna˜o pode aparecer em P(a).
Prof. Dr. Leandro Balby Marinho 59 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 29
Mostre o argumento ∀x P(x)→ ∃x P(x)
Passo Justificativa
1. ∀x P(x) Hipo´tese
2. P(a) Particularizac¸a˜o Universal (1)
3. ∃x P(x) Generalizac¸a˜o Existencial em (2)
Prof. Dr. Leandro Balby Marinho 60 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exemplo 30
Prove o argumento (∀x) [P(x) ∧ Q(x)]→ ∀x P(x) ∧ ∀x Q(x)
Passo Justificativa
1. (∀x)[P(x) ∧ Q(x)] Hipo´tese
2. P(x) ∧ Q(x) Particularizac¸a˜o Universal (1)
3. P(x) Simplificac¸a˜o em (2)
4. Q(x) Simplificac¸a˜o em (2)
5. ∀x P(x) Generalizac¸a˜o Universal em (3)
6. ∀x Q(x) Generalizac¸a˜o Universal em (4)
7. ∀x P(x) ∧ ∀x Q(x) Conjunc¸a˜o em (5) e (6)
Prof. Dr. Leandro Balby Marinho 61 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Exerc´ıcio 10
Use regras de infereˆncia para mostrar que o seguinte argumento e´
va´lido: “Alguns alunos sa˜o mu´sicos. Todos os mu´sicos sa˜o sens´ıveis.
Portanto, alguns alunos sa˜o sens´ıveis.” Assumindo o dom´ınio de
todas as coisas.
Prof. Dr. Leandro Balby Marinho 62 / 63 UFCG CEEI
Lo´gica Proposicional Exemplos de Aplicac¸o˜es Equivaleˆncias Lo´gicas Lo´gica de Predicados Regras de Infereˆncia
Refereˆncias
Keneth H. Rosen. Discrete Mathematics and Its Applications.
Sexta Edic¸a˜o. McGRAW-HILL International Edition, 2007.
Judith L. Gersting. Fundamentos Matema´ticos para a Cieˆncia
da Computac¸a˜o. Quinta Edic¸a˜o. LTC, 2004.
Prof. Dr. Leandro Balby Marinho 63 / 63 UFCG CEEI
	1. Lógica Proposicional
	2. Exemplos de Aplicações da Lógica Proposicional
	3. Equivalências Lógicas
	4. Lógica de Predicados
	5. Regras de Inferência