1ª Lista de matemática discreta

Aluno: Mateus Cezário Barreto.

Nota: Ao lado de cada equivalência dentro de uma cadeia de equivalências, está grafada a propriedade usada para se chegar nela a partir da anterior.

Questão 1

`p vv not p equiv top`

`p ^^ not p equiv bot`

`p vv p equiv p`

`p ^^ p equiv p`

`not (p vv q) equiv (not p ^^ not q)`

`p => q equiv not p vv q`

`p vv q equiv q vv p`

`p ^^ q equiv q ^^ p`

`(p vv q) vv r equiv p vv (q vv r) equiv p vv q vv r`

`(p ^^ q) ^^ r equiv p ^^ (q ^^ r) equiv p ^^ q ^^ r`

`p vv top equiv top`

`p ^^ bot equiv bot`

`(p ^^ q) vv p equiv p`

`(p vv q) ^^ p equiv p`

`p vv bot equiv p`

`p ^^ top equiv p`

`p => not p equiv not p`

`because p => not p equiv (not p vv not p)` implicação e disjunção

`equiv not p` idempotência

`not p => p equiv p`

`because not p => p equiv (p vv p)` implicação e disjunção

`equiv p` idempotência

`(p <=> q) equiv (p => q) ^^ (q => p)`

Letra A

`not p => (q => r)`

`equiv p vv (q => r)` implicação e disjunção

`equiv p vv (not q vv r)` implicação e disjunção

`equiv p vv not q vv r` associatividade

`equiv not q vv p vv r` comutatividade

`equiv not q vv (p vv r)` associatividade

`equiv q => (p vv r)` implicação e disjunção

Letra B

`(p => r) vv (q => r)`

`equiv (not p vv r) vv (not q vv r)` implicação e disjunção

`equiv not p vv r vv not q vv r` associatividade da disjunção

`equiv not p vv not q vv r vv r` associatividade da disjunção

`equiv not p vv not q vv r` identidade da disjunção

`equiv (not p vv not q) vv r` associatividade da disjunção

`equiv not (not p vv not q) => r` implicação e disjunção

`equiv (p ^^ q) => r` de'morgan

Letra C

`not p ^^ (p vv q) => q`

`equiv not (not p ^^ (p vv q)) vv q` implicação e disjunção

`equiv (p vv not (p vv q)) vv q` de'morgan

`equiv (p vv not p) vv (q vv q)` idempotência

`equiv (p vv not p) vv q` terceiro excluído

`equiv top vv q` dominação

`equiv top`

Letra D

`a equiv (p ^^ not q)`

`(p ^^ not q) <=> ((p ^^ not q) => (q vv not p))`

`equiv a <=> (a => not a)` 1.D a

`equiv a <=> not a` contradição

`equiv (a => not a) ^^ (not a => a)` bi-implicação

`equiv not a ^^ (not a => a)` contradição

`equiv not a ^^ a` consequentia mirabilis

`equiv bot` terceiro excluído

Questão 2

`not p => r ^^ not s`

`t => s`

`u => not p`

`not w`

`u vv w`

`therefore not t vv w`

Suponhamos que f seja falsa.

`not t vv w`

`not (not t vv w)`

`equiv t ^^ not w`

Logo `t` é verdadeiro.

Com base em d e e, `u` é verdadeiro.

`u vv bot equiv u`

Com base em c, `p` é falso:

`top => not p`

`equiv not p`

Com base em a, e sendo `p` falso, `r` é verdadeiro e `s` é falso:

`top => r not s`

`equiv r ^^ not s`

No entanto, com base em b e na hipótese inicial (t é verdadeiro):

`top => s`

`equiv s`

Havendo uma contradição no valor de s

Questão 3

`E = (p oplus q) ^^ (p oplus not q)`

`p`	`q`	`E`
F	F	F
F	V	F
V	F	F
V	V	F

E é uma contradição

Questão 4

Seja o operador `odot` definido conforme definição de xnor

`(p odot q) equiv ((p^^q) vv (not p ^^ not q))`

Letra A

`a equiv (p ^^ q)`

`b equiv (not p ^^ not q)`

`p odot q equiv a vv b` definição de xnor

`x odot y ^^ z equiv x odot (y ^^ z) because a vv b ^^ z equiv a vv (b ^^ z)` xnor para disjunção

Letra B

Hipótese:

`x`	`y`	`z`	`x odot (y ^^ z)`	`(x odot y) ^^ (x odot z)`
F	F	F	V	V
F	F	V	V	F
F	V	F	V	F
F	V	V	F	F
V	F	F	F	F
V	F	V	F	F
V	V	F	F	F
V	V	V	V	V

Retomando 1:

O operador `odot` não segue a lei da distributiva.

`x odot (y ^^ z) != (x odot y) ^^ (x odot z)`

Questão 5

`p ^^ not q => r`

`p vv q`

`q => p`

`therefore r`

`(q => p)` c

`equiv (not q vv p)` implicação e disjunção

