Browse course

Tutorial 8. FOL

Exercise sheet
Decoding FOL

Paraphrase the following FOL formulas in natural language:

  1. exists x (FatherOf x brotherOf jimmy Conjunction Negation FatherOf x jimmy)

  2. forall x ( Fish x Implication exists y (Fish y Conjunction BiggerThan y x ))

  3. exists x SiblingOf jimmy x Implication exists x( SiblingOf jimmy x Conjunction forall y ( Sibling x y Implication YoungerThan y x))

  4. exists x exists y (Thief x Conjunction Thief y Conjunction Negation x = y)

Knowledge Engineering in FOL

Knowledge engineering is the complex process of developing a framework in which to encode knowledge about a specific domain. There are different approaches to this problem, but here we’ll try out an FOL-based approach.

The problem we’re tackling is to represent information about a given setup using FOL formulas. The first step on the approach is to decide on a suitable vocabulary. Since we’re working with FOL languages, this means that we need to pick suitable constants, function symbols, and predicates to represent the information. Picking the right vocabulary is crucial for success when dealing with a knowledge engineering problem: choosing the wrong vocabulary can make representations clunky and hard to work with, even if—in some sense—still correct.

Picking the right language is closely related to finding a suitable ontology for the problem. That is, we need to say which objects exist in the information, which functions and properties are at play. We also need to answer questions like whether we can reduce some properties to others do have a simpler language. For example, should we have a separate predicate for Uncle² or should we define it using Male¹, Sibling², and Parent², where rather than Uncle x y we use:

Male y Conjunction exists z (Parent z x Conjunction Sibling y z)

Uncle x y is much simpler, but the previous formula contains more information. There is a trade-off that needs to be weighed carefully for every proposed knowledge engineering solution.

The second step in FOL knowledge engineering is to take the given information and to encode it with FOL formulas. Here, the main challenge is adequacy: we need to find formulas whose FOL truth-conditions resemble the given information as closely as possible, while remaining within the confines of FOL.

For a concrete knowledge engineering problem, lets consider the following marketing information about IA   provided by its developer:

Our IA  is the top-of-the-line AI system from AI-Labs. It is a hybrid system that has both symbolic and sub-symbolic sub-routines. This means that IA  is both capable of carrying out all traditional reasoning tasks, such as natural deduction or SAT solving, as well as different learned tasks, such as image and voice recognition. This is in contrast to its predecessor model KnowIt∀, which only had symbolic routines and could only carry out reasoning tasks. It also makes IA superior to the competition’s model, DeepL, which is a purely sub-symbolic AI-system and while able to carry out all learned tasks, can only carry out some simple reasoning tasks.

  1. Devise a suitable FOL language for encoding the information about the three AI-systems. Justify your design choices.

  2. Encode as much information as possible from the advert as FOL formulas. Is there information you chose not to include? If so, why?

  3. It’s a bad idea to include a function symbol makerOf in this language. Explain why.

Knowledge Representation with FOL Models

For this exercise, we are working with an FOL language with the following vocabulary:

  • Constants: jimmy, linus, sir, sir,lady, gran, ny, london, soccer

  • Predicates: Loves², IsFrom², ParentOf², LivesIn²

Now consider the following facts about our protagonist, little Jimmy:

Little Jimmy and his brother, Linus, are the children of Mr Sir and Lady Dame. They family lives in New York, where Lady Dame is from. But both Jimmy and his brother were born in London, where their father is from. The children’s paternal grandmother is Granny Smith, who still lives in London, where she was born. The children and their grandmother love soccer, unlike their parents.

  1. Represent the information as a FOL model. Specify the model in set-theoretic terms, as a knowledge graph, and in table form. Make sure to include the information about which constant denotes which object.

  2. Go to https://www.db-fiddle.com/ and, taking the code from the textbook as a template, create a SQL database that contains the information about the model. Make sure to select SQLite v3.46 on the top left for the language, otherwise the code won’t run. Verify your code by running a query that prints all tables.

  3. In logic, there is the concept of a diagram , which is, essentially, the idea of collecting all the true atomic sentences and true negations of atomic sentences in the model. The positive diagram is the set of only the true atomic sentences, without the true negated ones. Determine the positive diagram of the model we’ve just described. Is this essentially different from any of the other methods of representing the model?

