Aula02 Logica de Proposicoes FTC

Prévia do material em texto

Fundamentos de Teoria da 
Computação
Lógica de Proposições
Rodrigo Yoshikawa Oeiras
Universidade Federal da Grande Dourados
Faculdade de Ciências Exatas e Tecnologia
Curso de Bacharelado em Sistemas de Informação
● A lógica proposicional é sistema formal que usa 
as FBFs proposicionais*.
● As proposições em forma simbólica são as FBFs 
proposicionais*.
Introdução – Lógica proposicional
FBF* Fórmula Bem Formulada
Proposição* É uma sentença que é falsa ou verdadeira.
*Judith L. Gersting, Fundamentos Matemáticos para a Ciência da Computação. 5Th ed.
● Um argumento em forma simbólica pode ser 
escrita como:
 P1 P˄ P 2 ... P˄ P ˄ P n→Q 
● Os elementos Pi e Q representam FBFs. Escritos 
desta forma, os Pi são hipóteses e Q é a 
conclusão do argumento. 
Introdução
● Quando o argumento é válido?
● Informalmente poderíamos dizer que Q é uma 
conclusão lógica de P1 … Pn, sempre que a 
verdade das proposições P1 … Pn implica na 
verdade de Q.
● Formalmente o argumento é válido quando:
P1 P˄ P 2 ... P˄ P ˄ P n→Q 
● for verdadeiro.
Introdução
Em geral, pensando no argumento, estamos preocupados com o que acontece quando 
todas as hipóteses são verdadeiras e estamos interessados quando o condicional do 
argumento é verdadeiro baseado na relação entre conclusão e hipótese*.
*Judith L. Gersting, Fundamentos Matemáticos para a Ciência da Computação. 5Th ed.
George Washington foi o primeiro presidente dos EUA. 
Thomas Jefferson escreveu a Declaração de 
Independência. Portanto, todo o dia tem 24 horas.
Exemplo 
George Washington foi o primeiro presidente dos EUA. 
Thomas Jefferson escreveu a Declaração de 
Independência. Portanto, todo o dia tem 24 horas.
Hipóteses:
1. George Washington foi o primeiro presidente dos EUA. 
2. Thomas Jefferson escreveu a Declaração de Independência.
Conclusão:
 todo o dia tem 24 horas.
Exemplo 
George Washington foi o primeiro presidente dos EUA. 
Thomas Jefferson escreveu a Declaração de 
Independência. Portanto, todo o dia tem 24 horas.
Observe as hipóteses e a conclusão são verdadeiras 
isoladamente, ie, não há uma relação entre P1 e P2 
com Q.
Em outras palavras, qual a relação entre o dia ter 24 
horas e a presidência dos EUA e a escrita da 
declaração de independência?
Exemplo 
● Estamos interessados em um argumento válido que 
é verdadeiro devido a sua estrutura interna.
● Assim,
Def. A FBF proposicional P1 P˄ P 2 ... P˄ P ˄ P n→Q é 
um argumento válido quando for uma tautologia
Definição de Argumento Válido
● Se George Washington foi o primeiro presidente dos 
EUA, então John Adams foi o primeiro vice-
presidente. George Washington foi o primeiro 
presidente dos EUA. Portanto, John Adams foi o 
primeiro vice-presidente.
Exemplo 
● Hipóteses:
1. Se George Washington foi o primeiro presidente dos 
EUA(A), então John Adams foi o primeiro vice-presidente(B). 
2. George Washington foi o primeiro presidente dos EUA(A). 
● Conclusão:
Portanto, John Adams foi o primeiro vice-presidente(B).
● Forma simbólica:
(A → B) ^ A → B
Exemplo 
● Neste exemplo observamos que o argumento é 
válido e podemos notar que a conclusão segue das 
hipóteses.
● Essa forma de argumento é conhecido como 
modens pones (método da afirmação – do latim) é 
uma regra de raciocínio usada na lógica 
proposicional.
(A → B) ^ A → B
Exemplo 
● Tabela verdade.
● Algoritmo.
● Lógica proposicional.
Verificar Tautologia?
Def. Um algoritmo é um conjunto de instruções 
que podem ser executadas mecanicamente em 
um tempo finito de modo a resolver algum 
problema.
Algoritmo
ALGORITMO TestaTautologia
Algoritmo
ALGORITMO TestaTautologia
Algoritmo
ALGORITMO TestaTautologia
Algoritmo
Continua ...
A lógica formal usa um sistema regras de dedução que 
modificam uma FBF de modo a preservar o valor lógico.
Usa-se as regras de dedução nas hipóteses P1 … Pn para obter 
a conclusão Q.
O sistema da lógica proposicional é um sistema correto e 
completo, isso significa que os argumentos válidos, e apenas 
estes, são demonstráveis.
Lógica Proposicional
P1 P˄ P 2 ... P˄ P ˄ P n→Q 
Correto: o argumento é uma tautologia.
Completo: o condicional é uma tautologia demonstrável.
Argumento válido: Tem a forma forma de uma FBF, P1^...^Pn→Q, que é 
uma tautologia.
O raciocínio usado na lógica proposicional pode ser aplicado no 
dia-a-dia e forma uma base para o raciocínio lógico em 
computação.
Embora a lógica proposicional pareça um sistema mecânico de 
aplicação de regras, mas a maneira de pensar ao se usar estas 
regras torna-se parte da pessoa que as praticou e esta pessoa 
poderá chegar a conclusões lógicas e reconhecer argumentos 
inválidos por conta própria. 
Lógica Proposicional
● Uma sequência de demonstração em lógica 
proposicional é uma sequência de FBFs nas quais 
algumas são hipóteses e outras são outras FBFs que 
são o resultado da aplicação das regras de dedução 
do sistema formal.
Sequência de demonstração
● Suponha que temos a seguinte FBF: 
A’ ^ B ^ [B→(A C)]→C˅C)]→C
● A sequência de demonstração seria assim:
Sequência de demonstração
 1. A’ P1 (hip)
