加权布尔多项式以及具有二值邏辑变量的队决策问题的解

D0I:10.13374/j.issn1001-053x.1983.02.024 北京钢铁学院学报 1983年第2期 加权布尔多项式以及 具有二值羅辑变量的队决策问题的解 计算机教研室王乘钦 摘要 本文研究了一种特殊的、但具有代表性的队决策问题。这种问题包括有二位的 逻辑变量。 文中提出了一种所谓的加权布尔多项式一它把实变量空问和逻辑变量空间联 系起来一一用来做为一种对这类队决策问题的求解方法。在讨论了加权布尔多项式 的若干重要性质之后，如完备性、正交性、增生与蛻化，作者提出了一种广义支付 矩阵（或称W矩阵）的概念。并通过一个典型的例子（协同模型）来说明它的运用 技巧。 一、队决策问题的一般提法和一个特例 队，是一个广义的组织，对其所有的成员来说，它有着共同的目标。 组织中的每一个成员可以从系统中获取各自的信息，并向系统施加各自的作用（或决 定)。它所要解决的问题是每个成员如何根据获得的信息来决定向系统施加的作用。即如何 决策，以达到共同的目标。 “共同的目标”是队决策问题的最本质性的特点。正因为如此，使它区别于博奕对策问 题。现以二人对策问题为例来说明它们之间的关系。假若局内双方各有其目标函数J:、J2。 那么： 若J1=J2,是为队决策问题， 若J:=~J2,是为零和博奕对策问题， 若J1≠J2,而且J1≠一J:,是为非零和博奕对策问题。 队决策问题对于现代控制理论，对于信息论，对于经济管理科学，对于现代的军事指挥 科学，都具有重大的理论意义。它的价值就在于它代表了近十年来系统科学家们所做的一种 势力：那就是用一个统一的观点和方法来处理上述不同领域中的一些问题一即建立一个统 一的决策理论。这些问题是：大系统理论中的分散控制问题【」，信息论中的传输通道上的 编码、解码问题，经济理论中的资源分配和市场报信问题【」·1，军事科学中的诸兵种协 同问题等。【1 在对于队决策问题给出它的准确提法之前，必须先做以下的五点说明： 1.系统中所有的不确定性的因素都归结成一个由随机变量构成的随机矢量 Market Signalng 41

北 京 钢 铁 学 院 学 报 年第 期 加权布尔多项式以及 具有二值耀辑变量的队决策问题的解 计 算机教研 室 王 秉 钦 摘 要 本文研 究 了一 种特殊 的 、 但 具 有代表性的队决策 问题 。 这种 问题 包括有二 位 的 逻 辑 变量 。 文 中提 出了一 种所谓 的加 权布 尔多项 式— 它把实 变量 空 间和 逻辑变量 空间联 系起来— 用 来做为 一 种对 这 类队决 策 问题 的求解方 法 。 在讨论 了加 权布 尔多项 式 的若 干重 要 性质之 后 ， 如完 备性 、 正 交性 、 增生与蜕化 ， 作者提 出了一 种广义 支付 矩 阵 或称 矩 阵 的概念 。 并通过 一 个典型 的例子 协同模型 来说 明它 的运用 技巧 。 一 、 队决 策问题的一 般提 法 和 一 个 特例 队 ， 是一个广义 的 组织 ， 对其所 有的成 员来 说 ， 它有着共 同的 目标 。 组织 中的每一个 成 员可 以 从系 统 中获取各自的 信息 ， 并向系统 施加 各自的 作用 或决 定 。 它所要解决的问 题是每个成 员如何根据获得 的信息来决定向系统施加的 作用 。 即如何 决策 ， 以达到共同的 目标 。 “ 共 同的 目标 ” 是队决策问 题的 最本质性的 特点 。 正 因为如此 ， 使 它 区别 于博 奕对策问 题 。 现 以二 人 对策问 题为例来说 明它们 之 间的关系 。 假若 局 内双 方各有其 目标函数 、 。 那 么 若 ， 是为队 决策问题 ， 若 一 ， 是为 零和博 奕对策问题 ， 若 子 ， 而且 沪 一 ， 是为 非零和博 奕 对策问题 。 队决 策问题 对于现代控 制理 论 ， 对于信息论 ， 对于经 济管 理 科学 ， 对于现代的 军事指挥 科学 ， 都具有重 大 的 理论意义 。 它的价值就在 于 它代表 了近十年来 系统科学家们 所做的一种 势力 那 就是 用一个统一 的 观 点和 方法来处理 上述不 同领域 中的 一些 问题 — 即建立一个统 一的决策理论 。 这些 问题 是 大系统理论 中的 分散 控制问 题 ‘ ， 信 息论 中的传输通道 上的 编码 、 解码问 题 ， 经 济理论 中的 资源分配和市场报信 朴问 题 川 ’ ‘ ， 军事科学 中的 诸兵种协 同问题 等 。 “ 在 对于队决 策问 题 给 出它的 准确提法 之前 ， 必须 先做 以 下 的五点说 明 系统 中所有的不 确定性的 因素都归结成一 个由随机变量 构成的 随机矢量 七 朴 DOI ：10．13374／j ．issn1001—053x．1983．02．024

