补充资料：Boole函数的极小化

Boole函数的极小化
f Boolean functions , minimization

玫心e函数的极小化〔致双ean如口比哪，而苗mi.垃皿成;脚月e.“盆中y.“”浦M..llM.3a皿.] 及川e函数的范式(Boolean fun以ions，normalforms of)表示，它们关于某种复杂性度量是最简单的.苹李的早杂堆(印mplexity ofa。ormal form)的通常的意义是指其中所含字母的个数.这种意义下的最简单的范式称为极小范式(minimal form).复杂性的度量有时是指在析取范式中出现的初等合取的个数，或是合取范式中因式的个数.在这种情形下，最简单的范式称作最短范式(s hortest form).鉴于析取范式与合取范式的对偶性，仅考虑析取范式就足够了. 最短析取范式与极小析取范式的构造各具特点.同一函数的极小析取范式的集合与最短析取范式的集合之间可能有如下的集合论关系:一个包含在另一个之内，交集是空集，或有非空的对称差.设mf是函数f的极小析取范式的复杂性，匆是它的最短析取范式的极小复杂性;又设l伍)是当f取遍所有。元函数时，比值气/。，中之最大者.于是有以下的渐近式成立: n ‘、”)~万· Boole函数的极小化问题，通常理解为构造它们的极小析取范式，构造任何Boole函数f(x1，…，x。)的一切极小析取范式，有一个平凡的算法如下:观察所有含变元x:，…，x。的析取范式，从中选取那些实现f，并且有极小复杂性的范式.实际上，这个算法即使对于小的n，也是不切实用的，因为它所需要的演算次数急剧上升.因此，许多别的算法被提出，但并不能有效地应用于所有的函数. 在极小化问题中，一个函数的初始指定通常是一个表，或一个完满析取范式(见B.诵e函数的范式(B 001-ean funCtions，normal formof))，或任何一个析取范式第一步在于转化成所谓的简约析取范式，这对每个函数都是唯一确定的.实现这个转化有许多方法可采用.最普遍的方法是在析取范式中作形式如下 的变换: AvA.B.A(吸收).带有关于邻域S、(吸，贝)的特殊记忆的最佳局部算法.上面所介绍的种种算法，都是丁粤可草捧(罗neral ringalgorithm)的特例.若 S*一，(贬，呢)={吸，贬，，…，班，}， Sk(班，卿二{级，贬.，，二，甄，贬，十，，…，吸，}以及、。一、一N·u自N一N一N·U自N、， Q(Sk)=Ns‘\N凡一，，则对于每个子集N三Q(S‘)，都可以确定一个并非到处有定义的Boole函数f，使得f取值l的集合M子为Ns八N，取值。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。