极小完备集的证明方法.pdfVIP

第24卷第1期 高等函授学报(自然科学版) V01．24No．1 of 2011年2月 Journal Education(NaturaISciences) 201l HigherCorrespondence ·大学教学· 极小完备集的证明方法 李艳华 张晓梅 李战国 (河南农业大学信息与管理科学学院，河南郑州450002) 摘要：本文分析了极小完备集的性质，并通过对几类极小完备集的证明。探讨了极小完备集 的证明方法。 关键词：完备集，极小完备集I联结词；命题变元 中圈分类号：0141 文献标识码：A 文章编号：1006—7353(2011)01一0036一02 集S定义，就称S是联结词完备集。 l极小完备集的性质 定义2 若S是一个联结词完备集且去掉其 极小完备集是离散数学中的一个重要概念， 中任一个联结词后，S都不再是完备集，就称S是 正确理解和掌握这个概念对于学好离散数学、提 极小完备集。 高初学者对数理逻辑的认识是非常必要的。众多 定理l 若S。是一个联结词完备集且S。量 离散数学教材以及文献着重研究了极小完备集的 s2，则S：也是联结词完备集。 有关性质和应用，然而，关于极小完备集的证明却 定理2{一，^，V)是完备集。 并不多见[1’2]，下文将对其证明方法进行探讨。 2证明极小完备集的方法 在离散数学中，一元联结词有如下4个， 按照极小完备集与完备集的定义，可知要证 其中， 明某个联结词集H是极小完备集，需要两个步 R1’ 硝1’ 髓” R1’ 骤：第一步：证明该联结词集H是完备集(即证H 0 O O 1 的完备性)，需要找到另外一个已知的完备集S为 l O 1 O 比较对象，并说明S中的每一个联结词都可以被 对任意一元命题变元p总有F；p甘o，不妨H定义。第二步：证明该联结词集H在去掉其中 称F{D为一元永假联结词。类似的，由于第忌个联结词后得到的联结词集H7。均不是完备 集(即证H的极小性)，需要找到合适的R并归纳 ED夕铮l，R”p甘户，称Fl”为一元永真联结词， 称F{D为一元不变联结词，碍D是常用的一元联出FI与命题变元生成的所有公式类型得到A。， 结词。 说明At不能被H’。定义。此步骤需要证明者具有 常用的二元联结词有如下5个， 较强的抽象和逻辑推理能力．当H中有z个联结 词时，就要分别证明z个H 户 口 7。不是完备集。因此，整 O 0 个证明过程中，证明H的极小性工作量最大。下 0 l 面以具体例题来说明极小完备集的证明方法。 1 O 例1 证明{一，V}的极小完备性。 l 1 证明 因为户^q甘-7(一夕V-7q)，所以^ 定义l 若任何竹元联结词F都