Introducing Rules of Inference

This is a work-in-progress. I will be updating this often!

It’s my sincere hope that my website will be useful to you. Logic is a wonderful “science” to learn and, of course, to practice and apply.

Please take a look at my tutorial. It will give you the tools to master logic.
If you profit from it or enjoy it, please consider supporting my work.

— George Wick

The Amateur Logician Tutorial:
Symbols & Translations | Basic Truth Tables | Complicated Translations | Introducing Rules of Inference | Equivalences (Replacement Rules) | Conditional & Indirect Proofs

Introduction: Syntax and Semantics

Basic Inferences in Propositional Logic
– Modus Ponens (MP)
– Modus Tollens (MT)
– Hypothetical Syllogism (HP)
– Disjunctive Syllogism (DS)
– Constructive Dilemma (CD)
– Simplification (SIM)
– Conjunction (CON)
– Addition (ADD)

Differing Terminology

Additional Inference Rules in Propositional Logic
– Destructive Dilemma (DD)
– Resolution (RES)

Tautological Implications

Simple Deductive Proofs with Rules of Inference
No Truth Tables Necessary! 🙂

Introduction: Syntax and Semantics

Logic is about argumentation. Arguments consist of moves from a set of given propositions — i.e., premises — to newly derived propositions — i.e., conclusions. It’s through inference that we can derive new propositions. When we follow the rules of inference, our conclusions validly “follow from” the premises.

Note that a valid argument need not have a true conclusion! Only insofar as a valid argument contains true premises are we guaranteed a true conclusion — and only then.

Basic rules of inference in propositional logic include modus ponens (MP), modus tollens (MT), hypothetical syllogism (HS), disjunction syllogism (DS), constructive dilemma (CD), simplification (SIM), conjunction (CON), and addition (ADD).

When thinking about the rules of inference, we can take two different viewpoints.

A syntactical viewpoint thinks about propositional logic as nothing more than a game of manipulating meaningless symbols by specified arbitrary rules whereby one proposition can be inferred from others. Truth or falsity doesn’t enter this picture.

The turnstile symbol ⊢ represents “syntactically entails.”

“Sentence j is a syntactical consequence, in propositional logic, of the set of propositions k as there is a proof from premises k to conclusion j.”

A theorem in propositional logic is an argument without premises.
Yes, that’s possible! We’ll encounter this later in more depth.

From this viewpoint, we can take note (for example) of modus ponens and apply it when applicable. Modus ponens tells us: P→Q, P⊢Q. That is, given the premise P→Q and the premise P, we can conclude Q. It’s just an arbitrary rule we can use in this “game” of manipulating meaningless symbols.

A semantic viewpoint thinks about propositional logic in terms of meaning and truth or falsity. Good logic is not just some arbitrary “game.” We can think about meaningful propositions, which must be true or false.

Inference, then, becomes not a matter of specified arbitrary rules; rather, it becomes a matter of thinking about, given the truth of a set of propositions, what follows about the truth or falsity of another set of propositions.

The double turnstile symbol ⊨ represents “semantically entails.”

“Sentence j is a semantic consequence, in propositional logic, of the set of propositions k because, by the definitions of the truth-functional sentential connectives, it is ensured that j must be true whenever the sentences in k are all true.”

From this viewpoint, we can justify (for example) modus ponens as a good inference by a truth table. The argument P→Q, P⊢Q is valid because whenever the premises are all true, the conclusion is true.

The truth table shows this! When both P→Q and P are true, Q is true. Whenever we have all true premises, this conclusion is always true. This is happening with modus ponens; ergo, it’s a good argument!

Basic Inferences in Propositional Logic

Note that ∴ represents “therefore.”
And from here out we’ll use ⊢ to also represent “therefore.”

Modus ponens (MP): P→Q, P ⊢ Q

With the conditional P→Q, P is “sufficient” for Q. That is, if P really is the case, then Q really will be the case.

“If it is raining, then it is cloudy. It is raining. Therefore, it is cloudy.”

Modus tollens (MT): P→Q, ~Q ⊢ ~P

With the conditional P→Q, Q is “necessary” for P. That is, if Q is not really the case, P cannot really be the case.

“If it is raining, then it is cloudy. It is not cloudy. Therefore, it is not raining.”

Let’s prove this with a truth table. Every time the premises are true, the conclusion is true. When both P→Q and ~Q are true, ~P is true.

Hypothetical Syllogism (HS):
P→Q, Q→R ⊢ P→R

A chain argument with conditionals!

“If Paul eats bananas, then he will get very sick. If he gets very sick, then he will stay home. Therefore, if Paul eats bananas, then he will stay home.”

Proving this with a truth table is a bit more work. Notice that the two premises can be true together in four different rows, and in each of those four different rows the conclusion is true. Hence, we have a truth table proof of the hypothetical syllogism!

Disjunctive Syllogism (DS):
PvQ, ~P ⊢ Q

A disjunction will only be true if at least one of its options is true; thus, if we know one option is false, then the other must be true.

“Either Catherine will shop at Walmart or at Fry’s. She doesn’t shop at Fry’s. Therefore, Catherine will shop at Walmart.”

Once again, we’ll prove this with a truth table. We can “read off” from our truth table that this is a valid argument. When both PvQ and ~P are true together, Q is true.

Constructive Dilemma (CD):
P→Q, R→S, PvR ⊢ QvS

A true disjuction has it that at least one of its options is true; thus, because each of those options is also part of an antecedent to a conditional, at least one of those consequents of those conditionals must be true.

