Law of Syllogism

This law can be proven by making a truth table. The goal is to see that the compound statement is always true.

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

The proof consists of three steps.

Determine the Number of Columns

To determine the number of columns in the truth table, the compound statement can be broken down into simpler statements until the simplest statements $p,$ $q,$ and $r$ are obtained.

The compound statement is broken down into simpler statements

The columns are formed by ordering each unique step of simplification from the simplest to the most complex. The last column of a truth table is always the original statement.

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

In this case, the truth table has eight columns.

Determine the Number of Rows

A truth table has as many rows as there are combinations of truth values of the variables. In this case, there are three simplest statements,

p,

q,

and

r .

\underline{Simplest Statements} p, q, and r

Each of these statements can be either true (T) or false (F). There are eight possible combinations for these truth values, so the table will have eight rows.

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	$?$	$?$	$?$	$?$	$?$
T	T	F	$?$	$?$	$?$	$?$	$?$
T	F	T	$?$	$?$	$?$	$?$	$?$
T	F	F	$?$	$?$	$?$	$?$	$?$
F	T	T	$?$	$?$	$?$	$?$	$?$
F	T	F	$?$	$?$	$?$	$?$	$?$
F	F	T	$?$	$?$	$?$	$?$	$?$
F	F	F	$?$	$?$	$?$	$?$	$?$

Fill in the Cells

The last step in making a truth table is to fill in the remaining empty cells, column by column. The first columns that will be filled in are the conditional statements $p \to q,$ $q \to r,$ and $p \to r .$ A conditional statement is false only when the hypothesis is $true$ and the conclusion $false .$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
$T$	$T$	$T$	$T$	$T$	$T$	$?$	$?$
$T$	$T$	$F$	$T$	$F$	$F$	$?$	$?$
$T$	$F$	$T$	$F$	$T$	$T$	$?$	$?$
$T$	$F$	$F$	$F$	$F$	$F$	$?$	$?$
$F$	$T$	$T$	$T$	$T$	$T$	$?$	$?$
$F$	$T$	$F$	$T$	$F$	$T$	$?$	$?$
$F$	$F$	$T$	$T$	$T$	$T$	$?$	$?$
$F$	$F$	$F$	$T$	$T$	$T$	$?$	$?$

The column containing the conjunction $(p \to q) \land (p \to r)$ is next to fill. A conjunction is $false$ unless both statements are $true .$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	$T$	$T$	T	$T$	$?$
T	T	F	$T$	$F$	F	$F$	$?$
T	F	T	$F$	$T$	T	$F$	$?$
T	F	F	$F$	$F$	F	$F$	$?$
F	T	T	$T$	$T$	T	$T$	$?$
F	T	F	$T$	$F$	T	$F$	$?$
F	F	T	$T$	$T$	T	$T$	$?$
F	F	F	$T$	$T$	T	$T$	$?$

The last column is another conditional statement, which is only false only when the hypothesis is true and the conclusion false.

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	T	T	$T$	$T$	$T$
T	T	F	T	F	$F$	$F$	$T$
T	F	T	F	T	$T$	$F$	$T$
T	F	F	F	F	$F$	$F$	$T$
F	T	T	T	T	$T$	$T$	$T$
F	T	F	T	F	$T$	$F$	$T$
F	F	T	T	T	$T$	$T$	$T$
F	F	F	T	T	$T$	$T$	$T$

As the truth table describes, the compound statement is always

true .

Therefore, the law is proven.

{{ article.displayTitle }}

Law of Syllogism

Proof

