Introducing KRR

Question 1

Knowledge Representation and Reasoning

Answer 1

Concerns
… the representation of knowledge in a form suitable for computational manipulation and exchange,
… together with the use of reasoning
… to process knowledge represented in this way
… in order to both generate new knowledge and uncover properties of existing knowledge.

Question 2

RDF

Answer 2

Resource Description Framework

A way to represent knowledge using triples.

(Subject, predicate, object)

Question 3

Advantage of RDF

Answer 3

A set of triples forms a graph where the nodes are labelled by things that can be subjects or objects, and the directed links are labelled by predicates.

Question 4

Ontology

Answer 4

An engineering artifact, usually a model of (some aspect of) the world.

It introduces vocabulary describing various aspects of the domain being modelled and provides an explicit specification of the intended meaning of that vocabulary.

Question 5

OWL

Answer 5

Web Ontology Language.

A W3C standard designed for the Semantic Web, and much more expressive than RDF.

Question 6

Logic

Answer 6

The study of entailment (and syntax, semantics, rules of inference).

Question 7

Propositional logic

Answer 7

The only things manipulated are propositions; things that are true or false.

Question 8

First order logic

Answer 8

Besides statements that can be true or false, there are also individual things that the statements can refer to.

There is quantification over the collection of individuals.

That means you can say that all of them have some property, or that at least one of them has some property.

Question 9

Higher order logic

Answer 9

Differs from first order logic by allowing quantification over sets of individuals (second order logic), or sets of sets, or sets of sets of sets, etc of the individuals. This can make some things easier to express at the expense of being more impractical to do than any computation.

Question 10

Modal logics

Answer 10

These arose traditionally in expressing statements about propositions such as necessity and possibility.

Modal logics can be used to represent concepts such as an agent knowing something, a person believing something, someone being obliged to do something, one event happening in the future or the past of something else (temporal logics).

Question 11

Non monotonic logics

Answer 11

In classical logic, adding new facts does not make something false that was previously true.

But in a log of human situations we do this in the sense of assuming things to be true that can be rejected after getting more information.

Question 12

Compound proposition

Answer 12

A statement that consists of simpler propositions combined together.

Question 13

Propositional logic builds statements out of: (3)

Answer 13

• Letters (or words) for atomic propositions, often called propositional variables or just variables
• The logical connectives
• Parentheses ‘(‘ and ‘)’ to avoid ambiguity.

Question 14

5 Logical Connectives

Answer 14

• ∧ (and),
• ∨ (or),
• ¬ (not),
• → (implies / if – then –),
• ↔ (iff / – if and only if –).

Question 15

Operator precedence

Answer 15

1. ¬ (not),
2. ∧ (and),
3. ∨ (or),
4. → (implies / if – then –),
5. ↔ (iff / – if and only if –).

Question 16

Tautology

Answer 16

This means a proposition is true under all values given to the variables it contains.

E.g. p ∨ ¬p is a tautology.

Question 17

Contingency

Answer 17

This means a proposition that is true overall when its variables are given some truth values, but false in other cases.

This means a proposition is true under all values given to the variables it contains.

E.g. p ⋁ q is a contingency.

Question 18

Contradiction

Answer 18

This means a proposition that is false overall whatever truth values its variables are given.

E.g. p ∧ ¬p is a contradiction.

Question 19

Satisfiable proposition

Answer 19

A proposition is said to be satisfiable when there is some choice of values for the variables that makes it true.

All tautologies and all contingencies are satisfiable.

Question 20

Logical implication

Answer 20

We say that proposition ɑ logically implies a proposition β if whenever ɑ evaluates to true, then β does so as well.

ɑ ⊫ β

Question 21

Literal

Answer 21

A variable or the negation of a variable

Question 22

Elementary product

Answer 22

A formula that is a conjunction of literals.

E.g. p ∧ q ∧ ¬p

Question 23

Elementary sum

Answer 23

A formula that is a disjunction of literals

E.g. p ∨ q ¬p

Question 24

Conjunctive normal form

Answer 24

A formula that is a conjunction of elementary sums.

Question 25

Disjunctive normal form

Answer 25

A formula that is a disjunction of elementary products.

Question 26

6 Rules to find CNF

Answer 26

• p → q is replaced by ¬p ∨ q
• ¬ ( p ∨ q ) is replaced by ¬p ∧ ¬q
• ¬ ( p ∧ q ) is replaced by ¬p ∨ ¬q
• ¬¬p is replaced by p
• p ∨ ( q ∧ r) is replaced by ( p ∨ q ) ∧ ( p ∨ r )
• ( p ∧ q ) ∨ r is replaced by ( p ∨ r ) ∧ ( q ∨ r )

Question 27

5 Rules to find DNF

Answer 27

• p→q is replaced by ¬p ∨ q
• ¬ ( p ∨ q ) is replaced by ¬p ∧ ¬q
• ¬¬p is replaced by p.
• p ∧ (q ∨ r) is replaced by ( p ∧ q ) ∨ ( p ∧ r )
• ( p ∨ q ) ∧ r is replaced by ( p ∧ r ) ∨ ( q ∧ r )

Question 28

Principal CNF & DNF

Answer 28

There are lots of different formulas in DNF/CNF which are all logically equivalent to a given formula.

To get a unique form, we need to use the principal CNF & DNF.

These are “essentially unique” in the sense that they only differ in the ordering of the elementary sums or products involved.

Question 29

Implication →

Answer 29

p → q
* p is called the antecedent
* q is called the consequent.

The implication p→q asserts that:
if the antecedent p is true, then the consequent q bust also be true.

However, when p is false, p→q does not make any specific claim about the truth value of the consequent q, therefore it is considered true by default.

Question 30

Implication equivalence

Answer 30

A → B

is equivalent to

~B → ~A

and equivalent to

¬A ∨ B

Question 31

Maxterm

Answer 31

An elementary sum is a maxterm over a given set of variables iff it uses every variable in the set exactly once.

E.g..
* p over {p}
* ¬p over {p}
* p ∨ q over {p, q}
* p ∨ q ∨ ¬r over {p, q, r}

Question 32

Minterm

Answer 32

An elementary product is a minterm over a given set of variables iff it uses every variable in the set exactly once.

E.g.
* p over {p}
* ¬p over {p}
* p ∧ q over {p, q}
* p ∧ q ∧ ¬r over {p, q, r}

Question 33

Define

Principal DNF

Answer 33

A formula is in principal DNF over a set of variables iff
* it is in DNF, and
* every elementary product is a minterm (over the set)

Question 34

Principal CNF

Answer 34

A formula is in principal CNF over a set of variables iff
* it is in CNF, and
* every elementary sum is a maxterm (over the set)

E.g.
* T
* p over {p}
* p ∨ q over {p, q}
* ( p ∨ q ) ∧ ( ¬p ∨ q ) over {p, q}
* ( p ∨ ¬q ∨ r ) ∧ ( p ∨ q ∨ ¬r ) over {p, q, r}