Write each of the following arguments in argument form. Then, use the rules of inference to show that each argument is valid.

Question

Let () be “ has taken Calculus I,” () be “ has taken Program Design I,” and () be “ has permission from the instructor to enroll in this class,” where the domain consists of all students in this class.

Every student in this class has taken Calculus I or Program Design I. Every student who has not taken Calculus I but has taken Program Design I, has permission from the instructor to enroll in this class. Therefore, every student who does not have permission from the instructor to enroll in this class has taken Calculus I.

Answer 1

The idea is that an expression of the form "Every student in this class..." refers to whatsoever element of the domain, thus they should be translated by a universal quantifier, i.e. $\forall x \dots$

Concretely,

1. "Every student in this class has taken Calculus I or Program Design I" can be translated by $$ \forall x \, (P(x) \lor Q(x))$$

2. "Every student who has not taken Calculus I but has taken Program Design I, has permission from the instructor to enroll in this class" can be translated by $$\forall x \, ((\lnot P(x) \land Q(x)) \to R(x))$$

3. "Every student who does not have permission from the instructor to enroll in this class has taken Calculus I" can be translated by $$\forall x \, (\lnot R(x) \to P(x))$$

Let us prove that the argument is valid.

First, let us fix an arbitrary $c$ in the domain. We prove that under the hypotheses $ \forall x \, (P(x) \lor Q(x))$ and $\forall x \, ((\lnot P(x) \land Q(x)) \to R(x))$ and the further hypothesis $\lnot R(c)$, then $P(c)$ holds.

1. $ \forall x \, (P(x) \lor Q(x))$ -- hypothesis
2. $\forall x \, ((\lnot P(x) \land Q(x)) \to R(x))$ -- hypothesis
3. $\lnot R(c)$ -- hypothesis
4. $(\lnot P(c) \land Q(c)) \to R(c)$ -- universal instantiation of 2. by $[c/x]$
5. $\lnot(\lnot P(x) \land Q(x))$ -- modus tollens
6. $P(c) \lor \lnot Q(c)$ -- De Morgan
7. $P(c) \lor Q(c)$ -- universal instantiation of 1. by $[c/x]$
8. $P(c)$ -- resolution

A well-known low of logic called Deduction Theorem says that if you can derive $B$ from the hypotheses $A, A_1, \dots, A_n$, then you can derive $A \to B$ from the hypotheses $A_1, \dots, A_n$.

Therefore, from the derivation above we conclude that there is a derivation of $\lnot R(c) \to P(c)$ from the hypotheses $ \forall x \, (P(x) \lor Q(x))$ and $\forall x \, ((\lnot P(x) \land Q(x)) \to R(x))$. But such a derivation is valid for an arbitrary $c$ (there is no hypothesis concerning $c$). Hence, by applying the rule of universal generalization, we conclude that $\forall x \, (\lnot R(x) \to P(x))$ holds under the hypotheses $ \forall x \, (P(x) \lor Q(x))$ and $\forall x \, ((\lnot P(x) \land Q(x)) \to R(x))$.