Propositional Logic Inference

Let KB = { S1, S2,..., SM } be the set of all sentences in our Knowledge Base, where

each Si is a sentence in Propositional Logic. Let { X1, X2, ..., XN } be the set of all the

symbols (i.e., variables) that are contained in all of the M sentences in KB. Say we want

to know if a goal (aka query, conclusion, or theorem) sentence G follows from KB.

Inference in First order logic

Rules of Inference

Here are some examples of sound rules of inference. Each can be shown to be sound once

and for all using a truth table. The left column contains the premise sentence(s), and the

right column contains the derived sentence. We write each of these derivations as A |- B ,

where A is the premise and B is the derived sentence.

Name Premise(s) Derived

Sentence

Modus Ponens A, A => B B

And Introduction A, B A ^ B

And Elimination A ^ B A

Double Negation ~~A A

Unit Resolution A v B, ~B A

Resolution A v B, ~B v C A v C

 Using Inference Rules to Prove a Query/Goal/Theorem

A proof is a sequence of sentences, where each sentence is either a premise or a sentence

derived from earlier sentences in the proof by one of the rules of inference. The last

sentence is the query (also called goal or theorem) that we want to prove.

Example for the "weather problem" given above.

1. Q Premise

2. Q => P Premise

3. P Modus Ponens(1,2)

4. (P ^ Q) => R Premise

5. P ^ Q And Introduction(1,3)

6. R Modus Ponens(4,5)