离散数学全课件含复习题2数理逻辑

第三题逻辑的主要内容自然推理系统形式系统的定义与自然推理系统在P中构造证明:直接证明法、附加前提证明法、1推理理前提是已 ，结论是从前题发应用推理规则推 2推理的形式结定义3.1设A1,A2,…,Ak,B为命题 .若对于每组赋值，则称由前提A1,A2,…,Ak推出结论B的推理是有效的或正确的,并称B是有效结论.定理3.1由命 A1,A2,…,Ak推B的推理正确当且仅A1A2…AkB为重注意:推理正确不能保证结论一定3推理的形式推理的形式结{A1,A2,…,Ak}若推理正确,记为 若推理正确记为A1A2Ak前提A1A2结论等值演主析取范4推理实例 判断下面推理是否正若今天是1号，则明天是5号.今天是1号.所以,明天是5号若今天是1号，则明天是5号.明天是5号.所以,今天是1号解设p：今天是1号，q：明天是5号推理的形式结构 用等值演pqq由定理3.15推理实

(pq)(pq)结果不含m1,故01是成假赋值，所以推理6例就不去游泳，天气凉快，所 没去游泳设p：天气凉快去游前提：p→﹁q,p。结论：﹁q推理的形式结((p→﹁q)∧p)→﹁q下面分别用三种方法来判断该蕴含式是否为重言真值表((p→﹁q)∧p)→﹁q(*)的真pq﹁p→﹁(p→﹁001101010101101111110001等值演算((p→﹁q)∧p)→﹁((﹁p∨﹁q)∧p)→﹁﹁((﹁p∨﹁q)∧p)∨﹁﹁(﹁p∨﹁q)∨﹁p∨﹁﹁(﹁p∨﹁q)∨(﹁p∨﹁该蕴该蕴含式是重言式，所以推理正﹁((﹁p∨﹁q)∧p)∨﹁﹁(﹁p∨﹁q)∨﹁p∨﹁(p∧q)∨(﹁p∧(q∨﹁q))∨(﹁q∧(p∨﹁(p∧q)∨(﹁p∧q)∨(﹁p∧﹁q))∨(﹁∨(﹁q∧﹁(p∧q)∨(﹁p∧q)∨(﹁p∧﹁q))∨(p∧﹁该该蕴含式的主析取范式中含有4个极小项，因而是重 前提，或者是由某些前提应用推理规则得到的论。其中有些规则建立在推理定律（重言蕴涵式的基础拒取式、析取、假言、等价、构造性二难破坏性二难。除此之外，每个等值式均产生两条推理定律。推理定律——重言蕴A(AB)(AB)A(AB)B(AB)B(AB)(BC)(AB)(BC)(AB)(CD)(AC)(AB)(AB)

等构造性二构造性二难(特殊形式(AB)(CD)(BD)每个等值式可产生两如由AA可产生AA和

破坏性自然推理系统定义 一个形式系统I由下面四个部分组成非空的字母表，记作 集，记作E(I)中一些特殊 组成的公理集，记作推理规则集，记作记I=<A(I),E(I),AX(I),R(I其中<A(I),E(I)>I形式语言系统,<AX(I),R(I)>I的形式演算系统自然推理系统:无公理,即公理推理系统推出的结论是系统中的重言式,称作定自然推理系统定义3.3自然推理系统P定义如下字母命题变项符号：pqrpiqiri联结词符号：括号与逗号：合 （同前推理规前提引入结论引入置换规假言推理 (6)化简 ∴(8)假 规

推理规附加规A(7)拒取式规 析 规 推理规构造性二破坏性二 合取引入规 在自然推理系统P中构造设前提A1,A2,,Ak,结论B及 序列C1,C2,,Cl.如果每一个Ci(1il)是某个Aj,或者可由序列中前面的 规则得到,并且Cl=B,则称这个 序列是由A1,A2,,Ak推例3构造下面推理的证若明天是星期一或星期三，我明天就有课.若我明天有解(1)设命题设p：明天是星期一，q：明天是星r：我明天有课，s：我今天备 直接证明写出证明前提 rs,结论证①②③④⑤⑥

前提前提引⑤置例写出对应下面推理的证解：将解：将简单命题符p：a是实数 前提：p→(q∨r),﹁s→﹁q,p∧﹁s。结论：r前提：p→(q∨r)﹁s→﹁qp∧﹁s。证明：①p∧﹁③﹁⑤⑥﹁s→﹁⑦﹁

前提引①化前提引③⑥假言推⑤⑦析0在使用构造证明法来进行推常常采用一些技巧，下面介1、附加前提证2附加前提证附加前提证明法适用于结论为蕴涵式前提：A1A2前提：A1A2Ak((附加前提证明法例 构造下面推理的证2是素数或合数若2是素数，则2是无理数若2是无数，则4不是素数.所以，如果4是素数，则2是合数设p：2是素数，q：2r：2是无理数，s：4是素推理的前提：pq,pr,附加前提证明法前提：pq,pr,结论证①②③④⑤⑥⑦

附加前提前提引②③假①④拒取前提引⑤⑥析解解：将简单命题符r：去看；去；s：小赵去；。前提：p→(q→r)﹁s∨pq结论：s→r例 去 。所以当小赵去 时，小李也去前提：p→(q→r)﹁s∨pq结论：s→r②前提引附加前③①②析④前提引⑤③④假⑥前提引⑦⑤⑥假归谬法（反证法归谬法(反证法欲前提：A1A2结论做提中加入B，推 理归谬法实例 前提：(pq)r,rs,s,结论证明①②③④⑤⑥⑦⑧⑨

结论否定②③拒取前提引④⑤析⑥置①⑦析前提引⑧⑨合例前提：p→(﹁(r∧s)→﹁q)p﹁s。结论：﹁q。证明：①p→(﹁(r∧s)→﹁②③﹁(r∧s)→﹁(﹁⑤⑥⑦s∧﹁

前提前提否定结论④置③⑤拒取⑥化前提⑨ 式，根据归谬法说明推理正确 主要内推理的形判断推理是否正确的方主析取范推理定自然推理系统构造推直接证附加前提归谬法(反证法基本要理解并记住推理形式结构的两种形前提：A1A2结论）牢记P系统中各条推理法会解决实际中的简单练习1：判断推理是否判断下面推理是否正确(1)前提：pq,解推理的形式结构 方法一10是成假赋值，不是重言式，所以推理不正确练习1解方法二：主析取范式未含m2,不是重言式,推理不正确练习1解方法三真值表pqpq00001011011011011101不是重言式,推理不正方法四直接观察出10练习1解(2)前提 结论理的形式结构用等值演推理正练习2：构造证在系统P如果今天是周六，我们就到或圆明园玩.如果颐和园游人太多，就不去.今天是周六，并且游人太多.所以,我们去圆明园或动物园玩.证明设p：今天是周六，q： 玩， 游人太多t：前提：p(qr),sq,p,练习2解前提 p,结论证明①②③④⑤⑥⑦⑧

前提引④⑤假言③⑥析⑦附习题三（52页

第四阶逻辑基本 是人；R R主要一阶逻辑一阶逻 及其解合 的解永真式 式、可满足一阶逻辑命题符号词——常项ab,表示变项：抽象的事物，用x,y,z 域，如{a,b,c},{1,2}无 域，如N,Z,R,全 域——由宇宙间一切事物组谓G(x,yx>y

n（n1）一元谓词(n=1)——表示性多元谓词(n2)——表示事物之间的如,L(x,y)：x与y有关系L，L(x,y)：xy，… 或命题谓词变

量量词——表示全称量词:表示所有的x: 域中所有的如,xF(x)表 域中所有的x具有性质xyG(x,y)表 域中所有的x和y有关系存在量词:表示存在,有一个x 域中有一个如,xF(x)表 域中有一个x具有性质xyG(x,y)表 域中存在x和y有关系xyG(x,y)表示 域中每一个x都存在一个y使x和y有关系xyG(x,y)表 域中存在一个x使得对每一个x和y有关系实例例1用0元谓词将命题符墨西哥位于32是无理数仅 是有理3如果2>3，则解：在命题逻辑中 p为墨西哥位于南美洲（假命题p→q,其中p是无理数，q3是有理数是假命pq,其中，p：2>3，q：3<4.是真命实例1解在一阶2F(a)，其中，a：墨西哥，F(x)：x位于南美洲2

其中，F(x)：x是无理数，G(x)：x是有理F(2,3)G(3,4)，其中，F(xy)：x>y，G(x例1用0元谓词将命题符墨西哥32是无理数仅 是有理3如果2>3，则实例人都爱有人用左域分D为人类集D为全 解 (1) G(x)：x爱(2)xG(x),G(x)：x用左(b)F(x)：x为人，G(x)：x引入特性谓词 2.(1),(2)是一阶逻辑中两个“基本实例正数都大有的无解注意：题目中没 域，一律用全 令F(x)：x为正数，G(y)：y为负数或者

令F(x)：x是无理数，G(y)：y或者实例例4在一阶逻辑中将下面命没有不呼解(1)F(x):x是人, G(x):x呼吸F(x):x是人 G(x):x喜欢吃实例例5 域为实数域,将下面命题符号对每一个数x都存在一个数y使得解L(x,y):x<y 注意:与不能随意交显然(1)是真命题,(2)是假命一阶逻 及解定义4.1设L是一个非逻辑符集合由L生成的一阶语言L的非逻辑常项符号：abcaibicii函数符号：fghfigihii谓词符号：FGHFiGiHii逻辑变项符号：xyzxiyizii量词符号：,联结词符号：括号与逗号：一阶语言L的项与原定义4.2L的项的定常项 变项是项如,a,x,x+y,f(x),g(x,y)等都是项定义4.3设R(x1x2xn)是L的任意n元谓词，t1t2是L的任意n个项，则称R(t1,t2,…,tn)是L的原 如，F(xyF(f(x1x2g(x3x4))一阶语言L定义4.4L的合 定义如下原 是合 若A是合 ，则(A)也是合若A,B是合 ，则(AB),(AB),(AB),(AB)也合若A是合 ，则xA,xA也是合只有有限次地应用(1)—(4)形成的符号串才是合 合 简如 F(x)G(x,y),xy(F(x)G(y)L(x,y))等都封闭定义4.5在xA和xA中，称x为指导变元，A为相应例如，x(F(x,y)G(x,z))，x为指导变元，(F(x,y)G(x,z))x的辖域，x的两次出现均为约束出现，y与z均为自由又如,x(F(x,y,z)y(G(x,y)H(x,y,z))),x中的x是指导变元辖域为(F(x,y,z)y(G(x,y)H(x,y,zy中的y是指导变元辖域为(G(x,y)H(x,y,z)).x的3次出现都是约束出现,y的第一次出现是自由出现,后2次是约束出现,z的2次出现都是自由出现封闭定义4.6 A中不含自由出现 变项，则称A为封 ，简称闭式例如，xy(F(x)G(y)H(x,y))为闭式 的解定义4.7设L是L生成的一阶语言L的解释I由4非 域DI对每一 常项符号aL,有一个aDI,称a为aI中的解释 对每一个n元谓词符号FL,有一个DI上的n元谓词常项F,称F为F在I中的解释. A,取 域DI,把A中的 号f、谓词符号F分别替换成它们在I中的解释a、f、F,称 A为A在I下的解释,或A在I下被解释成A.实例6给定解释Iaf(x,y)xF(x,y):x

g(x,y)x写出下 它的真值 (3) 真值不定,不是命 的类注意:不是闭式 在解释下可能是命题,也可能不是命题定义4.8若A在任何解释下均为真,则称A为永真式(逻辑有效式).若A在任何解释下均为假,则称A为式(永假式).若至少有一个解释使A为真,则称A为可满足式.几点说明永真式为可满足式，但反之不判 是否是可满足的(永真式 式)是不可判定代换实定义4.9设A0是含命题变项p1,p2,…,pn A2,…,An是n个谓词 例如，F(x)G(x),xF(x)yG(y)等都是pq的代换实例定理4.2重言式的代换实例都是永真式， 实例 判断下 中，哪些是永真式，哪些 式重言式p(qp)的代换实例，故为永真式式(pq)q的代换实例，故为永假式解释 域N,F(x):x>5,G(x): 为 域N,F(x):x<5,G(x):x<4, 结论:非永真式的可满足式习题四（65页 主要一阶逻辑一阶语言项、原 、合的解 的类永真式(逻辑有效式) 式(永假式)、可满足基本要准确地将给定命题符号理解一阶深刻理解熟练地给 的解记住闭式 练习在分别 域D3为全 的条件下,将下面命题符号化，并讨对于任意的数x，均有x22(x 2)(x 2

x22(x 2 又设F(x):x 练习1(续存在数x，使得解设 本例说明：不 域内，命题符号化形式可能不同（也能相同），真值可能不同（也可能相同练习在一阶大熊猫都设F(x):x为大熊猫，G(x):x可有人爱发设F(x):x是人，G(xx爱发说所有设F(x):x是人，G(xx爱吃x(F(x)G(x))或练习没有不设F(xx是人，G(xxx(F(x)G(x))任何两个设F(x):x是人H(x,yx与y相同L(x,y