MD05 - Logica Formal

Prévia do material em texto

Lógica Formal
Matemática Discreta
1
1Este material baseia-se no material do professor Eduardo Nakamura (nakamura@icomp.ufam.edu.br) e no livro
GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação: um Tratamento Moderno de Matemática Discreta, 7a ed. Livros Técnicos e Científicos, 2017.
mailto:emsantos@icomp.ufam.edu.br
Linha do tempo
Matemática Discreta
2
século IV 
a.C.
Aristóteles (384 a.C. – 322 a.C.) filósofo grego. Sistematizou a lógica, definindo as 
formas de inferência que eram válidas e as que não eram, formando um 
conjunto de regras para raciocínio dedutivo que pode ser usado em qualquer 
área do conhecimento.
h
tt
p
:/
/e
n
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
A
ri
st
o
tl
e
Linha do tempo
Matemática Discreta
3
século IV 
a.C.
Gottfried Wilhelm von Leibniz (1646 – 1716) filósofo e matemático alemão, 
conhecido por ter criado o cálculo integral e diferencial independentemente de 
Isaac Newton.
Uso de símbolos para mecanizar o processo de raciocínio dedutivo. 
século XVI 
d.C.
h
tt
p
:/
/e
n
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
G
o
tt
fr
ie
d
_W
ilh
el
m
_L
ei
b
n
iz
h
tt
p
:/
/e
n
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
A
ri
st
o
tl
e
Linha do tempo
Matemática Discreta
4
século IV 
a.C.
George Boole (1815 – 1864) filósofo e matemático inglês e Augustus De Morgan 
(1806 – 1871) matemático inglês.
Bases da lógica simbólica moderna usando as ideias de Leibniz. 
século XVI 
d.C.
século XIX 
d.C.
século XIX 
d.C.
h
tt
p
:/
/e
n
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
G
eo
rg
e_
B
o
o
le
h
tt
p
:/
/e
n
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
A
u
gu
st
u
s_
D
e_
M
o
rg
an
h
tt
p
:/
/e
n
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
G
o
tt
fr
ie
d
_W
ilh
el
m
_L
ei
b
n
iz
h
tt
p
:/
/e
n
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
A
ri
st
o
tl
e
O que é Lógica?
Matemática Discreta
5
 Estudo sistemático de regras e relações (ferramentas) 
que permitem avaliar se um argumento é válido o 
inválido.
 Argumento: 
◆ Sequência de proposições (premissas) que sustentam outra 
proposição (conclusão).
Lógica Formal
Matemática Discreta
6
 Fornece bases para o método de pensar organizado
 Expressa métodos de raciocínio sob a forma de 
argumentos
 Tem duas aplicações diretas em Ciência da Computação
1. Programação Lógica
2. Prova se programas estão corretos ou não
 É análoga à lógica de circuitos de um computador
Lógica Formal
Matemática Discreta
7
 Exemplos de utilização em computação:
◆ Inteligência Artificial
◆ Circuitos Lógicos
◆ Banco de Dados
◆ Sistemas Computacionais (hardware e software)
◆ Sistemas Distribuídos
◆ Teoria de autômatos e computabilidade
◆ Teoria de linguagens
Proposições
Matemática Discreta
8
 Uma proposição é uma sentença declarativa (afirmação) que 
admite apenas um dos dois valores lógicos (verdadeiro ou falso), 
nunca ambos
 Proposições?????
◆ Manaus é a capital do Amazonas
◆ 1 + 1 = 2
◆ Como você está?
◆ 9 < 6
◆ Estudem regularmente
◆ Londres é na Dinamarca
◆ Matemática Discreta é fácil
Proposições
Matemática Discreta
9
 PROPOSIÇÕES ATÔMICAS não podem ser sub-divididas em 
proposições mais simples
◆ Ex: O servidor de arquivos está desligado
 PROPOSIÇÕES COMPOSTAS são combinações de proposições 
atômicas via conectivos lógicos
◆ Ex: A rede local está mal configurada ou o servidor de arquivos 
está desligado
◆ O valor verdade é completamente determinado pelos valores-
verdade das subproposições junto com a forma como estão 
conectadas
Proposições
Matemática Discreta
10
 PROPOSIÇÕES ATÔMICAS são representadas por meio de 