Denotation

Suppose that we’re working with an FOL language that has the single constant null, as well as the function symbols succ¹ and prod².

Consider the model whose domain D = { 0, 1, 2, … } is the set of natural numbers and where:

  • Left semantic bracket null Right semantic bracket = 0
  • Left semantic bracket succ Right semantic bracket is defined by the equation Left semantic bracket succ Right semantic bracket (n) = n + 1 for all n Element { 0 , 1, 2, … }.
  • Left semantic bracket prod Right semantic bracket is defined by the equation Left semantic bracket prod Right semantic bracket (n,m) = n × m for all n, m Element { 0 , 1, 2, … }.

In this model, determine:

Left semantic bracket prod succ null prod succ succ 0 succ 0 Right semantic bracket

For this purpose:

  1. Parse the expression according to the grammar for FOL terms.

  2. Recursively calculate the values of each term, following the terms parsing tree.

Satisfaction

In the model you’ve characterized in exercise 3, determine the extensions of the following open formulas. Give them in table form:

  1. Loves x soccer Conjunction IsFrom x ny

  2. IsFrom x y Conjunction ParentOf x sir

  3. exists y ParentOf y x Conjunction exists z ParentOf z y

  4. IsFrom x y Conjunction LivesIn x y

SQL Queries  

We’ve mentioned that there is a one-to-one correspondence between SQL queries. In this exercise, we’ll explore this connection a bit more.

We return to our country DB from the textbook. You can open it again under db-fiddle .

I should preface this that what we’re doing here is not great SQL practice. We’re writing code that might seem unnatural in SQL and there certainly are better ways to code the queries. The point here is to get the idea of the correspondence across and then worry about learning to code “clean” SQL later (if you want to).

So: SQL is a rich and powerful language of domain-specific languages, and there are much easier ways to make some of these queries.

With this disclaimer out of the way, the starting point for our discussion of the relation between DB queries and open FOL formulas was the observation the SQL query

SQL_Logo 
1
2
3

SELECT country
FROM LocatedIn
WHERE continent = 'Europe';

directly corresponds to the open formula:

LocatedIn x Europe

This correspondence consists in the fact that the table returned by the query is precisely the extension of the formula. To begin with, let’s see if you can formula queries that correspond to other atoms:

  1. Write SQL queries that correspond to to the following atomic open formulas:

    • LanguageOf UnitedStates x
    • LocatedIn Japan x
    • LocatedIn x x

Verify your results using the df-fiddle.

We form complex formulas using the logical operators. These syntactic operations are mirrored by operations on the queries.

Let’s talk about the negation operator Negation first. To negate our atomic query for LocatedIn(x,Europe), we’d use the WHERE NOT EXISTS sub-query, such that

SQL_Logo 
1
2
3

SELECT country
FROM LocatedIn
WHERE continent = 'Europe';

becomes

SQL_Logo 
1
2
3
4
5
6
7
8

SELECT country
FROM CapitalOf
WHERE NOT EXISTS (
  SELECT *
  FROM LocatedIn
  WHERE LocatedIn.country = CapitalOf.country
    AND continent = 'Europe'
);

So, the idea is that we can look for the countries from the CapitalOf table, for which the query corresponding to our unnegated query doesn’t return any value. Note that this assumes that all countries occur in the CapitalOf and in the LocatedIn table. If that’s not the case, we’d need a domain table, but that’s another story.

To test the understanding of this:

  1. Write SQL queries that correspond to to the following negations:

    • Negation LanguageOf UnitedStates x
    • Negation LocatedIn Japan x
    • Negation LocatedIn x x

To conclude our little journey into queries as FOL formulas, let’s talk about conjunction. One approach to form the conjunction is to make sub-queries for each conjunct as follows:

SQL_Logo 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

SELECT country
FROM CapitalOf AS c
WHERE EXISTS (
  SELECT *
  FROM LocatedIn
  WHERE LocatedIn.country = c.country
    AND continent = 'Europe'
)
AND EXISTS (
  SELECT *
  FROM CapitalOf
  WHERE CapitalOf.country = c.country
    AND capital = 'Amsterdam'
);

