Mat Disc AULA01

Prévia do material em texto

Matemática Discreta - AULA01 - Prof. Rafael Matos 
 
Bibliografia utilizada: 
ROSEN, K. H. Matemática Discreta e suas aplicações. 
Introdução e Capítulo I. 
 
Tema: 
Lógica Formal. Conectivos e valores lógicos: Negação, conjunção, disjunção, implicação 
e bi-implicação. Tabelas-verdade. 
 
Notas: 
- TODO Diagramas de Venn na parte de conjuntos; 
 
Matemática discreta é a parte da matemática voltada para o estudo dos objetos discretos 
(elementos distintos ou desconexos). A partir deste estudo, pode-se chegar a soluções de 
problemas tais como: 
 
● Descobrir quantas formas de senhas válidas podem existir em um sistema 
computacional; 
● Calcular probabilidades de se ganhar na loteria; 
● Identificar ​e-mails ​ como ​spam​ ; 
● Descobrir o menor caminho entre duas cidades (por exemplo, por transporte público); 
● Verificar quantos passos são necessários para chegar a uma escolha; 
● Provar que algoritmos podem resolver corretamente um problema; 
 
A razão principal do crescimento da ​computação discreta ​é ser o modo como os 
computadores trabalham ​com as informações. Sua utilização em algoritmos e lógica de 
programação é essencial. 
 
Lógica formal 
 
Lógica é a base de todo raciocínio matemático e também automatizado, sendo aplicado em 
inteligência artificial e programação de computadores, entre outros. 
 
Baseado na estrutura do ​raciocínio​, a Lógica Formal relaciona conceitos e fornece um meio de 
compor provas de declarações (significado preciso para sentenças matemáticas). Os conceitos 
são rigorosamente definidos, e as proposições são transformadas em notações simbólicas 
precisas e sem ambiguidade. 
 
Os elementos mais básicos são as ​proposições​, ou seja, uma sentença que declara um fato, o 
qual pode ser verdadeiro ou falso (e não ambos ao mesmo tempo). 
 
Exemplo de proposições: 
1. Brasília é a capital do Brasil (verdadeira); 
2. Buenos Aires é a capital do Chile (falsa); 
3. 1 + 1 = 2 (verdadeira); 
4. 2 + 2 = 5 (falsa); 
 
Exemplo de não-proposições: 
1. Que horas são? (não declara um fato); 
2. x + y = z (não é verdadeiro nem falso); 
 
Variáveis proposicionais ​são as que representam proposições, sendo representadas por 
letras (por convenção, p, q, r, s, ...). Se uma proposição for verdade, seu valor-verdade é 
indicado por V. Caso seja falsa, indicado por F. 
 
Esta área de lógica proposicional foi desenvolvida por ​Aristóteles​, e métodos para produzir 
novas proposições a partir das já existentes foram discutidas por ​George Boole​. 
 
Conectivos e valores lógicos 
 
Tabelas verdade 
 
Tipo de tabela matemática usada em Lógica para determinar se uma fórmula é válida ou se um 
conjunto de proposições está correto. 
 
Negação 
Seja ​p uma proposição. A negação de ​p é indicada por ​e a sentença em questão p ou p¬ 
deve ser lida como "Não é o caso de ​p​ " ou "Não ​p​ ". 
Exemplo: 
"Hoje é domingo." A negação pode ser "Não é o caso de hoje ser domingo" ⇒ 
ou "Hoje não é domingo." 
p p¬ 
F V 
V F 
Tabela-Verdade para a negação de uma proposição 
 
Conjunção 
Sejam ​p e ​q proposições. A conjunção de ​p e ​q é indicada por ​e a sentença em p ⋀ q 
questão deve ser lida como "​p e ​q​ ". A conjunção será verdadeira apenas se ambas forem 
verdadeiras. 
p q p ⋀ q 
F F F 
F V F 
V F F 
V V V 
Tabela-Verdade para a conjunção de duas proposições 
 
Disjunção 
Disjunção inclusiva 
Sejam ​p e ​q proposições. A disjunção inclusiva de ​p e ​q é indicada por ​e a p ⋁ q 
sentença em questão deve ser lida como "​p ou ​q​ ". A disjunção será falsa apenas se ambas 
forem falsas. 
p q p ⋁ q 
F F F 
F V V 
V F V 
V V V 
Tabela-Verdade para a disjunção inclusiva de duas proposições 
 
Disjunção exclusiva 
Sejam ​p e ​q proposições. A disjunção exclusiva de ​p e ​q é indicada por ​e a p ⊕ q 
sentença em questão deve ser lida como "​p ou ​q​ ". A disjunção será verdadeira quando apenas 
uma, e somente uma, das proposições for verdadeira. 
p q p ⊕ q 
F F F 
F V V 
V F V 
V V F 
Tabela-Verdade para a disjunção exclusiva de duas proposições 
 
Implicação (ou condicional) 
Sejam ​p e ​q proposições. A proposição condicional ​deve ser lida como "se ​p, p → q 
então ​q​ ". A condicional será falsa quando ​p for verdadeira e ​q falsa, e será verdadeira nos 
outros casos. Neste caso, ​p​ é chamada hipótese e ​q​ a conclusão. 
p q p → q 
F F V 
F V V 
V F F 
V V V 
Tabela-Verdade para a implicação entre duas proposições 
 
Obs.: A implicação, em lógica, é diferente das declarações ​if ​p ​then ​q utilizadas em 
programação. 
 
Bi-implicação (ou equivalência) 
Sejam ​p e ​q proposições. A proposição bicondicional ​deve ser lida como "​p​ se e p ↔ q 
somente se ​q​ ". A bicondicional será verdadeira quando ambas forem verdadeiras ou ambas 
forem falsas. 
 
p q p ↔ q 
F F V 
F V F 
V F F 
V V V 
Tabela-Verdade para a bi-implicação entre duas proposições 
 
Prioridade dos Operadores 
 
Operador Prioridade 
¬ 1 
⋀ 2 
⋁ 3 
→ 4 
↔ 5 
Prioridade dos operadores 
 
Exercícios 
 
Construir a tabela-verdade de: 
 
a) ;p q) p )( ⋁ ¬ → ( ⋀ q 
b) ;p¬ 
c) ;p¬ ⋁ q 
d) ;pq ↔ ¬