1

假设我有以下布尔函数。

def Bottom():
    return False

def implies(var1, var2):
    if var1 == True and var2 == False: return False
    return True

def land(var1, var2):
    return var1 == True and var2 == True.

是否有一种有效的算法将这三个函数作为输入，并确定前两个函数的哪个（可能是多应用）函数组合将匹配第三个函数的输出，每个布尔（T，F）输入到第三个函数功能？

我正在使用 Python 来编写我的示例，但我并没有将解决方案限制为 Python 或任何编程语言。事实上，我实际上并不是在寻找代码，而更多的是对算法的描述或对为什么不存在的解释。

作为旁注，我尝试发现该算法的动机是因为我被要求展示一组特定逻辑连接词的功能完整性，我们通过展示一个逻辑连接词可以被一组其他逻辑连接词模拟来做到这一点。对于逻辑，我们必须使用一点猜测和检查，但如果没有对大量可能性进行线性搜索，我无法找到一种方法来在程序中捕获它。

4

1 回答 1

2

如果您只查看两个参数的布尔函数，那么简单的蛮力技术将起作用。它可以扩展到三元逻辑，或三元函数，甚至两者兼而有之，但它是指数的，所以你不能把它推得太远。这是布尔版本；我希望如何扩展它是显而易见的。

1）二进制布尔函数是一个关系{False, True} X {False, True} -> {False, True}。其中正好有 16 个。请注意，这些包括独立于一个或什至两个输入的各种功能。因此，让我们将集合完全由这 16 个函数组成，现在注意每个布尔函数都有一个对应的高阶函数 X -> 。

2) 现在，从布尔函数Take first和开始Take second，并使用对应于“给定函数”的 HOF 构造一个闭包。如果目标函数在闭包中，那么它可以通过给定函数的某种组合来实现。更一般地说，如果每个元素都在闭包中，那么给定的函数是通用的。

因此，让我们将此应用于您的示例。我将按(F,F) (F,T) (T,F) (T,T)顺序将 的元素编写为与输入相对应的四元组，并将 HOF 写为粗体。Bottom也是如此。FFFF_ Implies_ 底部(a, b)用于任何 (a,b)。TTFTFFFF

Take firstisFFTT和Take secondis FTFT，所以这是我们的起始集。我们可以使用Bottom来添加FFFF，但显然没有进一步的Bottom应用程序会添加任何东西。

所以现在我们有九对可能的函数可以应用于Implies。开始了：

暗示( FFTT, FFTT) == TTTT(新)

暗示( FFTT, FTFT) == TTFT(新)

暗示( FFTT, FFFF) == TTFF(新)

暗示( FTFT, FFTT) == TFTT(新)

暗示( FTFT, FTFT) ==TTTT

暗示( FTFT, FFFF) == TFTF(新)

暗示( FFFF, FFTT) ==TTTT

暗示( FFFF, FTFT) ==TTTT

暗示( FFFF, FFFF) ==TTTT

现在我们最多有 16 个函数中的 8 个函数，而且我们还有很多对要检查。由于这实际上是一个完整的集合，它会变得乏味，所以我将把下一步留给读者（或者可能是他们的计算机程序）。

于 2013-02-16T00:02:48.620 回答