The only thing to watch out for here is that we need to coordinate the variables across the sub-queries. This is what the FROM CapitalOf AS c and later c.country syntax does. Let’s see if you can apply this:

  1. Write SQL queries that correspond to to the following conjunctions:

    • LocatedIn x Europe Conjunction Negation LanguageOf x Dutch
    • Negation LocatedIn Japan x Conjunction Negation CaptailOf x WashingtonDC

We can go on from here and cover disjunction, conditionals, and existentials, but I hope that the sub-pattern strategy pattern has become clear. This is one way to obtain SQL queries for ever FOL formula. There is much more to be said about this, but let’s leave it here.

As a final brain teaser:

  1. Write SQL queries that corresponds to LocatedIn x Europe Disjunction LanguageOf x English using only the patterns for Negation and Conjunction we’ve already discussed.
Solution

  1. Here’s a list of queries that work:

    • LanguageOf UnitedStates x

      SQL_Logo 
      1
2
3

      SELECT language
FROM LanguageOf
WHERE country = 'United States';

    • LocatedIn Japan x

      SQL_Logo 
      1
2
3

      SELECT continent
FROM LocatedIn
WHERE country = 'Japan';

    • LocatedIn x x

      SQL_Logo 
      1
2
3

      SELECT country, continent
FROM LocatedIn
WHERE country = continent;

  2. Here we go:

    • Negation LanguageOf UnitedStates x

      SQL_Logo 
      1
2
3
4
5
6
7
8

      SELECT language
FROM Language
WHERE NOT EXISTS (
  SELECT *
  FROM Language
  WHERE country = 'United States'
    AND Language.language = language
);

    • Negation LocatedIn Japan x

      SQL_Logo 
      1
2
3
4
5
6
7
8

      SELECT DISTINCT continent
FROM LocatedIn
WHERE NOT EXISTS (
  SELECT *
  FROM LocatedIn
  WHERE country = 'Japan'
    AND LocatedIn.continent = continent
);

    • Negation LocatedIn x x

      SQL_Logo 
      1
2
3
4
5
6
7
8

      SELECT continent
FROM LocatedIn
WHERE NOT EXISTS (
  SELECT *
  FROM LocatedIn
  WHERE country = 'Japan'
    AND LocatedIn.continent = continent
);

  3. And the last

    • LocatedIn x Europe Conjunction Negation LanguageOf x Dutch

      SQL_Logo 
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

      SELECT country
FROM CapitalOf AS outer
WHERE
  -- LocatedIn(x, 'Europe')
  EXISTS (
    SELECT *
    FROM LocatedIn
    WHERE country = outer.country
      AND continent = 'Europe'
  )
  -- ¬Language(x, 'Dutch')
  AND NOT EXISTS (
    SELECT *
    FROM LanguageOf
    WHERE country = outer.country
      AND language = 'Dutch'
  );

    • Negation LocatedIn Japan x Conjunction Negation CaptailOf x WashingtonDC

      SQL_Logo 
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

      SELECT country
FROM CapitalOf AS outer
WHERE
  -- ¬ LocatedIn Japan x
  NOT EXISTS (
    SELECT *
    FROM LocatedIn
    WHERE country = 'Japan'
      AND continent = outer.country     
  )
  -- ¬CapitalOf x Washington D.C.
  AND NOT EXISTS (
    SELECT *
    FROM CapitalOf
    WHERE country = outer.country
      AND capital = 'Washington D.C.'
  );

  4. Here we go:

SQL_Logo 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

SELECT country
FROM CapitalOf AS outer
WHERE NOT (
    NOT EXISTS (
      SELECT *
      FROM LocatedIn
      WHERE country = outer.country
        AND continent = 'Europe'
    )
    AND
    NOT EXISTS (
      SELECT *
      FROM LanguageOf
      WHERE country = outer.country
        AND language = 'English'
    )
);

A much simpler code uses OR, but that wasn’t the question:

SQL_Logo 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


SELECT country
FROM CapitalOf AS outer
WHERE
  EXISTS (
    SELECT *
    FROM LocatedIn
    WHERE country = outer.country
      AND continent = 'Europe'
  )
  OR
  EXISTS (
    SELECT *
    FROM LanguageOf
    WHERE country = outer.country
      AND language = 'English'
  );