variáveis proposicionais
◆ Variáveis proposicionais: (P, Q, R, S,...)
◆ Constantes proposicionais: (V, F) → (V, F)
 Nas PROPOSIÇÕES COMPOSTAS, as variáveis proposicionais são 
combinadas através de, pelo menos, um operador ou conectivo 
lógico
◆ Operadores lógicos são utilizados para combinar proposições e 
formar novas proposições
Conectivos lógicos básicos
Matemática Discreta
11
 Terminologia 
◆ Negação: ¬
◆ Conjunção: ∧
◆ Disjunção: ∨
◆ Condicional: →
◆ Bicondicional: 
Proposições atômicas
P: MD é fácil
Q: Cálculo é fácil
¬Q: (não Q)
Cálculo não é fácil
Cálculo é difícil
Conectivos lógicos básicos
Matemática Discreta
12
 Terminologia 
◆ Negação: ¬
◆ Conjunção: ∧
◆ Disjunção: ∨
◆ Condicional: →
◆ Bicondicional: 
P∧Q: (P e Q)
MD é fácil e Cálculo também
P∧¬Q: (P e não Q)
MD é fácil, mas Cálculo não é
Proposições atômicas
P: MD é fácil
Q: Cálculo é fácil
Conectivos lógicos básicos
Matemática Discreta
13
 Terminologia 
◆ Negação: ¬
◆ Conjunção: ∧
◆ Disjunção: ∨
◆ Condicional: →
◆ Bicondicional: 
P∨Q: (P ou Q)
MD é fácil ou Cálculo é fácil
P∨¬Q: (P ou não Q)
MD é fácil ou Cálculo não é fácil
Proposições atômicas
P: MD é fácil
Q: Cálculo é fácil
Exercícios 01a
Matemática Discreta
14
1. Escreva as seguintes sentenças como proposições em lógica:
a) Agesilau vai sair mais cedo e não vai voltar.
b) Hermosina é aluna de MD e Agesilau também.
c) Hermosina está no laboratório e Agesilau não, ou ele está e ela não.
2. Considere as seguintes proposições:
P: “Ariosto é rico” Q: “Ariosto é educado” 
Escreva as proposições abaixo em Lógica Formal:
a) Ariosto não é nem rico e nem educado.
b) Ariosto é rico, ou é pobre e educado.
c) É falso que Ariosto seja rico e educado.
d) Não é falso que Ariosto é mal educado ou ele é pobre. Slide 45
Tabela verdade
Matemática Discreta
15
 Ferramenta usada para 
determinar os valores de 
uma expressão lógica 
◆ Gottlob Frege e Charles 
Peirce, em 1880
◆ Emil Post e Ludwig 
Wittgenstein, em 1922 
forma atual
h
tt
p
:/
/p
t.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Lu
d
w
ig
_W
it
tg
en
st
ei
n
h
tt
p
:/
/p
t.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Em
il_
P
o
st
h
tt
p
:/
/p
t.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
C
h
ar
le
s_
Sa
n
d
er
s_
P
ei
rc
e
h
tt
p
:/
/p
t.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
G
o
tt
lo
b
_F
re
ge
Tabela verdade e conectivos lógicos
Matemática Discreta
16
 Negação Negação
P ¬P
V F
F V
Se P é verdade, então ¬P é 
falso; e se P é falso ¬P é 
verdade
Tabela verdade e conectivos lógicos
Matemática Discreta
17
 Conjunção Conjunção
P Q P∧Q
V V V
V F F
F V F
F F F
Se P e Q são verdade, 
então P∧Q é verdade; caso 
contrário P∧Q é falso
Exemplo da conjunção
Matemática Discreta
18
Vou ao cinema se dispuser 
de tempo E tiver dinheiro
Tabela verdade e conectivos lógicos
Matemática Discreta
19
 Disjunção Disjunção
