5. Knowledge Representation and Reasoning

Introduction ¹

• A proposition is a statement offered for consideration.
• Propositional calculus is simply a language with a grammar that can be used to describe whether something is true or false in a world.
• In propositional calculus, we offer statements and then consider or evaluate their truthfulness.
• A proposition can be any of the following:
  • An atomic proposition … a symbol that is either true or false.
  • A compound proposition is a combination of other propositions all of which collectively will evaluate to either true or false using the grammar defined in the following.

Statement	Meaning
p ˅ q	p or q
p ˄ q	p and q
¬p	not p
p ⇒ q	if p then q (p logically implies q)
p ⇔ q	p if and only if q (p logically equals q)
p ← q	p if q
p ⊕ q	p xor q

⁢

• A knowledge base is a set of propositions that are given to be true and each element in a knowledge base is called an axiom.
• Propositional logic helps to accomplish the task of determining valid solutions and reasoning through solution options.
• Horn Clauses:
  • A horn clause provides the ability to provide by contradiction.
  • One form of the horn clause is with the false statement.
  • Sahpe: false ←a1 ^ a2 ^ …^ ak.
  • The Horn clause can either be a definite clause of the normal form or an integrity constraint clause of the form defined above.
• Complete Knowledge Assumption:
  • For every atom within the environment every case in which the atom is true is known.
  • In this environment, an agent can assume that an atom is false if it cannot determine that is true.
  • To have a complete knowledge assumption requires a closed-world assumption.  This can be contrasted with an open-world assumption.
  • In the open-world assumption, the agent does not know every case in which an atom is true and as such cannot make any assumptions about the atom because there is a lack of knowledge.
• Deduction:
  • Top-down reasoning, or from general to specific.
  • It is the process of following a set of axioms to determine a conclusion.
  • Example: If A is true, and B is equivalent to A, then B must also be true.
• Induction:
  • Bottom-up reasoning, or from specific to general.
  • Conclusions are drawn from the strong evidence offered in the axioms (or propositions).
  • In inductive reasoning, we have no absolute proof of the truthfulness of a proposition merely strong evidence (a high probability) that the proposition is true.
• Abduction:
  • Reasoning from effect to cause.
  • It is an educated guess.
  • Occam’s razor comes into play here because we want to identify the most simple ‘theory’ or hypothesis that fits the data.

Propositions and Inference ²

5.1 Propositions

• A proposition is a sentence, written in a language, that has a truth value (i.e., it is true or false) in a world.
• A proposition is built from atomic propositions and logical connectives.
• The operators ¬, ∧, ∨, →, ←, ↔, and ⊕ are logical connectives.
• A knowledge base is a set of propositions that are stated to be true.
• An element of the knowledge base is an axiom.
• A model of knowledge base K⁢B is an interpretation in which all the propositions in K⁢B are true.

5.2 Propositional Constraints

• The class of propositional satisfiability or SAT problems have:
  • Boolean variables.
  • Calusal constraints. an or of literals l1 ∨ l2 ∨ ... ∨ ln, and it is true if at least one of the literals is true.
• Any propositional formula can be converted into clausal form.
• A total assignment corresponds to an interpretation.
• It is possible to convert any finite constraint satisfaction problem (CSP) into a propositional satisfiable problem.

5.3 Propositional Definite Clauses

• The language of propositional definite clauses is a subset of propositional calculus that does not allow uncertainty or ambiguity.
• h ← ⁢a1 ∧ ⁢... ∧ ⁢am:
  • It is a definite clause.
  • It reads as “h if a1 and … and am”.
  • h is the head of the clause and a1, …, am are the body of the clause.
  • If m > 0, then the clause is called a rule.
  • If m = 0, then the clause is called a fact or an atomic clause.
