Friday, May 31, 2019

[Part 11] Raymond Smullyan's Certified Knights and Knaves puzzles
A new puzzle



Here is a completely new puzzle that (as far as I know) isn't in any of Smullyan's or anybody else's books:
Every day on the island, I kept meeting natives and over time started to invent my own labels for them. For example, when two natives had a different type, i.e., knight versus knave, and a different certification status, i.e., certified versus uncertified (in any order), I thought of them as "full opposites".
One day, I met three natives A, B, and C. I knew nothing about A and B, and all I already knew about C (based on an earlier encounter) was that she was uncertified. During our brief encounter, A and B each made one statement that allowed me to infer that they were complete opposite of each other, but that neither one of them was a complete opposite of C. I was also able to infer that exactly one of my three interlocutors was a knave.
Which two statements would work? 
Can you solve this puzzle?

If so, can you find a "better" solution than mine?

How do you rank solutions anyway?

I can't wait to read your comments!
SPOILER: My answer appears below.

























Here is my solution:

 A: "I am certified, C is a knight, but B and I are not both knights."
B: "Either A and I are knaves or else I am certified and C is a knight."

 that I obtained by translating the following two formulas:

A <-> ((-A | -B) & (Ac & C))
B <-> ((-A & -B) | (Bc & C))
Posted by at No comments:
Labels: , , , , , , , ,

Thursday, May 30, 2019

[Part 10] Raymond Smullyan's Certified Knights and Knaves puzzles
Puzzle #6 - A new variant



Now that we have a JavaScript program to solve the following puzzle (see the last four posts):
On another particularly interesting occasion I came across two natives A and B each of whom made a statement such that I could infer that at least one of them must be an uncertified knight, but there was no way to tell which one it was. From neither statement alone could one have deduced this.
What two statements would work? [This problem is not easy!]
we can modify this program to solve a new puzzle, namely:
On another particularly interesting occasion I came across two natives A and B, only one of whom made a statement such that I could infer that at least one of them must be an uncertified knight, but there was no way to tell which one it was. From neither statement alone could one have deduced this.
What statement would work? [This problem is easy if you can program an automatic solver for it.]
So, can you modify our program (listed below) to solve this puzzle?
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) ); };

var literals = [A, Ac, B, Bc, NOT(A), NOT(Ac), NOT(B), NOT(Bc)];
var ops = [AND, OR];
var solutions = [];  // no solutions found yet

for(let pA1 of literals)
  for(let pA2 of literals) 
    for(let pB1 of literals) 
      for(let pB2 of literals) 
        if ((pA1 < pA2) && (pB1 < pB2)) 
          for(let opA of ops) 
            for(let opB of ops)
              check(pA1, opA, pA2, pB1, opB, pB2);

function check(pA1, opA, pA2, pB1, opB, pB2) {
    var phi = AND( IFF(A,opA(pA1,pA2)), IFF(B,opB(pB1,pB2)) );

    if (!(phi & none) && (phi & onlyA) && (phi & onlyB)) {
        // phi meets the requirements of a solution
        printAndSaveIfNewSolution(phi, pA1, opA, pA2, pB1, opB, pB2); 
    }
};

function printAndSaveIfNewSolution(phi, pA1, opA, pA2, pB1, opB, pB2) {
  if (! solutions.includes(phi)) {           // this is a new solution
    solutions.push(phi);                     // store it
    /* printing of the solution is omitted (see full code in Part 8) */
  }
};
In my solution, I assumed that the statement was made by A (say) and had the following structure:

\(A \leftrightarrow (\ (l_1\ op_2\ l_2)\  op_1\ (l_3\ op_3\ l_4)\ )\)

 in which \(l_1\), \(l_2\), \(l_3\), and \(l_4\) are literals chosen from the same list as above and \(op_1\), \(op_2\), and \(op_3\) are logical operators chosen from the list:

ops = [AND, OR, XOR];

 Note that I added XOR as a usable logical connective in this puzzle.

 I hope that you'll have fun solving this puzzle!

 For reference, here are the only three solutions that my program found:

Solution #1 
 A <-> ( (A & Ac) ^ (Bc | -B) )  

Solution #2 
 A <-> ( (B & -Bc) | (-A | -Ac) ) 

