100% tevredenheidsgarantie Direct beschikbaar na betaling Zowel online als in PDF Je zit nergens aan vast
logo-home
Knowledge Representation (XM_0059): Complete summary with practice questions €7,99   In winkelwagen

Samenvatting

Knowledge Representation (XM_0059): Complete summary with practice questions

 59 keer bekeken  2 keer verkocht

An overview for SAT-solving, Ontology Reasoning and Bayesian Networks, which were the content of the 2020 Knowledge Representation course at Vrije Universiteit. Including practice questions and answers!

Voorbeeld 3 van de 22  pagina's

  • 5 november 2021
  • 22
  • 2020/2021
  • Samenvatting
Alle documenten voor dit vak (2)
avatar-seller
timdeboer
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.

Voordelen van het kopen van samenvattingen bij Stuvia op een rij:

Verzekerd van kwaliteit door reviews

Verzekerd van kwaliteit door reviews

Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!

Snel en makkelijk kopen

Snel en makkelijk kopen

Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.

Focus op de essentie

Focus op de essentie

Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper timdeboer. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €7,99. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 67474 samenvattingen verkocht

Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen

Start met verkopen
€7,99  2x  verkocht
  • (0)
  Kopen