第5期 汪培庄，等：因素表示的信息空间与广义概率逻辑 ·849· 有效地联系起来，意义重大。但是这种联系有一 都找不到的信息组态必是虚组合，不妨碍命题的 个前提，表现逻辑的电路开关必须相互独立。如 成立。 果开关之间存在着关联，或者，由于系统受到侵 极小化方法（新）： 蚀，两个开关在开时连通，在变元非独立的情况 1)将赋值表中所有不属于背景R的所有列去 下，逻辑的结构功能关系应当如何进行呢？例 掉，得到R子表； 如，给出下面一张三变元公式p的赋值表（见表1）。 2)将p=1的点集合而成正类，将p=0的点 表1公式p在U上的赋值表 集合而成反类： Table 1 The assignment table of formula p on U 3)逐一检查长度k=1的字组，若它在反类的 00001111 所有字组中都不出现，则它是p的一个素蕴涵 X2 0 0110011 式，从中删除它的所有蕴涵式，如此继续直到所 有单字都检查完毕； X3 0 01 0 0 4)字组长度k=k+1,重复3)，重复此过程， 0 0 0 1 直到正类字组被删尽。将T的所有素蕴涵式用 3个开关，每个开关有2种状态，搭配出8种 加号连接起来，就得到T的极小析取范式 组态，形成表现论域U,由于这3个开关都是独立 命题7用极小化方法所得到的是T的一个 的。U中8种搭配都用上了。现在，设想这3个 极小析取范式。 开关不是独立的，譬如：2和是等效的： 证明首先要证明算法一定有停止的时候， 2=3。在这种限制下，第二、三、六、七列的组态 亦即，正字类一定会被删尽。设{x是P的一 是不可能出现的，背景R只包含4种组态： 点。它一定不属于P。以它为真集的公式就是n R={0,0,0),(0,1.1),(1,0,0),(1,1,1)}, 字组x=xAx2A…Axmm。假设这一点没有在 注意，为了简单，我们在符号上有下列等价的 以前的比对中被删除，那么就对此n-字进行检 表示方法： 查，因为它不会在负类字组中出现，所以这个字 0,0,0)=(p)A(P2)A(P3)=,S1A2A=1S 组一定在正类的某个字组中出现，因而它就是 (0,1,1)=(一P1)Λ(p2)A(p3)=,x1AxA=x3 的一个蕴涵式，从而这个点就可被删除。这说 p1、p2和P3是B中的字，但字组中的字：既 明，任何正字都可在算法执行的过程中被删除。 可以是P:也可以是P。在做这张表的时候，由 所记下的每一字或字组都被P所包含，根据 于有4种状态是不能出现的，所以，经典的最小化 命题5，这个字或字组就是P的素蕴涵式。全 问题是无解的，因为赋值没有完全。但用因素逻 体素蕴涵式的析取就是P的极小析取范式。 辑，可以作功能结构分析如下： 证毕。 命题5若字组q蕴涵字组p,则q的字长必 例3以表1为例，给定R=(0,0,0),(0,1,1), 大于p的字长。 (1,0,0),(1,1,1),要把开关的线路结构寻找出来。 证明若字组g蕴涵字组p,则存在字组s 1)将赋值表中所有不属于背景R的所有列去 使q=pAs,且s不包含p中的字。于是q的字长 掉，得到R子表（见表2）。 是p与s的字长之和。证毕。 表2表1在R上的子表 命题6若字组q是蕴含p的最短字组。若 Table 2 The sub-table of table 1 on R 它不在蕴含一p的任何n字组中出现，则g是p的 X1 0 0 1 素蕴涵式。 1 证明若字组q不在蕴含p的任何n字组 0 0 中出现，则q的有效真集Q必在p的真集P之 3 0 0 内，从而有RnQCP,故q是p的蕴涵式。若有 0 q蕴含p,由于q是蕴含p的最短字组，故不可 2)将p=1的点集合而成正类，将p=0的点 能蕴涵9，故q是p的素蕴涵式。证毕。 集合而成反 当R=If)×I)×.×I(f)是包含所有信息 正类={x2,2x3,x123} 组态的完全空间，对R所作的任何分割，每一信 反类={x12x} 息组态x必在一方。当R≠I(F)时，对R分割的 3)逐一检查长度k=1的字组q,首先考虑 双方可能都找不到某些信息组态，但是这些双方 q=x,它不在反类的字组中出现，所以它是p的p 有效地联系起来，意义重大。但是这种联系有一 个前提，表现逻辑的电路开关必须相互独立。如 果开关之间存在着关联，或者，由于系统受到侵 蚀，两个开关在开时连通，在变元非独立的情况 下，逻辑的结构功能关系应当如何进行呢？例 如，给出下面一张三变元公式 的赋值表（见表 1）。 表 1 公式 p 在 U 上的赋值表 Table 1 The assignment table of formula p on U x1 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 x3 0 1 0 1 0 1 0 1 p 0 0 0 1 1 1 1 1 U U x2 x3 x2 = x3 R R = {(0,0,0),(0,1,1),(1,0,0),(1,1,1)} 3 个开关，每个开关有 2 种状态，搭配出 8 种 组态，形成表现论域 ，由于这 3 个开关都是独立 的。 中 8 种搭配都用上了。现在，设想这 3 个 开关不是独立的，譬如： 和 是等效的： 。在这种限制下，第二、三、六、七列的组态 是不可能出现的，背景 只 包 含 4 种组态： ， 注意，为了简单，我们在符号上有下列等价的 表示方法： (0,0,0) = (¬p1)∧(¬p2)∧(¬p3) =, x1 ∧ x2 ∧ x3 = x1 x2 x3 (0,1,1) = (¬p1)∧(p2)∧(p3) =, x1 ∧ x2 ∧ x3 = x1 x2 x3 p1 p2 p3 B xi pi ¬pi 、 和 是 中的字，但字组中的字 既 可以是 也可以是 。在做这张表的时候，由 于有 4 种状态是不能出现的，所以，经典的最小化 问题是无解的，因为赋值没有完全。但用因素逻 辑，可以作功能结构分析如下： q p q p 命题 5 若字组 蕴涵字组 ,则 的字长必 大于 的字长。 q p s q = p∧ s s p q p s 证明 若字组 蕴涵字组 ，则存在字组 使 ，且 不包含 中的字。于是 的字长 是 与 的字长之和。证毕。 q p ¬p n q p 命题 6 若字组 是蕴含 的最短字组。若 它不在蕴含 的任何 字组中出现，则 是 的 素蕴涵式。 q ¬p n q Q p P R∩ Q ⊆ P q p q ′ p q ′ p q ′ q q p 证明 若字组 不在蕴含 的任何 字组 中出现, 则 的有效真集 必在 的真集 之 内，从而有 ，故 是 的蕴涵式。若有 蕴含 ，由于 是蕴含 的最短字组，故 不可 能蕴涵 ，故 是 的素蕴涵式。证毕。 R = I(f1)× I(f2)×...× I(fn) R x R , I(F) R 当 是包含所有信息 组态的完全空间，对 所作的任何分割，每一信 息组态 必在一方。当 时，对 分割的 双方可能都找不到某些信息组态，但是这些双方 都找不到的信息组态必是虚组合，不妨碍命题的 成立。 极小化方法 (新)： R R 1) 将赋值表中所有不属于背景 的所有列去 掉，得到 子表； 2) 将 p = 1 的点集合而成正类, 将 p = 0 的点 集合而成反类; k = 1 p 3) 逐一检查长度 的字组, 若它在反类的 所有字组中都不出现，则它是 的一个素蕴涵 式，从中删除它的所有蕴涵式，如此继续直到所 有单字都检查完毕； k := k+1 T T 4) 字组长度 ，重复 3），重复此过程， 直到正类字组被删尽。将 的所有素蕴涵式用 加号连接起来，就得到 的极小析取范式 命题 7 用极小化方法所得到的是 T 的一个 极小析取范式。 {x} P P c n x = x1i(1) ∧ x2i(2) ∧ ··· ∧ xni(n) n− yi 证明 首先要证明算法一定有停止的时候， 亦即，正字类一定会被删尽。设 是 的一 点。它一定不属于 。以它为真集的公式就是 字组 。 假设这一点没有在 以前的比对中被删除，那么就对此 字进行检 查，因为它不会在负类字组中出现，所以这个字 组一定在正类的某个字组中出现，因而它就是 的一个蕴涵式，从而这个点就可被删除。这说 明，任何正字都可在算法执行的过程中被删除。 P P P 所记下的每一字或字组都被 所包含，根据 命题 5，这个字或字组就是 的素蕴涵式。全 体素蕴涵式的析取就是 的极小析取范式。 证毕。 R = ((0,0,0),(0,1,1), (1,0,0),(1,1,1)) 例 3 以表 1 为例，给定 , 要把开关的线路结构寻找出来。 R R 1) 将赋值表中所有不属于背景 的所有列去 掉，得到 子表（见表 2）。 表 2 表 1 在 R 上的子表 Table 2 The sub-table of table 1 on R x1 0 0 1 1 x2 0 1 0 1 x3 0 1 0 1 p 0 1 1 1 2) 将 p = 1 的点集合而成正类, 将 p = 0 的点 集合而成反类： 正类 = {x1 x2 x3, x1 x2 x3, x1 x2 x3} 反类 = {x1 x2 x3} k = 1 q q = x1 p 3) 逐一检查长度 的字组 ，首先考虑 ，它不在反类的字组中出现，所以它是 的 第 5 期 汪培庄，等：因素表示的信息空间与广义概率逻辑 ·849·