01-LogicaFormal - aula1

Prévia do material em texto

1 - Lógica Formal 
• 1.1 Proposições e Tautologias 
• 1.2 Lógica Proposicional 
• 1.3 Quantificadores e Predicados 
• 1.4 Lógica de Predicados 
Lógica é a “ciência do raciocínio”. 
Aristóteles 
(384 a.C.–322 a.C.) 
Leibniz 
(1646–1716) 
George Boole 
(1815–1864) 
Augustus De Morgan 
(1806–1871) 
Aristóteles 
• Fez o primeiro tratamento sistemático 
das leis do pensamento relacionado 
com aquisição de conhecimento. 
• Originalmente a lógica lidou com 
argumentos na forma natural do idioma 
humano. 
Aristóteles 
• Todos os homens são mortais 
• Sócrates é um homem 
Aristóteles 
• Todos os homens são mortais 
• Sócrates é um homem 
‣ Então, Sócrates é mortal 
Problemas 
• Ambiguidades da linguagem natural 
Problemas 
• Ambiguidades da linguagem natural 
‣ “Bartolomeu é um touro” 
Problemas 
• Ambiguidades da linguagem natural 
‣ “Bartolomeu é um touro” 
• Paradoxos 
Problemas 
• Ambiguidades da linguagem natural 
‣ “Bartolomeu é um touro” 
• Paradoxos 
‣ Paradoxo do Mentiroso. “Essa frase é falsa” 
Lógica é a “ciência do raciocínio”. 
Aristóteles 
(384 a.C.–322 a.C.) 
Leibniz 
(1646–1716) 
George Boole 
(1815–1864) 
Augustus De Morgan 
(1806–1871) 
• Só no século 19 a lógica passa a ser 
constituída como ciência independente 
da filosofia. 
• George Boole e Augustus de Morgan 
mostram que as fórmulas algébricas 
podem ser usadas perfeitamente para 
expressar relações lógicas. 
• a*(b+c) = (a*b) + (a*c) é similar a 
 a˄(b˅c) = (a ˄ b) ˅ (a ˄c) 
Lógica é a “ciência do raciocínio”. 
Aristóteles 
(384 a.C.–322 a.C.) 
Leibniz 
(1646–1716) 
George Boole 
(1815–1864) 
Augustus De Morgan 
(1806–1871) 
Leibniz 
• Criador do termo “função” para descrever 
inclinações ou pontos situados numa curva. 
• É creditado a Leibniz e a Newton o 
desenvolvimento do cálculo moderno, em 
particular o desenvolvimento da Integral e da 
Regra do Produto. 
• Um dos grandes entusiastas da idéia de uma 
linguagem artificial para a apresentação formal 
das regras do pensamento, dedicou parte 
expressiva de seus escritos à tarefa de 
elaborar um sistema simbólico apropriado 
 
