Logical deductions, or inference rules, are used to prove new propositions using
previously proved ones.
A fundamental inference rule is modus ponens. This rule says that a proof of P
together with a proof that P IMPLIES Q is a proof of Q.
Inference rules are sometimes written in a funny notation. For example, modus
ponens is written:
P; P IMPLIES Q/ Q
When the statements above the line, called the antecedents, are proved, then we
can consider the statement below the line, called the conclusion or consequent, to
also be proved.
A key requirement of an inference rule is that it must be sound: an assignment
of truth values to the letters P, Q, . . . , that makes all the antecedents true must
also make the consequent true. So if we start off with true axioms and apply sound
inference rules, everything we prove will also be true.
There are many other natural, sound inference rules, for example:
(P IMPLIES Q; Q IMPLIES R)/P IMPLIES R
(NOT.P IMPLIES NOT.Q)/Q IMPLIES P
On the other hand,
(NOT.P IMPLIES NOT.Q)/P IMPLIES Q
is not sound: if P is assigned T and Q is assigned F, then the antecedent is true
and the consequent is not.
As with axioms, we will not be too formal about the set of legal inference rules.
Each step in a proof should be clear and “logical”; in particular, you should state
what previously proved facts are used to derive each new conclusion.
Mathematics for Computer Science
This subject offers an interactive introduction to discrete mathematics oriented toward computer science and…
source- MATHS for computer science by Eric Lehman.