Lógica Proposicional

Prévia do material em texto

Lógica Proposicional 
Rogério Melo Nepomuceno
Introdução à Lógica Matemática
Lógica e Computação
Lógica
Fornece as bases para o método de 
pensar organizado e cuidadoso que 
caracteriza qualquer atividade 
racional.
Proposição
Sentença ou frase, com sujeito e predicado bem definido, a qual
podemos interpretar, sem ambiguidade, como sendo verdadeira ou
falsa.
Exemplos de Proposições:
▪ A: Dez é menor que 7.
▪ B: Brasil é um país localizado na América Latina.
▪ C: 5 + 2 = 6.
▪ D: Todos os gatos são pardos.
Não são Proposições:
▪ Ela é muito inteligente.
▪ X + 2 = 5.
▪ Olá!
▪ Como está você?
Representamos as 
proposições com letras 
maiúsculas do início do 
alfabeto.
Valor Lógico
Denominamos de valor lógico () ou interpretação (I) de uma
proposição à sua avaliação, a qual resulta em um valor de
verdade (V) ou falsidade (F).
Exemplos - considerando as proposições:
▪ A: Dez é menor que 7.
▪ B: Brasil é um país localizado na América Latina.
Então temos:
▪ I(A) = F
▪ I(B) = V
Princípios Fundamentais
▪ Princípio da Não-Contradição: uma
proposição não pode se simultaneamente
verdadeira e falsa.
▪ Princípio do Terceiro Excluído: toda
proposição ou é só verdadeira ou é só falsa,
nunca ocorrendo um terceiro caso; ou seja,
toda proposição só admite os valores lógicos V
ou F.
Conectivos Lógicos
Denominamos de conectivos lógicos àqueles
conectivos que nos permitem combinar
proposições.
São eles:
▪ Negação: não ()
▪ Conjunção: e ()
▪ Disjunção: ou ()
▪ Condicional: se .. então (→)
▪ Bicondicional: se e somente se ()
A 
A  B
A  B
A → B
A  B
Fórmulas Bem Formadas
Denominamos de fórmula bem formada (fbf) a
uma proposição composta obtida pela
combinação de uma ou mais proposições.
Para representarmos fbfs normalmente
utilizamos letras no final de nosso alfabeto,
como por exemplo P, Q, R e S, podendo cada
letra possuir um índice, como, por exemplo, P1,
P2, P3, S1, S2, etc.
Fórmulas Bem Formadas
Uma fórmula bem formada (fbf) pode ser obtida de acordo com as seguintes regras 
sintáticas:
1. Toda proposição A é uma fbf, denominada de fórmula atômica;
2. Se P e Q são fbf, então (P) (negação), (P  Q) (conjunção), (P  Q) (disjunção), 
(P→ Q) (implicação ou condicional) e (P Q) (bicondicional) também são fbf.
Exemplos: sejam as proposições
▪ A: Dez é menor que 7,
▪ B: Brasil é um país localizado na 
América Latina,
▪ C: 5 + 2 = 6.
As fórmulas a seguir são fbf:
▪ P: A
▪ Q: A  B
▪ R: (A  B)
▪ S: (A  B)→ C
▪ P1: ((A → B)  (B→ C)) → (A → C)
▪ P2: (A → B)  (B →A)
Precedência dos Conectivos
A avaliação de uma fórmula deve ser feita respeitando-se a seguinte
precedência para os conectivos:
1. Parênteses
2. Negação
3. Conjunção
4. Disjunção
5. Implicação
6. Bicondicional
Exemplo: a fórmula A → B  C  B  (A → C) deve ser
interpretada como:
( ((A) )→ (B  C) ) (B  (A → C) ).
Tradução de uma Fórmula
Expressão em Português Conectivo Lógico Fórmula
Não
É falso que
Não é verdade que
Negação A
E
Mas
Também
Além disso
Conjunção A  B
Ou Disjunção A  B
Se A, então B
A implica B
A, logo B
A somente se B
B, se A
B, quando A
B segue de A
A é uma condição suficiente para B
B é uma condição necessária para A
Implicação A → B
A se, e somente se, B
A é condição necessária e suficiente para B
Bicondicional A  B
Tradução de uma Fórmula
Sentenças Fórmula
▪ O Brasil não fica na África.
▪ É falso que quatro mais dois é igual a 6. 
▪ Não é verdade que hoje é Domingo. 
A
▪ Carlos gosta de futebol e Ana gosta de novela. 
▪ Hoje esta calor, mas ontem choveu. 
▪ Marcos foi ao teatro. Ele Também foi ao cinema. 
▪ O Dólar é uma moeda forte. Além disso, em agosto ele atingiu o valor de R$ 5,42. 
▪ Gosto de rapadura também, além de mel. 
A  B
▪ Guilherme é inteligente ou dedicado. (ou inclusivo)
▪ Às 20:00 horas, Tânia irá ao cinema ou à sorveteria. (ou exclusivo)
A  B
A  B
▪ Se o dia está nublado, então está chovendo. 
▪ Uma condição suficiente para a falha de uma rede elétrica é que a chave central 
desligue. 
▪ Os abacates estão maduros quando estão escuros e macios. 
▪ Ser um número par implica em ser divisível por dois. 
A → B
▪ Um número é primo se, e somente se, ele é divisível por um e por ele mesmo. 
▪ Nevar é uma condição necessária e suficiente para fazer frio. 
A  B
Decomposição de uma Fórmula
Toda fbf pode ser decomposta (d) em sub-
fórmulas, respeitando-se as regras de sintaxe
estabelecidas e a precedência dos conectivos
lógicos, criando o que denominamos de árvore
de decomposição.
Decomposição de uma Fórmula
Seja P uma fbf e c o seu conectivo principal:
1. Se c é um conectivo unário, então P = Q, e 
sua árvore de decomposição é dada por:
Decomposição de uma Fórmula
2. Se c é um conectivo binário, então P pode
ser do tipo (Q  R), (Q  R), (Q → R) ou
(Q  R), e, portanto, sua árvore de
decomposição é dada por:
Decomposição de uma Fórmula
Seja a fbf: (A  B) → C. A árvore de
decomposição associada a esta fórmula é:
Decomposição de uma Fórmula
Seja a fbf: (A → B)  [(B → C)  (A → C)]. A
árvore de decomposição associada a esta
fórmula é:
Valor Lógico de uma Fórmula
P Q P P  Q P  Q P → Q P  Q
V V F V V V V
V F F F V F F
F V V F V V F
F F V F F V V
Sejam as fórmulas P e Q. A tabela verdade
correspondente a avaliação dos conectivos lógicos é
dada por:
Tabela Verdade – Exemplos 
Sejam as seguintes proposições:
A: O Brasil é pentacampeão;
B: A Europa é um país de primeiro mundo;
C: 4 – 2 = 3.
Obter a interpretação das fórmulas abaixo.
▪ (A  B) → C:
▪ (A→ B)  (B → A):
A B C A  B (A  B) → C
V F F V F
A B A → B B A B →A (A → B)  (B →A)
V F F V F F V
Tabela Verdade – Exemplos 
Seja a fórmula (A  B).
Determine a sua tabela verdade.
A B A A  B (A  B)
1ª V V F V F
2ª V F F F V
3ª F V V V F
4ª F F V V F
Tabela Verdade – Exemplos 
Seja a fórmula (A  B)→ C.
Determine a sua tabela verdade.
A B C A A  B (A  B) (A  B) → C
1ª V V V F F V V
2ª V V F F F V F
3ª V F V F F V V
4ª V F F F F V F
5ª F V V V V F V
6ª F V F V V F V
7ª F F V V F V V
8ª F F F V F V F
Tabela Verdade – Exemplos 
Seja a fórmula ((A→ B)  (B→ C))→ (A→ C).
Determine a sua tabela verdade.
A B C A → B B → C A → C ((A → B)  (B → C) ((A → B)  (B → C)) → (A → C)
V V V V V V V V
V V F V F F F V
V F V F V V F V
V F F F V F F V
F V V V V V V V
F V F V F V F V
F F V V V V V V
F F F V V V V V
Tabela Verdade – Exemplos 
Seja a fórmula (A  B)(A  B).
Determine a sua tabela verdade.
A B A B A  B (A  B) A  B (A  B) (A  B) (A  B)
V V F F F V V F F
V F F V V F F V F
F V V F V F F V F
F F V V V F F V F
Exercícios
1. Quais das alternativas a seguir são proposições?
a) Carlos é um calouro estudioso.
b) Você está se sentindo bem?
c) Parabéns, Ana!
d) x2 + 2 > 10
e) Todos os veículos têm quatro rodas.
f) Existem aves que não voam.
Exercícios
2. Qual o valor lógico das proposições a seguir?
a) Sócrates foi um importante filósofo.
b) A lua é feita de queijo mineiro.
c) Todos os aviões são a jato.
d) Existem mamíferos aquáticos.
Exercícios
3. Qual a negação das frases a seguir?
a) Túlio gosta de estudar.
b) Paris não é a capital da França.
c) Está chovendo e fazendo sol.
d) Ou faz frio ou faz calor.
e) Todos os gatos são pardos.
f) Existem cegos que usam óculos.
g) Se eu ganhar na loteria eu comprarei uma fazenda.
Exercícios
4. Traduza as frases a seguir para a notação da lógica:
a) Maria gosta de sorvete, mas não gosta de goiabada.
b) Beatriz não sabe cozinhar ou Joaquim é atleta e corajoso.
c) Se fizer calor eu vou a praia. Entretanto, eu não vou 
pescar.
d) 5 > 7, se 7 for par.
e) Vou navegar se, e somente se, não estiver chovendo ou 
ventando forte.
Exercícios
5. Traduza as fórmulas a seguir para o português, 
considerando as proposições:
A: Mônica tem um pônei.
B: Ana tem um treno.
C: José tem uma bicicleta.
a) A  B
b) (A  B) → C 
c) A → (B C)
Exercícios
6. Qual o valor lógico associado a cada umadas 
fórmulas a seguir?
a) A  B
b) (A  B) → C 
c) A → (B C)