部分四值邏輯中保二元正則可離關系非最小覆蓋的剔除

摘 要：為確定部分四值邏輯的最小覆蓋，根據部分K值邏輯的完備性理論、正則可離關系以及準完備集之間的相似關系理論， 對部分四值邏輯的最小覆蓋進行分析，證明了270個保二元正則可離關系函數集中的222個函數集必不屬于部分四值邏輯中最小覆蓋的成員。

關鍵詞：多值邏輯；完備性；正則可離關系；最小覆蓋

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

1 引 言多值邏輯是指一切邏輯值的取值數大于2的邏輯，它是由二值邏輯擴展而來的。多值邏輯是計算機科學中的一個重要分支，隨著計算機科學與技術的不斷進步，多值邏輯得到了前所未有的發展，其研究內容主要包括理論、電路與系統、應用三個方面。在多值邏輯函數結構理論中， Sheffer 函數的判定與構造是一個非常重要的研究課題，其判定問題與函數集完備性之判定密切相關，完備性的判定可歸結為定出其中的所有準完備集，而Sheffer函數的構造又可歸結為定出準完備集的最小覆蓋。對于完全多值邏輯函數已由Schofield、Kudrjavcev和羅鑄楷教授等完全解決。對于部分多值邏輯， 羅鑄楷教授根據“保關系”的思想定出了部分多值邏輯中所有的準完備集(共七類) ［1］， 徹底解決了函數集的完備性問題，但Sheffer函數之判定與構造問題尚未徹底解決， 即未定出所有準完備集的最小覆蓋，只取得了部分結果［2-7］。對于其中的正則可離函數集，根據相似關系理論， 若某準完備集能被已確定的最小覆蓋成員之并所覆蓋，則它們在最小覆蓋中必不出現，即可以剔除。所有部分四值邏輯函數做成之集合記為P*4，本文根據已確定的最小覆蓋成員 ［2-6］，對P*4中的正則可離函數集SR，m的499個準完備集進行分析，證明了m＝2時的222個準完備集在部分四值邏輯的最小覆蓋中必不出現。