P Q P∨Q
V V V
V F V
F V V
F F F
Se P e Q são falsos, então 
P∨Q é falso; caso contrário 
P∨Q é verdade.
Exemplo da disjunção
Matemática Discreta
20
Irei à festa se tiver 
dinheiro OU ganhar um 
convite
Tabela verdade: proposição composta
Matemática Discreta
21
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q
V V
V F
F V
F F
Tabela verdade: proposição composta
Matemática Discreta
22
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q
V V
V F
F V
F F
Tabela verdade: proposição composta
Matemática Discreta
23
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q
V V F
V F
F V
F F
Tabela verdade: proposição composta
Matemática Discreta
24
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q
V V F
V F V
F V
F F
Tabela verdade: proposição composta
Matemática Discreta
25
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q
V V F
V F V
F V F
F F
Tabela verdade: proposição composta
Matemática Discreta
26
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q
V V F
V F V
F V F
F F V
Tabela verdade: proposição composta
Matemática Discreta
27
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q
V V F
V F V
F V F
F F V
Tabela verdade: proposição composta
Matemática Discreta
28
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q P∧¬Q
V V F F
V F V
F VF
F F V
Tabela verdade: proposição composta
Matemática Discreta
29
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q P∧¬Q
V V F F
V F V V
F V F
F F V
Tabela verdade: proposição composta
Matemática Discreta
30
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q P∧¬Q
V V F F
V F V V
F V F F
F F V
Tabela verdade: proposição composta
Matemática Discreta
31
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q P∧¬Q
V V F F
V F V V
F V F F
F F V F
Tabela verdade: proposição composta
Matemática Discreta
32
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q P∧¬Q
V V F F
V F V V
F V F F
F F V F
Tabela verdade: proposição composta
Matemática Discreta
33
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q P∧¬Q ¬(P∧¬Q)
V V F F V
V F V V
F V F F
F F V F
Tabela verdade: proposição composta
Matemática Discreta
34
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q P∧¬Q ¬(P∧¬Q)
V V F F V
V F V V F
F V F F
F F V F
Tabela verdade: proposição composta
Matemática Discreta
35
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q P∧¬Q ¬(P∧¬Q)
V V F F V
V F V V F
F V F F V
F F V F
Tabela verdade: proposição composta
Matemática Discreta
36
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q P∧¬Q ¬(P∧¬Q)
V V F F V
V F V V F
F V F F V
F F V F V
Tabela verdade: proposição composta
Matemática Discreta
37
 Qual a tabela verdade da proposição ¬(P∧¬Q) ?
¬(P∧¬Q) 
P Q ¬Q P∧¬Q ¬(P∧¬Q)
V V F F V
V F V V F
F V F F V
F F V F V
Assinalar “valores-verdade” para proposições compostas permite o uso da
lógica para decidir a verdade de uma proposição usando somente o
conhecimento das partes
Exercícios 01b
Matemática Discreta
38
1. Considere as sentenças abaixo:
P: “Elefantes são grandes” Q: “Bolas de futebol são redondas” 
Qual o valor lógico das seguintes expressões:
a. P ∧ Q, sendo P verdadeira e Q, falsa.
b. Q V P, sendo Q verdadeira e P, falsa.
2. Escreva a tabela-verdade da seguinte proposiçã0:
a. Vai chover ou vai nevar, mas não ambos
Ambiguidade
Matemática Discreta
39
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R ?
2. P ∨ Q ∧ R = P ∨ (Q ∧ R)?
◆ O Caprichoso ganhou o festival ou o Garantido ganhou o 
festival, e Parintins começou a mudar.
◆ O Caprichoso ganhou o festival, ou o Garantido ganhou o 
festival e Parintins começou a mudar.
Ambiguidade
40
P Q R P ∨ Q Q ∧ R (P ∨ Q) ∧ R P ∨ (Q ∧ R)
V V F
V V V
V F F
V F V
F V F
F V V
F F F
F F V
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R? 2. P ∨ Q ∧ R = P ∨ (Q ∧ R)?
Matemática Discreta
Ambiguidade
41
P Q R P ∨ Q Q ∧ R (P ∨ Q) ∧ R P ∨ (Q ∧ R)
V V F V
V V V V
V F F V
V F V V
F V F V
F V V V
F F F F
F F V F
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R? 2. P ∨ Q ∧ R = P ∨ (Q ∧ R)?
Ambiguidade
42
P Q R P ∨ Q Q ∧ R (P ∨ Q) ∧ R P ∨ (Q ∧ R)
V V F V F
V V V V V
V F F V F
V F V V V
F V F V F
F V V V V
F F F F F
F F V F F
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R? 2. P ∨ Q ∧ R = P ∨ (Q ∧ R)?
Ambiguidade
43
P Q R P ∨ Q Q ∧ R (P ∨ Q) ∧ R P ∨ (Q ∧ R)
V V F V F F
V V V V V V
V F F V F F
V F V V F V
F V F V F F
F V V V V V
F F F F F F
F F V F F F
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R? 2. P ∨ Q ∧ R = P ∨ (Q ∧ R)?
Ambiguidade
44
P Q R P ∨ Q Q ∧ R (P ∨ Q) ∧ R P ∨ (Q ∧ R)
V V F V F F V
V V V V V V V
V F F V F F V
V F V V F V V
F V F V F F F
F V V V V V V
F F F F F F F
F F V F F F F
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R? 2. P ∨ Q ∧ R = P ∨ (Q ∧ R)?
Ambiguidade
45
P Q R P ∨ Q Q ∧ R (P ∨ Q) ∧ R P ∨ (Q ∧ R)
V V F V F F V
V V V V V V V
V F F V F F V
V F V V F V V
F V F V F F F
F V V V V V V
F F F F F F F
F F V F F F F
1. P ∨ Q ∧ R = (P ∨ Q) ∧ R? 2. P ∨ Q ∧ R = P ∨ (Q ∧ R)?
Ambiguidade
Matemática Discreta
46
 Solução: ordem de precedência
