1、2020/8/30,一階邏輯,1,一階(謂詞)邏輯,量詞 謂詞、函數(shù) 個(gè)體詞 個(gè)體域 全總個(gè)體域: 世界上的萬事萬物 特性謂詞: 表示所關(guān)注的對(duì)象的性質(zhì),2020/8/30,一階邏輯,2,蘇格拉底三段論,重新符號(hào)化：, , F( ), x, a 設(shè)：F(x)：x是人。G(x)：x是要死的。 a：蘇格拉底。 前提：x(F(x)G(x)，F(xiàn)(a) 結(jié)論：G(a),凡人都是要死的。 蘇格拉底是人。 所以，蘇格拉底是要死的。,2020/8/30,一階邏輯,3,注意：,在論域不同時(shí)，命題符號(hào)化的形式也不同 若未給出論域，則以全總個(gè)體域?yàn)檎撚?論域確定后，使用全稱量詞與存在量詞符號(hào)化形式不同 多個(gè)量詞同時(shí)

2、出現(xiàn)時(shí)，不能隨意顛倒次序 xy(xy) xy(xy),2020/8/30,一階邏輯,4,謂詞演算的形式系統(tǒng),字母表 公式 公理 推理規(guī)則,2020/8/30,一階邏輯,5,一階語言與一階邏輯,一階語言是用于一階邏輯的形式語言 一階邏輯是建立在一階語言上的邏輯體系,2020/8/30,一階邏輯,6,一階語言,謂詞演算形式系統(tǒng)語言,項(xiàng) （合式）公式,非邏輯符號(hào) 邏輯符號(hào),2020/8/30,一階邏輯,7,非邏輯符號(hào),個(gè)體常元: a, b, c, , a1, b1, c1, 函數(shù)符號(hào): f, g, h, , f1, g1, h1, 謂詞符號(hào): F, G, H, , F1, G1, H1, 把函數(shù)和謂

3、詞中的變?cè)苯訉懙椒?hào)后的括號(hào)中,如F(x,y,x), g(x,y)等 非邏輯符號(hào)集合常記為L,2020/8/30,一階邏輯,8,邏輯符號(hào),個(gè)體變?cè)? x, y, z, , x1, y1, z1, 量詞符號(hào): , 聯(lián)結(jié)詞符號(hào): , , , , 括號(hào)與逗號(hào): (, ), ，,2020/8/30,一階邏輯,9,字母表,個(gè)體常元: a, b, c, , a1, b1, c1, 函數(shù)符號(hào): f, g, h, , f1, g1, h1, 謂詞符號(hào): F, G, H, , F1, G1, H1, 個(gè)體變?cè)? x, y, z, , x1, y1, z1, 量詞符號(hào): , 聯(lián)結(jié)詞符號(hào): , , , , 括號(hào)與

4、逗號(hào): (, ), ，,2020/8/30,一階邏輯,10,L生成的一階語言,個(gè)體常元: a, b, c, , a1, b1, c1, 函數(shù)符號(hào): f, g, h, , f1, g1, h1, 謂詞符號(hào): F, G, H, , F1, G1, H1, 非邏輯符號(hào)并不一定都出現(xiàn) 一階語言隨著非邏輯符號(hào)的不同而不同，稱為由非邏輯符號(hào)集合L生成的一階語言。,2020/8/30,一階邏輯,11,L生成的一階語言舉例,如：非邏輯符號(hào) 個(gè)體常元: 0 函數(shù)符號(hào): + L1=0, + 如：非邏輯符號(hào) 個(gè)體常元: 0，1 函數(shù)符號(hào): +,* L2=0,1, +,*,2020/8/30,一階邏輯,12,L生成的