Extra

	{{ 'ml-lesson-number-slides' \| message : article.intro.bblockCount }}
	{{ 'ml-lesson-number-exercises' \| message : article.intro.exerciseCount }}
	{{ 'ml-lesson-time-estimation' \| message }}

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	$?$	$?$	$?$	$?$	$?$
T	T	F	$?$	$?$	$?$	$?$	$?$
T	F	T	$?$	$?$	$?$	$?$	$?$
T	F	F	$?$	$?$	$?$	$?$	$?$
F	T	T	$?$	$?$	$?$	$?$	$?$
F	T	F	$?$	$?$	$?$	$?$	$?$
F	F	T	$?$	$?$	$?$	$?$	$?$
F	F	F	$?$	$?$	$?$	$?$	$?$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
$T$	$T$	$T$	$T$	$T$	$T$	$?$	$?$
$T$	$T$	$F$	$T$	$F$	$F$	$?$	$?$
$T$	$F$	$T$	$F$	$T$	$T$	$?$	$?$
$T$	$F$	$F$	$F$	$F$	$F$	$?$	$?$
$F$	$T$	$T$	$T$	$T$	$T$	$?$	$?$
$F$	$T$	$F$	$T$	$F$	$T$	$?$	$?$
$F$	$F$	$T$	$T$	$T$	$T$	$?$	$?$
$F$	$F$	$F$	$T$	$T$	$T$	$?$	$?$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	$T$	$T$	T	$T$	$?$
T	T	F	$T$	$F$	F	$F$	$?$
T	F	T	$F$	$T$	T	$F$	$?$
T	F	F	$F$	$F$	F	$F$	$?$
F	T	T	$T$	$T$	T	$T$	$?$
F	T	F	$T$	$F$	T	$F$	$?$
F	F	T	$T$	$T$	T	$T$	$?$
F	F	F	$T$	$T$	T	$T$	$?$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	T	T	$T$	$T$	$T$
T	T	F	T	F	$F$	$F$	$T$
T	F	T	F	T	$T$	$F$	$T$
T	F	F	F	F	$F$	$F$	$T$
F	T	T	T	T	$T$	$T$	$T$
F	T	F	T	F	$T$	$F$	$T$
F	F	T	T	T	$T$	$T$	$T$
F	F	F	T	T	$T$	$T$	$T$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	$?$	$?$	$?$	$?$	$?$
T	T	F	$?$	$?$	$?$	$?$	$?$
T	F	T	$?$	$?$	$?$	$?$	$?$
T	F	F	$?$	$?$	$?$	$?$	$?$
F	T	T	$?$	$?$	$?$	$?$	$?$
F	T	F	$?$	$?$	$?$	$?$	$?$
F	F	T	$?$	$?$	$?$	$?$	$?$
F	F	F	$?$	$?$	$?$	$?$	$?$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
$T$	$T$	$T$	$T$	$T$	$T$	$?$	$?$
$T$	$T$	$F$	$T$	$F$	$F$	$?$	$?$
$T$	$F$	$T$	$F$	$T$	$T$	$?$	$?$
$T$	$F$	$F$	$F$	$F$	$F$	$?$	$?$
$F$	$T$	$T$	$T$	$T$	$T$	$?$	$?$
$F$	$T$	$F$	$T$	$F$	$T$	$?$	$?$
$F$	$F$	$T$	$T$	$T$	$T$	$?$	$?$
$F$	$F$	$F$	$T$	$T$	$T$	$?$	$?$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	$T$	$T$	T	$T$	$?$
T	T	F	$T$	$F$	F	$F$	$?$
T	F	T	$F$	$T$	T	$F$	$?$
T	F	F	$F$	$F$	F	$F$	$?$
F	T	T	$T$	$T$	T	$T$	$?$
F	T	F	$T$	$F$	T	$F$	$?$
F	F	T	$T$	$T$	T	$T$	$?$
F	F	F	$T$	$T$	T	$T$	$?$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	T	T	$T$	$T$	$T$
T	T	F	T	F	$F$	$F$	$T$
T	F	T	F	T	$T$	$F$	$T$
T	F	F	F	F	$F$	$F$	$T$
F	T	T	T	T	$T$	$T$	$T$
F	T	F	T	F	$T$	$F$	$T$
F	F	T	T	T	$T$	$T$	$T$
F	F	F	T	T	$T$	$T$	$T$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	$?$	$?$	$?$	$?$	$?$
T	T	F	$?$	$?$	$?$	$?$	$?$
T	F	T	$?$	$?$	$?$	$?$	$?$
T	F	F	$?$	$?$	$?$	$?$	$?$
F	T	T	$?$	$?$	$?$	$?$	$?$
F	T	F	$?$	$?$	$?$	$?$	$?$
F	F	T	$?$	$?$	$?$	$?$	$?$
F	F	F	$?$	$?$	$?$	$?$	$?$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
$T$	$T$	$T$	$T$	$T$	$T$	$?$	$?$
$T$	$T$	$F$	$T$	$F$	$F$	$?$	$?$
$T$	$F$	$T$	$F$	$T$	$T$	$?$	$?$
$T$	$F$	$F$	$F$	$F$	$F$	$?$	$?$
$F$	$T$	$T$	$T$	$T$	$T$	$?$	$?$
$F$	$T$	$F$	$T$	$F$	$T$	$?$	$?$
$F$	$F$	$T$	$T$	$T$	$T$	$?$	$?$
$F$	$F$	$F$	$T$	$T$	$T$	$?$	$?$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	$T$	$T$	T	$T$	$?$
T	T	F	$T$	$F$	F	$F$	$?$
T	F	T	$F$	$T$	T	$F$	$?$
T	F	F	$F$	$F$	F	$F$	$?$
F	T	T	$T$	$T$	T	$T$	$?$
F	T	F	$T$	$F$	T	$F$	$?$
F	F	T	$T$	$T$	T	$T$	$?$
F	F	F	$T$	$T$	T	$T$	$?$

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$	$(p \to q) \land (q \to r)$	$[(p \to q) \land (q \to r)] \to (p \to r)$
T	T	T	T	T	$T$	$T$	$T$
T	T	F	T	F	$F$	$F$	$T$
T	F	T	F	T	$T$	$F$	$T$
T	F	F	F	F	$F$	$F$	$T$
F	T	T	T	T	$T$	$T$	$T$
F	T	F	T	F	$T$	$F$	$T$
F	F	T	T	T	$T$	$T$	$T$
F	F	F	T	T	$T$	$T$	$T$