部分四值邏輯中保三元正則可離關系函數集最小覆蓋的確定

摘要:Sheffer函數的判定與構造是多值邏輯函數結構理論中的重要問題之一，此問題可歸結為定出多值邏輯函數集之準完備集的最小覆蓋#65377;本文根據部分K值邏輯的完備性理論以及準完備集之間的相似關系理論，定出部分四值邏輯中保三元正則可離關系的準完備集之最小覆蓋的成員#65377;

關鍵詞:多值邏輯; 完備性;Sheffer函數; 最小覆蓋

中圖分類號:TP301文獻標識碼:A

1引言

在多值邏輯函數結構理論中， Sheffer 函數的判定與構造是一個非常重要的研究課題，其判定問題與函數集完備性之判定密切相關，完備性的判定可歸結為定出其中的所有準完備集[2-3]，而Sheffer 函數的判定又可歸結為定出準完備集的最小覆蓋#65377; 對于部分多值邏輯，其函數集的完備性問題已徹底解決，但其中Sheffer 函數之判定與構造問題尚未徹底解決[4]#65377;本文根據準完備集之間的相似關系理論[5]， 定出了部分四值邏輯中保三元正則可離關系函數集的最小覆蓋成員#65377;

2基本定義

設Ek={0，1，…，k-1}， k≥2， Ek上的完全和非完全K值邏輯函數統稱為部分多值邏輯函數，所有部分K值邏輯函數作成的集合記為Pk#65377;

函數f(x1，…，xn)(∈Pk)說是一個Sheffer函數，如果f能疊合出Pk中的所有函數#65377;

部分四值邏輯中保三元正則可離關系函數集最小覆蓋的確定若Gm正則可離， 則稱T(Gm)為保正則可離函數集， 并記為SR，m#65377;

顯然， 相似關系是一個等價關系， 我們用Gm~φG′m來表示Gm與G′m在雙射φ下相似#65377;

3主要結果及其證明

定理部分四值邏輯中保三元正則可離關系G3的準完備集T(G3)共有36個屬于最小覆蓋的成員， 按相似關系分為8類#65377;

證明根據相似關系理論[5]， 任何兩個相似的準完備集要么同屬于最小覆蓋， 要么同不屬于最小覆蓋，而相似關系又是一個等價關系#65377;因此，我們只需從以上8類中各取其中一個(以下均取第一個)G3來證明保此關系的準完備集屬于最小覆蓋#65377;下面按類分別進行證明#65377;

由此可得出G3={<0，0，0>，<1，1，1>，<2，2，2>，<3，3，3>，<0，1，2>}必是部分四值邏輯中準完 備集之最小覆蓋的成員， 同時也證得此類相似關系的準完備集均為最小覆蓋的成員#65377;

由于以下七類的證明方法與第一類的類似， 而篇幅有限， 故只寫出了各類中某一準完備集的 構造函數， 具體證明過程略#65377;

4結束語

本文定出了部分四值邏輯中保三元正則可離關系的準完備集之最小覆蓋成員，為定出P4中的所有準完備集的最小覆蓋奠定了良好的基礎，并為以后定出Pk(k>4) 中所有準完備集的最小覆蓋提供了有益的幫助#65377;

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。