Created on March 5, 2013, 7:48 p.m. by Hevok & updated by Hevok on May 2, 2013, 5:34 p.m.
Ontologies can be represented with Logic. This can be done via Description Logics which is somewhere between Propositional Logics and First Order Logics. It means it is a Fragment of First Order Logic that is restricted in some Sense, while preserving some of its Expressivity and on the other hand with using its Complexity.
In order to try to understand how to do calculations on top of that knowledge one has to look at the Foundations of Logic.
If we are able to express our thoughts with the help of Logic or mathematics, than we would be able to calculate the answer of a dispute and we do not need to struggle or to argue.
The only way to rectify our reasonings is to make them as tangible as those of the Mathematicians, so that we can find our error at a glance, and when there are disputes among persons, we can simply say: Let s calculate, without further ado, to see who is right.
First at all in Logic we have Syntax. But Syntax are only Symbols without Meaning, meaning the Syntax defines Rules on how to construct well formed and valid sequences of simple Symbols (i.e. Strings). On top of that we have the Semantic. The Semantic defines the Meaning of the Syntax. So the Semantic defines Rules how the Meaning of Complex Sequences of Symbols can be derived from simpler ones, from atomic sequences of Symbols.
For example, given the Syntax of a Programming Language: if is i is smaller than zero, then display negative account. It has a specific Assignment of the Meaning.
If (i<0) then display ("negative account!")
Assignment of the Meaning
print the message "negative account!", if the account balance is negative
However there are different types of Semantic (Variants of Semantics)
For any kind of Logic you have a Set of Statements. To deduce or infer new knowledge you need some kind of an Entailment Relation. So Logic consists of a Set of Statements and an Entailment. Then from a Set of Statements Φ, which is a subset of S (the set of all Statements) one can entail with the help of the Entailment Relation, another Statement φ which is also an Element of the Set of Statements. So big phi Φ entails small phi φ. φ is a Logical Consequence of the Set of Statements represented by Φ. From the from the Assertions of Φ follows the Assertion φ. On the other hand vice versa if for two Assertions φ,ψ both Element of Set S of Statements, if for them holds that ψ is a logical consequence of φ and φ is a logical Consequence of ψ. Here one has to consider that on the right side of the Entailment Relation there is always a Set, therefore also for a single Relation we consider the Set consisting of this single Relation. This entails the other Relation. If both hold vice versa, then both Φ and φ are logical equivalent. So with these two things the set of statements and the Entailment Relation, each Logic is defined.
Any logic L:= ( S, ⊨) consists of
Let Φ ⊆ S and φ ∈ S: Φ ⊨ φ
"φ is a logical consequence of Φ" or
"from the Assertions of Φ follows the Assertion φ"
If for 2 Assertions φ,ψ ∈ S
both {φ} ⊨ ψ and {ψ} ⊨ φ,
then both Assertions φ and ψ are logically equivalent
φ ≡ ψ
The Entailment Relation need to be made explicitly so one need to define a model for the Entailment Relation.
In the most simple Logic, the Propositional Logic one has a small set of logical connectives (Negation, Conjunctions, Disjunction, Implication, Equivalence) and one has a Set of Symbols. These both Sets are disjoint. On the other hand one has the two Truth values (true and false) that have been applied or assigned to the Statements. Then one has Production Rules for Propositional Formulas (Propositions). All Atomic Formulas are Propositions, which means e.g. all elements of φ are Propositions. If φ is a Proposition than also not ¬φ is a Proposition. φ and ψ are Propositions then both of them are connected with a Set of Logical Connectives (and, or, if-then, equivalent) are then also Propositions. There are certain Priority Rules, which means the Negation is prior the Conjugation and Disjunction and this is prior to Implication and Equivalence.
Logical connective | Name | Intentional Meaning |
⌐ | Negation | "not" |
∧ | Conjunction | "and" |
∨ | Disjunction | "or" |
→ | Implication | "if - then" |
↔ | Equivalence | "if, and only if, then" |
Logical connectives: Op=¬,∧,∨,→, (,)}, a set of Symbols Σ
with Σ∩Op=∅ and {true, false}
Production rules for propositional formula (Propositions):
Priority: ¬ prior to ∧, ∨ prior to →, ↔
Facts in Propositional Logic can be modeled with simple Statements assigned to Symbols.
Simple Assertions | Modeling |
The moon is made of green cheese | g |
It rains | r |
The street is getting wet | n |
With this simple Assertions one can make more complicated Assertions and more complex Statements for example one can compose Assertions.
Composed Assertions | Modeling |
It it rains, then the street will get wet. | r → n |
If it rains and the street does not get wet, | (r ∧ ⌐n) → g |
the moon is made of green cheese. |
In the Model-theoretic Semantics for Propositional Logic one has to map all Atomic Propositions to true and false.
Quantifier Name Intentional Meaning ---------- -------------------- ------------------- ∃ Essential Quantifier "it exists" ∀ Universal Quantifier "for all" ========== ==================== ===================
Operators (logical connectives) as in Propositional Logic
Variables e.g. X, Y, Z, ...
Constants e.g. a, b, c, ...
Functions e.g. f, g, h, ... (incl. arity)
Relations/Predicates e.g. p, q, r, ... (incl. arity)
(∀X(∃Y)((p(X)∨ ¬q(f(X),Y))→ r(X))
FOL: Syntax
In First Order Logic on distinguishes between Terms, which are made from Variables, Constants and Functions, so one has a selection of different kind of Terms.
More complex are Atoms that are Relations with Terms as Arguments.
If one also additionally to the Atoms applies Operators an Quantifiers then one has a Formula, e.g. for all Pixels it holds that if the location of Pixel is greater than 128 then it must be a red Pixel.
Overall if one makes Statements in First Order Logic, use brackets whenever one is in doubt about the priority. Also all Variables should be quantified. If a Variable is not quantified, most times we assume that all of its Assignment should be meant by its Statement. I.e. if there is no Quantifier it will be interpreted as an universal Quantifier.
"correct" formulation of Terms from Variables, Constants and Functions:
f(X), g(a,f(Y)), s(a), i(H,T), x_location(Pixel)
"correct" formulation of Atoms from Relations with Terms as arguments
p(f(x)), q(s(a),g(a,f(Y))), add(a,s(a),s(a)), greater_than(x_location(Pixel),128)
"correct" formulation of Formulas from Atoms, Operators and Quantifiers:
(∀Pixel)(greater_than(x_location(Pixel),128) → red(Pixel))
if in doubt, use brackets!
All Variables should be quantified!
In First order Logic one can model Facts simply by translation of Natural Language into First Order Logic.
For example to state that all child loves coding is defined as that for all Variables X it holds if X is a Child, then X loves Coding.
For all X and all Y it holds that if X is the father of Y then and only then X is male and X is parent of Y.
Another example if there is one or ore interesting lecture, i.e. if there exists one or more interesting lecture then one states this fact with: There exists and Variable X where X is a Lecture and X is also interesting.
So one can define Facts by First Order Logic and one has much more Expressivity compared to Propositional Logics where one can only make Facts and Statements about single objects and not about Sets of Objects for example, so about Classes and Objects that are not directly named.
Another example would be that for all X and all Y if X is a neighbor of Y than Y is also a neighbor f X.
"All kids love coding."
∀X: Child(X) → lovesCoding(X)
"the father of a person is a male parent."
∀X ∀Y: isFather(X,Y) ↔ (Male(X) ∧ isParent(X,Y))
"There are (one or more) interesting lectures."
∃X: Lecture(X) ∧ Interesting(X)
"The Relation 'isNeighbor' is symmetric."
∀X ∀Y: isNeighbor(X,Y) → isNeighbor(X,Y)
If one wants to look the model-theoretic Semantics of First Order Logics then first of all one has to define a domain that we consider, then we have to map all Constants Symbols to elements of D and then we have all functions Symbols and all Relations Symbols to Relations of this Domain.
Then automatically Assertions become Elements of D of the Domain and Relation Symbols with Arguments will become True or False in the End, and logical connectives and Quantifiers are treated likewise.
Given a complex expression in First Order Logic, for instance all Penguins are black and white and some old TV shows also are black and white, Therefore, it implies that some Penguins must be old TV shows.
Although this does not make really Sense, one has to find a mechanism to prove this. One can proof this if we find an Assignment of the Variables given that does not fulfill this Formula, i.e. the Formula in the End is not refutable, which means it is not a Tautology and there is an Assignment that this Formula is wrong.
Considering a domain, for example a set M that contains all the Elements a and b. We have no constants Symbol, but only variables and we show that the Formula is refutable which means it is not a Tautology.
For example taking a Symbol or an Element of the Set a and we have the interpret-ion of the Penguin where we have the Variable a as one of the placeholders for the Variables X. And we say we take black and white as the interpretation a we take old TV shows b and black and white b which should be true. So Pingiun a should be a Pinguin and a should be black, b should be a TV show and b should also be black and white which should be true. If we assign a is not a and b is not a Pinguin then the entire Formula if we substitute, this Interpretation, i.e. this elements of the set a and b into the positions of the variables with the assignment that the first part is true and the second part is wrong, then the formula would also compute to wrong which means that this Interpretation will not entail the formula F and is not a model for F. Therefore we have shown that this Statement is not always True, i.e. it is not a Tautology.
If one finds an interpretation, which means an Assignment, that holds and is consistent and that computes for the Formula as False then one has formula proven in an automated way that this Assertions, i.e. this Statement is really wrong.
((∀X( penguin(X) → blackandwith(X) ) ∧ (∃X)( oldTVshow(X) ∧ blackandwith(X) ) ) → (∃X)( penguin(X) ∧ oldTVshow(X) )
I(penguin)(a), I(blackandwite)(a), I(oldTVshow)(b), I(blackandwhite)(b) is true, I(oldTVshow)(a) and I(penguin)(b) is wrong,
Comment on This Data Unit