
Introduction to Logic

Tools for Thought

As defined in Lesson 6, a model in Relational Logic is an assignment of truth values to the ground atoms of our language. We treat each ground atom in our language as a variable and assign it a single truth value (1 or 0). In general, this is a good way to proceed. However, we can sometimes do better.
Consider, for example, a theory with four object constants and two unary relation constants. In this case, there would be eight elements in the Herbrand base and 2^{8} (256) possible truth assignments. Now, suppose we had the constraint that each relation is true of at most a single object. Most of these assignments would not satisfy the single value constraint and thus considering them is wasteful.

Luckily, in cases like this, there is a representation for truth assignments that allows us to eliminate such possibilities and thereby save work. Rather than treating each ground atom as a separate variable with its own Boolean value, we can think of each relation as a variable with 4 possible values. In order to analyze sentences in such a theory, we would need to consider only 4^{2} (16) possibilities.
Even if we search the entire space of assignments, this a significant saving over the pure truth table method. Moreover, we can combine this representation with the techniques described earlier to find assignments for these nonBoolean variables in an even more efficient manner.

The game of Sukoshi illustrates this technique and its benefits. (Sukoshi is similar to Sudoku, but it is smaller and simpler.) A typical Sukoshi puzzle is played on a 4x4 board. In a typical instance of Sukoshi, several of the squares are already filled, as in the example below. The goal of the game is to place the numerals 1 through 4 in the remaining squares of the board in such a way that no numeral is repeated in any row or column.

We can formalize the rules of this puzzle in the language of Logic. Once we have done that, we can use the techniques described here to find a solution.
In our formalization, we use the expression cell(1,2,3) to express the fact that the cell in the first row and the second column contains the numeral 3. For example, we can describe the initial board shown above with the following sentences.
cell(1,2,4) 
cell(1,4,1) 
cell(2,1,2) 
cell(3,4,3) 
cell(4,3,4) 

We use the expression same(x,y) to say that x is the same as y. We can axiomatize same by simply stating when it is true and where it is false. An abbreviated axiomatization is shown below.
same(1,1) 
¬same(2,1) 
¬same(3,1) 
¬same(4,1) 
¬same(1,2) 
same(2,2) 
¬same(3,2) 
¬same(4,2) 
¬same(1,3) 
¬same(2,3) 
same(3,3) 
¬same(4,3) 
¬same(1,4) 
¬same(2,4) 
¬same(3,4) 
same(3,4) 

Using this vocabulary, we can write the rules defining Sukoshi as shown below. The first sentence expresses the constraint that two cells in the same row cannot contain the same value. The second sentence expresses the constraint that two cells in that same column can contain the same value. The third constraint expresses the fact that every cell must contain at least one value.
∀x.∀y.∀z.∀w.(cell(x,y,w) ∧ cell(x,z,w) ⇒ same(y,z)) 
∀x.∀y.∀z.∀w.(cell(x,z,w) ∧ cell(y,z,w) ⇒ same(x,y)) 
∀x.∀y.∃w.cell(x,z,w) 

As a first step in solving this problem, we start by focussing on the fourth column, since two of the cells in that column are already filled. We know that there must be a 4 in one of the cells. It cannot be the first, since that cell contains a 1, and it cannot be the third since that cell contains a 3. It also cannot be the fourth, since there is already a 4 in the third cell of the fourth row. By process of elimination, the 4 must go in the fourth cell of the second row, leading to the board shown below.

At this point, there is a four in every row and every column except for the first column in the third row. So, we can safely place a four in that cell.

Since there is just one empty cell in the fourth column, we know it must be filled with the single remaining value, viz. 2. After adding this value, we have the following board.

Now, let's turn our attention to the first column. We know that there must be a 1 in one of the cells. It cannot be the first, since there is already a 1 in that row, and it cannot be the second or third since those cell already contain values. Consequently, the 1 must go in the first cell of the fourth row.

Once again, we have a column with all but one cell filled. Column 1 has a 2 in the second cell, a 4 in the third, and a 1 in the fourth. So, we can place a 3 in the first cell of that column.

At this point, we can fill in the single empty cell in the first row, leading to the following board.

And we can fill in the single empty cell in the fourth row as well.

Now, let's consider the second column. We cannot put a 2 in the second cell, since there is already a 2 in that row. Since the first and last cells are already full, the only option is to put the 2 into the third cell.

Finishing off the third row leads to the board below.

Finishing off the third column leads to the following board.

Finally, we can place a 1 in the second cell of the second row. And, with that, the board is full. We have a distinct numeral in every row and every column, as required by the rules.

Given the initial assignment in this case, it is fairly easy to find a complete assignment that satisfies the Sukoshi constraints. For other initial assignments, solving the problem is more difficult. However, the techniques described here still work to cut down on the amount of work necessary. In fact, virtually all Sukoshi puzzles can be solved using these techniques without any form of trial and error.

Use the arrow keys to navigate.