1. Parênteses mais internos
2. Negação: ¬
3. Conjunção: ∧, Disjunção: ∨
4. Condicional: →
5. Bicondicional: 
Agora, sabendo disso, voltar e refazer Exercícios 01a.
Conectivos lógicos no mundo real
Matemática Discreta
47
 Diferença de resposta em programas de busca na internet para 
as seguintes pesquisas: 
◆ carros usados
◆ "carros usados”
◆ "carros usados” + (Ford OU Gurgel) = "carros usados” E (Ford 
OU Gurgel)
◆ "carros usados” + (Ford OU Gurgel) - caminhões = "carros
usados” E (Ford OU Gurgel) E NÃO caminhões
A última limita a pesquisa a lugares que mencionam as 
marcas específicas e que não mencionam caminhões.
Conectivos lógicos condicional e bicondicional
Matemática Discreta
48
 Terminologia 
◆ Negação: ¬
◆ Conjunção: ∧
◆ Disjunção: ∨
◆ Condicional: →
◆ Bicondicional: 
P→Q: (se P, então Q)
- se MD é fácil então serei aprovado
- MD ser fácil implica que serei 
aprovado
- MD é fácil, logo serei aprovado
- MD é fácil só se eu for aprovado
- MD é fácil somente se eu for 
aprovado
- MD ser fácil é condição suficiente 
para eu ser aprovado
Proposições atômicas
P: MD é fácil
Q: Serei aprovado
- Basta MD ser fácil para eu ser 
aprovado
- Serei aprovado caso MD seja fácil
- Ser aprovado é condição necessária 
para MD ser fácil
Conectivos lógicos condicional e bicondicional
Matemática Discreta
49
 Terminologia 
◆ Negação: ¬
◆ Conjunção: ∧
◆ Disjunção: ∨
◆ Condicional: →
◆ Bicondicional: 
PQ: (P se, e somente se, Q)
- x é par se, e somente se, x+1 é 
ímpar
- x é par é condição necessária e 
suficiente para, x+1 ser ímpar
- se x é par, então x+1 é ímpar, e 
vice-versa
Proposições atômicas
P: x é par
Q: x+1 é ímpar
Tabela verdade e conectivos lógicos
Matemática Discreta
50
 Condicional Condicional
P Q P→Q
V V V
V F F
F V V
F F V
Se P é verdade e Q é falso, 
então P→Q é falso; caso 
contrário é verdadeiro
Tabela verdade e conectivos lógicos
Matemática Discreta
51
 Condicional Condicional
