数理逻辑命题逻辑.ppt

1、 两个集合两个集合 a和和 b相等相等 它们具有相同的元素。即对任意它们具有相同的元素。即对任意 集合集合a、b,a=b x(x ax b) 如果如果a的的 每一个元素都是每一个元素都是b的元素，则称的元素，则称集合集合a是是集合集合b的的 （或（或，subsets），或称），或称a包含在包含在b内，内， a b 或称或称b包含包含a，b a 。 即即 a b x(x ax b) 设设a，b，c为任意集合，根据定义，显然有：为任意集合，根据定义，显然有： 包含关系具有自反性包含关系具有自反性：a a 包含关系具有传递性：若包含关系具有传递性：若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 练习练习 设设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)设设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.范式的涵义：在数学中通常称之为范式的涵义：在数学中通常称之为“通式通式”。把命把命 题公式化归为一种标准的形式，称此标准形式为范式。题公式化归为一种标准的形式，称此标准形式为范式。 它是一种形式上有一定规律的公式，因而它具有一些它是一种形式上有一定规律的公式，因而它具有一些 形式方面的特征。凭借这种特征，我们就能确定一个形式方面的特征。凭借这种特征，我们就能确定一个 真值形式是不是重言式。

6、简单地说就是一个真值形式真值形式是不是重言式。简单地说就是一个真值形式 如果命题逻辑公式只包含联结词如果命题逻辑公式只包含联结词“合取合取”、“析取析取” 及及“否定否定”，并且其中否定符号只属于一个变项，那，并且其中否定符号只属于一个变项，那 么就是范式。如（么就是范式。如（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、是否为以有限次步骤来决定命题公式是否为 永真式、永假式，还是可满足的，或者判定二个命题永真式、永假式，还是可满足的，或者判定二个命题 公式是否等价等这一类的问题，统称为判定问题。公式是否等价等这一类的问题，统称为判定问题。 （1 1）若今天下雪）若今天下雪, ,则将去滑则将去滑 雪。今天下雪，所以去滑雪。今天下雪，所以去滑 雪。雪。 （2 2）现在气温在冰点以下。）现在气温在冰点以下。 因此，要么现在气温在冰因此，要么现在气温在冰 点以下，要么现在下雨。点以下，要么现在下雨。 （3 3）现在气温在冰点以下并）现在气温在冰点以下并 且正在下雨。因此，现在且正在下雨。因此，现在 气温在冰点以下。气

8、温在冰点以下。 （7 7）构造性二难推理规则）构造性二难推理规则 a ab b c cd d a a c c b b d d （8 8）破坏性二难推理规则）破坏性二难推理规则 a ab b c cd d b bd d a ac c （9 9） 合取引入规则合取引入规则 a a b b a a b b 例例 3 3 在 自 然 推 理 系 统在 自 然 推 理 系 统 p p 中 构 造 下 面 推 理 的 证 明 ：中 构 造 下 面 推 理 的 证 明 ： 若数若数a a是实数，则它不是有理数就是无理数；若是实数，则它不是有理数就是无理数；若a a不能表不能表 示成分数，则它不是有理数；示成

9、分数，则它不是有理数；a a是实数且它不能表示成分数。是实数且它不能表示成分数。 所以所以a a是无理数。是无理数。 有时推理的形式结构具有如下形式有时推理的形式结构具有如下形式 （a1a2ak)(ab) （1） （1）式中结论也为蕴涵式。此时可将结论中的前件也作为推理的前提，使结论只为）式中结论也为蕴涵式。此时可将结论中的前件也作为推理的前提，使结论只为b。 即，将（即，将（1）化为下述形式）化为下述形式 (a1a2aka)b （2） 其正确性证明如下：其正确性证明如下： （a1a2ak)(ab)） (a1a2ak)(a b） (a1a2aka)b (a1a2aka)b (a1a2aka)b

10、 （1）式与（）式与（2）式是等值的，因而若能证明（）式是等值的，因而若能证明（2）式是正确的，则（）式是正确的，则（1）式也是正确的。）式也是正确的。 用形式结构（用形式结构（2）式证明，将）式证明，将a称为附加前提，并称此证明法为附加前提证明法。称为附加前提，并称此证明法为附加前提证明法。 q 有时推理的形式结构具有如下形式：有时推理的形式结构具有如下形式： 前提：前提：a a1 1, , a a2 2, , , , a ak k 结论： 结论：b b q 如果将如果将bb作为前提能推出矛盾来，则说明推理正确。作为前提能推出矛盾来，则说明推理正确。 前提：前提：a a1 1, , a a2

11、 2, , , , a ak k, , b b 结论：矛盾结论：矛盾 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在自然推理系统在自然推理系统p p中构造下面推理的证明。中构造下面推理的证明。 如果小张守第一垒并且小李向如果小张守第一垒并且小李向b b队投球，则队投球，则a a队将

12、取胜；或者队将取胜；或者a a 队未取胜，或者队未取胜，或者a a队获得联赛第一名；队获得联赛第一名；a a队没有获得联赛的第一队没有获得联赛的第一 名；小张守第一垒。因此，小李没有向名；小张守第一垒。因此，小李没有向b b队投球。队投球。 构造证明：构造证明： （1 1）将简单命题符号化：）将简单命题符号化： 设设 p:p:小张守第一垒。小张守第一垒。 q:q:小李向小李向b b队投球。队投球。 r:a r:a队取胜。队取胜。 s:as:a队获得联赛第一名。队获得联赛第一名。 （2 2）形式结构：）形式结构： 前提：前提：(p(pq)q)r,r,r rs,s,s ,p s ,p 结论：结论：

13、q q （5 5）证明：）证明：用归谬法用归谬法 q q 结论的否定引入结论的否定引入 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 合取合取 由于最后一步由于最后一步为矛盾式为矛盾式，所以推理正确。，所以推理正确。 小节结束小节结束 1、用不同的方法验证下面推理是否正确。对于正确的推理还、用不同的方法验证下面推理是否正确。对于正确的推理还 要在要在p系统中给出证明。系统中给出证明。 （1） 前提：前提： pq, q 结论：结论： p （2） 前提：前提：qr, pr 结论：结论：qp 方法三方法三 直接观察出