部分K值逻辑中Sheffer函数的判定问题

摘要

多值逻辑是计算机科学与技术的一个重要分支。其研究内容大体可分为三个方面，即多值逻辑理论、多值电路与多值数字系统、多值逻辑的应用。 多值逻辑理论中的一个重要问题是Sheffer函数的判定。此问题的解决依赖于定出所有准完备集，并可归结为定出所有准完备集的最小覆盖。本文主要研究部分K值逻辑中Sheffer函数的判定。 本文首先分析了完全和部分多值逻辑函数的结构理论，详细讨论了完全二值逻辑函数的准完备集以及它的最小覆盖，完全K值逻辑函数集中的准完备集，部分K值逻辑函数集中的准完备集。 对于部分二值逻辑中Sheffer函数的判定，本文首先用保关系的函数集来表示部分二值逻辑函数集P*2中的两个准完备集T(N0)，T(N1)，然后再利用“保关系”的思想，定出了*2中8个准完备集中的5个准完备集为最小覆盖。 对于部分K值逻辑函数集P*k中Sheffer函数的判定，本文首先提出了准完备集之间相似关系的概念，并证明了任意两个保相似关系的准完备集要么同是最小覆盖的成员，要么都不是，为Sheffer函数的判定提供了更简便的方法。 根据部分K值逻辑的完备性理论，本文证明了部分K值逻辑中七个准完备类中的三类，即保E函数类TE，L型函数类LG4,2，拟线性函数类LP，均为最小覆盖中的成员。 对部分K值逻辑中七个准完备类中的其它三类较复杂的准完备类，即完满对称数类Fs，m，单纯可离函数类SI，m，正则可离函数类SR,m，本文利用准完备集之间相似关系的概念，给出了m=2时，这几类中的准完备集属于最小覆盖的充分条件。

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权说明

第1章绪论

1.1研究多值逻辑的意义

1.2多值逻辑研究的一些新动向

1.2.1多值逻辑与分子计算机

1.2.2多值逻辑与VLSI

1.2.3多值逻辑与光计算机

1.2.4多值逻辑与人工智能

1.3多值逻辑函数结构理论研究

1.4论文研究的内容与所做的工作

1.5论文的结构

第2章多值逻辑系统简介

2.1多值逻辑代数系统

2.1.1 Post n值系统

2.1.2 Allen和Givone系统

2.1.3 Vranesic、Lee与Smith系统

2.1.4模代数系统

2.1.5 Webb运算系统

2.2阈值逻辑

2.2.1二值阈值逻辑

2.2.2三值阈值函数

2.2.3三元阈值函数的检验和实现

2.3本章小结

第3章多值逻辑函数的结构理论

3.1完全多值逻辑函数结构理论

3.2完全二值逻辑函数集

3.3完全K值逻辑函数集中的准完备集

3.4部分K值逻辑函数集中的准完备集

3.5一元K值逻辑函数

3.6本章小结

第4章部分二值逻辑中准完备集的最小覆盖

4.1基本定义

4.2P*2中准完备集之最小覆盖

4.3部分二值n元Sheffer函数的个数

4.4本章小结

第5章部分K值逻辑中准完备集之间的相似关系

5.1相似关系

5.2保相似关系的准完备集之间的性质

5.3本章小结

第6章部分K值逻辑中准完备集之最小覆盖(Ⅰ)

6.1引言

6.2关于保E函数集TE

6.3关于L型函数集LG42

6.4关于拟线性函数集LP

6.3本章小结

第7章部分K值逻辑中准完备集之最小覆盖(Ⅱ)

7.1关于正则可离函数集

7.2关于完满对称函数集

7.3关于二元单纯可离关系

7.4本章小结

第8章结束语

8.1工作总结

8.2进一步的研究工作

致谢

攻博期间从事科研项目及主要成果

参考文献