數(shù)理邏輯命題邏輯.ppt

1、 兩個集合兩個集合 a和和 b相等相等 它們具有相同的元素。即對任意它們具有相同的元素。即對任意 集合集合a、b,a=b x(x ax b) 如果如果a的的 每一個元素都是每一個元素都是b的元素，則稱的元素，則稱集合集合a是是集合集合b的的 （或（或，subsets），或稱），或稱a包含在包含在b內(nèi)，內(nèi)， a b 或稱或稱b包含包含a，b a 。 即即 a b x(x ax b) 設(shè)設(shè)a，b，c為任意集合，根據(jù)定義，顯然有：為任意集合，根據(jù)定義，顯然有： 包含關(guān)系具有自反性包含關(guān)系具有自反性：a a 包含關(guān)系具有傳遞性：若包含關(guān)系具有傳遞性：若a b且且b c，則，則a c。 a b或或b a

2、 ，也可能兩者均不成立，不，也可能兩者均不成立，不 是兩者必居其一。是兩者必居其一。 例：例：a=1，2，3，b=1，2，c=1，3， d=3，f=1，4， 則則b a， c a， d c， f a a c b a b c d e f g h ij 練習練習 設(shè)設(shè)a=a,b,c,a,a,ba=a,b,c,a,a,b，試指出下列，試指出下列 論斷是否正確？論斷是否正確？ (1)a(1)a a ( ) (8)ba ( ) (8)b a ( )a ( ) (2)a (2)a a ( ) (9)a,ba ( ) (9)a,b a ( )a ( ) (3)a (3)a a ( ) (10)a,ba (

3、) (10)a,b a ( )a ( ) (4) (4) a ( ) (11)ca ( ) (11)c a ( )a ( ) (5) (5) a ( ) (12)ca ( ) (12)c a ( )a ( ) (6)b (6)b a ( ) (13)ca ( ) (13)c a ( )a ( ) (7)b (7)b a ( ) (14)a,b,ca ( ) (14)a,b,c a ( )a ( ) 證明：證明： a)設(shè)設(shè)s= a (b c)，t= (a b) (a c)，若，若x s，則，則x a且且x b c，即，即x a且且 x b或或 x a且且 x c， x a b或或x a c即即x

4、 t，所以，所以s t。 反之，若反之，若x t，則，則x a b或或x a c， x a且且 x b或或 x a且且 x c，即，即x a且且x b c，于是，于是x s，所以，所以t s。 因此，因此，s=t。 b)證明完全與證明完全與a)類似。類似。 證明：證明： a)a (a b)=(a e) (a b) =a (e b)=a e=a b)a (a b)=(a a) (a b) =a (a b)=a 證明：若證明：若a b，對任意，對任意x a必有必有x b，對任意，對任意x a b，則，則x a或或x b，即，即x b，所以 ，所以a b b。 又又b a b ，因此得到，因此得到a

5、 b=b 。 反之，若反之，若a b=b，因為，因為a a b ，所以，所以a b 。 同理可證得同理可證得a b=a 約定：若約定：若a=或或b=，則，則a b= ，b a= 四、范式：四、范式： 1.1.范式的涵義：在數(shù)學中通常稱之為范式的涵義：在數(shù)學中通常稱之為“通式通式”。把命把命 題公式化歸為一種標準的形式，稱此標準形式為范式。題公式化歸為一種標準的形式，稱此標準形式為范式。 它是一種形式上有一定規(guī)律的公式，因而它具有一些它是一種形式上有一定規(guī)律的公式，因而它具有一些 形式方面的特征。憑借這種特征，我們就能確定一個形式方面的特征。憑借這種特征，我們就能確定一個 真值形式是不是重言式。

6、簡單地說就是一個真值形式真值形式是不是重言式。簡單地說就是一個真值形式 如果命題邏輯公式只包含聯(lián)結(jié)詞如果命題邏輯公式只包含聯(lián)結(jié)詞“合取合取”、“析取析取” 及及“否定否定”，并且其中否定符號只屬于一個變項，那，并且其中否定符號只屬于一個變項，那 么就是范式。如（么就是范式。如（p p q)q) ( r r s)s) ( ( p p q)q)就是范式。就是范式。 而（而（p p q q） （q q r r） s s就不是范式，因為其中的就不是范式，因為其中的 屬于（屬于（q q r r）的整體，不合范式的涵義。）的整體，不合范式的涵義。 2.2.判定的涵義：判定的涵義：以有限次步驟來決定命題公式

7、是否為以有限次步驟來決定命題公式是否為 永真式、永假式，還是可滿足的，或者判定二個命題永真式、永假式，還是可滿足的，或者判定二個命題 公式是否等價等這一類的問題，統(tǒng)稱為判定問題。公式是否等價等這一類的問題，統(tǒng)稱為判定問題。 （1 1）若今天下雪）若今天下雪, ,則將去滑則將去滑 雪。今天下雪，所以去滑雪。今天下雪，所以去滑 雪。雪。 （2 2）現(xiàn)在氣溫在冰點以下。）現(xiàn)在氣溫在冰點以下。 因此，要么現(xiàn)在氣溫在冰因此，要么現(xiàn)在氣溫在冰 點以下，要么現(xiàn)在下雨。點以下，要么現(xiàn)在下雨。 （3 3）現(xiàn)在氣溫在冰點以下并）現(xiàn)在氣溫在冰點以下并 且正在下雨。因此，現(xiàn)在且正在下雨。因此，現(xiàn)在 氣溫在冰點以下。氣

