Valid Arguments and Logical Implication

Having tested tautologies, contradictions, and valid arguments by final truth-table columns, the next step is to express argument validity as logical implication. Valid arguments and logical implication give a precise way to say that a conclusion is forced by given premises. In ordinary reasoning, students often accept a conclusion because it sounds plausible; in mathematical logic, plausibility is not enough. In this lesson, valid arguments and logical implication will be studied through implication forms, truth conditions, and short formal deductions.

Let

p_1,p_2,p_3,\ldots,p_n

and

q

be statements. In an argument of the form

\begin{equation*} p_1,\ p_2,\ p_3,\ldots,p_n\ \therefore\ q, \end{equation*}

the statements

p_1,p_2,p_3,\ldots,p_n

are called the \textbf{premises}, and the statement

q

is called the \textbf{conclusion}.

Let

p_1,p_2,p_3,\ldots,p_n

and

q

be statements. In an argument of the form

\begin{equation*} p_1,\ p_2,\ p_3,\ldots,p_n\ \therefore\ q, \end{equation*}

the statements

p_1,p_2,p_3,\ldots,p_n

are called the \textbf{premises}, and the statement

q

is called the \textbf{conclusion}.

Let

p_1,p_2,\ldots,p_n

be premises and let

q

be a conclusion. The \textbf{implication form} corresponding to the argument

\begin{equation*} p_1,\ p_2,\ldots,p_n\ \therefore\ q \end{equation*}

is the conditional statement

\begin{equation*} (p_1\land p_2\land\cdots\land p_n)\to q. \end{equation*}

Let

p_1,p_2,\ldots,p_n

be premises and let

q

be a conclusion. The argument

\begin{equation*} p_1,\ p_2,\ldots,p_n\ \therefore\ q \end{equation*}

is called a \textbf{valid argument} if whenever all the premises are true, the conclusion is also true. Equivalently, the argument is valid if

\begin{equation*} (p_1\land p_2\land\cdots\land p_n)\to q \end{equation*}

is a tautology.

A valid argument does not require that the premises are actually true in the real world. It requires that no truth-value assignment makes all premises true while making the conclusion false. Thus, to disprove validity, one searches for a row where every premise has value

1

and the conclusion has value

0

. To prove validity, one may show directly that such a row cannot occur. This is why valid arguments and logical implication are closely connected.

A valid argument fails only if one row makes every premise true while the conclusion is false. Use the controls to choose truth values for the statements in the Roger studies argument. The display evaluates each premise and the conclusion for that single row. Notice that a row with a false premise does not disprove validity, but a row with all true premises and a false conclusion would be a counterexample.

Let

p

mean “Roger studies,”

q

mean “Roger plays tennis,” and

r

mean “Roger passes discrete mathematics.” Consider the argument

\begin{equation*} p\to r,\ \neg q\to p,\ \neg r\ \therefore\ q. \end{equation*}

The corresponding implication form is

\begin{equation*} [(p\to r)\land(\neg q\to p)\land\neg r]\to q. \end{equation*}

Assume that all premises are true. Since

\neg r

is true,

r

is false. Since

p\to r

is true and

r

is false,

p

must be false. Since

\neg q\to p

is true and

p

is false,

\neg q

must be false. Therefore

q

is true. Hence, the argument is valid.

Let

p

and

q

be statements. If

p\to q

is a tautology, then

p

is said to \textbf{logically imply}

q

. This is denoted by

\begin{equation*} p\Rightarrow q. \end{equation*}

Thus

p\Rightarrow q

means that whenever

p

is true,

q

must also be true.

Let

p

and

q

be statements. The statement

p

does not logically imply

q

, written

\begin{equation*} p\not\Rightarrow q, \end{equation*}

p\to q

is not a tautology. Equivalently, there exists at least one truth-value assignment for which

p

is true and

q

is false.

Let

p

and

q

be statements. Then

p

and

q

are logically equivalent if and only if

p

logically implies

q

and

q

logically implies

p

. That is,

\begin{equation*} p\Leftrightarrow q \quad\text{if and only if}\quad (p\Rightarrow q)\ \text{and}\ (q\Rightarrow p). \end{equation*}

Given that

p

and

q

are statements. To prove that

p\Leftrightarrow q

if and only if

(p\Rightarrow q)

and

(q\Rightarrow p)

. [1] Suppose

p\Leftrightarrow q

. Then

p

and

q

have the same truth value for every truth-value assignment. Therefore, whenever

p

is true,

q

is true, so

p\Rightarrow q

. Also, whenever

q

is true,

p

is true, so

