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

第四章(中)集合运算与逻辑演算第一节集合的基本概念3、A、B两个集合，B的元素都是A的元素，称B是A的子集。一、集合、元素、子集1、集合（Set）是在一定范围中确定的、可区别的事物组成的整体。一般用大写字母A、B、C、表示。2、属于集合的事物叫元素，简称为“元”（Element）。一般用小写字母a、b、c表示。A=﹛a,b,c,d﹜二、有限集（Finiteset）、无限集（Infiniteset）1、如果集合A包含了一定论域的一切元素，称为全集；通常用“I”表示。2、集合A的所有子集组成的集合称为A的幂集。如果集合A为幂集，用公式表示为P（A）。A的幂集的元素要比A的元素的个数多，例如P(﹛真，假﹜)=﹛￠，﹛真﹜，﹛假﹜﹛真，假﹜﹜，再如P(￠)=﹛￠﹜空集、全集、幂集第四章(中)集合运算与逻辑演算第二节集合的关系及其应用一、集合的关系：属于关系、包含关系、相等关系1、属于关系是元素与集合之间的关系，2、包含关系是子集与包含它的集合的关系；子集在后，称为“包含”，用符号表示，如BA。子集在前称为包含于，用表示，如AB；当A是B的真子集时，用符号表示。当两者互相包含时就是相等。也就是“AB并且BA”元素a是集合A的元素，用符号“∈”表示，a∈A。元素a不是集合A的元素，用符号“”表示，aA。AB用符号＝表示，即A=B∈属于Belongto不属于notbelongto包含于Included包含Include真包含trulyInclude真包含于trulyIncluded＝equalto第四章(中)集合运算与逻辑演算第三节集合的运算一并、交、差、补运算1、并运算是指集合相加的推演。两个集合的元素和。A集合的元素和B集合的元素组成的集合称为A与B的并集，也叫逻辑和，简称并（Union）；记为：A∪B。2、交运算是指集合相乘的推演。两个集合的公共元素。以属于A且属于B的元素为元素的集合称为A与B的交集，也叫逻辑积，简称为交（Intersection）记为：A∩B。3、差运算是指集合相减的推演。以属于A而不属于B的元素为元素组成的集合称为A与B的差集也叫逻辑差，简称为差，记为：A\BA与B可以是真包含也可以是交叉关系：如果A=﹛1，2，3﹜，B=﹛2，3，4﹜，则A\B=1并和交积第四章(中)集合运算与逻辑演算第三节集合的运算4、补运算集合的补运算是差运算的特例。以全集I与子集A的差集为元素的集合，叫做A的补集，简称补，记为：I\A，或理解这几个规律关键是理解外延和差交并补的含义，二、集合运算的规律还要在大脑中出现圆圈。1、交换律：适用于“并”和“交”，如：A∪B=B∪AA∩B=B∩A2、结合律：如：A∪（B∪C）=（A∪B）∪CA∩（B∩C）=（A∩B）∩C以上两个不用记，关键是下面两个。3、分配律：在并与交中，两者之一对于另一个都是可以分配的。A∪（B∩C）=（A∪B）∩（A∪C）A∩（B∪C）=（A∩B）∪（A∩C）\补Complement第四章(中)集合运算与逻辑演算第三节集合的运算4、德·摩根律（De.Morgan）：取补后（并交）互换A\（B∪C）=（A\B）∩（A\C）A\（B∩C）=（A\B）∪（A\C）第四章(中)集合运算与逻辑演算第四节真值联结词真值联结词是对日常语言联结词的一种抽象。它只保留了对命题真值关系的刻画。由一个命题变项（判断变项，命题变项，逻辑变项）定义的真值联结词称为一元真值联结词，由两个命题变项定义的的是二元真值联结词，由n个命题变项加以定义的是n元真值联结词。是一元真值联结词，∧∨→是二元真值联结词，这五个称为基本（或常用）真值联结词。第四章(中)集合运算与逻辑演算第四节真值联结词对真值联结词的进一步的研究表明：一、n元真值联结词共４n个，因此一元联结词共４个，二元真值联结词共16个，以此类推。二、任一真值联结词都可以用基本真值联结词定义。如p←q可定义为p→q三、在基本真值联结词｛，∧｝、｛，∨｝和｛，→｝中任意一组都可以定义其余的基本真值联结词，因而可以定义任一真值联结词第四章(中)集合运算与逻辑演算第五节真值形式的类型真值形式就是由命题变项和真值联结词合乎定义地构成的符号表达式单个命题变项如p也是真值形式，真值联结词在其中零次出现用命题变项和基本真值联结词就能刻画出任一复合命题的真值形式（符号表达式）。（p→q）∧（p←q）要注意括号的使用。括号内表示出简单命题构成复合命题的逻辑层次。有时括号不同，复合命题的逻辑内容也会随之发生改变可见重言式都是可真式，可真式不一定是重言式。真值形式的种类一、重言式（永真式）指在命题变项的任意一组赋值下都真。二、矛盾式（永假式）指在命题变项的任意一组赋值下都假。三、可真式（偶真式、可满足式）指命题变项至少在一组赋值下为真。第四章(中)集合运算与逻辑演算第六节用真值表方法对命题真值形式的类别进行判定真值就是真假值，也叫命题的逻辑值。普通形式逻辑是二值逻辑，对于它的任何命题来说，其真值只有两个：真或假。把一个真值形式中各个命题变项所取真值的每一种可能的组合排列成一个图表，就是真值表Truevaluetable真值表显示了复合命题的子命题的真假与复合命题本身真假的关系，反映了各种复合命题的逻辑性质（逻辑特性）我们可以用真值表方法对命题真值形式类别进行判定，步骤如下：一、用命题变项和基本真值联结词表示复合命题的真值形式。注意：其他真值联结词都可用基本真值联结词表示。（三）多重复合命题（p→q）（p∧q）二、把复合命题的形式逐层揭示出来（一）最小的子命题：p,q,p（二）基本的复合命题，所学的几种常见复合命题p→q，p∧q第四章(中)集合运算与逻辑演算第六节用真值表方法对命题真值形式的类别进行判定三、构造真值表：一般地n个命题变项的不同赋值共2n组。（一）找出所要判定的真值形式中所有不同的命题变项，并列出这些命题变项的所有各组不同的真值赋值。如单个命题变项的不同赋值共两组：真，假两个命题变项的不同赋值共四组：真真，真假，假真，假假。一般用T代表真，F代表假，也可用1代表真，0代表假直到列出这个复合命题的本身的真值形式。（二）由简到繁把某一复合命题真值形式的各层结构（子公式）列出，（三）根据基本真值联结词的定义和各复合命题的逻辑性质，计算出在命题变项的各组赋值下各层真值形式的真值，最后得出这个复合命题的的真值，然后看属于何类型的真值形式。第四章(中)集合运算与逻辑演算第六节用真值表方法对命题真值形式的类别进行判定练习3、判定（（p→q）∧p）→q是何类型的真值形式可真练习1、判定（p→q）（p∧q）是何类型的真值形式重言练习2、判定（p→q）∧（p∨q）是何类型的真值形式矛盾p→q,（p→q）∧p可单列两列求出其真值，相当于1和3T真TruthF假False第四章(中)集合运算与逻辑演算第七节真值表的其他功能真值表除了能判定真值形式的类型，还能一、真值判定通过真值表可以读出某一复合命题的真值形式在什么情况下是真，在什么情况下是假，这就是真值判定。二、等值判定利用真值表，可以判定几个复合命题形式是否等值。如判定（p←q）和（p∧q）以及p→q是否等值。三、矛盾命题的判定如果一对复合命题的真值形式在各组不同赋值下的真假完全相反那么这对复合命题是一对矛盾命题。如用真值表判定p∧q与（p∧q）是否是一对矛盾命题。（p←q）:并非只有上大学才能成才（p∧q）：不上大学，也可以成才p→q：如果上大学就可以成才第四章(中)集合运算与逻辑演算第八节真值形式类型的其他判定方法一、归谬赋值法（Valueassignedbyreductiontoabsurdity）：从理论上讲对于任意的真值形式都可以用真值表的方法对其类型加以判定，但实际上包含三个命题变项的真值形式构建起真值表来已经比较臃肿了，何况三个以上命题变项的复合命题了。归廖赋值法是一种运用归谬推理简化真值表的方法。也称为简化真值表法。复合推理都是蕴涵式，而归谬赋值法就是一种仅适用于蕴涵式（→）的推理是否是重言式的方法。（一）（二）为了证明一个蕴涵式是重言式必须证明它不可能装前件真且后假。（三）假设一个蕴涵式前件真而后件假而得出逻辑矛盾，则说明前件真后件假是不可能的，从而说明原蕴涵式是重言式，如果得不出逻辑矛盾，则说明前件真后件假是可能的，原蕴涵不是重言式第四章(中)集合运算与逻辑演算第八节真值形式类型的其他判定方法例如：判定(p∨q∨r)∧r→(p∨q)是否是重言式或者在出现在矛盾的下方划一横线。（（p∧q∧r）→s）→（s→（p→（q→r）））11111100101101001第四章(中)集合运算与逻辑演算第八节真值形式类型的其他判定方法二、范式的方法：合取范式和析取范式（一）简单析取式：（１）它的任一析取支是一命题变项或命题变项的否定如p∨q和p∨q∨r是，而p∨（q∧r）则不是一简单析取式是重言式当且仅当存在一命题变项及其否定同时是它的析取支（因其析取支总有一真）（２）如p∨q∨q是重言的简单析取式（二）简单合取式：（１）它的任一合取支是一命题变项或命题变项的否定如p∧q和p∧q∧r是，而p∧(q∨r)则不是一简单合取式是矛盾式当且仅当存在一命题变项及其否定同时是它的合取支（因其合取支总有一假）（２）如p∧q∧p是矛盾的简单合取式第四章(中)集合运算与逻辑演算第八节真值形式类型的其他判定方法（三）合取范式：（１）它的任一合取支都是简单析取式一合取范式是重言式，当且仅当它的任一合取支都是重言的简单析取式。（２）（四）析取范式：（１）它的任一析取支都是简单合取式一析取范式是矛盾式，当且仅当它的任一析取支都是矛盾的简单合取式。（２）（五）运用范式方法的步骤（１）先将真值形式中的→和消去把p→q换成p∨q，把pq换成(p∧q)∨(p∧q)（２）把逐步内移至命题变项前，消支双重否定号。把(p∨q)换成p∧q，把(p∧q)换成p∨q，把p换成p经过这两个步骤，真值形式中只有命题变项及其否定以及∧和∨运用合取分配律加以化简就得到原真值形式的析取范式，运用析取分配律加以化简就得到原真值形式的合取范式。（３）任何真值形式，运用上述方法都能在有限步骤内得到一个与之等值的范式。等值式第四章(中)集合运算与逻辑演算第八节真值形式类型的其他判定方法三、归谬式推理和反证式推理归谬式推理：如果从一个判断出发能推出自相矛盾的结论，则这个判断不成立1.如果p则q,如果p则非q。所以非p。2.反证式推理：如果否定一个判断能够推出自相矛盾的结论，则这个判断肯定成立如果非p则q,如果非p则非q。所以p。归谬式推理和反证式推理对于解某些逻辑运算特别有用，具体办法是：先假设某个前提或选项为真或为假，看能否从中推出矛盾。如果能推出矛盾，则原来的假设不成立，该假设的否定成立。如果不能推出矛盾，则该假设可能成立也可能不成立。第四章(中)集合运算与逻辑演算第八节真值形式类型的其他判定方法(p←q)是否等值p→q？(p←q)得到(p∧q)而p→q得到(p∨q)所以不等值。练习：用范式方法判定(p∧(p→q))→q是否为重言式。第四章(中)集合运算与逻辑演算第八节真值形式类型的其他判定方法如何用等价代换证明((p∨q)→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∧