Theory Of Inference For The Predicate Calculas

If an implication P → Q is a tautology where P and Q may be compound statement involving any number of propositional variables we say that Q logically follows from P. Suppose (P1, P2 ....... Pn) P →Q. Then this implication is true regardless of the truth values of any of its components. In this case, we say that q logically follows from P1, P2…..,Pn.
Proofs in mathematics are valid arguments that establish the truth of mathematical statements.

To deduce new statements from statements we already have, we use rules of inference which are templates for constructing valid arguments. Rules of inference are our basic tools for establishing the truth of statements. The rules of inference for statements involving existential and universal quantifiers play an important role in proofs in Computer Science and Mathematics, although they are often used without being explicitly mentioned.

Valid Argument :

  • An argument in propositional logic is a sequence of propositions.
  • All but the final propositions in the argument are called hypothesis or Premises.
  • The final proposition is called the conclusion.
  • An argument form in propositional logic is a sequence of compound propositions - involving propositional variables.
  • An argument form is valid if no matter which particular propositions are substituted for the propositional variables in its premises, the conclusion is true if the premises are all true.

Rules of Inference for Propositional logic
We can always use a truth table to show that an argument form is valid. Arguments based on tautologies represent universally correct method of reasoning. Their validity depends only on the form of statements involved and not on the truth values of the variables they contain such arguments are called rules of inference.

These rules of inference can be used as building blocks to construct more complicated valid argument forms
Let P: “You have a current password”
Q: “You can log onto the network”.
Then, the argument involving the propositions,
“If you have a current password, then you can log onto the network”.
“You have a current password” therefore: You can log onto the network” has the form…

Where is the symbol that denotes ‘therefore we know that when P & Q are proposition variables, the statement ((P→Q) ∧ P)→Q is a tautology.

This is valid argument and hence is a rule of inference, called modus ponens or the law of detachment.
(Modus ponens is Latin for mode that affirms)
The most important rules of inference for propositional logic are as follows…..

Example : Show that R→S can be derived from the premises (i) P→(Q→S) (ii) ¬ (R → P) and iii) Q.

Solution : The following steps can be used to establish the conclusion.

Hence the proof