Using the Rules of Inference

The Book of
Foundational Mathematics

Detailed Contents

Propositional Logic

Arguments and Proof

Verifying Mathematical Arguments in Maple

Set Theory

Set Theory in Maple

Using the Rules of Inference

In the previous section, we collected a large sample of commonly occurring logical implications. We briefly touched on why we would want such a list, but just to reiterate, what we’re trying to do is determine if a given argument is valid. In addition to trying to determine if an argument is valid, we can use the rules of inference to make valid deductions based on a given list of premises.

In this section, we work through multiple examples of both use cases for the rules of inference.

Determining an Argument’s Validity

Suppose we are presented with some argument. We have a list of premises, and a desired conclusion. We can determine if the argument is valid by appealing to the rules of inference.

Example 2.3.1

Because AC/DC is the greatest band ever, you decide to purchase front row tickets for their upcoming concert. The tickets are really expensive, so you’ll need to save up money working a summer job in order to purchase the tickets. The problem is that everybody wants front row seats, so they may be sold out by the time you you have enough money.

Consider the following propositions:

a:	You save up enough money to purchase front row seats.
b:	There are no more front row seats available.
c:	You sit front row at the AC/DC concert.

Now consider the following argument:

	¬b
	¬b → a
	a → c
∴	c

To determine if the above argument is valid, note that because we have both ¬b and (¬b → a), we must have a by Modus Ponens.

Now, because we have both a and (a → c), we also have c by Modus Ponens.

We just reached the desired conclusion c by appealing to Modus Ponens twice, meaning the above argument was valid. Thus, if there are front row seats available, you’ll be able to save up enough money to sit front row at the AC/DC concert. Awesome!

In Example 2.3.1, we showed how we can verify that a given argument is valid simply by appealing to the rules of inference. However, it seems a bit cumbersome to write out all of our logic in paragraphs. Just like we did when showing that two compound propositions were logically equivalent, we can write out a sequence of steps in a tabular form.

Example 2.3.2

Luckily for us, AC/DC are performing another concert, which means we need to start saving even more money, and hoping that front row seats are still available.

Reconsider the argument presented in Example 2.3.1:

	¬b
	¬b → a
	a → c
∴	c

We can write out the sequence of steps we took in Example 2.3.1 in a tabular form:

Step	Proposition	Reason
(1)	¬b	Premise
(2)	¬b → a	Premise
(3)	a	Modus Ponens on Steps (1) and (2)
(4)	a → c	Premise
(5)	∴ c	Modus Ponens on Steps (3) and (4)

Just like before, we reached conclusion c using the rules of inference.

We will use the tabular form of validating an argument henceforth.

There are many rules of inference, so we may be able to validate a given argument in multiple different ways.

Example 2.3.3

Let’s reconsider the argument from Example 2.3.2:

	¬b
	¬b → a
	a → c
∴	c

Instead of using Modus Ponens twice, we could possibly take another look at the big list of inference rules from the previous section. One such rule that stands out is the Law of the Syllogism because we have two implications as premises. Let’s try and use that rule of inference:

Step	Proposition	Reason
(1)	¬b → a	Premise
(2)	a → c	Premise
(3)	¬b → c	Law of the Syllogism on Steps (1) and (2)
(4)	¬b	Premise
(5)	∴ c	Modus Ponens on Steps (3) and (4)

Of course, we arrive yet again at the desired conclusion of c.

Just for clarity, when we write out these tabular forms in the future, we will omit the word “Steps”, and just write out which numbered step is being used in a rule of inference. This will save us a bit of writing.

Also worth pointing out is that since some propositions are given as premises of the argument, they require no justification, perhaps other than to simply mention that they are in fact premises of the argument.

Some arguments require multiple rules of inference to determine if they’re valid.

Example 2.3.4

Let’s consider the following argument with propositions s, t, x, y, and z:

	x
	x → y
	s ∨ t
	t → ¬y