• After the computer is given a knowledge base about a particular domain, a user might like to ask the computer questions about that domain.
• A query is a way of asking whether a proposition is a logical consequence of a knowledge base, using the command ask(KB, α).
  • KB is the knowledge base.
  • α is the query.
  • It returns true if α is a logical consequence of KB, and false otherwise.
  • If ask returns false, it does not mean that α is false, but rather that it is impossible to prove that α is true with the given knowledge base.
• A proof is a mechanically derivable demonstration that a proposition logically follows from a knowledge base.
• A theorem is a provable proposition.
• A proof procedure is a –possibly non-deterministic– algorithm for deriving consequences of a knowledge base.
• A proof procedure is sound with respect to the semantics if everything that can be derived from a knowledge base is a logical consequence of the knowledge base. That is, if K⁢B ⊢ g, then K⁢B ⊧ g.
• A proof procedure is complete with respect to the semantics if there is a proof of each logical consequence of the knowledge base. That is, if K⁢B⊧g, then K⁢B⊢g.

5.4 Querying the User

• An agent receives some information as background knowledge and some as observations online.
• An observation is information received online from users, sensors, or other knowledge sources.
• Assume an observation is a set of atomic propositions, which are implicitly conjoined.

5.5 Knowledge-Level Debugging

• Three types of non-syntactic errors arise in rule-based systems:
  • Incorrect answers (false positives): some atom that is false in the intended interpretation was derived.
  • No answer (false negative): the proof failed on a particular true atom when it should have succeeded.
  • Infinite loop; the proof procedure never terminates because it is stuck in a cycle.

5.6 Proving by Contradiction

• The definite-clause language does not allow a contradiction to be stated. However, a simple expansion of the language can allow proof by contradiction.
• An integrity constraint is a clause of the form f⁢a⁢l⁢s⁢e ← ⁢a1 ∧ ⁢... ∧ ⁢ak.
• A Horn clause is either a definite clause or an integrity constraint. That is, a Horn clause has either false or a normal atom as its head.
• Reasoning from contradictions is a very useful tool. For many activities it is useful to know that some combination of assumptions is incompatible.
• An assumable is an atom that can be assumed in a proof by contradiction. A proof by contradiction derives a disjunction of the negation of assumables.

5.6.3 Consistency-Based Diagnosis

• Making assumptions about what is working normally, and deriving what components could be abnormal, is the basis of consistency-based diagnosis.
• A fault is something that is wrong with a system.
• The aim of consistency-based diagnosis is to determine the possible faults based on a model of the system and observations of the system.
• By making the absence of faults assumable, conflicts can be used to prove what is wrong with the system.
• Given the set of all conflicts, a user can determine what may be wrong with the system being diagnosed.
• Given a set of conflicts, a consistency-based diagnosis is a set of assumables that has at least one element in each conflict.

5.7 Complete Knowledge Assumption

• A database is often complete in the sense that anything not implied is false.
• The given definite-clause logic does not allow the derivation of a conclusion from a lack of knowledge or a failure to prove.
• The complete knowledge assumption assumes that, for every atom, the clauses with the atom as the head cover all the cases when the atom is true. In particular, an atom with no clauses is false.

5.8 Abduction

• Abduction is a form of reasoning where assumptions are made to explain observations.
• For example, if an agent were to observe that some light was not working, it hypothesizes what is happening in the world to explain why the light was not working.
• A tutoring agent could try to explain why a student gives some answer in terms of what the student understands and does not understand.
• The term abduction was coined by Peirce (1839–1914) to differentiate this type of reasoning from:
  • Deduction which involves determining what logically follows from a set of axioms.
  • Induction, which involves inferring general relationships from examples.
