Question Source:
2019W1 module 7
formulasheet链接
问题分析属原创， 仅供参考， 如果对notes 有疑问，欢迎跟帖发表
————————————————————————————————————————————————
Q1 slide 4
How many of the following statements are log.
equivalent to ∀x ∈ B, ∃y ∈ C, P(x) → Q(y)?
(1)∀x ∈ B, ∃y ∈ C, ~ Q(y) → ~ P(x)
(2)~ (∃x ∈ B, ∀y ∈ C, P(x) ^ ~ Q(y))
(3)~ (∃x ∈ B, ∀y ∈ C, ~ P(x) v ~ Q(y))
(4)∀y ∈ B, ∃x ∈ C, P(y) → Q(x)
a) None of them
b) One of them
c) Two of them
d) Three of them
e) All four of them
notes:
(1) by contrapositive: ∼q →∼p ≡ p → q
P(x) → Q(y) ≡ ~ Q(y) → ~ P(x), 所以 (1) 是相等的
(2) ~ (∃x ∈ B, ∀y ∈ C, P(x) ^ ~ Q(y))
≡ ∀x ∈ B, ~ (∀y ∈ C, P(x) ^ ~ Q(y))
≡ ∀x ∈ B, ∃y ∈ C, ~ (P(x) ^ ~ Q(y))
≡ ∀x ∈ B, ∃y ∈ C, ~ P(x) ^ (~ ~ Q(y)) De Morgan’s: [DM] ∼(p ∧ q) ≡ (∼p) ∨ (∼q)
≡ ∀x ∈ B, ∃y ∈ C, ~ P(x) ∨ Q(y) Double Negation: [DNEG] ∼(∼p) ≡ p
≡ ∀x ∈ B, ∃y ∈ C, P(x) → Q(y) Implication: [IMP]: p → q ≡∼p ∨ q
所以 (2) 也是相等的
(3) 刚好是 (2) 的相反
(4) 也是相等的。
x 和 y 只是 variable 的名字
domain 是一样的话， 就是相等的
∀x ∈ B, ∃y ∈ C, P(x) → Q(y)
∀y ∈ B, ∃x ∈ C, P(y) → Q(x)
换成另外的名字，像这样，
∀b ∈ B, ∃c ∈ C, P(b) → Q(c)
也是相等的。
所以有三个相等的 [(1), (2), (4)]
————————————————————————————————————————————————
Q2 slide 6
Which of the following could be the result of
applying one of the negation equivalence laws
to the statement:
∀x ∈ D, Q(x)→[(∃ y ∈ D, P(x, y)) ∧ ~(∀y ∈ D, P(x, y))]
a) ∀x ∈ D, Q(x) → F
b) F
c) None: we can not apply the law to just the right side of the statement.
d) None: the law doesn't match the right side of the statement.
notes:
从formulasheet知道， 总共有三个negation laws
Negation: [NEG] p ∨ (∼p) ≡ T *** p ∧ (∼p) ≡ F
Double Negation: [DNEG] ∼(∼p) ≡ p
De Morgan’s: [DM] ∼(p ∧ q) ≡ (∼p) ∨ (∼q) *** ∼(p ∨ q) ≡ (∼p) ∧ (∼q)
问题等式的右边
∃ y ∈ D, P(x, y) ∧ ~(∀y ∈ D, P(x, y))
好像可以用 Negation law 中的 p ∧ (∼p) ≡ F
但是,
~(∀y ∈ D, P(x, y)) ≡ ∃ y ∈ D, ~ P(x, y)
∃ y ∈ D, ~ P(x, y) 不等于 ~(∃ y ∈ D, P(x, y))
所以, no Negation law match the right part of the statement
————————————————————————————————————————————————
Q3 slide 15
What can we do with the negation in:
~ ∃c ∈ R+ , ∃n0 ∈ N, ∀n ∈ N, n ≥ n0 → f(n) ≤ cg(n) ?
a) It cannot be moved inward.
b) It can only move across one quantifier because the
generalized De Morgan’s law can only handle one
quantifier.
c) It can only be moved across all three quantifiers
because a negation can't appear between quantifiers.
d) It could be moved across one, two or all three
quantifiers.
e) None of the above.
notes:
not "" 能往右边挪， 但是quantifier 要改变
∼ ∀x ∈ D, P(x) ≡ ∃x ∈ D, ∼P(x)
∼ ∃x ∈ D, P(x) ≡ ∀x ∈ D, ∼P(x)
例如，
aa~ ∃c ∈ R+ , ∃n0 ∈ N, ∀n ∈ N, n ≥ n0 → f(n) ≤ cg(n)
≡ ∀c ∈ R+ , ~ (∃n0 ∈ N, ∀n ∈ N, n ≥ n0 → f(n) ≤ cg(n) )
≡ ∀c ∈ R+ , ∀n0 ∈ N, ~(∀n ∈ N, n ≥ n0 → f(n) ≤ cg(n) )
≡ ∀c ∈ R+ , ∀n0 ∈ N, ∃n ∈ N, ~ n ≥ n0 → f(n) ≤ cg(n)
~ 可以像内移动到任意位置， 但quantifier要相应变化
所以题目应该选e
————————————————————————————————————————————————
Q4 slide 21
Consider existential instantiation:
∃x ∈ D, P(x)
a ∈ D
——————
P(a)
a) This argument is valid: P(a) is true.
b) This argument is invalid: P(a) is false.
c) This argument is invalid: P(a) might be false.
d) This argument is invalid for another reason.
notes:
例如， D = {1, 2, 3} , P(X) ≡ x > 2
x = 3 时, x > 2，
∃x ∈ D, P(x)
当a = 1 时, 1 ∈ D
但P(a) 不成立
所以， 这一题选C
————————————————————————————————————————————————
Q5 slide 23
What about existential modus ponens?
∃x ∈ D, P(x) → Q(x)
P(a)
—————————
Q(a)
a) This argument is valid, and Q(a) is true.
b) The argument is valid, but the 1st premise can not
be true; so Q(a) might be false.
c) This argument is invalid because Q(a) is false.
d) The argument is invalid for another reason.
notes:
例如， D = {6, 12} , P(X) ≡ x 可以被2整除， Q(X) ≡ x 可以被3整除
x = 6 时, P(x) → Q(x)
所以， ∃x ∈ D, P(x) → Q(x)
当a = 4 时, a 可以等于4 因为题目并没有规定a ∈ D
但P(a) 成立, 但Q(a) 不成立
所以， 这一题选d, The argument is invalid 因为没有规定a ∈ D
————————————————————————————————————————————————
Q6 slide 26
Which propositional logic equivalences apply to predicate logic?
a) Double negative, Identity, and De Morgan's (not all equivalences!)
b) ~(P(x) → Q(x)) ≡ P(x) ∧ ~ Q(x)
c) Commutative, Associative, and the “definition of conditional”
d) All propositional logic equivalences apply to predicate logic.
e) None of the above
notes:
All propositional logic equivalences apply to predicate logic.
————————————————————————————————————————————————
Q7 slide 29
Which rules of inference apply to predicate logic?
a) Modus ponens, modus tollens and elimination only.
b) All rules apply, but only if they follow universal quantifiers, not existential quantifiers.
c) All rules apply, but only if they follow existential quantifiers, not universal quantifiers.
d) All rules apply, no matter what quantifiers are used.
e) None of the above.
notes:
选(b) All rules apply, but only if they follow universal quantifiers, not existential quantifiers.
如果是existential quantifiers的话，就不成立， 例如Q3 slide 15