Objetivos 
• Proporcionar universalidade na 
representação do “raciocínio”. 
• Evitar ambigüidades 
• Garantir consistência 
A Lógica formal ignora o conteúdo 
de um argumento e se preocupa 
com a validade da argumentação. 
A Lógica formal fornece as 
estruturas básicas para descrever o 
método de pensar organizado e 
cuidadoso que caracteriza qualquer 
atividade racional. 
Conceitos Primitivos 
• Sentença 
• Valores Lógicos 
‣ Falso (F ou 0) 
‣ Verdadeiro (V ou 1) 
Proposições 
• Uma proposição é uma sentença que é 
falsa ou verdadeira. 
• Em lógica, utilizamos proposições para 
representar afirmações que fazemos 
em linguagem natural (fatos e 
informações) 
‣ Usaremos letras maiúsculas para 
representar proposições. 
Exemplo 1 
• Quais das seguintes sentenças são 
proposições? 
‣ A = “Dez é menor do que sete”; 
‣ B = “Como você está?”; 
‣ C = “Ela é muito talentosa”; 
‣ D = “Existe vida em outros planetas do 
universo”. 
Exemplo 1 
• Quais das seguintes sentenças são 
proposições? 
‣ A = “Dez é menor do que sete”; 
‣ B = “Como você está?”; 
‣ C = “Ela é muito talentosa”; 
‣ D = “Existe vida em outros planetas do 
universo”. 
Conectivos Lógicos 
• Podemos usar conectivos lógicos para 
combinar proposições em expressões. 
‣ Conjunção 
‣ Disjunção 
‣ Condicional 
‣ Equivalência 
‣ Negação 
Conjunção 
• A expressão A ∧ B é chamada 
conjunção 
• O símbolo ∧ é o conectivo lógico de 
conjunção (“e”). 
• A e B são os fatores (ou elementos) da 
expressão. 
• Qual é o valor lógico da expressão A ∧ 
B? 
A B A ∧ B 
V V V 
V F F 
F V F 
F F F 
Tabela-Verdade da conjunção 
A B A ∧ B 
V V V 
V F F 
F V F 
F F F 
Tabela-Verdade da conjunção – “mínimo” 
A B A ∧ B 
1 1 1 
1 0 0 
0 1 0 
0 0 0 
Disjunção 
• Denotada pelo símbolo ∨ (“ou”) 
A B A ∨ B 
V V V 
V F V 
F V V 
F F F 
Disjunção 
• Denotada pelo símbolo ∨ (“ou”) 
• máximo 
A B A ∨ B 
V V V 
V F V 
F V V 
F F F 
A B A ∨ B 
1 1 1 
1 0 1 
0 1 1 
0 0 0 
Condicional 
• O conectivo → representa uma 
expressão condicional 
• A → B significa “se A, então B” 
• Uma expressão condicional é também 
denominada “implicação” 
‣ A → B também significa “A implica B” 
 
Condicional 
• Suponha que A → B seja verdadeira, então: 
‣ A ser verdadeira implica que B seja 
verdadeira 
‣ B é uma condição necessária para A. 
A B A → B 
V V V 
V F F 
F V V 
F F V 
Exemplo 2 
• Expressão condicional (implicação) 
‣ A = “Há fumaça” 
‣ B = “Há fogo” 
‣ A → B (“se há fumaça, então há fogo”) 
A B A → B 
V V V 
V F F 
F V V 
F F V 
Equivalência 
• O símbolo ↔ é o conectivo de 
equivalência 
• A ↔ B = (A → B) ∧ (B → A) 
A B A → B B → A A ↔ B 
V V V V V 
V F F V F 
F V V F F 
F F V V V 
Negação 
• A negação é um “conectivo” lógico 
unário, simbolizada por ′ (“não”) 
A A′ 
V F 
F V 
Exemplo 3 
• Negação de uma expressão 
‣ A = “Pedro é alto” 
‣ B = “Pedro é magro” 
‣ (A ∧ B) = “Pedro é alto e magro” 
‣ (A ∧ B)′ = “Pedro é baixo e gordo” 
FBF 
• Uma combinação válida de proposições 
e conetivos lógicos é denominada uma 
fórmula bem formulada (FBF) 
‣ (A → B) ∧ (B → C) é uma FBF 
‣ A)) → ∧C não é uma FBF 
 