• In abduction, an agent hypothesizes what may be true about an observed case. An agent determines what implies its observations –what could be true to make the observations true.
• Observations are trivially implied by contradictions (as a contradiction logically implies everything), so we want to exclude contradictions from our explanation of the observations.
• A scenario of ⟨K⁢B,A⟩ is a subset H of A such that K⁢B∪H is satisfiable. K⁢B∪H is satisfiable if a model exists in which every element of K⁢B and every element H is true. This happens if no subset of H is a conflict of K⁢B.
• An explanation of proposition g from ⟨K⁢B,A⟩ is a scenario that, together with K⁢B, implies g.
• Abduction differs from consistency-based diagnosis in:
  • In CBD, only normal behavior needs to be represented, and the hypotheses are assumptions of normal behavior. In abductive diagnosis, faulty behavior as well as normal behavior needs to be represented, and the assumables need to be for normal behavior and for each fault (or different behavior).
  • In abductive diagnosis, observations need to be explained. In CBD, observations are added to the knowledge base, and f⁢a⁢l⁢s⁢e is proved.
• Abductive diagnosis requires more detailed modeling and gives more detailed diagnoses, because the knowledge base has to be able to actually prove the observations from the knowledge base and the assumptions.
• Abductive diagnosis is also used to diagnose systems in which there is no normal behavior. For example, in a tutoring agent.
• Abduction can also be used for design, in which the query to be explained is a design goal and the assumables are the building blocks of the designs.

Deduction, Induction, Abduction ³

• Rule: Cause → Effect.
• Example 1:
  • Rule: If it is cloudy, then it will rain.
  • Cause: It is cloudy.
  • Effect: It will rain.
• Example 2:
  • Rule: Joe hates Mary. (If Mary is present, Joe will leave; “implication”).
  • Cause: Mary is present.
  • Effect: Joe will leave.
• Example 3:
  • Rule: If flue, then fever.
  • Cause: Fever.
  • Effect: Flue.
• Deduction:
  • We know the rule and the cause, and we can deduce the effect.
  • Example, if we know that Joe hates Mary, and Mary arrives, we can deduce that Joe will leave.
  • It is truth-preserving; if the rule is true and we observe the cause, the effect is always true.
• Induction:
  • We know the effect and the cause, and we can induce the rule.
  • Example: if we we notice repeatedly that it rains when it is cloudy, we can induce the rule that if it is cloudy, it will rain.
  • It is NOT truth-preserving; we could have induced the wrong rule (aka, the rule is not always true); in other words, if we know a cause and effect for a sample, it does not mean that it applies for the entire population.
• Abduction:
  • We know the effect and the rule, and we can abduce the cause.
  • Example: If Joe leaves when Mary arrives, we can abduce that Joe hates Mary (aka, ask ourselves, does Joe hate Mary?).
  • Diagnosis is an instance of abduction.
  • It is NOT truth-preserving; we could have abduced the wrong cause (aka, there are other reasons that we are not considering); in other words, there could be multiple causes for the same effect.
• Deduction, abduction, and induction are all forms of inference.
• We are scientists:
  • We observe some data about the world (effect).
  • We abduce some explanation for it (cause).
  • We induce the rules that explain the data (rule).
  • We deduce the consequences of the rules (effect).

ProLog ⁴

First Order Logic ⁵

References

---

1. Learning Guide Unit 5: Introduction | Home. (2025). Uopeople.edu. https://my.uopeople.edu/mod/book/view.php?id=454706&chapterid=555049 ↩

2. Poole, D. L., & Mackworth, A. K. (2017). Artificial Intelligence: Foundations of computational agents. Cambridge University Press. https://artint.info/2e/html/ArtInt2e.html Chapter 5 - Propositions and Inference. ↩

3. Udacity. (2015, February 23). Deduction, induction, abduction - Georgia Tech - KBAI: Part 5 [Video]. YouTube. https://youtu.be/-nn3XMoPC7s ↩

4. The Power of Prolog. (2019, October 21). Horn clauses [Video]. YouTube. https://youtu.be/hgw59_HBU2A ↩

5. Iacobelli, F. (2015, July 20). FOL (First order logic) [Video]. YouTube. https://youtu.be/73AUBVOW-sM ↩