Aula2 logica

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

Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Fundamentos de Matemática para Computação
FMC
Prof.a Dr.a Diane Castonguay
Prof.a Dr.a Elisângela Silva Dias
{diane, elisangela}@inf.ufg.br
Instituto de Informática
Universidade Federal de Goiás
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Introdução
Definição de lógica
Segundo Chauí [3], a lógica pode ter qualquer das
definições abaixo:
estudo do raciocínio;
estudo do pensamento correto e verdadeiro;
regras para demonstração científica verdadeira;
regras para pensamentos não-científicos;
regras sobre o modo de expor o conhecimento; e
regras para verificação da verdade ou falsidade de um
pensamento.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Introdução
Definição 1 (Proposições)
Uma proposição é uma sentença declarativa que pode ser
verdadeira (V) ou falsa (F), mas não ambas.
Exemplo 1
1 Salvador é a capital da Bahia (V);
2 2 + 2 = 3 (F).
3 A lua é satélite da Terra (V).
Exemplo 2 (Não são proposições:)
1 Que dia é hoje?
2 Leia isto cuidadosamente.
3 x+ 1 = 2.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Princípios ou axiomas da lógica clássica
Princípio da identidade
Toda proposição é idêntica a si mesma.
Princípio da não contradição
Uma proposição não pode ser verdadeira e falsa ao mesmo
tempo.
Princípio do terceiro excluído
Toda proposição ou é verdadeira ou é falsa, não existindo
um terceiro valor que ela possa assumir.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Proposições simples
São sentenças declarativas (palavras ou símbolos) que
exprimem um pensamento de sentido completo.
São conhecidas como sentenças atômicas, átomos ou
subfórmulas.
Não contêm nenhuma outra proposição como parte
integrante de si mesma.
São representadas por letras minúsculas do alfabeto da
língua portuguesa.
Exemplo 3
p: “Hoje é segunda-feira”.
q: “Hoje está chovendo”.
r: “Carlos tem uma moto”.
s: “O número 25 é par”.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Proposições compostas
São formadas pela composição de duas ou mais
proposições simples (subfórmulas).
Também são conhecidas como moléculas ou fórmulas.
São representadas por letras maiúsculas do alfabeto da
língua portuguesa ou letras gregas.
Exemplo 4
Seja p a proposição “Hoje é segunda-feira” e q a proposição
“Hoje está chovendo”.
P1: “Hoje não é segunda-feira” (P1 = ¬p).
Q1: “Hoje é segunda-feira e está chovendo” (Q1 = p ∧ q).
R: “Hoje é segunda-feira ou está chovendo” (R = p ∨ q).
φ: “Se hoje é segunda-feira, então está chovendo”
(φ = p→ q).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Conectivos
São símbolos (palavras) utilizados para formar proposições
compostas a partir de proposições simples.
Exemplo 5
Negação: ¬ (não, é falso que, não é verdade que).
Conjunção: ∧ (e).
Disjunção: ∨ (ou).
Disjunção exclusiva: ⊕ (ou exclusivo, ou . . . ou).
Condicional: → (se . . . então, implica).
Bicondicional: ↔ (se e somente se).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Tabelas-verdade
São tabelas com todos os valores-verdade ou valores
lógicos possíveis das proposições simples.
O valor-verdade da fórmula depende unicamente dos
valores de verdade das proposições simples componentes,
ficando por elas univocamente determinados.
As tabelas-verdade têm 2n linhas, onde n é a quantidade
de proposições simples.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Definição 2 (Negação)
Seja p uma proposição. A negação de p, denotada por ¬p
(e também por p¯ ou ∼ p), é a sentença “não é o caso de p”.
A proposição ¬p é lida como “não p”. O valor-verdade da
negação de p (¬p) é o oposto do valor-verdade de p.
Tabela-verdade da negação de uma fórmula
p ¬p
F V
V F
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Exemplo 6 (Negação)
Seja a proposição p: “Hoje é sexta-feira.”
A negação de p é:
¬p: “Não é o caso de hoje ser sexta-feira.”
A negação pode ser expressa:
¬p: “Não é verdade que hoje é sexta-feira.”
¬p: “Hoje não é sexta-feira.”
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Definição 3 (Conjunção)
Sejam p e q proposições. A conjunção de p e q, denotada
por p ∧ q, é a proposição “p e q”.
A conjunção (p ∧ q) é verdadeira quando ambos os
valores-verdade são V, e falsa em qualquer outro caso.
Pode ser expressa por palavras como: mas, todavia,
contudo, no entanto, visto que, enquanto, além disso,
embora.
Tabela-verdade para a conjunção de duas fórmulas
p q p ∧ q
F F F
F V F
V F F
V V V
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Exemplo 7 (Conjunção)
Seja a proposição p:“Hoje é sexta-feira.”
Seja a proposição q: “Hoje está chovendo.”
Então, p ∧ q: “Hoje é sexta-feira e está chovendo.”
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Definição 4 (Disjunção)
Sejam p e q proposições. A disjunção de p e q, denotada
por p ∨ q, é a proposição “p ou q”.
Também é conhecida como disjunção inclusiva.
A disjunção (p ∨ q) é falsa se os valores-verdade de p e q
são ambos F, e verdadeira em qualquer outro caso.
Tabela-verdade para a disjunção de duas fórmulas
p q p ∨ q
F F F
F V V
V F V
V V V
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Exemplo 8 (Disjunção)
Seja a proposição p:“Hoje é sexta-feira.”
Seja a proposição q: “Hoje está chovendo.”
Então, p ∨ q: “Hoje é sexta-feira ou está chovendo.”
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Definição 5 (Disjunção exclusiva)
Sejam p e q proposições. A disjunção exclusiva de p e q,
denotada por p⊕ q, é a proposição “p ou exclusivo q”.
A disjunção exclusiva é verdadeira quando os
valores-verdade de p e q são distintos e falsa quando são
idênticos.
Tabela-verdade para o ou exclusivo de duas fórmulas
p q p⊕ q
F F F
F V V
V F V
V V F
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Exemplo 9 (Disjunção exclusiva)
Seja a proposição p:“Hoje é sexta-feira.”
Seja a proposição q: “Hoje está chovendo.”
Então, p⊕ q: “Ou hoje é sexta-feira ou está chovendo.”
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Definição 6 (Condicional)
Sejam p e q proposições. A proposição condicional p→ q
é a proposição “se p, então q”.
A condicional é falsa quando o valor-verdade de p é V e o
de q é F e é verdadeira em qualquer outro caso.
Dizemos que p é a hipótese (ou antecedente ou
premissa) e q é a conclusão (ou consequente ou
consequência).
Tabela-verdade para a condicional de duas fórmulas
p q p→ q
F F V
F V V
V F F
V V V
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Condições necessárias e suficientes
Podemos expressar:
p implica q;
Sempre que p, temos q;
p é suficiente para q;
q é necessário para p.
Os termos “necessidade” e “suficiência”, amplamente
difundidos na análise lógica e matemática, são utilizados
para denotar a implicação e a equivalência.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Condições necessárias e suficientes
Exemplo 10
Quais são as condições necessárias para alguém se tornar juiz?
Uma condição necessária é que o indivíduo tenha se
formado em um curso de direito.
Este fato é representado por: juiz → formado em direito.
O que significa que se o indivíduo é juiz, então ele é
formado em direito.
Mas apenas ser formado em direito não é suficiente para
ser juiz.
Para ser juiz é também necessário que o indivíduo tenha
sido aprovado na OAB.
Se o indivíduo é juiz, então ele é formado em direito e foi
aprovado no exame da OAB, o que pode ser representado
por: juiz → (formado em direito) ∧ (aprovado OAB).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Condições necessárias e suficientes
Exemplo 8 - continuação
As duas condições são necessárias para alguém ser juiz,
mas não são suficientes.
Além delas, é necessário que o profissional tenha 2 anos de
experiência em advocacia e tenha sido aprovado em
concurso público para juiz.
Então, juiz → (formado em direito) ∧ (aprovado OAB) ∧
(concurso juiz) ∧ (experiência).
Neste caso, as condições necessárias são também
suficientes para alguém ser juiz.
(formado em direito) ∧ (aprovado OAB) ∧ (concurso juiz)
∧ (experiência) → juiz.
Observe que a condição suficiente é o antecedente da
implicação e a condição necessária é o consequente.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Exemplo 11 (Condicional)
Seja a proposição condicional “Se Marcos passar no teste de
FMC, então irá ao cinema no sábado”.
p é “Marcos passar no teste deFMC”.
q é “irá ao cinema no sábado”.
Se Marcos não passar no teste, independente se ele vai ou
não ao cinema, não podemos afirmar que a proposição
é falsa.
Se Marcos passar no teste e for ao cinema, a proposição é
verdadeira.
Se Marcos passar no teste e não for ao cinema, a
proposição é falsa.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Exercício 1 (Condicional)
Indique o antecedente e o consequente de cada uma das
seguintes sentenças:
O crescimento sadio das plantas é consequência de
quantidade suficiente de água.
O crescimento da oferta de computadores é uma condição
necessária para o desenvolvimento científico.
Haverá novos erros apenas se o programa for alterado.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Definição 7 (Bicondicional)
Sejam p e q proposições. A proposição bicondicional
(p↔ q) é a proposição “p se e somente se q”.
Ela é verdadeira sempre que p e q têm o mesmo
valor-verdade e é falsa em qualquer outro caso.
É uma abreviação de (p→ q) ∧ (q → p).
Tabela-verdade para a bicondicional de duas fórmulas
p q p↔ q
F F V
V F F
F V F
V V V
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Lógica Proposicional
Podemos expressar:
se p então q e vice-versa;
p é necessária e suficiente para q;
p sse q (p iff q).
Exemplo 12 (Bicondicional)
Seja a proposição “Marcos será aprovado se e somente se
obtiver média maior ou igual a 6,0 na disciplina FMC”.
1 Se Marcos não obtiver média maior ou igual a 6,0
e for reprovado, a proposição é verdadeira.
e for aprovado, a proposição é falsa.
2 Se Marcos obtiver média maior ou igual a 6,0
e for reprovado, a proposição é falsa.
e for aprovado, a proposição é verdadeira.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Definição
Proposições
Tabelas-
verdade
Negação
Conjunção
Disjunção
Condicional
Bicondicional
Precedência
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Tabelas-verdade
Prioridades entre os operadores lógicos
Operador Prioridade
¬ 1
∧,∨ 2
→,↔ 3
Exemplo 13
P → ¬Q ∧R representa a fórmula:
(P → ((¬Q) ∧R)).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Tautologia ou validade
Definição 8 (Tautologia ou validade)
Uma proposição composta (fórmula) que é sempre
verdadeira é chamada de tautologia ou é dita que é
válida.
Uma fórmula é uma tautologia se e somente se todo
valor-verdade é V.
Tabela-verdade de uma tautologia
p ¬p p ∨ ¬p
F V V
V F V
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Contradição
Definição 9 (Contradição)
Uma fórmula que é sempre falsa é chamada de
contradição.
Uma fórmula é contraditória se e somente se todos os
valores-verdade são F.
Tabela-verdade de uma tautologia e uma contradição
p ¬p p ∨ ¬p p ∧ ¬p
F V V F
V F V F
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Satisfatibilidade
Definição 10 (Satisfatibilidade)
Uma fórmula é satisfatível ou é dita factível se e somente
se existe um valor-verdade V.
Toda taulologia é satisfatível, mas nem toda fórmula
satisfatível é tautologia.
Tabela-verdade para a bicondicional de duas fórmulas
p q p↔ q
F F V
V F F
F V F
V V V
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Implicação lógica
Definição 11 (Implicação lógica (⇒))
Dadas duas fórmulas p e q, p implica logicamente q se e
somente se p→ q é uma tautologia.
Exemplo 14
Considere as fórmulas E = ((p ∧ q) ∨ q), G = (p→ q) e
H = (p ∧ q). Construindo a tabela-verdade, temos:
p q H = (p ∧ q) E = ((p ∧ q) ∨ q) G = (p→ q)
F F F F V
F V F V V
V F F F F
V V V V V
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Implicação lógica
Exemplo 15 (Implicação lógica)
E → G E → H H → E H → G G→ E G→ H
V V V V F F
V F V V V F
V V V V V V
V V V V V V
E implica logicamente G (E ⇒ G);
E não implica logicamente H;
H implica logicamente E (H ⇒ E);
H implica logicamente G (H ⇒ G);
G não implica logicamente E;
G não implica logicamente H;
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Equivalências lógicas ou equivalências tautológicas
Definição 12 (Equivalência lógica (⇔))
Dadas duas fórmulas p e q, p equivale a q se e somente se
todos os valores-verdade são idênticos.
Ou seja, p e q têm a mesma tabela-verdade.
Também podemos dizer que p e q são logicamente
equivalentes se p↔ q é uma tautologia.
A notação utilizada é p⇔ q ou p ≡ q.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Oposta, contrapositiva e inversa
Seja a proposição p→ q:
q → p é a sua recíproca ou oposta;
¬q → ¬p é a sua contrapositiva;
¬p→ ¬q é a sua inversa ou contrária;
Observações:
A proposição condicional e a sua contrapositiva são
equivalentes;
A recíproca e a inversa são equivalentes, mas não são
equivalentes à proposição condicional original.
Exercício 2
Faça as tabelas-verdade da recíproca, contrapositiva e inversa.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Leis de De Morgan
Augustus De Morgan (1806-1871)
Foi um matemático indiano que deu contribuições
fundamentais para a lógica simbólica.
Escreveu milhares de artigos e muitos livros teóricos sobre
vários assuntos da matemática.
Criou notações que o ajudaram a provar equivalências
proposicionais,
assim como as leis que receberam seu nome.
Leis de De Morgan
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Leis de De Morgan
Exercício 3
Faça a tabela-verdade para mostrar a equivalência das leis de
De Morgan.
Exercício 4
Use as leis de De Morgan para expressar as negações de:
1 Marcos tem um carro e uma moto.
2 Rodrigo vai ao cinema ou ao teatro
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Equivalências lógicas ou tautológicas
Tabela 1/2
Equivalências Nome
p∧ V ≡ p Propriedades de identidade
p∨ F ≡ p
p∨ V ≡ V Propriedades de dominação
p∧ F ≡ F
p ∨ p ≡ p Propriedades idempotentes
p ∧ p ≡ p
p ∨ q ≡ q ∨ p Propriedades comutativas
p ∧ q ≡ q ∧ p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Propriedades associativas
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Equivalências lógicas ou tautológicas
Tabela 2/2
Equivalências Nome
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Propriedades distributivas
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
¬(p ∧ q) ≡ ¬p ∨ ¬q Leis de De Morgan
¬(p ∨ q) ≡ ¬p ∧ ¬q
p ∨ (p ∧ q) ≡ p Propriedades de absorção
p ∧ (p ∨ q) ≡ p
¬(¬p) ≡ p
p ∨ ¬p ≡ V Propriedades de negação
p ∧ ¬p ≡ F
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Propriedades de definição de conectivos
Reescrita da condicional
p→ q ≡ ¬p ∨ q
p→ q ≡ ¬q → ¬p
¬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
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Tautologia
Contradição
Satisfatibilidade
Implicações
Equivalências
Oposta, con-
trapositiva e
inversa
De Morgan
Tabelas
Lógica de
Predicados
Próxima aula
Bibliografia
Propriedades de definição de conectivos
Reescrita da bicondicional
p↔ q ≡ (p→ q) ∧ (q → p)
p↔ q ≡ ¬p↔ ¬q
p↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
¬(p↔ q) ≡ p↔ ¬q
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Lógica de Primeira Ordem (LPO)
Definição 13 (Predicados)
Predicados representam propriedades e relações entre
objetos.
Ex.: Maria é bonita. “Bonita” é uma propriedade de Maria.
Tal fato pode ser representado, na LPO, por B(x).
De maneira informal, podemos dizer: B(x) é verdadeiro se,
e somente se, x é bonita.
Quando x é Maria, o valor-verdade é V.
Ex.: a relação “irmão” pode ser representada por I(x, y).
Neste caso, dizemos que I(x, y) é verdadeiro se, e somente
se, a pessoa x é irmã de y.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Lógica de Primeira Ordem (LPO)
Maneira informal de ver o quantificador universal
Utilizamos com frequência na nossa linguagem cotidiana.
Todo homem é mortal.
Todos os homens são mortais.
Os homens são mortais.
Homens são sempre mortais.
Somente mortais é que são homens.
Apenas mortais é que são homens.
Só mortais é que são homens.
Se algo é homem, então é mortal.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Lógica de Primeira Ordem (LPO)
Maneira informal de ver o quantificador universal
Todas as sentenças anteriores têm o mesmo sentido.
Considere x a variável que representa homens e o
predicado M(x) é verdadeiro quando x é mortal.
As sentenças podem ser representadas por ∀x M(x).
Neste caso, ∀x representa a universalização de x.
Tem sentido de que todo, para todo, qualquer que seja,
todos ou cada x, sem exceção, satisfaz M(x).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Lógica de Primeira Ordem (LPO)
Maneira informal de ver o quantificador existencial
Considere as sentenças:
Existe um homem inteligente.
Há um homem inteligente.
Há pelo menos um homem inteligente.
Há homens inteligentes.
Algum homem é inteligente.
Alguns homens são inteligentes.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Lógica de Primeira Ordem (LPO)
Maneira informal de ver o quantificador existencial
Todas as sentenças anteriores têm o mesmo sentido.
Considere x a variável que representa homens e o
predicado I(x) é verdadeiro quando x é inteligente.
Então, as sentenças podem ser representadas por ∃x I(x).
Neste caso, ∃x representa a existência de x.
Tem sentido de que existe um, alguns, algum, um ou pelo
menos um x, que representa homem e que satisfaz I(x).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Linguagem de Predicados
Exemplo 16 (Traduções)
Todo estudante é mais jovem do que algum instrutor.
E(x): x é um estudante.
I(y): y é um instrutor.
J(x, y): x é mais jovem que y.
∀x(E(x)→ (∃y (I(y) ∧ J(x, y)))).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Linguagem de Predicados
Exercício 5 (Traduções)
Traduza as seguintes sentenças para a LPO:
1 Nem todas as aves podem voar.
A(x): x é uma ave.
V (x):
x pode voar.
¬(∀x(A(x)→ V (x))). Alternativa: ∃x(A(x) ∧ ¬V (x)).
2 Toda criança é mais jovem que sua mãe.
C(x): x é uma criança.
M(y, x): y é mãe de x.
J(x, y): x é mais jovem que y.
∀x∀y(C(x) ∧M(y, x)→ J(x, y)).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Linguagem de Predicados
Definição 14 (Correspondência entre os quantificadores)
∀x φ ≡ ¬(∃x(¬φ)).
∃x φ ≡ ¬(∀x(¬φ)).
¬(∀x φ) ≡ ∃x(¬φ).
¬(∃x φ) ≡ ∀x(¬φ).
Exemplo 17
“Existe uma aluna de computação que é bonita”: ∃x B(x).
“É falso que toda aluna de computação é feia”:
¬(∀x(¬B(x))).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Linguagem de Predicados
Correspondência entre os quantificadores
Negar sentenças com quantificadores requer um certo
cuidado.
A negação da sentença “Tudo é bonito” é “Não é verdade
que tudo é bonito” ou “Algo não é bonito”.
B(x): x é bonito.
Tudo é bonito: ∀x B(x).
Não é verdade que tudo é bonito: ¬(∀x B(x)).
Algo não é bonito: ∃x ¬B(x).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Linguagem de Predicados
Exercício 6 (Correspondência entre os quantificadores)
Qual é a negação correta?
1 Algumas pessoas gostam de Matemática.
a) Algumas pessoas não gostam de Matemática.
b) Todo o mundo não gosta de Matemática.
c) Todo o mundo gosta de Matemática.
2 Todo o mundo gosta de sorvete.
a) Ninguém gosta de sorvete.
b) Todo o mundo não gosta de sorvete.
c) Alguém não gosta de sorvete.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Linguagem de Predicados
Exercício 7 (Correspondência entre os quantificadores)
Qual é a negação correta?
1 Todo o mundo é alto e magro.
a) Alguém é baixo e gordo.
b) Ninguém é alto e magro.
c) Alguém é baixo ou gordo.
2 Alguns retratos estão velhos ou apagados.
a) Nenhum retrato está velho ou apagado.
b) Alguns retratos não estão velhos ou apagados.
c) Todos os retratos não estão velhos e não estão apagados.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Introdução
∀ e ∃
Traduções
Correspondência
entre ∀ e ∃
Precedência
Próxima aula
Bibliografia
Tabelas-verdade
Prioridades entre os operadores lógicos
Operador Prioridade
¬ 1
∀x,∃x 2
∧,∨ 3
→,↔ 4
Exemplo 18
∀x ∃y P (x, y)→ ∃z ¬Q(z) ∧R(y) representa a fórmula:
(∀x(∃y P (x, y)))→ (∃z(¬Q(z)) ∧R(y)).
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Próxima aula
Técnicas de demonstração.
Fundamentos
de
Matemática
para
Computação
Prof.a Dr.a
Diane
Castonguay
Prof.a Dr.a
Elisângela
Silva Dias
Introdução
Propriedades
semânticas
Lógica de
Predicados
Próxima aula
Bibliografia
Referências Bibliográficas
Referências
ALENCAR Filho, Edgard de,
Iniciação à Lógica Matemática.
Editora Nobel, 1990.
BISPO, C.A.; CASTANHEIRA, L.B.; SOUZA Filho, O.M.,
Introdução à Lógica Matemática.
Editora Cengange Learning, 2011.
CHAUÍ, M.,
Convite à Filosofia.
Editora Ática, 2002.
MENDELSON, E.,
Introduction to Mathematical Logic.
Wadsworth and Brook, 1987.
SOUZA, João Nunes de,
Lógica para Ciência da Computação.
Editora Campus, 2002.
SOUZA, João Nunes de,
Lógica para Ciência da Computação e áreas afins.
3a. edição, Editora Elsevier, 2015.
	Introdução
	Definição
	Proposições
	Tabelas-verdade
	Negação
	Conjunção
	Disjunção
	Condicional
	Bicondicional
	Precedência
	Propriedades semânticas
	Tautologia
	Contradição
	Satisfatibilidade
	Implicações
	Equivalências
	Lógica de Predicados
	Introdução
	 e 
	Traduções
	Correspondência entre e 
	Precedência
	Próxima aula
	Bibliografia