Notebook

Truth Tables Tutorial Workbook¶

What is this workbook? A workbook is a collection of problems, accompanied by solutions to them. The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required.

Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.

This workbook describes the solutions to the problems offered in the Truth Tables tutorial. Since the tasks are offered as programming problems, the explanations also cover some elements of Python that might be non-obvious for a first-time user.

What you should know for this workbook

Truth tables.
Basic Python knowledge is helpful but not necessary.

Task 1. Projective functions (elementary variables)¶

Goal: Describe the three projective functions $x_1$, $x_2$, $x_3$ represented by integers. Each of them is a 3-input function, i.e., $f(x) : \{0,1\}^{3} \rightarrow \{0,1\}$

We use the following convention:

$x_1$ is the least significant input.
$x_3$ is the most significant input.

The function $x_1$ (least significant input) is given as an example.

The function is true for assignments $001$, $011$, $101$, and $111$, since for all these assignments their least significant bit $x_1 = 1$.

If $x_1 = 0b10101010$, what are the values of $x_2$ and $x_3$?

Solution¶

Let's take another look at the truth table for the functions $x_1$, $x_2$, and $x_3$

$x_3$	$x_2$	$x_1$	Is $x_1 = 1?$	Is $x_2 = 1?$	Is $x_3 = 1?$	Bit of the integer which represents the truth table
0	0	0				Least significant
0	0	1	Yes
0	1	0		Yes
0	1	1	Yes	Yes
1	0	0			Yes
1	0	1	Yes		Yes
1	1	0		Yes	Yes
1	1	1	Yes	Yes	Yes	Most Significant

To convert this form of a truth table into a single integer format, we need to write out all the bits of its values, from the most significant to the least significant.

The truth table for $x_2$ is 0b11001100 (the bits in the $x_2$ column, from the bottom row to the top row) and the truth table for $x_3$ is 0b11110000.

In [ ]:

%kata T01_ProjectiveTruthTables 

open Quantum.Kata.TruthTables;

function ProjectiveTruthTables () : (TruthTable, TruthTable, TruthTable) {
    let x1 = TruthTable(0b10101010, 3);
    let x2 = TruthTable(0b11001100, 3);
    let x3 = TruthTable(0b11110000, 3);

    return (x1, x2, x3);
}

Return to task 1 of the Truth Tables kata.

Task 2. "Exactly 1 bit is true" function¶

Goal: Describe a 3-input function $f(x_3,x_2,x_1)$ represented by an integer which is true if and only if exactly 1 bit out of $x_1$, $x_2$ or $x_3$ is true.

Solution¶

The function is true for assignments $100$, $010$, and $001$, since for these assignments exactly one bit is true. The function is false for assignments $000$, $011$, $101$, $110$, and $111$, since for all these assignments either all bits are false or more than one bit is true.

To spell out the binary notation of the resulting integer, we list the bits (1 if the function is true and 0 if it is false), starting with the input $111$ and ending with $000$: 0b00010110.

In [ ]:

%kata T02_ExactlyOneBitTrue

open Quantum.Kata.TruthTables;

function ExactlyOneBitTrue () : (TruthTable) {
    let f = TruthTable(0b00010110, 3);
    return f;
}

Return to task 2 of the Truth Tables kata.

Task 3. "Exactly 2 bits are true" function¶

Goal: Describe a 3-input function $f(x_3,x_2,x_1)$ represented by an integer which is true if and only if exactly 2 bits out of $x_1$, $x_2$ or $x_3$ are true.

If $f = 0$, what are the values of $x_1$, $x_2$, and $x_3$?

Solution¶

The function is true for assignments $011$, $101$, and $110$, since for these assignments exactly 2 bits are true. The function is false for assignments $000$, $001$, $010$, $100$, $111$, since all these assignments do not have exactly 2 bits as true.

The binary notation of the resuling integer is 0b01101000.

In [ ]:

%kata T03_ExactlyTwoBitsTrue

open Quantum.Kata.TruthTables;

function ExactlyTwoBitsTrue () : (TruthTable) {
    let f = TruthTable(0b01101000, 3);            // Update the value of f ...
    return f;
}

Return to task 3 of the Truth Tables kata.

Task 4. Compute AND of two truth tables¶

Goal: Compute a truth table that computes the conjunction (AND) of two truth tables. Find a way to perform the computation directly on the integer representations of the truth tables, i.e., without accessing the bits individually.

Solution¶

For each input, the value of the goal function is an AND of the values of the two given functions for the same input. We can use &&& operator to compute the bitwise conjunction (AND) of two integers representing truth tables to get the integer representing the goal function directly.

Remember that TruthTable is a user-defined type with fields bits and numVars. You can access these fields as tt1::bits and tt1::numVars, respectively, and construct the return value from the fields using a constructor TruthTable(newBits, newNumVars).

In [ ]:

%kata T04_TTAnd 

open Quantum.Kata.TruthTables;

