赋值代数是从人工智能领域中包括约束系统、信任函数系统、数据库理论等抽象出来的用于描述信息处理方式的一种特殊的代数结构模型, 它由从事信任理论函数的Prakash Shenoy教授首次提出, 并命名为Valuation-Based Systems (VBS).之后, Kohlas教授对其进行了明确、完整的表达^[1].在一个赋值代数中, 系统通过对变量的赋值来表达知识和信息, 通过联合运算表示对信息进行合成, 通过投影运算得到在指定变量集上的相关信息, 从而完成信息的提取.赋值代数是非确定情形下知识表示和推理的重要工具.

局部计算问题是赋值代数中的一个核心内容, 在赋值代数中关于这方面的研究成果极为丰富^[1-4].而在半环诱导的赋值代数中, 投影运算就转化为求和运算.特别地, 在全序幂等的半环诱导的赋值代数中, 求和运算即为求最大值运算.因此, 对于全序幂等的半环赋值$\varphi\in \Phi$, 当投影到空集时, 满足等式$\varphi(x)=\varphi ^{\downarrow \varnothing}(\diamond)$的$x$就是使得$\varphi$取得最大值的轮廓, $\varphi ^{\downarrow\varnothing}(\diamond)$就是该赋值的最大值.基于此, 文献[2]提出了全序幂等的半环所诱导的赋值代数中轮廓解与扩展解的概念, 并对它们进行了深入地讨论, 文献[2, 5, 6]也对其解的情况进行了进一步的研究.然而这些研究仅局限于全序幂等的半环诱导的赋值代数, 对于一般的半环诱导的赋值代数并没有相应的结论.因此, 本文在这些工作的基础上, 将全序幂等的半环诱导的赋值代数中轮廓解与扩展解的概念推广到约束半环诱导的赋值代数中, 研究了约束半环所诱导的赋值代数的性质以及其上任两赋值联合的轮廓解、投影的轮廓解的性质.最后给出了约束半环诱导的赋值代数中寻求轮廓解的一个新算法.这使得由全序幂等的半环诱导的赋值代数的相应结果得到良好的完善和推广.

本文中变量用大写字母$X, Y, \cdots$来表示.符号$\Omega_{X}$表示由变量$X$的取值构成的有限集合, 称为$X$的框架.用小写黑体字母$s, t, \cdots$来表示由变量构成的集合.这些集合一般假设是有限的.对于一个非空有限变量集$s$, 符号$\Omega_{s}$表示集合$s$中的所有变量的框架的笛卡尔积, 即$\Omega_{s}=\prod_{X \in s}\Omega_{X}$.若$s$为空集, 记$\Omega_{\varnothing}=\{\diamond\}$.$\Omega_{s}$中的元素用黑体的小写字母$x, y, \cdots$来表示, 称为具有域为$s$的轮廓.若$x\in \Omega_{s} $且$t\subseteq s$, 用$x^{\downarrow t}$表示$x$在子域$t$上的投影, 那么对于任一轮廓$x\in \Omega_{s}$, 可分解为$x=(x^{\downarrow t}, x^{\downarrow s-t})$.

一般地, 我们可以通过对变量赋值来传达知识或信息, 在本理论中称这个基本元素为赋值, 用符号$\varphi, \psi$等表示, 用$\Phi, \Psi$等表示由信息构成的集合.首先我们给出赋值代数的概念.

定义 2.1^[1] 这是定义内容.设$(\Phi, D)$是一个具有如下三种运算的二元组, 其中$(D, \vee, \wedge)$是一个格:

1、论域运算: $\Phi\rightarrow D;\varphi\rightarrow d(\varphi)$,

2、联合运算: $\Phi\times \Phi\rightarrow \Phi;(\varphi, \psi)\rightarrow \varphi\otimes \psi$.

3、投影运算: $\Phi\times D\rightarrow \Phi;(\varphi, t)\rightarrow \varphi^{\downarrow t}$.

若系统$(\Phi, D)$满足如下公理, 则称其是一个带标记的赋值代数:

1、半群律: $\Phi$关于联合运算满足交换律与结合律, 且有单位元.

2、论域律:若$\forall\varphi, \psi\in\Phi$, 则有$d(\varphi\otimes \psi)=d(\varphi)\vee d(\psi)$

