逻辑学课件4b逻辑学第四章(中)集合运算与逻辑演算

1、第四章(中) 集合运算与逻辑演算,第一节 集合的基本概念,3、a、b两个集合，b的元素都是a的元素，称b是a的子集。,一、集合、元素、子集,1、集合（set）是在一定范围中确定的、可区别的事物组成的整体。,一般用大写字母a、b、c、表示。,2、属于集合的事物叫元素，简称为“元” （element） 。,一般用小写字母a、b、c表示。 a=a, b, c, d,二、有限集（finite set）、无限集（infinite set）,1、如果集合a包含了一定论域的一切元素，称为全集；,i”表示。,2、集合a的所有子集组成的集合称为a的幂集。,如果集合a为幂集，用公式表示为p（a）。,a的幂集的元素

2、要比a的元素的个数多，例如 p(真，假)= ，真，假真，假， 再如p()= ,空集、 全集、幂集,第四章(中) 集合运算与逻辑演算,第二节 集合的关系及其应用,、集合的关系：属于关系、包含关系、相等关系,1、属于关系是元素与集合之间的关系，,2、包含关系是子集与包含它的集合的关系；,子集在后，称为“包含”，用符号 表示，如b a。,子集在前称为包含于，用 表示，如a b；,当a是b的真子集时，用符号 表示。,当两者互相包含时就是相等。也就是 “a b并且b a”,元素a是集合a的元素，用符号“”表示，aa。,元素a不是集合a的元素，用符号 “ ” 表示，a a。,a b,用符号表示，即a=b,

3、属于belong to 不属于not belong to,包含于included,包含include,真包含truly include,真包含于truly included,equal to,第四章(中) 集合运算与逻辑演算,第三节 集合的运算,并、交、差、补运算,1、并运算 是指集合相加的推演。 两个集合的元素和。,a集合的元素和b集合的元素组成的集合称为a与b的并集，,也叫逻辑和，简称并（union） ；记为：ab。,2、交运算 是指集合相乘的推演。 两个集合的公共元素。,以属于a且属于b的元素为元素的集合称为a与b的交集，,也叫逻辑积，简称为交（intersection）记为：ab。,3

4、、差运算 是指集合相减的推演。,以属于a而不属于b的元素为元素组成的集合称为a与b的差集,也叫逻辑差，简称为差，记为：ab,a与b可以是真包含也可以是交叉关系：,如果a=1，2，3，b=2，3，4，则ab=1,并和,交积,第四章(中) 集合运算与逻辑演算,第三节 集合的运算,4、补运算 集合的补运算是差运算的特例。,以全集i与子集a的差集为元素的集合，叫做a的补集，,简称补，记为：ia，或,理解这几个规律关键是理解外延和差交并补的含义，,二、集合运算的规律,还要在大脑中出现圆圈。,1、交换律：适用于“并”和“交”，,如：ab=ba ab=ba,2、结合律：,如：a（bc）=（ab）c,a（bc

5、）= （ab）c,以上两个不用记，关键是下面两个。,3、分配律：在并与交中，两者之一对于另一个都是可以分配的。,a（bc）=（ab）（ac）,a（bc）= （ab）（ac）, 补 complement,第四章(中) 集合运算与逻辑演算,第三节 集合的运算,4、德摩根律（de.morgan）：取补后（并交）互换,a（bc）=（ab）（ac）,a（bc）= （ab）（ac）,第四章(中) 集合运算与逻辑演算,第四节真值联结词,真值联结词是对日常语言联结词的一种抽象。,它只保留了对命题真值关系的刻画。,由一个命题变项（判断变项，命题变项，逻辑变项）定义的真值联结词称为一元真值联结词，由两个命题变项定

