4a_Knowledge_Representation.dvi
COMP9414 Knowledge Representation 1
This Lecture
� Knowledge Representation and Logic
� Logical Arguments
� Propositional Logic
◮ Syntax
◮ Semantics
� Validity, Equivalence, Satisfiability, Entailment
� Inference by Natural Deduction
UNSW ©W. Wobcke et al. 2019–2021
COMP9414: Artificial Intelligence
Lecture 4a: Knowledge Representation
Wayne Wobcke
e-mail:w. .au
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Knowledge Representation 3
Knowledge Representation
� Any agent can be described on different levels
◮ Knowledge level (knowledge ascribed to agent)
◮ Logical level (algorithms for manipulating knowledge)
◮ Implementation level (how algorithms are implemented)
� Knowledge Representation is concerned with expressing knowledge
explicitly in a computer-tractable way (for use by an agent in
reasoning) – not the same as Newell’s view
� Reasoning attempts to take this knowledge and draw inferences (e.g.
answer queries, determine facts that follow from the knowledge,
decide what to do, etc.) – as part of the agent architecture
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Knowledge Representation 2
The Knowledge Level
Knowledge Level Hypothesis. There exists a distinct computer systems
level, lying immediately above the symbol level, which is characterized
by knowledge as the medium and the principle of rationality as the law of
behavior.
Principle of Rationality. If an agent has knowledge that one of its actions
will lead to one of its goals, then the agent will select that action.
Knowledge. Whatever can be ascribed to an agent, such that its behavior
can be computed according to the principle of rationality.
“The Knowledge Level” (Newell, 1982)
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Knowledge Representation 5
Motivating Example – Ontologies
AfPak Ontology
� Ashraf Ghani is President Ghani – equality
� Ashraf Ghani is the President of Afghanistan – role
� Ashraf Ghani is in the government – part of
� Nangarhar is a province – a kind of
� Nangarhar is in Afghanistan – part of
� Bombing implies Attacking – linguistic meaning/semantics
Ontology = Set of such facts
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Knowledge Representation 4
Knowledge Representation and Reasoning
� A knowledge-based agent has at its core a knowledge base
� A knowledge base is an explicit set of sentences about some domain
expressed in a suitable formal representation language
◮ Sentences express facts (true) or non-facts (false)
◮ So the “knowledge base” is better called a “belief base”
� Fundamental Questions
◮ How do we write down knowledge about a domain/problem?
◮ How do we automate reasoning to deduce new facts or ensure
consistency of a knowledge base?
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Knowledge Representation 7
Syntax vs Semantics
Syntax Describes the legal sentences in a knowledge representation
language (e.g. in the language of arithmetic expressions x < 4) Semantics Refers to the meaning of sentences. Relates sentences (and sentence fragments) to aspects of the world the sentence is about. Semantics refers to a sentence’s relationship to the “real world” or to some model of the world. Semantic properties of sentences include truth and falsity (e.g. x < 4 is true for x = 3 and false when x = 5). Semantic properties of names and descriptions include referents. Note: The meaning of a sentence is not intrinsic to that sentence. An interpretation is required to determine sentence meanings. Interpretations are agreed amongst a linguistic community. UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 6 Why Formal Languages – not English? � Natural languages exhibit ambiguity “The fisherman went to the bank” (lexical) “The boy saw a girl with a telescope” (structural) “The table won’t fit through the doorway because it is too [wide/narrow]” (co-reference) � Ambiguity makes it difficult to interpret meaning of phrases/sentences ◮ But also makes inference harder to define and compute � Symbolic logic is a syntactically unambigious language (originally developed in an attempt to formalize mathematical reasoning) UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 9 Logical Arguments An argument relates a set of premises to a conclusion – valid if the conclusion necessarily follows from the premises All humans have 2 eyes Jane is a human Therefore Jane has 2 eyes All humans have 4 eyes Jane is a human Therefore Jane has 4 eyes � Both are (logically) correct valid arguments � Which statements are true/false? UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 8 Propositions � Propositions are entities (facts or non-facts) that can be true or false � Expressed using ordinary declarative sentences (not questions) ◮ “The sky is blue” expresses the proposition that the sky is blue (here and now). Is this proposition true? � Examples “Socrates is bald” (assumes ‘Socrates’, ‘bald’ are well defined) “The car is red” (requires ‘the car’ to be identified) “Socrates is bald and the car is red” (complex proposition) � In Propositional Logic, use single letters to represent propositions, a scheme of abbreviation, e.g. P: Socrates is bald � Important: Reasoning is independent of propositional substructure! UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 11 Propositional Logic � Use letters to stand for “basic” propositions; combine them into more complex sentences using operators for not, and, or, implies, iff � Propositional connectives: ¬ negation ¬P “not P” ∧ conjunction P∧Q “P and Q” ∨ disjunction P∨Q “P or Q” → implication P → Q “If P then Q” ↔ bi-implication P ↔ Q “P if and only if Q” UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 10 Logical Arguments An argument relates a set of premises to a conclusion – invalid if the conclusion can be false when the premises are all true All humans have 2 eyes Jane has 2 eyes Therefore Jane is human No human has 4 eyes Jane has 2 eyes Therefore Jane is not human � Both are (logically) incorrect invalid arguments � Which statements are true/false? UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 13 Improving Readability � (P → (Q → (¬(R))) vs P → (Q →¬R) � Rules for omitting brackets ◮ Omit brackets where possible (except maybe last example below!) ◮ Precedence from highest to lowest is: ¬, ∧, ∨, →, ↔ ◮ All binary operators are left associative (so P→Q→R abbreviates (P → Q)→ R) � Questions ◮ Is (P∨Q)∨R (always) the same as P∨ (Q∨R)? ◮ Is (P → Q)→ R (always) the same as P → (Q → R)? UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 12 From English to Propositional Logic � “It is not the case that the sky is blue”: ¬B (alternatively “the sky is not blue”) � “The sky is blue and the grass is green”: B∧G � “Either the sky is blue or the grass is green”: B∨G � “If the sky is blue, then the grass is not green”: B →¬G � “The sky is blue if and only if the grass is green”: B ↔ G � “If the sky is blue, then if the grass is not green, the plants will not grow”: B → (¬G →¬P) UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 15 Example – Complex Sentence R S ¬R R∧S ¬R∨S (R∧S)→ (¬R∨S) True True False True True True True False False False False True False True True False True True False False True False True True Thus (R∧S)→ (¬R∨S) is a tautology UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 14 Truth Table Semantics � The semantics of the connectives can be given by truth tables P Q ¬P P∧Q P∨Q P → Q P ↔ Q True True False True True True True True False False False True False False False True True False True True False False False True False False True True � One row for each possible assignment of True/False to variables � Important: P and Q are any sentences, including complex sentences UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 17 Material Implication � P → Q evaluates to False only when P is True and Q is False � P → Q is equivalent to ¬P∨Q: material implication � English usage often suggests a causal connection between antecedent (P) and consequent (Q) – this is not reflected in the truth table � Examples ◮ (P∧Q)→ Q is a tautology for any Q ◮ P → (P∨Q) is a tautology for any Q ◮ (P∧¬P)→ Q is a tautology for any Q UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 16 Definitions � A sentence is valid if it is True under all possible assignments of True/False to its variables (e.g. P∨¬P) � A tautology is a valid sentence � Two sentences are equivalent if they have the same truth table, e.g. P∧Q and Q∧P ◮ So P is equivalent to Q if and only if P ↔ Q is valid � A sentence is satisfiable if there is some assignment of True/False to its variables for which the sentence is True � A sentence is unsatisfiable if it is not satisfiable (e.g. P∧¬P) ◮ Sentence is False for all assignments of True/False to its variables ◮ So P is a tautology if and only if ¬P is unsatisfiable UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 19 Proof of Equivalence Let P ⇔ Q mean “P is equivalent to Q” (P ⇔ Q is not a formula) Then P∧ (Q → R) ⇔ ¬(P → Q)∨ (P∧R) P∧ (Q → R) ⇔ P∧ (¬Q∨R) [Implication] ⇔ (P∧¬Q)∨ (P∧R) [Distributivity] ⇔ (¬¬P∧¬Q)∨ (P∧R) [Double negation] ⇔ ¬(¬P∨Q)∨ (P∧R) [De Morgan] ⇔ ¬(P → Q)∨ (P∧R) [Implication] Assumes substitution: if A ⇔ B, replace A by B in any subformula Assumes equivalence is transitive: if A ⇔ B and B ⇔C then A ⇔C UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 18 Logical Equivalences – All Valid Commutativity: p∧q ↔ q∧ p p∨q ↔ q∨ p Associativity: p∧ (q∧ r)↔ (p∧q)∧ r p∨ (q∨ r)↔ (p∨q)∨ r Distributivity: p∧ (q∨ r)↔ (p∧q)∨ (p∧ r) p∨ (q∧ r)↔ (p∨q)∧ (p∨ r) Implication: (p → q)↔ (¬p∨q) Idempotent: p∧ p ↔ p p∨ p ↔ p Double negation: ¬¬p ↔ p Contradiction: p∧¬p ↔ FALSE Excluded middle: p∨¬p ↔ TRUE De Morgan: ¬(p∧q)↔ (¬p∨¬q) ¬(p∨q)↔ (¬p∧¬q) UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 21 Simple Entailments Write P |= Q for {P} |= Q P∧Q |= P P∧Q |= Q P |= P∨Q Q |= P∨Q P |= ¬¬P ¬¬P |= P {P, P → Q} |= Q If P |= Q then |= P → Q UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 20 Entailment � S entails P (S |= P) if whenever all formulae in S are True, P is True ◮ Semantic definition – concerns truth (not proof) � Compute whether S |= P by calculating a truth table for S and P ◮ Syntactic notion – concerns computation/proof ◮ Not always this easy to compute (how inefficient is this?) � A tautology is a special case of entailment where S is the empty set ◮ All rows of the truth table are True UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 23 Entailment – Tautology R S ¬R R∧S ¬R∨S (R∧S)→ (¬R∨S) True True False True True True True False False False False True False True True False True True False False True False True True Therefore |= (R∧S)→ (¬R∨S) UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 22 Entailment Example P Q P → Q Q True True True True True False False False False True True True False False True False Therefore {P, P → Q} |= Q � In the only row where both P and P → Q are True (row 1), Q is also True (here S is the set {P, P → Q}) Note: The column for P → Q is calculated from that for P and Q using the truth table definition, and Q is used again to check the entailment UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 25 Natural Deduction Proofs Notes: ⊢ means proof; ⇒ is our → UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 24 Models Can also think in terms of models, formally structured interpretations with respect to which truth is evaluated � For Propositional Logic, a model is one row of the truth table A model M is a model of a sentence α if α is True in M Let M(α) be the set of all models of α Then KB |= α if and only if M(KB)⊆ M(α) M( ) M(KB) x x x x x x x x x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x x x x UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 27 Conclusion � Ambiguity of natural languages avoided with formal languages � Enables formalization of (truth preserving) entailment � Propositional Logic: Simplest logic of truth and falsity � Knowledge Based Systems: First-Order Logic � Automated Reasoning: How to compute entailment (inference) � Many many logics not studied in this course UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Knowledge Representation 26 Natural Deduction Example UNSW ©W. Wobcke et al. 2019–2021