3、边缘化律: $\forall \varphi \in \Phi$, $t \in D$, 若$t\leq d(\varphi)$, 则有$d(\varphi^{\downarrow t})=t$.

4、传递律:若$\forall \varphi \in \Phi$, $t\leq s \leq d(\varphi)$, 则$(\varphi^{\downarrow s})^{\downarrow t}=\varphi^{\downarrow t}$

5、联合律: $\forall\varphi, \psi\in\Phi$, 若$d(\varphi)=s, d(\psi)=t$, 则有$(\varphi \otimes \psi)^{\downarrow s}=\varphi \otimes \psi ^{\downarrow s}\wedge t$.

6、单位元律: $\forall s$, $t\in D, $有$e_{s}\otimes e_{t}=e_{s}\vee t$.

例 2.2(指示函数) 称$i:\Omega_{s}\rightarrow \{0, 1\}$为$s$上的指示函数, 这里$s\subseteq r$, $r$为全体变量之集.在全体指示函数上定义如下三种运算:

1. 论域运算:若$i:\Omega_{s}\rightarrow \{0, 1\}$, 则$d(i)=s$.

2. 联合运算:设$i_{1}, i_{2}$分别为$s$与$t$上的指示函数, 对于$x\in \Omega_{s}\cup t$, 则有

$ i_{1}\otimes i_{2}(x)=i_{1}(x^{\downarrow s})i_{2}(x^{\downarrow t}). $

3. 投影运算:对于$x\in \Omega_{t}, t\subseteq s$, $i^{\downarrow t}(x)=\mathop{\max}\limits_{y\in\Omega_{s}}:y^{\downarrow t}=xi(y)$.

由文献[1]知$(\Phi, D)$构成一个赋值代数, 其中$D$是$r$的幂集, 即$D=P(r)$.

定义 2.3^[3] 设非空集合$A$上有两个二元运算$+, \times$, 且元素$0, 1\in A$.称$(A, +, \times, 0, 1)$是一个半环, 若以下条件成立:

(1) 加法和乘法均满足交换律和结合律;

(2) 乘法在加法上满足分配律;

(3) $\forall a\in A$, 有$a+0=a, a\times 0=0$, 称$0$为$A$的零元;

(4) $\forall a\in A$, 有$a\times 1=a$, 称$1$为单位元.

由文献[3]知, 若半环$A$还满足$\forall a\in A$, 有$a+1=1$, 则称$A$是一个约束半环, 或者$c$ -半环.

例 2.4 四元菱形格是一个半环, 且是一个约束半环.

例 2.5 设命题变元之集$v$上的全体布尔函数$F_{v}=\{f:B^{v}\rightarrow B\}$, 其中$B=\{0, 1\}$, 则$(F_{v}, \max, \min, f_{0}, f_{1})$构成一个半环, 并且是一个约束半环, 其中$\forall x\in B^{v}$, 有$f_{0}(x)\equiv 0, f_{1}(x)\equiv 1$.

在半环$A$上定义序关系$\leq$: $a\leq b\Leftrightarrow a+b=b$.由文献[3]可知, 若$A$是一个约束半环, 则序关系$\leq$是半环$A$上的一个偏序关系, 且$\forall a, b, a', b'$, 有

(1) $a+a=a, a+b=\sup\{a, b\}$;

(2) 若$a\leq b, a'\leq b'$, 则有$a+a'\leq b+b', a\times a'\leq b\times b'$.

现在考虑一个非空变量集$r$以及一个半环$A$.若$s\subseteq r$, 称映射$\varphi:\Omega_{s}\rightarrow A$是域为$s$的一个半环赋值, 记$d(\varphi)=s$.令$\Phi_\textbf{s}=\{\varphi:d(\varphi)=\textbf{s}\}$, 则所有半环赋值之集记为$\Phi= \mathop{\cup}\limits_{s}\subseteq r \Phi_{s}$.令$D=P(r)$, 其中$P(r)$为$r$的幂集.在$(\Phi, D)$上定义如下运算:

(1) 联合运算: $\forall\varphi\in \Phi_{s}$, $\psi\in\Phi_{t}$及$x\in \Omega_{s}\cup t$, 定义$\varphi\otimes \psi(x)=\varphi(x^{\downarrow s})\times \psi(x^{\downarrow t})$.

(2) 投影运算: $\forall \varphi \in \Phi_{s}$, $x\in \Omega_{t}$且$t\subseteq s$, 定义