ξ=〔51，ξ2…5m)∈2 它定意于概率空间并其有已知的分布P(),称为自然状态。因为它主要是代表了下述一 些自然因素：如系统的初始状态，外干扰，测量噪声等不确定事件。 2.对于每一个决策者DM,他所做出的决定为“；（即施加于系统的作用）。其全体 称为决定变量集 u=〔u1,u2…un)∈U 3.对于每一个决策者可做出各自的观察Z:,它是依赖于自然状态的，即Z,=门：() 并且，若各个决策者之间可以（当然是有限制地！）互相交换信息，即把自己的决定通知对 方。那么Zi的一般形式为 Z,=n:(ξ，U) vi 通常Z:是一个矢量，它是供决策者使用的信息。门：称为信息结构，它决定了信息的来源和 组成。通常它要遵循某种约束，例如某种形式的有因条件。所有的Z:全体构成观察集 Z=〔Z1,Z2…Z。)∈Z 4. 第i个决策者根据他获得的信息（或观察）Z:做出决定“：，应该遵循决策的规则 Yt,它是Z:→U:的映射 ui=Yi(Z:) vi Y:应在允许的函数集T:中选取，而上述各变量、u、Z则在相应的空间2、U、Z中取值。 5.支付函数（或损失函数）定义为 L(ξ，u）=L(u1yu2,…un,51,ξ2，…ξm) 当Y:选定后，L就是一确定的函数 L(5)=L(…u:=Y(n:(5),…5…) 按已知的分布P()取其数学期望，那么就得到某种代价的测度J, J=Ee〔L(u=Y(n(),)〕 有了上述五点说明之后，可以将队决策问题的提法叙述如下： 对于所有的i,求取Y:ET:,以便使J为最小。即求满足下式的函数集Y Minimize J=E(L(u=Y(n()),E)) (1-1) Y∈r 信息结构η对于队决策问题的解答是非常重要的。它不仅影知到决策的性质而且影响到 决策的质量。只有根据相对完善的信息，才能做出比较优越的决策。近十年来，对下述几种 信息结构已做了较充分的研究： 设H,是一个具有适当维数的常数矩阵，并且 Z,=H:ξ， vi 具有这种信息结构的问题称为静态队决策问题【2」。这时，除了共同的对于系统的先验统计 知识以外，各个成员之间没有任何的信息交换。信息的唯一来源是各自对自然状态的观察。 任一成员所做的决策都不影响其他成员的观察，因而各决策者进行观察和决策的先后次序对 于问题来说是不重要的。反之，如果决策的次序对于问题来说是一个本质性的因素，那么就 称为动态队决策问题。这反映在问题的信息结构上。若满足有因条件的矩阵D:1,使对所有 的i都有 Z,=H,5,+∑D1u1 Vi I<1 42

毛 〔 七 ， 息 · · 一 毓 〔 它定意于概 率空 间并共 有 已知 的分布 七 ， 七称为 自然 状态 。 因为 它主 要是 代表 了下述一 些 自然因素 如 系统的初始状态 ， 外干 扰 ， 测量 噪声 等不确定事件 。 对于每一个决策者 ‘ ， 他所做出的决定为 ‘ 即施加 于系统的 作用 。 其全体 称为决定变量 集 〔 ， … … 。 〕 ‘ 对于每一个决策者可 做出各 自的 观察 、 ， 它是依赖于 自然状态的 ， 即 ‘ ” ‘ 劫 并且 ， 若各个决策者之 间可 以 当然是有限制地 ， 互相交换信息 ， 即把 自己的决定通知 对 方 。 那 么 的一 般形式为 ‘ ” ‘ 七 ， 通常 ‘ 是一个矢量 ， 它是供决策 者 使用的信息 。 ‘ 称为信息 结构 ， 它决定 了信息的来源和 组成 。 通常它要遵循某种 约束 ， 例如 某种形式的有因条件 。 所有的 ‘ 全体构成观察集 〔 ， … … 。 〕 〔 第 个决策者 根据 他 获得 的信 息 或观察 ‘ 做 出决定 ‘ ， 应 该遵循决策的规则 ‘ ， 它是 ‘ 今 ‘ 的映射 ‘ 丫 ‘ ‘ ‘ 应 在允 许 的 函数集 ‘ 中选取 ， 而 上述 各变量 七 、 、 则在相应 的 空 间 、 、 中取 值 。 支付函数 或损失函数 定义为 七 ， ， ， “ 一 ， 七 ， 七 ， · ” 七 当丫 ‘ 选 定后 ， 就是一确定的 七函数 七 · · … ‘ 丫 ‘ 月‘ 七 ， … … 毛 · ” 一 按 已知 的 分 布 劫 取 其数学期望 ， 那 么就得 到某种 代价的测度 ， 。 〔 丫 毛 ， 专 〕 ‘ 有 了 上述五 点说 明之后 ， 可 以将队决策问题 的提法叙述如下 对于所 有的 ， 求取 ‘ 任 ，， 以便 使 为最小 。 即求满足下式的 函数集 〔 丫 七 ， 七 一 〔 信 息结构 月对于队决 策问题 的解答是 非 常重 要 的 。 它不仅影知到决策的性 质而且影响到 决策的 质量 。 ‘ 只有根据 相 对完善的信 息 ， 才能做 出 比较优越的决策 。 近十年来 ， 对下述几种 信息结构 巳做 了较充分的 研 究 设 ‘ 是一个具有适 当维数的常数矩阵 ， 并且 ‘ ‘ 七 ， 具有这种信息结构 的 问题 称为静态队决 策 问题 】 。 这 时 ， 除 了共 同 的对于系统的先验统计 知 识 以外 ， 各个成员之 间没 有任何的信息交换 。 信 息的 唯一来源是 各 自对 自然状态 的 观察 。 任一成员所做的 决 策都不影响其他成 员的 观察 ， 因而各决策者进行观察和决策的 先后 次序 对 于问题来说是 不重 要的 。 反 之 ， 如果 决 策的 次序 对于问题来说是一个本质性的 因素 ， 那 么就 称为 动态队决策问题 。 这反映 在 问 题 的信息结构 上 。 若满足有 因条件的 矩阵 门 ， 使 对所有 的 都有 ‘ 七 门

其中j<i,而且所有的D:1≠0，而D,1=0。上式称为完善记忆型信息结构【21。它意味着应 史上曾施加给系统的作用全部都提供做为当前的信息。可以证明，线性随机控制的LQG问 题就可以化成具有这种信息结构的队决策问题。若将上式推广，对于所有的而言，只是部 分的D1,中0，（当然仍然是在j<i,且D,1=0的条件下）。它意味着：若两个决策者存在 着先后次序关系，那么先行者知道的信息也必为其后继者所知道。即 Z1=H,5:+D1,u1 j( 这种信息结构称做部分嵌套结构。2！，〔】 部分嵌套结构包括了相当广泛的信息结构类型，如“一步延迟信息共享”结构和“分层” 结构。在大系统问题中它们都是典型的信息结构。若从一个统一的观点来看，它们都不过是 部分嵌套结构的特例而已。 经过近二十年的努力已经得出结论：对于上述所有的信息结构类型，队决策问题(1-1) 式的解u=Y(Z)都是线性的。【1，【1如果注意到前面所提到的在控制理论、信息论、经济管 理和军事科学中的许多问题都可以归结成对(1-1)式求解，而(1-1)式对于上述五种信息结 构的解又都是线性的，那么应该说：通过队决策问题的研究，跨学科地建立一个统一的决策 理论的努力是有成效的！早在1969年，文献7]提出了建立普遍控制理论的目标无疑是卓越 的、迷人的，近十年的进展也是令人鼓舞的。然而，要达到这一目标尚须要跨过一个未曾被 探索过的领域：即决策u的逻辑蕴含方面。迄今为止，决策问题，无论是队决策问题也好， 或者是博奕对策问题也好，论讨中所涉及的变量都是做为实变量来考虑的。例如本文前面所 提到的、Z、“集的元素都是实变量，它们都在实空间2、U、Z上取值。然而，决策过程远 非如此简单。譬如说，人们在做出决定u之前，首先要考虑的不是“应该施加多少作用”， (即u做为实变量如何取值)，而是首先要考虑“是否应该施加作用”，（即u做为布尔变 如何量取值)。决策者是做决定时，必须是先回答“是否”？，然后才是回答多少？。 “多少”，只有在“是”的前题下，才能算得上是正确的定量作用。在一个复杂的对局中， 拒绝做出反应(“否”)往往具有重大的策略价值。“沉默费如黄金”！沉默，它有时甚至 是唯一正确的决策。 过去，对快策问题的研究完全忽略了决策的形式逻辑方面的特点，因而研究工作总是局 限在泛函分析的框架之内。今天，只有冲破这个框架，丝毫不因数学上的困难而回避决策问 题的形式逻辑方面的特点，并寻求新的数学工具来概括这些特点。那么，也许决策问题的研 究会因此而出现一个新的局面。 为了突出这一特点，下面举出一个队决策问题的例子。它所涉及的变量、Z、“不是实 型的而是逻辑型的。这个著名的例子是由哈佛大学的何(Y.C.HO)给出的，其背景是一个 军寧协同问题。【) 住在B市的B先生和住在H市的H先生，因为业务上的需要约定于第二天在W市会面， 如果届时W市是晴天的话。从他们约定之后到他们第二天会面之前，由于种种原因他们是不 能直接通讯联系的。当第二天早上B先生和H先生从各自的城市准备出发时，W市的气象情 况是否为晴天完全是一个随机事件。不果他们两人是可以从各自的城市得到当地的气象情 报，而B、H、W三个城市的气象情况又是相关的。他们会面的性质要求，必须是双方在晴 天到达W市为最佳，而一方到达另一方不到，或者双方都到但W市为雨天，这都是不利的。 这可用支付矩阵（狭义的）表示如表1

其 中 ， 而且所 有的 ，笋 。 ， 而 ，， 。 上式 称为 完善记忆型 信 息结构 【 。 它意味着应 史 上 曾施加 给 系统 的 作用 全部都 提供 做为 当前 的 信 息 。 可 以 证 明 ， 线性随机 控 制 的 问 题 就可 以 化成具有这种 信 息结构 的队 决策问题 。 若 将 上式 推广 ， 对于所有的 而言 ， 只是部 分 的 ，笋 ， 当然仍然是 在 ， 且 ， 。 的 条件下 。 它意 味着 若两个 决 策者存在 着先后 次序关系 ， 那 么先行者 知 道 的信 息也 必为 其后 继者所 知道 。 即 七 艺 ， ， ， 这种信息结构称做部分嵌套结构 。 ， 〔吕 部分嵌套结 构包括 了相 当广 泛的信息结构类型 ， 如 “ 一步 延迟信息共享 ” 结构和 分层” 结构 。 在大系统问 题 中它们 都是典型 的信息结构 。 若 从一个统一的 观 点来看 ， 它们 都不过是 部分嵌套结构 的 特例而 巳 。 经 过近二十年的 努力 已经得 出结论 对于 上述所有的 信息结构类型 ， 队 决策问题 一 式 的解 丫 都是线性 的 。 〔 ， “ 如果 注意到前面 所提到的在控制理论 、 信息论 、 经济管 理 和 军事科学 中的 许多 问题都可 以归结 成 对 一 式求解 ， 而 一 式 对于 上述五种信息结 构 的解又都是线性 的 ， 那 么应 该 说 通 过队决 策问题 的 研究 ， 跨 学科地建立一 个统一 的决策 理论的努力是有 成效的 早 在 年 ， 文 献 提 出了建立普 遍 控制理论 的 目标无疑 是卓越 的 、 迷 人的 ， 近十年的进 展也是 令人 鼓舞的 。 然而 ， 要达到这一 目标 尚须 要跨过一 个未曾被 探索过 的领域 即决 策 的逻 辑蕴 含方面 。 迄今为止 ， 决策问题 ， 无论是 队决 策问题 也好 ， 或者是博奕对策问 题 也好 ， 论讨 中所涉及 的 变量 都是做为实变量 来考虑的 。 例如 本文前面所 提到的 息 、 、 集 的元素都是 实变量 ， 它们 都在实空 间 、 、 上取 值 。 然而 ， 决 策过程远 非如此 简单 。 譬如 说 ， 人们 在做出决定 之前 ， 首先要 考虑的 不是 “ 应 该 施加 多少作用” ， 即 做为实变量 如何取 值 ， 而是 首 先要 考虑 “ 是 否应 该 施加 作用” ， 即 做为布尔变 如 何量取 值 。 决 策 者是 做决定 时 ， 必 须是 先回答 “ 是 否” ， 然后才 是 回 答多少 。 “ 多少 ” ， 只 有在 “ 是 ” 的前题 下 ， 才 能算得 上是 正确的定量 作用 。 在一个复杂的 对局 中 ， 拒绝做出反应 “ 否” 往往具 有重 大 的 策略价 值 。 “ 沉默贵如黄 金” 沉默 ， 它有时甚 至 是 唯一正确的决 策 。 过去 ， 对决 策问 题 的 研 究完全 忽略 了决 策 的形式逻 辑方面 的 特点 ， 因而研 究工 作总是局 限在泛 函分 析的 框 架之 内 。 今天 ， 只 有 冲破这个 框架 ， 丝毫不 因数学 上的 困难而回避决策问 题 的形 式逻 辑方面 的特点 ， 并寻求新 的数 学工具来概 括这些 特点 。 那 么 ， 也许决 策问题 的 研 究会因此 而 出现一 个新 的 局面 。 为 了突出这一 特点 ， 下面 举 出一个队决策问 题 的例 子 。 它所涉及 的 变量 息 、 、 不是实 型的而是逻辑型 的 。 这个著 名的例 子是 由哈佛大学 的何 给 出的 ， 其 背景是一个 军事协同问题 。 住在 市的 先生 和住 在 市 的 先生 ， 因为 业务 上的 需要 约定于 第二天在 市 会面 ， 如果届 时 市是 晴天 的话 。 从他们 约定 之后 到他们 第二天会面 之前 ， 由于种 种原因他们是不 能直接 通讯联系 的 。 当第二天早 上 先生 和 先生从各 自的城市 准备出发时 ， 市 的气 象情 况 是 否为 晴天 完全是一个随机事件 。 不果 他们 两 人是可 以从 各 自的城市 得 到 当地 的气象情 报 ， 而 、 、 三个城市 的气 象情 况 又是相 关的 。 他们 会面 的性 质要求 ， 必须是双方在晴 天到达 市为最佳 ， 而一 方 到达 另一方 不 到 ， 或者双 方都到但 市为雨天 ， 这都是 不利的 。 这可 用 支付矩阵 狭义 的 表示如表

表1 Ew 0 0 0 1 un 0 0 1 1 0 0 1 UH 0 1 0 1 0 L 5 -2 -2 4 0 -3 3 10 其中： w:为W市的气象，它是一个不确定事件。由于是以“晴天”或“雨天”来描述气象的， 所以是一个二值的逻辑变量。用“1”代表晴天，·“0”代表雨天。 u,uH:为B、H两人的决定。也是二值的逻辑变量。“1”代表出发去W市，“0” 代表不去。 L:为支付或代价（本题中为增益），取实数值。 应该注意的是，逻辑变量的取值0、1与L的实数值0,1完全不同，它们是逻辑值。 对于B、H二人所提出的问题是：各自是否决定向W市出发。三个城市的气象情况是互 相关联的，5w、号、5H三个二值随机逻辑变量的联合概率分布如表2所示。 这一问题的特点在于两个决策者所得到的信息是互相关联的。设想一下B、H、W三城 市相距很远以致三城市的气象情况是毫不相关的，那么ξ、“对于决策者来说就毫无用处， 而W又是未知的，那么这就失去了现场观察信息的来源，决策问题就只能靠对W市的气象的 先验统计知识所给出的期望值来解决。这一问题的另一点在于每个决策者在做出决策时必须 考虑到其同伙可能会做出的决定，以便共同的支付函数取得极值。假若失去了这两个特点， 问题就被解耦而简化了。 表2 Ew 0 0 0 EB ① 0 EH 0 I 0 0 0 1 P 0.25 0.1 0.1 0.05 0.05 0.1 0.1 0.25 现在针对这一特例，参照一般提法的五个要点，给出这一问题的数学形式如下： 这是一个静态队决策问题，其信息结构为 Z=n() 快策规则为 u=Y(Z) J=-2L(uB,u5m)p(店nEn、5m） 求Y∈「，使得期望支付取最大 J=Maximize J (1-2) 此处Y具有如下形式 un=YB(EB) (1-3) uH=YH(ξH) 44

表 。 … 几 。 】 ， ， ， … ， … 。 。 … … 。 。 。 】 … 。 ， 一 一 一 。 。 二 上二 … 一 一 … 其 中 七 为 市的气象 ， 它是一 个不确定事件 。 由于是以 “ 晴天 ” 或 “ 雨天 ” 来描述气象的 ， 所 以 肠是一 个二 值 的 逻 辑 变量 。 用 ，’ ” 代 表晴天 ， ’ ” 代 表雨天 。 。 ， 。 为 、 两 人 的 决定 。 也是二值 的逻 辑变量 。 ，’ ” 代表出 发去 市 ， ” 代表不去 。 为 支付 或代价 本题 中为 增益 ， 取实数值 。 应 该 注意的 是 ， 逻 辑 变量 的取 值。 、 与 的实数值。 、 完余不 同 ， 它们是逻辑值 。 对于 、 二人所提 出 的问 题是 各 自是 否决 定向 市出发 ， 三个城市的气象情况是互 相关联 的 ， 毛 、 是。 、 履 三个二值 随机逻 辑 变量 的联 合概率分布如表 所示 。 这一问题 的特点在 于两 个决策者所 得 到的信 息是互 相关联 的 。 设想一下 、 、 三城 市相距 很远 以致 三城市的气 象情况是毫 不相关的 ， 那么 邑 。 、 七 对于决策者来说就毫 无用 处 ， 而 七禅又是未知 的 ， 那 么这就失去 了现场 观察信息的来源 ， 决策问题就只能靠对 市的气象的 先验统计知 识所给 出的期望 值来解决 。 这一问题的 另一 点在于每个决策者在做出决策时必须 考虑 到其 同伙可 能 会做出的决 定 ， 以便共同的 支付 函数取得 极值 。 假若失去了这两 个特点 ， 问 题 就被解 藕而简 化 了 。 ， 表 ， ， 甘 】 】 一 一 刁叫户 一 一 ， 一 一 ，， 叫 」 ’ 】 】 现在针 对这一 特例 ， 参照一般提法 的五个要 点 ， 给出这一问题的数学形式如下 这是一 个静态队决策问题 ， 其信 息结构为 决策规则为 七 ， 艺 。 、 。 、 七，， · “ 卜 息 。 、 “ ， 枯 求 丫 〔 ， 使得期望 支付取 最大 二 此处 丫具有如下形式 。 七 。 。 毛 。 一 一

为了理论上的兴趣，还可以把问题扩展一下，即每一个决策者不仅可获得本城市的气象 观察而且还可以获得其同伙所在城市的气象观察。即在： uB=YB（5B,EH) uH=YH(ξH,5B) (1-4) 的条件下求解(1-2)式。 由于和u都是二值的逻辑变量。形式如(1-3)式的解空间Γ是由16种函数“对”构成。 原则上讲，可以逐个地许算这16种情况下的J值，然后选取最大者即可获得解答。至于形式 如(1-4)式的解，以后可以证明，其解空间是由256个函数“对”构成。由此可见求解过程 的计算工作是很繁重的。若仍然逐个地计算J值，甚至是行不通的。 特别应该强调的是，这里的问题不是求解过程的难易、繁简问题，而是为了理论上的目 的，是否能寻求到一个适当的数字工具来概括这种具有逻辑变量的队决策问题的求解过程。 或者说，这里所迫求的目标是从逻辑的目度，为队决策问均寻求理论基础。 关键是，这一数学工具要能够把二值的逻辑变量和实质变量联系起来。 上面提到的两位先生会面的队决策问题是一个具有代表性的特例。在这一特例中所有 的变量都是二值的逻辑变量，而支付函数却是在实空间上取值。下一节就来讨论解决这种决 策问题的数学工具一加权布尔多项式。并研究它的若干有趣的性质和使用这一工具的技 巧。 二、加权布尔多项式以及它的若干性质 本节中将给出关于加权布尔多项式的六个定理。定理1=5只给出证明要点。而定理6，这 也是最重要的一个，将给出详细的证明。 考虑N个布尔变量，以后称其为逻辑变量： 1=1,2…N 它们中的每一个，都在集合{0,1}上取值。当所有的：的值给定之后，可以得到一个有序的 (按照！从1到N的次序)逻辑值的组合，称之为一个“点”。例如： (ξN=0,ξN-1…ξ1=1)a(01…1) 那么(01…1)就是一个点。所有的这样定义的点的集合，构成一个N维逻辑变量空间， 记做 {}={ENξ-1…ξi} 定理1.N维逻辑变量空间中，点的总数是2个。 证明要点，做一个N位的二进制数DN, DN=dndN-1…d 让其中的每一位二进制数d,(1=1,2…N)对应于一个（二值的)逻辑变量1。做为一个二 进制数的D,由数制的理论知，它所最多可能的取值于互相区别的数的总个数是2个，即从 00…0到111。所以与DN对应的空间{5，}必具有2w个点。于是定理得证。 N维逻辑变量空间具有可数的点数2个。称之为其容积。这一点是和实变量构成的空间 不同的。实空间的点是不可数的。 对N个逻辑变量进行与(*)、或（①）、非(-)的逻辑运算，就得到一个布尔函数B B=B(专N,ξN-1,…51) 5

