【正文】 則稱(chēng) A為矛盾式或永假式（真值表最后一列全為 0） ?若 A至少存在一組賦值是成真賦值，則稱(chēng) A為可滿(mǎn)足式（真值表最后一列有 1） 2020/11/17 24 等值演算 ? 判斷公式性質(zhì)的辦法 ?真值表 ?等值演算將之演算成簡(jiǎn)單形式，判斷其性質(zhì) ? 定義 10 ?設(shè) A,B為 2個(gè)命題公式，若等價(jià)式 A B是重言式，則稱(chēng) A與 B是等值的，記做 A B ?? ：不是邏輯聯(lián)結(jié)詞，一個(gè)等值的記號(hào)，不能夠用＝（數(shù)值上的相等）代替 ?等值本質(zhì)上是指：公式 A和 B在任何解釋下都相等 2020/11/17 25 邏輯等值式 2020/11/17 26 邏輯等值式 2020/11/17 27 邏輯等值式 2020/11/17 28 等值演算 ? 利用等值式，將一個(gè)公式變換成另外一種形式的過(guò)程 ? 例子 2020/11/17 29 等值演算 2020/11/17 30 等值演算 2020/11/17 31 簡(jiǎn)單析取式及簡(jiǎn)單合取式 ? 簡(jiǎn)單析取式和簡(jiǎn)單合取式 定義 10：僅由有限個(gè)命題變項(xiàng)或其否定構(gòu)成的析取式稱(chēng)為，簡(jiǎn)單析取式；僅由有限個(gè)命題變項(xiàng)或其否定構(gòu)成的合取式稱(chēng)為，簡(jiǎn)單合取式 例子： 簡(jiǎn)單析取式： p, q, p∨ 172。q, 172。p∨ q, 172。p∨ 172。q∨ r 簡(jiǎn)單合取式： p, q, p∧ 172。q, 172。p∧ q, 172。p∧ 172。q∧ r 2020/11/17 32 合取范式 ? 定義 11： ?僅有有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱(chēng)為合取范式 A=A1∧ A2∧ … ∧ An 其中 A1， A2， … ， An為簡(jiǎn)單析取式 ?例子： A=(172。p∨ q∨ r)∧ (172。p∨ q)∧ (q∨ 172。q) ? 任何公式都有與其對(duì)應(yīng)的合取范式 2020/11/17 33 化成合取范式的步驟 ? 1. 消去對(duì) {172。， ∧ ， ∨ }來(lái)說(shuō)冗余的聯(lián)結(jié)詞 ? 2. 否定聯(lián)結(jié)詞的消除或內(nèi)移 ? 3. 利用分配率 2020/11/17 34 合取范式 ? 原子：命題常項(xiàng)或變項(xiàng) ? 文字：原子或原子的否定 ? 子句：文字的析取 ? 合取范式：子句的合取 ? 子句集：合取范式的集合表示 ?每一個(gè)合取項(xiàng)作為集合的元素 ?元素之間的關(guān)系為合取 2020/11/17 35 命題邏輯的問(wèn)題 ? 命題作為命題演算的基本單位，不再分解 ? 無(wú)法研究命題內(nèi)部的結(jié)構(gòu)和命題之間的聯(lián)系 ? 例子：蘇格拉底三段論 ?p:凡人都是要死的 ?q:蘇格拉底是人 ?r:蘇格拉底是要死的 ?命題符號(hào)化： (p∧ q)→ r 真值不定！ ? 解決問(wèn)題的辦法 ?將命題進(jìn)一步分解成：個(gè)體詞，謂詞和量詞等 ?研究它們的形式結(jié)構(gòu)和邏輯關(guān)系，總結(jié)出正確地推理形式和規(guī)則 ?一階謂詞邏輯 2020/11/17 36 二、一階謂詞邏輯 ? 簡(jiǎn)單命題的分解：個(gè)體詞和謂詞 ? 個(gè)體詞 ?指可以獨(dú)立存在的客體 ?可以表示具體的事物：李明，玫瑰花，自然數(shù) ?可以表示抽象的概念：思想 ? 謂詞 ?用于刻畫(huà)個(gè)體詞的 性質(zhì) 或個(gè)體詞之間的 關(guān)系 的詞 2是有理數(shù)， 是有理數(shù) 小李比小王高， … 比 … 高 2020/11/17 37 個(gè)體常項(xiàng)、個(gè)體變項(xiàng)和個(gè)體域 ? 個(gè)體常項(xiàng) ? 定義：表示具體或特定的詞 ? 表示：小寫(xiě)的英文字母 a,b,c,… 表示 ? 個(gè)體確定下來(lái) ? 個(gè)體變項(xiàng) ? 定義：泛指的個(gè)體的詞 ? 表示：小寫(xiě)的英文字母 x,y,z,… 表示 ? 個(gè)體沒(méi)有確定下來(lái) ? 個(gè)體域 ? 個(gè)體變項(xiàng)的取值范圍 ? 可以是一個(gè)有限的集合 {a,b,c} ? 也可以是一個(gè)無(wú)限的集合：全體自然數(shù)，全體實(shí)數(shù) ? 全總個(gè)體域：宇宙間的一切事物組成的個(gè)體域 2020/11/17 38 謂詞常項(xiàng)、謂詞變項(xiàng) ? 謂詞常項(xiàng) ?定義：表示具體性質(zhì)或關(guān)系的詞 ?表示：大寫(xiě)英文字母 F,G,H,… ? 謂詞變項(xiàng) ?定義：表示抽象或泛指的性質(zhì)或關(guān)系的詞 ?表示：大寫(xiě)英文字母 F,G,H,… F(x): x很高， x是無(wú)理數(shù) ,… 。 L(x,y):x比 y學(xué)習(xí)好 , x比 y大 ,… 。 2020/11/17 39 謂詞的元數(shù) ? 謂詞的元數(shù)：謂詞中包含的個(gè)體詞的個(gè)數(shù) ? n元謂詞：包含有 n個(gè)個(gè)體詞的謂詞 ?F(x)一元謂詞 ?L(x,y)二元謂詞 ? 有時(shí) n元謂詞：包含有 n個(gè)個(gè)體變項(xiàng)的謂詞 ?F(a): 0元謂詞 ?L(x,a):1元謂詞 2020/11/17 40 謂詞符號(hào)化的例子 ? 2是素?cái)?shù)且是偶數(shù) ?F(x): x是素?cái)?shù) 。G(x)： x是偶數(shù) ?a:2 ?F(a)∧ G(a) ? 如果 2大于 3，則 2大于 4 ?L(x,y): x大于 y ?a:2。 b:3 。 c:4 ?L(a,b)→ L(b,c) 2020/11/17 41 全稱(chēng)量詞和存在量詞 ? 謂詞符號(hào)化下面的句子 ?所有的人都是要死的 ?有的人活到 100歲以上 ? 量詞：表示數(shù)量的詞 ? 全稱(chēng)量詞 ?對(duì)應(yīng)于日常語(yǔ)言中的“一切”，“任意的”， ?“所有的” ?表示： ? xF(x） 2020/11/17 42 全稱(chēng)量詞和存在量詞 ? 存在量詞 ?對(duì)應(yīng)于日常語(yǔ)言中的“存在著”，“有一個(gè)”，“至少一個(gè)”等詞 ?表示： ? xF(x) 2020/11/17 43 謂詞符號(hào)化的例子 ? 所有的人都是要死的 ?定義謂詞： F(x）， x是要死的 ?個(gè)體域?yàn)槿w人類(lèi)時(shí)： xF(x） ?全總個(gè)體域 (沒(méi)有申明個(gè)體域 )： x(M(x)→ F(x)) ?特性謂詞： M(x) ? 有的人活到 100歲以上 ?定義謂詞： G(x） x活到 100歲以上 ?個(gè)體域?yàn)槿w人類(lèi)時(shí)： xG(x） ?全總個(gè)體域 (沒(méi)有申明個(gè)體域 )： x(M(x)∧ G(x)) 2020/11/17 44 量詞使用的注意事項(xiàng) 1. 不同的個(gè)體域，符號(hào)化的形式可能不一樣 2. 如果沒(méi)有給出個(gè)體域，都應(yīng)以全總個(gè)體域?yàn)閭€(gè)體域 3. 引入 特性謂詞 后，使用全稱(chēng)量詞和存在量詞符號(hào)化的形式不一樣 4. 個(gè)體詞和謂詞的涵義確定之后， n元謂詞轉(zhuǎn)化成命題至少要 n個(gè)量詞 2020/11/17 45 量詞使用的注意事項(xiàng) 5. 當(dāng)個(gè)體域?yàn)橛邢藜瘯r(shí)， D={a1,a2,… ,an},由量詞的意義可以看出，對(duì)于任意的謂詞 F(x)，都有 xF(x) F(a1)∧ F(a2)∧ … ∧ F(an) xF(x) F(a1)∨ F(a2)∨ … ∨ F(an) 6. 多個(gè)量詞同時(shí)出現(xiàn)，不能夠隨意顛倒它們的次序 x yH(x, y) x yH(x, y) 2020/11/17 46 一階謂詞邏輯中的命題符號(hào)化 ? 凡是有理數(shù)都可以表示成分?jǐn)?shù) ?不用引入特性謂詞的情況 xF(x) ?引入特性謂詞的情況 x(R(x)→ F(x)) 2020/11/17 47 一階謂詞邏輯中的命題符號(hào)化 ? 沒(méi)有不犯錯(cuò)誤的人 ? 沒(méi)有指定個(gè)體域，以全總個(gè)體域作為個(gè)體域 ? 謂詞： M(x) x是人； F(x): x犯錯(cuò)誤 ? 172。 x(M(x)∧ 172。F(x)) ? 在北京工作的人未必是北京人 ? F(x): x在北京工作； G(x): x是北京人 ? 172。 x(F(x)→ G(x)) 2020/11/17 48 謂詞公式的字母表 ? 定義 11 字母表 ?個(gè)體常項(xiàng) :a,b,c,… , ai,bi,ci,… , i=1 ?個(gè)體變項(xiàng) :x,y,z,… , xi,yi,zi,… , i=1 ?函數(shù)符號(hào) :f,g,h,… , fi,gi,hi,… , i=1 ?謂詞符號(hào) :F,G,H,… , Fi,Gi,Hi,… , i=1 ?量詞符號(hào) : , ?聯(lián)結(jié)詞符： 172。, ∧ , ∨ , → , ?逗號(hào)和括號(hào)： （，），， 2020/11/17 49 項(xiàng)的遞歸定義 ? 定義 12