$ \varphi^{\downarrow t}(x)=\mathop{\sum}\limits_{y\in\Omega_{s}-t}\varphi(x, y). $

文献[3]中已证明:该系统在上述运算下构成一个赋值代数, 称$(\Phi, D)$为由半环$A$诱导的赋值代数.

在全序幂等的半环所诱导的赋值代数中, 满足$\varphi(x)=\varphi^{\downarrow \varnothing}(\diamond)$的$x$即为$\varphi$取得最大值的轮廓.而在约束半环所诱导的赋值代数中, $\varphi^{\downarrow \varnothing}(\diamond)\in \{\varphi(x):x\in \Omega_{d(\varphi)}\}$未必成立.因此在约束半环所诱导的赋值代数中, 我们从偏序关系的角度出发考虑那些使得$\varphi$取得极大值的轮廓, 从而给出约束半环所诱导的赋值代数中轮廓解的概念.

定义 3.1  设$(\Phi, D)$是由约束半环所诱导的赋值代数, 如果$x\in \Omega_{d(\varphi)}$满足$\forall y\in \Omega_{d(\varphi)}$, 都有$\varphi(x)\nless \varphi(y)$, 则称$x$为$\varphi$的一个轮廓解(Solution Configuration), $\varphi$的全体轮廓解之集记为$C_{\varphi}$.

注  当上述定义中约束半环取全序半环时, 这时这里的轮廓解即为文献[2]中的轮廓解, 所以全序半环诱导的赋值代数中轮廓解是上述定义中约束半环取全序半环时的特殊情形.

例 3.2  设$A=(\{0, 1, a, b\}, \vee, \wedge, 0, 1)$是四元菱形格, 变量集

$ s=\{X_{1}, X_{2}\}, \Omega_{X_{1}}=\Omega_{X_{2}}=\{0, 1\}, $

由$A$诱导的赋值代数中赋值$\varphi\in \Phi_{\{X_{1}, X_{2}\}}$满足

$ \varphi(1, 0)=\varphi(0, 1)=0, \varphi(0, 0)=a, \varphi(1, 1)=b, $

则$C_{\varphi}=\{(0, 0), (1, 1)\}$.

定理 3.3  设$(\Phi, D)$是由约束半环所诱导的赋值代数, $\varphi, \psi\in \Phi$, 且有

$ d(\varphi)=s, d(\psi)=t, s\cap t=\varnothing. $

如果$\varphi\otimes \psi$有唯一轮廓解$x$, 则有$x^{\downarrow s}\in C_{\varphi}$且$x^{\downarrow t}\in C_{\psi}$.

证  假设$x^{\downarrow s}\notin C_{\varphi}$, 或者$x^{\downarrow t}\notin C_{\psi}$.当$x^{\downarrow s}\notin C_{\varphi}$时, 则存在$y\in \Omega _{s}$且$y \neq x^{\downarrow s}$, 使得$\varphi(x^{\downarrow s})<\varphi(y)$, 所以有

$ \varphi(x^{\downarrow s})\psi(x^{\downarrow t})\leq\varphi(y)\psi(x^{\downarrow t}), $

即$\varphi\otimes \psi(x)\leq \varphi\otimes \psi(y, x^{\downarrow t})$, 因为$\varphi\otimes \psi$有唯一轮廓解, 因此上述等号不成立, 从而有$\varphi\otimes \psi(x)< \varphi\otimes \psi(y, x^{\downarrow t})$, 这与$x\in C_{\varphi\otimes \psi}$矛盾.因此$x^{\downarrow s}\in C_{\varphi}$, 同理可得$x^{\downarrow t}\in C_{\psi}$.

上述命题的逆命题在全序幂等的半环诱导的赋值代数中已知是成立的, 但在约束半环诱导的赋值代数中不再成立, 如下例:

例 3.4  设$A=(\{0, 1, a, b\}, \vee, \wedge, 0, 1)$是四元菱形格, 变量集$s=\{X_{1}, X_{2}\}, \Omega_{X_{1}}=\Omega_{X_{2}}=\{0, 1\}$, $A$诱导的赋值代数中赋值$\varphi$与$\psi$满足$\varphi(0)=a, \varphi(1)=b, \psi(0)=0, \psi(1)=a$, 其中$d(\varphi)=\{X_{1}\}, d(\psi)=\{X_{2}\}$, 则$C_{\varphi}=\{0, 1\}, C_{\psi}=\{1\}$, 但$(1, 1)\notin C_{\varphi\otimes \psi}=\{(0, 1)\}$.

