电子科技大学王丽杰老师离散数学课程个人学习笔记
集合是由指定范围内的满足给定条件的所有对象聚集在一起构成，每一个对象称为这个集合的元素
\(|\{\varnothing\}|\)是空集作为集合中的一个元素，所以集合基数为1
针对一个具体范围，我们考虑的所有对象的集合叫做全集(universalset)，记作\(U\)或\(E\)
在文氏图一般使用方形表示全集
两个集合A和B相等，当且仅当它们的元素完全相同，记为\(A=B\),否则A和B不相等，记为\(A\neB\)
如果B的每个元素都是A中的元素，则称B是A的子集，也称做B被A包含或A包含B，记作\(B\subseteqA\)，否则记作$B\not\subseteqA$
如果\(B\subseteqA\)并且\(A\neB\)，则称B是A的真子集，也称做B被A真包含或A真包含B，记作\(B\subsetA\)，否则记作\(B\not\subsetA\)
∈是「属于」的意思，用在「元素」属于「集合」的时候，比如Ａ是集合，元素有｛a,b,c｝，那麽a∈Ａ。是「包含于」的意思，用在「集合」属于「集合」的时候，比如Ａ是Ｂ的子集合，我们就可以说ＡＢ
设A,B为任意两个集合，则\(A=B\LeftrightarrowA\subseteqB\text{并且}B\subseteqA\)
对于任意n元集合A，它的m元\((0\lem\len)\)子集个数为\(C_n^m\)个所以不同的子集个数为：\(C_n^0+C_n^1+...+\)\(C_n^n=(1+1)^n=2^n\)
设U为全集，A，B，C为任意集合
证明集合A和B相等，通常方法是证明两个集合间的相互包容关系，即\(A=B\LeftrightarrowA\subseteqB\text{并且}B\subseteqA\)
而证明集合的包含关系则使用如下方法
对于两个有限集合而言，比较二者大小只需要看集合的基数
对于无限集合需要采用一种通过判断两个无限集合之间是否存在一种一一对应的关系来解决这个问题
equipotentia。若在A,B之间存在一种一一对应的关系
凡与自然数集合N等势的集合，称为可数集合(countableset)，该集合的基数记为\(\aleph_0\)阿列夫零
从有限到无限，不仅仅是简单数量上的变化(量变)，而引起了本质的改变(质变)
开区间\((0,1)\)称为不可数集合，凡与开区间\((0,1)\)等势的集合，称为不可数集合，该类集合的基数记为\(\aleph\)阿列夫
推理的前提和结论都是命题。命题是推理的基本单位。
具有确切真值的陈述句称为命题(proposition)。该命题可以取一个“值”，称为真值，真值只有真为假两种，取T、F或1、0
一切没有判断内容的句子，如命令句(或祈使句)、感叹句、疑问句、二义性的陈述句等都不能作为命题
约定：通常用大写的带或不带下标的英文字母表示命题
\(A,B,C,...,P,Q,R,...,A_i,B_i,C_i,...\)
最常见的联结词：“或者”、“并且”、“不”、“如果......则......”、“当且仅当”
非P（P的否定），称为P的否定式，记作\(\negP\)，\(\neg\)为否定联结词。P为真当且仅当\(\negP\)为假
非、不、没有
P并且Q（P和Q），称为P与Q的合取式，记作\(P\wedgeQ\)，\(\wedge\)为合取联结词。\(P\wedgeQ\)为真当且仅当P，Q同为真
“∧”是自然语言中的“并且”、“既...又...”、“但”、“和”、“与”、“不仅...而且...”、“虽然...但是...”、“一面...,一面...”等的逻辑抽象；但不是所有的“和”，“与”都要使用合取联结词表示，要根据句子的语义进行分析。
P或Q，称为P与Q的析取式，记作\(P\veeQ\)，\(\vee\)为析取联结词。$P\veeQ$为真当且仅当P，Q至少一个为真
联结词“∨”是自然语言中的“或”、“或者”等的逻辑抽象。自然语言中的“或”有“可兼或”(或称为同或)、“不可兼或”(即异或)两种。严格来讲，析取联结词实际上代表的是可兼或，异或有时会使用单独的异或联结词“⊕”或“\(\bar{\vee}\)”来表示。
同或情况都可成立，异或只能选其中一种
如果P，则Q，称为P与Q的蕴涵式，记作\(P\rightarrowQ\)，\(\rightarrow\)为蕴涵联结词。\(P\rightarrowQ\)当且仅当P为真且Q为假。一般把蕴涵式\(P\rightarrowQ\)中的P称为该蕴涵式的前件，Q称为蕴涵式的后件
在自然语言中，前件为假，不管结论真假，整个语句的意义，往往无法判断。但对于数理逻辑中的蕴涵联结词来说，当前件P为假时，不管Q的真假如何，则P→Q都为真。此时称为“善意推定”
P当且仅当Q，称为P与Q的等价式，记作\(P\leftrightarrowQ\)，\(\leftrightarrow\)为等价联结词（双条件联结词）。$P\leftrightarrowQ$为真当且仅当P、Q同为真假
“”是自然语言中的“等价”、“充分必要条件”、“当且仅当”等的逻辑抽象。
A当B=BA=B或A=如果B那么A=B是A的充分条件
A仅当B=AB=B或A=如果A那么B=B是A的必要条件
A当且仅当B=AB=(A且B)或(A且B)=如果A那么B而且如果B那么A=B是A的充要条件
当：if
仅当：onlyif
当且仅当：ifandonlyif
AistrueifBistrue.B=》A.必要条件.necessarycondition.栗子：猫会咬我，如果我摸它。我摸它=》咬我。但咬我的时候我不一定摸了它。
AistrueonlyifBistrue.A=》B.充分条件.sufficientcondition.只有B为真的时候A才为真，所以如果已知A为真，那B必然为真。栗子：猫会来蹭我仅当它饿了。猫来蹭我=》他饿了。但他饿了不一定来蹭我，还可能去吃粮。
ifandonlyif就是两个都满足A《=》B.栗子：当且仅当猫拉屎，我去铲屎。我铲可以推出猫拉了。猫拉推出我去铲。
否命题与命题的否定是两个不同的概念。
命题的否定只针对原命题的结论进行否定。而否命题同时否定条件和结论：
原命题：pq
否命题：pq
逆否命题：qp
原命题的否定：pq
若原命题pq为真
先对原命题的结论进行否定，即写出原命题的否定：若p则q
从结论的反面出发，推出矛盾，即命题：若q则p为假（即存在矛盾）（qp）
从而该命题的逆否为真。
再利用原命题和逆否命题的真假性一致，即原命题：pq为真
命题联结词\(\wedge、\vee、\leftrightarrow\)具有对称性，而\(\neg、\rightarrow\)没有
联结词是两个命题真值之间的联结，而不是命题内容之间的连接，因此复合命题的真值只取决于构成他们的各简单命题的真值，而与它们的内容无关，与二者之间是否有关系无关。
优先顺序为：否定、合取、析取、蕴涵、等价
同级的联结词，按出现的先后次序（从左到右）；若运算要求与优先次序不一致可使用括号；同级符号相邻时也可使用括号，括号为最高优先级
在布尔检索中，联接词“∧”（一般用AND表示）用于匹配包含两个检索项的记录，联接词“∨”（一般用OR表示）用于匹配包含两个检索项至少一个的记录，而联接词“”（一般用NOT表示）用于排除某个特定的检索项
计算机中的信息采用二进制的方式来表达。每个二进制位只能是1或0，可对应于某一个布尔变量的真值。当我们需要判断该布尔变量的真值时，就可以利用按位与（bitwiseAND）或按位或（bitwiseOR）以及按位取反（bitwiseNOT）等来操作
一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。
一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)(propositionalvariable)，该命题变量无具体的真值，它的变域是集合{T,F}(或{0,1})。
复合命题是由原子命题与联结词构成的命题。所以，当其中的原子命题是命题变元时，此复合命题也即为命题变元的函数，且该函数的值仍为“真”或“假”值，这样的函数可形象地称为“真值函数”或“命题公式”，此命题公式没有确切的真值。例如：G=P∧Q→R.
如果G是含有n个命题变元P1、P2、P3、···、Pn的公式，可记为：G(P1,P2,P3,···,Pn)或简写为G。
设P1、P2、P3、···、Pn是出现在公式G中的所有命题变元，指定P1、P2、P3、···、Pn一组真值，则这组真值称为G的一个解释，常记为I
如果公式G在解释I下是真的，则称I满足G，此时I是G的成真赋值；如果G在解释I下是假的，则称I弄假于G，此时I是G的成假赋值
由公式G在其所有可能的解释下所取真值构成的表，称为G的真值表(truthtable)。
设G，H是两个命题公式，P1，P2，P3，···，Pn是出现在G，H中所有的命题变元，如果对于P1，P2，P3，···，Pn的\(2^n\)个解释，G与H的真值结果都相同，则称公式G与H是等价的，记作G=H。（或GH）
单箭头是运算符，双箭头是关系（不是运算符）
对于任意两个公式G和H，G=H的充分必要条件是公式GH是永真公式
可判定性:能否给出一个可行方法，完成对任意公式的判定类问题。（类型或等价判定）命题公式命题变元有限，解释数量有限，命题公式是可判定的
不正式的说法：如果A成立的话，那么我们会推出相反的结论，这显然不可能，所以A只能不成立了
首先消去蕴涵、等价联结词
范式：公式的一种规范形式
真值表能够方便的给出命题公式的真值情况，但真值表的规模随命题变元的数量呈指数形式增长，因而我们考虑一种真值表的替代方法，这种方法是基于命题公式的一种标准形式。
在含有n个命题变元P1,P2,P3,···,Pn的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，并且出现的次序与P1,P2,P3,···,Pn一致，则称此短语或子句为关于P1,P2,P3,···,Pn的一个极小项或极大项
一般来说，若有n个命题变元，则应有\(2^n\)个不同的极小项和\(2^n\)个不同的极大项。
所谓推理，是指从一组前提合乎逻辑的推出结论的思维过程。使用命题公式来表达前提和结论
公式H是前提集合Γ={G1,G2,···,Gn}的逻辑结果当且仅当(G1∧G2∧···∧Gn)→H为永真公式。
可以用真值表技术、公式转换法、主析取范式法
三个推理规则加上全部的基本等价公式和基本蕴涵公式，可作为推理与演绎的基础，从而构造一个完整的命题演算推理系统。即所有命题逻辑的定理都可以用这些规则严格地证明出来
从前提集合Γ推出结论H的一个演绎是构造命题公式的一个有限序列：
其中，\(H_i\)或者是\(\Gamma\)中的某个前提，或者是前面的某些\(H_j(j 大写字母I用的是基本蕴涵关系，大写字母E用的是基本等价公式 从结论出发，倒推 反证法是CP规则的一种变形 推理是有效，结论可能是错误的：推理理论只管推理本身，不能管到具体的命题内容