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

Question

假设我有一个由{0₁, ¯1₂, 0₂, 1₂, ¯2₃, ¯1₃, 0₃, 1₃, 2₃, ¯3₄, ¯2₄, ¯1₄, 0₄, 1₄, 2₄, 3₄}组成的集合S。我想在 S:

上定义以下操作

S < 0 当且仅当 S 为负数时 returns 一个。
¯S returns S.
S + 0其中returnsS加零，即S不变
S + 1其中returnsS的绝对值加一，下标取模。例如：
- ¯1₃ + 1 和 1₃ + 1 的计算结果都是 2₃。
- ¯2₃ + 1 和 2₃ + 1 的计算结果都是 0₃。
- 表达式 0₃ + 1 的计算结果为 1₃。
S ¢ 0 其中 returns S + 0 的 carry 为零。
S ¢ 1 returns S + 1 的进位，当且仅当 S + 1 = 0ₙ 对于 n > 1.

这些信息可以以真实的形式被捕获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 │
└───┴───┴───┴───┴───┴───┴───┘

我想做的是将这个多值真值table转换成布尔真值table，这样我就可以使用位运算符来实现并行化的操作。听起来很简单。将 0000 分配给 0₁，0001 分配给 ¯1₂，...，1111 分配给 3₄。求解生成的 Karnaugh map to get a CNF or DNF 表达式并收工。

不幸的是，对于 S 到布尔值的这种天真映射，生成的 CNF 或 DNF 表达式可能效率不高。我想找到最有效的方法来将这个多值真理 table 表示为布尔真理 table。在这里，高效意味着使用最少的运算符来实现各种运算，并优先考虑加法、取反、进位和比较的顺序。但是，问题是有 16! 或 20922789888000 方法可以将 S 映射到布尔值。有没有比蛮力更好的方法来找到解决方案？

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₂解决这个问题。但是，我们希望以解决方案相似的方式进行。因此，当我们组合它们时，我们可以利用相似性来减少所涉及的操作数量。这是我提出的解决方案：

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

所有零元素都属于 C'D' 列。因此，使用 C+D 很容易 select 其余元素。这个以后用得上。
负元素始终在 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。 Common subexpression elimination 和 xor 操作被用于 reduce 操作。

我不知道是否可以做得比这更好。这是我想到的最好的解决方案。

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

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

logic

boolean-logic

karnaugh-map