为 了理 论 上的兴 趣 ， 还可 以把问题 扩展一 下 ， 即每一 个决策者不仅可 获得 本城市的气象 观察而且还可 以 获得 其 同伙所 在城 市的气 象观 察 。 即 在 。 。 七 。 ， 七 一 。 。 七 ， 七 的 条件下求解 一 式 。 由于 七和 都是二值的 逻 辑变量 。 形 式如 一 式 的解 空 间 是 由 种 函数 “ 对 ” 构成 。 原则 上讲 ， 可 以逐个 地 许算这 种倩况 下的 值 ， 然后选取 最大 者即可 获得解答 。 至 于形式 如 一 式的解 ， 以后可 以证 明 ， 其解空 间 七是 由 个函数 “ 对 ” 构 成 。 由此可 见求解过程 的计算工 作是很繁重 的 。 若 仍然逐个地计算 值 ， 甚至 是 行 不通 的 。 难 特别应 该 强调 的是 ， 这里 的问 题 不 是 求解过 程 的难易 、 繁简问题 ， 而是为 了理论 上的 目 的 ， 是 否能寻求到一 个适 当的数 字工具来概括这种具 有逻 辑变量 的队决 策问题的 求解过 程 。 或者说 ， 这里所迫求的 目标是 从逻辑 的 目度 ， 为 队决 策问 均寻求理论基础 。 关键是 ， 这一数 学工具 要能够把 二值 的 逻辑变量 和实质变量 联 系起来 。 上面 提 到 的 两 位 先生 会面 的队 决 策问 题是一 个具有代 表性 的 特例 。 在这一 特 例 中所有 的 变量都是 二值 的 逻辑 变量 ， 而 支付函数却是 在实空 间 上取值 。 下一节就来讨论解决这种决 策问题 的 数学工具 —加权布 尔多项 式 。 并研究它 的若干有趣的性质 和使用 这一工具 的技 巧 。 二 二 、 加权 布尔多项 式 以 及 它的若干 性 质 本节 中将给 出关于加 权布尔多项式 的 六个定理 。 定理 巧只 给 出证明要点 。 而定理城 ， 也是最重要 的一 个 ， 将给出详细的 证 明 。 考虑 个布尔变量 ， 以后 称 其为逻辑 变量 几 七 ， ， · · 一 这 它们 中的 每一 个 ， 都在集合 诬 ， 卜上取 值 。 当所 有的 毛 的值 给 定之 后 ， 可 以得 到一个有序 的 按照 从 到 的 次序 逻辑值 的 组 合 ， 称之为一 个 “ 点 ” 。 例如 息 ， 毛 … … 息 卜 · · … 那么 … … 就是 一个 点 。 所有 的这样 定义 的 点的 集合 ， 构 成一个 维逻 辑 变量 空 间 ， ， 记做 遥七 “ 王七 七、 … … 七 定理 维 逻辑 变量空 间 中 ， 点的 总数是 付个 。 ， ” · 证 明要 点 做一 个 位 的二进 制数 ， ’ ” ” · 、 让其 中的每一 位二 进 制数 二 ， · 、 … 对应 于一个 二值 的 逻 辑变量 息 。 做为一个二 进制数的 ， 由数制 的 理论知 ， 它所最多可 能 的取 值 于 互相 区别 的数 的 总个数是 个 ， 即从 · · … 到 卜 · · … 。 所 以与 对应 的空 间佳 必具有 个点 。 于是 定理得证 。 维逻辑变量 空 间具有可数 的 点数 个 。 称 之为其容积 。 这一 点是 和 实变量 构成 的空卿 不 同的 。 实空 间的 点是 不可 数的 。 对 个逻 辑变量 进 行 与 勺 、 或 ① 、 非 一 的 逻 辑运 算 ， 就得 到一个布尔函数 二 虽 ， 七、 ， … … 毛