∴	s ∨ z

Here, propositions s, t, x, y, and z are arbitrary propositions. We could take the following steps in out attempt to validate this argument:

Step	Proposition	Reason
(1)	x	Premise
(2)	x → y	Premise
(3)	y	Modus Ponens on (1) and (2)
(4)	t → ¬y	Premise
(5)	y → ¬t	Contrapositive of (4) [(t → ¬y) ⟺ (y → ¬t)]
(6)	¬t	Modus Ponens on (3) and (5)
(7)	s ∨ t	Premise
(8)	s	Rule of Disjunctive Syllogism on (6) and (7)
(9)	∴ s ∨ z	Rule of Disjunctive Amplification on (8)

So, we arrive at the desired conclusion of (s ∨ z), using a wide variety of rules for inference.

In Example 2.3.4, one of the steps listed (specifically, step 5) made use of a logical equivalency between contrapositives. As we work through an argument, we can introduce logically equivalent propositions whenever we want. As such, we should make use of this ability as much as possible.

Example 2.3.5

For arbitrary propositions a, b, c, d, e, and, f, consider the following argument:

	a → e
	e → (b ∧ c)
	¬c ∨ (f ∨ ¬d)
	d ∧ a
∴	f

This one may require a lot of work, so let’s get started:

Step	Proposition	Reason
(1)	a → e	Premise
(2)	e → (b ∧ c)	Premise
(3)	a → (b ∧ c)	Law of the Syllogism on (1) and (2)
(4)	d ∧ a	Premise
(5)	a	Conjunctive Simplification on (4)
(6)	b ∧ c	Modus Ponens on (3) and (5)
(7)	c	Conjunctive Simplification on (6)
(8)	¬c ∨ (f ∨ ¬d)	Premise
(9)	f ∨ ¬d	Disjunctive Syllogism on (7) and (8)
(10)	d	Conjunctive Simplification on (4)
(11)	∴f	Disjunctive Syllogism on (9) and (10)

Making Valid Inferences

When determining if an argument is valid, we were given a list of premises, and a conclusion. When checking for validity, we wrote out our justifications in a tabular form with the conclusion being the last entry in the table. There were many intermediate steps.

Theoretically, we could do the same thing even if we were not given a conclusion. It’s just that if we are not given a conclusion, then we don’t have a “goal” to reach. We could just apply whatever rule of inference seems appropriate on the given premises, and any previous conclusions reached based on those premises.

Let’s look at an example.

Example 2.3.6

Consider the following propositions:

c:	“I am clever.”
ℓ:	“I am lucky.”
w:	“I win the lottery.”

Now consider the following premises:

c ∨ ℓ
¬ℓ
ℓ → w

We are not given a conclusion, but can we make any inference or deduction from these premises?

One conclusion we could reach easily is to use the Rule of Disjunctive Syllogism on the first two premises listed, giving us conclusion c.

As such, we know that the argument

[(c ∨ ℓ) ∧ (¬ℓ) ∧ (ℓ → w)] → c

is valid.

Note that once you use a rule of inference on a given list of premises, you are making a valid argument. Reconsider Example 2.3.5. Every single intermediate step produced a valid argument because they were constructed by means of a rule of inference.

Example 2.3.7

Consider the collection list of premises:

If AC/DC can not perform their concert, or their t-shirts are not available for purchase at the concert, then the after-party will be cancelled, and you will not purchase front row seats. If the after-party is cancelled, then ticket sales will have to be issued refunds. No refunds were issued.

We start by picking out the propositions:

a:	“AC/DC can perform their concert.”
t:	“AC/DC’s t-shirts are available for purchase.”
p:	“The after-party was cancelled.”
y:	“You do not buy front row seats.”
r:	“Ticket sales are issued refunds.”

We thus have the following premises:

(¬a ∨ ¬t) → (p ∧ y)
p → r
¬r

