Logic for Computer Science/Applications

From Wikibooks, open books for an open world
< Logic for Computer Science
Jump to navigation Jump to search

In the following we briefly consider some applied problems where the expressibility of languages matter. It easily becomes clear that FO is not sufficient for many cases. For overcoming the resrtrictions of FO there exist a lot of extensions like fixed point logic, counting logics, misc flavours of second order logic etc. that are not covered in this chaper [chapter | paper].

Database Theory: SQL[edit]

Relations have named columns called attributes

   frequents |  drinker  bar
   serves    |  bar  beer
   likes     |  drinker  beer

Standard Query Language:

Relational calculus variant of FO on relational vocabulary (no functions just relations).

Here constants have a fixed interpretation, this is slightly different than in FO logic.

Examples of relational queries:

(i) Find all bars that serve Bud

b is a free variable, Bud is a constant.

(ii) Find the drunkers [drinkers | drunkards] who frequent some bar that serves Bud

(iii) Find the drinkers who frequent only bars serving Bud

(iv) Find drinkers who frequent only bars serving some beer they like

SQL Representation of these queries:

   SELECT s.bar
   FROM serves s
   WHERE s.beer = 'Bud'

   SELECT f.drinker
   FROM freq f, serves s
   WHERE f.bar = s.bar and s.beer = 'Bud'

   SELECT drinker
   FROM freq
       SELECT f.drinker
       FROM frequents f
       WHERE f.bar NOT IN
           (SELECT bar
            FROM serves
            WHERE beer = 'Bud')

Relational Algebra

Is an alternative representation language used in SQL. What you can represent using relational algebra is absolutely the same as what you can represent in FO logic. It constitues of simple operations on relations that allow you to specify queries.

Main Operations

Projection : Project relations on a subset of its columns (attributes).

Selection : Selects a subset of tuples from a particular relation, based upon a specified selection cond ition.

, Union, Diff : similar to set operations.

|><| Join : allows you to combine tuples from two relations.

Rename : renames A to B.

Expressions built from these expressions are called a relational algebra query. Whatever you can express in algebra we can represent in FO.





Expressive Power

Graph properties correspond to properties of datastructures in relational databases (see the chapter on database queries), e.g.:

  • Consider a companies database that contains all managers together with the 'is superordinate' relation amongst them. In a proper hierachy the database should contain no circles, i.e. a manager can not be a superordinate of his superordinate. Querying this corresponds to checking a graph for cyclicity. As from above this can not be done in FO.
  • Say two managers want to find out if one of them is more powerful than the other. So the want to query the database if the number of their subordinates is equal, i.e. the cardinalities of the sets of subordinates (say, directly and indirectly) is equal. This can't be done in FO ("FO can not count"). This is the reason why SQL is extended by a counting function.
  • Consider a database of aiports and connection fligths among them. In order to query the direct reachibility of airport b from airport a we can write


Now in order to query connections with one change of plane we write

and get

for connections with zero or one change. Thus in order to extend this to reachibility (of no matter how many changes) we have to write

what is not a FO expression. So we are fine with FO for a restricted reachibility up to a certain k but not for reachibility as it appears in graph theory. In fact it can be shown that reachibility can not be queried in FO.

Descriptive Complexity Theory[edit]

As mentioned above Hamiltonicity can not be expressed in FO. So now one can think of an extension of FO in order to express this property. This can be done like

where the quantifiers on the left state the existence of the binary realations L and S that satisfy the formula on the right. The realtion isLinOrd states that L is a linear order and isSucRelOf means that S is the successor relation of L. Both can be expressed in FO. The pattern as above, second-order existential quantifiers followed by a first order formula is called existential second order logic.

Now it is well known that Hamiltonicity is a NP-complete problem and one can ask: is there a natural connection between NP and second order logic? Indeed, there is a very amazing one: existential second-order logic corresponds exactly (!) to the class of NP-complete problems! This result is known as Fagin's theorem , it has lead to the new area of descriptive complexity where complexity classes are described by means of logical formalisms.