B(“)又称布尔算子。显然函数B仍然是在{0,1}集上取值。 下面引用数理逻辑中的一个定理。！，1山 定理2.任一布尔函数B(N,5心1，…1)，都可以唯一地展开成如下的析取规范形式 2N-1 51=y①B1( (2-1) 1=0 (5N5N-1…)是第i个合取项。合取项是N个因子的逻辑积，其每个因子取自！或 者1（按1=1,2…N次的次序）。例如N=4,那么(E,*9*2号1)就是i=1001（二进制 数表永)，或i=9(十进制数表示)的合取项。 (5,5,…5),■(5050写051)简记为(5，写3E:51) (2-1)式中B1是布尔函数在i点的值（显然B,或为0，或为1）。例如i=9(或i=1001), 就是5。=1，E3=0,52=0,ξ1=1的点，对应于该点的函数值就是B,即 B。=B(1,0,0,1) 符号①表示连续的或运算（又称逻辑连加）。 由定理2，可以得到以下三个推论。 推论1：如果布尔函数在N维逻辑变量空间中某一点处的值为0，则其规范展开式中没有 相应的合取项。 举例来说，若B。=0,则其析取范式中就没有(，，25：)项。 推论2：如果布尔函数在N维逻辑变量空间中所有点上的值皆为1，则其析取范式中含有 全部2N个合取项。 由此联系到定理1，可知，析取范式中的每一个合取项唯一对应于逻辑空间中的一个点。 推论3：如果一个布尔函数规范展开式如(2~1)，那么其“非”式的规范展开式如下 2N-1 B(5N,51…5)=了①B1*(5N5N1…5)1 t■0 为以后的讨论在语言的方便，特做如下的定义。 定义：如果布尔函数的析取范式中含有全部2个合取项，则称它是完备的。并把这种规 范展开式称为完备的布尔多项式。 有了以上的准备之后，下面来讨论加权布尔多项式。加权布尔多项式实质上就是定义在 N维逻辑变量空间上的实函数。 首先来定义实数a与逻辑变量u的“乘积” W =a.u 它定义为一个实函数，与逻辑变量u的对应关系如下， 如果u=1 W0, a 如果u=0 (2-2) 注意逻辑0与实0不能混淆，这里对u的唯-一要求就是它在集合{0,1}上取值，所以u可理解 成任何的逻辑表达式。例如“是几个逻辑变量的逻辑积。 设一个由实数构成的有序数组A A={80,a1…ak…} 用它的每个数分别乘布尔多项式的每个合取项，然后取代数和，这就得到一个加权布尔多项 46