So, what deductions can we make? Let’s set up a table to help us organize our thinking.

Step	Proposition	Reason
(1)	p → r	Premise
(2)	¬r	Premise
(3)	¬p	Modus Tollens on (1) and (2)
(4)	¬p ∨ ¬y	Disjunctive Amplification on (3)
(5)	¬(p ∧ y)	DeMorgan’s Law on (4)
(6)	(¬a ∨ ¬t) → (p ∧ y)	Premise
(7)	¬(¬a ∨ ¬t)	Modus Tollens on (5) and (6)
(8)	¬¬a ∧ ¬¬t	DeMorgan’s Law on (7)
(9)	a ∧ ¬¬t	Law of Double Negation on (8)
(10)	a	Conjunctive Simplification on (9)
(11)	a ∧ t	Law of Double Negation on (9)
(12)	t	Conjunctive Simplification on (11)

Notice that one of the conclusions we came up with was a in step (10). As such, we know that

[((¬a ∨ ¬t) → (p ∧ y)) ∧ (p → r) ∧ (¬r)] → (a)

is a valid argument. As such, with the given premises, we could deduce that AC/DC performed their concert!

However, we did not stop at that one conclusion. Step (12) left us with conclusion t. This means that the argument

[((¬a ∨ ¬t) → (p ∧ y)) ∧ (p → r) ∧ (¬r)] → (t)

is also valid. As such, we could also deduce that, with the given premises, that AC/DC’s t-shirts were available for purchase at their concert!

Yet another inference we made was ¬p, meaning the after-party was not cancelled!

Of course, any of the intermediate propositions that were not premises are valid inferences with the given premises.

One more strategy we could use is to use a truth table to see what combinations of truth values for the propositions yield true premises.

Example 2.3.8

Consider the following propositions:

s:	“Johnny had to go to summer school.”
j:	“Johnny could work a summer job.”
a:	“Johnny could purchase front-row seats at the AC/DC concert.”

Now consider the following premises:

s
s → ¬j
¬j → ¬a

Let’s see what happens when we construct a truth table. We’ll highlight any rows where all premises are true.

					p₂	p₃	p₁ ∧ p₂ ∧ p₃
s	j	a	¬j	¬a	s → ¬j	¬j → ¬a	s ∧ (s → ¬j) ∧ (¬j → ¬a)
0	0	0	1	1	1	1	0
0	0	1	1	0	1	0	0
0	1	0	0	1	1	1	0
0	1	1	0	0	1	1	0
1	0	0	1	1	1	1	1
1	0	1	1	0	1	0	0
1	1	0	0	1	0	1	0
1	1	1	0	0	0	1	0

So, the only combinations of truth values that yield all true premises are the following:

s = 1
j = 0
a = 0

So, we need some combination of these three propositions that yield a truth value of 1. One such example is ¬j, meaning

[s ∧ (s → ¬j) ∧ (¬j → ¬a)] → (¬j)

is a valid argument. We also have that ¬a = 1, meaning

[s ∧ (s → ¬j) ∧ (¬j → ¬a)] → (¬a)

is also a valid argument.

Note that since j = 0 and ¬a = 1, we have that (j ∧ ¬a) = 0, meaning

¬(j ∧ ¬a) = 1,

and so we have that

¬j ∨ a = 1

as well. As such, the argument

[s ∧ (s → ¬j) ∧ (¬j → ¬a)] → (¬j ∨ a)

is also valid.

It’s good practice to try and come up with a sequence of inference rules you can use to reach these conclusions without going through a truth table.

The Book ofFoundational Mathematics

Using the Rules of Inference

Determining an Argument’s Validity

Example 2.3.1

Example 2.3.2

Example 2.3.3

Example 2.3.4

Example 2.3.5

Making Valid Inferences

Example 2.3.6

Example 2.3.7

Example 2.3.8

The Book of
Foundational Mathematics