Page 91 - Discrete Mathematics and Its Applications

70 1 / The Foundations: Logic and Proofs

Before we discuss the validity of this particular argument, we will look at its form. Use p
to represent “You have a current password” and q to represent “You can log onto the network.”
Then, the argument has the form

p → q
p
∴ q

where ∴ is the symbol that denotes “therefore.”
We know that when p and q are propositional variables, the statement ((p → q) ∧ p) → q
is a tautology (see Exercise 10(c) in Section 1.3). In particular, when both p → q and p are
true, we know that q must also be true. We say this form of argument is valid because whenever
all its premises (all statements in the argument other than the final one, the conclusion) are true,
the conclusion must also be true. Now suppose that both “If you have a current password, then
you can log onto the network” and “You have a current password” are true statements. When
we replace p by “You have a current password” and q by “You can log onto the network,” it
necessarily follows that the conclusion “You can log onto the network” is true. This argument
is valid because its form is valid. Note that whenever we replace p and q by propositions where
p → q and p are both true, then q must also be true.
What happens when we replace p and q in this argument form by propositions where not
both p and p → q are true? For example, suppose that p represents “You have access to the
network” and q represents “You can change your grade” and that p is true, but p → q is false.
The argument we obtain by substituting these values of p and q into the argument form is

“If you have access to the network, then you can change your grade.”
“You have access to the network.”
∴ “You can change your grade.”

The argument we obtained is a valid argument, but because one of the premises, namely the first
premise, is false, we cannot conclude that the conclusion is true. (Most likely, this conclusion
is false.)
In our discussion, to analyze an argument, we replaced propositions by propositional vari-
ables. This changed an argument to an argument form. We saw that the validity of an argument
follows from the validity of the form of the argument. We summarize the terminology used to
discuss the validity of arguments with our definition of the key notions.

DEFINITION 1 An argument in propositional logic is a sequence of propositions.All but the final proposition
in the argument are called premises and the final proposition is called the conclusion.An
argument is valid if the truth of all its premises implies that the conclusion is true.
An argument form in propositional logic is a sequence of compound propositions involv-
ing propositional variables. An argument form is valid no matter which particular proposi-
tions are substituted for the propositional variables in its premises, the conclusion is true if
the premises are all true.

From the definition of a valid argument form we see that the argument form with premises
p 1 , p 2 ,...,p n and conclusion q is valid, when (p 1 ∧ p 2 ∧ ··· ∧ p n ) → q is a tautology.
The key to showing that an argument in propositional logic is valid is to show that its
argument form is valid. Consequently, we would like techniques to show that argument forms
are valid. We will now develop methods for accomplishing this task.