Matemática Discreta para
Computação e Informática
P. Blauth Menezes blauth@inf.ufrgs.br Departamento de Informática Teórica
Instituto de Informática / UFRGS

Matemática Discreta para Computação e Informática - P. Blauth Menezes

1

Matemática Discreta para Computação e Informática
P. Blauth Menezes
1
2
3
4
5
6
7
8
9
10
11

Introdução e Conceitos Básicos
Noções de Lógica e Técnicas de Demonstração
Álgebra de Conjuntos
Relações
Funções Parciais e Totais
Endorrelações, Ordenação e Equivalência
Cardinalidade de Conjuntos
Indução e Recursão
Álgebras e Homomorfismos
Reticulados e Álgebra Booleana
Conclusões

Matemática Discreta para Computação e Informática - P. Blauth Menezes

2

2 – Lógica e …exibir mais conteúdo…

Blauth Menezes

10

2.1.1

Proposições

Def: Proposição
Construção (sentença, frase, pensamento) que pode-se atribuir juízo
• tipo de juízo na Lógica Matemática
∗ verdadeiro-falso
∗ interesse é na “verdade” das proposições

♦ Forma tradicional de tratar com a “verdade”
• dois valores verdade V (verdadeiro) e F (falso)
• proposições só podem assumir esses valores

♦ Denotação do valor verdade de uma proposição p
V(p)
Matemática Discreta para Computação e Informática - P. Blauth Menezes

11

Exp: Proposição
•
•
•
•

Brasil é um país
Buenos Aires é a capital do Brasil
3+4>5
7-1=5

(valor verdade V)
(valor verdade F)
(valor verdade V)
(valor verdade F)

Ou seja
•
•
•
•

V(Brasil é um país) = V
V(Buenos Aires é a capital do Brasil) = F
V(3 + 4 > 5) = V
V(7 - 1 = 5) = F

Matemática Discreta para Computação e Informática - P. Blauth Menezes

12

Exp: Não são proposição
Vá tomar banho.
Que horas são?
Parabéns!

Matemática Discreta para Computação e Informática - P. Blauth Menezes

13

2 – Noções de Lógica e

Técnicas de Demonstração
2.1 Lógica
2.1.1
2.1.2
2.1.3
2.1.4
2.1.5
2.1.6
2.1.7

Proposições
Conetivos
Fórmulas, Ling. Lógica e Tabelas Verdade
Lógica nas Linguagens de Programação
Tautologia e Contradição
Implicação e Equivalência
Quantificadores

2.2 Técnicas