q\Rightarrow p

. Hence,

(p\Rightarrow q)

and

(q\Rightarrow p)

. [2] Conversely, suppose

p\Rightarrow q

and

q\Rightarrow p

. Then whenever

p

is true,

q

is true, and whenever

q

is true,

p

is true. Therefore

p

and

q

have the same truth value under every truth-value assignment. Hence

p\Leftrightarrow q

if and only if

(p\Rightarrow q)

and

(q\Rightarrow p)

\square

For any statements

p

and

q

\begin{equation*} p\Rightarrow (p\lor q). \end{equation*}

Given that

p

is true. To prove that

p\lor q

is true. Since a disjunction is true when at least one component is true,

p\lor q

is true regardless of the truth value of

q

. Therefore

p\to(p\lor q)

is a tautology. Hence

p\Rightarrow(p\lor q)

For any statements

p

and

q

\begin{equation*} \neg(p\land q)\Rightarrow(\neg p\lor\neg q) \end{equation*}

and

\begin{equation*} (\neg p\lor\neg q)\Rightarrow\neg(p\land q). \end{equation*}

Therefore,

\begin{equation*} \neg(p\land q)\Leftrightarrow(\neg p\lor\neg q). \end{equation*}

This shows that De Morgan’s law may be expressed through two opposite logical implications.

Verify that

[p\land((p\land r)\to s)]\to(r\to s)

is a tautology.

Let

p

and

(p\land r)\to s

be true. To prove that

r\to s

is true, assume that

r

is true. Since

p

is true and

r

is true,

p\land r

is true. Since

(p\land r)\to s

is true and

p\land r

is true,

s

is true. Therefore, whenever

r

is true,

s

is true. Hence

r\to s

is true, and the given implication is a tautology.

Verify that

[(p\to q)\land(q\to r)]\to(p\to r)

is a logical implication.

Let

p\to q

and

q\to r

be true. To prove that

p\to r

is true, assume that

p

is true. Since

p\to q

is true and

p

is true,

q

is true. Since

q\to r

is true and

q

is true,

r

is true. Therefore, whenever

p

is true,

r

is true. Hence

p\to r

is true, and the given implication is a tautology.

Truth tables can always be used to test valid arguments and logical implication. However, if an argument contains

n

primitive statements, then its truth table contains

2^n

rows. For arguments with many primitive statements, a truth table becomes lengthy. This motivates the use of rules of inference, which prove validity without listing every truth-value assignment.

Establish the validity of each argument by means of a truth table: (1)

[p\land(p\to q)\land r]\to[(p\lor q)\to r]

. (2)

[((p\land q)\to r)\land\neg q\land(p\to\neg r)]\to(\neg p\lor\neg q)

. (3)

[[p\lor(q\lor r)]\land\neg q]\to(p\lor r)

Each statement is tested by constructing a full truth table and checking whether the final conditional column contains only

1

's. In each case, if no row has true premises and false conclusion, the argument is valid.

Use truth tables to verify the following logical implications: (1)

[(p\to q)\land(q\to r)]\to(p\to r)

. (2)

[(p\to q)\land\neg q]\to\neg p

. (3)

[(p\lor q)\land\neg p]\to q

. (4)

[(p\to r)\land(q\to r)]\to[(p\lor q)\to r]

The four implications correspond respectively to the Law of the Syllogism, Modus Tollens, Disjunctive Syllogism, and Proof by Cases. Each is a tautology.

No. Validity says that if all premises are true, then the conclusion must be true.

One truth-value assignment with all premises true and the conclusion false makes the argument invalid.

Logical implication means the corresponding conditional is a tautology, not merely true in one assignment.

BMLabs Mathematics

BMLabs Mathematics

Valid Arguments and Logical Implication

Valid Arguments and Logical Implication

FROM TRUTH TABLES TO LOGICAL CONSEQUENCE

PREMISES AND CONCLUSION

IMPLICATION FORM OF AN ARGUMENT

VALID ARGUMENT

HOW VALIDITY IS TESTED

EXPLORING VALIDITY ROW BY ROW

VALIDITY ROW EXPLORER

ROGER STUDIES ARGUMENT

LOGICAL IMPLICATION

FAILURE OF LOGICAL IMPLICATION

LOGICAL EQUIVALENCE BY MUTUAL LOGICAL IMPLICATION

LOGICAL IMPLICATION FROM DISJUNCTION

DE MORGAN IMPLICATIONS

FREQUENTLY ASKED QUESTIONS

PRACTISE LOGICAL CONSEQUENCE

Introduction To Discrete Mathematics

Paths and Circuits