部分四值邏輯中sheffer函數(shù)的判定與構(gòu)造

1、 I 學(xué)校代號 10530 學(xué) 號 200611021187 分 類 號 TP301.1 密 級 碩 士 學(xué) 位 論 文 部分四值邏輯中 Sheffer 函數(shù)的判定與構(gòu)造 學(xué) 位 申 請 人 朱 玲 芳 指 導(dǎo) 教 師 劉任

2、任 教授 學(xué) 院 名 稱 信息工程學(xué)院 學(xué) 科 專 業(yè) 計算機(jī)軟件與理論 研 究 方 向 多值邏輯 二 0 一 0 年四月 III 摘 要 多值邏輯是一種邏輯取值數(shù)大于 2 的非經(jīng)典邏輯系統(tǒng)。 其研究內(nèi)容主要包括多值邏輯理論、電路與系統(tǒng)和應(yīng)用等三個方面。 多值邏輯函數(shù)結(jié)構(gòu)理論是多值邏輯理論的研究內(nèi)容之一， 它主要包括

3、多值邏輯函數(shù)的完備性理論、 函數(shù)表示理論以及單向陷門函數(shù)， 其中一個基本且重要的問題是多值邏輯函數(shù)集的完備性判定， 在多值邏輯網(wǎng)絡(luò)以及自動機(jī)理論中， 這也是一個必須解決的問題。 此問題的解決與多值邏輯函數(shù)集中準(zhǔn)完備集 （又稱極大封閉集）的確定密切相關(guān)。 多值邏輯中 Sheffer 函數(shù)的判定與構(gòu)造是多值邏輯完備性理論中的又一個重要問題，該問題歸結(jié)為找出全部準(zhǔn)完備集的最小覆蓋。對于完全多值邏輯中Sheffer 函數(shù)的判定問題，已于 20

4、世紀(jì) 70 年代完全解決；對于部分多值邏輯中Sheffer 函數(shù)的判定問題，由于準(zhǔn)完備集的最小覆蓋問題還沒有完全解決而尚未徹底解決。 本文較深入地研究了部分四值邏輯中 Sheffer 函數(shù)的判定和構(gòu)造問題。根據(jù)部分四值邏輯中準(zhǔn)完備集的最小覆蓋，分別給出了判定和構(gòu)造部分四值邏輯中Sheffer 函數(shù)的算法。該算法可判定任意一個部分四值邏輯函數(shù)是否為 Sheffer 函數(shù)，此外，還能構(gòu)造出所有部分四值邏輯 Sheffer 函數(shù)。為解決部分