[Part 7] Raymond Smullyan's Certified Knights and Knaves puzzles Building truth tables in JavaScript

In the previous post, I promised to write a JavaScript program to find formulas that satisfy a given truth table.

Before we can write such a program, we need to understand how to build truth tables in JavaScript.

This post is thus devoted to a discussion of the tools that JavaScript (and similar programming languages) provides to manipulate truth tables and perform Boolean logic operations.

First, it is common to represent the Boolean constants True and False with the integer values 1 and 0, respectively.

Here are two variables declarations that implement this approach in JavaScript:

var True = 1;
var False = 0;

Second, many programming languages include operators that behave like connectives in Boolean logic, such as:

• the & operator for logical conjunction (AND)
• the | operator for logical disjunction (OR)
• the ^ operator for exclusive disjunction (XOR)

Here is a Javascript code sample, in which the function call

 console.log( <expression> );

evaluates <expression> and then prints its value in the console window:

console.log( False & False );    // outputs 0, i.e., False
console.log( False & True );     // outputs 0, i.e., False
console.log( True & False );     // outputs 0, i.e., False
console.log( True & True );      // outputs 1, i.e., True

console.log( False | False );    // outputs 0, i.e., False
console.log( False | True );     // outputs 1, i.e., True
console.log( True | False );     // outputs 1, i.e., True
console.log( True | True );      // outputs 1, i.e., True

console.log( False ^ False );    // outputs 0, i.e., False
console.log( False ^ True );     // outputs 1, i.e., True
console.log( True ^ False );     // outputs 1, i.e., True
console.log( True ^ True );      // outputs 0, i.e., False

The case of negation is a bit tricky and will be discussed later.

Of course, in the code sample above, we did not need to declare the variables True and False; we could have used the numbers 0 and 1 directly, like this:

console.log( 0 & 0 );    // outputs 0
console.log( 0 & 1 );    // outputs 0
console.log( 1 & 0 );    // outputs 0
console.log( 1 & 1 );    // outputs 1

console.log( 0 | 0 );    // outputs 0
console.log( 0 | 1 );    // outputs 1
console.log( 1 | 0 );    // outputs 1
console.log( 1 | 1 );    // outputs 1

console.log( 0 ^ 0 );    // outputs 0
console.log( 0 ^ 1 );    // outputs 1
console.log( 1 ^ 0 );    // outputs 1
console.log( 1 ^ 1 );    // outputs 0

As it turns out, the Boolean logic operators in JavaScript are more powerful than we have shown so far.

This is because each integer value they operate on is first converted to a 32-bit string that is the binary encoding of the integer value (read about the binary number system).

So the number 0 is converted to a string of thirty-two 0s, while the number 1 is converted to a string of thirty-one 0s followed by one 1.

In JavaScript, the function call:

 parseInt( <binary string> , 2 );

returns the integer value of the given binary string. In other words, it converts a binary string to its equivalent (decimal) integer value.

Here are some examples:

// the next line outputs: 0
console.log( parseInt("00000000000000000000000000000000", 2) );
// the next line outputs: 1
console.log( parseInt("00000000000000000000000000000001", 2) );
// the next line outputs: 2
console.log( parseInt("00000000000000000000000000000010", 2) );
// the next line outputs: 4
console.log( parseInt("00000000000000000000000000000100", 2) );
// the next line outputs: 8
console.log( parseInt("00000000000000000000000000001000", 2) );
// the next line outputs: 9
console.log( parseInt("00000000000000000000000000001001", 2) );
// the next line outputs: 65535
console.log( parseInt("00000000000000001111111111111111", 2) );

Note that the last binary string above contains sixteen 0s followed by sixteen 1s. Since the leading zeros do not affect the value of the binary number (the same way that the decimal number 000314 is equal to 314), the largest number that can be represented with 16 bits (i.e., when they are all equal to 1) is 65535. We will use this fact later on.

Now, the reason I said that Boolean logic operators in JavaScript are more powerful than we have shown so far is because they are really bitwise operators.

This means that, given two integers m and n (i.e., internally, two strings of 32 bits each), they perform their operation in parallel on each one of the 32 pairs of matching bits in m and n. 

For example, the operation 8 | 1 is performed on the corresponding bits strings, namely:

  00000000000000000000000000001000
| 00000000000000000000000000000001
----------------------------------
  00000000000000000000000000001001

and is thus equal to 9, whereas  8 & 9 becomes:

  00000000000000000000000000001000
& 00000000000000000000000000001001
----------------------------------
  00000000000000000000000000001000

and is equal to 8.

Indeed, if you execute the following JavaScript code, you will get the promised output:

console.log( 8 | 1 )  // outputs 9
console.log( 8 & 9 )  // outputs 8

Now, back to our sixth puzzle!

Remember that we built the following truth table for this puzzle:

\(A\)	\(Ac\)	\(B\)	\(Bc\)	\(\varphi = (A \leftrightarrow \varphi_A)\ \&\ (B \leftrightarrow \varphi_B)\)
\(F\)	\(F\)	\(F\)	\(F\)	\(F\)
\(F\)	\(F\)	\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(T\)	\(F\)	\(T\)	only B
\(F\)	\(F\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(F\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	only B
\(F\)	\(T\)	\(T\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(F\)	\(T\)	only A
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	only A
\(T\)	\(F\)	\(T\)	\(F\)	\(T\)	both A and B
\(T\)	\(F\)	\(T\)	\(T\)	\(T\)	only A
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)
\(T\)	\(T\)	\(F\)	\(T\)	\(F\)
\(T\)	\(T\)	\(T\)	\(F\)	\(T\)	only B
\(T\)	\(T\)	\(T\)	\(T\)	\(F\)

We can now represent each column of this table, that is, a sequence of 16 truth values, with a string of 16 bits in which each bit value 0 or 1 represents the value False or True, respectively.
For example, we can represent the four leftmost columns of this table with four numbers in JavaScript as follows:

var A  = parseInt("0000000011111111",2);     // A  = 255
var Ac = parseInt("0000111100001111",2);     // Ac = 3855 
var B  = parseInt("0011001100110011",2);     // B  = 13107
var Bc = parseInt("0101010101010101",2),;    // Bc = 21845

Note that the name of each column becomes the name of the integer value representing that column. Also, the decimal values listed on the right are not important for solving the puzzle.

Observe that the values listed from top to bottom in each column of the truth table are listed from left to right in the corresponding bit string. This is an arbitrary convention but it must be applied consistently so that the bits (that is, the rows) match up correctly when performing Boolean operations.

For example, we can compute the logical AND of the first two columns in a single operation by computing the value of A & Ac.

In fact, we will define new functions with explicit names, namely, AND, OR, and XOR, so you do not have to overload your brain with recalling the meaning of the &, |, and ^ operators:

function AND(x,y) { return x & y; };
function OR(x,y)  { return x | y; };
function XOR(x,y) { return x ^ y; };

Now, to compute the values in the column corresponding to the formula A & Ac, you could simply type:

console.log( AND(A,Ac) );

For convenience, we will also define variables corresponding to the types of rows (white, green, red, and blue) in the truth table. 

More specifically, we will create a variable called onlyA, which corresponds to a column that contains a 1 (True) in each green row and a 0 (False) in all other rows.

Similarly, we define the variables onlyB, both, and none, corresponding to the red, blue, and white rows, respectively:

var onlyA = parseInt("0000000011010000",2);    
var onlyB = parseInt("0010001000000010",2);
var both  = parseInt("0000000000100000",2);
var none  = parseInt("1101110100001101",2);

Before we can program the algorithm we'll use to solve the puzzle, we will also need to handle:

• logical negation and 
• the biconditional connective.

In JavaScript, the ~ operator performs the bitwise logical negation (that is, replaces each 0 with 1, and vice versa) of its integer argument.

Here, we need to remember that each argument to a Boolean operator is converted to a thirty-two bit string.

For example, the value 1 becomes:

00000000000000000000000000000001

Therefore, ~1 is equal to:

11111111111111111111111111111110

which is NOT equal to 0.

[In fact, this binary string (like all binary strings that start with a 1) represents a negative number. You can read more about the so-called two's complement representation; but that topic is not relevant for our discussion of the puzzle.]

What we need to keep in mind is that all of the values to which we apply Boolean operations in JavaScript contain 32 bits.

In contrast, our truth table contains only 16 rows. So, when we wrote:

var A  = parseInt("0000000011111111",2);     // A  = 255

we only gave the 16 least significant (or rightmost) bits of A. We implicitly used the fact that the 16 most significant (or leftmost) bits of A were 0s.

So, every time we (logically) negate a column of our truth table, we only care about the rightmost 16 bits of the result.

For example, A defined above, internally, is really the 32-bit string:

00000000000000000000000011111111

So, ~A is the 32-bit string:

11111111111111111111111100000000

But we really only care about the 16 least significant (rightmost) bits of it.
So the NOT function is defined as follows:

function NOT(x)   { return ~x & 65535; };

which masks (that is, sets to 0) the 16 leftmost bits by performing a logical AND with the constant value that starts with sixteens 0s and ends with sixteen 1s.

Finally, the biconditional (or if-and-only-if, often abbreviated IFF) connective can be implemented as follows:

function IFF(x,y)   { return NOT( XOR(x,y) ); };

since XOR returns 1 when its two arguments are different and 0 otherwise, which is the logical negation of the behavior of the biconditional (check their truth tables if needed).

To recap, let me list here ALL of the JavaScript code that we discussed in this post and that we will use in our final program:

var     A = parseInt("0000000011111111",2);
var    Ac = parseInt("0000111100001111",2);
var     B = parseInt("0011001100110011",2);
var    Bc = parseInt("0101010101010101",2);
var onlyA = parseInt("0000000011010000",2);    
var onlyB = parseInt("0010001000000010",2);
var  both = parseInt("0000000000100000",2);
var  none = parseInt("1101110100001101",2);

function AND(x,y) { return x & y; };
function OR(x,y)  { return x | y; };
function XOR(x,y) { return x ^ y; };
function NOT(x)   { return ~x & 65535; };
function IFF(x,y) { return NOT( XOR(x,y) ); };

Now that we know how to compute truth tables in JavaScript, we can turn to the design of the algorithm for our program to solve the puzzle.

This will be the focus of the next post.