护 又 称布尔算子 。 显然函数 仍然是在 福。 ， 卜集上取 值 。 下面 引用数理 逻辑 中的一 个定理 。 ‘ 。 定理 任一布尔函数 如 ， 七、 ， 一 玉 七 ， 都可 以 唯一地 展开 成如下 的析取 规范形 式 ” ‘ 毛 “ ， 七 ’ ” ” ’ 如 ’ 艺④“ ’ ‘ 七七 ’ “ ’ ” 劫 ’ 一 七 七 一 … … 七 是第 个合取项 。 合取项是 个 因 子的 逻辑积 ， 其每个因子取 自如 或 者乙 按 二 ， · · … 次的 次序 。 例如 ， 那 么 息 ‘ 盯 牙 七 就是 二进 制 数表示 ， 欢 二 十进制数表示 的合取项 。 七 ‘ ， 七 ， …… 七 二 七声砚 毓 七 简记为 毛 瓦 飞 乙 一 式 中 是布 尔函 数在 点的值 显然 ，或为 ， 或为 。 例 如 或 ， 就是 七 ‘ ， 七 。 ， 七 ， 七 的 点 ， 对应 于该 点的 函数值就 是 ， 即 一 ， ， ， 符号艺曰 表示 连续的 或运算 又 称逻辑 连加 。 由定理 ， 可 以得 到以下三个推论 。 推论 如果布尔函数在 维逻辑变量 空 间 中某一 点处的值为 ， 则 其规范展开式 中没 有 相应 的 合取项 。 举例来 说 ， 若 。 二 ， 则 其析取范式 中就没 有 七 七 七 息 项 。 推论 如果布尔函数在 维逻 辑变量 空 间中所 有点上的值 皆为 ， 则 其析取 范式 中含有 全部 ” 个合取项 。 由此联系到定理 可 知 ， 析取范式 中的每一个合取项唯一 对应 于逻 辑空 间 中的一个点 。 推论 如果一个布尔函数规范 展开 式如 一 ， 那 么其 “ 非 ” 式 的规范展开 式 如下 一 七 ， 七、 ， … … 毛 艺④ “ ·’ ‘流 一 ” ” ” 孰 ’ 为 以后的讨论在语 言的方便 ， ’ 特做如下的 定义 。 定义 如果布尔函数 的析取范式 中含有全部 个 合取 项 ， 则 称它是 完备 的 。 并把这种 规 范展开 式 称为完备的布尔多项式 。 有 了以 上的 准备之后 ， 下面来讨论加权布尔多项式 。 加权布尔多项式 实质上就是 定义 在 维逻辑变 空 间 上的实函数 。 首先来定义 实数 与逻辑变 的 “ 乘积 ” 一 它定义为一个实函数 ， 与逻 辑 变量 的 对应 关系如 下 如果 如果 二 一 ‘ 八 一 ‘ 注 意逻辑 与实 不能 混淆 ， 这里 对 。 的 唯一要求就是 它 在 集合 扣 ， 上取 值 ， 所 以 可 理解 成任何的 逻辑表达式 。 例如 是几个逻辑 变量 的逻辑积 。 设一个 由实数构成的有序数组 。 ， … … ‘ … … 用 它 的每个数分别 乘布尔多项式的 每个合取项 ， 然后取代数和 ， 这就得到一个加权布尔多项

