Logical Deductions-Maths for Computer Science

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:

Rule.

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:

Rule.

(P IMPLIES Q; Q IMPLIES R)/P IMPLIES R

Rule

(NOT.P IMPLIES NOT.Q)/Q IMPLIES P

On the other hand,

Non-Rule.

(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.

source- MATHS for computer science by Eric Lehman.

thank you!!!!

Programmer | Technical content Writer | Lives in India | Wanna go where I can breathe freedom