Discrete Mathematics Study Center

Home Course Notes Exercises Mock Exam About

Arguments and Validity

Now that we know how to state things precisely, we are ready to think about putting statements together to form arguments. A rigorous argument that is valid constitutes a proof. We need to put the statements together using valid rules.

For example, given the premises:

• "if it is cloudy outside, then it will rain"
• "it is cloudy outside"

a conclusion might be "it will rain". Intuitively, this seems valid.

An argument is valid if the truth of the premises implies the conclusion. Given premises $p_1, p_2, \ldots, p_n$, and conclusion $c$, the argument is valid if and only if $(p_1 \wedge p_2 \wedge \cdots \wedge p_n) \rightarrow c$. Note that false premises can lead to a false conclusion!

Rules of Inference

How do we show validity? We use the rules of inference:

• Addition: given $p$, conclude $p \vee q$
• Conjunction: given $p$ and $q$, conclude $p \wedge q$
• Simplification: given $p \wedge q$, conclude $p$ and $q$
• Modus Ponens: given $p$ and $p \rightarrow q$, conclude $q$
• Modus Tollens: given $\neg q$ and $p \rightarrow q$, conclude $\neg p$
• Hypothetical Syllogism: given $p \rightarrow q$ and $q \rightarrow r$, conclude $p \rightarrow r$
• Disjunctive Syllogism: given $p \vee q$ and $\neg p$, conclude $q$
• Resolution: given $p \vee q$ and $\neg p \vee r$, conclude $q \vee r$

To show that the premises imply the conclusion, we apply the rules of inference to the premises until we get the conclusion. Here are some examples of how to show an argument is valid:

• Consider the argument:
  • It is not sunny this afternoon and it is colder than yesterday.
  • We will go swimming only if it is sunny.
  • If we do not go swimming, then we will take a canoe trip.
  • If we take a canoe trip, we will be home by sunset.
  • Therefore, we will be home by sunset.
  To determine if this argument is valid, we should begin by translating it into logic. Let $p$ denote "It is sunny this afternoon", $q$ denote "It is colder than yesterday", $r$ denote "We will go swimming", $s$ denote "We will take a canoe trip" and $t$ denote "We will be home by sunset." The premises are therefore $\neg p \wedge q$, $r \rightarrow p$, $\neg r \rightarrow s$, $s \rightarrow t$ and the conclusion is $t$. Apply the following rules of inference. \begin{array}{lll} 1. & \neg p \wedge q & \\ 2. & r \rightarrow p & \\ 3. & \neg r \rightarrow s & \\ 4. & s \rightarrow t & \therefore t \\ \hline 5. & \neg p & \text{Simplification (1)} \\ 6. & \neg r & \text{Modus Tollens (2,5)} \\ 7. & s & \text{Modus Ponens (3,6)} \\ 8. & t & \text{Modus Ponens (4,7)} \\ \end{array} Since we were able to derive the conclusion from the premises using the rules of inference, the argument is valid.

It is also valid to replace premises with others that are logically equivalent. For example, an implication can be replaced with its contrapositive.

• Consider the argument:
  • If you send me an email message, then I will finish writing the program.
  • If you do not send me an email message, then I will go to sleep early.
  • If I go to sleep eaerly, then I will wake up feeling refreshed.
  • Therefore, if I do not finish writing the program, I will wake up feeling refreshed.
  We begin by translating this argument into logic. Let $p$ denote "You send me an email message", $q$ denote "I will finish writing the program", $r$ denote "I will go to sleep early" and $s$ denote "I will wake up feeling refreshed." The premises are therefore $p \rightarrow q$, $\neg p \rightarrow r$, $r \rightarrow s$ and the conclusion is $\neg q \rightarrow s$. Apply the following rules of inference. \begin{array}{lll} 1. & p \rightarrow q & \\ 2. & \neg p \rightarrow r & \\ 3. & r \rightarrow s & \therefore \neg q \rightarrow s \\ \hline 4. & \neg q \rightarrow \neg p & \text{Contrapositive (1)} \\ 5. & \neg q \rightarrow r & \text{Hypothetical Syllogism (4,2)} \\ 6. & \neg q \rightarrow s & \text{Hypothetical Syllogism (3,5)} \\ \end{array} Since we were able to derive the conclusion from the premises using the rules of inference, the argument is valid.
