
Introduction to Logic

Tools for Thought

Truth tables and semantic trees are good ways of explicitly representing multiple models for a set of sentences. In some cases, there is just one model.
In this approach, we write out an empty table for each relation and then fill in values based on the constraints of the problem. For example, for any unit constraint, we can immediately enter the corresponding truth value in the appropriate box. Given these partial assignments, we then simplify the constraints (as in the semantic trees method), possibly leading to new unit constraints. We continue until there are no more unit constraints.

As an example, consider the Sorority problem introduced in Chapter 1. We are given the constraints shown below, and we want to know whether Dana likes everyone that Bess likes. In other words, we want to confirm that, in every model that satisfies these sentences, Dana likes everyone that Bess likes.
Dana likes Cody. 
Abby does not like Dana. 
Dana does not like Abby. 
Abby likes everyone that Bess likes. 
Bess likes Cody or Dana. 
Abby and Dana both dislike Bess. 
Cody likes everyone who likes her. 
Nobody likes herself. 

In this particular case, it turns out that there is just one model that satisfies all of these sentences. The first step in creating this model is to create an empty table for the likes relation.

Abby 
Bess 
Cody 
Dana 
Abby 




Bess 




Cody 




Dana 





The data we are given has three units  the fact that Dana likes Cody and the facts that Abby does not like Dana and Dana does not like Abby. Using this information we can refine our model by putting a one into the third box in the fourth row and putting zeros in the fourth box of the first row and the first box of the fourth row.

Abby 
Bess 
Cody 
Dana 
Abby 
 

0 
Bess 




Cody 




Dana 
0
 
1 


Now, we know that Abby likes everyone that Bess likes. If Bess likes Dana, then we could conclude that Abby likes Dana as well. We already know that Abby does not like Dana, so Bess must not like Dana either.

Abby 
Bess 
Cody 
Dana 
Abby 
 

0 
Bess 


 0

Cody 




Dana 
0
 
1 


At the same time, we know that Bess likes Cody or Dana. Since Bess does not like Dana, she must like Cody. Once again using the fact that Abby likes everyone whom Bess likes, we know that Abby also likes Cody.

Abby 
Bess 
Cody 
Dana 
Abby 
 
1 
0 
Bess 

 1
 0

Cody 




Dana 
0
 
1 


Abby and Dana both dislike Bess. Using this fact we can add 0s to the first and last cells of the second column.

Abby 
Bess 
Cody 
Dana 
Abby 
 0 
1 
0 
Bess 

 1
 0

Cody 




Dana 
0
 0 
1 


On the other hand, Cody likes everyone who likes her. This allows us to put a 1 in every column of the third row where there is a 1 in the corresponding rows of the third column.

Abby 
Bess 
Cody 
Dana 
Abby 
 0 
1 
0 
Bess 

 1
 0

Cody 
1
 1

 1

Dana 
0
 0 
1 


Since nobody likes herself, we can put a 0 in each cell on the diagonal.

Abby 
Bess 
Cody 
Dana 
Abby 
0
 0 
1 
0 
Bess 
 0
 1
 0

Cody 
1
 1
 0
 1

Dana 
0
 0 
1 
0 

Finally, using the fact that Abby likes everyone that Bess likes, we conclude that Bess does not like Abby. (If she did then Abby would like herself, and we know that that is false.) At this point, we have a complete model, and we can check our conclusion to see that this model satisfies the desired conclusion. In this case, it is easy to see that Dana indeed does like everyone that Bess likes.

Abby 
Bess 
Cody 
Dana 
Abby 
0
 0 
1 
0 
Bess 
0
 0 
1 
0 
Cody 
1
 1 
0 
1 
Dana 
0
 0 
1 
0 

We motivated this method by talking about cases where the given sentences have a unique model, as in this case. However, the method can also be of value even when there are multiple possible models. For example, if we had left out the belief that Cody likes everyone who likes her, we would still have eight models (corresponding to the eight possible combinations of feelings Cody has for Abby, Bess, and Dana). Yet, even with this ambiguity, it would be possible to determine whether Dana likes everyone Bess likes using just the portion of the table already filled in.

Use the arrow keys to navigate.