• Assim como em linguagens de 
programação, existe uma certa sintaxe 
Ordem de 
Precedência 
1. ′ 
2. ∧, ∨ 
3. → 
4. ↔ 
Em uma FBF, o último conectivo a ser aplicado é 
denominado o conectivo principal. 
Exemplos: 
A ∨ B′ = A ∨ (B′) 
A ∨ B → C = (A ∨ B) → C 
• O valor lógico de uma FBF depende 
dos valores lógicos associados às 
proposições que fazem parte da 
fórmula. 
• Podemos identificar o valor lógico para 
uma FBF construindo sua tabela-
verdade. 
Exemplo 4 
• Construa a tabela-verdade para a 
seguinte fórmula: 
‣ A ∨ B′ → ( A ∨ B)′ 
Exemplo 4 
• Construa a tabela-verdade para a 
seguinte fórmula: 
‣ A ∨ B′ → (A ∨ B)′ 
A B B′ 
V V F 
V F V 
F V F 
F F V 
Exemplo 4 
• Construa a tabela-verdade para a 
seguinte fórmula: 
‣ A ∨ B′ → (A ∨ B)′ 
A B B′ A ∨ B′ 
V V F V 
V F V V 
F V F F 
F F V V 
Exemplo 4 
• Construa a tabela-verdade para a 
seguinte fórmula: 
‣ A ∨ B′ → (A ∨ B)′ 
A B B′ A ∨ B′ ( A ∨ B) 
V V F V V 
V F V V V 
F V F F V 
F F V V F 
Exemplo 4 
• Construa a tabela-verdade para a 
seguinte fórmula: 
‣ A ∨ B′ → (A ∨ B)′ 
A B B′ A ∨ B′ ( A ∨ B) ( A ∨ B)′ 
V V F V V F 
V F V V V F 
F V F F V F 
F F V V F V 
Exemplo 4 
• Construa a tabela-verdade para a 
seguinte fórmula: 
‣ A ∨ B′ → (A ∨ B)′ 
A B B′ A ∨ B′ ( A ∨ B) ( A ∨ B)′ A ∨ B′ → ( A ∨ B)′ 
V V F V V F F 
V F V V V F F 
F V F F V F V 
F F V V F V V 
Tautologia 
• Uma tautologia é uma FBF 
“intrinsecamente verdadeira” pela sua 
própria estrutura. 
‣ Ela assume o valor verdadeiro (V) 
independentemente do valor associado às 
proposições da fórmula. 
• Exemplos: 
‣ A ∨ A′ 
‣ (A → B) ↔ (B′ → A′) 
Contradição 
• Uma contradição é uma FBF cujo valor 
lógico é sempre falso 
• Exemplos 
‣ A ∧ A′ 
‣ (A ∨ A′) → (B ∧ B′) 
FBFs Equivalentes 
• Sejam P e Q duas FBFs 
• Se P ↔ Q é uma tautologia, então 
dizemos que P e Q são FBFs 
equivalentes. 
‣ P ⇔ Q 
Equivalências 
Tautológicas• A ∨ B ⇔ B ∨ A (comutatividade) 
• (A ∨ B) ∨ C ⇔ A ∨ (B ∨ C) (associatividade) 
• A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C) (distributividade) 
• A ∨ 0 ⇔ A (elemento neutro) 
• A ∧ 1 ⇔ A (elemento neutro) 
• A ∧ A′ ⇔ 0 (complementares) 
• A ∨ A′ ⇔ 1 (complementares) 
Leis de Morgan 
(A ∨ B)′ ⇔ A′ ∧ B′ 
(A ∧ B)′ ⇔ A′ ∨ B′ 
Exercício 1 
• Utilize a notação simbólica da lógica formal 
para representar as seguintes expressões. 
1. Tanto ir dormir como ir nadar é uma 
condição suficiente para a troca de roupa; 
além disso, mudar a roupa não significa que 
se vai nadar. 
2. Se Jane vencer ou perder, ela vai ficar 
cansada. 
3. Ou Jane irá vencer ou, se perder, ela ficará 
cansada. 
4. Vai chover ou nevar, mas não ambos. 
Exercício 2 
• Construa a tabela-verdade para a 
seguinte fórmula e verifique se é 
tautologia ou contradição: 
‣ (A → B) ↔ A′ ∨ B 
Exercício 3 
• Prove que é verdadeira a seguinte Lei 
de Morgan (A ∨ B)′ ⇔ A′ ∧ B′ 
Exercício 4 
• Suponha que você está viajando em 
um país onde todo habitante é 
completamente honesto ou 
completamente mentiroso. Você 
encontra dois habitantes daquele país: 
Parcival e Levelim. Parcival diz: “pelo 
menos um de nós é mentiroso”. 
‣ Parcival é honesto ou mentiroso? 
‣ E Levelim?