BACKUP_3a_prova_lma_2012_2

Prévia do material em texto

3a Avaliação de Lógica Matemática (LMA) - Joinville, 9 de novembro de 2012
Acadêmico(a):
1. Construa as duas fórmulas abaixo em suas respectivas FNC e FND1:
(a) (p→∼ q) ∨ (∼ q → p)
(b) p↔ q
2. Verificar a validade dos teoremas abaixo, usando um dos seguintes métodos de prova:
dedução natural (regras de inferência diretas e propriedades lógicas), ou pela con-
tradição, ou método da demonstração indireta (escolha Duas das Tres abaixo):
(a) {p→∼ q, ∼ p→ (r →∼ q), (∼ s∨ ∼ r)→∼∼ q, ∼ s } ` ∼ r
(b) {(∼ p ∨ q)→ r, (r ∨ s)→∼ t, t } ` ∼ q
(c) {p→ q, q ↔ s, t ∨ (r∧ ∼ s) } ` p→ t
3. Considere cada uma das proposições atômicas abaixo:
(a) y < 0
(b) y = 0
(c) y > 0
(d) x < y
(e) x > y
(f) x = y
Quais destas proposições deveriam ser escolhidas e combinadas, para demostrar ou
concluir a proposição x < 0? Faça suas escolhas e exiba esta demonstração.
4. Rogério, que tal esta questao???? terias que traduzir. Achei esta questao
muito legal.
Consider the game of rock, paper, scissors. With two players, we will use the following
six propositions:
r1 Player 1 chooses rock.
p1 Player 1 chooses paper.
s1 Player 1 chooses scissors.
r2 Player 2 chooses rock.
p2 Player 2 chooses paper.
s2 Player 2 chooses scissors.
(a) Express as a proposition: “Each player must choose at least one of rock, paper, or
scissors.”
(b) Express as a proposition: “Each player cannot choose more than one of rock, paper,
or scissors.”
(c) (100 pts., shared extra credit) Express as short as possible: “Each player must
choose exactly one of rock, paper, or scissors.”
(d) Express as a proposition: “The players tie.” Assume you don’t have to worry about
the previous rule.
1alguns alunos ficaram com dúvidas neste importante tópico do curso
1
(e) Express as a proposition: “Player 1 wins.” Assume you don’t have to worry about
the rule in part (c).
5. Determine o valor verdade {V, F} (a interpretação Φ) de cada uma das fórmulas abaixo,
em seu respectivo domínio. Faça os cálculos em separado e preencha a tabela abaixo.
(Determine the truth value of each statement for each domain.)
Domínios
Num. Reais Reais Positivos Inteiros Inteiros Positivos
∃x(x = −x)
∀x(2x ≤ 3x)
∃x(x2 = 2)
∀x(x ≤ x2)
∀x∃y(xy = 1)
6. Seja o enunciado: “. . . para todo caminho definido de x até z e arco entre z e y, então
há um caminho entre x e y. Sabe-se que todo arco entre x e y é também um caminho
entre x e y”. Sabe-se ainda que há arcos definidos pelas fórmulas: arco(a, b), arco(a, c),
arco(b, d), e arco(c, d). Prove que é possível ir de um ponto a a e definido por um
caminho(a, e) como verdade. Desta vez vamos fornecer a fórmulas referente ao texto
acima, as quais são dadas por:
(a) ∀x∀y∀z(caminho(x, z) ∧ arco(z, y)→ caminho(x, y))
(b) ∀x∀y(arco(x, y)→ caminho(x, y))
(c) arco(a, b)
(d) arco(a, c)
(e) arco(b, d)
(f) arco(c, d)
(g) arco(d, e)
Deduza tal caminho como verdade, indicando todas instâncias das variáveis, PU’s, PE’s
e regras de inferências utilizadas. Faça um grafo (flechas e nós) orientado para ver o
que estás calculando.
2
Equivalências Notáveis:
Idempotência (ID): P ⇔ P ∧ P ou P ⇔ P ∨ P
Comutação (COM): P ∧Q⇔ Q ∧ P ou P ∨Q⇔ Q ∨ P
Associação (ASSOC): P ∧ (Q ∧R)⇔ (P ∧Q) ∧R ou P ∨ (Q ∨R)⇔ (P ∨Q) ∨R
Distribuição (DIST): P ∧(Q∨R)⇔ (P ∧Q)∨(P ∧R) ou P ∨(Q∧R)⇔ (P ∨Q)∧(P ∨R)
Dupla Negação (DN): P ⇔∼∼ P
De Morgan (DM): ∼ (P ∧Q)⇔∼ P∨ ∼ Q ou ∼ (P ∨Q)⇔∼ P∧ ∼ Q
Equivalência da Condicional (COND): P → Q⇔∼ P ∨Q
Bicondicional (BICOND): P ↔ Q⇔ (P → Q) ∧ (Q→ P )
Contraposição (CP): P → Q⇔∼ Q→∼ P
Exportação-Importação (EI): P ∧Q→ R⇔ P → (Q→ R)
Contradição: P∧ ∼ P ⇔ �
Tautologia: P∨ ∼ P ⇔ �
Regras Inferencias Válidas (Teoremas):
Adição (AD): P ` P ∨Q ou P ` Q ∨ P
Simplificação (SIMP): P ∧Q ` P ou P ∧Q ` Q
Conjunção (CONJ) P,Q ` P ∧Q ou P,Q ` Q ∧ P
Absorção (ABS): P → Q ` P → (P ∧Q)
Modus Ponens (MP): P → Q,P ` Q
Modus Tollens (MT): P → Q,∼ Q `∼ P
Silogismo Disjuntivo (SD): P ∨Q,∼ P ` Q ou P ∨Q,∼ Q ` P
Silogismo Hipotético (SH): P → Q,Q→ R ` P → R
Dilema Construtivo (DC): P → Q,R→ S, P ∨R ` Q ∨ S
Dilema Destrutivo (DD): P → Q,R→ S,∼ Q∨ ∼ S `∼ P∨ ∼ R
Observações:
1. Qualquer dúvida, desenvolva a questão e deixe tudo explicado, detalhadamente, que
avaliaremos o seu conhecimentos sobre o assunto;
2. Clareza e legibilidade;
3