2. B P2 (hip)
3. B→(A C) ˅C)]→C P3 (hip)
4. A C˅C)]→C
5. (A’)’ C˅C)]→C
6. A'→C 
7. C Q
Obtidas pelas
Regras de 
dedução
● Nas deduções, usamos dois tipos de regras: as 
regras de equivalências e as regras de inferência. 
● As regras de equivalências dizem se determinados 
pares de FBFs são equivalentes (já vimos estas 
regras anteriormente). Neste caso, a mudança de 
uma proposição numa FBF não altera o valor lógico 
da proposição.
Exemplo: (P→Q) ↔ (P’ ˅C)]→C Q)
Verificar se é uma tautologia 
Lógica proposicional(Regras de dedução)
● (P→Q) ↔ (P’ ˅C)]→C Q)
Exemplo: (P→Q) ↔ (P’ ˅C)]→C Q)
P Q P → Q P’ P’ Q˅C)]→C (P→Q) ↔ (P’ Q)˅C)]→C
V V V F V V
V F F F F V
F V V V V V
F F V V V V
Logo são equivalentes.
● (P→Q) ↔ (P’ ˅C)]→C Q)
● Qual é a negação de sentença abaixo?
Se a comida é boa, então o serviço é excelente.
(Obs: exercício da aula passada.)
Exemplo: (P→Q) ↔ (P’ ˅C)]→C Q)
● (P→Q) ↔ (P’ ˅C)]→C Q)
● Qual é a negação de sentença abaixo?
Se a comida é boa, então o serviço é excelente.
(P → Q) ↔ (P’ ˅C)]→C Q)
Exemplo: (P→Q) ↔ (P’ ˅C)]→C Q)
● (P→Q) ↔ (P’ ˅C)]→C Q)
● Qual é a negação de sentença abaixo?
Se a comida é boa, então o serviço é excelente.
(P’ ˅C)]→C Q)
Fazendo a negação:
(P’ ˅C)]→C Q)’
P’’ ^ Q’
P ^ Q’
A comida é boa, mas o serviço é ruim.
Exemplo: (P→Q) ↔ (P’ ˅C)]→C Q)
de Morgan
(FCC-2013) - Ao se admitir por verdadeira a 
declaração “Se Paulo é alto, então Gabriela não é 
alta”, conclui-se, de maneira correta e necessária, 
que se:
a) Gabriela é alta, então Paulo não é alto. 
b) Gabriela é alta, então Paulo é alto. 
c) Gabriela não é alta, então Paulo não é alto. 
d) Gabriela não é alta, então Paulo é Gabriela. 
e) Paulo não é alto, então Gabriela é maior que 
Paulo.
GABARITOS: A
Exemplo: (P→Q) ↔ (P’ ˅C)]→C Q)
● FBFs equivalentes
Tabelas de regras de equivalências
Expressão Equivalente a Nome/Abreviação da Regra
P Q˅C)]→C
P Q˄ P
Q P˅C)]→C
Q P˄ P
Comutatividade-com
(P Q) R˅C)]→C ˅C)]→C
(P Q) R˄ P ˄ P
P (Q R)˅C)]→C ˅C)]→C
P (Q R)˄ P ˄ P
Associatividade-ass
(P Q)’˅C)]→C
(P Q)’˄ P
P’ Q’˄ P
P’ Q’˅C)]→C
Leis de De Morgan – De Morgan
P→Q P’ Q˅C)]→C Condicional - cond
P (P’)’ Dupla negação - dn
P↔Q (P→Q) (Q→P)˄ P Def. de equivalência - equi
● Se uma ou mais FBFs estão presentas na sequência de 
demonstração, então podemos adicionar uma nova FBF 
na sequência substituindo as anteriorespelas FBFs 
correspondentes na segunda coluna.
Tabela de Regras de Inferência
De Podemos Deduzir Nome/Abreviação da Regra
P , P→Q Q Modus pones – mp
P→Q , Q’ P’ Modus tollens – mt
P , Q P Q˄ P Conjunção – conj
P Q˄ P P , Q Simplificação – simp
P P Q˅C)]→C Adição - ad
● Considere que A e A→(B C) ˄ P são hipóteses de algum 
argumento. Logo, podemos ter como conclusão 
(B C).˄ P
● Vamos representar os passos dessa dedução 
abaixo.
Exemplo 1
1) A
2) A→(B C)˄C)
3) (B C) ˄C)
Hipótese 1
Hipótese 2
1,2, mp
● Considere que A e A→(B C) são hipóteses de algum ˄ P
argumento. Logo, podemos ter como conclusão 
(B C).˄ P
● Vamos representar os passos dessa dedução 
abaixo.
Exemplo 1
1) A
2) A→(B C)˄C)
3) (B C) ˄C)
Hipótese 1
Hipótese 2
1,2, mp
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P = A
Q = B C˄ P
1. P
2. P→Q
3. Q 
● É dado:
1) (A B’)→C hipótese ˄ P
2) C’ hipótese 
Qual será o passo 3) da dedução?
Exemplo 2
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
● É dado:
1) (A B’)→C hipótese ˄ P
2) C’ hipótese 
Qual será o passo 3) da dedução ?
Exemplo 2
De Podemos Deduzir Nome/Abreviação da Regra
P→Q,Q’ P’ Modus tollens – mt
● É dado:
1) (A B’)→C hipótese ˄ P
2) C’ hipótese
3) (A B’)’ 1,2,mt˄ P
Exemplo 2
● Mostre que A (B→C) [(A B)→(D C’)] B→D ˄ P ˄ P ˄ P ˅C)]→C ˄ P é válida
● A FBF a esquerda tem que fornecer como resultado 
o D. 
Exercício P1 P˄ P 2 ... P˄ P ˄ P n→Q 
● Mostre que A (B→C) [(A B)→(D C’)] B→D ˄ P ˄ P ˄ P ˅C)]→C ˄ P é válida
Exercício P1 P˄ P 2 ... P˄ P ˄ P n→Q 
Expressão Equivalente a Nome/Abreviação da Regra
P Q˅C)]→C
P Q˄ P
Q P˅C)]→C
Q P˄ P
Comutatividade-com
(P Q) R˅C)]→C ˅C)]→C
(P Q) R˄ P ˄ P
P (Q R)˅C)]→C ˅C)]→C
P (Q R)˄ P ˄ P
Associatividade-ass
(P Q)’˅C)]→C
(P Q)’˄ P
P’ Q’˄ P
P’ Q’˅C)]→C
Leis de De Morgan – De Morgan
P→Q P’ Q˅C)]→C Condicional - cond
P (P’)’ Dupla negação - dn
P↔Q (P→Q) (Q→P)˄ P Def. de equivalência - equi
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
● A (B→C) [(A B)→(D C’)] B˄ P ˄ P ˄ P ˅C)]→C ˄ P →D
● Logo, a ideia é mostrar que do lado esquerdo da 
FBF chegamos ao lado direito.
● Fazemos isso usando a tabela de inferências.
Exercício - solução
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(D C’)˄ P ˅C)]→C
4) B
Usar a 3). 
Preciso de (A B), mas não tem nas hipóteses 1 a 4˄ P .
Exercício - solução
Tem D
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(D C’)˄ P ˅C)]→C
4) B
Exercício - solução
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(D C’)˄ P ˅C)]→C
4) B
5) (A B˄ P ) 1,4, conj
Preciso de isolar (D C’).˅C)]→C
Exercício - solução
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(˄ P D C’˅C)]→C )
4) B
5) (A B) 1,4, conj˄ P
Preciso de isolar (D C’).˅C)]→C
Exercício - solução
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(D C’)˄ P ˅C)]→C
4) B
5) (A B) 1,4, conj˄ P
6) (D C’) 3,5,mp˅C)]→C
Exercício - solução
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(D C’)˄ P ˅C)]→C
4) B
5) (A B) 1,4, conj˄ P
6) (D C’) 3,5,mp˅C)]→C
Não tem regra na tabela de inferência!
Exercício - solução
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(D C’)˄ P ˅C)]→C
4) B
5) (A B) 1,4, conj˄ P
6) (D C’) 3,5,mp˅C)]→C
Na tabela de equivalência tem! 
Exercício - solução
D C’=C’ D˅C)]→C ˅C)]→C
Fazendo P=C e Q=D, eu tenho que 
C’ D é análoga a P’ Q.˅C)]→C ˅C)]→C
Eu tenho que D C’=C’ D= C→D˅C)]→C ˅C)]→C
Expressão Equivalente a Nome/Abreviação da Regra
P Q˅C)]→C
P Q˄ P
Q P˅C)]→C
Q P˄ P
Comutatividade-com
(P Q) R˅C)]→C ˅C)]→C
(P Q) R˄ P ˄ P
P (Q R)˅C)]→C ˅C)]→C
P (Q R)˄ P ˄ P
Associatividade-ass
(P Q)’˅C)]→C
(P Q)’˄ P
P’ Q’˄ P
P’ Q’˅C)]→C
Leis de De Morgan – De Morgan
P→Q P’ Q˅C)]→C Condicional - cond
P (P’)’ Dupla negação - dn
P↔Q (P→Q) (Q→P)˄ P Def. de equivalência - equi
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(D C’)˄ P ˅C)]→C
4) B
5) (A B) 1,4, conj˄ P
6) (D C’) 3,5,mp˅C)]→C
7) (C→D) equivalência (com e cond)
Exercício - solução
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(D C’)˄ P ˅C)]→C
4) B
5) (A B) 1,4, conj˄ P
6) (D C’) 3,5,mp˅C)]→C
7) (C→D) equivalência (com e cond)
Só falta o C para determinar o D usando a regra mp
Exercício - solução
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(D C’)˄ P ˅C)]→C
4) B
5) (A B) 1,4, conj˄ P
6) (D C’) 3,5,mp˅C)]→C
7) (C→D) equivalência (com e cond)
8) C 2,4,mp
Só falta o C para determinar o D usando a regra mp
Exercício - solução
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
P=B
Q=C
Eu tenho que P e P→Q é 
análogo a B e B→C.
● A (B→C) [(A B)→(D C’)] B→D˄ P ˄ P ˄ P ˅C)]→C ˄ P
● Desta forma temos as hipóteses:
1) A
2) (B→C)
3) (A B)→(D C’)˄ P ˅C)]→C
4) B
5) (A B) 1,4, conj˄ P
6) (D C’) 3,5,mp˅C)]→C
7) (C→D) equivalência (com e cond)
8) C 2,4,mp
9) D 7,8,mp 
Exercício - solução
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
FIM
P=C
Q=D
Eu tenho que P e P→Q é 
análogo a C e C→D.
 Prove a validade A’ (A B)→B˄ P ˅C)]→C