8、溫在冰點以下。 （7 7）構(gòu)造性二難推理規(guī)則）構(gòu)造性二難推理規(guī)則 a ab b c cd d a a c c b b d d （8 8）破壞性二難推理規(guī)則）破壞性二難推理規(guī)則 a ab b c cd d b bd d a ac c （9 9） 合取引入規(guī)則合取引入規(guī)則 a a b b a a b b 例例 3 3 在 自 然 推 理 系 統(tǒng)在 自 然 推 理 系 統(tǒng) p p 中 構(gòu) 造 下 面 推 理 的 證 明 ：中 構(gòu) 造 下 面 推 理 的 證 明 ： 若數(shù)若數(shù)a a是實數(shù)，則它不是有理數(shù)就是無理數(shù)；若是實數(shù)，則它不是有理數(shù)就是無理數(shù)；若a a不能表不能表 示成分數(shù)，則它不是有理數(shù)；示成

9、分數(shù)，則它不是有理數(shù)；a a是實數(shù)且它不能表示成分數(shù)。是實數(shù)且它不能表示成分數(shù)。 所以所以a a是無理數(shù)。是無理數(shù)。 有時推理的形式結(jié)構(gòu)具有如下形式有時推理的形式結(jié)構(gòu)具有如下形式 （a1a2ak)(ab) （1） （1）式中結(jié)論也為蘊涵式。此時可將結(jié)論中的前件也作為推理的前提，使結(jié)論只為）式中結(jié)論也為蘊涵式。此時可將結(jié)論中的前件也作為推理的前提，使結(jié)論只為b。 即，將（即，將（1）化為下述形式）化為下述形式 (a1a2aka)b （2） 其正確性證明如下：其正確性證明如下： （a1a2ak)(ab)） (a1a2ak)(a b） (a1a2aka)b (a1a2aka)b (a1a2aka)b

10、 （1）式與（）式與（2）式是等值的，因而若能證明（）式是等值的，因而若能證明（2）式是正確的，則（）式是正確的，則（1）式也是正確的。）式也是正確的。 用形式結(jié)構(gòu)（用形式結(jié)構(gòu)（2）式證明，將）式證明，將a稱為附加前提，并稱此證明法為附加前提證明法。稱為附加前提，并稱此證明法為附加前提證明法。 q 有時推理的形式結(jié)構(gòu)具有如下形式：有時推理的形式結(jié)構(gòu)具有如下形式： 前提：前提：a a1 1, , a a2 2, , , , a ak k 結(jié)論： 結(jié)論：b b q 如果將如果將bb作為前提能推出矛盾來，則說明推理正確。作為前提能推出矛盾來，則說明推理正確。 前提：前提：a a1 1, , a a2

11、 2, , , , a ak k, , b b 結(jié)論：矛盾結(jié)論：矛盾 q 理由：理由：a a1 1 a a2 2 a ak kb b ( (a a1 1 a a2 2 a ak k) ) b b ( (a a1 1 a a2 2 a ak kb b) ) q若若a a1 1 a a2 2 a ak kb b為矛盾式，則說明為矛盾式，則說明( (a a1 1 a a2 2 a ak kb b) ) 為重言式。為重言式。 例例5 5在自然推理系統(tǒng)在自然推理系統(tǒng)p p中構(gòu)造下面推理的證明。中構(gòu)造下面推理的證明。 如果小張守第一壘并且小李向如果小張守第一壘并且小李向b b隊投球，則隊投球，則a a隊將

12、取勝；或者隊將取勝；或者a a 隊未取勝，或者隊未取勝，或者a a隊獲得聯(lián)賽第一名；隊獲得聯(lián)賽第一名；a a隊沒有獲得聯(lián)賽的第一隊沒有獲得聯(lián)賽的第一 名；小張守第一壘。因此，小李沒有向名；小張守第一壘。因此，小李沒有向b b隊投球。隊投球。 構(gòu)造證明：構(gòu)造證明： （1 1）將簡單命題符號化：）將簡單命題符號化： 設(shè)設(shè) p:p:小張守第一壘。小張守第一壘。 q:q:小李向小李向b b隊投球。隊投球。 r:a r:a隊取勝。隊取勝。 s:as:a隊獲得聯(lián)賽第一名。隊獲得聯(lián)賽第一名。 （2 2）形式結(jié)構(gòu)：）形式結(jié)構(gòu)： 前提：前提：(p(pq)q)r,r,r rs,s,s ,p s ,p 結(jié)論：結(jié)論：

13、q q （5 5）證明：）證明：用歸謬法用歸謬法 q q 結(jié)論的否定引入結(jié)論的否定引入 r rs s 前提引入前提引入 s s 前提引入前提引入 r r 析取三段論析取三段論（否定肯定律）（否定肯定律） (p (pq)q)r r 前提引人前提引人 (p(pq)q) 拒取式拒取式 p pq q 置換置換 p p 前提引入前提引入 q q 析取三段論析取三段論 q qq q 合取合取 由于最后一步由于最后一步為矛盾式為矛盾式，所以推理正確。，所以推理正確。 小節(jié)結(jié)束小節(jié)結(jié)束 1、用不同的方法驗證下面推理是否正確。對于正確的推理還、用不同的方法驗證下面推理是否正確。對于正確的推理還 要在要在p系統(tǒng)中給出證明。系統(tǒng)中給出證明。 （1） 前提：前提： pq, q 結(jié)論：結(jié)論： p （2） 前提：前提：qr, pr 結(jié)論：結(jié)論：qp 方法三方法三 直接觀察出