《部分四值逻辑中保三、四元正则可离关系函数集最小覆盖之判定》由会员分享，可在线阅读，更多相关《部分四值逻辑中保三、四元正则可离关系函数集最小覆盖之判定（67页珍藏版）》请在金锄头文库上搜索。
1、湘潭大学 硕士学位论文 部分四值逻辑中保三、四元正则可离关系函数集最小覆盖之判 定 姓名：周小强 申请学位级别：硕士 专业：计算机软件与理论 指导教师：刘任任 20070401 I 摘 要 多值逻辑是计算机科学中的一个重要分支。随着计算机科学与技术的不断进 步，多值逻辑得到了前所未有的发展，其研究主要包括理论、电路与系统、应用 三个方面的内容。 多值逻辑函数的完备性理论是多值逻辑理论研究中的一个重要的研究课题,此 问题的解决依赖于定出多值逻辑函数集中的所有准完备集(又称极大封闭集)。 Sheffer 函数的判定是又多值逻辑完备性理论中的一个重要问题，此问题的解 决可归结为定出所有准完备集的最小
2、覆盖。 完全多值逻辑函数中 Sheffer 函数的判 定已由 Schofield 和 Kudrjavcev 等完全解决。但部分多值逻辑函数中 Sheffer 函 数的判定尚未彻底解决。 本论文主要讨论了部分四值逻辑中准完备集之最小覆盖的判定问题。重点研 究了 * 4 P中保三、四元正则可离关系函数集之最小覆盖的判定。 本论文共分五章。在第一章中，主要介绍了本研究课题的学术背景、来源和主要 的研究内容。 在第二章中，概述了多值逻辑函数结构理论。首先介绍了完全多值逻辑函数 结构理论中的基本概念和重要研究成果， 然后介绍了部分 K 值逻辑函数集中的准 完备集以及sheffer函数的判定问题。最后总结
3、了部分多值逻辑函数集中最小覆盖 成员判定已经取得的成果。 在第三章中，根据相似关系的性质，剔除了 10 类共 84 个在最小覆盖中必不出现 的保三元正则可离关系准完备集， 并证明了未被剔除的 8 类共 36 个准完备集在最小 覆盖中必出现。 在第四章中，剔除了 29 类共 67 个在最小覆盖中必不出现的保四元正则可离关系 准完备集，并证明了未被剔除的 22 类共 42 个准完备集在最小覆盖中必出现，从而 定出了部分四值逻辑中所有保正则可离关系函数集的最小覆盖成员。 在第五章中，构造了部分 * 4 P中的 Sheffer 函数。 关键词：多值逻辑；完备性；准完备集；Sheffer 函数；最小覆盖
4、；正则可离关系. II Abstract Multiple-valued logic is an important branch of computer science. With the progress of computer science and technology, multiple-valued logic got unprecedented development. It includes the research of the theory, circuit Completeness; precomplete set; Sheffer Functions; Minimal
5、covering; Regularly separable relation. 湘潭大学湘潭大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印
6、件和电子版，允许论文被查阅和借 阅。 本人授权湘潭大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 涉密论文按学校规定处理。 作者签名： 日期： 年 月 日 导师签名： 日期： 年 月 日 湘潭大学硕士论文 部分四值逻辑中保三、四元正则可离关系函数集最小覆盖之判定 第 1 页 共 62 页 第一章第一章 引引 言言 1.1 课题研究背景 多值逻辑一种非经典的逻辑系统。在经典逻辑中，每一个命题皆取真假二值之一 为值，每一命题或者真或者假。但是，一个命题可以不是二值的。即不只是真或假，例 如，对于“明年 12 月 31 日正午我
7、将在长沙”这类命题，在说出它的当时，它既不真也不 假,而是可能。这也就是说,命题可以有三值，推而广之，还可以有四值，五值。因此， 对每一自然数 n，有 n 值，以至于无穷多值。研究这类命题之间逻辑关系的理论，即为 多值逻辑。 多值逻辑的思想可以追源到 19 世纪的苏格兰学者 MacColl1。但多值逻辑 正式作为一门独立的学科，则是由波兰逻辑学家、哲学家 J. Lukasiewicz3和美国 数学家 E. L. Post4分别各自独立提出来的。在 Lukasiewicz 1920 年发表的论三值 逻辑一文中，建立了一个三值逻辑系统，在 Post 1921 年发表的初等命题的一般理 论一文中，建
8、立了任意有穷多个值的逻辑系统。该系统对于任意的自然数 n2，序列 t1,tn的每一项都可以取作命题的值，其中 t1为真值,tn为假值。2050 年代，许多逻 辑学家建立了 n 值命题演算与谓词演算的公理系统,并探讨了它们的一致性和完全性问 题,同时也研究了多值命题演算与多值命题演算的子系统问题。1942 年，Rosenbloom 系 统地阐述了第一个真正意义上的完全多值逻辑代数。Rosser 和 Turquette 在 1945 年对 多值逻辑作出了确切的表述，并于 1952 年撰写了第一部关于多值逻辑的书籍。多值逻 辑在 60 年代获得了新的推广，从多值的线序域推广到多值的偏序域，建立了格值
9、逻辑。 70 年代后，多值逻辑被用于人工智能、新一代的计算机系统、和 VLSI 等计算机领域。 多值逻辑的研究内容很多，但大体上可分为三个方面。第一是理论方面：研 究逻辑系统的内部规律，主要包括多值逻辑函数的完备性理论，多值逻辑代数理 论，特殊多值逻辑结构，以及演算与推理系统等。第二是电路与系统方面：研究 实现多值逻辑的各种物理器件，多址数字系统的信息密度，解决集成电路的引线 限制以及连接复杂度问体，提高数字系统的可靠性，可测试性以及容错能力等。 第三是应用方面：多值逻辑作为一种方法可以用于二值计算机的测试码生成，故 障定位，容错设计，计算机系统诊断和社会诊断等。 在多值逻辑理论研究中，多值逻
10、辑函数结构理论是一个重要的研究方向，它 主要包括完备性理论、函数表示理论以及单向陷门函数。多年来一直受到国内外 著名学者的关注。国外著名学者 E.L.Post（美） 、S.B.Jablonskii (前苏联院士)、 I.G.Rosenberg (加)、C.D.Rine(美)、宫川正弘(日)以及国内知名专家王湘浩教授（院 士） 、罗铸楷教授、刘任任教授等人从事这一领域的研究，并取得了重要成果。 函数系完备性的判定问题是多值逻辑函数结构理论中的一个基本问题，此问 题的解决依赖于定出多值逻辑函数集中的所有准完备集（即极大封闭集） 。它包含 湘潭大学硕士论文 部分四值逻辑中保三、四元正则可离关系函数集
11、最小覆盖之判定 第 2 页 共 62 页 三个著名问题，即分别定出完全 k 值逻辑函数集、部分 K 值逻辑函数集和一元 K 值逻辑函数集中的所有极大封闭集， K 1。 第一个问题首先由 Post4和 Jabloskii11 分别解决 K = 2，3 的情形。对于一般的 K，罗铸楷教授和 Rosenberg15完全解决 了，即著名的完备性定理。第二个问题由王湘浩教授解决了 K = 2，3 的情形。对 于一般的 K 由罗铸楷教授完全解决。对第三个问题，由罗铸楷教授和刘任任教授 合作解决了一元 p（质数）值逻辑函数集完备性问题，即第三个问题的特殊情形。 Sheffer 函数的判定又是多值逻辑完备性理
12、论中一个重要问题，此问题可归结 为定出所有准完备集的最小覆盖。对于完全多值逻辑函数已由 Schofield19和 Kudrjavcev20等完全解决。在部分多值逻辑的研究中，刘任任教授利用准完备集 的相似关系，简捷的定出了部分 3 值逻辑中准完备集之最小覆盖，并对于一般的 K，证明了 E T, 2,4 , GPK LLP四类函数集必须在最小覆盖中出现，对 mS F , 、 mI S , 和 mR S , 三类函数集，由于结构很复杂，到目前为止，只取得了部分结果32,33,55-65，还 需进一步研究。 1.2 课题来源及主要内容 本课题来源于国家自然科学基金资助项目多值逻辑函数结构及优化理论研
13、究 （60083001） 。 刘任任教授与前几届研究生对部分 K 值逻辑中准完备集的最小覆盖进行了研 究，但目前还没有完全定出最小覆盖成员。此课题就是在已取得的结果基础上重 点对部分四值逻辑中保三、四元正则可离函数集进行研究，定出了部分四值逻辑 中保三、四元正则可离关系函数集中必是最小覆盖的成员。即对3,4m=时，剔除 正则可离函数集 ,R m S中必不属于最小覆盖的准完备集，证明未被剔除的准完备集 必是最小覆盖成员。并进一步构造了部分 * 4 P 中的 sheffer 函数。本论文基本内容结 构如下：在第二章中，概述了多值逻辑函数结构理论。首先介绍了完全多值逻辑 函数结构理论中的基本概念和重
14、要研究成果， 然后介绍了部分 K 值逻辑函数集中 的准完备集以及 sheffer 函数的判定问题。最后总结了部分四值逻辑函数集中最小 覆盖成员判定已经取得的成果。在第三章中，根据相似关系的性质，剔除了10类共 84个在最小覆盖中必不出现的保三元正则可离关系准完备集，并证明了未被剔除的8 类共36个准完备集在最小覆盖中必出现。在第四章中，剔除了29类共67个在最 小覆盖中必不出现的保四元正则可离关系准完备集，并证明了未被剔除的22类共42 个准完备集在最小覆盖中必出现，从而定出了部分四值逻辑中所有保正则可离关 系函数集的最小覆盖成员。在第五章中，构造了部分 * 4 P 中的Sheffer 函数。
15、 湘潭大学硕士论文 部分四值逻辑中保三、四元正则可离关系函数集最小覆盖之判定 第 3 页 共 62 页 第二章 多值逻辑函数结构理论 在多值逻辑理论中，函数系完备性的判定问题是一个基本而重要的问题。同 时也是自动机理论、多值逻辑网络中必须解决的问题，此问题的彻底解决依赖于 定出多值逻辑函数集中的所有准完备集（又称极大封闭集） 。它包含着三个著名的 问题，即分别定出完全多值逻辑函数集、部分多值逻辑函数集、一元多值逻辑函 数集中的所有准完备集。在本章中将对多值逻辑中的基本概念和前人研究的完备 性方面的重要成果作出总结。 2.1 完全多值逻辑函数 2.1.1 基本概念 设0,1,1,2 k Ekk=
16、?。函数 k n km EExxxf: ),( 21 ?称为完全完全k值逻辑函 数 值逻辑函 数。所有完全k值逻辑函数作成的集合记为 k P 。 定义定义 2.1.1 设 k PA，函数Atttf m ),( 21 ?；函数 12 (,),(1, ) in g x xxim=? 或者属于A或者为自变数 i x。 称函数 11212 (,),(,) nmn f gxxxgxxx?是由A 中的函数复合出来的函数。 所有由A中的函数复合出来的函数作成之集合记为 A 。 由定义易知，,AA并且若BA ，则BA。 定义定义 2.1.2 设 k PA 。如果AA =，则称A是一个封闭集封闭集。 不难知道，任意有限多个封闭集的交集仍是封闭集。 定义
