Apostila-parte02

Prévia do material em texto

TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.: Gleide Nolasco 
Pág. 15 
3. PROCESSOS DE INFERÊNCIA 
3.1. Implicação Lógica 
Considere P e Q proposições compostas. Podemos dizer que uma proposição P(p, q, r,...) 
implica logicamente uma proposição Q(p, q, r,...), se Q é verdadeira todas as vezes que P 
é verdadeira, ou seja, se não ocorre P(p, q, r, ...) e Q(p, q, r, ...) com valores lógicos 
simultâneos respectivamente V e F em uma mesma linha. 
Notação: P(p, q, r, ...) ⇒ Q(p, q, r, ...) 
 P ⇒ Q (P implica Q) 
Exemplos: 
� p ^ q ⇒⇒⇒⇒ p v q e p ^ q ⇒⇒⇒⇒ p ↔ q 
Tabelas-verdade das proposições: p ^ q, p v q, p ↔ q 
 
p q p ^ q p v q p ↔ q 
V V V V V 
V F F V F 
F V F V F 
F F F F V 
A proposição “p ^ q“ é verdadeira(V) somente na linha 1 e, nesta linha, as proposições “p 
v q“ e “ p ↔ q “ também são verdadeiras(V). Logo, a primeira proposição implica cada uma 
das outras duas proposições. 
� p ↔ q ⇒⇒⇒⇒ p → q e p ↔ q ⇒⇒⇒⇒ q → p 
Tabelas-verdade das proposições: p ↔ q, p → q e q→ p 
 
p q p ↔ q p → q q → p 
V V V V V 
V F F F V 
F V F V F 
F F V V V 
A proposição p ↔ q é verdadeira nas linhas 1 e 4 e nestas linhas as outras duas proposições 
também são verdadeiras. Logo, a primeira proposição implica cada uma das outras duas 
proposições. 
3.1.1. Propriedades da Implicação Lógica 
À relação de implicação lógica entre proposições aplica-se as propriedades Reflexiva(R) e 
Transitiva(T), isto é, simbolicamente: 
Reflexiva: Se 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, ...) 
3.1.2. Regras de Adição e Simplificação para Implicações Lógicas 
Regra de Adição: Ocorre quando a partir de uma proposição simples temos uma 
implicação formada por duas proposições simples através da adição. (Utiliza-se ^ ou v). 
 
TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.: Gleide Nolasco 
Pág. 16 
 
 
 
 
 
 
 
Conclusão: p ⇒⇒⇒⇒ p v q, p ⇒⇒⇒⇒ q v p 
Regra de Simplificação: Ocorre quando a partir de uma proposição formada por duas 
proposições simples encontramos uma implicação formada por uma proposição. (Utiliza-se 
^ ou v) 
Exemplos: 
 
 
 
 
 
 
 
 
Conclusão: p ^ q ⇒⇒⇒⇒ q, q ^ p ⇒⇒⇒⇒ q 
 
p q p v q ~p (p v q) ^ ~p 
V V V F F 
V F V F F 
F V V V V 
F F F V F 
Conclusão: (p v q) ^ ~p ⇒⇒⇒⇒ q 
3.1.3. Silogismo 
Silogismo Disjuntivo 
Permite que a partir de uma proposição formada por algumas proposições (que utilizam ^ e 
v) encontramos uma implicação formada por uma proposição. 
Exemplo: 
 
A proposição (p v q) ^ ~p é verdadeira somente na linha 3, linha em que a proposição q é 
verdadeira. Logo, a implicação lógica pode ser: (p v q) ^ ~p ⇒⇒⇒⇒ q 
p q p v q ~p (p v q ) ^ ~ p (p v q ) ^ ~ q
V V V F F F
V F V F F V
F V V V V F
F F F V F F
p q p v q q v p 
V V V V 
V F V V 
F V V V 
F F F F 
 
 
 
 
 
 
p q p ^ q q ^ p 
V V V V 
V F F F 
F V F F 
F F F F 
 
 
 
TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.: Gleide Nolasco 
Pág. 17 
A proposição (p v q) ^ ~q é verdadeira somente na linha 2, linha em que a proposição p é 
verdadeira. Logo, a implicação lógica pode ser: (p v q) ^ ~q ⇒⇒⇒⇒ p 
Silogismo Modus Ponens: 
O argumento tem duas premissas. A primeira premissa é a condição "se - então", 
nomeadamente (P → Q) e a segunda premissa é que P é verdadeiro. Destas duas premissas 
pode ser logicamente concluído que Q tem de ser também verdadeiro. 
Exemplo: 
(p → q) ^ p ⇒⇒⇒⇒ q 
p q p → q (p → q) ^ p 
V V V V 
V F F F 
F V V F 
F F V F 
Silogismo Modus Tollens: 
O argumento tem duas premissas. A primeira premissa é a condição se-então, 
nomeadamente que P implica Q. A segunda premissa é que Q é falso. Destas duas 
premissas pode ser logicamente concluído que P tem de ser falso. 
Exemplo: 
(p→ q) ^ ~q ⇒⇒⇒⇒ ~p 
p q ~q p → q (p → q) ^ ~q ~p 
V V F V F F 
V F V F F F 
F V F V F V 
F F V V V V 
3.1.4. Tautologia e Implicação Lógica 
P(p, q, r, …) ⇒ Q(p, q, r, …), se somente se P(p, q, r, …) ⇒⇒⇒⇒ Q(p, q, r, …) 
P Q P → Q 
V V V 
V F F 
F V V 
F F V 
3.1.5. Silogismo Hipotético 
Se a primeira proposição implica na segunda e a segunda implica na terceira, então a 
primeira proposição implica na terceira. 
Portanto, toda IMPLICAÇÃO LÓGICA 
corresponde a uma CONDICIONAL 
TAUTOLÓGICA 
TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.: Gleide Nolasco 
Pág. 18 
(p → q) ^ (q → r) ⇒⇒⇒⇒ (p → r) 
p q r p → q q → r (p → q) ^ (q → r) (p → r) 
V V V V V V V 
V V F V F F F 
V F V F V F V 
V F F F V F F 
F V V V V V V 
F V F V F F V 
F F V V V V V 
F F F V V V V 
3.1.6. Princípio da Inconsistência 
Se uma afirmação e a sua negação unidas pela conjunção implicam em outra proposição, 
então encontramos o princípio da inconsistência. 
p ^ ~p ⇒⇒⇒⇒ q 
p q ~p p ^ ~p 
V V F F 
V F F F 
F V V F 
F F V F 
 
3.2. Equivalência Lógica 
Dadas as proposições compostas P e Q Uma proposição P(p, q, r,...) é logicamente 
equivalente ou apenas equivalente a uma proposição Q(p, q, r, ...), se as tabelas-verdade 
dessas duas proposições são idênticas. Portanto, uma proposição P é tautologicamente 
equivalente a uma sentença Q se e somente se a bicondicional P ↔ Q é uma tautologia. 
Notação: P ≡ Q ou P(p, q, r, ...) ⇔ Q(p, q, r, ...) 
 P ⇔⇔⇔⇔ Q (P é logicamente equivalente a Q) 
Observação: Se as proposições P(p, q, r,...) e Q(p, q, r, ...) são ambas tautologias ou são 
ambas contradições então são equivalentes. 
Exemplos: 
� (p →→→→ q) ^ (q →→→→ p) ⇔⇔⇔⇔ (p ↔↔↔↔ q) 
p q p →→→→ q q →→→→ p (p →→→→ q) ^ (q →→→→ p) p ↔↔↔↔ q (p →→→→ q) ^ (q →→→→ p) ⇔⇔⇔⇔ (p ↔↔↔↔ q) 
V V V V V V V 
V F F V F F V 
F V V F F F V 
F F V V V V V 
Logo: A proposição P é logicamente equivalente à proposição Q, ou seja, (P ≡≡≡≡ Q), 
sempre que o bicondicional (P ↔↔↔↔ Q) é uma tautologia. 
TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.: Gleide Nolasco 
Pág. 19 
� (p ^ q) 
 
 ⇔⇔⇔⇔ ∼ ∼ ∼ ∼ (~p v ~q) 
