Relational Logic: Satisfaction and Logical Entailment

Many students struggle with Exercise 8.3. Therefore, we've provided the following exercise that presents four different variants of the Exercise 8.3 along with hints regarding the satisfiability and entailment of the supplied relational logic sentences. Our hope is that after trying out and / or seeing the answers of this exercise, the students can better understand the relationship and the differences between consistency (also called satisfiable) and logical entailment of sentences.

You can access the four variants of Exercise 8.3 by choosing the appropriate option from the following dropdown menu. By default, Variant 1 is loaded.

Let's suppose that our vocabulary consists of the object constants:a, b and c and the binary relation constantsp and r. The p relation is axiomatized below.

¬p(a,a)

p(a,b)

¬p(a,c)

¬p(b,a)

¬p(b,b)

p(b,c)

¬p(c,a)

¬p(c,b)

¬p(c,c)

Consider the following sentence about r.

Say whether each of the following sentences is (a) consistent with the above sentence about r, and (b) logically entailed by the above sentence about r.

Sentence \ Property:

Consistent?

Logically Entailed?

r(a, b)

r(b, c)

r(a, c)

r(a, a)

r(b, b)

r(c, c)

r(b, a)

r(c, a)

r(c, b)

Hints

1. Since, the sentence about r contains r(a, b) ∧ r(b, c) as a conjunct, the sentences r(a, b) and r(b, c) are both consistent and logically entailed by the sentence about r.

2. Consider a truth assignment where all the ground terms except r(a, b) and r(b, c) are assigned the value 0.

3. Consider a truth assignment where all the ground terms are assigned the value 1.

Hints

1. Since, the sentence about r contains r(a, b) ∧ r(b, c) as a conjunct, the sentences r(a, b) and r(b, c) are both consistent and logically entailed by the sentence about r. Same holds for the sentence r(a, c). To see why, substitute x = a, y = b, and z = c in ∃y.(r(x, y) ∧ r(y, z)).

2. Consider a truth assignment where all the ground terms except r(a, b), r(b, c), and r(a, c) are assigned the value 0.

3. Consider a truth assignment where all the ground terms are assigned the value 1.

Hints

1. Since, the sentence about r contains r(a, b) ∧ r(b, c) as a conjunct, the sentences r(a, b) and r(b, c) are both consistent and logically entailed by the sentence about r. Same holds for the sentence r(a, c). To see why, substitute x = a, y = b, and z = c in ∃y.(r(x, y) ∧ r(y, z)).

2. Since, the sentence about r contains ∀x.¬r(x, x) as a conjunct, the sentences ¬r(a, a), ¬r(b, b), and ¬r(c, c) are both consistent and logically entailed by the sentence about r.

3. If ¬r(a, a) is logically entailed, can r(b, a) be true in any truth assignment? Recall that from (1), we have r(a, b) to be logically entailed i.e. true in any truth assignment that satisfies the supplied sentence about r. Try to reason similarly about r(c, a) and r(c, b).

Hint

What happens when there is a contradiction i.e. there exists a inconsistent set of sentences?

Reference:What is consistency? What is logical entailment?

A sentence φ is consistent with a set of sentences Δ if and only if there exists a truth assignment that satisfies all the sentences in Δ ∪ {φ}. To show that a sentence is consistent with a supplied set of sentences, it suffices to find one truth assignment that satisfies all the supplied sentences.

A sentence φ is logically entailed by a set of sentences Δ if and only if all the truth assignments that satisfy the sentences in Δ, also satisfy φ.