6、义的的是二元真值联结词，由n个命题变项加以定义的是n元真值联结词。,是一元真值联结词，是二元真值联结词，,这五个称为基本（或常用）真值联结词。,第四章(中) 集合运算与逻辑演算,第四节真值联结词,对真值联结词的进一步的研究表明：,一、n元真值联结词共n个，因此一元联结词共个，,二元真值联结词共16个，以此类推。,二、任一真值联结词都可以用基本真值联结词定义。,如pq可定义为pq,三、在基本真值联结词，、，和，中,任意一组都可以定义其余的基本真值联结词，,因而可以定义任一真值联结词,第四章(中) 集合运算与逻辑演算,第五节真值形式的类型,真值形式就是由命题变项和真值联结词合乎定义地构成的,符号表

7、达式,单个命题变项如p也是真值形式，真值联结词在其中零次出现,用命题变项和基本真值联结词就能刻画出任一复合命题的 真值形式（符号表达式）。,（pq）（ pq）,要注意括号的使用。括号内表示出简单命题构成复合命题的逻辑层次。有时括号不同，复合命题的逻辑内容也会随之发生改变,可见重言式都是可真式，可真式不一定是重言式。,真值形式的种类,一、重言式（永真式）指在命题变项的任意一组赋值下都真。,二、矛盾式（永假式）指在命题变项的任意一组赋值下都假。,三、可真式（偶真式、可满足式） 指命题变项至少在一组赋值下为真。,第四章(中) 集合运算与逻辑演算,第六节用真值表方法对命题真值形式的类别进行判定,真值就

8、是真假值，也叫命题的逻辑值。,普通形式逻辑是二值逻辑，对于它的任何命题来说， 其真值只有两个：真或假。,把一个真值形式中各个命题变项所取真值的每一种可能的组合排列成一个图表，就是真值表true value table,真值表显示了复合命题的子命题的真假与复合命题本身真假的关系，反映了各种复合命题的逻辑性质（逻辑特性）,我们可以用真值表方法对命题真值形式类别进行判定 ， 步骤如下：,一、用命题变项和基本真值联结词表示复合命题的真值形式。,注意：其他真值联结词都可用基本真值联结词表示。,（三）多重复合命题（p q）（ pq）,二、把复合命题的形式逐层揭示出来,（一）最小的子命题：p,q, p,（二

9、）基本的复合命题，所学的几种常见复合命题p q，p q,第四章(中) 集合运算与逻辑演算,第六节用真值表方法对命题真值形式的类别进行判定,三、构造真值表：,一般地n个命题变项的不同赋值共2n组。,（一）找出所要判定的真值形式中所有不同的命题变项，,并列出这些命题变项的所有各组不同的真值赋值。,如单个命题变项的不同赋值共两组：真，假,两个命题变项的不同赋值共四组：真真，真假，假真，假假。,一般用t代表真，f代表假，也可用1代表真，0代表假,直到列出这个复合命题的本身的真值形式。,（二）由简到繁把某一复合命题真值形式的各层结构（子公式）列出，,（三）根据基本真值联结词的定义和各复合命题的逻辑性质，

10、,计算出在命题变项的各组赋值下各层真值形式的真值，,最后得出这个复合命题的的真值，然后看属于何类型的真值形式。,第四章(中) 集合运算与逻辑演算,第六节用真值表方法对命题真值形式的类别进行判定,练习3、判定（pq）p）q是何类型的真值形式 可真,练习1、判定（pq）（pq）是何类型的真值形式 重言,练习2、判定（pq）（pq）是何类型的真值形式 矛盾,pq ,（pq） p 可单列两列求出其真值，相当于1和3,t真truth f假false,第四章(中) 集合运算与逻辑演算,第七节 真值表的其他功能,真值表除了能判定真值形式的类型，还能,一、真值判定,通过真值表可以读出某一复合命题的真值形式在什

