A MATEMÁTICA DISCRETA

wRESOLUÇÃO DA LISTA DOS MONITORES - MINIPROVA 1

MATEMÁTICA DISCRETA

1. Escreva uma equação equivalente ao XOR (OU exclusivo) usando apenas AND, OR  ou NOT.

Utilizando a tabela da verdade do XOR, observamos que:

P	Q	P xor Q
F	F	F
F	V	V
V	F	V
V	V	F

P xor Q é verdade apenas quando P e Q forem diferentes.

Escrevendo isso com AND, OR e NOT, temos que:

P xor Q ≡ (¬P ∧ Q) ∨ ( P ∧ ¬Q)

2. Se x³ é um número irracional, então x é um número irracional ?

Por contraposição (A → B ≡ ¬B→¬A), vamos provar que se x não é um número irracional, então x³ também não será um número irracional.

Se um número não é irracional, ele é racional, e pode ser escrito como uma fração irredutível entre dois inteiros.

Logo, se assumirmos que x é um número racional, o mesmo pode ser escrito como:

x = a/b

Onde a e b são inteiros e primos entre si.

Logo a expressão de x³ vira:

x³ = a³/b³

Onde a³ e b³ também são primos entre si, logo a³/b³ não é redutível. Ou seja, quando x for racional, x³ também será.

Isso prova, por contraposição, que o único jeito de x³ ser irracional, é se x também for irracional.

3. Se x é um número irracional, então x³ é um número irracional ?

Isso não é verdade, então não pode ser provado.

Um contraexemplo para provar que essa implicação é falsa seria qualquer raiz cúbica de um inteiro, visto que raiz cúbica de 5 é um número irracional, mas 5 é racional.

Vale lembrar que para provar que uma expressão não é verdade, precisa-se apenas de um exemplo, mas para provar que é verdade, é necessário utilizar as estratégias de provas trabalhadas em sala.

4. Prove que:

¬(P↔Q) ≡ ¬P↔Q

a) Por tabela da verdade.

P	Q	P↔Q	¬(P↔Q)	¬P↔Q
F	F	V	F	F
F	V	F	V	V
V	F	F	V	V
V	V	V	F	F

b) Por equivalência lógica.

¬(P↔Q) ≡ ¬P↔Q

[29]

¬( (P→Q) ∧ (Q→P) ) ≡ ¬P↔Q

[20]

¬( (¬P ∨ Q) ∧ (¬Q ∨ P) ) ≡ ¬P↔Q

[14]

¬(¬P ∨ Q) v ¬(¬Q ∨ P) ≡ ¬P↔Q

[15]

(P ∧ ¬Q) ∨ (Q ∧ ¬P) ≡ ¬P↔Q

[8]

(P ∧ ¬Q) ∨ (¬P ∧ Q) ≡ ¬P↔Q

[31]

 ¬P↔Q ≡ ¬P↔Q

5. Determine se as sentenças abaixo são verdadeiras ou falsas.

A diferença entre pertencer e estar contido é uma das informações triviais que se deve levar para prova.

Quando refere-se a pertencer, estamos falando de um elemento em relação a um conjunto.

Um elemento pertence a um conjunto quando o conjunto contém o elemento como um de seus elementos. É uma noção bem intuitiva que ficará bem clara com os exemplos dados.

Quando refere-se a estar contido, estamos falando de uma relação de um conjunto para com outro conjunto.

Isso ocorre quando todos os elementos de um conjunto estão presentes no outro.

Ou seja, um conjunto {0, 1, 2} está contido em {0, 1, 2, 3}, porque 0, 1 e 2 pertencem ao conjunto {0, 1, 2, 3}.

1. 2 ∈ {0, 2, 4, 6, 8}

É verdade, pois o elemento 2 está explicitamente declarado como parte do conjunto {0, 2, 4, 6, 8}.

1. {2} ⊆ { {0}, {2}, {4}, {6}, {8} }

É falso, para estar contido, todos os elementos do primeiro conjuntos precisam pertencer ao segundo conjunto.

Nesse caso, { {0}, {2}, {4}, {6}, {8} } precisaria conter o elemento 2. Note que um dos elementos é um conjunto que contém 2, mas

{2} não é 2, não confundam.

Algumas pessoas gostam de visualizar um conjunto como uma caixa. Nessa lógica, considera-se que uma caixa que tem um 2 dentro, não é a mesma coisa do 2 em si.

1. {1, 2} ⊆ {0, 1, 2, 3, 4}

É verdade, pois tanto o 1 como o 2 pertencem ao segundo conjunto.

{1, 2} C {0, 1, 2, 3, 4}.

1. 5 ∈ { {1, 2}, {3, 4, 5} }

É falso, pois o elemento 5 não pertence ao conjunto.

Seguindo a mesma lógica da caixa, pode-se olhar o conjunto como uma caixa que contém duas caixas menores, {1, 2} e {3, 4, 5}. Perceba que nenhuma dessas caixas é o elemento 5, então 5 não está na bolsa.