“If God exists, then the human being, created in His image, has supernatural significance. If atheism is true, then the human being is, at most, a super intelligent animal. Either God exists or atheism is true. Therefore, the human being has supernatural significance or is a super intelligent animal.”

This requires a large truth table! There are four atomic propositions here, which implies there will be 2^4 = 16 rows. Notice that each time all premises are true, the conclusion is likewise true.

Simplification (SIM): P&Q ⊢ P

Surely, when we have a true conjunction, one of its conjuncts alone must be true.

“I drank coffee and ate eggs. Therefore, I drank coffee.”

Our truth table shows that whenever the premise P&Q is true, the conclusion P is true. Simple! That’s the truth table proof.

Conjunction (CON): P, Q ⊢ P&Q

P is true. Q is true.
They are both true!

“Three is a prime. Five is a prime. Ergo, three and five are primes.”

The truth table confirms this valid inference.

Addition: P ⊢ PvQ

A disjunction is true if at least one choice is true. We can always, therefore, place a true proposition in a disjunction with some arbitrary proposition whatever its truth or falsity.

“Earth is a planet. That’s true. Therefore, Earth is a planet or the Moon is made out of cheese.”

In the truth table, the premise is true in two cases and in each of those cases the conclusion is true. Hence, it’s a valid argument.

It is, to be sure, a strange “inference”! That’s because the conclusion is very “weak.” The premise is true. Granted. But did we learn anything new from really throwing that premise into a disjunction with an arbitrary proposition? Not really.

All above terminology is fairly standard nowadays. There are exceptions to this rule. It’s usually not difficult to figure out what refers to what.

The conjunction rule is also called &-introduction (&I). Simplification is also called &-elimination (&E). Disjunctive syllogism is also known as modus tollendo ponens (MTP) and wedge-elimination (vE). Etc.

Additional Inference Rules in Propositional Logic

Although those are the “standard” rules of inference most contemporary textbooks cover, some textbooks will list additional rules. While more rules might indeed make writing proofs easier, more rules would, at some point, become cumbersome and redundant. Rules would become redundant because we could derive them from previous rules and/or conditional or indirect proofs.

Strictly speaking, if we so desired, any valid argument in propositional logic could be turned into a rule of inference. Though it would be impractical! A balance between minimalism and efficiency is best.

The destructive dilemma (DD) is the counterpart to the constructive dilemma (CD).

DD: P→Q, R→S, ~Qv~S ⊢ ~Pv~R

Aristotelian-Scholastic logic can teach us a lot about the practical uses of dilemmas!

Resolution (RES) is another inference rule that might pop up in a textbook. Kenneth H. Rosen’s discrete math textbook has it, for example, though it doesn’t have the dilemmas. (Don’t ask me why!)

RES: PvQ, ~PvR ⊢ QvR

Tautological Implications

With true premises and a valid argument, we always will get a true conclusion. These arguments can be written as a conditional Φ → ψ. We combine the premises in conjunctive relations in the antecedent Φ and place the conclusion in the consequent ψ.

This conditional will always be a tautology; otherwise, the argument is bad.
Such conditionals are called tautological implications.

Example 1. Consider the modus ponens rule of inference.
There’s two premises: P and P → Q
There’s the conclusion: Q
Potential tautological implication? [P&(P → Q)]→ Q

When we write the modus ponens argument into this conditional form, its truth table shows that it’s a tautology.

This is a tautological implication!

Example 2. We can think about any argument made in propositional logic, not just one of the rules of inference. Consider S↔E, E&M ⊢SvC.
There’s two premises: S↔E and E&M
There’s the conclusion: SvC
Potential tautological implication? [( S↔E)&(E&M)]→(SvC)

This truth table proves the argument S↔E, E&M ⊢SvC is valid.

Simple Deductive Proofs with Rules of Inference

It would be long and tedious to make arguments or proofs with truth tables alone.

As indicated above, that is technically possible. It’s a “mechanical” method that will always work. All we have to do is construct the relevant truth table so as to check to see if whenever all the premises are true simultaneously the conclusion is always true; and if it is, we then have a good argument or proof. Alternatively, we can construct a truth table to determine if the argument is a tautological implication; and if it is, we then have a good argument or proof.

Deductive proofs take a bit of intuition and sometimes guess work to pull off.
We derive propositions step-by-step by resorting to such things as the rules of inference.

We’ll number each line of our proof.
Each line must be justified as a premise, rule of inference, or other proof technique.

Example 1. . .

This proof contains five lines. One proposition appears per line. There are three premises. They are “justified” as being premises. Line four we inferred ~P from modus tollens (MT) with lines 1 and 2. When using a rule of inference, it’s important to state which rule we’re using and what propositions the inference is being used with. And line 5 brings us to our conclusion of ~R with the inference modus tollens (MT) from lines 3 and 4.

Example 2. . .

This proof contains six lines. There are three premises. Line 4 we inferred Q by modus ponens (MP) with lines 1 and 3. Line 5 we got R by modus ponens (MP) with lines 2 and 4. Line 6 brings us to the conclusion of Q&R by the conjunction rule (CON) with lines 4 and 5.

Example 3 . . .

This proofs contains seven lines with four premises. Line five uses the disjunctive syllogism (DS) rule of inference to get ~S with lines 3 and 4. Line six uses modus tollens (MT) to get ~B with lines 2 and 5. And line seven uses modus tollens (MT) to get ~X with lines 1 and 6.

Propositional logic proofs are often more complicated.

Before we look into them, however, we need to study logical equivalency (or rules of replacement), conditional proofs, and indirect proofs.