PROPOSITIONAL CALCULUS
Using Constraints on Feature Values
The agent's world can be represented in either icon based or feature based. Icon based representations shows simulations of certain state of world. Feature based representations are descriptions of the world and these are easy to communicate among agents. In case feature values cannot be sensed directly, feature values are inferred from other feature values using constraints imposed by agent on the world.
The following statements are difficult to represent iconically,
1) General rules
Example: All red boxes are pushable.
2) Negative Statements
Example: .Block B is not on floor (Here it is not specifying where block B is).
3) Uncertain Information
Example: Either Block B is on Block C or Block B is on Block A.
These type of statements can be formulated as constraints on the feature values. These constraints are useful in inferring feature values that cannot be sensed directly. This act of inferring information about agent's present state to compute future state is known as reasoning.
For example, consider a robot need to move a box from one place to another, the robot should have adequate battery power source and the box should be liftable by robot. This constraint can be represented in propositional calculus as,
Battery_OK ^ Liftable ⊃ Moves
Here symbol '^' means 'and' and '⊃' _means .'implies'
Local languages such as propositional calculus and first order predicate (FOPC) are very much important in area of artificial intelligence. Logic can be defined as a scientific study of the process of reasoning and the system of rules and procedures that help in reasoning process. The logic involves,
- Language (syntax).
- Inference rules.
- Semantics.
The Language
The language provides syntax for expressing the statements. The elements of the language are,
Atoms: Atoms are set of strings of characters that start with capital letter (Example: P1, P2, P, Q, R .....) and two atoms T(true) and F(false).
Connectives: The following connectives are used to give relation between two atoms.
∨ - or
Λ - and
⊃ - implies
¬ - not
WFF's: (Well Formed Formulas)
Wffs are also as sentences. Wffs are defined as,
1) Every atom (P, Q, P1....) is a wff.
2) Assume ∝, β are wffs, then,
Disjunction : ∝ v β
Conjunction : ∝ ∧ β
Implication : ∝ ⊃ β
Negation : ¬ ∝
Are also wffs. Here left side of connective is known as antecedent (Here antecedent is ∝) consequent (Here it is β). In case of negation (¬) the atom is known as literal.
Examples:
(P v Q) ⊃ P
P ⊃ ¬ Q
P ∧ P ⊃ P
(P ⊃ Q) ⊃ (¬Q ∧ P)
Rules of Inference
We can produce additional wffs, by imposing certain laws on existing wffs." These ar called rules of inference. Some of the examples of inference rules are as follows,
1) Modus Ponens: The wff β can be inferred from wffs ∝ and ∝ ⊃ β
2) Commutative: The wff β ∧ ∝ is inferred from wff ∝ ∧ β .
3) â´· Introduction: The wff ∝ ∧ β is inferred from two wffs ∝ and β
4) ∨ Introduction: The wff ∝ v β can be inferred either from ∝ or from β.
5) ∧ Elimination: The wff ∝ can be inferred from ∝ ∧ β
6) ¬ Elimination: The wff ∝ can be inferred from ¬(¬ ∝)
Definition of Proof
Proof a wff ∝n is a sequence of wffs (∝1, ∝2,....∝n) from set Δ where each ∝i is in the set or it is derived from wffs of that set. Here ∝n is known as theorem of set Δ. The notation for representing that ∝n is proved from Δ is,
Δ ⊢ ∝n
If ∝n is derived by using inference rules from set of inference rules R then the notation is as follows,
Δ ⊢r ∝n
Example
Δ = {P, Q, P ⊃ R }
Proof of Q ∧ R = {P, P ⊃ R, R, Q, Q ∧ R}
The same can be represented as proof tree as follows,
Fig: Proof tree of Q ∧ R
