【正文】 x):x4, 公式為假 結(jié)論 : 非永真式的可滿足式 2022/8/27 離 散 數(shù) 學(xué) 65 練習(xí) 1 )2)(2(22 ???? xxx1. 在分別取個(gè)體域?yàn)? (a) D1=N (b) D2=R (c) D3為全總個(gè)體域 的條件下 , 將下面命題符號(hào)化，并討論真值 (1) 對(duì)于任意的數(shù) x，均有 解 設(shè) G(x): (a) ?xG(x) )2)(2(22 ???? xxx(b) ?xG(x) (c) 又設(shè) F(x):x是實(shí)數(shù) ?x(F(x)?G(x)) 真 真 假 2022/8/27 離 散 數(shù) 學(xué) 66 練習(xí) 1(續(xù) ) 解 設(shè) H (x)： x+7=5 (a) ?xH (x) (2) 存在數(shù) x，使得 x+7=5 (b) ?xH (x) (c) 又設(shè) F (x)： x為實(shí)數(shù) ?x (F (x)?H (x)) ? 本例說明：不同個(gè)體域內(nèi)，命題符號(hào)化形式可能不同（也可能相同），真值可能不同（也可能相同） . 真 真 假 2022/8/27 離 散 數(shù) 學(xué) 67 練習(xí) 2 ? 2. 在一階邏輯中將下列命題符號(hào)化 ? (1) 大熊貓都可愛 ? (2) 有人愛發(fā)脾氣 ? (3) 說所有人都愛吃面包是不對(duì)的 設(shè) F(x): x為大熊貓， G(x): x可愛 ?x(F(x)?G(x)) 設(shè) F(x): x是人， G(x): x愛發(fā)脾氣 ?x(F(x)?G(x)) 設(shè) F(x): x是人， G(x): x愛吃面包 ??x(F(x)?G(x)) 或 ?x(F(x)??G(x)) 2022/8/27 離 散 數(shù) 學(xué) 68 練習(xí) 2 ? (4) 沒有不愛吃糖的人 ? (5) 任何兩個(gè)不同的人都不一樣高 ? (6) 不是所有的汽車都比所有的火車快 設(shè) F(x): x是人， G(x): x愛吃糖 ??x(F(x)??G(x)) 或 ?x(F(x)?G(x)) 設(shè) F(x):x是人 , H(x,y), x與 y相同 , L(x,y): x與 y一樣高 ?x(F(x)??y(F(y)??H(x,y)??L(x,y))) 或 ?x?y(F(x)?F(y)??H(x,y)??L(x,y)) 設(shè) F(x):x是汽車 , G(y):y是火車 , H(x,y):x比 y快 ??x?y(F(x)?G(y)?H(x,y)) 或 ?x?y(F(x)?G(y)??H(x,y)) 2022/8/27 離 散 數(shù) 學(xué) 69 練習(xí) 3 ?x(2x=x) 假 yxyxgyxyxf ???? ),(,),(ayxyxF ?:),(3. 給定解釋 I 如下 : (a) 個(gè)體域 D=N (b) =2 (c) (d) 說明下列公式在 I 下的涵義 ,并討論真值 (1) ?xF(g(x,a),x) (2) ?x?y(F(f(x,a),y)?F(f(y,a),x)) ?x?y(x+2=y?y+2=x) 假 2022/8/27 離 散 數(shù) 學(xué) 70 練習(xí) 3 (3) ?x?y?zF(f(x,y),z) (5) ?xF(f(x,x),g(x,x)) (4) ?x?y?zF(f(y,z),x) ?x?y?z(y+z=x) 假 ?x?y?z(x+y=z) 真 ?x(x+x=x?x) 真 ? (3),(4)說明 ?與 ?不能隨意交換 2022/8/27 離 散 數(shù) 學(xué) 71 練習(xí) 4 ? 4. 證明下面公式既不是永真式，也不是矛盾式 : (1) ?x(F(x)?G(x)) (2) ?x?y(F(x)?G(y)?H(x,y)) 解釋 1: D1=N, F(x):x是偶數(shù) , G(x): x是素?cái)?shù) , 真 解釋 2: D2=N, F(x):x是偶數(shù) , G(x): x是奇數(shù) , 假 解釋 1: D1=Z, F(x):x是正數(shù) , G(x): x是負(fù)數(shù) , H(x,y):xy 真 解釋 2: D2=Z, F(x):x是偶數(shù) , G(x): x是奇數(shù) , H(x,y):xy 假 2022/8/27 離 散 數(shù) 學(xué) 72 練習(xí) 5 ? 5. 證明下列公式為永真式 : (1) (?xF(x)??yG(y))??xF(x)??yG(y) (2) ?x(F(x)?(F(x)?G(x))) (A?B)?A?B的代換實(shí)例 設(shè) I是任意的一個(gè)解釋 , 對(duì)每一個(gè) x?DI, F(x)?(F(x)?G(x))恒為真 謂詞公式的真假 非邏輯符號(hào)集 L, 由 L生成的一階語(yǔ)言 ?, ? 中公式 A,B ? 的一個(gè)解釋 I: DI,{Fm}m∈ M,{fn}n∈ N,{ck}k∈ K 在解釋 I中 : 對(duì)于 A的一個(gè)賦值 ζ : ζ在 I中滿足 A, 或者 ζ在 I中不滿足 A A在 I中為真 , 如果 I中任意賦值 ζ都滿足 A A在 I中為假 , 如果 I中任意賦值 ζ都不滿足 A 注意 : A在 I中不真并不意味 A在 I中假 A為永真式 , 如果 A在 ? 的任意一個(gè)解釋中都為真 A為永假式 , 如果 A在 ? 的任意一個(gè)解釋中都為假 A為可滿足式 , 如果至少存在 ? 的一個(gè)解釋使 A為真 考慮 : ―A→ B永真 ‖ 當(dāng)且僅當(dāng) ―172。A永真或者 B永真 ‖ ―A∨ B永真 ‖ 當(dāng)且僅當(dāng) ―A永真或者 B永真 ‖ 2022/8/27 離 散 數(shù) 學(xué) 74 小結(jié) 主要內(nèi)容 ? 個(gè)體詞、謂詞、量詞 ? 一階邏輯命題符號(hào)化 ? 一階語(yǔ)言 L ? 項(xiàng)、原子公式、 合式公式 ? 公式的解釋 ? 量詞的轄域、指導(dǎo)變?cè)?、個(gè)體變項(xiàng)的自由出現(xiàn)與約束出現(xiàn)、閉式、解釋 ? 公式的類型 ? 永真式 (邏輯有效式 )、矛盾式 (永假式 )、可滿足式 2022/8/27 離 散 數(shù) 學(xué) 75 基本要求 ? 準(zhǔn)確地將給定命題符號(hào)化 ? 理解一階語(yǔ)言的概念 ? 深刻理解一階語(yǔ)言的解釋 ? 熟練地給出公式的解釋 ? 記住閉式的性質(zhì)并能應(yīng)用它 ? 深刻理解永真式、矛盾式、可滿足式的概念 , 會(huì)判斷簡(jiǎn) 單公式的類型 2022/8/27 離 散 數(shù) 學(xué) 76 基本題型 題型 1 一階邏輯中命題符號(hào)化 題型 2 在一階邏輯中將簡(jiǎn)單的數(shù)學(xué)命題符號(hào)化 題型 3 給定解釋 , 解釋給定的公式 閉式在任何解釋下都是命題 , 而非閉式?jīng)]有這個(gè)性質(zhì) , 但非閉式在某些解釋下也可能是命題 . 題型 4 證明公式既不是永真式 , 也不是矛盾式 題型 5 證明永真式或永假式 2022/8/27 離 散 數(shù) 學(xué) 77 作業(yè) Page 6365 ? 5 ? 10 ? 11