定理 3.5  设$(\Phi, D)$是由约束半环所诱导的赋值代数, 则$C_{\varphi ^{\downarrow t}}\subseteq C_{\varphi}^{\downarrow t}$, 其中$t\subseteq s=d(\varphi)$.

证  任取$x\in C_{\varphi ^{\downarrow t}}$, 假设$x\notin C_{\varphi} ^{\downarrow t}$, 即$\forall z\in \Omega_{s-t}, \exists y_{0}\in \Omega _{s}$, 且$y_{0}^{\downarrow t}\neq x$, 使得$\varphi(x, z)<\varphi(y_{0})$, 从而有$\mathop{\Sigma}\limits_{z\in\Omega_{s-t}}\varphi(x, y)\leq \varphi(y_{0})$, 即

$ \begin{equation}\varphi^{\downarrow t}(x)\leq \varphi(y_{0}). \end{equation} $

(3.1)

另一方面, 有

$ \begin{equation}\varphi(y_{0})\leq \mathop{\Sigma}\limits_{y\in\Omega_{s-t}}\varphi(y_{0}^{\downarrow t}, y) =\varphi^{\downarrow t}(y_{0}^{\downarrow t}). \end{equation} $

(3.2)

由式(3.1) 与(3.2) 式可得$\varphi^{\downarrow t}(x)\leq \varphi^{\downarrow t}(y_{0}^{\downarrow t}).$因为$x\in C_{\varphi ^{\downarrow t}}$, 因此必然有$x=y_{0}^{\downarrow t}$, 这与上述假设矛盾.因此, $x\in C_{\varphi } ^{\downarrow t}$, 从而有$C_{\varphi ^{\downarrow t}}\subseteq C_{\varphi}^{\downarrow t}$.

上述命题的逆命题在约束半环诱导的赋值代数中也不再成立, 如下例.

例 3.6  设$A=(\{0, 1, a, b\}, \vee, \wedge, 0, 1)$是四元菱形格, 变量集

$ r=\{X_{1}, X_{2}\}, \Omega_{X_{1}}=\Omega_{X_{2}}=\{0, 1\}, $

$A$诱导的赋值代数中赋值$\varphi$满足:

$ \varphi(0, 1)=a, \varphi(1, 0)=\varphi(0, 0)=b, \varphi(1, 1)=0, $

则$\varphi^{\downarrow\{X_{1}\}}(0)=1, \varphi^{\downarrow\{X_{1}\}}(1)=b$, 从而$C_{\varphi}^{\downarrow \{X_{1}\}}=\{0, 1\} \nsubseteq \{0\}= C_{\varphi ^{\downarrow \{X_{1}\}}}$.

在约束半环所诱导的赋值代数中, 当赋值$\varphi$作用的变量的某一部分固定时, 变化部分取某些值时可使$\varphi$达到极大值, 我们称这些“某些值”为扩展解, 即下面的定义.

定义 3.7  设$(\Phi, D)$是由约束半环所诱导的赋值代数, $\varphi\in \Phi_{s}$, 其中$t\subseteq s$, 若对于$x\in \Omega_{t}$, 存在$c\in \Omega_{s-t}$, 使得对任意的$y\in \Omega _{s-t}$且$y\neq c$, 都有$\varphi(x, c)\nless \varphi(x, y) $, 则称$c$为赋值$\varphi$对于$x$的扩展解, 记$\varphi$对于$x$的扩展解之集为$W_{\varphi}^{t}(x)$.

显然$W_{\varphi}^{\varnothing}(\diamond)=C_{\varphi}, W_{\varphi}^{d(\varphi)}(x)=\{\diamond\}$.

本小节将文献[2]中给出的全序幂等的半环诱导的赋值代数中轮廓解的算法推广到约束半环诱导的赋值代数中.在给出之前, 我们先做一些准备工作.