P Q P→Q
V V V
V F F
F V V
F F V
Caso interessante: se P é 
falso e Q é verdadeiro, 
então P→Q é verdadeiro
Se Luan Santana cantar no 
BTS, então todos passarão em 
MD
Se nevar em Manaus, então 
choverá piranhas em Paris
Verdadeiro ou falso?
Tabela verdade e conectivos lógicos
Matemática Discreta
52
 Condicional Condicional
P Q P→Q
V V V
V F F
F V V
F F V
Bruna fez a seguinte promessa 
para Ernestino:
Se você ganhar na Megasena, 
então eu me caso com você.
Em que situação Bruna estaria 
mentindo?
E se Ernestino não ganhar na 
Megasena?
Tabela verdade e conectivos lógicos
Matemática Discreta
53
 Condicional Condicional
P Q P→Q
V V V
V F F
F V V
F F V
Promessa:
Se você se apresentar para 
trabalhar na segunda, então 
você terá o emprego.
Em que situação o empregador 
não falou a verdade?
E se a afirmação P não for 
satisfeita?
Não é ‘justo’ dizer que a 
promessa é falsa.
Tabela verdade e conectivos lógicos
Matemática Discreta
54
 Bicondicional Bicondicional
P Q PQ
V V V
V F F
F V F
F F V
Se P e Q são iguais, então 
PQ é verdadeiro; caso 
contrário é falso
Galvão é pai de Cacá se, e 
somente se, Cacá é filho de 
Galvão.
Condicional e Bi-condicional
Matemática Discreta
55
 Condição necessária e condição suficiente
P→ Q
• A proposição antecedente é chamada de condição suficiente. 
• A proposição consequente é chamada de condição necessária.
• Uma condição suficiente gera um resultado necessário.
• Q é uma condição necessária para P – se P for verdade, Q
também tem, necessariamente, que ser verdadeira.
Proposição 
antecedente
(Suficiente)
Proposição 
consequente
(Necessária)
Condicional e Bi-condicional
Matemática Discreta
56
 Exemplo:
• Se João é elegível para votar então ele tem pelo menos 16 anos.
P: João é elegível para votar.
Q: João tem pelo menos 16 anos.
P→ Q
• João ser elegível para votar é condição suficiente para que ele 
tenha pelo menos 16 anos.
• João ter pelo menos 16 anos é condição necessária para que ele 
seja elegível para votar.
Condicional e Bi-condicional
Matemática Discreta
57
 Exemplo:
◆ Converta uma condição suficiente para a forma se–então:
O nascimento de João emsolo brasileiro é uma condição suficiente para
ele ser cidadão brasileiro
Se João nasceu em solo brasileiro então ele é um cidadão brasileiro.
◆ Converta uma condição necessária para a forma se–então:
João ter pelo menos 35 anos é uma condição necessária para ser 
presidente do Brasil
Se João pode ser o presidente do Brasil então ele já tem pelo menos 35 
anos.
Exemplos
Matemática Discreta
58
 O fogo é uma condição necessária para a fumaça.
Se houver fumaça, então haverá fogo.
 Uma condição suficiente para a falha da rede elétrica é que a
chave central desligue.
Se a chave central desligar, então haverá falha da rede elétrica.
 O crescimento sadio de plantas é consequência de quantidade
suficiente de água.
Se houver quantidade suficiente de água, então haverá 
crescimento sadio de plantas.
Exemplos
Matemática Discreta
59
 O aumento da disponibilidade de informação é uma condição
necessária para um maior desenvolvimento tecnológico.
Se há maior desenvolvimento tecnológico, então há aumento da 
disponibilidade de informação.
 A economia de energia para aquecimento implica boa insulação
ou vedação de todas as janelas.
Se houver economia de energia, então haverá boa insulação ou 
vedação de todas as janelas.
Exercícios 01c
Matemática Discreta
60
1. Escreva as seguintes proposições compostas em notação simbólica:
a) Os abacates estão maduros quando estão macios.
b) Uma boa dieta é uma condição necessária para você ser saudável.
c) Se os preços subirem, então haverá muitas casas para vender, e elas 
serão caras; mas se as casas não forem caras, então ainda assim 
haverá muitas casas para vender.
d) Tanto ir para cama como nadar é condição suficiente para trocar de 
roupa; no entanto, trocar de roupa não significa que se vai nadar.
2. Escreva as tabelas-verdade das seguintes proposições:
a) (P ∧ Q) (¬P ∨ ¬Q)
b) [P ∧ (¬Q → ¬P)] → Q
c) (¬P → ¬Q) ∧ [(P → Q) → P]
Exercícios 01c – Resolução parcial
Matemática Discreta
61
 Os abacates estão maduros quando estão macios.
