logicboolean-logickarnaugh-map

How to convert many-valued logic into efficient boolean logic?

Suppose that I have a set S consisting of {0₁, ¯1₂, 0₂, 1₂, ¯2₃, ¯1₃, 0₃, 1₃, 2₃, ¯3₄, ¯2₄, ¯1₄, 0₄, 1₄, 2₄, 3₄}. I want to define the following operations over S:

This information can be captured in the form of a truth table:

  S  S<0 ¯S  S+0 S+1 S¢0 S¢1
┌───┬───┬───┬───┬───┬───┬───┐
│ 0₁│ 0 │ 0₁│ 0₁│ 0₁│ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
│¯1₂│ 1 │ 1₂│¯1₂│ 0₂│ 0 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
│ 0₂│ 0 │ 0₂│ 0₂│ 1₂│ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
│ 1₂│ 0 │¯1₂│ 1₂│ 0₂│ 0 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
│¯2₃│ 1 │ 2₃│¯2₃│ 0₃│ 0 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
│¯1₃│ 1 │ 1₃│¯1₃│ 2₃│ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
│ 0₃│ 0 │ 0₃│ 0₃│ 1₃│ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
│ 1₃│ 0 │¯1₃│ 1₃│ 2₃│ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
│ 2₃│ 0 │¯2₃│ 2₃│ 0₃│ 0 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
│¯3₄│ 1 │ 3₄│¯3₄│ 0₄│ 0 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
│¯2₄│ 1 │ 2₄│¯2₄│ 3₄│ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
│¯1₄│ 1 │ 1₄│¯1₄│ 2₄│ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
│ 0₄│ 0 │ 0₄│ 0₄│ 1₄│ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
│ 1₄│ 0 │¯1₄│ 1₄│ 2₄│ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
│ 2₄│ 0 │¯2₄│ 2₄│ 3₄│ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
│ 3₄│ 0 │¯3₄│ 3₄│ 0₄│ 0 │ 1 │
└───┴───┴───┴───┴───┴───┴───┘

What I want to do is convert this many-valued truth table into a boolean truth table so that I can implement the operations using bitwise operators for parallelization. Sounds simple enough. Assign 0000 to 0₁, 0001 to ¯1₂, ..., 1111 to 3₄. Solve the resulting Karnaugh map to get a CNF or DNF expression and call it a day.

Unfortunately, the resulting CNF or DNF expressions might not be efficient with this naive mapping of S to boolean values. I want to find the most efficient way to represent this many-valued truth table as a boolean truth table. Here, efficient means using the fewest operators to implement the various operations with preference being given to addition, negation, carry and comparison in that order. However, the problem is that there are 16! or 20922789888000 ways to map S to boolean values. Is there a better way to find the solution than brute force?

Solution

  • I can't think of a general solution to this problem but here's a specific solution for my problem. We begin by diving the set S into two disjoint sets, S₁ and S₂. The set S₁ would contain 0₁ and the subscript ₄ elements. The set S₂ would contain the subscript ₂ and subscript ₃ elements:

    S₁ = {0₁, ¯3₄, ¯2₄, ¯1₄, 0₄, 1₄, 2₄, 3₄}
S₂ = {¯1₂, 0₂, 1₂, ¯2₃, ¯1₃, 0₃, 1₃, 2₃}
S  = S₁ ∪ S₂

    Now, we can solve this problem separately for S₁ and S₂. However, we want to do it in such a way that the solutions are similar. Thus, when we combine them we can take advantage of the similarity to reduce the number of operations involved. Here's the solution that I came up with:

    Solution

    There are two things to notice about my solution:

    1. All the zero elements belong to the C'D' column. Hence, it's easy to select the rest of the elements using C+D. This will come in handy later.
    2. The negative elements are always in the B row, and in the same column as the corresponding positive elements. This makes negation and checking whether negative easy.

    Anyway, here are the operations implemented using bitwise operators where (A, B, C, D) ∈ S:

    (A, B, C, D) < 0 = B (C + D)

¯(A, B, C, D)    = (A, B ^ (C + D), C, D)

(A, B, C, D) + M =
    E = C D
    N = M'
    (A, B N + M E,
        C N + M (A ^ C ^ D ^ A E),
        D N + M D' (B + C))

(A, B, C, D) ¢ M = M D (A + C)

    The number of operations required for addition, carry, negation and comparison are 18, 3, 2 and 2 respectively. Notice that for negation we only need to modify B and for addition we don't need to modify A. Common subexpression elimination and xor operations are used reduce operations.

    I don't know whether it's possible to do better than this. This is the best solution that I came up with.