p q p ^ q ~ p ~q ~p v ~q ~(~p v~q) p ^ q ⇔⇔⇔⇔ ~(~p v~q) 
V V V F F F V V 
V F F F V F F V 
F V F V F V F V 
F F F V V V F V 
Como (p ^ q) ↔ ∼↔ ∼↔ ∼↔ ∼(~p v ~q) é uma tautologia, então (p ^ q) ⇔⇔⇔⇔ ∼ ∼ ∼ ∼(~p v ~q), isto é, 
ocorre a equivalência lógica. 
3.2.1. Propriedades 
Reflexiva: P(p, q, r, ...) ⇔⇔⇔⇔ P(p, q, r, ...) 
Simétrica: Se P(p, q, r, ...) ⇔⇔⇔⇔ Q(p, q, r, ...) 
 então Q(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, ...) 
Observações: 
Temos que P (p, q, r,...) ⇔⇔⇔⇔ Q(p, q, r,...) se e somente se a bicondicional P(p, q, r,...) ↔ 
Q(p, q, r,...) é uma tautologia. Portanto a toda equivalência lógica corresponde uma 
bicondicional tautológica e vice-versa. 
 
Exemplo: 
A bicondicional (p ^ q → r) ↔ (p → (q → r)) é uma tautologia então p ^ q → r ⇔⇔⇔⇔ p → (q 
→ r) 
Observação: Os símbolos “ ↔ “ e ⇔⇔⇔⇔ são distintos, pois o primeiro é de operação lógica 
(aplicado às proposições p e q dá a nova proposição p ↔ q, enquanto que o segundo é de 
relação (estabelece que a bicondicional P(p, q, r, ...) ↔ Q(p, q, r,...) é uma tautologia). 
3.2.2. Proposições associadasa uma condicional 
Dada a condicional p→q, chamam-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 ou inversa de p → q : ~p → ~q 
� Proposição contrapositiva (contrária da recíproca, denominada contra-recíproca de p→q) 
de p → q : ~q → ~p 
 
 
 
 
TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.: Gleide Nolasco 
Pág. 20 
As tabelas-verdade dessas quatro proposições são: 
p q ~p ~q p → q q → p ~p → ~ q ~q → ~p 
V V F F V V V V 
V F F V F V V F 
F V V F V F F V 
F F V V V V V V 
 
e demonstram as duas importantes propriedades: 
� A condicional p → q e a sua contrapositiva ~q → ~p são equivalentes, isto é, 
p → q ⇔⇔⇔⇔ ~q → ~p. 
� A recíproca q → p e a contrária ~p → ~q da condicional p → q são equivalentes, isto é, 
q → p ⇔⇔⇔⇔ ~p → ~q 
� Também se diz que p → q é a direta em relação às associadas. 
3.2.3. 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 proposições p e q também se indica pela notação “ p ↓ q ”. 
Portanto, temos: 
Notação: p ↓ q ⇔⇔⇔⇔ ~p ^ ~q 
Tabela-verdade: 
 
p q ~p ~q p ↓ q 
V V F F F 
V F F V F 
F V V F F 
F F V V V 
 
 
3.2.4. 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 v ~q. 
A negação disjunta de duas proposições p e q também se indica pela notação “ p ↑ q “. 
Notação: p ↑ q ⇔⇔⇔⇔ ~p v ~q 
 
Tabela-verdade: 
 
p q ~p ~q p ↑ q 
V V F F F 
V F F V V 
F V V F V 
F F V V V 
TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.: Gleide Nolasco 
Pág. 21 
 
Observação: 
Os símbolos “ ↑ “ e “ ↓ “ são chamados conectivos de Scheffer. 
 
4. ÁLGEBRA DAS PROPOSIÇÕES 
4.1. PROPRIEDADES DA CONJUNÇÃO 
Sejam p, q e r proposições simples quaisquer e sejam t e c proposições também simples 
cujos valores lógicos respectivos são V(t) = V(verdade) e V(c) = F(falsidade). 
4.1.1. Idempotente: p ^ p <=> p 
Demonstração – Com efeito, são idênticas as tabelas-verdade das proposições p ^ p e p, 
ou seja, a bicondicional p ^ p ↔ p é tautológica: 
 
p p ^ p p ^ p ↔ p 
 
 
Assim, por exemplo, temos: 
(i) x ≠ 1 ^ x ≠ 1 <=> x ≠ 1 
(i i) x < 0 ^ x < 0 <=> x < 0 
4.1.2. Comutativa: p ^ q <=> q ^ p 
Demonstração – Com efeito, são idênticas as tabelas-verdade das proposições p ^ q e q ^ 
p, ou seja, a bicondicional p ^ q ↔ q ^ p é tautológica: 
 
p q p ^ q q ^ p p ^ q ↔ q ^ p 
 
 
 
 
4.1.3. Associativa: (p ^ q) ^ r <=> p ^ (q ^ r) 
Demonstração – Com efeito, são idênticas as tabelas-verdade das proposições (p ^ q) ^ r 
e p ^ (q ^ r): 
 
p q r p ^ q (p ^ q) ^ r q ^ r p ^ (q ^ r) 
 
 
 
 
 
 
 
 
Observa-se que a bicondicional (p ^ q) ^ r <=> p ^ (q ^ r) é tautológica. 
4.1.4. Identidade: p ^ t <=> p e p ^ c <=> c 
TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.: Gleide Nolasco 
Pág. 22 
Demonstração – Com efeito, são idênticas as tabelas-verdade das proposições p ^ t e p, p 
^c e c, ou seja as bicondicionais p ^ t ↔ p e p ^ c ↔ c são tautológicas: 
 
 
p t c p ^ t p ^ c p ^ t ↔ p p ^ c ↔ c 
V V F 
F V F 
Estas propriedades exprimem que t e c são respectivamente elemento neutro e elemento 
absorvente da conjunção. 
4.2. PROPRIEDADES DA DISJUNÇÃO 
Sejam p, q e r proposições simples quaisquer e sejam t e c proposições também simples 
cujos valores lógicos respectivos são V(verdade) e F(falsidade). 
4.2.1. Idempotente: p v p <=> p 
Demonstração – Com efeito, são idênticas as tabelas-verdade das proposições p v p e p, ou 
seja, a bicondicional p v p ↔ p é tautológica: 
p p v p p v p ↔ p 
 
 
Assim, por exemplo, temos: 
I. x ≠ 0 v x ≠ 0 <=> x ≠ 0 
II. x ≤ 1 v x ≤ 1 <=> x ≤ 1 
4.2.2. Comutativa: p v q <=> q v p 
Demonstração – Com efeito, são idênticas as tabelas-verdade das proposições p ^ q e q ^ 
p, ou seja, a bicondicional p ^ q ↔ q ^ p é tautológica: 
p q p v q q v p p v q ↔ q v p 
 
 
 
 
4.2.3. Associativa: (p v q) v r <=> p v (q v r) 
Demonstração – Com efeito, são idênticas as tabelas-verdade das proposições (p v q) v r e 
p v (q v r): 
p q r p v q (p v q) v r q v r p v (q v r) 
 
 
 
 
 
 
 
 
Observa-se que a bicondicional (p v q) v r ↔ p v (q v r) é tautológica. 
TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.: Gleide Nolasco 
Pág. 23 
4.2.4. Identidade: p v t <=> t e p v c <=> p 
Demonstração – Com efeito, são idênticas as tabelas-verdade das proposições p v t e p, p 
v c e c, ou seja as bicondicionais p v t ↔ t e p v c ↔ p são tautológicas: 
 
p t c p v t p v c p v t ↔ t p v c ↔ p 
V V F 
F V F 
Estas propriedades exprimem que t e c são respectivamente elemento neutro e elemento 
absorvente da disjunção. 
4.3. PROPRIEDADES DA CONJUNÇÃO E DA DISJUNÇÃO 
Sejam p, q e r proposições simples quaisquer. 
4.3.1. Distributivas: 
I. p ^ (q v r) <=> (p ^ q) v (p ^ r) 
II. p v (q ^ r) <=> (p v q) ^ (p v r) 
Demonstração: 
I. Com efeito, são idênticas as tabelas-verdade das proposições p ^ (q v r) e (p ^q) v (p ^ 
r): 
p q r q v r p ^ (q v r) p ^ q p ^ r (p ^q) v (p ^ r) 
 
 
 
 
 
 
 
 
Observa-se que a bicondicional p ^ (q v r) ↔(p ^ q) v (p ^ r) é tautológica. 
II. Analogamente, são idênticas as tabelas-verdade das proposições p v (q ^ r) e (p v q) ^ 
(p v r): 
p q r q ^ r p v (q ^r) p v q p v r (p v q) ^ (p v r) 
 
 
 
 
 
 
 
 
Observa-s que a bicondicional p v (q ^ r) ↔ (p v q) ^ (p v r) é tautológica. 
4.3.2. Absorção: 
I. p ^ (p v q) <=> p 
II. p v (p ^ q) <=> p 
TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.: Gleide Nolasco 
Pág. 24 
Demonstração – (I) Com efeito, são idênticas as tabelas-verdade das proposições p ^ (p v 
q) e p , ou seja, a bicondicional p ^ (p v q) ↔ p é tautológica: 
 
 
 
 
 
 
(II) Analogamente, são idênticas as tabelas-verdade das proposições p v (p ^q) e p, ou 
seja, a bicondicional p v (p ^ q) ↔ p é tautológica: 
 
 
 
 
 
 
4.3.3. Regras de De Morgan 
I. ~(p ^ q) <=> ~p v ~q 
II. ~(p v q) <=> ~p ^ ~q 
Demonstração: 
(I) Com efeito, são idênticas as tabelas-verdade das proposições ~(p ^ q) e ~p v ~q: 
 
 
 
 
 
 
Observa-se que a bicondicional ~(p ^ q) ↔ ~p v ~q é tautológica. 
(II) Analogamente, são idênticas as tabelas-verdade das proposições ~(p v q) e ~p ^ ~q 
 
 
 
 
 
 
Observação: 
As regras de De Morgan mostram como é possível definir a conjunção a partir da disjunção 
e da negação, ou a disjunção a partir da conjunção e da negação: 
p ^ q <=> ~(~p v ~q) 
p v q <=> ~(~p ^ ~q) 
4.4. NEGAÇÃO DA CONDICIONAL 
Como p → q <=> ~p v q, temos: ~(p → q) <=> ~(~p v q) <=> ~ ~p ^ ~q 
Ou seja: ~(p → q) <=> p ^ ~q 
TR JHMHRMHMMMMMMMMMMMM MMMMM MM MMM MM MMMMMMM MMMMMMMM MMMMM MUJNV MMTY/ 
Lógica Matemática e Computacional 
Prof.:Gleide Nolasco 
Pág. 25 
Esta equivalência também é demonstrada pelas tabelas-verdade das proposições ~(p → q) 
e p ^ ~q, que são idênticas: 
 
 
p q p → q ~(p → q) ~q p ^~q 
 
 
 
 
Observação: 
A condicional p → q não goza das propriedades idempotente, comutativa e associativa, pois, 
as tabelas-verdade das proposições p → p e p; p → q e q → p; (p→ q) → r e p → (p → r) 
não são idênticas. 
4.5. NEGAÇÃO DA BICONDICIONAL 
Como p ↔ q <=> (p → q) ^ (q → p) temos: (p ↔ q) <=> (~p v q) ^ (~q v p) 
E portanto: ~(p ↔ q) <=> ~(~p v q) v ~(~q v p) 
 ~(p ↔ q) <=> (~~ p ^ ~q) v (~~q ^~p) 
Ou seja: ~(p ↔ q) <=> (p ^ ~q) v (~p ^q) 
Esta equivalência também é demonstrada pelas tabelas-verdade das proposições ~(p ↔ q) 
e (p ^ ~q) v (~p ^q), que são idênticas: 
 
 
 
 
 
As tabelas-verdade das proposições ~(p ↔ q) , p ↔ ~q e ~p ↔ q são idênticas: 
 
 
 
 
 
 
Observação: 
A bicondicional p ↔ q não se aplica mas propriedades idempotente, pois, não são idênticas 
as tabelas-verdade das proposições p ↔ p e p, mas goza das propriedades comutativa e 
associativa.