Foundations of Logics

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)

How Logic Works

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

    1. a Set of Statements S
    2. an an Entailment Relation
  • 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.

Propositional Logic

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):

    • all atomic formulas are Propositions (all elements of Σ)
    • if φ is a Proposition, then also ¬φ
    • if φ and ψ are Propositions, then also φ∧ψ, φ∨ψ, φ→ψ, φ↔ψ
  • Priority: ¬ prior to ∧, ∨ prior to →, ↔

How to model Facts?

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.  

PL - Model-theoretic Semantics

In the Model-theoretic Semantics for Propositional Logic one has to map all Atomic Propositions to true and false.

  • Interpretations I: Mapping of all atomic propositions to {t,f}.
  • If F is a formula and I an Interpretation, then I(F) is a truth value computed from F and I via truth tables. If one has two variables and two constants one of them can be true or false or both of they can be true or false. Then one can consider what happen if one has the negations of them for instance. In the according truth table trues and false is assigned to this propositions according to the assignment of p and q. In this way one decides which interpretation is given and which truth value is assigned to a complex formula in Propositional Logic. One can prove this via truth Tables.

System Message: ERROR/3 (, line 124)

Malformed table. Bottom/header table border does not match top border.

======== ======== ====== ======= ======= ======= =======
**I(p)** **I(q)** I(⌐p)  I(p∨q)  I(p∧q)  I(p→q)  I(p↔q)
-------- -------- ------ ------- ------- ------- -------
**f**    **f**     t     f       f       t       t
**f**    **t**     t     t       f       t       f
**t**    **f**     f     t       f       f       f
**t**    **t**     f     t       t       t       t
-------- -------- ------ ------- ------- ------- -------

For the model-theoretic semantic of Propositional Logic one need the Entailment Relation, and one says for example: With the Interpretation I, F is True, means that the Interpretation I is a model of Formula F. Then one can state that I entails the Formula F. This entails that the Formula F means it is true. Then this Interpretation of I is a Model of F. The Rules for the Semantics are simple. I is a model not φ, only then if I is not a model of φ. Also I is only a Model of (φ∧ψ), if I is a model of φ and I is also as well a model of ψ.

Then some basic Concepts are defined such as Tautology which is an Assertion or Proposition that is always True. Satisfiable means there is a satisfiable Assignment of Variables that a Statement/complex Statement is True. On the other hand a Statement can also be Refutable, which means that there is an Assignment that is not true for that complex Statement. Unsatisfiable means that there does not exists any Assignment that a given complex Statement is satisfiable, i.e. it is a Contradiction.

* We write **I ⊨ F**, if **I(F) = w**,

  and call Interpretation I a **Model** of formula F.

* Rules of Semantics:

  - I is model of ¬φ, if I is not a model of φ
  - I is model of (φ∧ψ), if I is a model of φ AND of ψ

* Basic Concepts

  - Tautology: All Interpretations are True
  - Satisfiable: Some Interpretations are True
  - Refutable: Not all Interpretations are True
  - Unsatisfiable (Contradiction): Not Interpretation is True

First Order Logic
In First Order Logic, in addition to the Logical connectives we have Quantifiers. First Order Logic has the possibility to Assertions and Statements about Sets of Things without naming these Things or without naming the individual Things. For these we have the Quantifiers: The Existential and Universal Quantification. Then in First Order Logic one as Variables (written in Capital Letters), then one has Constants and Functions. For those Functions one has also an ``Arity`` which is the number of Arguments given. Further one has Relations and Predicates.

One can form complex Statements, for example: For all Variables X there exists a Variable Y where the Predicate p of X and not of f of X and Y implies r of X.

Although it is pretty complicated to read, it is understandable by a machine, i.e. it can be interpreted correctly by a machine.

========== ==================== ===================

System Message: WARNING/2 (, line 162)

Blank line required after table.

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)),
  • "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.

  • Structure: - Definition of a domain D. - Constant Symbols are mapped to Elements of D. - Function Symbols are mapped to Functions of D. - Relation Symbols are mapped to Relations of D.
  • Then: - Assertions will become Elements of D. - Relation Symbols with Arguments will become true or false. - Logical connectives and quantifiers are treated likewise.

FOL - Model-theoretic Semantics

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) )
  • Interpretation I:

    • Domain: a set M, containing elements a,b.
    • ... no constant of function symbols ...
    • We show: the formula is refutable (i.e. it is not a Tautolgy)
    • If
    I(penguin)(a), I(blackandwite)(a), I(oldTVshow)(b),
    I(blackandwhite)(b) is true,
    I(oldTVshow)(a) and I(penguin)(b) is wrong,

Tags: logic, semantics, foundations
Categories: News, reST
Parent: Logic

Update entry (Admin) | See changes

Comment on This Data Unit