11、么情况下是真， 在什么情况下是假，这就是真值判定。,二、等值判定,利用真值表，可以判定几个复合命题形式是否等值。 如判定（pq）和（pq）以及pq是否等值。,三、矛盾命题的判定,如果一对复合命题的真值形式在各组不同赋值下的真假完全相反那么这对复合命题是一对矛盾命题。,如用真值表判定pq与（pq）是否是一对矛盾命题。,（pq）: 并非只有上大学才能成才,（pq）：不上大学，也可以成才,pq ：如果上大学就可以成才,第四章(中) 集合运算与逻辑演算,第八节真值形式类型的其他判定方法,一、归谬赋值法 （value assigned by reduction to absurdity）：,从理论上讲对

12、于任意的真值形式都可以用真值表的方法对其类型加以判定，但实际上包含三个命题变项的真值形式构建起真值表来已经比较臃肿了，何况三个以上命题变项的复合命题了。,归廖赋值法是一种运用归谬推理简化真值表的方法。也称为简化真值表法。,复合推理都是蕴涵式，而归谬赋值法就是一种仅适用于蕴涵式（）的推理是否是重言式的方法。,（一）,（二）为了证明一个蕴涵式是重言式必须证明它不可能装前件真,且后假,。,（三）,假设一个蕴涵式前件真而后件假而得出逻辑矛盾，则说明前件真后件假是不可能的，从而说明原蕴涵式是重言式，如果得不出逻辑矛盾，则说明前件真后件假是可能的，原蕴涵不是重言式,第四章(中) 集合运算与逻辑演算,第八节

13、真值形式类型的其他判定方法,例如：判定(pqr) r(pq)是否是重言式,或者在出现在矛盾的下方划一横线。,（pq r）s） （ s （ p （q r）,1 1 1 1 1 1 0 0 1 0 1 1 0 1 0 0 1,第四章(中) 集合运算与逻辑演算,第八节真值形式类型的其他判定方法,二、范式的方法：合取范式和析取范式,（一）简单析取式：,（）它的任一析取支是一命题变项或命题变项的否定,如pq 和 pq r是，而 p（qr）则不是,一简单析取式是重言式当且仅当存在一命题变项及其否定同时是它的析取支（因其析取支总有一真）,（）,如pqq是重言的简单析取式,（二）简单合取式：,（）它的任一合取

14、支是一命题变项或命题变项的否定,如pq和pqr是，而p(qr ) 则不是,一简单合取式是矛盾式当且仅当存在一命题变项及其否定同时是它的合取支（因其合取支总有一假）,（）,如pqp是矛盾的简单合取式,第四章(中) 集合运算与逻辑演算,第八节真值形式类型的其他判定方法,（三）合取范式：,（）它的任一合取支都是简单析取式,一合取范式是重言式，当且仅当它的任一合取支都是重言的简单析取式。,（）,（四）析取范式：,（）它的任一析取支都是简单合取式,一析取范式是矛盾式，当且仅当它的任一析取支都是矛盾的简单合取式。,（）,（五）运用范式方法的步骤,（）先将真值形式中的和消去,把pq换成pq， 把pq 换成

15、( pq) (pq),（）把逐步内移至命题变项前，消支双重否定号。,把 (pq)换成pq，把 ( pq)换成pq，把p换成p,经过这两个步骤，真值形式中只有命题变项及其否定以及和,运用合取分配律加以化简就得到原真值形式的析取范式，运用析取分配律加以化简就得到原真值形式的合取范式。,（）,任何真值形式，运用上述方法都能在有限步骤内得到一个与之等值 的范式。,等值式,第四章(中) 集合运算与逻辑演算,第八节真值形式类型的其他判定方法,三、归谬式推理和反证式推理,归谬式推理：如果从一个判断出发能推出自相矛盾的结论，则这个判断不成立,1.,如果p则q, 如果p则非q。所以非p。,2.,反证式推理：如果

