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

第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算 第一节第一节 集合的基本概念集合的基本概念 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的幂集的元素要比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属于属于Belong to 不属于不属于not belong to包含于包含于Included 包含包含Include真包含真包含truly Include真包含于真包含于truly Includedequal to.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算 第三节第三节 集合的运算集合的运算一并、交、差、补运算并、交、差、补运算1、并运算 是指集合相加的推演。两个集合的元素和。A集合的元素和B集合的元素组成的集合称为A与B的并集，也叫逻辑逻辑和和，简称并（，简称并（Union）；记为：；记为：AB。2、交运算 是指集合相乘的推演。两个集合的公共元素。以属于A且属于B的元素为元素的集合称为A与B的交集，也叫逻辑逻辑积积，简称为交（，简称为交（Intersection）记为：）记为：AB。3、差运算 是指集合相减的推演。以属于以属于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=BA2、结合律：如：A（BC）=（AB）CA（BC）=（AB）C以上两个不用记，关键是下面两个。3、分配律：在并与交中，两者之一对于另一个都是可以分配的。A（BC）=（AB）（AC）A（BC）=（AB）（AC）补 Complement.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算 第三节第三节 集合的运算集合的运算4、德摩根律（De.Morgan）：取补后（并交）互换取补后（并交）互换 A（BC）=（AB）（AC）A（BC）=（AB）（AC）.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算 第四节真值联结词第四节真值联结词真值联结词真值联结词是对日常语言联结词的一种抽象。它只保留了对命题真值关系的刻画。由一个命题变项（判断变项，命题变项，逻辑变项）定义的真值联结词称为一元真值联结词一元真值联结词，由两个命题变项定义的的是二二元真值联结词元真值联结词，由n个命题变项加以定义的是n元真值联结词元真值联结词。是一元真值联结词，是二元真值联结词，这五个称为基本（或常用）真值联结词基本（或常用）真值联结词。.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算 第四节真值联结词第四节真值联结词对真值联结词的进一步的研究表明：一、n元真值联结词共n个，因此一元联结词共个，二元真值联结词共16个，以此类推。二、任一真值联结词都可以用基本真值联结词定义。如pq可定义为pq三、在基本真值联结词，、，和，中任意一组都可以定义其余的基本真值联结词，因而可以定义任一真值联结词.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第五节真值形式的类型第五节真值形式的类型真值形式真值形式就是由命题变项和真值联结词合乎定义地构成的符号表达式单个命题变项如p也是真值形式，真值联结词在其中零次出现 用命题变项和基本真值联结词就能刻画出任一复合命题的真值形式（符号表达式）。（pq）（pq）要注意括号的使用。括号内表示出简单命题构成复合命题的逻辑层次。有时括号不同，复合命题的逻辑内容也会随之发生改变可见重言式都是可真式，可真式不一定是重言式。真值形式的种类真值形式的种类一、重言式（永真式）一、重言式（永真式）指在命题变项的任意一组赋值下都真。二、矛盾式（永假式）二、矛盾式（永假式）指在命题变项的任意一组赋值下都假。三、可真式（偶真式、三、可真式（偶真式、可满足式可满足式）指命题变项至少在一组赋值下为真。.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第六节用真值表方法对命题真值形式的类别进行判定第六节用真值表方法对命题真值形式的类别进行判定 真值真值就是真假值真假值，也叫命题的逻辑值逻辑值。普通形式逻辑是二值逻辑二值逻辑，对于它的任何命题来说，其真值只有两个：真或假。把一个真值形式中各个命题变项所取真值的每一种可能的组合排列成一个图表，就是真值表真值表True value table真值表显示了复合命题的子命题的真假与复合命题本身真假的关系，反映了各种复合命题的逻辑性质逻辑性质（逻辑特性）我们可以用真值表方法对命题真值形式类别进行判定，步骤如下：一、用命题变项和基本真值联结词表示复合命题的真值形式。注意：其他真值联结词都可用基本真值联结词表基本真值联结词表示。（三）多重复合命题多重复合命题（p q）（pq）二、把复合命题的形式逐层揭示出来（一）最小的子命题子命题：p,q,p（二）基本的复合命题复合命题，所学的几种常见复合命题p q，p q.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第六节用真值表方法对命题真值形式的类别进行判定第六节用真值表方法对命题真值形式的类别进行判定 三、构造真值表：一般地n个命题变项的不同赋值共2n组。（一）找出所要判定的真值形式中所有不同的命题变项不同的命题变项，并列出这些命题变项的所有各组不同的真值赋值。如单个命题变项的不同赋值共两组：真，假两个命题变项的不同赋值共四组：真真，真假，假真，假假。一般用T代表真，F代表假，也可用1代表真，0代表假 直到列出这个复合命题的本身的真值形式。（二）由简到繁把某一复合命题真值形式的各层结构（子公式各层结构（子公式）列出，（三）根据基本真值联结词的定义和各复合命题的逻辑性质，计算出在命题变项的各组赋值下各层真值形式的真值，最后得出这个复合命题的的真值这个复合命题的的真值，然后看属于何类型的真值形式。.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第六节用真值表方法对命题真值形式的类别进行判定第六节用真值表方法对命题真值形式的类别进行判定 练习3、判定（pq）p）q是何类型的真值形式 可真 练习1、判定（pq）（pq）是何类型的真值形式 重言练习2、判定（pq）（pq）是何类型的真值形式 矛盾pq,（pq）p 可单列两列求出其真值，相当于1和3T真真Truth F假假False.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第七节第七节 真值表的其他功能真值表的其他功能真值表除了能判定真值形式的类型，还能 一、真值判定一、真值判定通过真值表可以读出某一复合命题的真值形式在什么情况下是真，在什么情况下是假，这就是真值判定。二、等值判定二、等值判定利用真值表，可以判定几个复合命题形式是否等值。如判定（pq）和（pq）以及pq是否等值。三、矛盾命题的判定三、矛盾命题的判定如果一对复合命题的真值形式在各组不同赋值下的真假完全相反那么这对复合命题是一对矛盾命题。如用真值表判定pq与（pq）是否是一对矛盾命题。（pq）:并非只有上大学才能成才（pq）：不上大学，也可以成才pq：如果上大学就可以成才.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第八节真值形式类型的其他判定方法第八节真值形式类型的其他判定方法一、归谬赋值法一、归谬赋值法 （Value assigned by reduction to absurdity）：）：从理论上讲对于任意的真值形式都可以用真值表的方法对其类型加以判定，但实际上包含三个命题变项的真值形式构建起真值表来已经比较臃肿了，何况三个以上命题变项的复合命题了。归廖赋值法是一种运用归谬推理简化真值表的方法。也称为简化真值表法简化真值表法。复合推理都是蕴涵式，而归谬赋值法就是一种仅适用于蕴归谬赋值法就是一种仅适用于蕴涵式（涵式（）的推理是否是重言式的方法。（一）（二）为了证明一个蕴涵式是重言式必须证明它不可能装前件真且后假。（三）假设一个蕴涵式前件真而后件假而得出逻辑矛盾，则说明前件真后件假是不可能的，从而说明原蕴涵式是重言式，如果得不出逻辑矛盾，则说明前件真后件假是可能的，原蕴涵不是重言式.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第八节真值形式类型的其他判定方法第八节真值形式类型的其他判定方法例如：判定(pqr)r(pq)是否是重言式或者在出现在矛盾的下方划一横线。或者在出现在矛盾的下方划一横线。（p q 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是重言的简单析取式（二）简单合取式：（二）简单合取式：（）它的任一合取支是一命题变项或命题变项的否定 如pq和pqr是，而p(qr)则不是 一简单合取式是矛盾式矛盾式当且仅当存在一命题变项及其否定同时是它的合取支（因其合取支总有一假）（）如pqp是矛盾的简单合取式.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第八节真值形式类型的其他判定方法第八节真值形式类型的其他判定方法（三）合取范式：（三）合取范式：（）它的任一合取支都是简单析取式一合取范式是重言式重言式，当且仅当它的任一合取支都是重言的简单析取式。（）（四）析取范式：（四）析取范式：（）它的任一析取支都是简单合取式一析取范式是矛盾式矛盾式，当且仅当它的任一析取支都是矛盾的简单合取式。（）（五）运用范式方法的步骤（五）运用范式方法的步骤（）先将真值形式中的和消去把pq换成 p q，把pq 换成(p q)(p q)（）把逐步内移至命题变项前，消支双重否定号。把(pq)换成pq，把(pq)换成pq，把p换成p经过这两个步骤，真值形式中只有命题变项及其否定以及只有命题变项及其否定以及 和和 运用合取分配律加以化简就得到原真值形式的析取范式，运用析取分配律加以化简就得到原真值形式的合取范式。（）任何真值形式，运用上述方法都能在有限步骤内得到一个与之等值的范式。等值式等值式.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第八节真值形式类型的其他判定方法第八节真值形式类型的其他判定方法三、归谬式推理和反证式推理三、归谬式推理和反证式推理归谬式推理：归谬式推理：如果从一个判断出发能推出自相矛盾的结论，则这个判断不成立1.如果如果p则则q,如果如果p则非则非q。所以非。所以非p。2.反证式推理：反证式推理：如果否定一个判断能够推出自相矛盾的结论，则这个判断肯定成立如果非如果非p则则q,如果非如果非p则非则非q。所以。所以p。归谬式推理和反证式推理对于解某些逻辑运算特别有用，具归谬式推理和反证式推理对于解某些逻辑运算特别有用，具体办法是：先假设某个前提或选项为真或为假，看能否从中体办法是：先假设某个前提或选项为真或为假，看能否从中推出矛盾。如果能推出矛盾，则原来的假设不成立，该假设推出矛盾。如果能推出矛盾，则原来的假设不成立，该假设的否定成立。如果不能推出矛盾，则该假设可能成立也可能的否定成立。如果不能推出矛盾，则该假设可能成立也可能不成立。不成立。.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第八节真值形式类型的其他判定方法第八节真值形式类型的其他判定方法(pq)是否等值是否等值pq？(pq)得到得到(p q)而而 pq得到得到(p q)所以不等值。所以不等值。练习：用范式方法判定练习：用范式方法判定(p(pq)q是否为重言式。是否为重言式。.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第八节真值形式类型的其他判定方法第八节真值形式类型的其他判定方法如何用等价代换证明(pq)r)s如何证明是永假式、永真式还是可满足式？(p q)r)s (p q)r)s)(s(p q)r)(p q)r)s)(s(p q)r)(p q)r)s)(s(p q)r)(p q)r)s)(s(p q)r)(p r)(q r)s)(s(p r)(q r)(p r)(q r)s)(s(p r)(q r)(p r)(q r)s)(r s(p q)(p r)(q r)(p r s)(q r s)(r s)(p q s)(p r s)(q r s)（析取范式）（析取范式）(p q s)(p r s)(q r s)(r s)(p q r s)(p r s)(q r s)（合取范式）（合取范式）.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第八节真值形式类型的其他判定方法第八节真值形式类型的其他判定方法如何用等价代换证明(pq)r)s如何证明是永假式、永真式还是可满足式？一个命题是永真式当且仅当它的析取范式包含一个命题符号及一个命题是永真式当且仅当它的析取范式包含一个命题符号及其否定式其否定式 一个命题是永假式当且仅当它的合取范式包含一个命题符号及一个命题是永假式当且仅当它的合取范式包含一个命题符号及其否定式其否定式 在题目的情况下，原命题为可满足式在题目的情况下，原命题为可满足式 若令若令r=p，那么析取范式化为：，那么析取范式化为：(p s)(p q s)(p s)(p q s)再令再令s=p，化为：，化为：p(p q)p(p q)此时，析取范式包含此时，析取范式包含p和和p，即为永真式。，即为永真式。.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第八节真值形式类型的其他判定方法第八节真值形式类型的其他判定方法.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第九节常用的重言式第九节常用的重言式 在现代命题逻辑中，一切符合规则的正确推理形式都表现为重言式并且视之为可以用数理符号刻画的逻辑规则命题逻辑规律下面是命题逻辑中常用的重言式第一部分：基本规律第一部分：基本规律分离律分离律（肯定前件律、充足理由律）：(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)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)等价否定等值式等价否定等值式：(p q)(pq)(pq)换位律换位律：(pq)(q p)结合律（结合律（Associative law）：）：(pq)r)(p(qr)(pq)r)(p(qr)幂等律幂等律（重写律）：合取简化律：(pp)p 析取简化律：(pp)p 永真消去律永真消去律：p(qq)p 或表示为p T说明一个永真的合取项不影响合取式的真假这个大写加粗的T是一个元语言符号，它不再是一个简单的变项，而代表一个永真式。前面真值表内的真假不大写前面真值表内的真假不大写 永假消去律永假消去律：p(qq)p或表示为p说明一个永假的析取项不影响析取式的真假.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第十节真值表的综合运用第十节真值表的综合运用 运用真值表可以解决现实中一些较为复杂的问题。如下：。李、赵、黄三人参加了厅长的公开选拔，已知下列情况是真的：李、赵、黄三人至少一人选上厅长。如果李选上，赵或黄也会选上。如果赵选上，李或黄也会选上。如果黄选上，赵和李则不会选上。赵、李至少有一人选不上。问谁选上厅长？.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第十节真值表的综合运用第十节真值表的综合运用 解：设“李选上厅长李选上厅长”为为p，“赵选上厅长赵选上厅长”为为q，“黄选上厅长黄选上厅长”为为r，则得出下逻辑形式：李、赵、黄三人至少一人选上厅长。李、赵、黄三人至少一人选上厅长。pqr 如果李选上，赵或黄也会选上。如果李选上，赵或黄也会选上。p(qr)如果赵选上，李或黄也会选上。如果赵选上，李或黄也会选上。q(pr)如果黄选上，赵和李则不会选上。如果黄选上，赵和李则不会选上。r(p p q)赵、李至少有一人选不上。赵、李至少有一人选不上。p q.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第十节真值表的综合运用第十节真值表的综合运用 真值表的综合运用真值表的综合运用pqr p q 11100111001100011110101011110110001101110111011101010101101100111111110001101111列出真值表如右：只有李赵选不上，黄选上才能同时满足条件从右表可以看出.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第十节真值表的综合运用第十节真值表的综合运用 练习：如课本练习：如课本162页第十题第页第十题第1题每题每2题第题第3题题.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第十节真值表的综合运用第十节真值表的综合运用.第第四四章章(中中)集集合合运运算算与与逻逻辑辑演演算算第十节真值表的综合运用第十节真值表的综合运用.