Solution #3 
 A <-> ( (Bc | -B) & (-A | -Ac) )

I think that the second solution is easiest to state concisely in English, namely:

A: "B is an uncertified knight or I am not a certified knight."

This solution is easy to check informally:
  • If A is a knight:
    • A's statement must be true. Therefore, either B is an uncertified knight or A is (since A is a knight but not a certified one), or both.
  • If A is a knave:
    • A's statement must be false. Therefore, both disjuncts must be false, including the second one, which implies that A must be a certified knight, which contradicts this case's assumption (i.e., A is a knave).
Therefore, in this solution, A must be a knight, but we do not know whether or not A is certified. However, if A is certified, then B must be an uncertified knight. So both A and B could be uncertified knights.

We can also check this solution formally with a truth table:

\(A\)\(Ac\)\(B\)\(Bc\)\(B\ \&\ {-Bc}\)\({-A}\ |\ {-Ac}\)\((B\ \&\ {-Bc})\ |\ ({-A}\ |\ {-Ac})\)Sol. #2
\(F\) \(F\) \(F\) \(F\) \(F\) \(T\) \(T\)
\(F\) \(F\) \(F\) \(T\) \(F\) \(T\) \(T\)
\(F\) \(F\) \(T\) \(F\) \(T\)\(T\) \(T\)
 only B
\(F\) \(F\) \(T\) \(T\) \(F\) \(T\) \(T\)
\(F\) \(T\) \(F\) \(F\) \(F\) \(T\) \(T\)
\(F\) \(T\) \(F\) \(T\) \(F\) \(T\) \(T\)
\(F\) \(T\) \(T\) \(F\) \(T\) \(T\) \(T\)
 only B
\(F\) \(T\) \(T\) \(T\) \(F\) \(T\) \(T\)
\(T\) \(F\) \(F\) \(F\) \(F\) \(T\) \(T\) ✓  only A
\(T\) \(F\) \(F\) \(T\) \(F\) \(T\) \(T\) ✓  only A
\(T\) \(F\) \(T\) \(F\) \(T\) \(T\) \(T\) ✓  both A and B
\(T\) \(F\) \(T\) \(T\) \(F\) \(T\) \(T\) ✓  only A
\(T\) \(T\) \(F\) \(F\) \(F\) \(F\) \(F\)
\(T\) \(T\) \(F\) \(T\) \(F\) \(F\) \(F\)
\(T\) \(T\) \(T\) \(F\) \(T\) \(F\) \(T\) ✓  only B
\(T\) \(T\) \(T\) \(T\) \(F\) \(F\) \(F\)

Can you check the other two solutions for correctness?

 Can you translate them into English?
Posted by at No comments:
Labels: , , , , , , , ,

Wednesday, May 29, 2019

[Part 9] Raymond Smullyan's Certified Knights and Knaves puzzles
Puzzle #6 - (At least) nine distinct solutions



Recall our sixth puzzle:
On another particularly interesting occasion I came across two natives A and B each of whom made a statement such that I could infer that at least one of them must be an uncertified knight, but there was no way to tell which one it was. From neither statement alone could one have deduced this.
What two statements would work? [This problem is not easy!]
and the nine solutions that our JavaScript program found:

Solution #1            Solution #4           Solution #7 
 A <-> (A | Bc)         A <-> (B | -A)        A <-> (-Bc | -A)
 B <-> (-B | -Ac)       B <-> (-Bc | -Ac)     B <-> (A & Ac) 

Solution #2            Solution #5           Solution #8
 A <-> (Ac | Bc)        A <-> (B | -Ac)       A <-> (-Bc | -A)
 B <-> (-B | -Ac)       B <-> (-Bc | -A)      B <-> (Ac | B)

Solution #3            Solution #6           Solution #9
 A <-> (B & Bc)         A <-> (-B | -Ac)      A <-> (-Bc | -B)
 B <-> (-Ac | -A)       B <-> (A | -Bc)       B <-> (A & Ac)

Solution #3 is the one that Smullyan discusses for this puzzle on page 45 of his book, namely:

 A: "B is a certified knight."
 B: "A is not a certified knight."

Note that B's statement can be more directly translated into propositional logic as:

B <-> -(Ac & A)

which, by De Morgan's law, is equivalent to the formula output by our program, namely:

B <-> (-Ac | -A)

Note that Solution #9 is equivalent to Solution #3 if we switch the names of the two natives.

These two solutions are the only ones in which each native only talks about the other native.

 In Solution #7, B only talks about A but A describes both natives:

 A: "Either I am a knave or B is uncertified."
 B: "A is a certified knight."

 In all other solutions, each native refers to both of them.

 When translating these solution formulas into English statements, we can vary the grammatical structure using the following logical equivalences:
  1. "-x | -y" is equivalent to "-(x & y)"
  2. "-x | y" is equivalent to "x -> y"
  3. "x | y" is equivalent to "--x | y" is equivalent to "-x -> y"
B's statement in Solution #3 discussed above is an example of the first equivalence.

We can use the second equivalence to translate A's statement in Solution #4:

 A: "If I am a knight, then so is B."
 B: "At least one of us is uncertified."

Note that we used the commutativity of disjunction when translating A's statement.

We can use the third equivalence to translate A's statement in Solution #1:

 A: "If I am a knave, then B is certified."
 B: "If I am a knight then A is uncertified."

To conclude this discussion, it is worth emphasizing that all of these solutions are logically distinct.

Recall that each solution (i.e., each formula \(\varphi\)), is encoded by an integer (see the JavaScript program that we discussed earlier) and that the program removes duplicates.

This means that, in addition to the many ways to express them in grammatically correct English, these solutions ALL describe different scenarios.

This can be demonstrated easily by building a truth table for all of these solutions:

\(A\)\(Ac\)\(B\)\(Bc\)\(S1\)\(S2\)\(S3\)\(S4\)\(S5\)\(S6\)\(S7\)\(S8\)\(S9\)
\(F\)\(F\)\(F\)\(F\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)
\(F\)\(F\)\(F\)\(T\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)
\(F\)\(F\)\(T\)\(F\)✓✓✓\(\)\(\)\(\)\(\)\(\)\(\) only B
\(F\)\(F\)\(T\)\(T\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)
\(F\)\(T\)\(F\)\(F\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)
\(F\)\(T\)\(F\)\(T\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)
\(F\)\(T\)\(T\)\(F\)\(\)\(\)✓\(\)\(\)✓\(\)\(\)\(\) only B
\(F\)\(T\)\(T\)\(T\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)
\(T\)\(F\)\(F\)\(F\)\(\)\(\)\(\)\(\)\(\)\(\)✓✓✓ only A
\(T\)\(F\)\(F\)\(T\)\(\)\(\)\(\)\(\)✓\(\)\(\)\(\)✓ only A
\(T\)\(F\)\(T\)\(F\)✓\(\)\(\)✓✓✓\(\)✓\(\) both A and B
\(T\)\(F\)\(T\)\(T\)✓✓✓✓\(\)✓\(\)\(\)\(\) only A
\(T\)\(T\)\(F\)\(F\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)
\(T\)\(T\)\(F\)\(T\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)
\(T\)\(T\)\(T\)\(F\)\(\)\(\)\(\)✓✓\(\)✓✓✓ only B
\(T\)\(T\)\(T\)\(T\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)\(\)

In the table above, in each solution column, I used a checkmark instead of a True value and omitted the False values in order to make the relevant cases easier to pick out.

 It is now easy to check that no two solutions pick out the same scenario.

 For example, solutions 1, 4, 5, 6, and 8 make it possible for both natives to be uncertified knights, but none of the other solutions do.

 Even solutions that allow exactly one native to be an uncertified knight are all distinct:
  • In Solution 2, the "other one" is either an uncertified knave (A) or a certified knight (B).
  • Solution 3 differs from solution 2 in that it allows for an extra possibility, namely for the other one (A) to be a certified knave.
  • Solution 7 only allows for two possibilities that are different from the ones in Solution 2.
  • Solution 9 allow for three possibilities that do not overlap with those in Solution 3.
Finally, there is one aspect of the puzzle that we have not discussed yet, namely, the condition that:

"From neither statement alone could one have deduced this."

 Homework:
  • Do all nine solutions above satisfy this extra requirement?
  • Can you modify our program to check this automatically?