式。a是其第k项的权系数。而且，说一个加权布尔多项式是完备的，如果它所对应的布尔 多项式是完备的。也就是说，加权布尔多项式的完备性是以其对应的布尔多项式的完备性来 定义的。显然，完备的加权布尔多项式具有以下的形式： u(A)=ao(写N5M-1…号)+a1(5N号w1…专，)+…+ 2N-1 a2N-1(5N名1…5)=∑a1(店N5N1…专)1 (2-3) 0 不难看出，它是定义在N维逻辑变量空间中的实函数。对于空间中的每一点都有、而且也仅 有一个权系数与之对应。并且把 2N-1 WT=∑a: fg} (2-4) 1=0 称为“(A)在其定义空间内的总权重。 在讨论加权布尔多项式的运算之前，先定义只有一个单项情况下的加法和乘法运算。 设a、b为两个实数。u1、“z为两个逻辑变量，由(2-2)式的定义知 W.=aui,W。=b·uz 定义“加”：W,+W,记着W,+b W。+b=au1+bu2 (2-5) 特别是当W。、W。具有同一个定义空间，即当u1=“z=u时，上式成为 W。+b=(a+b)·u 定义“乘”，W。×W记做W.xb(或W.b) W。xb=(a×b)(u1™uz) 简记为ab·(u1uz) (2-6) 这时，乘积的逻辑空间增大成二维的。当然若u!=42=u则 W.xb=(a×b)u 由于上述的“加”、“乘”定义和已知的实数加、乘运算和逻辑的“或”、“与”运算 的规定，是无矛盾的、互相协调。这就使帅权布尔多项式具有许多有价值的性质和非常简明 的运算规则。 为了以后在叙述上的方便，特规定以下的符号。 设有序的实数组A、B A={a0,a1…ag…} B={bg,b…bk…} 则符号A+B,A×B分别表示下述数组 A+B={a。+b。,a1+b1…ak+bt…} AXB={a0Xbo,a1Xb1,…xbk…} 定理3.（选加原理）设有定义在同一个N维逻辑变量空间上的完备的加权布尔多项式 u(A)、u(B),则 u(A)+u(B)=u(A+B) (2-7) 这一定理的正确性是很明显的，证明从略。这是布尔多项式的一个重要性质。 定理4.：（正交原理)设从上述的完备加权布尔多项式u(A)中取出第i项， 47

式 。 是 其第 项 的权系数 。 而且 ， 说一个加 权布尔多项式是完备的 ， 如果 它所对应 的布尔 多项式是完备的 。 也就是 说 ， 加 权布尔多项式 的完备性是 以其 对应 的布尔多项式 的 完备性来 定义 的 。 显然 ， 完备的加权布尔多项式具有 以下的形 式 二 。 七 七、 · · 一 息 七 七、 · ” … 七 · · 一 一 。 一 ， ‘ 、 … … “ ， ‘ 艺 一 … … ， “ 不难看出 ， 它是定义 在 维逻辑 变量 空 间 中的实函 数 。 对于空 间 中的每一点都有 、 而且也仅 有一个 权系数与之 对应 。 并且把 二 福 一 称为 在其 定义 空 间内的总权重 。 在讨论加权布尔多项式的运 算之前 ， 先定义只有一个单项情况 下的加法和果法运算 。 设 、 为 两个实数 。 、 。 为两个逻辑变里 ， 由 一 式的 定义 知 一， 。 一 定义 “ 加 ” 。 十 。 记着 。 ， 。 。 二 · · 一 特别是 当 。 、 。 具有同一个定义空 间 ， 即 当 时 ， 上式成为 。 、 一 定义 乘 ” 。 。 记做 、 或 。 。 。 。 一 简记为 一 这时 ， 乘积 的逻辑 空 间增 大成二维 的 。 当然若 二 则 二 、 一 由于 上述的 “ 加 ” 、 “ 乘” 定义 和 已知的 实数加 、 乘运算和 逻辑 的 “ 或” 、 “ 与” 运算 的规定 ， 是 无矛盾的 、 互相协调 。 这 就使加权布尔多项式具有许多有价值 的性质和 非常简明 的运 算规则 。 为 了以后在叙述 上的方便 ， 特规定 以下的符 号 。 设有序 的 实数组 、 二 。 ， … … … … 卜 二 魂 ， ，… … … … 卜 则符号 ， 分 别 表示下述数组 毛 。 ， … … ‘ … … 。 。 ， ， … … … … 定理 迭加原 理 设有定义在同一个 维逻辑变 空 间 上的完备的加权布尔多项式 、 ， 则 一 这一定理 的正 确性是很 明显的 ， 证明从略 。 这是布尔多项式 的一布甲重要性质 。 定理 正交原理 设 从 上 述 的 完 备加权 布尔 多项式 《 中取 出 第 项

