Prova Matemática Discreta UFG

Prévia do material em texto

UFG - Instituto de Informática Matemática Discreta
Ciências da Computação Prof.a Márcia Cappelle
3a Avaliação 2015.1
Aluno(a): Data : 05/05/2015
1. Seja R uma relação sobre R tal que (x, y) ∈ R se e somente se x− y ∈ Z.
(a) 1,5 Prove que R é uma relação de equivalência.
(b) 1,0 Qual a classe de equivalência do número real 0, 5 na relação R, ou seja, quais os elementos
do conjunto [0, 5]R?
2. Dê um contraexemplo para cada proposição abaixo.
(a) 1,0 Seja P = (A,≺) um conjunto parcialmente ordenado. Se |A| = 3, então (A,≺) tem no
máximo dois elementos maximais.
(b) 1,0 Se R e S são relações de equivalência sobre um conjunto A, então R ∪ S é uma relação de
equivalência sobre A.
(c) 1,0 Seja P = (A,≺) um conjunto parcialmente ordenado. Se a é comparável a qualquer elemento
de A e existe b ∈ A tal que a � b, então a é um elemento mínimo de P .
(d) 1,0 Se R é uma relação de equivalência sobre A, então R não é um relação de ordem parcial
sobre A.
3. 2,0 Responda a estas questões para o poset (X,⊆), X = {{1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {3, 4},
{1, 3, 4}, {2, 3, 4}}.
(a) Desenhe o diagrama de Hasse.
(b) Encontre os elementos maximais.
(c) Encontre os elementos minimais.
4. 1,5 Seja P = (A,≺) um conjunto parcialmente ordenado. Prove que os elementos maximais de P
formam uma anticadeia.
Observações:
• Também serão aceitas respostas a lápis.
• A avaliação é individual e sem qualquer tipo de consulta!
• Para a correção da avaliação serão levados em consideração, além da exatidão, a organização, o rigor e o formalismo
empregados nas respostas.
• Defina a notação utilizada, justifique suas afirmações e os conceitos empregados.