大一各科课件-离散数理逻辑slide3-proplogic

马帅 提基本概念：集合、函数、归纳、数理1.1命题和联结1.21.3等值演1.4对偶定1.51.6范1.7逻辑推 集 元素与a不是集合S的元素，记为a集合的特点：唯一性、无序性、确集合的表示空集x 集合的外概括原则：每一性质(或谓词)产生一个集集合集合所包含的元素全体集合示例-非负偶数集外延—024 集合的关为B的子集，记为AB等价关系如果集合A和集合B包含相同元素，则称AB相等，记为 集合的操{x|xA或者x{x|xA并且x集合的差：ABA{x|xA并且x集合的笛卡尔积A{(x,y)|xA,y

元素个数67函7(x…xn为A上的n元运算。f：A×A×…×A序列全体AnAn=xx2,…,n|A={0,A3={0,1}3={(0,0,0),(0,0,1),(0,1,0),(0,1,(1,0,0),(1,0,1),(1,1,0),(1,1,归纳采用归纳法定义自然数集合n'是n的唯一后继（函数–n'=n+N是满足以下条件的N0N，且0是任何数n的后–对于任何n，如果nN，则n'N 归纳采用设R是一个性质，R(x)表示x有R性质–»»对于任何kN–»–»对于任何nN，R(n)

排序概 数理逻辑基本概真可证 概念与论概基本概念：不加定义的概函数（运算每个定义域值唯一对应值域一关有序偶(orderedpairs)集合 概念与论域（续 (2一个关于D的函数集合论论域=<对象集合运算集合关系集合>论域研究对象 欧几里德几何《几何原本》是一个实质公理系命题分为公理（5）、公设由公理公设出发加以证明的定理公12．等最加等3，等量减等4．彼此能重合的物体是全等的5．整体

公1.由任2.一条3.以任4.凡直 皮亚诺算术实质公基本概数数n的后继n'自然数公1．02．对每个自然数n，存在另一自然数n'3．没有自然数n，使得n'等于04．对任意的自然数m和n，如果m'=n'，那么m=nn'N，那么N包含每个自然数。 自然数论对象集合：自然数运算（函数）：+,关系：=,特殊 自然数理L=<=，+，∘,s,0>，其中=是等词，s是一元函词；公xy 逻辑形式结例13所以32也是奇数

如果A，那么B并且所以B 逻辑形式结例角A和角B相等或互角x和角y不相所以角x与角y互补例函数y=f(x所以函数y=f(x

逻辑形式结A或B并且非所以B 论域、理论及普遍真论域—实质公原始概念、导出概论域上的定理：具体概念关系证理论—形式公符原始理论上的定理：公式之间的形式证在论域（模型）上的真理与在理论上的真理关研究普遍性的真理（有效性 数理命题逻辑、谓词逻辑（一阶逻辑数理逻辑使用特制的表意符号，亦称为符号逻辑研究对象—逻辑真，表示为T或假，表示为F或正确正确必然 提基本概念：集合、函数、归纳1.1命题和联结1.21.3等值演1.4对偶定1.51.6范1.7逻辑推 什么命题的如何有多 语句陈述疑问祈使感叹

雪是白的2X+Y>5你是我正在说的首前进自然语言、命命题表达为具有确定真假意义的陈述句 命题雪是2是奇数X+Y>5你是我正在说谎的首都21世纪有人住在月球他很一个

命题命题不确定，非命疑问句，非命悖论，非命命题命题，真，有唯一真假值命题无法确定，非命命题，假，1不是合数和素简单命题与复合命简单命子命

语句联并或否如果当且仅既不…，也不 命题的抽象表自然语言具有用小写字母表示命题，取值为{0,1陈述句的意义为真，称为真命题，真值为1陈述句的意义为假，称为假命题，真值为0命题逻辑的研究对象—数理逻辑从形式结构 逻辑联结若n=0，则称为0元函数命题的操作符（联结词

0元函1元函2元函、、、

当且仅 异

逻辑联结词—非 真值

真值 pq称为p和q的合 p

逻辑联结词—或 真值 pq称为p和q的析取 p

读作p或 真值pqpq001011100111

读作p则 逻辑联结词—等值 真值 p

pq称为p与q，读作p当且仅当q, 真值 pq称为p与q异 p

pq=1 北航在海淀区或北航西城区2 比较2 逻辑逻辑对象：{0,运算：关系：=,pqppqppqpqpq000011010110100100111111

R=={<0,0>,<1,R╞={<0,0>,<0,1>,<1, 命题逻辑运算符数p0001110101pq0000110010110110010011111110 pqpqF101010101010011001100110011100000111100001111110000000011111111

变量数为变量组合 2n运算

22n提基本概念：集合、函数、归纳1.1命题和联结1.21.3等值演1.4对偶定1.51.6范1.7逻辑推 1.2公式和真值赋合式语可满足性与有效 常元0和1变元：命题变元，其值取为真值{0,1定义：命题变元称为原子公式(命题逻辑)合式公式定(1)常元0和1是合式公式(2)(3)若Q,R(Q)、(QRQR(QR)QRQR)是合式公式 合式公式1）0和1是符号，没有表示逻辑真值的意2）、、、、和，也没有表示逻辑运算的意3）命题变元也是符号合式公式的定义具有抽象性和严格 合式设S是联结词的集合。由S生成的公式1）若c是S中的0元联结词，则c是由S2）原子公式是由S卢卡西维茨运算符表 合式设S是联结词的集合是{，∧，∨，，→，↔(pq)(pq)p,q(pq),(pq(pq(pq是合式

(p→0)∧(q→1)0,1合式公p,q(p0q1)是(p0q1)是 命题逻辑 命题逻辑语言，记为L。一般来说，命题逻辑语言L是无穷集，也就是说合式公式有无穷多个 公式复杂公式A的复杂度表示为1）常元复杂度为02）命题变元复杂度为0，如果p是命题变FCp)=03）如果公式A=B，则FC(A)FC(B)14）如果公式A=B1B2或A=B1B2或A=B1B2或A=B1B2或A=B1B2，则FCA)=max{FC(B1),FC(B21 公式序：联结词的 联结词的优先(((((pq)r)q)p)=((((pqr)q)p)=(((pqrq)p)=((pqrqp)q)=(pqrqp) 真值表计 真值表(pq)(pq (pq)(pq

容易、直pqp¬p∨q¬(p∧q)↔¬p∨q00011111010110111001011111100001 (命题逻辑)合式公式语论域：研究对象的集合用论域的对象对应变元符号指称的对象公式所指称对象合式公式的语义是其对应的逻辑真值 常元和运算符语合式 真值赋值V：A题变元p的真值,v{0,1}。 合式公式设S是联结词的集合是{，，，，，由S生成的合式公式Q在真值赋值v下的真值指派v(Q)v(0)=0v(1)=1⑵若Q是命题变元p，则v(Q)=pvQ1,Q2是合式公若Q= 则v(Q)=)若=， 则v)若=1Q2则v(Q)=v(Q1))若Q=Q1Q2，则v(Q)=v(Q1) 真值由S生成的公式Q在真值赋值vv(Q⑴若Q是S中的0元联结词c，则v(Q)=c⑵若Q是命题变元p，则v(Q)=pv⑶若Q是Q1n，其中n≥1F是S中 语义方法的计真值赋值函v(p)=1,v(q)=1,=v(p)=v(p)

v(p)=0,v(q)=1,=v(p)=v(p) 简化v(p)=0或==1 简化计算（续v(p)=1并且==1 等价真值Q中出现的每个命题变元ppv1pv2；则证明对Q的长度(复杂度)若Q的长度是0，则Q是命题变元或0⑵若Q是命题变元p则v)pv1pv2=v( 等价真值赋值（续归纳假设知道(Qi)=(Qi)i=1,…,nQQ•=FQ•=FQ•QQ因此v1(FQ1QnQQ证 定理1.1的涵若公式Q中出 题变元为p,pk真值赋值，则v(Q)只与pv有关k用

/a1,...p

an表示满

pv,...,p

的真值赋值 p a,...,pvp 例1设公式Q为p∨0→q∧1, =v(p)∨v(0)→v(q)∧ 定理1.1的涵义（续(pq)v((pq)=(v(p)v(q))=(00)=0

v((pq)pq)v((pq)pq)v((pq)pq) 可满足性和有效定义1.7设Q⑴如果真值赋值v使得v(Q)=1，则称v满足Q 代换和替定义1.8用B1,...,Bn公式分别代换公式Q命题变p1pn得到的公式记代换产

QQ

，称为Qr(ppqr=(rp)(rp) (p/rp, v(Qp1,...,pn)v([

/v(B),...,p/

(,/(pv

v(B1

pp1...v p Bv(Qp1,...,pn)B 先代换而后求值=？先代换式求值，再代换，再求证明：对Q进行归B⑴若Q是pi，其中1≤i≤n，则v(Qp1,...,pn是B

)v(B)B)⑵若Q是除p1,...,)仍是

之外题变元p，则

,...,pnBv(Qp1,...,pn)v(p)B B(3)若Q是0元联结词c，则v(Qp1,...,pnB BQ1,...,pn)v(c)vB

...,pn

)v'(Qi 若Q是FQ1,,Qk其中F是k元联结词，是

p1,...,p

)F(v((Q)p1,...,pn

),..., )p1,...,pn Fv'1v'(Qk))v'F(Q1),...,Qk)v'(Q)定理1.3设Q是公⑴若Q是永真式，则Q的每个替换实例都是永真式

p1,...,pQQ

，对p1,...,p

)v[

/

/

)](Q)所以p1,...,p所以

是永真式pqp)是永真设Q,R是任意公[p/Q,Q=p∨q,R=(p∨(p∨q((pr(p∨q)是永替得到的公式记为，定义1.8用B1,...,Bn公得到的公式记为，合式公

为Q的替换 定理：设Q是合式公式，是Q的子公R1R2，则Q/R因为R1R2，所以v(R1(R2首先选择一个不是公式Q中题变元p。不因此，有/R1QQ/R2QR1/R2Q又因为v(p/R1]Q')=v(pR2Q)v(因此，有v(p/v(R1)]Qv([/v有v(p/R1]Qv(有v(QvR1/R2]Q有Q/因此，若R1R2，有Q提基本概念：集合、函数、归纳1.1命题和联结1.21.3等值演1.4对偶定1.51.6范1.7逻辑推 等值演定义1.9设QR是公式，如果对于每个真值赋R逻辑等价，记为QR。判断(p∨q)和p∧q是否等pqp∨(p∨0001111011010010100101110000 等值式模式(演算零幂等吸收

双重律排中同一Q

Q∨Q假言易位(逆否命题P→Q 等值式模式（续德摩根Q 等值式模式（续结合 等值式模式（续例1.5证明证明

摩根示例(pr)(qr)(pq)(pr)(q(pr)(q(pq)prqrr(pq)prqr(pq)(pq)(pq)

摩根 示例p(qr)(pq)(pp(qp(qpqpq(pp)pqpqppqpqpp(pq)p(pq)(p(pq)(p

示例例1.6用等值演算证明p⊕(q∧r)→p∨q∨r1∧1 提基本概念：集合、函数、归纳1.1命题和联结1.21.3等值演1.4对偶定1.51.6范1.7逻辑推 对偶定定义1.10对偶A=A*=定义1.11相反真值赋

B=(p∨0)B*=如果真值赋值v和v满足对每个命题变元p，

pp

称v和v是相

反的 v1p0q1 v2=<p1,q0, 示

v'((p∧q∧1)∨r∨0=(v'(p)∧v'(=(0∧1∧1)∨0∨0=0= 对偶式的真值赋证明1.A的复杂度为0，定理成⑴若A为命题变元则A*也为p，v(p)=v'(p⑵若A为0，则A*为1，v(1)=v'(0⑶若A为1，则A*为0，v(0)=v'(1 2.假设对于复杂度不超过n的每个公式B，v(B*)=v'(B3.证明复杂度等于n(1)若A为B，v(B*)=v'(B)，并且A*为B*因此，v(A*)=v(B*)=v(B*)=v'(B)=v'(B)=因此=v'(B)∨v'(C)==v'(B∧C)=因此=v'(B)∧v'(C)=v'(B∨C)=对偶定理5对偶定理：A,{,,,,}生成的公式，A与与偶式。如果AB，则A*B*。证明v(A*)=v'(A)=v'(B)=v(B*)所以，A*B*证 借助对偶定理的证证明等值式(1)(pq)(p(pq))p(2)(pq)(p(pq))p证明：等值式(pq)(pp证明：等值式对偶 提基本概念：集合、函数、归纳1.1命题和联结1.21.3等值演1.4对偶定1.51.6范1.7逻辑推 p→q=pq=(p→q)∧(q→p)=pq=(p∧q)∨结论，，，，，不是独立问题命题逻辑的最少联接词集是什 完全 定义F称F可由S定义。如：S={,,}p→q=pq=(p→q)(q→p)=pq= 真值表的(p/0,q/1),(p/0,q/1)(p/0,q/1),(p/1,q/0),

pqF101010101010011001100110011100000111100001111110000000011111111 定义1.13完全 完全集定定理题变元，可以找出定义F的由{,,}生成的公式A。若Fp1p2pn是永假式，取A为p1p1pa1pa1pampam，则取A (p1.....p1)......(pm.....pm 其 p 若 ijj 若ai 完全集定任取真值赋值v，v(A)=当且仅当有1≤i≤n当且仅当有1≤i≤n当且仅当有1≤i≤n当且仅当有1≤i≤n

v(pi.....pi) v(pi).....v(pi) v(pi).....v(pi) v(p/ai,......, 都可由联结词集合S定义，则S也是完全极小完全 极小完全集定定理⑴{,∧}，⑵{,∨}，⑶{,证明：（先证明是完全集，在证 定义是完全集，所以{,∧}也是完全集

(3)证明{,∧}是极小完全证明{∧}不是完全 题变元，其公式模式：p∧p∧…∧p结论:不能由∧再证明{取一元联结词F使F(0)=F(1令真值赋值v1p1和任取由{}生成只出现命题变元p的公式公式F不能由{}定义。{}是完全是完全集，所以{,}也是完全证明{取真值赋值v=(p/1v(A)=1，而v(p)=0，A不能定义所以不能由{{}不是完全{结论：{,与非（↑）、或非 pq0011011010101100{↑}是完备{↓}是完备提基本概念：集合、函数、归纳1.1命题和联结1.21.3等值演1.4对偶定1.51.6范1.7逻辑推

1.6=(pr)(q=(pqr)(pqr)(pqr)(pq结论公式唯一性等值公式有唯一的表判断公式等值—

范式定义⒈１４原子公式和原子公式的否定统定义设n是正整数，A,,An都是A1An为简单合取式。例如：(pqr)，(pq

定义⒈１６设n是正整数B1B为析取范式简单合取式的析取是析取(pqr)(pqr)(pq简单析取式的合取是和取(pqr)(pqr)(pq合取范式与析取范(pqr)((pq)r)p((pq)r)((pq)r)(pq)(r

(pqp)(r合取(p(rp))(q(r(pp)(pr)(qr)(qp(pr)(qr)(qp(qr)(q

析取p(rr)(pr)(qr)(q(pr(pr(qr)(q 不唯

主析取范式与主合取范是不同题变元。若对于每个i

定义⒈１８设m是自然数主析取范式和主合取范式统称为主范式为p1p2…,，则称B为A的主析取范式（主合取范式）主范式变换联接（1）消去联接词、、将公式由∧、∨、表ABABAB德.摩根（2）(A∨B) (A∧B)主范式变换步分配（3）A∨(B∧C)A∧(B∨C) A∧A A∨A交换（5）A∨B A∧B

主合取范(p∨r∨q)∧(p∨r∨q)∧

主析((pq)(pq))(pq)(pq)p((pq)(pq))p(pq)(pq)ppqpqppqp(qq)qp(pq)(pq)(pq)ppqpqpqp任何公任何公每一公每一公⑴A是永真式⑴A提基本概念：集合、函数、归纳1.1命题和联结1.21.3等值演1.4对偶定1.51.6范1.7逻辑推

1.7逻辑推论— 公式取值，v(A)=任意赋值函数为任意赋值函数为有的赋值函数为可满足的公式之间的关当v(AB)=1,V(A)=1,ABAB00010010111010011111

当V(AB)=1,v(BC)=1,ABC000111001111010101011111100010101011110100111111

1.7逻辑推Γ={A,…,定义若真值赋值v满足公式集合Γ中的每个公式，1=1,