`equiv (p vv not q)` comutatividade

`(p vv q) ^^ (p vv not q)` b e

`((p ^^ (p vv q)) vv (not q ^^ (p vv q)))` distributividade

`((p^^p) vv (p^^q)) vv ((not q ^^ p) vv (not q ^^ q))` distributividade

`((p^^p) vv (p^^q)) vv ((not q ^^ p) vv bot)` terceiro excluído

`((p^^p) vv (p^^q)) vv (not q ^^ p)` identidade

`(p vv (p^^q)) vv (not q ^^ p)` idempotência

`p vv (not q ^^ p)` absorção

`p` absorção

A conclusão d seria sustentada pelo valor de `q`, pois, conforme em a

`p ^^ not q => r` a

`equiv top ^^ not q => r` p verdadeiro

`equiv not q => r`

Mas, já exauridas as considerações, nada leva à assumir o valor de `q`. E, portanto, nada leva a assumir o valor de `r`.

Questão 6

Como por (e) sabemos que s é falso e a falsidade de s implica na falsidade de t, conforme (c), resta que w seja verdadeiro, baseado em (g).

Sabendo que s é falso, baseado em (b), r é verdadeiro. A mesma lógica ocorrem em (d), de onde extrai-se que q é falso. A partir de (a), sendo q falso, p também é falso, completando a condição de (f) de onde afirma-se que u é verdadeiro.

Sendo u e w veradeiros, a conclusão em (h) é válida.

Questão 7

a = [Sistema de arqivos está destravado]

b = [Novas mensagens serão enfileiradas]

c = [Novas mensagens serão enviadas para o buffer]

d = [Sistema funcionando]

`a => b`

`a <=> d`

`a vv not b => c`

`c`

O O sistema é consistente. As duas primeiras proposições lógicas não apresentam contradição, e o fato de `c` ser verdadeiro valida a implicação em `c`.

Questão 8

`x leftarrow not (x odot y)`

`y leftarrow not (x odot y)`

`x leftarrow not (x odot y)`

`not (p odot q) equiv p oplus q`

`x leftarrow x oplus y`

`y leftarrow x oplus y`

`x leftarrow x oplus y`

O valor final de `x` contém o valor inicial de `y`, e o valor final de `y` contém o valor inicial de `x`.

É possível visualizar melhor a troca com mais identificadores para representar os três valores, respectivamente.

`x oplus y`

`a oplus y`

`a oplus b`

`b equiv (x oplus y) oplus y`

`equiv x oplus (y oplus y)` associatividade

`equiv x oplus bot` contradição

`equiv x` identidade

`c equiv a oplus x` valor de b

`equiv (x oplus y) oplus x` a

`equiv x oplus y oplus x` associatividade

`equiv x oplus x oplus y` comutatividade

`equiv bot oplus y` contradição

`equiv y` identidade

Lembrando que `b` representa o valor final de `y` (que é `x`) e `c` representa o valor final de `y` (que é `y`).

Questão 9

`e = ` [Estudante dessa classe]

`l = ` [Ter lido o livro]

`p = ` [Passar no primeiro exame]

`exists e (not l(e))`

`forall e (p(e))`

`therefore exists e (not l(e) ^^ p(e))`

A conclusão pode ser justificada por instanciação.

`exists e (not l(e)) => not l(c)`

`forall e (p(e)) => p(c)`

`therefore not l(c) ^^ p(c)`

Questão 10

`i = ` [Diminuição da taxa para importação]

`f = ` [Diminuição da taxa federal]

`c = ` [Aumento do comércio]

`i => c`

`f oplus not c equiv f odot c`

`i`

`therefore f`

Se `i` é verdadeiro, `c` também é com base em importação e comércio. Isso significa que `f` também é verdadeiro, conforme taxa federal e comércio. O argumento é válido.

Questão 11

`p => q equiv (p ^^ not q) => bot`

`p`	`q`	`p => q`	`(p ^^ not q) => bot`
F	F	V	V
F	V	V	V
V	F	F	F
V	V	V	V

Questão 12

Sabemos que existe um `x` que satisfaz `P` e que existe um `x` que satisfaz `Q`, o erro está em 3 e 5, ao supor que a instância que satisfaz cada propriedade é a mesma.

Questão 13

Letra A

`s_1 : p ^^ not q ^^ not r`

`s_1** : p vv not q vv not r`

`s_2 : (p ^^ q ^^ r) vv t`

`s_2** : (p vv q vv r) ^^ t`

`s_3 : (p vv bot) ^^ (q vv top)`

`s_3** : (p ^^ top) vv (q ^^ bot)`

Letra B

`s_1 : `(p ^^ q) vv p equiv p`

`s_1** : `(p vv q) ^^ p equiv p`

`s_1 equiv s_1**` absorção

Letra C

`p : x vv top`

`p** : x ^^ bot`

`q : top`

`q** : bot`

`p equiv q` dominação

`p** equiv q** ` dominação