Formal Logic/Predicate Logic/Satisfaction

← Models ↑ Predicate Logic Truth →



Satisfaction

edit

The rules for assigning truth to sentences of   should say, in effect, that

 

is true if and only if   is true of every object in the domain. There are two problems. First,   can, in general, have free variables. In particular,   will normally be free (otherwise saying "for all   …" is irrelevant). But formulae with free variables are not sentences and do not have a truth value. Second, we do not yet have a precise way of saying that   is true of every object in the domain. The solution to these problems comes in two parts:

  • assignment of objects from the domain to each of the variables,
  • specification of whether a model satisfies a formula with a particular assignment of variables.

We can then define truth in a model in terms of satisfaction.

Variable assignment

edit

Given model  , a variable assignment, denoted  , is a function assigning a member of the domain   to each variable of  . For example, if   contains natural numbers, then   applied to variable   could be  .

In addition to variable assignment, we also have the assignment of domain members to constant symbols by the model's interpretation function  . Together, we use this information to generate assignments of domain members to arbitrary terms (including, constant symbols, variables, and complex terms formed by operation letters acting on other terms). This is accomplished by an extended variable assignment, denoted  , which is defined below. Recall that the interpretation function   assigns semantic values to the operation letters and predicate letters of  .

An extended variable assignment   is a function that assigns a value from   as follows.

If   is a variable, then:
 
If   is a constant symbol (i.e., a 0-place operation letter), then:
 
If   is an n-place operation letter (n greater than 0) and   are terms, then:
 

Some examples may help. Suppose we have model   where:

 
 
 
 
 
 

On the previous page, it was noted that we want the following result:

 

We now have achieved this because we have for any   defined on  :

 
 

Suppose we also have a variable assignment   where:

 
 

Then we get:

 
 

Satisfaction

edit

A model, together with a variable assignment, can satisfy (or fail to satisfy) a formula. Then we will use the notion of satisfaction with a variable assignment to define truth of a sentence in a model. We can use the following convenient notation to say that the interpretation   satisfies (or does not satisfy)   with  .

 
 

We now define satisfaction of a formula by a model with a variable assignment. In the following, 'iff' is used to mean 'if and only if'.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 .
 
 
 .

Examples

edit

The following continue the examples used when describing extended variable assignments above. They are based on the examples of the previous page.

A model and variable assignment for examples

edit

Suppose we have model   where

 
 
 
 
 
 
 
 

Suppose further we have a variable assignment   where:

 
 
 


We already saw that both of the following resolve to 1:

 
 

Examples without quantifiers

edit

Given model  , the previous page noted the following further goals:

 
 
 
 
 
 

We are not yet ready to evaluate for truth or falsity, but we can take a step in that direction by seeing that these sentences are satisfied by   with   Indeed, the details of   will not figure in determining which of these are satisfied. Thus   satisfies (or fails to satisfy) them with any variable assignment. As we will see on the next page, that is the criterion for truth (or falsity) in  .


Corresponding to (1),

 

In particular:

 
 
 


Corresponding to (2) through (6) respectively:

 
 
 
 
 


As noted above, the details of   were not relevant to these evaluations. But for similar formulae using free variables instead of constant symbols, the details or   do become relevant. Examples based the above are:

 
 
 
 
 
 
 
 

Examples with quantifiers

edit

Given model  , the previous page also noted the following further goals:

 
 

Again, we are not yet ready to evaluate for truth or falsity, but again we can take a step in that direction by seeing that the sentence in (7) is and the sentence in (8) is not satisfied by   with  


Corresponding to (7):

 

is true if and only if at least one of the following is true:

 
 
 

The formula of (7) and (9) is satisfied by   if and only if it is satisfied by   with each of the modified variable assignments. Turn this around, and we get the formula failing to be satisfied by   if and only if it fails to be satisfied by the model with at least one of the three modified variable assignments as per (10) through (12). Similarly, (10) is true if and only if at least one of the following are true:

 
 
 

Indeed, the middle one of these is true. This is because

 

Thus (9) is true.


Corresponding to (8),

 

is true if and only if at least one of the following is true:

 
 
 

The middle of these is true if and only if at least one of the following are true:

 
 
 

Indeed, the last of these is true. This is because:

 

Thus (13) is true.