定理20.9（可滿足性定理）設(shè)A是P(X)的協(xié)調(diào)子集,則存在.ppt

《定理20.9（可滿足性定理）設(shè)A是P(X)的協(xié)調(diào)子集,則存在.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。

1、定理20.9(可滿足性定理):設(shè)A是P(X)的協(xié)調(diào)子集，則存在賦值v:P(X)?Z2，使得v(A)?{1}。構(gòu)造P(X)?Z2的函數(shù)v,證明所構(gòu)造的v是賦值(即為同態(tài)映射)0元運(yùn)算:v(F)=0二元運(yùn)算:v(p?q)?=v(p)?v(q)(1)q?M(2)p?M(3)p?M,q?M定理20.10(完備性定理):設(shè)A?P(X),p?P(X)，若在Prop(X)中有A╞p，則在Prop(X)中有A┣p。引理20.6:設(shè)w=w(x1,…,xn)?P(X)，則╞w當(dāng)且僅當(dāng)w的真值函數(shù)fw是常值函數(shù)1。定理20.11:Prop(X)的有效性是

2、可判定的推論20.4:Prop(X)是可證明性可判定的。x>3,就無法用命題的形式來表示，含有變量。不能斷定x>3是真還是假。只有用變量x代之以具體的值時(shí)，如以5代替x的值時(shí)：就變成5>3,這是一個(gè)真命題。而當(dāng)x取值為2時(shí)，就是2>3，成了一個(gè)假命題。在數(shù)學(xué)中有下面三個(gè)命題：P：所有的有理數(shù)都是實(shí)數(shù)。Q：3是有理數(shù)。所以R：3是實(shí)數(shù)。當(dāng)前面兩個(gè)命題為真時(shí)，可得出第三個(gè)命題也是真的。即第三個(gè)命題是前兩個(gè)命題的邏輯推論。用符號P,Q,R分別表示這三個(gè)命題，則應(yīng)有{P,Q}╞R，但在命題邏輯中是無法得出此結(jié)論的。需要引進(jìn)新的邏輯系統(tǒng)——謂

3、詞邏輯第二十一章謂詞邏輯§1謂詞代數(shù)一、項(xiàng)與原子公式一數(shù)的平方與一數(shù)的平方根之和大于0”。命題涉及3個(gè)個(gè)體對象:兩個(gè)不確定數(shù)，x1,x2一個(gè)常數(shù)0，用c1表示；涉及3個(gè)函數(shù)，兩個(gè)一元運(yùn)算(即平方與平方根)，分別記為f1(1),f1(2)，求和運(yùn)算則是二元運(yùn)算，用f2(1)表示；最后，還有一個(gè)關(guān)于數(shù)的二元關(guān)系“大于”，用R2(1)表示。命題表示成R2(1)(f2(1)(f1(1)(x1),f1(2)(x2)),c1)。這個(gè)命題是否正確，取決于對x1,x2所作的賦值。若x1,x2都是非負(fù)實(shí)數(shù)且至少有一個(gè)不為0，則命題正確若x1,x2都為

4、0，則命題不正確。通過分解命題可以發(fā)現(xiàn)，命題的內(nèi)部結(jié)構(gòu)包含了下述內(nèi)容：(1)一些個(gè)體對象及對它們進(jìn)行的某些運(yùn)算；(2)關(guān)于這些對象的一個(gè)關(guān)系。思考：P40023