Posted by at No comments:
Labels: , , , , , , , ,

Tuesday, May 28, 2019

[Part 8] Raymond Smullyan's Certified Knights and Knaves puzzles
Puzzle #6 - Finding solutions using JavaScript



In the previous post, we discussed how to represent an entire column of a truth table as a single integer and how to perform Boolean operations on entire columns in JavaScript.

 Here is the code that we wrote last time:
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) ); };
In this post, we will complete this program to solve Puzzle #6. 

Recall that we are looking for a formula:

\(\varphi = (A \leftrightarrow \varphi_A)\ \&\ (B \leftrightarrow \varphi_B)\)

that satisfies the requirements represented by the following truth table:

\(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\)

More specifically, we are looking for formulas \(\varphi_A\) and \(\varphi_B\) such that the formula \(\varphi\) is:
  • always False in the white rows
    AND
  • True in one or more green rows 
    AND
  • True in one or more red rows
While we are interested in finding as many solutions as possible, we will limit our search to formulas of a given form.

 More precisely, we are going to consider all formulas \(\varphi_A\) and \(\varphi_B\) that are either a conjunction or a disjunction of two literals, where a literal is a single proposition or its negation.

 Therefore, we build a list (i.e., an array) of all the literals we will need, as follows:
var literals = [A, Ac, B, Bc, NOT(A), NOT(Ac), NOT(B), NOT(Bc)];
that is, the list of our four propositions and their negation.

 Similarly, the list of logical connectives or operators (ops, for short) we are considering using in \(\varphi_A\) and \(\varphi_B\) is defined as follows: 
var ops = [AND, OR];
where AND and OR are the JavaScript functions that we defined above.

To summarize, we are going to consider for \(\varphi_A\) all formulas of the form:

pA1 opA pA2

where pA1 and pA2 are two distinct propositions (or their negation) and opA is either AND or OR.

 Similarly, we are going to consider for \(\varphi_B\) all formulas of the form:

pB1 opB pB2

where pB1 and pB2 are two distinct propositions (or their negation) and opB is either AND or OR.

 Since all combinations are possible, the core of our algorithm is a sequence of nested FOR loops that cover all of the combinations just described, namely:
for(let pA1 of literals)
  for(let pA2 of literals) 
    for(let pB1 of literals) 
      for(let pB2 of literals) 
        if ((pA1 < pA2) && (pB1 < pB2)) 
          for(let opA of ops) 
            for(let opB of ops)
              check(pA1, opA, pA2, pB1, opB, pB2);

 Note that I added an IF statement to make sure that we do not waste time considering the same literal twice in a formula, or even the same pair of literals in reverse order, since both OR and AND are commutative operators. Since each literal is an integer that is different from all other literals in our list, making sure that one is less than the other is enough to avoid the duplication just mentioned.

 The last line of the code above is a call to a function that checks each combination to determine whether or not it yields a formula \(\varphi\) that is a solution to the puzzle.

 This check function is coded as follows:
function check(pA1, opA, pA2, pB1, opB, pB2) {
    var phi = AND( IFF(A,opA(pA1,pA2)), IFF(B,opB(pB1,pB2)) );

    if (!(phi & none) && (phi & onlyA) && (phi & onlyB)) {
       printAndSaveIfNewSolution(phi, pA1, opA, pA2, pB1, opB, pB2); 
    }
};

This function first computes the Boolean value of the formula \(\varphi\), which was defined as:

\((A \leftrightarrow \varphi_A)\ \&\ (B \leftrightarrow \varphi_B)\)

The value of \(\varphi\) is stored in the variable phi.

 As a second step, this value, which represents an entire column of the truth table corresponding to the formula \(\varphi\), is checked against each one of the three requirements of a solution.

 First, it is a solution if it is False in all white rows, that is, if:

phi & none

is equal to zero (i.e., "falsy" in JavaScript). or equivalently, if:

!(phi & none)

is True (note that the ! operator is the Boolean (NOT the bitwise) negation in JavaScript).

Second, it is a solution if it is True in at least one green row, that is, if:

phi & onlyA

is NOT equal to 0  (i.e., "truthy" in JavaScript).

 Third, it is a solution if it is True in at least one red row, that is, if:

