如何将多值逻辑转换为高效的布尔逻辑？

Question

假设我有一个集合 S，包含以下元素：{0₁, ¯1₂, 0₂, 1₂, ¯2₃, ¯1₃, 0₃, 1₃, 2₃, ¯3₄, ¯2₄, ¯1₄, 0₄, 1₄, 2₄, 3₄}。我想对 S 定义以下操作：

• S < 0表示当S为负数时返回1。
• ¯S表示S的否定。
• S + 0表示返回S加零，即S不变。
• S + 1表示返回S的绝对值加一，模下标。例如：
  • ¯1₃ + 1和1₃ + 1都被计算为2₃。
  • ¯2₃ + 1和2₃ + 1都被计算为0₃。
  • 表达式0₃ + 1被计算为1₃。
• S ¢ 0表示返回S + 0的进位，即零。
• S ¢ 1表示返回S + 1 = 0ₙ（其中n > 1）的进位，当且仅当S + 1 = 0ₙ时返回1。

这些信息可以通过真值表的形式进行捕捉：

  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 │
└───┴───┴───┴───┴───┴───┴───┘

我想要做的是将这个多值真值表转换成布尔真值表，以便我可以使用位运算符进行并行操作。听起来很简单。将0₁赋值为0000，将¯1₂赋值为0001，依此类推，将3₄赋值为1111。解决所得到的卡诺图，得到一个合取范式(CNF)或析取范式(DNF)表达式，然后就可以了结了。

不幸的是，使用这种天真的将S映射到布尔值的方法得到的CNF或DNF表达式可能不够有效。我想找到最有效的方法将多值真值表表示为布尔真值表。在这里，有效意味着使用最少的运算符来实现各种操作，首选加法、否定、进位和比较。然而，问题在于有16!或20922789888000种将S映射到布尔值的方式。有没有比暴力搜索更好的方法来找到解决方案？

- Aadit M Shah

---

你不应该在左侧列添加 1 和 0 吗？ - Stanislav Kralin

我不明白你的意思。 - Aadit M Shah

我的意思是1和0也应该是逻辑值。1₂ + 0是1₂，但是1 + 0是什么呢？顺便问一下，位移运算符允许使用吗？ - Stanislav Kralin

它们属于不同的集合。1₂ 属于集合 S，而 1 和 0 属于布尔值集合 B。+ 操作要求其左操作数属于集合 S，右操作数属于集合 B。+ 操作的结果是来自集合 S 的一个值。 - Aadit M Shah

不允许使用位移运算符，因为每个位都将被单独存储。这样做的原因是为了并行性。例如，给定一个包含“S”值的矩阵，所有高位都存储在一个位数组中，所有低位都存储在另一个位数组中，等等。因此，位移运算符会将位移动到矩阵的值上。想法是使用位运算执行卷积。 - Aadit M Shah

Answer 1

我无法想出一个通用的解决方案来解决这个问题，但是这里有一个针对我的问题的具体解决方案。我们将集合S分为两个不相交的集合：S₁和S₂。集合S₁包含0₁和下标₄的元素。集合S₂包含下标₂和下标₃的元素：

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

现在，我们可以分别解决S₁和S₂的问题。但是，我们希望以一种使解决方案相似的方式来解决它们。因此，在将它们组合时，我们可以利用相似性来减少所涉及的操作数。以下是我提出的解决方案：

我的解决方案有两个需要注意的地方：

1. 所有的零元素都属于 C'D' 列。因此，使用 C+D 很容易选择其余的元素。这在后面会很有用。
2. 负数元素总是在 B 行，并且与相应正数元素在同一列。这使得取反和检查是否为负数变得容易。

无论如何，以下是使用位运算符实现的操作，其中 (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)

加法、进位、否定和比较所需的操作次数分别为18、3、2和2。请注意，对于否定，我们只需要修改B，而对于加法，我们不需要修改A。公共子表达式消除和异或运算用于简化操作。

我不知道是否可能比这更好。这是我想出的最佳解决方案。

- Aadit M Shah