Logic in Predicate and Propositional Logic

Predicate logic and propositional logic are used to represent the Knowledge base inferences.

1. -propositional logic Syntax, semantics, inferences and reasoning patterns -predicate logic Syntax, semantics, instance and its relationships -Unification and Resolution Prepared by T.ARCHANA, AP/CSE LOGIC

2. What is a Logic? A language with concrete rules No ambiguity in representation (may be other errors!) Allows unambiguous communication and processing

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

4. Proposition : Symbol Daisuke is a Japanese: P1 Chieko is a Japanese: P2 • Daisuke and Chieko are husband and wife: P3 • Makoto is the child of Chieko: P4 • If Chieko is a Japanese AND Mokoto is the child of Chieko, THEN Mokoto is a Japanese: P2∧P4⇒ P5 If Daisuke and Chieko are husband and wife AND Makoto is the child of Chieko, THEN Mokoto is the child of Daisuke: P3∧P4⇒ P6

5. An atomic formula is a logic formula. If P is a logic formula, ￢P is also a logic formula. If P and Q are logic formulas, P∧Q, P∨Q, P ⇒ Q, and P⇔Q are also logic formulas. Logic formulas defined in the previous page are called well-formed formulas. Similar to operators used in arithmetic calculation, logic symbols also have priorities. We can also use parentheses to define the priorities if the formula is ambiguous.

6. Logic symbols and their priorities

7. PROPOSITIONAL LOGIC CONNECTIVES

8. TRUTH TABLES

9. PROPERTIES OF OPERATORS

10. Predicate Logic Propositional logic combines atoms An atom contains no propositional connectives Have no structure ( today_is_wet , john_likes_apples ) Predicates allow us to talk about objects Properties:   is_wet (today) Relations:    likes(john, apples) True or false In predicate logic each atom is a predicate e.g. first order logic, higher-order logic

11. Basic Elements of First-order logic: Constant 1, 2, A, John, Mumbai, cat,.... Variables x, y, z, a, b,.... Predicates Brother, Father, >,.... Function sqrt, LeftLegOf, .... Connectives ∧, ∨, ¬, ⇒, ⇔ Equality == Quantifier ∀, ∃

12. Atomic sentences: Atomic sentences are the most basic sentences of first-order logic. These sentences are formed from a predicate symbol followed by a parenthesis with a sequence of terms. We can represent atomic sentences as  Predicate (term1, term2, ......, term n) . Example: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).                 Chinky is a cat: => cat ( Chinky ) .

13. Complex Sentences: Complex sentences are made by combining atomic sentences using connectives. First-order logic statements can be divided into two parts: Subject:  Subject is the main part of the statement. Predicate:  A predicate can be defined as a relation, which binds two atoms together in a statement. Consider the statement: "x is an integer." , it consists of two parts, the first part x is the subject of the statement and second part "is an integer," is known as a predicate.

14. Quantifiers in First-order logic A quantifier is a language element which generates quantification, and quantification specifies the quantity of specimen in the universe of discourse. These are the symbols that permit to determine or identify the range and scope of the variable in the logical expression. There are two types of quantifier: Universal Quantifier, (for all, everyone, everything) Existential quantifier, (for some, at least one).

15. Universal Quantifier Universal quantifier is a symbol of logical representation, which specifies that the statement within its range is true for everything or every instance of a particular thing. The Universal quantifier is represented by a symbol ∀, which resembles an inverted A. If x is a variable, then ∀x is read as: For all x For each x For every x.

16. Example: All man drink coffee. ∀x man(x) → drink (x, coffee). It will be read as: There are all x where x is a man who drink coffee.

17. Existential Quantifier Existential quantifiers are the type of quantifiers, which express that the statement within its scope is true for at least one instance of something. It is denoted by the logical operator ∃, which resembles as inverted E. When it is used with a predicate variable then it is called as an existential quantifier. If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be read as: There exists a 'x.' For some 'x.' For at least one 'x.'

18. Example: Some boys are intelligent. ∃x: boys(x) ∧ intelligent(x) It will be read as: There are some x where x is a boy who is intelligent.