5、一階語言說明,非邏輯符號(hào)與所描述的特定對(duì)象有關(guān)。 邏輯符號(hào)是邏輯系統(tǒng)中的符號(hào)。 一階邏輯研究一階語言的一般性質(zhì)，而不是針對(duì)某個(gè)特定的一階語言。對(duì)一個(gè)具體的應(yīng)用而言，L通常是不言自明的，由使用的全部非邏輯符號(hào)組成。,2020/8/30,一階邏輯,13,一階(first order)邏輯的合式公式,項(xiàng) 原子公式 合式公式,2020/8/30,一階邏輯,14,項(xiàng)(term),個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng) 若(x1,x2,xn)是n元函數(shù), t1,t2,tn是項(xiàng), 則(t1,t2,tn)是項(xiàng) 所有的項(xiàng)都是有限次地應(yīng)用上述規(guī)則形成的 例如: a, x, f(a), g(a,x), g(x,f(a),2020/

6、8/30,一階邏輯,15,原子公式(atomic formula),若R(x1,x2,xn)是n元謂詞, t1,t2,tn是項(xiàng), 則R(t1,t2,tn)是原子公式 例如: F(a), G(a,y), F(f(a), G(x,g(a,y),2020/8/30,一階邏輯,16,合式公式(well-formed formula),原子公式是合式公式 若A是合式公式，則(A)是合式公式 若A,B是合式公式，則(AB), (AB), (AB), (AB)也是合式公式 若A是合式公式，則xA, xA也是合式公式 只有有限次地應(yīng)用上述規(guī)則形成的符號(hào)串才是合式公式,2020/8/30,一階邏輯,17,合式公

7、式（舉例）,x(F(x)y(G(y)H(x,y) F(f(a,a),b) F(x,y) 約定：省略多余括號(hào) 最外層 優(yōu)先級(jí)遞減： , ; ; , ,2020/8/30,一階邏輯,18,合式公式中的變項(xiàng),量詞轄域: 在xA, xA中, A是量詞的轄域. 例如: x(F(x)y(G(y)H(x,y) 指導(dǎo)變項(xiàng): 緊跟在量詞后面的個(gè)體變項(xiàng).例如: x(F(x)y(G(y)H(x,y) 約束出現(xiàn): 在轄域中與指導(dǎo)變項(xiàng)同名的變項(xiàng). 例如: x(F(x)y(G(y)H(x,y) 自由出現(xiàn): 既非指導(dǎo)變項(xiàng)又非約束出現(xiàn). 例如: y(G(y)H(x,y),2020/8/30,一階邏輯,19,合式公式中的變項(xiàng)(

8、舉例),H(x,y)xF(x)y(G(y)H(x,y) x 與 y 是指導(dǎo)變項(xiàng) x與y是約束出現(xiàn) x與 y是自由出現(xiàn) 注：同一變?cè)谕还街锌赡芗扔屑s束出現(xiàn)又有自由出現(xiàn),2020/8/30,一階邏輯,20,閉式(closed form),閉式: 無自由出現(xiàn)的變項(xiàng) 一般來說, 閉式表示的是命題, 例如 F(a) xF(x) F(x) y(G(y)H(x,y) 后兩個(gè)不是閉式,2020/8/30,一階邏輯,21,賦值(解釋interpret),對(duì)一個(gè)合式公式的賦值包括給出 個(gè)體域 謂詞 函數(shù) 個(gè)體常項(xiàng) 的具體含義,2020/8/30,一階邏輯,22,賦值(舉例),F(f(a,a),b) 賦值1：

9、 個(gè)體域是全體自然數(shù); a: 2; b: 4; f(x,y)=x+y; F(x,y): x=y 原公式賦值成: “2+2=4”。 賦值2： 個(gè)體域是全體實(shí)數(shù); a: 3; b: 5; f(x,y)=x-y; F(x,y): xy 原公式賦值成: “3-35”。,2020/8/30,一階邏輯,23,賦值,是否存在一種公式在任何賦值下都取相同的真值呢？,2020/8/30,一階邏輯,24,一階邏輯永真式(tautology),永真式:在各種賦值下取值均為真(邏輯有效式) 命題邏輯永真式: 在各種賦值下取值均為真(重言式) 永假式:在各種賦值下取值均為假(矛盾式) 命題邏輯永假式: 在各種賦值下取值均為假(矛盾式) 可滿足式：非永假式,2020/8/30,一階邏輯,25,代換實(shí)例,在含命題變項(xiàng)p1,p2,pn的命題公式中, 每個(gè)命題變項(xiàng)代換成一階邏輯公式所得到的式子, 稱為原來公式的代換實(shí)例. 例： F(x)