为了讨论方便, 以下变量集$r$指命题变元之集, $P(r)$是其幂集.不失一般性, 以下不妨设$\forall A\in r$, 都有$\Omega_{A}=\{0_{A}, 1_{A}\}$.我们用命题公式来表示来表示布尔函数.例如$f(0, 0, 1)=1$可用命题公式$\neg A\wedge \neg B\wedge C$来表示.对于布尔函数$f$, 若$\forall x\in \Omega_{r}$, 都有$f(x)=1$, 则称$f$为重言式, 此时记$f$为$f_{T}$.若$ x\in \Omega_{r}$, 有$f(x)=1$, 则称$x$为布尔函数$f$的模型, 函数$f$的全体模型之集记为Models$(f)$.另外, 以下用$f_{A}$与$f_{\bar{A}}$表示如下定义的布尔函数: $\forall x\in \Omega_{r}, f_{A}(x)=1\Leftrightarrow A=1, f_{\bar{A}}(x)=1\Leftrightarrow A=0$.

设$A$是一个约束半环, 一个记忆约束半环赋值$\varphi$定义如下:

$ \forall x\in \Omega_{s}, d(\varphi)=s\subseteq r, \varphi:\Omega_{s}\rightarrow A\times F_{s}, x\rightarrow (\varphi_{A}(x), \varphi_{F}(x)), $

其中$F_{s}=\{f:\{0, 1\}^{|s|} \rightarrow \{0, 1\}\}$, 称$\varphi_{A}(x)$为记忆约束半环赋值的半环赋值部分, $\varphi_{F}(x)$是定义在$r$上的一个布尔函数, 称其为记忆约束半环赋值的记忆部分.我们用$\tilde{\Phi}_{s}$表示域为$s$的所有约束半环赋值构成的集合, 全体约束半环赋值之集记为$\tilde{\Phi}$, 取$D=P(r)$.对于记忆约束半环赋值, 定义如下三种运算:

1、标记运算: $\tilde{\Phi}\rightarrow D$; 如果$\varphi\in \tilde{\Phi}_{s}$, 则$d(\varphi)=s$.

2、联合运算:若$\varphi\in \tilde{\Phi}_{s}, \psi\in \tilde{\Psi}_{t}$, 则$\forall x\in \Omega_{s\cup t}$, 有

$ \varphi\otimes \psi(x)= (\varphi_{A}(x^{\downarrow s})\times \psi_{A}(x^{\downarrow t}), \varphi_{F}(x^{\downarrow s})\wedge \psi_{F}(x^{\downarrow t})). $

3、投影运算(变元消去运算):若$\varphi\in \tilde{\Phi}_{s}, Y\in s, x\in \Omega_{s- \{Y\}}$, 则

$ \begin{equation} \varphi ^{\downarrow d(\varphi)-\{Y\}}(x)=(\varphi_{A}^{\downarrow d(\varphi)-\{Y\}}(x), \varphi_{F}^{\downarrow d(\varphi)-\{Y\}}(x)), \end{equation} $

其中