• Consider the arugment:
  • Either I study or I fail.
  • I did not study.
  • Therefore, I fail.
  Let $s$ denote "I study" and $f$ denote "I fail". The premises are therefore $s \vee f$ and $\neg s$ and the conclusion is $f$. Apply the following rules of inference. \begin{array}{lll} 1. & s \vee f & \\ 2. & \neg s & \therefore f \\ \hline 4. & f & \text{Disjunctive Syllogism (1,2)} \\ \end{array}

Not all arguments are valid! To show an argument is invalid, find truth values for each proposition that make all of the premises true, but the conclusion false.

This works because proving an argument is valid is just showing that an implication is true. Therefore, to show an argument is invalid, we need to show that the implication is false. An implication is false only when the hypothesis is true and the conclusion is false. Since the hypothesis is the conjunction of the premises, this means that each premise is true and the conclusion is false. $$ \underbrace{(p_1 \wedge p_2 \wedge \cdots \wedge p_n)}_{\text{all $T$}} \rightarrow \underbrace{c}_{F} $$

• Consider the argument:
  • If I did all the suggested exercises, then I got an A+
  • I got an A+
  • Therefore, I did all of the suggested exercises.
  Let $s$ denote "I did all of the suggested excerises" and $a$ denote "I got an A+." The premises are therefore $s \rightarrow a$ and $a$ and the conclusion is $c$. To show this argument is invalid, we find truth values to make all of the premises true, but the conclusion false. If we set $s = F$ and $a = T$, we have $s \rightarrow a \equiv F \rightarrow T \equiv T$ and $a \equiv T$, and so the premises are true. However, the conclusion is $s \equiv F$, and so the argument is invalid.

In the above example, it happens that there is only one truth setting that results in all premises being true and the conclusion being false. In general, there could be many different such truth settings.

Arguments with Quantified Statements

Until now, we have restricted our attention to propositional logic. Recall that $P(x)$ is a propositional function, and so when $x$ is an element of the universe of discourse, we simply have a proposition that can be dealt with using the rules of inference for propositions. For predicate logic, we need a few more rules of inference that will allow us to deal with quantified statements.

• Universal Instantiation: given $\forall x\;{P(x)}$, conclude $P(c)$ for any $c$ in the universe of discourse (if $P$ holds for everything, it must hold for each particular thing)
• Existential Generalization: given $P(c)$ for some $c$ in the universe of discourse, conclude $\exists x\;{P(x)}$ (if I can find an element for which $P$ is true, then there must exist at least one such element)
• Universal Generalization: given $P(c)$ for an arbitrary $c$ in the universe of discourse, conclude $\forall x {P(x)}$ (here, $c$ must be arbitrary; it must hold for any $c$!)
• Existential Instantiation: given $\exists x\;{P(x)}$, conclude $P(c)$ for some $c$ in the universe of discourse (you must pick a new $c$ about which you know nothing else)

Here are some examples of arguments with quantified statements:

• Consider the following argument, where the universe of discourse is the set of all things.:
  • All men are mortal.
  • Socrates is a man.
  • Therefore, Socrates is mortal.
  Let $M(x)$ denote "$x$ is a man", $O(x)$ denote "$x$ is mortal" and $s$ denote Socrates. The premises are therefore $\forall x\;{(M(x) \rightarrow O(x))}$ and $M(s)$ and the conclusion is $O(s)$. Apply the following rules of inference. \begin{array}{lll} 1. & \forall x\;{(M(x) \rightarrow O(x))} & \\ 2. & M(s) & \therefore O(s) \\ \hline 3. & M(s) \rightarrow O(s) & \text{Universal Instantiation (1)} \\ 4. & O(s) & \text{Modus Ponens (2,3)} \\ \end{array} Since we were able to derive the conclusion from the premises using the rules of inference, the argument is valid. Notice that in Step 3, we chose to apply Universal Instantiation and used the object $s$. Of course, we could have used any object in the universe of discourse, but no other object would allow us to reach the desired conclusion.
