Computational Thinking (CO2412) Tutorial 4.7: Week 24

This worksheet deals with first-order logic, the most powerful kind of logic discussed in our module. Some of the questions below will require thorough attention and work to familiarize yourselves with the concepts and the notation from first-order logic. Also confer the literature: The book by Erciyes is a good source for beginners.

First, make sure that you understand how predicates work (see also Problem 4.6.3) and how the universal quantifier ∀ ("for all") and the existential quantifier ∃ ("there is") are used in first-order logic:

For the variables to which quantifiers are applied, the possible values are taken from what is referred to as the domain of quantification (or just the domain). Every model comes with a domain; e.g., if the model is visualized as a knowledge graph, the domain often consists of the nodes and node labels, or it consists of the nodes only. The domain might also consist of words in a language, numbers from a certain set (e.g., natural numbers), and similar.

Then, "∀x …" translates to "for all values from the domain of quantification, if assigned to x, …," and "∃x …" translates to "for at least one value from the domain of quantification, if assigned to x, …"

4.7.1 From human language to FO logic

Assume that we are making statements about directed graphs using the binary predicate edge(), with edge(v, w) to be understood as "there is an edge from the vertex v to the vertex w."

Accordingly, the human-language expression "every node in the graph can be reached from every node by a path that consists of two edges" can be expressed by the first-order logic statement:

S0 = ∀x ∀y ∃z (edge(x, z) ∧ (edge(z, y)).

  1. Statement S0 more literally translates to "for all x, for all y, there is a z such that there is an edge from x to z and an edge from z to y." Make sure that you understand exactly why the given logical statement is an equivalent expression of the given human-language statement.
  2. Formulate a first-order logic statement S1 with the meaning: "Every node has at least one outgoing edge."
  3. Formulate a first-order logic statement S2 ≡ ¬S1 with the meaning: "There is a node with outdegree zero."
  4. How about S3 = ∀x ∃z ∀y (edge(x, z) ∧ (edge(z, y)): Does it have the same meaning as S0? Why - or why not?
  5. For the present examples, what is the domain of quantification?

4.7.2 From FO logic to human language

Consider the following three first-order logic statements which use a binary predicate greater_than(), with greater_than(v, w) to be understood as "the value v is greater than the value w."

S4 = ¬∃x ∃y (greater_than(x, y) ∧ greater_than(y, x))

S5 = ∀x ∀y ∀z ((greater_than(x, y) ∧ greater_than(y, z)) → greater_than(x, z))

S6 = ∀x ∃y greater_than(y, x)

  1. Statement S4 could be translated into human language as "there are no x and y such that x is greater than y, while y is also greater than x." Make sure that you understand how the first-order logic statement and its equivalent in human language correspond to each other.
  2. What is the meaning of S5 and S6, respectively, in human language?
  3. Think of a joint model of S4, S5, and S6. That is, a case where S4, S5, and S6 are all True. For your example model, what would be the domain of quantification?

4.7.3 Satisfiability

Are the following statements satisfiable? (Defined just like for propositional logic: Can they become True? Do they have a model?)

  1. S7 = ∃x ∃y ∃z (R(x, y) ∧ R(y, z) ∧ ¬R(x, z))
  2. S8 = ∃x (P(x) ∧ Q(x)) ∧ ∀x (¬P(x) ∨ ¬Q(x))
  3. S9 = ∃x (P(x) ∧ Q(x)) ∧ ∀y (¬P(y) ∨ ¬Q(y))
  4. S10 = ¬∀x ∀y (P(x) → (R(x, y) ∨ P(x)))

Above, P(), Q(), and R() are predicates.

4.7.4 Entailment

For first-order logic, entailment is defined in the same way as for propositional logic: Premises entail a conclusion if all the joint models of all the premises are also models of the conclusion. In other words, whenever all the premises become True, the conclusion must also be True. Here, consider the axioms S4, S5, and S6 from Problem 4.7.2 as premises.

  1. Do the premises entail S11 = ∀x ∀y (greater_than(x, y) → ∃z (greater_than(x, z) ∧ greater_than(z, y)))? In other words, does S4, S5, S6 ⊨ S11 hold? Why - or why not?
  2. Do the premises entail S12 = ∀x ¬greater_than(x, x)? In other words, does S4, S5, S6 ⊨ S12 hold? Why - or why not?

This worksheet will be discussed in the 29th March 2022 lecture. If you are interested in feedback on your work, send an email to Oliver Kerr and Martin Horsch.