1

这是我要解决的问题...

证明 n 个变量的布尔函数个数由递推式给出

T(1) = 4

T(n) = (T(n-1))^2

求解 T(n)。

我一直在通过多种不同的方式思考这个问题，但对我来说唯一有意义的是 T(n) 将是 O(1)，因为

T(n) = T(n-1) = T(n-2) = T(n-3) = ... = T(ni) 使用 i = n-1 会得到 T(n) = 4

这意味着 T(n) 是 O(1) 并且平方它不会改变任何东西所以

T(n) = (T(n-1))^2 = T(n-1)*T(n-1) ... = 4*4 = 16

这意味着在这种情况下 T(n) 也是 O(n)。这是正确的想法还是我完全离开了？任何帮助将非常感激。

4

1 回答 1

0

这里有两个独立的问题：

  1. 证明 n 个变量上的布尔函数个数服从递推关系。
  2. 求解递推关系。

让我们依次解决每个问题。

推导递归

让我们从单个变量的布尔函数开始。这些函数会将 0 或 1 分配给输入 0，并将 0 或 1 分配给输入 1。这意味着基于这些可能的输出有四种可能的功能。事实上，你可以在这里列出它们：

f(0) = 0    g(0) = 0   h(0) = 1   i(0) = 1
f(1) = 0    g(1) = 1   h(1) = 0   i(1) = 1

因此，T(1) = 4。

现在，让我们考虑一下有多少个 (n + 1) 变量布尔函数。您可以将 (n + 1) 变量布尔函数 f(b 1 , b 2 , ..., b n , b n+1 ) 视为根据另外两个 n 变量布尔函数 g 和 h 定义：

g(b 1 , b 2 , ..., b n ) = f(b 1 , b 2 , ..., b n , 0)

h(b 1 , b 2 , ..., b n ) = f(b 1 , b 2 , ..., b n , 1)

换句话说，对于任何一对 n 变量布尔函数 g 和 h，您都可以导出一个唯一的 (n + 1) 变量布尔函数。有 T(n) 2对 n 变量布尔函数，因此 (n + 1) 变量布尔函数的总数为 T(n) 2。因此 T(n + 1) = T(n) 2。

解决复发

现在，我们必须弄清楚如何解决递归

T(1) = 4

T(n + 1) = T(n) 2

这是尝试展开前几个术语的好地方：

  • T(1) = 4
  • T(2) = 16
  • T(3) = 256
  • T(4) = 65536

这些都是 2 的幂，因此对于k的各种选择，将它们重写为 2 k可能是个好主意。这样做会产生

  • T(1) = 2 2
  • T(2) = 2 4
  • T(3) = 2 8
  • T(4) = 2 16

由此看来，模式似乎是 T(n) = 2 2 n。我们可以通过归纳将其形式化：

  • T(1) = 4 = 2 2 1
  • T(n + 1) = T(n) 2 = (2 2 n ) 2 = 2 2 · 2 n = 2 2 n + 1

所以一切都检查出来了。

还有另一种思考方式。任何 n 个布尔变量的字符串都可以被认为是一个二进制数，范围从 0 到 2 n - 1。也就是说，有 n 个布尔变量有 2 n 个选择。对于这些选择中的每一个，一个函数有两个可能的输出，0 或 1。因此，您可以将 n 变量布尔函数的数量视为从一组 2 n 个元素到一组两个要素。函数在一个输入上的输出选择完全独立于函数在另一个输入上的输出选择，所以我们要做出 2 n 个独立决定是分配 0 还是 1。有 2 2 n种方法这样做，匹配之前的界限。

希望这可以帮助！

于 2014-05-22T16:24:44.710 回答