19. Points to remember: The main connective for universal quantifier  ∀  is implication  → . The main connective for existential quantifier  ∃  is and  ∧ . Properties of Quantifiers: In universal quantifier, ∀ x∀y is similar to ∀ y∀x . In Existential quantifier, ∃ x∃y is similar to ∃ y∃x . ∃ x∀y is not similar to ∀ y∃x .

20. Some Examples of FOL using quantifier: 1. All birds fly. 2. Every man respects his parent. 3. Some boys play cricket. 4. Not all students like both Mathematics and Science. 5. Only one student failed in Mathematics.

21. 1. All birds fly. ∀x bird(x) →fly(x) . 2. Every man respects his parent. ∀x man(x) → respects (x, parent) . 3. Some boys play cricket. ∃x boys(x) → play(x, cricket) . 4. Not all students like both Mathematics and Science. ¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)]. 5. Only one student failed in Mathematics. ∃(x) [ student(x) → failed (x, Mathematics) ∧∀ (y) [¬(x==y) ∧ student(y) → ¬failed (x, Mathematics)] .

22. First Order Logic More expressive logic than propositional Constants are objects: john, apples Predicates are properties and relations: likes(john, apples) Functions transform objects: likes(john, fruit_of ( apple_tree )) Variables represent any object:  likes(X, apples) Quantifiers qualify values of variables True for all objects (Universal):              ∀X. likes(X, apples) Exists at least one object (Existential):   ∃X. likes(X, apples)

23. Example: FOL Sentence “Every rose has a thorn” For all X if (X is a rose) then there exists Y (X has Y) and (Y is a thorn)

24. Example: FOL Sentence “On Mondays and Wednesdays I go to John’s house for dinner”

25. i mplication elimination A particularly important rule allows you to get rid of the implication operator, ⇒ : X ⇒ Y  ≡  ¬X ∨ Y We will use this later on as a necessary tool for simplifying logical expressions The symbol   ≡  means “is logically equivalent to”

26. Conjunction elimination Another important rule for simplifying logical expressions allows you to get rid of the conjunction ( and ) operator, ∧ : This rule simply says that if you have an and operator at the top level of a fact (logical expression), you can break the expression up into two separate facts: MaryIsFemale ∧ MaryIsRich becomes: MaryIsFemale MaryIsRich

27. Forward and backward reasoning Situation: You have a collection of logical expressions (premises), and you are trying to prove some additional logical expression (the conclusion) You can: Do forward reasoning: Start applying inference rules to the logical expressions you have, and stop if one of your results is the conclusion you want Do backward reasoning: Start from the conclusion you want, and try to choose inference rules that will get you back to the logical expressions you have

28. Example Given: it_is_raining ∨ it_is_sunny it_is_sunny ⇒ I_stay_dry it_is_raining ⇒ I_take_umbrella I_take_umbrella ⇒ I_stay_dry You can conclude:   it_is_sunny ∨ it_is_raining     I_take_umbrella ∨ it_is_sunny     I_stay_dry ⇒ I_take_umbrella

29. unification Unification is a process of making two different logical atomic expressions identical by finding a substitution. Unification depends on the substitution process. It takes two literals as input and makes them identical using substitution. Let Ψ 1  and Ψ 2  be two atomic sentences and 𝜎 be a unifier such that,  Ψ 1 𝜎 = Ψ 2 𝜎 , then it can be expressed as  UNIFY(Ψ 1 , Ψ 2 ) . Example: Find the MGU for Unify{King(x), King(John)} Let Ψ 1  = King(x), Ψ 2  = King(John), Substitution θ = {John/x}  is a unifier for these atoms and applying this substitution, and both expressions will be identical. The UNIFY algorithm is used for unification, which takes two atomic sentences and returns a unifier for those sentences (If any exist). Unification is a key component of all first-order inference algorithms. It returns fail if the expressions do not match with each other. The substitution variables are called Most General Unifier or MGU.

30. Conditions for Unification: Following are some basic conditions for unification: Predicate symbol must be same, atoms or expression with different predicate symbol can never be unified. Number of Arguments in both expressions must be identical. Unification will fail if there are two similar variables present in the same expression.

31. Implementation of the Algorithm Step.1:  Initialize the substitution set to be empty. Step.2:  Recursively unify atomic sentences: Check for Identical expression match. If one expression is a variable v i , and the other is a term t i  which does not contain variable v i , then: Substitute t i  / v i  in the existing substitutions Add t i  /v i  to the substitution setlist . If both the expressions are functions, then function name must be similar, and the number of arguments must be the same in both the expression.

32. example From the pair of facts (not yet clauses, just facts): seafood(X) ⇒ likes(John, X)     (where X is a variable) seafood(shrimp) We ought to be able to conclude likes(John, shrimp) We can do this by unifying the variable X with the constant shrimp This is the same “unification” as is done in Prolog This unification turns seafood(X) ⇒ likes(John, X) into seafood(shrimp) ⇒ likes(John, shrimp)

33. Unification is a “pattern-matching” procedure  Takes two atomic sentences, called literals, as input Returns “Failure” if they do not match and a substitution list, θ, if they do That is, unify( p,q ) = θ means subst (θ, p) = subst (θ, q) for two atomic sentences, p and q θ is called the most general unifier ( mgu ) 

34. Resolution Resolution is a theorem proving technique that proceeds by building refutation proofs, i.e., proofs by contradictions. It was invented by a Mathematician John Alan Robinson in the year 1965 .

35. Steps for Resolution: Conversion of facts into first-order logic. Convert FOL statements into CNF( conjunctive normal form) Negate the statement which needs to prove (proof by contradiction) Draw resolution graph (unification).

36. Example: John likes all kind of food. Apple and vegetable are food Anything anyone eats and not killed is food. Anil eats peanuts and still alive Harry eats everything that Anil eats. Prove by resolution that: John likes peanuts.

37. Step-1: Conversion of Facts into FOL In the first step we will convert all the given statements into its first order logic.

38. Step-2: Conversion of FOL into CNF Eliminate all implication (→) and rewrite Move negation (¬)inwards and rewrite Rename variables or standardize variables Eliminate existential instantiation quantifier by elimination . Drop Universal quantifiers . Distribute conjunction ∧ over disjunction ¬.

39. Step-3: Negate the statement to be proved In this statement, we will apply negation to the conclusion statements, which will be written as ¬likes(John, Peanuts)

40. Step-4: Draw Resolution graph:

41. Practice example Jack owns a dog. Every dog owner is an animal lover. No animal lover kills an animal. Either Jack or Curiosity killed the cat, who is named Tuna. Did Curiosity kill the cat? These can be represented as follows: A. (∃x) Dog(x) ∧ Owns( Jack,x ) B. (∀x) ((∃y) Dog(y) ∧ Owns(x, y)) → AnimalLover (x) C. (∀x) AnimalLover (x) → ((∀y) Animal(y) → ¬Kills( x,y )) D. Kills( Jack,Tuna ) ∨ Kills( Curiosity,Tuna ) E. Cat(Tuna) F. (∀x) Cat(x) → Animal(x)  G. Kills(Curiosity, Tuna)

42. Convert to clause form CNF A1. (Dog(D))  A2. (Owns( Jack,D )) B. (¬Dog(y), ¬Owns(x, y), AnimalLover (x)) C. (¬ AnimalLover (a), ¬Animal(b), ¬Kills( a,b )) D. (Kills( Jack,Tuna ), Kills( Curiosity,Tuna )) E. Cat(Tuna) F. (¬Cat(z), Animal(z)) Add the negation of query:   G: (¬Kills(Curiosity, Tuna))

43. The resolution refutation proof   R1: ¬G, D, {} (Kills(Jack, Tuna)) R2: R1, C, {a/Jack, b/Tuna} (~ AnimalLover (Jack), ~Animal(Tuna)) R3: R2, B, {x/Jack} (~Dog(y), ~Owns(Jack, y), ~Animal(Tuna)) R4: R3, A1, {y/D} (~Owns(Jack, D), ~Animal(Tuna)) R5: R4, A2, {} (~Animal(Tuna)) R6: R5, F, {z/Tuna} (~Cat(Tuna)) R7: R6, E, {} FALSE

44. THANK YOU