Aulas de MD

Prévia do material em texto

Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Prof Edjard Mota 
Instituto de Computação 
(UFAM)
Parte desses slides foram adaptados de aulas do 
professor Eduardo Nakamura
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Lógica
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Estuda os princípios de raciocínio válidos, 
inferências e demonstrações.
● Origens pré-históricas
‣ Babilônia 
‣Sakikkū: Manual de Diagnóstico - 1000 AC de 
Esagil-kin-apli baseado em axiomas e premissas.
‣Astrônomos usavam “lógica interna”, 800 a 700 
AC, para prever trajetos de objetos planetários.
‣ Egito antigo 3000 AC: “descobriram” a geometria 
(Frustum - volume do tronco de uma pirâmide)
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
● India 650 AC, (Ānvīkṣikī): “ciência do 
inquirir”: exame sistemático usando
‣ P: ser
‣ não P: não ser
‣ P e não P: ser e não ser
‣ não (P ou não P): nem ser, nem não ser
● China 500-400 AC (Escola Mohist): 
inferências válidas e conclusões corretas
Matemática Discreta
Lógica
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
século	5	
A.C.
Tales (624 A.C. – 546 A.C.) filósofo, matemático e astrônomo grego. O 
primeiro a explicar o mundo e o universo usando hipóteses e teorias.
ht
tp
:/
/e
n.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Th
al
es
_o
f_
M
ile
tu
s
Lógica no Ocidente
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
século	4	
D.C.
ht
tp
:/
/e
n.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Py
th
ag
or
as
século	5	
A.C.
ht
tp
:/
/e
n.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Th
al
es
_o
f_
M
ile
tu
s
Pitágoras (570 A.C. – 495 A.C.) filósofo, matemático grego. O primeiro a 
construir uma prova de a2 = b2 + c2 (usado por hindus e babilônios)
Lógica no Ocidente
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
século	IV	
A.C.
Aristóteles (384 a.C. – 322 a.C.) filósofo grego. Sistematizou a lógica, 
definindo esquemas de argumentos, silogismos, para efetuar 
interferência que eram válidas e as que não eram. Base do raciocínio 
dedutivo aplicado em qualquer área do conhecimento.
ht
tp
:/
/e
n.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
A
ri
st
ot
le
Lógica no Ocidente
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
século	IV	
A.C.
Gottfried Wilhelm von Leibniz (1646 – 1716) filósofo e matemático 
alemão. Desenvolveu o cálculo diferencial e integral, quase que em 
em paralelo e independente de Isaac Newton. Introduziu o uso
de símbolos para mecanizar o processo de raciocínio dedutivo. 
século	XVI	
D.C.
ht
tp
:/
/e
n.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
G
ot
tf
ri
ed
_W
ilh
el
m
_L
ei
bn
iz
ht
tp
:/
/e
n.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
A
ri
st
ot
le
Lógica no Ocidente
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Filósofos e matemáticos ingleses George Boole (1815 – 1864) e 
Augustus De Morgan (1806 – 1871), lançaram as Bases da lógica 
simbólica moderna usando as ideias de Leibniz. 
século	XIX	
D.C.
século	XIX	
D.C.
ht
tp
:/
/e
n.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
G
eo
rg
e_
Bo
ol
e
ht
tp
:/
/e
n.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
A
ug
us
tu
s_
D
e_
M
or
ga
n
ht
tp
:/
/e
n.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
G
ot
tf
ri
ed
_W
ilh
el
m
_L
ei
bn
iz
ht
tp
:/
/e
n.
w
ik
ip
ed
ia
.o
rg
/w
ik
i/
A
ri
st
ot
le
século	IV	
A.C.
século	XVI	
D.C.
Lógica no Ocidente
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Lógica Formal
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Bases para o método de pensar organizado;
● Sistema (linguagem) formal usado para 
representar o conhecimento, ou premissas e 
efetuar (execução de regras)
● Definem uma linguagem lógica
◆ Sintaxe (Notação), conjunto de símbolos e expressões 
◆ O significado das expressões na linguagem lógica 
◆ Regras de transformação (ou de dedução)
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Fundamental para o desenvolvimento da 
Ciência da Computação
1. Circuitos Lógicos;
2. Prova se programas/hardware estão corretos ou não
3. Teoria de autômatos e computabilidade;
4. Teoria de linguagens;
5. Inteligência Artificial;
6. Banco de Dados;
7. Sistemas Computacionais (hardware e software)
8. Sistemas Distribuídos;
Lógica Formal
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Proposições
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Uma proposição é uma sentença, cujo valor lógico é 
verdadeiro (V) ou falso (F), nunca ambos
● Exemplo de proposições (atômicas)
Manaus é a capital do Amazonas
1 + 1 = 2
x + 5 = 3
Como você está?
9 < 5
Ela é muito talentosa
Existem outras formas de vida em outros universos
Esta frase é falsa
V
V
V ou F
-
F
?
V ou F
!
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Argumento
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Do ponto de vista da matemática e da 
lógica
◆ Um argumento não é uma disputa
◆ Um argumento é uma sequência de comandos/afirmações que 
termina numa conclusão
● Um argumento ser válido significa que a 
conclusão pode ser obtida 
necessariamente das afirmações que 
precedem
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Proposições
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● PROPOSIÇÕES	ATÔMICAS	são	representadas	por	
meio	de	variáveis	proposicionais	
◆ Variáveis proposicionais: (P, Q, R, S, . . .)
◆ Constantes proposicionais: (V, F) → (T, 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
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Conectivos lógicos básicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● 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
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Conectivos lógicos básicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● 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
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Conectivos lógicosbásicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● 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
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Exercícios
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
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.
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● 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
ht
tp
:/
/p
t.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Lu
dw
ig
_W
itt
ge
ns
te
in
ht
tp
:/
/p
t.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Em
il_
Po
st
ht
tp
:/
/p
t.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
Ch
ar
le
s_
Sa
nd
er
s_
Pe
irc
e
ht
tp
:/
/p
t.w
ik
ip
ed
ia
.o
rg
/w
ik
i/
G
ot
tlo
b_
Fr
eg
e
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade e conectivos lógicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Tabela da Verdade
● Negação
Negação
P ¬P
V F
F V
Se	P	é	verdade,	então	¬P	é	falso;	e	se	P	
é	falso	¬P	é	verdade
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade e conectivos lógicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Tabela da Verdade
● Conjunção
Conjunção
P Q P∧Q
V V V
V F F
F V F
F F FSe	P	e	Q	são	verdade,	então	P∧Q	
é	verdade;	caso	contrário	P∧Q	é	
falso
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade e conectivos lógicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Tabela da Verdade
● Disjunção
Disjunção
P Q P∨Q
V V V
V F V
F V V
F F FSe	P	e	Q	são	falsos,	então	P∨Q	é	
falso;	caso	contrário	P∨Q	é	
verdade.
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade: proposição composta
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● 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
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade: proposição composta
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● 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
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Exercícios
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
1. Escreva as seguintes sentenças como 
proposições em lógica:
a) Milcíades lê O Mascate ou Folha de São Paulo, mas não lê o Valor 
Econômico.
b) Leonêsa é pobre, ou é rica e infeliz.
c) Vai chover ou vai nevar, mas não ambos.
2. Construa a tabela-verdade das seguintes 
proposições:
a) (P∧Q)∧¬(P∨Q) 
b) ¬(¬P∨Q)
c) (P∨Q)∧¬Q
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Conectivos lógicos condicional e bicondicional
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● 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 ser fácil é condição suficiente 
 para eu ser aprovado 