a!(N…ξ)1，从u(B)中联出第i项，b,(5NN-1…专)1，则两者的乘积为 a1（5N5-W,xb,(5w54…E,={0 i中j 1arb,(5w5N1…5:)1i=j (2-8) 证明要点，由(2-6)式知 a1(5N5N-1…5:),Xb,(5N5N-1…51), =(a1Xb,)X(5N5N-1…ξ)10（ξN5N-1…51)1) 若i中，则逻辑积中： 〔（ξNξN-1…51)10(5NEN-1…E1）,) 至少存在一对互斥的因子51*，所以该逻辑积恒等于0，函数值（实值)也就恒等于0。 若i=j,则根据逻辑运算的吸收律，该逻辑积就等于（w5N-1…号：)！本身，而权因子成 为a1b,。于是定理得证。。并且当u(B)=u（A)时，定理4亦真。 该定理给出了加权布尔多项式的另一个重要性质。就是，它的各个项之间是两两正交 的。换句话说，加权布尔多项式一定是正交多项式。并由此而得到一个重要的推论： u(A)×u(B)=u(A×B) 根据以上对加权布尔多项式的性质的讨论，不难证明下述的运算规则： 设完备的加权布尔多项式u(A)、u(B)、u(C),它们具有共同的定义空间， (1)交换律 u(A)+u(B)=u(B)+.(A) u(A)×u(B)=u(B)Xu(A) (2)结合律 ..u(A)+u(B)+u(C)=u(A)+(u(B)+u(C)=(u(A)+u(B)+u(C) u(A)×u(B)×u(C)=u(A)×(u(B)×u(C))=〔u(A)×u(B)Xu(C) (3)分配律 u(A)X(u(B).tu(C)=u(A)×u(B)+u(A)×u(C) 下面来讨论定义在不同逻辑变量空间中的两个加权布尔多项式的运算，特别是它的果运 算。 首先考虑加权布尔多项式u(A)与一个单项Wc的乘积。设a1、c为实数，1、门为逻辑 变量，则 2N-1 u(A)=∑a(5N5N-…5: Wc=c·I 那么必有如下的等式成立 2N= 2N-1 )x(en）=∑(a1xc)(5x-4…5)*n =0 (2-9) 并把等式左端记做· 48

， 息 。 争 · · … 如 ， 从 中取 出第 项 ， ， 七 七一 … … 七 ，， 则两者的乘积为 价 七 七 一 · …… ‘ ， 毛 七、 、… … 七 ， ， 毛 七、 … … 七 二 ‘ 、‘ 、 一 一 证 明要 点 ， 由 一 式知 七 七 一 … … 七 ， 七凡 七 一 … … 七 ， 二 ， ， 火 七。 七 … … 息 ， 七 七 一 … … 七 ， 〕 若 户声 ， 则 逻揖积中 以 七 七 一 … … 毛 ，一 七 七 一 … … 毛 ， 至 少存在一 对互斥的 因 子 七 乙 ， 所以该 逻辑积 恒等于。 ， 函数值 实值 也就恒等于。 。 若 ’ ， 则 根据逻辑运 算的吸 收律 ， 该 逻 辑积 就 等于 标 七 、 一 … … 七 ，本身 ， 而 权因子成 为 。 于 是 定理得 证 。 。 并且 当 时 ， 定理 亦真 。 该定理 给出了 加权布尔多项式 的 另一 个重 要性 质 。 就是 ， 它的 各 个项之 间是 两 两正交 的 。 换句话 说 ， 加 权布尔多项 式一 定是正交多项式 。 并由此而得 到一 个重 要的推论 。 ， 根据 以 上对加 权布尔多项式的性 质的讨论 ， 不 难证 明下述的运 算规则 设完备的加 权布尔多项 式 、 、 ， 它们 具有共同的 定义 空 间 ， 交换律 ‘ 结 合律 。 〔 丫 “ 》 分配律 不 久七 〕 。 ‘ ， 下面来讨论定义 在 木向逻辑变量空 间中的两个加权布尔多项式 的运 算 ， 特别是它的乘运 算二 ’ 首先考虑加 权布尔多项 式 与一个单项 。 的 乘 积 。 设 、 为实数 ， 七 、 ” 为逻辑 变量 ， 则 一 ‘ 艺 “ “ “ 一 … … 七 ， 犷 一 那 么必有如 下 的 等式成立 一 盲 睿礼 … … 一 “ ‘， ， 又‘ 。 二，· 互 ‘一 ， · 〔 ‘ · ‘一 ’ ‘ ’ “ ’ ’ ” 一‘︺ 了吸、 、 一 并把等式 左端记做

2N-1 u(A)xWc= tE 0 (2-9)式的正确性是很容易验证的。根据(2-2)、(2-3)式的定义：(2-9)式左端是两个实 数的乘积，而右端是一个定义在{专：|.1,2…，n}空间上的加权布尔多顶式（不过，它是 不完备的)，当然也是一个实函数。当逻辑变量的取值使 (ξNξN-1…5)1=15门=1. 注意此处下标：为一确定的数。由于逻辑空间中的点唯一地对应于·个合取顶，那么上述取 值对于j中i的项必然有 (5N5N-1…51),=0影门=1 由此，(2-9)式两瑞皆为a:×c。而其他取值情况 （ξNξN-1…ξ)1=1；n=0 (ξNξN-1…ξ)，=0；1=0 (2-9)式两端皆为0。既然在逻辑变量任何取值情况下，(2-9)式两端皆相等，所以它是一个 恒等式。特别是当c=1时，(2-9)式成为 2N-1 2N-1 ∑a1(5N5N-t…5）×(1)=∑a1(5x5-…5)*n(2-10) 1-0 这一关系式以后要引用。 以下来考虑两个完备的、但定义在不同逻辑空间上的加权布尔多项式的乘积。 设有m个变量构成m维逻辑变量空间，及定义在该空间上的元备加权布尔多项式P(α) 2m-1 P(a)=∑a1(55m-1…5, 另有n个u变量构成n维空间，定义在该空间上的元备加权多项式是L(B) 2n-1 L(B)=∑B,(unun-…u), 10 两者的乘积 2m-1 Gw)=P(a)xL(B)=（∑a1(55-4…),g 2n-1 x(∑B,(uu4…u),） 由于多项式P(α)、L(B)的每一项都是一个实函数，两者相乘当然满足分配律。现付下标为 j的项，逐项引用(2-9)式，并今C=B,门=(unu-1…u)1,然后再对j取和即得到 2-12m-1 (W)= 由子G()的每一项都是实数，取和的先后次序可以交换。因而得到 49

一 。 、 · 。 二 艺一 一 · ‘二 。 一 式的 正确性 是 很容 易验证的 。 根 据 一 、 一 式 的 定 义 ， 一 式 左端是 两 个实 数 的 乘积 ， 而右 端是一个 定义 在 是， 。 ， … … 、 ， 心 空 间 上 的 加 权布 尔多项式 不过 ， 夕已是 不 完备 的 ， 当然 也是 一 个实 函 数 。 当逻辑 变量 的取 值 使 七 息 一 ， · · … 邑 ， ， ，’ 注 意此 处下 标 为 一 确 定 的 数 。 由于 逻辑 空 间 中的 点 唯一 地 对 应 于一 个 合取 项 ， 那 么上 述取 值 对于 祷 的项 必 然有 息 邑 一 ，… … 邑 ， 月 由此 ， 一 式 两 端 皆为 。 。 而其 他取 值情 况 七 乞 一 … … 七 卜 · 七 冬 … … 邑 ， 二 ，飞二 一 式 两端 皆为 。 。 既然 在 逻辑 变量 任 何取 值 情况 下 ， 一 式 两端 皆相 等 ， 所 以 它是一 个 恒 等式 。 特 别 是 当 。 时 ， 一 式 成为 一 一 乏一 · · 一 ， · 一、 艺一 · · 一 ，一 一 。 这一关系 式 以 后 要 引用 。 以 下来 考虑 两个 完备 的 、 但 定义 在 不 同逻辑 空 间上 的加 权布尔 多项 式 的 〔 乘 积 。 没有 个 毛变量 构 成 维 逻辑 变量 空 间 ， 及定义 在该 空 间上 的 元备加 权布 尔 多项 式 口 一 。 ， 艺 。 ， 毛 ， 毛 一 … … 屯 、 ， 另有 个 变量 构成 维 空 间 ， 定义 在该 空 间上 的 完备加 权多项式是 由 “ 一 日 二 乏日 ， 一 、 “ ’ ‘ ” “ ， ’ 两者 的乘 积 ， 。 。 ，、 。 一 乏 。 ， ‘ “ 。 七 一 ，… … ，， 侣 、 三 ‘ 。 · 。 · · 由于多项 式 、 日 的 每一 项都 一 是一 个 实 函数 ， 两 者 相 乘 当然 满 足 分 配 律 。 现 对下标为 的项 ， 逐项 引用 一 式 ， 并令 二 日 ，， 介“ 。 。 。 一 、 … … ，， 然后 再 对 取 和 即得烈 。 一 “ 一 一 一 黑 只 一 日 · 〔 之 二 毛 一 几 】 · · · · 一 〕 由 于 的 每一 项都 是 实函 数 ， 取 和的 先后 次 序 。吓以 交换 。 因 而得 到

2-1,2-1 Gw)（三aB,au-…u1t.-4…t） (2-11) 定理5！ 若加权布尔多项式P(a)、L(B)是完备的，那么两者之积G(W)也必然是完 备的。而且G(W)可表达成如下形式： 2+)-1 G(W)= Ws(unum-1…u1喜5=ξm-1…51)s (2-12) s 0 其中 5=i×2"+j,或者s=j×2+i Wg=a:×B, (un“g-1…u1*5=5a…ξ)s=(uu-1…u1）,*(5m5-…5） 证明要点：将(2-11)式的二凰求和式展开，并引入新的序号5，s与i、j的关系如上所述， 即可将(2-11)式的二重求和形式改写成(2~12)式的一重求和形式。又因为加权布尔多项式的 完备性是以其对应的布尔多项式的完备性来定义的。所以只要证明(2~12)式中的逻辑变量合 取项 （4aua-1…u105mξm-1…5,)5=(u。4n-……u1)1*(5m5m-1…51)1 一共有2+“项即可。 由于L(B)是完备的，所以(un“m-1…u1),一定有2“个互相区别的合取项。由于P(a) 是完备的，所以(51…)1一定有2“个互相区别的合取项。则两者的“与”式一定有 互相区别的合取项数是2”×2=2"+”。于是定理得证。 积G(W)的定义空间，对于粟式和被乘式的定义空间而言，增大成为m+·维逻辑空 间。这一现象称做加权布尔多项式的定义空间的“增生”。。 假若Y,()是一个布尔算子，u是E的布尔函数。即 u,=Y1（Ea,…5:) vj (2-13) 代入(2~12)之后，就得到一个新的加权布尔多项式G,(W)。显然，它的定义空间与G(W) 的不同，而是m维的空间。高维(m+n维)空间经(2-13)式的代换后成为低维(m维)空 间，这一现象称为加权布尔多项式的定义空间的“蛻化”。 定理6：设形式如(2-12)式的G(W)是完备的，经(2-13)的代换之后，蛻化后的G,(W) 也一定是完备的。而且G,(W)可表达成以下的形式 2-1 G,(W)=∑W(5m5-1…5): (2-14) 1=0 其中 WI EWs i=0,1,…2"-1 s=0,1,…2m+n-1 即全部W,是所有的Ws所构成的集合中的一个子集。 证明，由于G(W)是完备的多项式如下 2m+0-1 G(W)=∑Ws(uau-1…u1*5m5m-1…51)5 80 50

上 ， ‘ ’ “ 么 戈 二 艺 。 日，‘ 。 。 卜 … … ，二 “ 七卜 … … ‘ ，， ， ‘卜‘ ，， 定理 若加权布 尔多项式 、 日 是完备的 ， 那么两者 之积 也必然是完 备的 。 而且 可 表达成如下形式 ， 二，· 》 二 艺 · 。 。 卜 … … 。 。 · · … … 如 ‘ 其 中 二 ， 或者。 二 体 。 。 ， 。 “ … … 专 七 。 … … 七 二 ， ， … … ， 如 如一 · … 七 ， 证明要点 将 《卜 式的二重求和式 展开 ， 并引入 新的 序号 ， 与 、 的关系如 上所述 ， 即可将 卜 式的二重求和形式改写 成 《卜 》式的 一重求和形式 。 又 因为加权布尔多项式 的 完备性是 以其对应 的布尔多项式的完备性来定义的 。 所以只要证明《 一 式中的逻辑变盆合 取项 。 。 … … 专 七一 · · … 七 。 二 。 。 一 … … ， 息 七一 … … 七 ， 一共有 小 项即可 。 由于 是完备的 ， 所以 。 。 一 … … ，一定 有 “ 个互 相区别的 合取项 。 由于 是完备的 ， 所以 《 毛。 息卜 … … 七， 一定有 个互相 区别的 合取项 。 两者的 “ 与 ” 式一定有 互相 区别的合取项数是 二 今 ” 。 于是定理得证 。 乘积 》的定义 空 间 ， 对于乘式 和被乘式的定义 空 间而言 ， 增大成为 维逻辑空 间 。 这一现象称做加权布尔多项式的定义 空 间的 厂“ 增生” 。 ， 假若丫 ， 是一个布尔算子 ， 是 七的布尔函数 。 即 ， ‘ ， 毛一， … … 七 一 代入 卜 之后 ， 就得到一个新 的加权布尔多项式 ， 。 显然 ， 它的定义 空 间与 的 不 同 ， 而是 绷抽勺七空 间 。 高维 《 维 空 间经 一 式 的 代 换后成为低 维 维 空 间 ， 这一现象称为加权布尔多项式 的定义 空 间的 “ 镜化 ” 。 定理 设形式如 《卜 式的 是完备的 ， 经 卜 的 代换 之后 ， 境 化后 的 也一定是完备的 。 而且 可 表达成 以下的形式 一 ， 艺 · ‘ “ 。 ‘ 、 一 … … “ ， 一 其 中 一 〔 ， ， … … ， 一 ， ， 二 ， … 一 即全部 是所有的 所构成的集合中的一个子集 。 证明 由于 是完备的 多项 式如下 今 “ 一 艺 。 卜 … … 。 二 。 一 … … “