离散数学 命题逻辑15节

数理逻辑部分第1章命题逻辑命题符号化及联结词命题: 判断结果惟一的陈述句命题的真值: 判断的结果真值的取值: 真与假真命题: 真值为真的命题假命题: 真值为假的命题注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

简单命题(原子命题)：简单陈述句构成的命题复合命题：由简单命题与联结词按一定规则复合而成的命题简单命题符号化用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示简单命题用“1”表示真，用“0”表示假例如，令p：是有理数，则p 的真值为 0q：2 + 5 = 7，则q 的真值为 1联结词与复合命题1.否定式与否定联结词“”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假.2.合取式与合取联结词“∧”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真注意：描述合取式的灵活性与多样性分清简单命题与复合命题例将下列命题符号化.(1) 王晓既用功又聪明.(2) 王晓不仅聪明，而且用功.(3) 王晓虽然聪明，但不用功.(4) 张辉与王丽都是三好生.(5) 张辉与王丽是同学.解令p：王晓用功，q：王晓聪明，则(1) p∧q(2) p∧q(3) p∧q.令r : 张辉是三好学生，s :王丽是三好学生(4) r∧s.(5) 令t : 张辉与王丽是同学，t 是简单命题 .说明:(1)~(4)说明描述合取式的灵活性与多样性.(5) 中“与”联结的是两个名词，整个句子是一个简单命题.3.析取式与析取联结词“∨”定义设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q. ∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例将下列命题符号化(1) 2或4是素数.(2) 2或3是素数.(3) 4或6是素数.(4) 小元元只能拿一个苹果或一个梨.(5) 王晓红生于1975年或1976年.解令p:2是素数, q:3是素数, r:4是素数, s:6是素数,则 (1), (2), (3) 均为相容或.分别符号化为: p∨r , p∨q, r∨s,它们的真值分别为 1, 1, 0.而 (4), (5) 为排斥或.令t :小元元拿一个苹果，u:小元元拿一个梨，则 (4) 符号化为 (t∧u) ∨(t∧u).令v :王晓红生于1975年,w:王晓红生于1976年,则 (5) 既可符号化为 (v∧w)∨(v∧w), 又可符号化为v∨w , 为什么?4.蕴涵式与蕴涵联结词“”定义设p,q为二命题，复合命题“如果p,则q” 称作p与q的蕴涵式，记作p q，并称p是蕴涵式的前件，q为蕴涵式的后件. 称作蕴涵联结词，并规定，p q为假当且仅当p 为真q 为假.p q 的逻辑关系：q 为p 的必要条件“如果p，则q ” 的不同表述法很多：若p，就q只要p，就qp 仅当q只有q 才p除非q, 才p 或除非q, 否则非p.当p 为假时，p q 为真常出现的错误：不分充分与必要条件5.等价式与等价联结词“”定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p q. 称作等价联结词.并规定p q为真当且仅当p与q同时为真或同时为假.说明:(1) p q 的逻辑关系:p与q互为充分必要条件(2) p q为真当且仅当p与q同真或同假联结词优先级:( ),, , , ,同级按从左到右的顺序进行以上给出了5个联结词：, , , , ，组成一个联结词集合{, , , , }，联结词的优先顺序为：, , , , ; 如果出现的联结词同级，又无括号时，则按从左到右的顺序运算; 若遇有括号时，应该先进行括号中的运算.注意: 本书中使用的括号全为园括号.命题常项命题变项命题公式及分类命题变项与合式公式命题常项：简单命题命题变项：真值不确定的陈述句定义合式公式 (命题公式, 公式) 递归定义如下：(1) 单个命题常项或变项p,q,r,…,p i ,q i ,r i ,…,0,1是合式公式(2) 若A是合式公式，则 (A)也是合式公式(3) 若A, B是合式公式，则(A B), (A B), (A B), (A B)也是合式公式(4) 只有有限次地应用(1)~(3)形成的符号串才是合式公式说明: 元语言与对象语言, 外层括号可以省去合式公式的层次定义(1) 若公式A是单个的命题变项, 则称A为0层公式.(2) 称A是n+1(n≥0)层公式是指下面情况之一：(a) A=B, B是n层公式；(b) A=B C, 其中B,C分别为i层和j层公式，且n=max(i, j)；(c) A=B C, 其中B,C的层次及n同(b)；(d) A=B C, 其中B,C的层次及n同(b)；(e) A=B C, 其中B,C的层次及n同(b).例如公式p 0层p 1层p q 2层(p q)r 3层((p q) r)(r s) 4层公式的赋值定义给公式A中的命题变项p1, p2, … , p n指定一组真值称为对A的一个赋值或解释成真赋值: 使公式为真的赋值成假赋值: 使公式为假的赋值说明：赋值=12…n之间不加标点符号，i=0或1.A中仅出现p1, p2, …, p n，给A赋值12…n是指p1=1, p2=2, …, p n=nA中仅出现p,q, r, …, 给A赋值123…是指p=1,q=2 , r= 3 …含n个变项的公式有2n个赋值.真值表真值表: 公式A在所有赋值下的取值情况列成的表例给出公式的真值表A= (q p) q p的真值表例 B = (p q) q的真值表例C= (p q) r的真值表命题的分类重言式矛盾式可满足式定义设A为一个命题公式(1) 若A无成假赋值，则称A为重言式(也称永真式)(2) 若A无成真赋值，则称A为矛盾式(也称永假式)(3) 若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式A= (q p)q p，B =(p q)q，C= (p q)r等值演算等值式定义若等价式A B是重言式，则称A与B等值，记作A B，并称A B是等值式说明：定义中，A,B,均为元语言符号, A或B中可能有哑元出现.例如，在 (p q) ((p q) (r r))中，r为左边公式的哑元.用真值表可验证两个公式是否等值请验证：p(q r) (p q) rp(q r) (p q) r基本等值式双重否定律 : A A等幂律：A A A, A A A交换律: A B B A, A B B A结合律: (A B)C A(B C)(A B)C A(B C)分配律: A(B C)(A B)(A C)A(B C) (A B)(A C)德·摩根律: (A B)A B(A B)A B吸收律: A(A B)A, A(A B)A零律: A11, A00同一律: A0A, A1A排中律: A A1矛盾律: A A0等值演算:由已知的等值式推演出新的等值式的过程置换规则：若A B, 则(B)(A)等值演算的基础：(1) 等值关系的性质：自反、对称、传递(2) 基本的等值式(3) 置换规则应用举例——证明两个公式等值例1 证明p(q r) (p q)r证p(q r)p(q r) （蕴涵等值式，置换规则）(p q)r（结合律，置换规则）(p q)r（德摩根律，置换规则）(p q) r（蕴涵等值式，置换规则）说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出应用举例——证明两个公式不等值例2 证明: p(q r) (p q) r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一真值表法（自己证）方法二观察赋值法. 容易看出000, 010等是左边的的成真赋值，是右边的成假赋值.方法三用等值演算先化简两个公式，再观察.应用举例——判断公式类型例3 用等值演算法判断下列公式的类型(1) q(p q)解q(p q)q(p q) （蕴涵等值式）q(p q) （德摩根律）p(q q) （交换律，结合律）p0 （矛盾律）0 （零律）由最后一步可知，该式为矛盾式.(2) (p q)(q p)解 (p q)(q p)(p q)(q p) （蕴涵等值式）(p q)(p q) （交换律）1由最后一步可知，该式为重言式.问：最后一步为什么等值于1？(3) ((p q)(p q))r)解 ((p q)(p q))r)(p(q q))r（分配律）p1r（排中律）p r（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些对偶与范式对偶式与对偶原理定义在仅含有联结词, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)* 还原成A定理设A和A*互为对偶式，p1,p2,…,p n是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则 (1) A(p1,p2,…,p n) A* (p1, p2,…, p n) (2) A(p1, p2,…, p n) A* (p1,p2,…,p n) 定理（对偶原理）设A，B为两个命题公式，若A B，则A* B*.析取范式与合取范式文字:命题变项及其否定的总称简单析取式:有限个文字构成的析取式如p, q, p q, p q r, …简单合取式:有限个文字构成的合取式如p, q, p q, p q r, …析取范式:由有限个简单合取式组成的析取式A 1A2Ar, 其中A1,A2,,A r是简单合取式合取范式:由有限个简单析取式组成的合取式A 1A2Ar, 其中A1,A2,,A r是简单析取式范式:析取范式与合取范式的总称公式A的析取范式: 与A等值的析取范式公式A的合取范式: 与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式p q r, p q r既是析取范式，又是合取范式(为什么?)命题公式的范式定理任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1) 消去A中的, （若存在）(2) 否定联结词的内移或消去(3) 使用分配律对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一求公式的范式举例例求下列公式的析取范式与合取范式(1) A=(p q)r解 (p q)r(p q)r（消去）p q r（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）(2) B=(p q)r解 (p q)r(p q)r（消去第一个）(p q)r（消去第二个）(p q)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续： (p q)r(p r)(q r) （对分配律）这一步得到合取范式（由两个简单析取式构成）极小项与极大项定义在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1i n）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用m i表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用M i 表示第i个极大项，其中i是该极大项成假赋值的十进制表示, m i(M i)称为极小项(极大项)的名称.m与M i的关系: m i M i , M i m ii主析取范式与主合取范式主析取范式: 由极小项构成的析取范式主合取范式: 由极大项构成的合取范式例如，n=3, 命题变项为p, q, r时，(p q r)(p q r) m1m3是主析取范式(p q r)(p q r) M1M5 是主合取范式A的主析取范式: 与A等值的主析取范式A的主合取范式: 与A等值的主合取范式.定理任何命题公式都存在着与之等值的主析取范式和主合取范式, 并且是惟一的.用等值演算法求公式的主范式的步骤：(1) 先求析取范式（合取范式）(2) 将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.(3) 极小项（极大项）用名称m i（M i）表示，并按角标从小到大顺序排序.求公式的主范式例求公式A=(p q)r的主析取范式与主合取范式.(1) 求主析取范式(p q)r(p q)r , （析取范式）①(p q)(p q)(r r)(p q r)(p q r)m 6m7,r(p p)(q q)r(p q r)(p q r)(p q r)(p q r)m 1m3m5m7③②, ③代入①并排序，得(p q)r m1m3m5m6m7（主析取范式）(2) 求A的主合取范式(p q)r(p r)(q r) , （合取范式）①p rp(q q)r(p q r)(p q r)M 0M2,②q r(p p)q r(p q r)(p q r)M 0M4③②, ③代入①并排序，得(p q)r M0M2M4 （主合取范式）主范式的用途——与真值表相同(1) 求公式的成真赋值和成假赋值例如 (p q)r m1m3m5m6m7，其成真赋值为001, 011, 101, 110, 111，其余的赋值 000, 010, 100为成假赋值.类似地，由主合取范式也可立即求出成假赋值和成真赋值.(2) 判断公式的类型设A含n个命题变项，则A为重言式A的主析取范式含2n个极小项A的主合取范式为1.A为矛盾式A的主析取范式为0A的主合取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项例某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件：(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国？解此类问题的步骤为：①将简单命题符号化②写出各复合命题③写出由②中复合命题组成的合取式④求③中所得公式的主析取范式解①设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.② (1) (p q)(2) (s u)(3) ((q r)(q r))(4) ((r s)(r s))(5) (u(p q))③ (1) ~ (5)构成的合取式为A=(p q)(s u)((q r)(q r))((r s)(r s))(u(p q))④ A (p q r s u)(p q r s u)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:A (p q)((q r)(q r))(s u)(u(p q)) ((r s)(r s)) （交换律) B1= (p q)((q r)(q r))((p q r)(p q r)(q r)) （分配律）B2= (s u)(u(p q))((s u)(p q s)(p q u)) （分配律）B 1B2(p q r s u)(p q r s u) (q r s u)(p q r s)(p q r u)再令B3 = ((r s)(r s))得A B1B2B3(p q r s u)(p q r s u)注意：在以上演算中多次用矛盾律要求：自己演算一遍推理理论推理的形式结构推理的形式结构—问题的引入推理举例:(1) 正项级数收敛当且仅当部分和有上界.(2) 若推理: 从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明: 描述推理正确的过程.判断推理是否正确的方法•真值表法•等值演算法判断推理是否正确•主析取范式法•构造证明法证明推理正确说明：当命题变项比较少时，用前3个方法比较方便, 此时采用形式结构“” . 而在构造证明时，采用“前提: , 结论: B”.推理定律与推理规则推理定律——重言蕴涵式构造证明——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以，明天不是星期一和星期三.解设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课推理的形式结构为例构造下面推理的证明:2是素数或合数. 若2是素数，则是无理数.若是无理数，则4不是素数. 所以，如果4是素数，则2是合数.用附加前提证明法构造证明解设p：2是素数，q：2是合数，r：是无理数，s：4是素数推理的形式结构前提：p∨q, p r, r s结论：s q证明① s附加前提引入②p r前提引入③r s前提引入④p s②③假言三段论⑤p①④拒取式⑥p∨q前提引入⑦q⑤⑥析取三段论请用直接证明法证明之。

