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