• Consider the following argument, where the universe of discourse is the set of all people.
  • A student in this class has not read the textbook.
  • Everyone in this class did well on the first assignment.
  • Therefore, someone who did well on the first assignment has not read the textbook.
  Let $C(x)$ denote "$x$ is a student in this class", $B(x)$ denote "$x$ has read the textbook" and $A(x)$ denote "$x$ did well on the first assignment." The premises are therefore $\exists x\;{(C(x) \wedge \neg B(x))}$ and $\forall x\;{(C(x) \rightarrow A(x))}$ and the conclusion is $\exists x\;{(A(x) \wedge \neg B(x))}$. Apply the following rules of inference. \begin{array}{lll} 1. & \exists x\;{(C(x) \wedge \neg B(x))} & \\ 2. & \forall x\;{(C(x) \rightarrow A(x))} & \therefore \exists x\;{(A(x) \wedge \neg B(x))} \\ \hline 3. & C(a) \wedge \neg B(a) & \text{Existential Instantiation (1)} \\ 4. & C(a) & \text{Simplification (3)} \\ 5. & C(a) \rightarrow A(a) & \text{Universal Instantiation (2)} \\ 6. & A(a) & \text{Modus Ponens (4,5)} \\ 7. & \neg B(a) & \text{Simplification (3)} \\ 8. & A(a) \wedge \neg B(a) & \text{Conjunction (6,7)} \\ 9. & \exists x\;{(A(x) \wedge \neg B(x))} & \text{Existential Generalization (8)} \\ \end{array} Since we were able to derive the conclusion from the premises using the rules of inference, the argument is valid. Notice that in Step 3, we chose to apply Existential Instantiation and used the object $a$. This is valid because we have not seen $a$ before and therefore know nothing else about it. We later apply Universal Instantiation using $a$, but this is valid because this rule can be applied using any object. Note that applying these rules in the opposite order would not have been valid, since we would have already seen $a$ when applying Existential Instantiation.
• Consider the following argument, where the universe of discourse is the set of people.
  • All human beings are from Earth.
  • Every person is a human being.
  • Therefore, every person is from Earth
  Let $H(x)$ denote "$x$ is a human being" and $E(x)$ denote "$x$ is from Earth." The premises are therefore $\forall x\;{(H(x) \rightarrow E(x))}$ and $\forall x\;{H(x)}$ and the conclusion is $\forall x \;{E(x)}$. Apply the following rules of inference. \begin{array}{lll} 1. & \forall x\;{(H(x) \rightarrow E(x))} & \\ 2. & \forall x\;{H(x)} & \therefore \forall x\;{E(x)} \\ \hline 3. & H(c) \rightarrow E(c) & \text{Universal Instantiation (1)} \\ 4. & H(c) & \text{Universal Instantiation (2)} \\ 5. & E(c) & \text{Modus Ponens (3,4)} \\ 6. & \forall x\;{E(x)} & \text{Universal Generalization (5)} \\ \end{array} Since we were able to derive the conclusion from the premises using the rules of inference, the argument is valid. Notice that in Step 6, we chose to apply Universal Generalization and used the object $c$. This is valid because we could have performed the instantiations in Steps 3 and 4 with any object, and so $c$ could be any object in the universe of discourse.

The next example will help to illustrate when Universal Generalization may not be applied.

• Consider the following argument, where the universe of discourse is the set of people.
  • If John knows discrete mathematics, he will pass this course.
  • John knows discrete mathematics.
  • Therefore, everyone will pass this course
  Let $D(x)$ denote "$x$ knows discrete mathematics", $P(x)$ denote "$x$ will pass this course" and $j$ denote John. The premises are therefore $D(j) \rightarrow P(j)$ and $D(j)$ and the conclusion is $\forall x\;{P(x)}$. One might be tempted to apply the following rules of inference. \begin{array}{lll} 1. & D(j) \rightarrow P(j) & \\ 2. & D(j) & \therefore \forall x\;{P(x)} \\ \hline 3. & P(j) & \text{Modus Ponens} (1,2) \\ 4. & \forall x\;{P(x)} & \text{Universal Generalization (3)} \\ \end{array} The Universal Generalization applied in Step 4 is not valid since $j$ represents only John and not necessarily any object in the universe of discourse. By itself, this does not show that the argument is invalid, however, since this simply may not be the correct way to prove it. To show the argument is invalid, we need to assign truth values such that the premises are true but the conclusion is false. Set $D(j) = T$, $P(j) = T$ so that the premises are true, but set $P(a) = F$ for some person $a$ to make the conclusion false. Therefore, the argument is invalid.