


VIP免費下載
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
命題邏輯中范式教學的思考與總結摘要:范式是命題邏輯中的重要概念,范式是把命題公式化歸為一種標準的形式。范式最大的作用是可以進行兩個命題的等價判定。本文通過剖析范式的定義和判定方法,幫助離散數學的初學者深入理解范式并能夠熟練書寫命題的范式。關鍵詞:范式;命題邏輯;等價判定;離散數學一、范式的引入在引入范式的定義之前,我們先來講解一下判定的含義:以有限次步驟來決定命題公式是否為永真式、永假式還是可滿足式,或者判定兩個命題公式是否定價等這一類問題統稱為判定問題。在命題邏輯中,講解了兩個命題A和B等價(A<=>B)的充要條件是A<->B為永真式。具體判斷的方法可以歸納為三種:第一種是真值表法,即對于等價號兩邊的命題變元給予相同的真值指派,看結果是否相同,相同的話A<->B即為永真式,此時A<=>B。第二種是命題演算的方法,即化簡命題A<->B至最簡式,看是否為T,然后判斷。第三種就是我們要介紹的范式判定的方法,將命題公式A和B分別化成主析取范式(或主合取范式)。如果化成后的主范式相同,則可以判定兩個公式等價。把命題公式化歸為一種規(guī)范標準的形式,稱此標準形式為范式。二、析(合)取范式許多教材對析取和合取范式有著不同類型的定義。這里我們先引入兩個詞的定義:基本積和基本和。命題的析取式稱為“和”,命題的合取式稱為“積”。基本積是指命題公式的變元和變元的否定之積。同理,基本和是指命題公式的變元和變元的否定之和。若“基本積”和“基本和”中有子公式,則稱為基本積(和)的因子。基本積和永假式有著密切的關系,一個基本積是永假式的充分必要條件是它至少包含一對因子,其中一個是另一個的否定。該判定很容易理解,因為一旦包含這樣的因子,那么其中必然含有F,由于基本積是合取,那么整個命題的值為F,即為永假命題。同理,一個“基本和”必定為永真式的充分必要條件是該公式至少包含一對因子,其中一個是另一個的否定。析取范式的定義可以簡稱為“積之和”,即與命題公式等價的一個公式,如果是由基本積之和組成,則稱它為命題的析取范式。并記為:PP1∨P2∨…∨Pn(n∈I+)。其中P1,P2…Pn均為基本積。合取范式和析取范式相反,可以簡稱為“和之積”,具體定義在此就不再贅述。從上面的定義可以看出,一個命題公式的析(合)取范式并不是唯一的,但是同一命題公式的析(合)取范式之間一定是等價的。可以說,一個命題公式的析(合)取范式有無數多個,因此單純討論析(合)取范式意義不大。我們更希望能夠找到一種標準的形式,使得一個命題公式僅僅對應一個等價的析(合)取范式,這樣就引入了主析(合)取范式。三、主析(合)取范式限于篇幅,這里我們以主析取范式為例。講解之前,先要給出極小項的定義,而極小項又和前面講的基本積息息相關。在n個變元的基本積中,若每個變元及其否定并不同時存在,且二者之一出現一次且僅出現一次,則稱此基本積為極小項。對于兩個命題變元來說,極小項有2的2次方4個,即P∧Q、?P∧Q、P∧?Q、?P∧?Q。對于只有一個變元的命題,極小項有2個,即P、?P。依次類推,對于三個命題變元來說,極小項有8個,即P∧Q∧R、P∧Q∧?R、P∧?Q∧R、?P∧Q∧R、?P∧Q∧?R、?P∧?Q∧R、P∧?Q∧?R、?P∧?Q∧?R。推廣到一般,n個命題變元構成的不同極小項有2的n次方個。而使得每個極小項為真的賦值僅有一個。有了極小項的定義,就可以定義主析取范式了,對于給定的命題公式來講,僅含有極小項的析取的等價式稱為給定命題公式的主析取范式。在真值表中,一個公式真值為T的指派所對應的極小項的析取,即為此公式的主析取范式。對于該定義,要注意一下幾點:第一,只要命題公式不是永假式,則一定可以根據該命題公式的真值表直接寫出其主析取范式,其方法是找出該公式為“T”的行,對應寫出極小項的析取式,且該公式一定是唯一的。第二,若命題公式是含有n個變元的永真式,則它的主析取范式一定含有2的n次方個極小項。第三,若兩個命題公式對應的主析取范式相同,則此兩個命題公式一定是定價的。第四,命題公式的主析取范式中極小項的個數一定等于對應真值表中真值為“T”的個數。四、求主析取范式的方法求主析取范式的方法主要有兩種,第一種是真值表法,其含義就是將真值表中對應結果為“T”的項列出來,然后將這些項用∨連接起來。這種方法較為簡單,列出真值表,結果就一目了然了。但是當命題變元為3個以上時,真值表的數目將指數級增長,較為麻煩。下面介紹不用真值表,直接求命題公式主析取范式的方法,分為4步:第1步將命題公式化為與其等價的析取范式。第2步除去永假項,合并基本積中相同項,變?yōu)樽詈唵挝鋈》妒健5?步是利用添變元的方法,將所有基本積變?yōu)闃O小項。第4步合并相同的極小項變?yōu)橐豁棥N濉⒖偨Y主范式是將無數不同的命題公式轉化成標準形式,以此來判斷不同的命題公式之間是否等價。我們知道,含有1個命題變元的公式對應的真值表有兩行,每一行的結果有兩種,分別是T和F,那么可以產生2的2次方種(即4種)不同的真值表。同理,含有2個命題變元的公式可以產生出2的4次方種(即16種)不同的真值表。含有變元個數越多
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年面料采購合同范本
- 2025合同范本股權轉讓協議模板
- 2025企業(yè)租賃合同樣本
- 2025汽車買賣合同解除協議
- (高清版)DB13∕T 2937-2019 非煤礦山雙重預防機制建設規(guī)范
- 物業(yè)管理服務質量提升合同書
- 2025年餐飲服務外包合同
- 工程承建合同條款明確
- 農村土地復墾和資源保護利用合同
- 2025巖土工程檢測儀器產品購銷合同(示范文本)
- 巨人的花園說課ppt
- 西藏自治區(qū)2022年事業(yè)單位考試真題與答案解析
- GB/T 42605-2023移動式壓力容器修理導則
- 第三單元+第2課+親切的使者 人教版+七年級下冊+
- 浙江農林大學2023
- 義務教育體育與健康課程標準(2022年版)
- GA 1807-2022核技術利用單位反恐怖防范要求
- 2023-2024學年江蘇省太倉市小學語文五年級期末自測試卷
- 發(fā)展?jié)h語(第二版)高級綜合Ⅰ第8課課件
- 項目volume3修改版-舊20.commissioning servicing manualFMZ5000火災探測和滅火系統控制盤安裝調試維保手冊
- 消防安全常識二十條系列掛圖清晰版
評論
0/150
提交評論