離散數(shù)學(xué)復(fù)習(xí)資料-展示頁(yè)
2024-08-20 10:25本頁(yè)面
【正文】 為邏輯有效式(永真式)；在任何解釋下謂詞公式A取真值0，公式A為永假式；至少有一個(gè)解釋使公式A取真值1，公式A稱(chēng)為可滿足式. 3. 前束范式 一個(gè)謂詞公式的前束范式仍是謂詞公式. 若謂詞公式F等值地轉(zhuǎn)化成 那么就是F的前束范式，其中Q1，Q2，…，Qk只能是或$，x1,x2,…,xk是個(gè)體變?cè)?，B是不含量詞的謂詞公式. 每個(gè)謂詞公式F都可以變換成與它等值的前束范式. 其步驟如下： ① 消去聯(lián)結(jié)詞174。F(y)217。G(x))，$x(F(x)217。；使用存在量詞$，特性謂詞后用217。謂詞是用來(lái)刻劃個(gè)體詞的性質(zhì)或事物之間關(guān)系的詞. 個(gè)體詞分個(gè)體常項(xiàng)(用a,b,c,…表示)和個(gè)體變項(xiàng)(用x,y,z,…表示)；謂詞分謂詞常項(xiàng)(表示具體性質(zhì)和關(guān)系)和謂詞變項(xiàng)(表示抽象的或泛指的謂詞)，用F,G,P,…表示. 注意，單獨(dú)的個(gè)體詞和謂詞不能構(gòu)成命題，將個(gè)體詞和謂詞分開(kāi)不是命題. h量詞，是在命題中表示數(shù)量的詞，量詞有兩類(lèi)：全稱(chēng)量詞，表示“所有的”或“每一個(gè)”；存在量詞$，表示“存在某個(gè)”或“至少有一個(gè)”. 在謂詞邏輯中，使用量詞應(yīng)注意以下幾點(diǎn)： (1) 在不同個(gè)體域中，命題符號(hào)化的形式可能不同，命題的真值也可能會(huì)改變. (2) 在考慮命題符號(hào)化時(shí)，如果對(duì)個(gè)體域未作說(shuō)明，一律使用全總個(gè)體域. (3) 多個(gè)量詞出現(xiàn)時(shí)，不能隨意顛倒它們的順序，否則可能會(huì)改變命題的含義. 謂詞公式只是一個(gè)符號(hào)串，沒(méi)有什么意義，但我們給這個(gè)符號(hào)串一個(gè)解釋?zhuān)顾哂姓嬷担妥兂梢粋€(gè)命題. 所謂解釋就是使公式中的每一個(gè)變項(xiàng)都有個(gè)體域中的元素相對(duì)應(yīng). 在謂詞邏輯中，命題符號(hào)化必須明確個(gè)體域，無(wú)特別說(shuō)明認(rèn)為是全總個(gè)體域。 推理方法有： 真值表法；等值演算法；主析取范式法，構(gòu)造證明法(直接證明法、附加前提證明法和間接證明法)第2章 謂詞邏輯 本章重點(diǎn)：謂詞與量詞，公式與解釋?zhuān)笆妒?，謂詞邏輯推理證明. Pi)，再利用分配律展開(kāi)，使得每個(gè)合取項(xiàng)(析取項(xiàng))的命題變項(xiàng)齊全；④ 將極小(極大)項(xiàng)按由小到大的順序排列，用S(P)表示. 5. 命題演算的推理理論 h設(shè)A1,A2,…,An,C是命題公式，如果是重言式，稱(chēng)C是前提集合{ A1,A2,…,An}的有效結(jié)論或{A1,A2,…,An}邏輯地推出C。Pi(Pi217。Pi，則添加Pi218。mi(Mi217。P(P218。216。216。)；② 將否定聯(lián)結(jié)詞216。171。218。 每項(xiàng)含有n個(gè)命題變項(xiàng)(變項(xiàng)字母齊全)的合取式(析取式)的析取(合取)為主析取(合取)范式. 任意命題公式都存在與之等值的范式，存在與之等值的主范式，且是惟一的. 求范式，包括求析取范式、合取范式、主析取范式和主合取范式. 關(guān)鍵有兩點(diǎn)：其一是準(zhǔn)確掌握范式定義；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，結(jié)果的前一步適當(dāng)使用冪等律. 求析取(合取)范式的步驟： ① 將公式中的聯(lián)結(jié)詞都化成216。216。Q,M11=216。Q,M10=216。Q，M01=P217。Q是極小項(xiàng)。216。P217。216。F(B). 4. 范式 h 析取(合取)范式，僅有有限個(gè)簡(jiǎn)單合取式(析取式)構(gòu)成的析取式(合取式)，就是析取(合取)范式. h 極小項(xiàng)(極大項(xiàng))，n個(gè)命題變項(xiàng)P1,P2,…,Pn，每個(gè)變項(xiàng)或它的否定兩者只有其一出現(xiàn)且僅出現(xiàn)一次，第i個(gè)命題變項(xiàng)或者其否定出現(xiàn)在從左起第i個(gè)位置上(無(wú)腳標(biāo)時(shí)，按字典序排列)，這樣的簡(jiǎn)單合取式(析取式)為極小項(xiàng)(極大項(xiàng)). 以?xún)蓚€(gè)命題變項(xiàng)為例，m00=216。定理1 設(shè)F(A)是含命題公式A的命題，F(xiàn)(B)是用命題公式B置換F(A)中的A之后得到的命題公式. 如果A219。Q取值1當(dāng)且僅當(dāng)P，Q真值相同.3. 命題公式、賦值與解釋?zhuān)}公式的分類(lèi)與判別 h命題公式與賦值，命題P含有n個(gè)命題變項(xiàng)P1，P2,…,Pn，給P1，P2,…,Pn各指定一個(gè)真值，稱(chēng)為對(duì)P的一個(gè)賦值(真值指派). 若指定的一組值使P的真值為1，則這組值為P的真指派；若使P的真值為0，則稱(chēng)這組值稱(chēng)為P的假指派. h命題公式分類(lèi)，在各種賦值下均為真的命題公式A，稱(chēng)為重言式(永真式)；在各種賦值下均為假的命題公式A，稱(chēng)為矛盾式(永假式)；命題A不是矛盾式，稱(chēng)為可滿足式；判定命題公式類(lèi)型的方法：其一是真值表法，任給公式，列出該公式的真值表，若真值表的最后一列全為1，則該公式為永真式；若真值表的最后一列全為0，則該公式是永假式；若真值表的最后一列既非全1，又非全0，. 利用基本等值式()，對(duì)給定公式進(jìn)行等值推導(dǎo)，若該公式的真值為1，則該公式是永真式；若該公式的真值為0，也非用假，(合取)范式法，該公式的主析取范式有2n個(gè)極小項(xiàng)(即無(wú)極大項(xiàng))，則該公式是永真式；該公式的主合取范式有2n個(gè)極大項(xiàng)(即無(wú)極小項(xiàng))，則該公式是永假式；該公式的主析取(或合取)范式的極小項(xiàng)(或極大項(xiàng))個(gè)數(shù)大于0小于2n,，則該公式是可滿足式.h等值式A219?！焙蚉，Q組成的復(fù)合命題. “171?！?等價(jià)聯(lián)結(jié)詞，P171。0的真值均為1. 在語(yǔ)句中，“如果P則Q”或“只有Q，才P，”表示為“P174。1，1174。Q的真值為1，亦即1174?！焙蚉，Q組成的復(fù)合命題，只有P取值為1，Q取值為0時(shí)，P174?！碧N(yùn)含聯(lián)結(jié)詞， P174。Q取值1，只要P，Q之一取值1，P218。216。Q)218。“(216?！痹谝粋€(gè)語(yǔ)句中都表示“或”的含義，前者表示相容或，后者表示排斥或不
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1