16、否定一个判断能够推出自相矛盾的结论，则这个判断肯定成立,如果非p则q, 如果非p则非q。所以p。,归谬式推理和反证式推理对于解某些逻辑运算特别有用，具体办法是：先假设某个前提或选项为真或为假，看能否从中推出矛盾。如果能推出矛盾，则原来的假设不成立，该假设的否定成立。如果不能推出矛盾，则该假设可能成立也可能不成立。,第四章(中) 集合运算与逻辑演算,第八节真值形式类型的其他判定方法,(pq) 是否等值pq？ (pq)得到 ( pq)而 pq得到 ( pq) 所以不等值。,练习：用范式方法判定 (p(pq) ) q是否为重言式。,第四章(中) 集合运算与逻辑演算,第八节真值形式类型的其他判定方法,

17、如何用等价代换证明(pq)r)s如何证明是永假式、永真式 还是可满足式？,(pq)r)s (pq)r)s)(s(pq)r) (pq)r)s)(s(pq)r) (pq)r)s)(s(pq)r) (pq)r)s)(s(pq)r) (pr)(qr)s)(s(pr)(qr) (pr)(qr)s)(s(pr)(qr) (pr)(qr)s)(rs(pq)(pr)(qr) (prs)(qrs)(rs)(pqs)(prs)(qrs) （析取范式） (pqs)(prs)(qrs)(rs)(pqrs)(prs)(qrs) （合取范式）,第四章(中) 集合运算与逻辑演算,第八节真值形式类型的其他判定方法,如何用等价

18、代换证明(pq)r)s如何证明是永假式、永真式 还是可满足式？,一个命题是永真式当且仅当它的析取范式包含一个命题符号及其否定式 一个命题是永假式当且仅当它的合取范式包含一个命题符号及其否定式 在题目的情况下，原命题为可满足式 若令r=p，那么析取范式化为： (ps)(pqs)(ps)(pqs) 再令s=p，化为：p(pq)p(pq) 此时，析取范式包含p和p，即为永真式。,第四章(中) 集合运算与逻辑演算,第八节真值形式类型的其他判定方法,第四章(中) 集合运算与逻辑演算,第九节常用的重言式,在现代命题逻辑中，一切符合规则的正确推理形式都表现为重言式,并且视之为可以用数理符号刻画的逻辑规则命题

19、逻辑规律,下面是命题逻辑中常用的重言式,第一部分：基本规律,分离律（肯定前件律、充足理由律）：(pq) p) q,同一律：p p,矛盾律： (p p ),排中律：pp,刻画充分条件假言推理肯定前件式,p p,第四章(中) 集合运算与逻辑演算,第九节常用的重言式,第二部分：重言蕴涵式（不会出现前真后假）,否后律（否定后件律）：(pq) q) p,刻画充分条件假言推理的否定后件式,否析律（析取否定肯定律）：(pq) p )q,刻画选言推理,合简律（合取分解律）：(pq) p(pq) q,刻画联言推理的分解式,连锁蕴涵律（三段论律）：(pq) (qr) ) (pr),刻画三段论,归谬律：(p(rr)

20、 )p,如从一个命题可以推出矛盾，那么这个命题是假,(pq) q )p,第四章(中) 集合运算与逻辑演算,第九节常用的重言式,第三部分：重言等值式,双否律（双重否定律）：q q,德摩根律 （de morgans law）,否定合取推理： (pq) (pq),否定析取推理： (pq) (pq),pq可以定义为 (pq)，而pq 可定义为 (pq),说明和可以相互定义,交换律（commutative law）：,合取交换律：(pq) ( qp),析取交换律：(pq) ( qp),分配律：,合取分配律：( (p(qr) (pq)(pr),分配,（去商店买p送q或r，最后只能选一个）,析取分配律：( (p(qr) (pq)(pr), 分配,蕴涵析取律：(pq) (pq),蕴涵析取互换推理，说明和可以互相定义,（distributive law）,第四章(中) 集合运算与逻辑演算,第九节常用的重言式,加元律（吸取律）：p (p (qq) ) p (p(qq) ),等值式：,等价等值式：(p q ) ( (pq ) (qp) ),等价否定等