Knowledge Representation - Vrije Universiteit 2020
Contents
Essence of SAT-solving ............................................................................................................................ 2
Essence of Ontology Reasoning .............................................................................................................. 8
Essence of Bayesian Networks .............................................................................................................. 13
,Essence of SAT-solving
In this first part of the series on Knowledge Representation (KR), we will dive into one of the
well-studied fields of KR: Boolean Satisfiability Checking, in short written as SAT-checking
or also called SAT-solving. The idea of SAT-checking is to translate a real world problem into
a question which contains multiple terms. We want to find a assignment of truth values (True
or False) to these terms for which the question or problem will be solved. This assignment of
truth values gives us the solution to the original problem!
A decision tree of a SAT-problem
However, a problem arises when randomly assigning truth values to our terms: when we have
n terms, we have to search through all n² combinations of truth values! For small problems, a
computer will solve the problem in less than a couple of seconds. However, realistic problems
can have up to a million terms! Try typing 1.000.000² in your calculator….
Luckily, a lot of smart people have thought about this problem and tried to come up with
faster and more efficient ways of searching through all the combinations of truth values. This
is the field of SAT-solving! Before we head into this field though, I would first like to give a
overview of the logic on which SAT-solving is based: Propositional Logic.
Propositional Logic
Statements in a knowledge base of Propositional Logic, or PL, are facts about the current
world of which we know are true of false. In PL, we make a new statement for every
observation we encounter, such as ‘John has red hair’, ‘Mary is a girl’ for which we assign
True of False to. We can combine statements with connectives to derive new information
(which is called inference).
Below, the most important connectives are stated in order of precedence (meaning that
statements should first be solved for the most important connective):
• Not (Negation) : ¬. A statement ¬p is true when p is false.
, • And (Conjunction) : ∧. A statement p ∧ q is true when p and q are both true, else false.
• Or (Disjunction) : ∨. A statement p ∨ q is true when p or q is true, or both are true.
• XOR (Exclusive Disjunction) : ⊕. A statement p ∨ q is true when p or q is true, but
NOT when both are true.
• Implication : →. The logical meaning of implication p → q is a claim that if p is true,
q should also be true. If p is false, I make no claim and the statement will be true
regardless of q.
• Bi-implication : ↔. A statement p ↔ q is true if p and q have the same truth value
(both true of both false).
Not sure yet about the implications of these connectives? Fill in some formula’s on this
website from Stanford, which will automatically derive the truth table for you.
We can derive truth tables ourselves for complex statements to find the results of all possible
truth assignments, for example for the statement:
(p ∨ ¬q) ∧ r
• Take all 8 combinations of possible truth values of p, q and r.
• Calculate the value of ¬q from the values of q
• Calculate the value for (p ∨ ¬q) by combining values from p and ¬q
• Calculate the value of (p ∨ ¬q) ∧ r by combining values from (p ∨ ¬q) and r.
A statement is a tautology (or a valid statement) if the results of the truth table is true for all
combinations. A statement is inconsistent (or invalid) if the result is false for all
combinations. A statement is satisfiable if at least one combinations of truth assignments
gives true as result. One statement A entails another statement B if when A is true, B is also
true (but not the other way around). When also the other way around is the case, so two
statements have the same truth tables, A and B are logically equivalent.
For complex statements with multiple terms, multiple combinations of truth assignments
could make the statement true. However, when solving problems with 1.000.000 terms, we
really do not want to manually derive a truth table and write down all combinations of terms
which would make the statement true. Researchers have found that finding a satisfiable truth
assignment for complex problems writing the problem in Conjunctive Normal Form (CNF)
can decrease the search time for SAT algorithms.
Practice questions PL:
PL1
Write truth tables for the following statements:
p↔q
¬p ∨ q
p ∧ ¬p
p∧q∧r
p→q→r
(p ∧ q) ∨ (q ∧ r)
((p ∧ q) ∧ ¬ r) → p
Are any of these statements a tautology? Or inconsistent? After trying for some minutes,
check your truth table answer at this website from Stanford.
Contents
Essence of SAT-solving ............................................................................................................................ 2
Essence of Ontology Reasoning .............................................................................................................. 8
Essence of Bayesian Networks .............................................................................................................. 13
,Essence of SAT-solving
In this first part of the series on Knowledge Representation (KR), we will dive into one of the
well-studied fields of KR: Boolean Satisfiability Checking, in short written as SAT-checking
or also called SAT-solving. The idea of SAT-checking is to translate a real world problem into
a question which contains multiple terms. We want to find a assignment of truth values (True
or False) to these terms for which the question or problem will be solved. This assignment of
truth values gives us the solution to the original problem!
A decision tree of a SAT-problem
However, a problem arises when randomly assigning truth values to our terms: when we have
n terms, we have to search through all n² combinations of truth values! For small problems, a
computer will solve the problem in less than a couple of seconds. However, realistic problems
can have up to a million terms! Try typing 1.000.000² in your calculator….
Luckily, a lot of smart people have thought about this problem and tried to come up with
faster and more efficient ways of searching through all the combinations of truth values. This
is the field of SAT-solving! Before we head into this field though, I would first like to give a
overview of the logic on which SAT-solving is based: Propositional Logic.
Propositional Logic
Statements in a knowledge base of Propositional Logic, or PL, are facts about the current
world of which we know are true of false. In PL, we make a new statement for every
observation we encounter, such as ‘John has red hair’, ‘Mary is a girl’ for which we assign
True of False to. We can combine statements with connectives to derive new information
(which is called inference).
Below, the most important connectives are stated in order of precedence (meaning that
statements should first be solved for the most important connective):
• Not (Negation) : ¬. A statement ¬p is true when p is false.
, • And (Conjunction) : ∧. A statement p ∧ q is true when p and q are both true, else false.
• Or (Disjunction) : ∨. A statement p ∨ q is true when p or q is true, or both are true.
• XOR (Exclusive Disjunction) : ⊕. A statement p ∨ q is true when p or q is true, but
NOT when both are true.
• Implication : →. The logical meaning of implication p → q is a claim that if p is true,
q should also be true. If p is false, I make no claim and the statement will be true
regardless of q.
• Bi-implication : ↔. A statement p ↔ q is true if p and q have the same truth value
(both true of both false).
Not sure yet about the implications of these connectives? Fill in some formula’s on this
website from Stanford, which will automatically derive the truth table for you.
We can derive truth tables ourselves for complex statements to find the results of all possible
truth assignments, for example for the statement:
(p ∨ ¬q) ∧ r
• Take all 8 combinations of possible truth values of p, q and r.
• Calculate the value of ¬q from the values of q
• Calculate the value for (p ∨ ¬q) by combining values from p and ¬q
• Calculate the value of (p ∨ ¬q) ∧ r by combining values from (p ∨ ¬q) and r.
A statement is a tautology (or a valid statement) if the results of the truth table is true for all
combinations. A statement is inconsistent (or invalid) if the result is false for all
combinations. A statement is satisfiable if at least one combinations of truth assignments
gives true as result. One statement A entails another statement B if when A is true, B is also
true (but not the other way around). When also the other way around is the case, so two
statements have the same truth tables, A and B are logically equivalent.
For complex statements with multiple terms, multiple combinations of truth assignments
could make the statement true. However, when solving problems with 1.000.000 terms, we
really do not want to manually derive a truth table and write down all combinations of terms
which would make the statement true. Researchers have found that finding a satisfiable truth
assignment for complex problems writing the problem in Conjunctive Normal Form (CNF)
can decrease the search time for SAT algorithms.
Practice questions PL:
PL1
Write truth tables for the following statements:
p↔q
¬p ∨ q
p ∧ ¬p
p∧q∧r
p→q→r
(p ∧ q) ∨ (q ∧ r)
((p ∧ q) ∧ ¬ r) → p
Are any of these statements a tautology? Or inconsistent? After trying for some minutes,
check your truth table answer at this website from Stanford.