Se os abacates estão maduros, então eles estão macios.
Antecedente (P): os abacates estão maduros
Consequente (Q): os abacates estão macios
 Uma boa dieta é uma condição necessária para você ser saudável.
Se você é saudável, então tem uma boa dieta.
Antecedente (P): você é saudável
Consequente (Q): você tem uma boa dieta
- P é condição suficiente para Q
- Basta P para Q
- Q caso P
- Q é condição necessária para P
- se P, então Q
- P implica Q
- P, logo Q
- P só se Q
- P somente se Q
P → Q
Linguagem proposicional
Matemática Discreta
62
 Uma linguagem proposicional L é composta por
◆ Um Alfabeto (letras maiúsculas, o conjunto {V,F} e os 
conectivos lógicos) 
◆ Símbolos para variáveis e constantes e proposições compostas 
ou fórmulas
 A Gramática de uma linguagem proposicional define a sintaxe 
das expressões
◆ Permite a formação e o reconhecimento de fórmulas bem 
formadas (fbf)
◆ Exemplo: P¬vQ (fórmula incorreta, mal formada)
Gramática de uma linguagem proposicional
Matemática Discreta
63
1. Letras proposicionais do vocabulário são fórmulas em L
2. Se α e β são fórmulas em L, então também são fórmulas as 
seguintes expressões:
◆ ¬α
◆ α ∧ β 
◆ α ∨ β 
◆ α → β
◆ α  β
 Somente o que pode ser gerado através dos itens 1 e 2 em um 
número finito de passos é uma fórmula em L
Tautologia
Matemática Discreta
64
 Sempre verdade independentemente dos valores verdade das 
variáveis
 Também denominada proposição tautológica ou logicamente 
verdadeira
 Exemplo
◆ P ∨ ¬P
◆ “Amanhã vai chover ou amanhã não vai chover” 
Contradição
Matemática Discreta
65
 Sempre falso independentemente dos valores verdade das 
variáveis
 Exemplo 
◆ P ∧ ¬P
◆ Hoje choveu e hoje não choveu
 Observação
◆ A negação de uma tautologia é uma contradição
◆ A negação de uma contradição é uma tautologia
Contingência
Matemática Discreta
66
 Fórmula bem formada que não é tautologia e nem é contradição
 Seu valor verdade depende dos valores verdade das variáveis
 Exemplo 
◆ P ∧ Q
◆ Hoje choveu e ontem nevou
Exercícios 01d
Matemática Discreta
67
Verifique se as proposições abaixo são tautologia, contradição ou 
contingência:
1. (P ∧ Q) → (P Q)
2. (P ∧ Q) ∧ ¬(P ∨ Q)
3. (P ∧ Q) (¬Q ∨ ¬P)
4. [(P → Q) → (P ∨ R)] → (Q ∨ R)
5. (P → Q) (¬P ∨ Q)
Equivalência lógica ()
Matemática Discreta
68
 Duas proposições  e  são logicamente equivalentes ( ), 
se ambas possuem tabelas-verdade idênticas
 Exemplo
◆ O São Raimundo é o melhor time do Amazonas e vence 
sempre 
◆ O São Raimundo vence sempre e é o melhor time do 
Amazonas
◆ (P ∧ Q) (Q ∧ P)
Equivalência lógica ()
Matemática Discreta
69
 Duas proposições  e  são logicamente equivalentes ( ), 
se ambas possuem tabelas-verdade idênticas
 Exemplo
◆ Jurandir é Garantido ou é Caprichoso
◆ Jurandir é Caprichoso ou é Garantido
◆ (P ∨ Q) (Q ∨ P)
Equivalência lógica ()
Matemática Discreta
70
 Duas proposições  e  são logicamente equivalentes ( ), 
se ambas possuem tabelas-verdade idênticas
 Exemplo
