Discrete Mathematics

Question

Let P(x), Q(x), and R(x) be the statements "x is a clear explanation,"

"x is satisfactory," and "x is an excuse," respectively. Suppose that the

domain for x consists of all English text. Express each of these statements using

quantiers, logical operators, and P(x), Q(x), and R(x).

(a) All clear explanations are satisfactory.

(b) Some excuses are unsatisfactory.

(c) Some excuses are not clear explanations.

(d) Does (c) follow from (a) and (b)?

Answer 1

The first three questions require translation, while the last requires a logical proof.

a) ∀x(P(x) ⊃ Q(x)) When you see "All" it's going to be a universal quantifier.

b) ∃x(R(x) ∧ ¬Q(x)) Likewise when you see "Some" it's an existential quantifier.

c) ∃x(R(x) ∧ ¬P(x))

Another "trick" is that for statements like these, universal quantifiers usually have a conditional inside them, whereas existential quantifiers will have a conjunction. This isn't a hard and fast rule, but it's a good assumption.

d) Yes

1. R(α) ∧ ¬Q(α), b Existential instantiation. α is a free variable (Note: To be a neat proof this step should come before 2. The reason is because it's an existential rather than universal instantiation. i.e α might be the only x that is both R and not Q)
2. P(α) ⊃ Q(α), a Universal instantiation
3. ¬Q(α), 1 Simplification
4. ¬P(α), 2 & 4 Modus tollens
5. R(α), 1 Simplification
6. R(α) ∧ ¬P(α), 4 & 5 Conjunction

∴ ∃x(R(x) ∧ ¬P(x)), 6 Existential generalization