AI-09 Logic in AI

Logic
Propositional Logic
Propositional Logic: Symbols
Propositional Logic: Syntax
Propositional Logic: Laws
Propositional Logic: Disadvantages
Predicate Logic
First Order Logic
Predicate Logic: Symbols
Well-Formed Formula
WFF

1. A RTIFICIAL I NTELLIGENCE PANKAJ DEBBARMA Deptt . of CSE, TIT, Narsingarh Logic in AI

2. CONTENTS Logic Logic Propositional Logic Predicate Logic Well-Formed Formula

3. Logic Environment Inference Engine Knowledge Base Learning (Updating KB) KBA Output Input from Environment Operations performed by KBA TELL the KB what it perceives from the environment. ASK the KB what action it should perform. PERFORM the selected action.

4. Logic We consider three modern roles for logic in AI: logic as a basis for computation, logic for learning from a combination of data and knowledge, and reasoning about the behavior of machine learning systems.

5. Propositional Logic In propositional logic, the most fundamental propositions are called primitive propositions . Primitive propositions cannot be decomposed. Propositions that can be decomposed are compound propositions . Primitive propositions can be denoted by some symbols, and these symbols are called atomic formulas . From atomic formulas we can construct various logic formulas corresponding to various compound propositions.

6. Propositional Logic In propositional logic, atomic formulas are propositions, i.e., assertions such as A := “ Aryabhata is dead.” B := “Nagpur is on the banks of Nag river.” C := “Sudoku is fun.” Atomic formulas are denoted by capital letters A, B, C, etc. Each atomic formula is assigned a truth value : true (1) or false (0) . “Propositional logic is not the study of truth, but of the relationship between the truth of one statement and that of another.” ( Hedman 2004)

7. Propositional Logic: Symbols Word Symbol Example Meaning of Example Terminus Technicus not ¬ ¬A not A negation and ∧ A ∧ B A and B conjunction or ∨ A ∨ B A or B disjunction implies → A → B A implies B implication if and only if ↔ A ↔ B A if and only if B biconditional Relationships between propositions

8. Propositional Logic The natural language words may have slightly different meanings. Example: A ∧ B and B ∧ A should always have the same meaning. But the sentences She became sick and she went to the doctor. and She went to the doctor and she became sick. have totally different meanings.

9. Propositional Logic: Syntax formula := atomicFormula | complexFormula atomicFormula := True | False | symbol symbol := P | Q | R | . . . complexFormula := ( ¬ formula ) [negation] ( formula ∧ formula ) [conjunction] [positive literal] the same as atomicFormula . [negative literal] ¬ P where P is an atomic formula. Formulas are also called sentences or propositions.

10. Propositional Logic: Syntax formula := atomicFormula | complexFormula atomicFormula := True | False | symbol symbol := P | Q | R | . . . complexFormula := ( ¬ formula ) [negation] ( formula ∧ formula ) [conjunction] [positive literal] the same as atomicFormula . [negative literal] ¬ P where P is an atomic formula. Formulas are also called sentences or propositions.

11. Propositional Logic: Laws Implication P  Q=￢P∨Q Equivalence P↔Q=(P  Q)∧(Q  P) Absorption laws P∧T=P, P∧F=F, P∨T=T, P∨F=P Involution law ￢ ( ￢ P)=P Idempotent laws P∧P=P, P∨P=P Complement laws P∧￢P=F , P∨￢P=T Commutative laws P∧Q=Q∧P, P∨Q=Q∨P Associative laws (P∧Q)∧R= P∧(Q∧R), (P∨Q)∨R= P ∨(Q ∨ R) Distributive laws P∧(Q∨R)=(P∧Q)∨(P∧R), P∨(Q∧R)=(P∨Q)∧(P∨R) De Morgan’s laws ￢(P∧Q)=￢P∨￢Q, ￢(P∨Q)=￢P∧￢Q

12. Propositional Logic: Disadvantages Example: All students are present in the class. Some students are absent in the class. All ( ∀ ) and Some ( ∃ ) can be represented only by quantifiers .

13. Predicate Logic | First Order Logic Think about expressing these phrases in propositional logic: A := “Socrates is human.” B := “All humans are mortal.” C := “Thus, Socrates is mortal .” How can we see that A , B , C are related ? First-order logic is richer than propositional logic : H(a ) ∀ x H(x )  M(x) M(a) where A stands for “Socrates”, H for “is human”, and M for “ is mortal ”.

14. Predicate Logic | First Order Logic H(a ) ∀ x H(x )  M(x) M(a) So what do we have here? – x is a variable . Variables denote arbitrary elements (objects) of an underlying set. – a is a constant . Constants denote specific elements of an underlying set. – H and M are unary relations. – ∀ is the all quantifier . It is read “for all”. – We can also use the connectives we already know from propositional logic. In first-order logic, there are also relations with other arities , as well as n- ary functions . In addition to the all quantifier, there is the existential quantifier , read “there exists”.

15. Predicate Logic: Symbols – Let { f, g, h, . . . , f 1 , f 2 , . . . } be the set of function symbols. Every function symbol has a given arity . Sometimes we write f n to denote that f has arity n . – Let { a, b, c, . . . , a 1 , a 2 , . . . } be the set of constant symbols. Constant symbols can be seen as 0-ary function symbols. – { P, R, S, . . . , P 1 , P 2 , . . . } be the set of relation symbols. Every relation symbol (predicate) has a given arity . Sometimes we write P n to denote that P has arity n . – { x, y, z, x 1 , x 2 , . . . } be the set of variable symbols.

16. Well-Formed Formula (WFF) Propositional logic uses symbolic language (rules) to represent logical structure (syntactic ) . A  well-formed formula  (WFF) is a string of symbols that is grammatically (syntactically) correct by virtue of belonging to some language of interest . Which symbolic representations are WFF ?

17. Well-Formed Formula (WFF) RULES A any capital letter ~ can be prefixed with NOT (e.g. ~A) A V B letters with connectors between two WFF Not WFF A~ NOT cannot be suffix ( A ) parenthesis can be used only to connect two WFF, single is not valid (A · ) connector cannot be suffix

18. Well-Formed Formula (WFF) The capital of India is Naypyitaw . Orange is gray . x is blue. blue( x ) x is round. round( x ) ∀x blue( x ) round( x ) Is it WFF ? t aller(A,B) taller(A,B) ∧ taller(B,C) WFF ? WFF ?

19. Well-Formed Formula (WFF) If x is a variable representing people in the world, then taller( x , Ravi) ∀x taller( x , Ravi) ∃ x taller ( x , Ravi) taller ( ∃ x , Ravi ) taller ( A ∧ B , C ) Is it WFF ? Is it WFF ?