离散数学第一章命题逻辑知识点总结-CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN数理逻辑部分第1章命题逻辑1.1 命题符号化及联结词命题: 判断结果惟一的陈述句命题的真值: 判断的结果真值的取值: 真与假真命题: 真值为真的命题假命题: 真值为假的命题注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

简单命题(原子命题)：简单陈述句构成的命题复合命题：由简单命题与联结词按一定规则复合而成的命题简单命题符号化用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示简单命题用“1”表示真，用“0”表示假例如，令p：是有理数，则p 的真值为 0q：2 + 5 = 7，则q 的真值为 1联结词与复合命题1.否定式与否定联结词“⌝”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作⌝p. 符号⌝称作否定联结词，并规定⌝p为真当且仅当p为假.2.合取式与合取联结词“∧”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p与q同时为真注意：描述合取式的灵活性与多样性分清简单命题与复合命题例将下列命题符号化.(1) 王晓既用功又聪明.(2) 王晓不仅聪明，而且用功.(3) 王晓虽然聪明，但不用功.(4) 张辉与王丽都是三好生.(5) 张辉与王丽是同学.解令p：王晓用功，q：王晓聪明，则(1) p∧q(2) p∧q(3) p∧⌝q.令r : 张辉是三好学生，s :王丽是三好学生(4) r∧s.(5) 令t : 张辉与王丽是同学，t 是简单命题 .说明:(1)~(4)说明描述合取式的灵活性与多样性.(5) 中“与”联结的是两个名词，整个句子是一个简单命题.3.析取式与析取联结词“∨”定义设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q. ∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假. 例将下列命题符号化(1) 2或4是素数.(2) 2或3是素数.(3) 4或6是素数.(4) 小元元只能拿一个苹果或一个梨.(5) 王晓红生于1975年或1976年.解令p:2是素数, q:3是素数, r:4是素数, s:6是素数,则 (1), (2), (3) 均为相容或.分别符号化为: p∨r , p∨q, r∨s,它们的真值分别为 1, 1, 0.而 (4), (5) 为排斥或.令t :小元元拿一个苹果，u:小元元拿一个梨，则 (4) 符号化为 (t∧⌝u) ∨(⌝t∧u).令v :王晓红生于1975年,w:王晓红生于1976年,则 (5) 既可符号化为 (v∧⌝w)∨(⌝v∧w), 又可符号化为v∨w , 为什么4.蕴涵式与蕴涵联结词“→”定义设p,q为二命题，复合命题“如果p,则q” 称作p与q的蕴涵式，记作p→q，并称p是蕴涵式的前件，q为蕴涵式的后件. →称作蕴涵联结词，并规定，p→q为假当且仅当p 为真q 为假.p→q 的逻辑关系：q 为p 的必要条件“如果p，则q ” 的不同表述法很多：若p，就q只要p，就qp 仅当q只有q 才p除非q, 才p 或除非q, 否则非p.当p 为假时，p→q 为真常出现的错误：不分充分与必要条件5.等价式与等价联结词“↔”定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p↔q. ↔称作等价联结词.并规定p↔q为真当且仅当p与q同时为真或同时为假.说明:(1) p↔q 的逻辑关系:p与q互为充分必要条件(2) p↔q为真当且仅当p与q同真或同假联结词优先级:( ),⌝, ∧, ∨, →, ↔同级按从左到右的顺序进行以上给出了5个联结词：⌝, ∧, ∨, →, ↔，组成一个联结词集合{⌝, ∧, ∨, →, ↔}，联结词的优先顺序为：⌝, ∧, ∨, →, ↔; 如果出现的联结词同级，又无括号时，则按从左到右的顺序运算; 若遇有括号时，应该先进行括号中的运算.注意: 本书中使用的括号全为园括号.⏹命题常项⏹命题变项1.2 命题公式及分类▪命题变项与合式公式▪命题常项：简单命题▪命题变项：真值不确定的陈述句▪定义合式公式 (命题公式, 公式) 递归定义如下：▪(1) 单个命题常项或变项p,q,r,…,p i ,q i ,r i ,…,0,1▪是合式公式▪(2) 若A是合式公式，则 (⌝A)也是合式公式▪(3) 若A, B是合式公式，则(A∧B), (A∨B), (A→B), (A↔B)也是合式公式▪(4) 只有有限次地应用(1)~(3)形成的符号串才是合式公式▪说明: 元语言与对象语言, 外层括号可以省去合式公式的层次定义(1) 若公式A是单个的命题变项, 则称A为0层公式.(2) 称A是n+1(n≥0)层公式是指下面情况之一：(a) A=⌝B, B是n层公式；(b) A=B∧C, 其中B,C分别为i层和j层公式，且n=max(i, j)；(c) A=B∨C, 其中B,C的层次及n同(b)；(d) A=B→C, 其中B,C的层次及n同(b)；(e) A=B↔C, 其中B,C的层次及n同(b).例如公式p 0层⌝p 1层⌝p→q 2层⌝(p→q)↔r 3层((⌝p∧q) →r)↔(⌝r∨s) 4层▪公式的赋值▪定义给公式A中的命题变项p1, p2, … , p n指定▪一组真值称为对A的一个赋值或解释▪成真赋值: 使公式为真的赋值▪成假赋值: 使公式为假的赋值▪说明：▪赋值α=α1α2…αn之间不加标点符号，αi=0或1.▪A中仅出现p1, p2, …, p n，给A赋值α1α2…αn是▪指p1=α1, p2=α2, …, p n=αn▪A中仅出现p,q, r, …, 给A赋值α1α2α3…是指▪p=α1,q=α2 , r=α3 …▪含n个变项的公式有2n个赋值.▪真值表真值表: 公式A在所有赋值下的取值情况列成的表例给出公式的真值表A= (q→p) ∧q→p的真值表例 B = ⌝ (⌝p∨q) ∧q的真值表例C= (p∨q) →⌝r的真值表命题的分类重言式矛盾式可满足式定义设A为一个命题公式(1) 若A无成假赋值，则称A为重言式(也称永真式)(2) 若A无成真赋值，则称A为矛盾式(也称永假式)(3) 若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式A= (q→p)∧q→p，B =⌝(⌝p∨q)∧q，C= (p∨q)→⌝r1.3 等值演算⏹等值式定义若等价式A↔B是重言式，则称A与B等值，记作A⇔B，并称A⇔B是等值式说明：定义中，A,B,⇔均为元语言符号, A或B中可能有哑元出现.例如，在 (p→q) ⇔ ((⌝p∨q)∨ (⌝r∧r))中，r为左边公式的哑元.用真值表可验证两个公式是否等值请验证：p→(q→r) ⇔ (p∧q) →rp→(q→r) (p→q) →r⏹基本等值式双重否定律 : ⌝⌝A⇔A等幂律：A∨A⇔A, A∧A⇔A交换律: A∨B⇔B∨A, A∧B⇔B∧A结合律: (A∨B)∨C⇔A∨(B∨C)(A∧B)∧C⇔A∧(B∧C)分配律: A∨(B∧C)⇔(A∨B)∧(A∨C)A∧(B∨C)⇔ (A∧B)∨(A∧C) 德·摩根律: ⌝(A∨B)⇔⌝A∧⌝B⌝(A∧B)⇔⌝A∨⌝B吸收律: A∨(A∧B)⇔A, A∧(A∨B)⇔A零律: A∨1⇔1, A∧0⇔0同一律: A∨0⇔A, A∧1⇔A排中律: A∨⌝A⇔1矛盾律: A∧⌝A⇔0等值演算:由已知的等值式推演出新的等值式的过程置换规则：若A⇔B, 则Φ(B)⇔Φ(A)等值演算的基础：(1) 等值关系的性质：自反、对称、传递(2) 基本的等值式(3) 置换规则应用举例——证明两个公式等值例1 证明p→(q→r) ⇔ (p∧q)→r证p→(q→r)⇔⌝p∨(⌝q∨r) （蕴涵等值式，置换规则）⇔(⌝p∨⌝q)∨r（结合律，置换规则）⇔⌝(p∧q)∨r（德⋅摩根律，置换规则）⇔(p∧q) →r（蕴涵等值式，置换规则）说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出应用举例——证明两个公式不等值例2 证明: p→(q→r) (p→q) →r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一真值表法（自己证）方法二观察赋值法. 容易看出000, 010等是左边的的成真赋值，是右边的成假赋值.方法三用等值演算先化简两个公式，再观察.应用举例——判断公式类型例3 用等值演算法判断下列公式的类型(1) q∧⌝(p→q)解q∧⌝(p→q)⇔q∧⌝(⌝p∨q) （蕴涵等值式）⇔q∧(p∧⌝q) （德⋅摩根律）⇔p∧(q∧⌝q) （交换律，结合律）⇔p∧0 （矛盾律）⇔ 0 （零律）由最后一步可知，该式为矛盾式.(2) (p→q)↔(⌝q→⌝p)解 (p→q)↔(⌝q→⌝p)⇔ (⌝p∨q)↔(q∨⌝p) （蕴涵等值式）⇔ (⌝p∨q)↔(⌝p∨q) （交换律）⇔ 1由最后一步可知，该式为重言式.问：最后一步为什么等值于1(3) ((p∧q)∨(p∧⌝q))∧r)解 ((p∧q)∨(p∧⌝q))∧r)⇔ (p∧(q∨⌝q))∧r（分配律）⇔p∧1∧r（排中律）⇔p∧r（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A⇔0A为重言式当且仅当A⇔1说明：演算步骤不惟一,应尽量使演算短些1.5 对偶与范式对偶式与对偶原理定义在仅含有联结词⌝, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)* 还原成A定理设A和A*互为对偶式，p1,p2,…,p n是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则 (1) ⌝A(p1,p2,…,p n) ⇔A* (⌝p1, ⌝p2,…, ⌝p n)(2) A(⌝p1, ⌝p2,…, ⌝p n) ⇔⌝A* (p1,p2,…,p n)定理（对偶原理）设A，B为两个命题公式，若A ⇔ B，则A*⇔ B*.析取范式与合取范式文字:命题变项及其否定的总称简单析取式:有限个文字构成的析取式如p, ⌝q, p∨⌝q, p∨q∨r, …简单合取式:有限个文字构成的合取式如p, ⌝q, p∧⌝q, p∧q∧r, …析取范式:由有限个简单合取式组成的析取式A∨A2∨⋯∨A r, 其中A1,A2,⋯,A r是简单合取式1合取范式:由有限个简单析取式组成的合取式A∧A2∧⋯∧A r , 其中A1,A2,⋯,A r是简单析取式1范式:析取范式与合取范式的总称公式A的析取范式: 与A等值的析取范式公式A的合取范式: 与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式p∧⌝q∧r, ⌝p∨q∨⌝r既是析取范式，又是合取范式(为什么)命题公式的范式定理任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1) 消去A中的→, ↔（若存在）(2) 否定联结词⌝的内移或消去(3) 使用分配律∧对∨分配（析取范式）∨对∧分配（合取范式）公式的范式存在，但不惟一求公式的范式举例例求下列公式的析取范式与合取范式(1) A=(p→⌝q)∨⌝r解 (p→⌝q)∨⌝r⇔ (⌝p∨⌝q)∨⌝r（消去→）⇔⌝p∨⌝q∨⌝r（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）(2) B=(p→⌝q)→r解 (p→⌝q)→r⇔ (⌝p∨⌝q)→r（消去第一个→）⇔⌝(⌝p∨⌝q)∨r（消去第二个→）⇔ (p∧q)∨r（否定号内移——德⋅摩根律）这一步已为析取范式（两个简单合取式构成）继续： (p∧q)∨r⇔ (p∨r)∧(q∨r) （∨对∧分配律）这一步得到合取范式（由两个简单析取式构成）极小项与极大项定义在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1≤i≤n）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用m i表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用M表示第i个极大项，其中i是该极大项成假赋值的十进制表示, m i(M i)称i为极小项(极大项)的名称.m与M i的关系: ⌝m i ⇔M i , ⌝M i ⇔m ii主析取范式与主合取范式主析取范式: 由极小项构成的析取范式主合取范式: 由极大项构成的合取范式例如，n=3, 命题变项为p, q, r时，(⌝p∧⌝q∧r)∨(⌝p∧q∧r) ⇔m1∨m3是主析取范式(p∨q∨⌝r)∧(⌝p∨q∨⌝r) ⇔M1∧M5 是主合取范式A的主析取范式: 与A等值的主析取范式A的主合取范式: 与A等值的主合取范式.定理任何命题公式都存在着与之等值的主析取范式和主合取范式, 并且是惟一的.用等值演算法求公式的主范式的步骤：(1) 先求析取范式（合取范式）(2) 将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.(3) 极小项（极大项）用名称m i（M i）表示，并按角标从小到大顺序排序.求公式的主范式例求公式A=(p→⌝q)→r的主析取范式与主合取范式.(1) 求主析取范式(p→⌝q)→r⇔ (p∧q)∨r , （析取范式）①(p∧q)⇔ (p∧q)∧(⌝r∨r)⇔ (p∧q∧⌝r)∨(p∧q∧r)⇔m6∨m7 ,r⇔(⌝p∨p)∧(⌝q∨q)∧r⇔(⌝p∧⌝q∧r)∨(⌝p∧q∧r)∨(p∧⌝q∧r)∨(p∧q∧r)⇔m1∨m3∨m5∨m7 ③②, ③代入①并排序，得(p→⌝q)→r⇔m1∨m3∨m5∨m6∨m7（主析取范式）(2) 求A的主合取范式(p→⌝q)→r⇔ (p∨r)∧(q∨r) , （合取范式）①p∨r⇔p∨(q∧⌝q)∨r⇔ (p∨q∨r)∧(p∨⌝q∨r)⇔M0∧M2,②q∨r⇔ (p∧⌝p)∨q∨r⇔ (p∨q∨r)∧(⌝p∨q∨r)⇔M0∧M4 ③②, ③代入①并排序，得(p→⌝q)→r⇔M0∧M2∧M4 （主合取范式）主范式的用途——与真值表相同(1) 求公式的成真赋值和成假赋值例如 (p→⌝q)→r⇔m1∨m3∨m5∨m6∨m7，其成真赋值为001, 011, 101, 110, 111，其余的赋值 000, 010, 100为成假赋值.类似地，由主合取范式也可立即求出成假赋值和成真赋值.(2) 判断公式的类型设A含n个命题变项，则A为重言式⇔A的主析取范式含2n个极小项⇔A的主合取范式为1.A为矛盾式⇔A的主析取范式为0⇔A的主合取范式含2n个极大项A为非重言式的可满足式⇔A的主析取范式中至少含一个且不含全部极小项⇔A的主合取范式中至少含一个且不含全部极大项例某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件：(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国？解此类问题的步骤为：①将简单命题符号化②写出各复合命题③写出由②中复合命题组成的合取式④求③中所得公式的主析取范式解①设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.② (1) (p→q)(2) (s∨u)(3) ((q∧⌝r)∨(⌝q∧r))(4) ((r∧s)∨(⌝r∧⌝s))(5) (u→(p∧q))③ (1) ~ (5)构成的合取式为A=(p→q)∧(s∨u)∧((q∧⌝r)∨(⌝q∧r))∧((r∧s)∨(⌝r∧⌝s))∧(u→(p∧q))④ A ⇔ (⌝p∧⌝q∧r∧s∧⌝u)∨(p∧q∧⌝r∧⌝s∧u)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:A⇔ (⌝p∨q)∧((q∧⌝r)∨(⌝q∧r))∧(s∨u)∧(⌝u∨(p∧q))∧((r∧s)∨(⌝r∧⌝s)) （交换律) B= (⌝p∨q)∧((q∧⌝r)∨(⌝q∧r))1⇔ ((⌝p∧q∧⌝r)∨(⌝p∧⌝q∧r)∨(q∧⌝r)) （分配律）B= (s∨u)∧(⌝u∨(p∧q))2⇔ ((s∧⌝u)∨(p∧q∧s)∨(p∧q∧u)) （分配律）B∧B2 ⇔ (⌝p∧q∧⌝r∧s∧⌝u)∨(⌝p∧⌝q∧r∧s∧⌝u)1∨(q∧⌝r∧s∧⌝u)∨(p∧q∧⌝r∧s)∨(p∧q∧⌝r∧u) 再令B3 = ((r∧s)∨(⌝r∧⌝s))得A⇔B1∧B2∧B3⇔ (⌝p∧⌝q∧r∧s∧⌝u)∨(p∧q∧⌝r∧⌝s∧u) 注意：在以上演算中多次用矛盾律要求：自己演算一遍1.6 推理理论推理的形式结构推理的形式结构—问题的引入推理举例:(1) 正项级数收敛当且仅当部分和有上界.(2) 若推理: 从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明: 描述推理正确的过程.判断推理是否正确的方法•真值表法•等值演算法判断推理是否正确•主析取范式法•构造证明法证明推理正确说明：当命题变项比较少时，用前3个方法比较方便, 此时采用形式结构“” . 而在构造证明时，采用“前提: , 结论: B”.推理定律与推理规则推理定律——重言蕴涵式构造证明——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以，明天不是星期一和星期三.解设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课推理的形式结构为例构造下面推理的证明:2是素数或合数. 若2是素数，则是无理数.若是无理数，则4不是素数. 所以，如果4是素数，则2是合数.用附加前提证明法构造证明解设p：2是素数，q：2是合数，r：是无理数，s：4是素数推理的形式结构前提：p∨q, p→r, r→⌝s结论：s→q证明① s附加前提引入②p→r前提引入③r→⌝s前提引入④p→⌝s②③假言三段论⑤⌝p①④拒取式⑥p∨q前提引入⑦q⑤⑥析取三段论请用直接证明法证明之。

