Introducing KRR Flashcards
Knowledge Representation and Reasoning
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.
RDF
Resource Description Framework
A way to represent knowledge using triples.
(Subject, predicate, object)
Advantage of RDF
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.
Ontology
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.
OWL
Web Ontology Language.
A W3C standard designed for the Semantic Web, and much more expressive than RDF.
Logic
The study of entailment (and syntax, semantics, rules of inference).
Propositional logic
The only things manipulated are propositions; things that are true or false.
First order logic
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.
Higher order logic
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.
Modal logics
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).
Non monotonic logics
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.
Compound proposition
A statement that consists of simpler propositions combined together.
Propositional logic builds statements out of: (3)
- Letters (or words) for atomic propositions, often called propositional variables or just variables
- The logical connectives
- Parentheses ‘(‘ and ‘)’ to avoid ambiguity.
5 Logical Connectives
- ∧ (and),
- ∨ (or),
- ¬ (not),
- → (implies / if – then –),
- ↔ (iff / – if and only if –).
Operator precedence
- ¬ (not),
- ∧ (and),
- ∨ (or),
- → (implies / if – then –),
- ↔ (iff / – if and only if –).
Tautology
This means a proposition is true under all values given to the variables it contains.
E.g. p ∨ ¬p is a tautology.
Contingency
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.
Contradiction
This means a proposition that is false overall whatever truth values its variables are given.
E.g. p ∧ ¬p is a contradiction.
Satisfiable proposition
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.
Logical implication
We say that proposition ɑ logically implies a proposition β if whenever ɑ evaluates to true, then β does so as well.
ɑ ⊫ β
Literal
A variable or the negation of a variable
Elementary product
A formula that is a conjunction of literals.
E.g. p ∧ q ∧ ¬p
Elementary sum
A formula that is a disjunction of literals
E.g. p ∨ q ¬p
Conjunctive normal form
A formula that is a conjunction of elementary sums.
Disjunctive normal form
A formula that is a disjunction of elementary products.
6 Rules to find CNF
-
p → qis replaced by¬p ∨ q -
¬ ( p ∨ q )is replaced by¬p ∧ ¬q -
¬ ( p ∧ q )is replaced by¬p ∨ ¬q -
¬¬pis replaced byp -
p ∨ ( q ∧ r)is replaced by( p ∨ q ) ∧ ( p ∨ r ) -
( p ∧ q ) ∨ ris replaced by( p ∨ r ) ∧ ( q ∨ r )
5 Rules to find DNF
-
p→qis replaced by¬p ∨ q -
¬ ( p ∨ q )is replaced by¬p ∧ ¬q -
¬¬pis replaced byp. -
p ∧ (q ∨ r)is replaced by( p ∧ q ) ∨ ( p ∧ r ) -
( p ∨ q ) ∧ ris replaced by( p ∧ r ) ∨ ( q ∧ r )
Principal CNF & DNF
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.
Implication →
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.
Implication equivalence
A → B
is equivalent to
~B → ~A
and equivalent to
¬A ∨ B
Maxterm
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}
Minterm
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}
Define
Principal DNF
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)
Principal CNF
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}
