Introduction: Proofs in mathematics are valid arguments that establish the truth of mathematical statements. By an argument, we mean a sequence of statements that end with a conclusion. By valid, we mean that the conclusion, or final statement of the argument, must follow from the truth of the preceding statements, or premises, of the argument. That is, an argument is valid if and only if it is impossible for all the premises to be true and the conclusion to be false. To deduce new statements from statements we already have, we use rules of inference which are templates for constructing valid arguments. Rules of inference are our basic tools for establishing the truth of statements.
Valid Arguments in Propositional Logic: Consider the following argument involving propositions (which, by definition, is a sequence of propositions):
“If you have a current password, then you can log onto the network.”
“You have a current password.”
Therefore,
“You can log onto the network.”
We would like to determine whether this is a valid argument. That is, we would like to determine whether the conclusion “You can log onto the network” must be true when the premises “If you have a current password, then you can log onto the network” and “You have a current password” are both true.
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.)
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 involving propositional variables. An argument form is valid no matter which particular propositions 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 p1, p2, . . . , pn and conclusion q is valid, when (p1 ∧ p2 ∧ · · · ∧ pn) → 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.