phi & onlyB

is NOT equal to 0  (i.e., "truthy" in JavaScript).

Since all three conditions must be true, I used the && operator, which is the Boolean (NOT the bitwise) conjunction in JavaScript.

 If all three conditions hold, I call the function printAndSaveIfNewSolution that is defined below:
function printAndSaveIfNewSolution(phi, pA1, opA, pA2, pB1, opB, pB2) {
    if (! solutions.includes(phi)) {   // this is a new solution
      solutions.push(phi);             // store it
      ...                              
      var phiStr = ...                 // convert phi to a string ...
      console.log(...);                // ... and print it
    }
};

This function is not that interesting (its full implementation is given below if you really want to dig deeper). It achieves two tasks if the input combination is a new solution:
  1. It stores this solution in the solutions array so that later duplicates will be eliminated (this array is initially empty before our nested loops are executed).
  2. It prints a human-readable version of the formula to the console.
Before continuing, did you try to solve this puzzle on your own?

 If so, how many solutions (i.e., pairs of statements) did you find?

 The answers found by my program will be revealed if you click the button below.


Solution #1 
 A <-> (A | Bc)
 B <-> (-B | -Ac) 

Solution #2 
 A <-> (Ac | Bc)
 B <-> (-B | -Ac) 

Solution #3 
 A <-> (B & Bc)
 B <-> (-Ac | -A) 

Solution #4 
 A <-> (B | -A)
 B <-> (-Bc | -Ac)

Solution #5 
 A <-> (B | -Ac)
 B <-> (-Bc | -A) 

Solution #6 
 A <-> (-B | -Ac)
 B <-> (A | -Bc) 

Solution #7 
 A <-> (-Bc | -A)
 B <-> (A & Ac) 

Solution #8 
 A <-> (-Bc | -A)
 B <-> (Ac | B) 

Solution #9 
 A <-> (-Bc | -B)
 B <-> (A & Ac)
Here is the program in full: 
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) ); };

var literals = [A, Ac, B, Bc, NOT(A), NOT(Ac), NOT(B), NOT(Bc)];
var ops = [AND, OR];
var solutions = [];  // no solutions found yet

for(let pA1 of literals)
  for(let pA2 of literals) 
    for(let pB1 of literals) 
      for(let pB2 of literals) 
        if ((pA1 < pA2) && (pB1 < pB2)) 
          for(let opA of ops) 
            for(let opB of ops)
              check(pA1, opA, pA2, pB1, opB, pB2);

function check(pA1, opA, pA2, pB1, opB, pB2) {
    var phi = AND( IFF(A,opA(pA1,pA2)), IFF(B,opB(pB1,pB2)) );

    if (!(phi & none) && (phi & onlyA) && (phi & onlyB)) {
        // phi meets the requirements of a solution
        printAndSaveIfNewSolution(phi, pA1, opA, pA2, pB1, opB, pB2); 
    }
};

function getLiteral(n) {
    switch (n) {
    case 255:   return "A";
    case 3855:  return "Ac";
    case 13107: return "B";
    case 21845: return "Bc";
    case 65280: return "-A";
    case 61680: return "-Ac";
    case 52428: return "-B";
    case 43690: return "-Bc";
    }
};

function printAndSaveIfNewSolution(phi, pA1, opA, pA2, pB1, opB, pB2) {
  if (! solutions.includes(phi)) {           // this is a new solution
    solutions.push(phi);                     // store it
    var opAstr = opA === ops[0] ? "&" : "|"; // print it
    var opBstr = opB === ops[0] ? "&" : "|";
    var phiAstr = getLiteral(pA1) + " " + opAstr + " " + getLiteral(pA2);
    var phiBstr = getLiteral(pB1) + " " + opBstr + " " + getLiteral(pB2);
    var phiStr = "A <-> (" + phiAstr + ")\n B <-> (" + phiBstr + ")";
    console.log( "Solution #" + solutions.length,"\n",phiStr,"\n");
  }
};
In the next post, we'll take a close look at the solutions that this program finds.
Posted by at No comments:
Labels: , , , , , , ,

Monday, May 27, 2019

[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.
Posted by at No comments:
Labels: , , , , , , ,
Subscribe to: Posts (Atom)