Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    Lecture 25

    Uploaded by

    Rana Babar

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lecture 25

    Uploaded by

    Rana Babar
    2 views30 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    2 views30 pages

    Lecture 25

    Uploaded by

    Rana Babar

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 30

    ITEC4119-Artificial Intelligence

    Lecture 25
    Knowledge representation

    Muhammad Umar Farooq


    Knowledge representation method
    • Logic
    – Propositional logic
    – Predicate logic
    • Semantic net
    • Frames
    Propositional logic
    • Propositional logic, also known as statement logic
    • True, false but not both
    – 2+2=4 T
    – 1+1=2 T
    – 1+5=4 F
    – George W. Bush is the 43rd President of the United
    States.
    – Paris is the capital of France.
    • Everyone born on Monday has purple hair.
    Propositional logic
    In propositional logic, a statement that can either be true
    or false is called a proposition. For example, the
    statement “it’s raining outside” is either true or false. If
    you have one or more propositions, you can connect
    them to make more complex sentences using logical
    connectives like “not,” “and,” “or,” “if…then,” and “if and
    only if.” In symbols these connectives look like this
    • not: ¬
    • and: ∧
    • or: ∨
    • if, then: →
    • if and only if: ⟺
    For multiple statements

    • Logical operators

    OR Disjunction v

    AND Conjunction ^
    Not Negation ¬
    If then Implication →
    If and only If Bi- implication ↔
    Truth table for OR operator

    A B A vB
    T T T
    T F T
    F T T
    F F F
    Truth table for AND operator

    A B A ^B
    T T T
    T F F
    F T F
    F F F
    Truth table for NOT operator

    A ¬A
    T F
    F T
    Truth table for Implication operator

    A B A → B
    T T T
    T F F
    F T T
    F F T
    Truth table for Bi- Implication

    A B A ↔B
    T T T
    T F F
    F T F
    F F T
    ( 𝑃^𝑄 →(¬𝑅))

    P Q R (P ^ Q) ¬𝑹 ( 𝑃^𝑄 →(¬𝑅))

    T T T T F F
    T T F T T T
    T F T F F T
    T F F F T T
    F T T F F T
    F T F F T T
    F F T F F T
    F F F F T T
    Translating between English and
    logical notation
    • “It is raining and it is Tuesday.”
    – R∧T
    – Where R means “it is raining” and T means “it is
    Tuesday.”
    • it is raining in New York”
    – N(R)
    – R(N)
    • it is raining in New York, and I’m either getting
    sick or just very tired”
    – R(N) ∧ (S(I) ∨ T(I))
    Translating between English and
    logical notation
    • It is not raining in New York,
    – ￢R(N)
    • “I’m either not well or just very tired”
    – ￢W(I) ∨ T(I)
    • “if it is raining then I will get wet.”
    – R→W(I)
    Translating between English and
    logical notation
    • Whenever he eats sandwiches that have pickles in
    them, he ends up either asleep at his desk or singing
    loud songs
    – S(y) ∧ E(x, y) ∧ P(y)→A(x) ∨ (S(x, z) ∧ L(z))
    • S(y) means that y is a sandwich.
    • E(x, y) means that x (the man) eats y (the sandwich).
    • P(y) means that y (the sandwich) has pickles in it.
    • A(x) means that x ends up asleep at his desk.
    • S(x, z) means that x (the man) sings z (songs).
    • L(z) means that z (the songs) are loud.
    Tautology
    • An expression that is always true is called a
    tautology.

    A A∨￢A
    False True
    True True

    • If A is a tautology, we write:
    |= A
    Logical equivalence
    • A∧B
    • B∧A
    • It should be fairly clear that these two
    expressions will always have the same value
    for a given pair of values for A and B. In other
    words , we say that the first expression is
    logically equivalent to the second expression.
    We write this as
    • A∧B≡B∧A
    Logical equivalence
    • A∨A≡ A
    • A∧A≡ A
    • A ∧ (B ∧ C) ≡ (A ∧ B) ∧C (∧ is associative)
    • A ∨ (B ∨ C) ≡ (A ∨ B) ∨C (∨ is associative)
    • A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) (∧ is distributive over ∨)
    • A ∧ (A ∨ B) ≡ A
    • A ∨ (A ∧ B) ≡ A
    • A ∧ true ≡ A
    • A ∧ false ≡ false
    • A ∨ true ≡ true
    • A ∨ false ≡ A
    • A→B ≡ ￢A ∨ B
    Homework
    • All of these equivalences can be proved by
    drawing up the truth tables for each side of
    the equivalence and seeing if the two tables
    are the same. You may want to try this to
    satisfy yourself that all of the equivalences are
    correct,
    DeMorgan’s Laws
    • A ∧ B ≡ ￢(￢A ∨ ￢B)
    • A ∨ B ≡ ￢(￢A ∧ ￢B)
    Simplification of logical expression
    • (C ∧ D) ∨ ((C ∧ D) ∧ E)
    • A ∨ (A ∧ B) ≡ A

    hence
    =(C ∧ D) ∨ ((C ∧ D) ∧ E) ≡ C ∧ D
    Deduction
    • If we have a set of assumptions
    {A1, A2, . . . , An},
    and from those assumptions we are able to derive a
    conclusion, C, then we say that we have deduced C
    from the assumptions, which is written
    • {A1, A2, . . . ,An} Ⱶ C
    • If C can be concluded without any assumptions,
    then we write
    • ⱵC
    Inference
    • To derive a conclusion from a set of
    assumptions, we apply a set of inference
    rules. To distinguish an inference rule from a
    sentence, we often write A Ⱶ B as follows:
    𝐴
    𝐵
    Inference rule
    • ∧-Introduction
    • ∧-Elimination
    • Or-introduction
    • →Elimination
    • → Introduction
    • ￢ ￢ Elimination
    ∧-Introduction

    A B
    •
    A∧B

    • Given A and B, we can deduce A∧B. This


    follows from the definition of ∧.
    ∧-Elimination
    A∧B
    –
    A

    • Similarly

    A∧B
    –
    B
    • These rules say that given A ∧ B, we can deduce A
    and we can also deduce B separately. Again,
    these follow from the definition of ∧.
    Or-introduction
    A
    •
    A∨B
    B
    •
    A∨B
    • These rules say that from A we can deduce the
    disjunction of A with any expression.
    • For example, from the statement “I like logic,” we can
    deduce expressions such as “I like logic or I like
    cheese,” “I like logic or I do not like logic,” “I like logic
    or fish can sing,” “I like logic or 2 + 2 = 123,” and so on.
    This follows because true ∨ B is true for any value of B.
    →Elimination
    A A→B
    •
    B
    • In other words, if A is true and A implies B is
    true, then we know that B is true.
    • For example, if we replace A with “it is
    raining” and B with “I need an umbrella,” then
    we produce the following:
    – It is raining. If it’s raining, I need an umbrella.
    Therefore, I need an umbrella.
    → Introduction
    A.
    ..

    • C
    A→C

    • This rule shows that if in carrying out a proof


    we start from an assumption A and derive a
    conclusion C, then we can conclude that A→C.
    ￢ ￢ Elimination
    ￢￢A
    •
    A

    • This rule states that if we have a sentence that


    is negated twice, we can conclude the
    sentence itself, without the negation. Clearly,
    this rule follows from the definition of ￢.
    Weakness in propositional logic
    • We can not deal with infinite data
    • All horses are black
    • All boys like cricket
    • Some boys like cricket
    Cricket Cricket
    Boys
    Boys

    You might also like