$ \varphi_{A}^{\downarrow d(\varphi)-\{Y\}}(x)=\left\{\begin{array}{lc} \varphi_{A}(x, 0_{Y})+\varphi_{A}(x, 1_{Y}), \;\;\;\;\mbox{当} \varphi_{A}(x, 0_{Y}) \mbox{与} \varphi_{A}(x, 1_{Y})\mbox{可比较时};\\ \varphi_{A}(x, 0_{Y})\mbox{或}\varphi_{A}(x, 1_{Y}),\;\;\;\;\mbox{当} \varphi_{A}(x, 0_{Y}) \mbox{与} \varphi_{A}(x, 1_{Y})\mbox{不可比较时}, \end{array}\right. \\ \varphi_{F}^{\downarrow d(\varphi)-\{Y\}}(x)=\left\{\begin{array}{lc} f_{Y}\wedge \varphi_{F}(x, 1_{Y}),&\mbox{当}\varphi_{A}(x, 0_{Y})<\varphi_{A}(x, 1_{Y})\mbox{时};\\ f_{\bar{Y}}\wedge \varphi_{F}(x, 0_{Y}),&\mbox{当}\varphi_{A}(x, 1_{Y})<\varphi_{A}(x, 0_{Y})\mbox{时};\\ (f_{Y}\wedge \varphi_{F}(x, 1_{Y}))\vee (f_{\bar{Y}}\wedge \varphi_{F}(x, 0_{Y})),&\mbox{当}\varphi_{A}(x, 0_{Y})=\varphi_{A}(x, 1_{Y})\mbox{时};\\ f_{\bar{Y}}\wedge \varphi_{F}(x, 0_{Y}),&\mbox{当}\varphi_{A}(x, 0_{Y})\mbox{与}\varphi_{A}(x, 1_{Y})\mbox{不可比}\\ &\mbox{且}\varphi_{A}^{\downarrow d(\varphi)-\{Y\}}(x)=\varphi_{A}(x, 0_{Y})\mbox{时};\\ f_{Y}\wedge \varphi_{F}(x, 1_{Y}),&\mbox{当}\varphi_{A}(x, 0_{Y})\mbox{与}\varphi_{A}(x, 1_{Y})\mbox{不可比}\\ &\mbox{且}\varphi_{A}^{\downarrow d(\varphi)-\{Y\}}(x)=\varphi_{A}(x, 1_{Y})\mbox{时}. \end{array}\right. $

我们假设记忆约束半环的记忆部分初始时为空, 半环部分赋值初始值为约束半环赋值, 因此, 对于半环赋值$\varphi$, 其对应的初始记忆半环赋值$\tilde{\varphi}$如下:

$ \begin{equation} \tilde{\varphi}:x\rightarrow (\varphi_{A}(x), f_{T}). \end{equation} $

(4.2)

以下我们证明, 当利用式子(4.1) 逐步消去所有变元后, Models$(\varphi_{F}^{\downarrow\varnothing}(\diamond))$即为$C_{\varphi}$.

下面我们先给出记忆半环赋值的记忆部分与轮廓解之间的关系.

引理 4.1  $\forall x\in \Omega_{t}, d(\varphi)=s$, 则有$W_{\varphi}^{t}(x)=[\hbox{Models}(\varphi_{F}^{\downarrow t}(x))]^{\downarrow s-t}$.

证  当$t=d(\varphi)$时, $\forall x\in \Omega_{t}$, 有

$ W_{\varphi}^{d(\varphi)}(x)=\{\diamond\}=[{\hbox{Models}}(f_{T})]^{\downarrow \varnothing}=[{\hbox{Models}}(\varphi_{F}(x))]^{\downarrow \varnothing}. $

当$t\subseteq d(\varphi)$时, 假设上式成立, 下证对于$t-\{X\}$时上式亦成立, 其中$X\in t$.下仅证$\forall x\in \Omega_{t}$, $\varphi ^{\downarrow t}(x^{\downarrow t-\{X\}}, 0_{X})$与$\varphi ^{\downarrow t}(x^{\downarrow t-\{X\}}, 1_{X})$不可比的情况, 其余可参阅文献[2].

(1) 当$\varphi_{A}^{\downarrow t-\{X\}}(x^{\downarrow t-\{X\}})$取$\varphi ^{\downarrow t}(x^{\downarrow t-\{X\}}, 1_{X})$时,

$ W_{\varphi}^{t-\{X\}}(x^{\downarrow t-\{X\}})\;=\;\{(c, 1_{X}):c\in W_{\varphi}^{t}(x)\}\nonumber \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\;\{(c, 1_{X}):c\in [\hbox{Models}(\varphi_{F}^{\downarrow t}(x))]^{\downarrow s-t}\}\nonumber \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\;[{\hbox{Models}}(f_{X}\wedge \varphi_{F}^{\downarrow t}(x))]^{\downarrow s-(t-\{X\})}\nonumber \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\;[{\hbox{Models}}(\varphi_{F}^{\downarrow t-\{X\}}(x^{\downarrow t-\{X\}}))]^{\downarrow s-(t-\{X\})}.\nonumber $

(2) 当$\varphi_{A}^{\downarrow t-\{X\}}(x^{\downarrow t-\{X\}})$取$\varphi ^{\downarrow t}(x^{\downarrow t-\{X\}}, 0_{X})$时,

$ W_{\varphi}^{t-\{X\}}(x^{\downarrow t-\{X\}})\;=\;\{(c, 0_{X}):c\in W_{\varphi}^{t}(x)\}\nonumber \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\;\{(c, 0_{X}):c\in [\hbox{Models}(\varphi_{F}^{\downarrow t}(x))]^{\downarrow s-t}\}\nonumber \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\;[{\hbox{Models}}(f_{\bar{X}}\wedge \varphi_{F}^{\downarrow t}(x))]^{\downarrow s-(t-\{X\})}\nonumber \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\;[{\hbox{Models}}(\varphi_{F}^{\downarrow t-\{X\}}(x^{\downarrow t-\{X\}}))]^{\downarrow s-(t-\{X\})}.\nonumber $

综上有$W_{\varphi}^{t}(x)=[{\hbox{Models}}(\varphi_{F}^{\downarrow t}(x))]^{\downarrow s-t}$.

由上引理, 我们可得下面结论.

定理 4.2  设$(\Phi, D)$是由约束半环所诱导的赋值代数, 则

$ {\hbox{Models}}(\varphi_{F}^{\downarrow\varnothing}(\diamond))=C_{\varphi}. $

由此, 对一个约束半环赋值$\varphi\in \Phi_{s}$的轮廓解, 我们可给出如下算法:

步骤 1  构造$\tilde{\varphi}$.由式子(4.2) 构造对应的记忆约束半环赋值$\tilde{\varphi}$.

步骤 2  计算$\tilde{\varphi}^{\downarrow\varnothing}(\diamond)$.通过式子(4.1) 逐次消去所有变元, 即得

$ \tilde{\varphi}^{\downarrow\varnothing}(\diamond)=(\varphi_{A}^{\downarrow\varnothing}(\diamond), \varphi_{F}^{\downarrow\varnothing}(\diamond)), $

其记忆部分即所求.

步骤 3  计算Models$(\varphi_{F}^{\downarrow\varnothing}(\diamond))$.由定理4.2知, $\varphi_{F}^{\downarrow\varnothing}(\diamond)$的模型即为$C_{\varphi}$.

下面我们给出一个例子.

例 4.3  近期某类动物有一种疾病, 医务专家人员对此不能确诊, 但凭借多年医学经验他们一致认为服用三唑核苷、氧氟沙星或胸腺素这三种药有助于该疾病的好转.多次实验表明该类动物按不同组合服用这三种药后可能有四种不同的状态: “差”, “良好1”, “良好2”, “极好”.现在对该类动物如何服用这三种药物给出一个较好的方案.

假设我们把这三种药依次看做变量$A, B, C$, 当服用某药物时该变量取值为$1$, 否则取值为$0$, 四种状态分别依次用$0, a, b$和$1$表示.若多次实验结果表明选择不同组合服用这三种药后情况如下:

$ \varphi(0, 0, 0)=\varphi(1, 0, 0)=\varphi(1, 1, 1) =\varphi(1, 0, 1)=\varphi(1, 1, 0)=0, \\ \varphi(0, 0, 1)=a, \varphi(0, 1, 0)=\varphi(0, 1, 1)=b. $

则上述$\varphi$实际上可以看做由四元菱形格$(A, \vee, \wedge, 0, 1)$所诱导的赋值代数中的某一赋值, 最佳方案即是求$\varphi$的轮廓解.因此我们可用上述算法, 求解如下:

1、构造初始$\tilde{\varphi}$. $\tilde{\varphi}(x)=(\varphi_{A}(x), f_{T})$.

2、依次消去$C, B, A$, 对应记忆约束半环赋值依次如下表 1、表 2、表 3所示.

3、由表 3知$ \varphi_{F}^{\downarrow\varnothing}(\diamond))=f_{\bar{A}}\wedge f_{\bar{B}}\wedge f_{C}$或$f_{\bar{A}}\wedge f_{B}$, 则

$ {\hbox{Models}}(\varphi_{F}^{\downarrow\varnothing}(\diamond))=\{(0, 0, 1), (0, 1, 0), (0, 1, 1)\}, $

因此$C_{\varphi}=\{(0, 0, 1), (0, 1, 0), (0, 1, 1)\}$.

由上述结果知, 单独服用胸腺素、氧氟沙星或同时服用氧氟沙星与胸腺素时效果较好.

结束语  赋值代数是信息进行处理的重要代数结构模型, 它是非确定情形下知识表示和推理的重要工具.本文将由全序幂等的半环诱导的赋值代数中的轮廓解与扩展解的概念推广到由约束半环所诱导的赋值代数上, 研究了它们的性质.在此基础上, 给出了约束半环赋值代数轮廓解的一个新算法并给出例子予以说明.这使得文献[2]中仅考虑全序半环诱导的赋值代数的相应结果得到完善和推广.而对于一般的半环, 文中的序关系不再是偏序, 因此本文中的算法不再适用.那么对于一般的半环, 关于其轮廓解与扩展解, 以及此时轮廓解的算法又是什么样的呢？这应该是下一步值得研究的问题.