◆ Se Nancy está dormindo, então Freddy Krueger aparece
◆ Se Freddy Krueger não aparece, então Nancy não está 
dormindo
◆ (P → Q)  (¬Q → ¬P)
Teorema ( e )
71
P  Q se, e somente se, P Q é tautologia.
 Exemplos
◆ (P →Q) (¬P ∨ Q) é tautologia
◆ Logo, (P → Q)  (¬P ∨ Q)
◆ [P → (Q → R)] [(P ∧ Q) → R] é tautologia
◆ Logo, [P → (Q → R)]  [(P ∧ Q) → R]
Exercícios 01e
Matemática Discreta
72
Verifique se as proposições abaixo são equivalências lógicas:
1. ¬(P ∧ Q) e (¬P ∨ ¬Q)
2. P ∨ (Q ∧ R) e (P ∨ Q) ∧ R
3. ¬(¬P ∨ Q) e (¬P)→ (¬Q)
Regras de equivalência
Matemática Discreta
73
 Duas proposições  e  são logicamente equivalentes ( ), 
se ambas possuem tabelas-verdade idênticas
◆ Definem que determinados pares de FBFs são equivalentes
◆ Portanto, se  , então  pode ser substituída por  em 
qualquer FBFs sem mudança em seu valor lógico
Teoremas de De Morgan
NÃO (A E B) (NÃO A) OU (NÃO B)
Negação do E
NÃO (A OU B) (NÃO A) E (NÃO B)
Negação do OU
74
Matemática Discreta
Teoremas de De Morgan
:: Negação do operador E
75
A B A E B
V V V
V F F
F V F
F F F
NÃO (A E B)
F
V
V
V
NÃO A NÃO B
F F
F V
V F
V V
(NÃO A) OU (NÃO B)
F
V
V
V
Equivalentes
Matemática Discreta
Teoremas de De Morgan
:: Exemplo com operador E
Vou ao cinema se 
dispuser de tempo E 
tiver dinheiro
FATO: NÃO fui ao 
cinema
OU
76
Matemática Discreta
Teoremas de De Morgan
:: Negação do operador OU
77
A B A OU B
V V V
V F V
F V V
F F F
NÃO (A OU B)
F
F
F
V
NÃO A NÃO B
F F
F V
V F
V V
(NÃO A) E (NÃO B)
F
F
F
V
Equivalentes
Matemática Discreta
Teoremas de De Morgan
:: Exemplo com operador OU
Irei à festa se tiver 
dinheiro OU ganhar um 
convite
FATO: NÃO fui à festa
E
78
Matemática Discreta
Regras de equivalência
79
Fórmula Lei
P  P ≡ P
P  P ≡ P
Idempotência
(P  Q)  R ≡ P  (Q  R)
(P  Q)  R ≡ P  (Q  R)
Associativa
P  Q ≡ Q  P
P  Q ≡ Q  P
Comutativa
(P  Q)  R ≡ (P  R)  (Q  R)
(P  Q)  R ≡ (P  R)  (Q  R)
Distributiva
P  F ≡ P
P  V ≡ V
P  V ≡ P
P  F ≡ F
Identidade
Matemática Discreta
Regras de equivalência
80
Fórmula Lei
P  ¬P ≡ V
¬V ≡ F
P  ¬P ≡ F
¬F ≡ V
Complemento
¬¬P ≡ P Involução
¬(P  Q) ≡ ¬P  ¬Q
¬(P  Q) ≡ ¬P  ¬Q
DeMorgan
P → Q ≡ ¬P  Q Condicional
Matemática Discreta
Regras de equivalência (resumo)
Fórmula Lei
P ∨ P ≡ P
P ∧ P ≡ P
Idempotência
(P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)
(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)
Associativa
P ∨ Q ≡ Q ∨ P
P ∧ Q ≡ Q ∧ P
Comutativa
(P ∧ Q) ∨ R ≡ (P ∨ R) ∧ (Q ∨ R)
(P ∨ Q) ∧ R ≡ (P ∧ R) ∨ (Q ∧ R)
Distributiva
P ∨ F ≡ P
P ∨ V ≡ V
P ∧ V ≡ P
P ∧ F ≡ F
Identidade
P ∨ ¬P ≡ V
¬V ≡ F
P ∧ ¬P ≡ F
¬F ≡ V
Complemento
¬¬P ≡ P Involução
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
¬(P ∨ Q) ≡ ¬P ∧ ¬Q
DeMorgan
P → Q ≡ ¬P ∨ Q Condicional
P → Q ≡ ¬Q→¬P Contrapositiva
	Slide 1: Lógica Formal
	Slide 2: Linha do tempo
	Slide 3: Linha do tempo
	Slide 4: Linha do tempoSlide 5: O que é Lógica?
	Slide 6: Lógica Formal
	Slide 7: Lógica Formal
	Slide 8: Proposições
	Slide 9: Proposições
	Slide 10: Proposições
	Slide 11: Conectivos lógicos básicos
	Slide 12: Conectivos lógicos básicos
	Slide 13: Conectivos lógicos básicos
	Slide 14: Exercícios 01a
	Slide 15: Tabela verdade
	Slide 16: Tabela verdade e conectivos lógicos
	Slide 17: Tabela verdade e conectivos lógicos
	Slide 18: Exemplo da conjunção
	Slide 19: Tabela verdade e conectivos lógicos
	Slide 20: Exemplo da disjunção
	Slide 21: Tabela verdade: proposição composta
	Slide 22: Tabela verdade: proposição composta
	Slide 23: Tabela verdade: proposição composta
	Slide 24: Tabela verdade: proposição composta
	Slide 25: Tabela verdade: proposição composta
	Slide 26: Tabela verdade: proposição composta
	Slide 27: Tabela verdade: proposição composta
	Slide 28: Tabela verdade: proposição composta
	Slide 29: Tabela verdade: proposição composta
	Slide 30: Tabela verdade: proposição composta
	Slide 31: Tabela verdade: proposição composta
	Slide 32: Tabela verdade: proposição composta
	Slide 33: Tabela verdade: proposição composta
	Slide 34: Tabela verdade: proposição composta
	Slide 35: Tabela verdade: proposição composta
	Slide 36: Tabela verdade: proposição composta
	Slide 37: Tabela verdade: proposição composta
	Slide 38: Exercícios 01b
	Slide 39: Ambiguidade
	Slide 40: Ambiguidade
	Slide 41: Ambiguidade
	Slide 42: Ambiguidade
	Slide 43: Ambiguidade
	Slide 44: Ambiguidade
	Slide 45: Ambiguidade
	Slide 46: Ambiguidade
	Slide 47: Conectivos lógicos no mundo real
	Slide 48: Conectivos lógicos condicional e bicondicional
	Slide 49: Conectivos lógicos condicional e bicondicional
	Slide 50: Tabela verdade e conectivos lógicos
	Slide 51: Tabela verdade e conectivos lógicos
	Slide 52: Tabela verdade e conectivos lógicos
	Slide 53: Tabela verdade e conectivos lógicos
	Slide 54: Tabela verdade e conectivos lógicos
	Slide 55: Condicional e Bi-condicional
	Slide 56: Condicional e Bi-condicional
	Slide 57: Condicional e Bi-condicional
	Slide 58: Exemplos
	Slide 59: Exemplos
	Slide 60: Exercícios 01c
	Slide 61: Exercícios 01c – Resolução parcial
	Slide 62: Linguagem proposicional
	Slide 63: Gramática de uma linguagem proposicional
	Slide 64: Tautologia
	Slide 65: Contradição
	Slide 66: Contingência
	Slide 67: Exercícios 01d
	Slide 68: Equivalência lógica ()
	Slide 69: Equivalência lógica ()
	Slide 70: Equivalência lógica ()
	Slide 71: Teorema ( e ↔)
	Slide 72: Exercícios 01e
	Slide 73: Regras de equivalência
	Slide 74: Teoremas de De Morgan
	Slide 75: Teoremas de De Morgan :: Negação do operador E
	Slide 76: Teoremas de De Morgan :: Exemplo com operador E
	Slide 77: Teoremas de De Morgan :: Negação do operador OU
	Slide 78: Teoremas de De Morgan :: Exemplo com operador OU
	Slide 79: Regras de equivalência
	Slide 80: Regras de equivalência
	Slide 81: Regras de equivalência (resumo)