第二章 一階邏輯

PAGEPAGE10一階邏輯基本概念[教學重點]量詞的概念、謂詞邏輯符號化的規(guī)則[教學目的]1：使學生理解謂詞邏輯的含義。2：熟練掌握量詞的意義。3[教學方法]講述法[課時安排]二課時。[教學過程]講述：命題邏輯是邏輯理論的基礎，是以命題為最小單元來分析研究推理理論的，現(xiàn)在來看如下日常生活中一個常見的推理。所有的人都是要死的；蘇格拉底是人。所以，蘇格拉底是要死的。符號化為： 顯然這是一個推理，但是是不正確的推理。日常推理卻是正確的。命題邏輯無法準確描述這個推理過程，原因在于命題邏輯本身未對各原子命題之間的內部成分的邏輯關系加以研究。為了更準確地對命題進行符號化，我們需要把一個邏輯判斷的對象和謂語分離并細化，分析出其中的個體詞、謂詞和量詞，研究它們的形式結構和邏輯關系，推理規(guī)則和推理形式，這就是本章的基本內容。本節(jié)主要討論一階邏輯（謂詞邏輯）的基本概念。板書講述謂詞邏輯是以謂詞為基礎的，類似以命題為基礎的命題邏輯首先從命題開始，我們這里也必須先從謂詞開始。在謂詞邏輯中，需要將簡單命題拆開，作為最為簡單的命題的陳述句，至少有主語和謂語組成，謂詞就是句子中相當謂語部分的詞，而把主語對應的部分稱為個體詞。板書：一、個體詞可以獨立存在的具體或抽象的客體。個體常項（a,b,c…全總個體域：將宇宙間的一切事物組成個體域。二、謂詞表示個體詞性質的或個體詞之間相互關系的詞謂詞常項：表示具體性質或關系的謂詞，用F、G、H…表示謂詞變項：表示抽象的、泛指的性質或關系的謂詞，也用F、G、H…表示n元謂詞：含有n個個體的謂詞n=0，0元謂詞，不含有任何個體變項的謂詞n=1，1元謂詞，以此類推。。示例1：H(a)，a：張華，H(x):“…是學生”H(x)是1元謂詞，不是命題，H(a)是0謂詞，是命題，示例2：小魏乘機去深圳；設：小魏，,,乘y去,提問：如何分析下列公式，，，1， 2。。。）n元謂詞（1，2），的n元函數(shù)。當P2an（a1a2an）才是命題。示例3：所有的人都要死的講述：板書：2A全稱量詞對應日常語言中的“一切x個體域里的所有個體都有性質。B存在量詞對應日常語言中的“存在著xF(xxF(x講述：符號化之前必須先明確個體域板書：第一種情況，個體域D為人類集合。xF(xF(x)：xxG(x)：x活百歲以上第二種情況，個體域為全總個體域這時必須引入一個特性謂詞，M(x)：x是人x(M(xF(x)F(x)：xx(M(x)G(x)G(x)：x在不同的個體域中，命題符號化的形式可能不一樣。如果事先沒有給出個體域，以全總個體域為個體域。引入特性謂詞后，使用全稱量詞與存在量詞符號化的形式是不同的。元謂詞要轉化為命題至少需要n個量詞。D={a1,a2an}，x)P(a1，y，z)P(a2，y，z)P(an，y，z)D={a1,a2anA(x)，有xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)∨A(a2)∨…∨A(an)這就是將謂詞邏輯中命題公式轉化為命題邏輯中的命題公式問題，叫做消去量詞等價式比如：對于任意的x，存在著y，使得x+y=5。取個體域為實數(shù)集。命題符號化為：xyH(x,y)，其中，H(x,y)：x+y=5。這是真命題如果將量詞顛倒，變?yōu)閥xH(x,y)，意義與原意不符，成了假命題。板書：例：求下列各式的真值（1）x(P(xQ(x。其中個體域D；一元謂詞P(x)：x1Q(x)：x2。（2）x(P(x)Q(x1。其中個體域D；一元謂詞P(x)：x2，Q(x)：x0。（3）x(PQ(xR(a。其中個體域D；零元謂詞1；一元謂詞Q(x)：x3R(x)：x5；個體常元。解（1）x(P(x)Q(x)) （2）x(P(x)Q(x))1(P(2)Q(2)) ((P(0)Q(0))(P(3)Q(3)))10)(0((00))111 0)11 1（3）x(PQ(x))R(a)((PQ(2))(PQ(3))(PQ(6)))R(5)((11)(11)(10))010)00下面舉幾個例子說明如何將命題符號化板書：例1：將下列命題符號化（1）所有的人都長著黑頭發(fā)。 （2）有的人登上過月球。（3）沒有人登上過火星。 （4）在美國留學的學生未必都是華人。解：本題沒有指明個體域，我們這里采用全總個體域。并設一元謂詞M(x)：x是人設P(x)：x長著黑頭發(fā)。命題符號化為x(M(x)P(x))這是個假命題。設P(x)：x登上過月球。命題符號化為x(M(x)P(x))或者x(M(x)P(x))這是個真命題。設P(x)：x登上過火星。命題符號化為x(M(x)P(x))這是個真命題。設P(x)：x是在美國留學的學生，Q(x)：x是華人。命題符號化為x(P(x)Q(x))或者x(P(x)Q(x))例2：兔子比烏龜跑的快有的兔子比所有的烏龜跑的快(4)不存在跑得同樣快的兩只兔子例3：解：1F(x):x是火車，G(x):x是輪船，H(x,y):x比y快。xy(F(x)G(y)H(x,y))2F(x):x是汽車，G(x):x是火車，H(x,y):x比y慢。x(F(x)y(G(y)H(x,y))或者xy(F(x)(G(y)H(x,y))例3：形式邏輯中有：**是***，**不是***兩句話，例如，“張三是教授”和“張三不是教授”。若其中一句是正確的，另一句就肯定不正確。請你構造出同時為真的兩個句子。)xF(x)4：當x趨向af(x)以b000|xa時，有|f(x)b。以實數(shù)集為個體域將該極限定義符號化解 令二元謂詞P(x，y)：x大于y，則P(xa|)P(|xa|表示：0xaP(f(x)b|)) 表示：|f(x)b所以該極限定義表示為xa|)P(|xa|f(x)b|))作業(yè)：P53，2.2，2.3一階邏輯合式公式及解釋[教學重點]公式解釋與賦值的意義，等值演算的規(guī)則[教學目的]1：使學生理解公式解釋和賦值的含義。2：熟習掌握等值演算的規(guī)則。3講述：上節(jié)討論了謂詞邏輯的謂詞、量詞、及符號化問題，按照命題邏輯講述的順序，下面需要涉及合式公式基本概念、公式的解釋和分類，然后是等值演算，最后就是推理理論。一、謂詞公式：個體常元：a,b,c,,ai,bi,ci,(i≥1)；個體變元：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)結詞∧,∨,,括號和逗號,), 。：個體常項和個體變項是項；如果,,,,,,,,,)是,,,的函數(shù)；c）只有有限次地使用（）生成的符號串才是項。合式公式（謂詞公式：原子公式：若P為不能再分解的一元或n元謂詞，P(x)或P(x1,x2,,xn)為原子公式。合式公式的遞歸定義為：原子公式為合式公式；若AA若A、B為合式公式，則ABAB、ABAB若AxxA只有有限次應用例：說明表達式P(f(a)，b)∧(x)(P(f(x)，g(x，f(x))Q(x))二、自由與約束在合式公式xA和xA中，稱x為指導變項，A為相應量詞的轄域。在轄域中，x的所有出現(xiàn)稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項的出現(xiàn)稱為自由出現(xiàn)。約束變元：約束出現(xiàn)的變元自由變元：非約束變元的變元。示例1：?x(P(x)→Q(y))∧R(y)答：?的轄域是P(x)→Q(y)，指導變元是x。整個公式中是約束出現(xiàn)，?x的約束是自由出示例2：(?xP(x,y)→R(y,z))∨ ?yQ(y)答：?的指導變元是x ，轄域是 P(x,y)(?xP(x,y)→R(y,中，是 x 約束出現(xiàn)且?x的約束，y，z 是自由出現(xiàn)。?yQ(y)中，?的指導變元是 y ，轄域是Q(y)， y 是約束出現(xiàn)。整個公式中， x 約束出現(xiàn)， y 既有約束出現(xiàn)又有自由出現(xiàn)，z 是自由出現(xiàn)在一個公式中，某一個體變元既可以自由出現(xiàn)，又可以約束出現(xiàn)。為了研究方便，而不致引起混淆，我們希望一個個體變元在同一個公式中只以一種身份出現(xiàn)，應用下面兩條規(guī)則可以做到這一點。1、約束變元的換名規(guī)則將量詞轄域中出現(xiàn)的某個約束變元及相應的指導變元，換成一個在轄域中未曾出現(xiàn)過的個體變元名。公式的其余部分不變。例如：(?xP(x,y)→R(y,zyQ(y)用ω?y(?xP(x,y)→R(y,z))∨?ωQ(ω)2、自由變元的替換規(guī)則對于謂詞公式中出現(xiàn)該自由變元的每一處，都使用同一個未在公式中出現(xiàn)過的變元替代。例如：(?xP(x,y)→R(y,z))∨ ?yQ(y)用ω?xy：(?xP(x,ω)→R(ω,z))∨?yQ(y)如果合式公式A中無自由變元，則稱A是封閉的。三、閉式設AAA式。閉式的重要性質：閉式在任何解釋下不是真就是假，不可能給出解釋I，使得閉式在I下真值不確定，這是閉式的一個重要特征。)→┑)→例：將下列兩個公式中的變項指定為常項使其成為命題：(1)x(F(x)→G(x))(2)xy(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))解(1)個體域 F(x) G(x) 命題 真全總 x是人 x是黃種人 所有人都是黃種人 1實數(shù) x是自然數(shù) x是整數(shù) 所有自然數(shù)都是整數(shù) 0(2)含兩個2元函數(shù)變項，一個1元謂詞變項，兩個2元謂詞變項。個體域 全總 x是實數(shù) y 2xy命題1：對于任意的，若x與y都是實數(shù)且≠，則真值為真。講述：以先給出解釋，再去解釋各種公式。四、謂詞邏輯公式的解釋和分類1、公式A的一個解釋：對公式A指定其中個體域的范圍，并指定其中謂詞的具體含義使其成為命題，一個一階語言中公式的解釋I包含：非空個體域個體域,上的函數(shù)集合{|1}，上的謂詞集合{|1}；P442.7，2.82、公式的分類邏輯有效式或永真式：在任何解釋中都為真的謂詞公式示例xP(x)xP(x)xPxP矛盾式或永假式：在任何解釋中都為假的謂詞公式可滿足式：至少有一個解釋能滿足的謂詞公式講述：顯然，判定一個謂詞公式是否為邏輯有效式或矛盾式，都要求所有的解釋滿足或不滿詞公式的永假、永真的判斷實際是異常的困難，在1936年，丘吉(A.(A.不過，幸好只要謂詞公式確實是永真的、或永假的，則有算法可在有限步內判定這個事實。五、代換實例設A0是含有命題變項p1,p2,…,pn的命題公式，A1,A2,…,An是n個謂詞公式，用Ai(1≤i≤n)處處代替A0中的pi，所得公式A稱為A0的代換實例。例如，F(xiàn)(x)G(x),xF(x)yG(y)等都是pq的代換實例，而x(F(x)G(x))等不是pq的代換實例。***重言式的代換實例都是永真式，矛盾式的代換實例都是矛盾式。例子見P45，例2.9一階邏輯等值式講述：邏輯推理。板書：一、等值式概念：設、是謂詞邏輯中任意的兩謂詞公式，若A 為邏輯有效式，則稱與等值的，記稱為謂詞邏輯等值。由于重言式及其代換實例都是邏輯有效式，因而命題邏輯中所提到的等值式及其代換實例都是謂詞邏輯中的等值式。例⑴?xF(x)??xF(x)∧?xF(x)是等值式，對應于A?A∧A；⑵?xF(x)→?xG(x)與┐?xF(x)∨?xG(x)對應于A→B?┐A∨B，也是等值的。在謂詞邏輯中也有置換規(guī)則：設(A)是含公式A的命題公式，(B)是用公式B置換了(A)中之后得到的命題公式，如果AB則(A) (B)。還有一些應用上很重要的等值式。1、量詞否定等值式：(1) xP(x)xP(x)(2) xP(x)xP(x)當個體域為有限集時，如何驗證？當給定個體域D為有限集時，比如D={a1,a2,…，an}，定理2.3-1的兩個等值式是容易驗證的。⑴┐?xA(x)?┐(A(a1)∧A(a2)∧…∧A(an))?┐A(a1)∨┐A(a2)∨……∨┐A(an)??x┐A(x)；⑵┐?xA(x)?┐(A(a1)∨A(a2)∨……∨A(an))?┐A(a1)∧┐A(a2)∧……∧┐A(an)??x┐A(x)。2、量詞轄域擴大或縮小的等值式：(1) x(P(x)Q)(x(P(x))Q)(2) x(P(x)Q)(x(P(x))Q)(3) x(P(x)Q)xP(x)Q(4) x(QP(x))QxP(x)(5) x(P(x)Q)(x(P(x))Q)(6) x(P(x)Q)(x(P(x))Q)(7) x(P(x)Q)xP(x)Q(8) x(QP(x))QxP(x)3、有關量詞分配的等值式：(1) x(P(x)Q(x))xP(x)xQ(x)(2) x(P(x)Q(x))xP(x)xQ(x)4（1）xyP(x，y)yxP(x，y)（2）xyP(x，y)yxP(x，y)5、有關蘊涵式的等值式：(1) x(P(x)Q(x))xP(x)xQ(x)(2) xP(x)xQ(x)x(P(x)Q(x))在命題演算中有時需將命題公式化成與之等價的規(guī)范形式