第二章 命题逻辑习题．解 ⑴不是陈述句，所以不是命题。

⑵x 取值不确定，所以不是命题。

⑶问句，不是陈述句，所以不是命题。

⑷惊叹句，不是陈述句，所以不是命题。

⑸是命题，真值由具体情况确定。

⑹是命题，真值由具体情况确定。

⑺是真命题。

⑻是悖论，所以不是命题。

⑼是假命题。

2．解 ⑴是复合命题。

设p ：他们明天去百货公司；q ：他们后天去百货公司。

命题符号化为q p ∨。

⑵是疑问句，所以不是命题。

⑶是悖论，所以不是命题。

⑷是原子命题。

⑸是复合命题。

设p ：王海在学习；q ：李春在学习。

命题符号化为pq 。

⑹是复合命题。

设p ：你努力学习；q ：你一定能取得优异成绩。

p q 。

⑺不是命题。

⑻不是命题⑼。

是复合命题。

设p ：王海是女孩子。

命题符号化为：p 。

3．解 ⑴如果李春迟到了，那么他错过考试。

⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。

⑶李春错过考试当且仅当他迟到了。

⑷如果李春迟到了并且错过了考试，那么他没有通过考试。

4．解 ⑴p (q r )。

⑵p q 。

⑶q p 。