Serei aprovado caso MD seja fácil 
Proposições	atômicas	
P:		MD	é	fácil	
Q:	Serei	aprovado
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Conectivos lógicos condicional e bicondicional
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● 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
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade e conectivos lógicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Tabela da Verdade
● Condicional
Condicional
P Q P→Q
V V V
V F F
F V V
F F VSe P é verdade e Q é falso, 
então P→Q é falso; caso 
contrário é verdadeiro
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade e conectivos lógicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Tabela da Verdade
● Condicional
Condicional
P Q P→Q
V V V
V F F
F V V
F F VCaso interessante: se P é 
falso e Q é verdadeiro, então 
P→Q é verdadeiro
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade e conectivos lógicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Tabela da Verdade
● Condicional
Condicional
P Q P→Q
V V V
V F F
F V V
F F V
Se	Ozzy	Osbourne	cantou	no	Restart,	então	
todos	passarão	em	MD	
Quando	nevou	em	Manaus,	choveu	piranhas	
em	Paris
Verdadeiro	ou	falso?
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade e conectivos lógicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Tabela da Verdade
● Condicional
Condicional
P Q P→Q
V V V
V F F
F V V
F F V
Bruna	Marquezine	lhe	fez	a	seguinte	
promessa	para	Ernestino:	
Se	você	ganhar	na	megasena,	então	
eu	caso	com	você
Em	que	situação	Bruna	
estaria	mentido?
E	se	Ernestino	não	ganhar	
na	megasena?
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Tabela verdade e conectivos lógicos
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
● Tabela da Verdade
● Bicondicional
Bicondicional
P Q P↔Q
V V V
V F F
F V F
F F VSe	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
Aula 01 Copyright 2018 Instituto de Computação-UFAM - Edjard Mota
Matemática Discreta
Exercícios
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
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 elasserã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 ]