function TTAnd (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {
    return TruthTable(tt1::bits &&& tt2::bits, tt1::numVars);
}

Return to task 4 of the Truth Tables kata.

Task 5. Compute OR of two truth tables¶

Goal: Compute a truth table that computes the disjunction (OR) of two truth tables.

Solution¶

Similarly to the previous task, we can use the bitwise OR ||| operator to compute the disjunction (OR) of two truth tables.

In [ ]:

%kata T05_TTOr 

open Quantum.Kata.TruthTables;

function TTOr (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {
    return TruthTable(tt1::bits ||| tt2::bits, tt1::numVars);
}

Return to task 5 of the Truth Tables kata.

Task 6. Compute XOR of two truth tables¶

Goal: Compute a truth table that computes the exclusive-OR (XOR) of two truth tables.

Solution¶

We can use the bitwise XOR ^^^ operator to compute the exclusive-OR (XOR) of two truth tables such as: tt1 ^^^ tt2.

In [ ]:

%kata T06_TTXor 

open Quantum.Kata.TruthTables;

function TTXor (tt1 : TruthTable, tt2 : TruthTable) : TruthTable {
    return TruthTable(tt1::bits ^^^ tt2::bits, tt1::numVars);
}

Return to task 6 of the Truth Tables kata.

Task 7. Compute NOT of a truth table¶

Goal: Compute a truth table that computes negation of a truth table.

Solution¶

We can use the bitwise negation ~~~ operator to compute the negation (NOT) a truth table. Note, though, that this operator will flip all bits of the integer, and we need to flip only $2^{numVars}$ least significant bits, since the rest of the bits should remain set to 0. To do this, we can do the following steps:

Construct a bitmask 0b0..01..1, in which the $2^{numVars}$ least significant bits are set to 1, representing all possible inputs to the function. This mask can be constructed as $2^{2^{numVars}} - 1$.
Subtract the integer representation of the truth table from this mask. This will have the effect of negating each of the least significant $2^{numVars}$ bits, while leaving the most significant bits set to 0.

In [ ]:

%kata T07_TTNot 

open Quantum.Kata.TruthTables;

function TTNot (tt : TruthTable) : TruthTable {
    return TruthTable((1 <<< (1 <<< tt::numVars)) - 1 - tt::bits, tt::numVars);
}

Return to task 7 of the Truth Tables kata.

Task 8. Build if-then-else truth table¶

Goal: Compute the truth table of the if-then-else function ttCond ? ttThen | ttElse (if ttCond then ttThen else ttElse) by making use of the truth table operations defined in the previous four tasks.

Solution¶

We can use the following formula to satisfy If/Else conditional function: ((NOT ttCond) AND ttThen) OR (ttCond AND ttElse). We've implemented all the building blocks of this formula in the previous tasks, so we can use them here.

In [ ]:

%kata T08_IfThenElseTruthTable 

open Quantum.Kata.TruthTables;

function TTIfThenElse (ttCond : TruthTable, ttThen : TruthTable, ttElse : TruthTable) : TruthTable {
    return TTXor(TTAnd(ttCond, ttThen), TTAnd(TTNot(ttCond), ttElse));
}

Return to task 8 of the Truth Tables kata.

Task 9. Find all true input assignments in a truth table¶

Goal: Return an array that contains all input assignments in a truth table that have a true truth value. These input assignments are called minterms. The order of assignments in the return does not matter.

Example:

The truth table of 2-input OR is 0b1110, i.e., its minterms are [1, 2, 3].

Solution 1¶

Let's iterate over all assignments, checking whether each of them is true, and aggregating the indices of those that are into an array to be returned.

In [ ]:

%kata T09_AllMinterms 

open Quantum.Kata.TruthTables;

function AllMinterms (tt : TruthTable) : Int[] {
    mutable minterms = [];
    mutable bits = tt::bits;
    for i in 0 .. 2 ^ tt::numVars - 1 {
        if bits % 2 == 1 {
            set minterms += [i];
        }
        set bits /= 2;
    }
    return minterms;
}

Solution 2¶

Alternatively, we can use Q# library functions for handling arrays to express the same logic:

IntAsBoolArray function will convert the truth table stored as an integer into an array of individual bits; the bit at index ind will be the value of the function for the input assignment ind.
Enumerated function will convert the array of values into an array of tuples, attaching the index ind to each bit.
Filtered function will filter out the tuples based on the value of the bit, keeping only the ones for which it is true.
Finally, Mapped function will keep only the indices of the remaining tuples.
Fst and Snd functions return the first and the second elements of the input tuple, respectively.

In [ ]:

%kata T09_AllMinterms

open Microsoft.Quantum.Arrays;
open Microsoft.Quantum.Convert;
open Quantum.Kata.TruthTables;

function AllMinterms (tt : TruthTable) : Int[] {
    let bits = IntAsBoolArray(tt::bits, 2^tt::numVars);
    let indexedBits = Enumerated(bits);
    let filteredTuples = Filtered(Snd, indexedBits);
    return Mapped(Fst, filteredTuples);
}

Return to task 9 of the Truth Tables kata.

Task 10. Apply the truth table as a quantum operation¶

Goal: Apply the X operation on the target qubit, if and only if the classical state of the controls is a minterm of the truth table.

Solution¶

A typical controlled gate (implemented by the ControlledOnInt function) applies the gate if the classical state of the control qubits matches the given integer. In our case, we need to apply the X gate if the classical state matches any one of the minterms; we can implement this by applying a series of controlled X gates, one per minterm. Since all minterms are different, the X gate will never end up being applied two or more times.

This operation is very similar to the operation ApplyXControlledOnTruthTable from the Q# libraries.

In [ ]:

%kata T10_ApplyFunction 

open Quantum.Kata.TruthTables;

operation ApplyXControlledOnFunction (tt : TruthTable, controls : Qubit[], target : Qubit) : Unit is Adj {
    for term in AllMinterms(tt) {
        ControlledOnInt(term, X)(controls, target);
    }
}

Return to task 10 of the Truth Tables kata.