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

關(guān)鍵詞:多值邏輯; 完備性;Sheffer函數(shù); 最小覆蓋

中圖分類號:TP301文獻(xiàn)標(biāo)識碼:A

1引言

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

2基本定義

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

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

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

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

3主要結(jié)果及其證明

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

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

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

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

4結(jié)束語

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

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