⑷q p 。

习题1．解 ⑴是1层公式。

⑵不是公式。

⑶一层： pq ，p二层：p q所以，)()(q p q p ↔⌝→∨是3层公式。

⑷不是公式。

⑸(pq )(q ( q r ))是5层公式，这是因为一层：p q ，q ，r二层：q r 三层：q ( qr )四层：(q ( q r ))2．解 ⑴A =(p q )q 是2层公式。

真值表如表2-1所示：pqq p ∨A0 0 0 0 0 1 1 1 1 0 1 0 1111⑵p q p q A →→∧=)(是3层公式。

真值表如表2-2所示：pqq p →)(q p q →∧A0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 11111⑶)()(q p r q p A ∨→∧∧=是3层公式。

真值表如表2-3所示：pqrq p ∧r q p ∧∧q p ∨A0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 1 0 1 1 1 111111⑷)()()(r q r p q p A ∨∧∨⌝∧∨=是4层公式。

离散数学笔记总结一、命题逻辑。

1. 基本概念。

- 命题：能够判断真假的陈述句。

例如“2 + 3 = 5”是真命题，“1 > 2”是假命题。

- 命题变元：用字母表示命题，如p,q,r等。

2. 逻辑联结词。

- 否定¬：¬ p表示对命题p的否定，若p为真，则¬ p为假，反之亦然。

- 合取wedge：pwedge q表示p并且q，只有当p和q都为真时，pwedge q才为真。

- 析取vee：pvee q表示p或者q，当p和q至少有一个为真时，pvee q为真。

- 蕴含to：pto q表示若p则q，只有当p为真且q为假时，pto q为假。

- 等价↔：p↔ q表示p当且仅当q，当p和q同真同假时，p↔ q为真。

3. 命题公式。

- 定义：由命题变元、逻辑联结词和括号按照一定规则组成的符号串。

- 赋值：给命题变元赋予真假值，从而确定命题公式的真值。

- 分类：重言式（永真式）、矛盾式（永假式）、可满足式。

4. 逻辑等价与范式。

- 逻辑等价：若A↔ B是重言式，则称A与B逻辑等价，记作A≡ B。

例如¬(pwedge q)≡¬ pvee¬ q（德摩根律）。

- 范式：- 析取范式：由有限个简单合取式的析取组成的命题公式。

- 合取范式：由有限个简单析取式的合取组成的命题公式。

- 主析取范式：每个简单合取式都是极小项（包含所有命题变元的合取式，每个变元只出现一次）的析取范式。

- 主合取范式：每个简单析取式都是极大项（包含所有命题变元的析取式，每个变元只出现一次）的合取范式。

二、谓词逻辑。

1. 基本概念。

- 个体：可以独立存在的事物，如人、数等。

- 谓词：用来刻画个体性质或个体之间关系的词。

例如P(x)表示x具有性质P，R(x,y)表示x和y具有关系R。

- 量词：- 全称量词∀：∀ xP(x)表示对于所有的x，P(x)成立。

- 存在量词∃：∃ xP(x)表示存在某个x，使得P(x)成立。

离散数学（课件上习题）第一章例1-1.1 判定下面这些句子哪些是命题。

⑴2是个素数。

⑵雪是黑色的。

⑶2013年人类将到达火星。

⑷如果a>b且b>c，则a>c 。

（其中a,b,c都是确定的实数）⑸x+y<5⑹请打开书！⑺您去吗？⑴⑵⑶⑷是命题例1-2.1 P：2是素数。

⌝P：2不是素数。

例1-2.2 P：小王能唱歌。

Q：小王能跳舞。

P∧Q：小王能歌善舞。

例1-2.3. 灯泡或者线路有故障。

（析取“∨”）例1-2.4. 第一节课上数学或者上英语。

（异或、排斥或。

即“⊽”）注意：P ⊽Q 与(P∧⌝Q)∨(Q∧⌝P ) 是一样的。

归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：（1）否定“⌝”(2) 合取“∧”(3) 析取“∨”(4) 异或“⊽”(5) 蕴涵“→”(6) 等价“↔”例1-2.5：P表示：缺少水分。

Q表示：植物会死亡。

P→Q：如果缺少水分，植物就会死亡。

P→Q：也称之为蕴涵式，读成“P蕴涵Q”，“如果P则Q”。

也说成P是P→Q 的前件，Q是P→Q的后件。

还可以说P是Q的充分条件，Q是P的必要条件。

以下是关于蕴含式的一个例子P：天气好。

Q：我去公园。

1.如果天气好，我就去公园。

2.只要天气好，我就去公园。

3.天气好，我就去公园。

4.仅当天气好，我才去公园。

5.只有天气好，我才去公园。

6.我去公园，仅当天气好。

命题1.、2.、3.写成：P→Q命题4.、5.、6.写成：Q→P例1-2.6：P：△ABC 是等边三角形。

Q ：△ABC是等角三角形。

P↔Q ：△ABC 是等边三角形当且仅当它是等角三角形。

课后练习：填空已知P∧Q为T，则P为( )，Q为( )。

已知P∨Q为F，则P为( )，Q为( )。

已知P为F，则P∧Q为( )。

已知P为T，则P∨Q为( )。

已知P∨Q为T，且P为F ，则Q为( )。

已知P→Q为F，则P为( )，Q为( )。

已知P为F，则P→Q为( )。

离散数学知识点总结（1）-命题逻辑⼀、命题命题：陈述句，有唯⼀真值/⾮真既假（不⼀定知道）简单命题/命题常元：真值确定。

命题变元p：常⽤来表⽰命题。

只有明确表⽰某个命题时才有具体的含意和确定的真值。

命题联结词/命题运算符：否定联结词┐、合取联结词∧、析取联结词∨、蕴含联结词→、与⾮联结词、或⾮联结词p→q：当且仅当p真q假时，p→q为假（因此它和┐p∨q等值）。

即p为假时，p→q必定为真⟷：当且仅当、充要条件、反之亦然⼆、命题公式命题公式/命题形式/合式公式/公式：（1）可满⾜式：⾮重⾔的可满⾜式重⾔式/永真式（2）⽭盾式/永假式（不存在成真指派）命题公式不是命题，只有当公式中的每⼀个命题变项都被赋以确定的真值时，公式的真值才被确定，从⽽成为⼀个命题。

三、命题逻辑的等值演算A⟺B：A和B有等值关系。

对任意真值指派，A与B取值相同。

A⟷B为永真式。

等值关系⼀般通过真值表法或者等值演算法得到。

⽽不等值，只能通过真值表法，找到某个真值指派使得⼀个为真⼀个为假德摩根律：┐(A∨B)⟺┐A∧┐B、┐(A∧B)⟺┐A∨┐B蕴含等值式：A→B⟺┐A∨B吸收律：A∨(A∧B)⟺A、A∧(A∨B)⟺A归谬式：(A→B)∧(A→┐B)⟺┐A例题：p→(q→r)⟺┐p∨(┐q∨r)⟺(┐p∨┐q)∨r⟺┐(p∧q)∨r⟺(p∧q)→r四、范式由有限个⽂字的析取所组成的公式称为析取式；由有限个⽂字的合取所组成的公式称为合取式形如A1∨A2∨…∨A n的公式称为析取范式DNF（其中A i为合取式）；形如A1∧A2∧…∧A n的公式称为合取范式CNF（其中A i为析取式）任⼀命题公式都存在着与之等值的析取范式和合取范式，但析取范式和合取范式可能不是惟⼀的。

极⼩项q1∧q2∧…∧q n：⼀共2n种解释，每个极⼩项只在⼀个解释下为真。

每个极⼩项对应⼀个⼆进制数，该⼆进制数正是该极⼩项真值为真的指派，即m0可表⽰┐q1∧┐q2∧…∧┐q n极⼤项q1∨q2∨…∨q n：⼀共2n种解释，每个极⼤项只在⼀个解释下为假。

离散数学命题逻辑知识点总结《离散数学命题逻辑知识点总结》命题逻辑是数理逻辑的一个分支，研究的是命题之间的关系以及它们的推理规则。

以下是离散数学命题逻辑的一些重要知识点的总结：1. 命题：命题是一个陈述句，它要么是真的，要么是假的，但不能同时既是真的又是假的。

2. 逻辑运算符：逻辑运算符用于组合和操作命题。

常见的逻辑运算符有：“与（∧）”、“或（∨）”、“非（¬）”、“蕴含（→）”和“等价（↔）”。

3. 真值表：真值表用于表示逻辑运算符的结果。

通过列出所有可能的命题组合，并在每个组合下计算逻辑运算符的结果，可以得到真值表。

4. 合取范式和析取范式：合取范式是通过将命题用“与”运算符连接起来得到的，析取范式是通过将命题用“或”运算符连接起来得到的。

将命题转化为它们的合取范式或析取范式，能方便地进行逻辑运算。

5. 重言式和矛盾式：重言式是指对于所有可能的命题组合，逻辑表达式都为真的命题。

矛盾式是指对于所有可能的命题组合，逻辑表达式都为假的命题。

重言式和矛盾式具有重要的推理性质。

6. 推理规则：推理规则是用来推导逻辑表达式的一些基本规则。

常见的推理规则有“假言推理法”、“逆命题推理法”、“逆否命题推理法”和“拒取式推理法”。

7. 等价关系和等价演算：等价关系是指两个逻辑表达式具有相同的真值。

等价演算是一种通过运用逻辑等价关系来简化逻辑表达式的方法。

通过应用等价演算，可以将复杂的逻辑表达式简化为更简单的形式。

8. 形式化证明：在命题逻辑中，形式化证明是用推理规则和等价演算来推导出逻辑表达式的一系列步骤。

形式化证明的目的是证明一个逻辑表达式的正确性。

离散数学命题逻辑是理解和应用数理逻辑的基础。

通过掌握上述知识点，我们能够准确地分析和推理命题逻辑问题，并在解决问题时运用逻辑规律和推理方法。

对于计算机科学、人工智能和数学等领域的研究和应用，命题逻辑具有重要的理论和实际意义。

离散数学命题逻辑公式1. 命题逻辑的基本概念命题逻辑是离散数学的一个重要分支，主要研究命题之间的关系以及命题的推理规则。

命题逻辑中的基本概念包括：命题：命题是描述客观事实真假的句子。

命题的真假值只有两个：真和假。

命题联结词：命题联结词用于将两个或多个命题连接起来，形成新的命题。

常见的命题联结词有：否定（¬）、合取（∧）、析取（∨）、蕴含（→）和等价（↔）。

命题公式：命题公式是由命题和命题联结词组成的表达式。

命题公式的真假值取决于其组成命题的真假值。

2. 命题逻辑的推理规则命题逻辑的推理规则是用于从给定的命题公式推导出新命题公式的规则。

常见的推理规则有：三段论：三段论是一种由两个前提和一个结论组成的推理形式。

如果两个前提都是真的，那么结论也一定是真的。

例如：所有哺乳动物都是恒温动物。

猫是哺乳动物。

所以，猫是恒温动物。

假言推理：假言推理是一种由一个条件句和一个结论组成的推理形式。

如果条件句是真的，那么结论也一定是真的。

例如：如果今天下雨，那么我就不出门。

今天下雨。

所以，我不出门。

选言推理：选言推理是一种由两个或多个分支组成的推理形式。

如果其中一个分支是真的，那么结论也一定是真的。

例如：要么今天下雨，要么明天下雨。

今天下雨。

所以，明天不会下雨。

3. 命题逻辑的应用命题逻辑在计算机科学、人工智能、哲学等领域有着广泛的应用。

在计算机科学中，命题逻辑用于设计和分析逻辑电路、编译器和操作系统等。

在人工智能中，命题逻辑用于知识表示和推理。

在哲学中，命题逻辑用于研究逻辑的本质和推理的有效性。

4. 结语命题逻辑是离散数学的一个重要分支，主要研究命题之间的关系以及命题的推理规则。

命题逻辑的应用非常广泛，包括计算机科学、人工智能、哲学等领域。

数理逻辑命题逻辑基本概念等值演算析取范式合取范式范式说明单个命题变元既是简单析取式又是简单合取式命题变元的析取式和合取式不唯一主析取范式由有限给简单析取式的合取构成的命题公式主合取范式简单合取式简单析取式由有限个的文字构成的析取式由有限个文字构成的合取式由有限个简单合取式的析取构成的命题公式（只能是单层括号且括号内部都是合取）命题变项及其否定都称作文字极小项n个命题变项的简单合取式按照下标从小到大或字典顺序排列，且每个命题变项及它的否定有且仅出现一次的简单析取式极大项所有简单合取式都是极小项的析取范式可以进行补项，使得每一项均含命题变项（析取0或合取1）真值可以变化的命题（命题变项不是命题）命题变项真值确定的简单命题命题常项将命题变项用联结词和圆括号按照一定逻辑关系联结起来的符号串合式公式在它的各种赋值下取值均为真重言式/永真式在它的各种赋值下取值均为假矛盾式/永假式若其不是矛盾式，则称其为重言式可满足式命题公式分类命题公式及其赋值否定联结词子主题1合取（交集）析取（并集）蕴涵（若p则q）等价联结词基本命题联结词非真即假的陈述句，有唯一真值命题命题陈述句所表达的判断结果（真值不确定，不代表真值不唯一）真值不能再被分解成更简单的命题简单命题/原子命题既不能为真也不能为假的陈述句悖论命题公式在所有赋值下取值情况列成的表指定的一组值使公式A全为1成真赋值指定的一组值使公式A全为0成假赋值真值表等值式命题相关基本概念命题与联结词A A⇔¬¬双重否定定律A A A⟺∨A A A⟺∧幂等律交换律结合律基础等值模式(A B)A B¬∨⟺¬∧¬徳摩根律(否定内移)A (A B)A∨∧⟺A (A B)A∧∨⟺吸收律A 11∨⟺A 00∧⟺零律A B A B→⟺¬∨蕴涵等值式A B （A B）（B A）↔⟺→∧→等价等值式A B B A →⟺¬→¬假言易位(A B)(A B)A →∧→¬⟺¬归谬论A B A B↔⟺¬↔¬等价否定等值式重点等值模式A 0A∨⟺A 1A ∧⟺同一律A A 0∧¬⟺矛盾律A A 1∨¬⟺排中律逻辑三大定律。