

Introduction to Logic

Tools for Thought


The semantics of Relational Logic presented here is termed Herbrand semantics. It is named after the logician Herbrand, who developed some of its key concepts. As Herbrand is French, it should properly be pronounced "airbrahn". However, most people resort to the Anglicization of this, instead pronouncing it "herbrand". (One exception is Stanley Peters, who has been known at times to pronounce it "harebrained".)

The Herbrand base for a vocabulary is the set of all ground relational sentences that can be formed from the constants of the language. Said another way, it is the set of all sentences of the form r(t_{1},...,t_{n}), where r is an nary relation constant and t_{1}, ... , t_{n} are object constants.
For a vocabulary with object constants a and b and relation constants p and q where p has arity 1 and q has arity 2, the Herbrand base is shown below.
{p(a), p(b), q(a,a), q(a,b), q(b,a), q(b,b)}
It is worthwhile to note that, for a given relation constant and a finite set of object constants, there is an upper bound on the number of ground relational sentences that can be formed using that relation constant. In particular, for a set of object constants of size b, there are b^{n} distinct ntuples of object constants; and hence there are b^{n} ground relational sentences for each nary relation constant. Since the number of relation constants in a vocabulary is finite, this means that the Herbrand base is also finite.

A truth assignment for a Relational Logic language is a function that maps each ground relational sentence in the Herbrand base to a truth value. As in Propositional Logic, we use the digit 1 as a synonym for true and 0 as a synonym for false. For example, the truth assignment defined below is an example for the case of the language mentioned earlier.
p(a)  →  1 
p(b)  →  0 
q(a,a)  →  1 
q(a,b)  →  0 
q(b,a)  →  1 
q(b,b)  →  0 

As with Propositional Logic, once we have a truth assignment for the ground relational sentences of a language, the semantics of our operators prescribes a unique extension of that assignment to the complex sentences of the language.

The rules for logical sentences in Relational Logic are the same as those for logical sentences in Propositional Logic. A truth assignment satisfies a negation ¬φ if and only if it does not satisfy φ. A truth assignment satisfies a conjunction (φ_{1} ∧ ... ∧ φ_{n}) if and only if it satisfies every φ_{i}. A truth assignment satisfies a disjunction (φ_{1} ∨ ... ∨ φ_{n}) if and only if it satisfies at least one φ_{i}. A truth assignment satisfies an implication (φ ⇒ ψ) if and only if it does not satisfy φ or does satisfy ψ. A truth assignment satisfies an equivalence (φ ⇔ ψ) if and only if it satisfies both φ and ψ or it satisfies neither φ nor ψ.

In order to define satisfaction of quantified sentences, we need the notion of instances. An instance of an expression is an expression in which all free variables have been consistently replaced by ground terms. Consistent replacement here means that, if one occurrence of a variable is replaced by a ground term, then all occurrences of that variable are replaced by the same ground term.

A universally quantified sentence is true for a truth assignment if and only if every instance of the scope of the quantified sentence is true for that assignment. An existentially quantified sentence is true for a truth assignment if and only if some instance of the scope of the quantified sentence is true for that assignment.

A truth assignment satisfies a sentence with free variables if and only if it satisfies every instance of that sentence.
A truth assignment satisfies a set of sentences if and only if it satisfies every sentence in the set.

Use the arrow keys to navigate.
Press the escape key to toggle all / one.