Exercício 2
Expressão Equivalente a Nome/Abreviação da Regra
P Q˅C)]→C
P Q˄ P
Q P˅C)]→C
Q P˄ P
Comutatividade-com
(P Q) R˅C)]→C ˅C)]→C
(P Q) R˄ P ˄ P
P (Q R)˅C)]→C ˅C)]→C
P (Q R)˄ P ˄ P
Associatividade-ass
(P Q)’˅C)]→C
(P Q)’˄ P
P’ Q’˄ P
P’ Q’˅C)]→C
Leis de De Morgan – De Morgan
P→Q P’ Q˅C)]→C Condicional - cond
P (P’)’ Dupla negação - dn
P↔Q (P→Q) (Q→P)˄ P Def. de equivalência - equi
De Podemos Deduzir Nome/Abreviação daRegra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
● Use lógica proposicional para provar os 
argumentos:
a) [(A B’)→C] (C→D) A→D˅C)]→C ˄ P ˄ P
b) (A→B) [A→(B→C)] A→C ˄ P ˄ P (13)
Exercício 3
● Use lógica proposicional para provar os 
argumentos:
a) [(A B’)→C] (C→D) A→D˅C)]→C ˄ P ˄ P
b) (A→B) [A→(B→C)] A→C ˄ P ˄ P (13)
Exercício 3
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
Expressão Equivalente a Nome/Abreviação da Regra
P Q˅C)]→C
P Q˄ P
Q P˅C)]→C
Q P˄ P
Comutatividade-com
(P Q) R˅C)]→C ˅C)]→C
(P Q) R˄ P ˄ P
P (Q R)˅C)]→C ˅C)]→C
P (Q R)˄ P ˄ P
Associatividade-ass
(P Q)’˅C)]→C
(P Q)’˄ P
P’ Q’˄ P
P’ Q’˅C)]→C
Leis de De Morgan – De Morgan
P→Q P’ Q˅C)]→C Condicional - cond
P (P’)’ Dupla negação - dn
P↔Q (P→Q) (Q→P)˄ P Def. de equivalência - equi
● Dado o seguinte argumento:
P1 ^ P2 ^ … ^ Pn → (R → S )
● O método dedutivo permite adicionar R como 
uma hipótese adicional para depois inferir S. 
P1 ^ P2 ^ … ^ Pn ^ R → S 
Método Dedutivo
● Use a lógica proposicional para provar os 
seguinte argumento:
[A →(A → B) ] → (A → B)
Exercício
Exercícios
1. A '→(A→B)
2.(A '→B ' )∧(A→C)→(B→C )
3.(A '→B)∧(B→C )∧(C→D)→(A '→D)
4.(A∨B)∧(A→C )∧(B→C )→C
5.(P→Q)∧(P'→Q)→Q
Prove usando lógica de predicados e usando a sequencia de demonstração.
Exercícios
De Podemos Deduzir Nome/Abreviação da Regra
P,P→Q Q Modus pones – mp
P→Q,Q’ P’ Modus tollens – mt
P,Q P Q˄ P Conjunção – conj
P Q˄ P P,Q Simplificação – simp
P P Q˅C)]→C Adição - ad
Expressão Equivalente a Nome/Abreviação da Regra
P Q˅C)]→C
P Q˄ P
Q P˅C)]→C
Q P˄ P
Comutatividade-com
(P Q) R˅C)]→C ˅C)]→C
(P Q) R˄ P ˄ P
P (Q R)˅C)]→C ˅C)]→C
P (Q R)˄ P ˄ P
Associatividade-ass
(P Q)’˅C)]→C
(P Q)’˄ P
P’ Q’˄ P
P’ Q’˅C)]→C
Leis de De Morgan – De Morgan
P→Q P’ Q˅C)]→C Condicional - cond
P (P’)’ Dupla negação - dn
P↔Q (P→Q) (Q→P)˄ P Def. de equivalência - equi
1. A '→(A→B)
2.(A '→B ' )∧(A→C)→(B→C )
3.(A '→B)∧(B→C )∧(C→D)→(A '→D)
4.(A∨B)∧(A→C )∧(B→C )→C
5.(P→Q)∧(P'→Q)→Q
Exercícios
6.(P∨(Q∧R))∧(R '∨S)∧(S→T )→(T→P)
Prove usando lógica de predicados e usando a sequencia de demonstração.
FIM
	Slide 1
	Slide 2
	Lógica proposicional
	Slide 4
	Exemplo
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Exemplo
	Slide 20
	Slide 21
	Sequência de demonstração
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Lógica proposicional Regras de dedução _clipboard1
	Lógica proposicional Regras de dedução
	Exemplo 1_clipboard2
	Exemplo 1
	Exemplo 2_clipboard3
	Exemplo 2_clipboard4
	Exemplo 2
	Slide 38
	Exemplo 3_clipboard5
	Exemplo 3_clipboard6
	Exemplo 3_clipboard7
	Exemplo 3_clipboard8
	Exemplo 3_clipboard9
	Exemplo 3_clipboard10
	Exemplo 3_clipboard11
	Exemplo 3_clipboard12
	Exemplo 3_clipboard13
	Exemplo 3_clipboard14
	Exemplo 3_clipboard15
	Exemplo 3_clipboard16
	Exemplo 3
	Exercício
	Exercícios 06
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60