1、離散數學第2章 復習總結1. 基本概念基本概念 1 1、謂詞、謂詞 用W表示“要喝水”，用H表示“喜歡帥哥”。 2 2、個體常元、個體常元 如a表示“劉翔”，c表示“姚明”， 表示具體個體的小寫字母，稱為“個體常元”或個體常量，用字母表中靠前的字母表示常量。 3 3、個體變元、個體變元 “某某要喝水”表示為W(x)，x泛指所有的人，這些小字字母稱為“個體變元”。 4 4、全稱量詞、全稱量詞 符號“”，表示“所有”，稱為全稱量詞。 5 5、存在量詞、存在量詞 符號“”，表示“存在，有些、有部分”等的含義。 6 6、謂詞公式、謂詞公式 將單個謂詞公式如W(x)，帶量詞的謂詞如zM(z)，統稱為“謂

2、詞公式”。例題例例5 5 表示“所有人都要變老的，楊圣洪是人，所以楊圣洪也會變老的”。解解：個體域為全總個體域，即對個體變元的取值不做任何限。 H(x)表示對象x是人類， O(x)表示對象x變老， c表示個體常元“楊圣洪”，則 H(c)表示個體常元楊圣洪是人類， O(c)表示個體常元楊圣洪要變老，原句表示 (x(H(x)O(x)H(c)O(c)。1. 基本概念基本概念 7 7、項的定義、項的定義：個體常元與變元及其函數式為項。 (1)個體常元和個體變元是項。 (2)若(x1,x2, xn)是n元函數,t1,t2,tn是n個項,則(t1,t2, tn)是項。 (3)有限次使用(2)得到的表達式是

3、項。 8 8、原子公式、原子公式： 設R(x1,x2,xn)是n元謂詞，t1,t2,tn是項，則R(t1,t2, tn)是原子公式。 9 9、合式謂詞公式、合式謂詞公式： (1)原子公式是合式公式； (2)若A是合式公式，則(A)也是合式公式； (3)若A,B合式，則AB, AB, AB , AB 合式 (4)若A合式，則xA、 xA合式 (5)有限次使用(2)(4)得到的式子是合式。1. 基本概念基本概念 10 10、量詞的指導變元與轄域，變元的約束出現、自由出現、量詞的指導變元與轄域，變元的約束出現、自由出現 (1) (1) 量詞指導變元量詞指導變元：xA和xA中的x (2) (2) 量詞

4、轄域量詞轄域：xA和xA中的A為量詞/轄域 (3) (3) 變元的約束出現變元的約束出現：指導變元的每次出現(稱約束變元)。 (4) (4) 變元的自由出現變元的自由出現：不是約束出現的變元(稱自由變元) 。 1111、閉公式、閉公式： 不含自由變元的謂詞公式不含自由變元的謂詞公式 。 12 12、謂詞公式的類型、謂詞公式的類型 永真式永真式( (邏輯有效式邏輯有效式): ): 在任何解釋下均為真；在任何解釋下均為真； 永假式永假式( (矛盾式矛盾式): ): 在任何解釋下均為假；在任何解釋下均為假； 可滿足式可滿足式: : 至少存在一種至少存在一種解釋下為真；解釋下為真；例題例題例題 分析x

5、y(P(x,y)Q(y,z)xP(x,y)作用域與變元約束情況 解解：x、y的作用域是(P(x,y)Q(y,z)， x的作用域是P(x,y)。 將與自由變元同名約束變元yr， 將與前一個同名約束變元xs，則原公式 xr(P(x,r)Q(r,z)sP(s,y) 改名規則：改名規則：一般僅對約束變元改名一般僅對約束變元改名, , 后出現者約束變元也要改名。后出現者約束變元也要改名。1. 基本概念基本概念 13 13、代換實例、代換實例： 設A0是含命題變元p1,p2,.,pn的命題公式，A1,A2,.,An是n個謂詞公式(其中個體常元/變元/函數/謂詞公式都未確定含義)，將A0中pi的每次出現都換

6、成Ai，所得公式A稱為A0的代換實例。2. 謂詞公式真值謂詞公式真值方法：方法：個體常元的值、個體變元的值域、確定函數、謂詞公式的含義。例題例題例題： x y (F(x) F(y) G(x,y)H(f(x,y),g(x,y) f(x,y),g(x,y)是函數變元，一元謂詞公式是函數變元，一元謂詞公式F(x),二元謂詞二元謂詞G與與H。 x與與y的個體域：全總個體域。的個體域：全總個體域。 F(x):x是實數是實數 G(x,y):x y H(x,y):xy f(x,y)=x2+y2 g(x,y)=2xy 這時整個公式的含義：這時整個公式的含義： 對于任意的對于任意的x和和y，若，若x與與y是實數

7、且是實數且x y，那么，那么x2+y2 2xy ，其真值為其真值為1.3. 謂詞公式等值演算謂詞公式等值演算定義定義1 1 設設A A、B B是兩個是兩個合法的謂詞合法的謂詞公式公式, ,如果在任何解釋下兩個如果在任何解釋下兩個公式的公式的真值真值都相等，則稱都相等，則稱A A與與B B等值等值記為記為A AB B。定義定義2 2 設設A A、B B是兩個合法謂詞公式，如果在任何解釋下，是兩個合法謂詞公式，如果在任何解釋下，A AB B為永真式，則為永真式，則A A與與B B等值，記為等值，記為A AB B。3. 謂詞公式等值演算謂詞公式等值演算1 1、 xA(x) xA(x) A(aA(a1

8、 1) ) A(aA(a2 2) ) A(aA(an n) ) 個體域為個體域為有限有限 xA(x) xA(x) A(aA(a1 1) ) A(aA(a2 2) ) A(aA(an n) )2 2、量詞的德摩律量詞的德摩律 xA(x)xA(x)x x A(x) A(x) x A(x)x A(x)x x A(x) A(x) 3 3、量詞分配律量詞分配律 x(A(x)x(A(x) B(x)B(x)xA(x)xA(x)xB(x)xB(x) x(A(x)x(A(x) B(x)B(x)xA(x)xA(x) xB(x) xB(x)4 4、量詞作用域的收縮與擴張律量詞作用域的收縮與擴張律 (1) (1) /

9、 / x x(A(x)(A(x) B)B)/ / xA(x)xA(x) B A(x)B A(x)含含自由自由x x (2) (2) / / x x(A(x)(A(x) B)B)/ / xA(x)xA(x) B BB B不含有自由不含有自由x x5 5 、約束變元改名規則約束變元改名規則 將將A A中某量詞轄域中變元的中某量詞轄域中變元的每次約束每次約束出現，全部換成公式出現，全部換成公式中中未出現未出現的字母，所得到的公式記為的字母，所得到的公式記為B B，則，則A AB B 6 、置換規則：公式局部等值變換后置換規則：公式局部等值變換后, ,仍與原公式等值。仍與原公式等值。3. 謂詞公式等值

10、演算謂詞公式等值演算例題例題: x y(F(x) G(y)H(x,y) x y(F(x) G(y)H(x,y) x y(F(x) G(y)H(x,y)x y (F(x) G(y)H(x,y) 德摩律德摩律x y ( (F(x) G(y) H(x,y) pqp q x y( (F(x) G(y)H(x,y)德摩律德摩律x y(F(x) G(y)H(x,y) ppx y(F(x) G(y)H(x,y) 結合律結合律 4. 謂詞公式范式謂詞公式范式 定義定義：一個謂詞公式，如果量詞均在全式的開頭，它們的作用域延伸到整個公式的末尾，則該公式稱為前束范式，形如Q1x1Q2x2QkxkB，其中Qi為或，B

11、中不含有數量詞。 定理定理1 1：任何邏輯公式可轉換為前束范式。：任何邏輯公式可轉換為前束范式。 步驟步驟： (1)剔除不起作用的量詞；(2)若約束變元與自由變元同名則約束變元改名；(3)如果與前面的約束變元同名，則后者改名；(4)利用代換實例，將、轉換表示；(5) 將否定深入到原子公式的前面；(6)利用量詞轄域的擴張與收縮規律或利用量詞的分配律，將量詞移到最左邊 。4. 謂詞公式范式謂詞公式范式例例 5. 謂詞推理謂詞推理定義定義1 1 若在各種解釋下A1A2A3AnB只能為真,則稱為前提A1,A2,An可推出結論B。定義定義2 2 當A1A2A3An為真時B為真，即當A1,A2,A3,An為真時B為真。: : 5. 謂詞推理謂詞推理例例 x(F(x) H(x), x(G(x) H(x) x(G(x) F(x)證明證明:(1) x(F(x) H(x)為真為真 (前提前提)(2) x( F(x) H(x)為真為真 (與與(1)等值等值)(3) F(x0) H(x0)