逻辑代数基本定理的证明，本文主要内容关键词为：代数论文,定理论文,逻辑论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
由n元逻辑函数F（A[,1]，A[,2]，…A[,n]）的定义可知， 每个逻辑变量A[,i]（ i＝1，2，…n）及其逻辑函数的取值集合均为L＝｛0,1｝，于是显然有
[引理] 对于n元逻辑函数F（A[,1]，A[,2]，…A[,n]），则有
F面给出n元逻辑函数基本定理，并分别给出三种证明方法。
[基本定理] 全体n元逻辑函数共有2[2][n]种不同形式。
一、数学归纳法证明
下面对变元个数n施行数学归纳证明：
1.当n＝1时，不难看出，由引理知，一元逻辑函数F（A）可表示为F（A）＝AF（1）+
F（0）因为逻辑函数的定义域和值域都是集合L＝｛0,1｝。因此，对于A＝1，有F（1）＝0或F（1）＝1；对于A＝0，有F（0）＝0或F（0）＝1，即一元逻辑函数F（A）存在有两种不同形式的函数值表示式F（1）、F（0），从而F（1），F（0）搭配有四种不同的取值组（情况），于是有
从而一元逻辑函数F（A）有且只有以下四种不同形式：
根据以上步骤1，2，知对于任何自然数n，结论均成立。
二、不完全归纳法证明
当n＝1时，由上法可知，一元逻辑函数F（A）总共有四种不同形式即
当n＝2时，二元逻辑函数F（A,B），由引理公式可得
在这里，二元逻辑函数F（ A,B）出现了四种不同的函数值表示式F（1,1），F（1,0），F（0,1）和F（0,0），且它们都在L＝｛0，1｝上取值，从而有
种不同的搭配取值组（情况），分别依次将各种取值组的值代入（1）式得
一般地，……，对于n元逻辑函数F（A[,1]，A[,2]，…A[,n]）共有2[n]个函数值表示式
三、范式定理证明
由范式定理：任一n元非0的逻辑函数F（A[,1]，A[,2]，…A[,n]）都可以化为和它相等的“与一或”范式和“或一与”范式且表示法是唯一的即
其中ik（K＝1，2，…m）分别取数集｛0，1，2，…2[n]－1｝中的不同的数且
为n之非0逻辑函数F（A[,1]，A[,2]，…A[,n]）的某一个最小项。
由此可知，一个n元非0的逻辑函数F（A[,1],A[,2],…A[,n]）完全由一个“与－或”范式所唯一决定，也就是说，n 元“与－或”范式不同，所表示的逻辑函数也就不同，因此，所有不同形式的n之非0逻辑函数的总数便由所有不同形式的（ 所有可能的组成情况）n元“与－或”范式的总数所决定。
下面我们具体找出n元“与－或”范式的所有可能的组成情况， 就可以得到所有不同形式的n元“与－或”范式的总数。
首先，根据n个变元的最小项的定义，可以知道n个变元A[,1]，A[,2]，…A[,n]的每一个最小项的n个因子分别取自n个不同的集合：
由排列组合的知识，这种取法的总数依n个步骤的乘法原理， 共有
（个），因此，n个变元的全体最小项共有2[n]个。
[收稿日期]1999—03—31