离散数学大作业.doc

离散数学大作业班级:15计算机2班学号:姓名:王鹏时间::数理逻辑将能够判断真假的陈述句称作命题。﹁∧同时为真,∨同时为假,→当且仅当p为真,,、,简称公式,定义为:(1)单个命题变元是公式;(2)如果P是公式,则﹁P是公式;(3)如果P、Q是公式,则P∧Q、P∨Q、PQ、PQ都是公式;(4)当且仅当能够有限次的应用(1)、(2)、(3)所得到的包括命题变元、联结词和括号的符号串是公式。,转变成数理逻辑中的符号形式,称为命题的翻译。命题翻译时应注意下列事项:(1)确定所给句子是否为命题。(2)句子中联结词是否为命题联结词。(3)要正确的选择原子命题和合适的命题联结词。,称为G的真值表。构造真值表的方法如下:(1)找出公式G中的全部命题变元,并按一定的顺序排列成P1,P2,…,Pn。(2)列出G的2n个解释,赋值从00…0(n个)开始,按二进制递加顺序依次写出各赋值,直到11…1为止(或从11…1开始,按二进制递减顺序写出各赋值,直到00…0为止),然后从低到高的顺序列出G的层次。(3)根据赋值依次计算各层次的真值并最终计算出G的真值成真赋值+成假赋值=:(1)如果G在所有解释下取值均为真,则称G是永真式或重言式;(2)如果G在所有解释下取值均为假,则称G是永假式或矛盾式;(3)如果至少存在一种解释使公式G取值为真,则称G是可满足式。,如果A和B在任意赋值情况下都具有相同的真值,则称A和B是等价公式。记为AB。性质定理设A、B、C是公式,则(1)AA(2)若AB则BA(3)若AB且BC则AC定理设A、B、C是公式,则下述等价公式成立:(1)双重否定律AA(2)等幂律A∧AA;A∨AA(3)交换律A∧BB∧A;A∨BB∨A(4)结合律(A∧B)∧CA∧(B∧C)(A∨B)∨CA∨(B∨C)(5)分配律(A∧B)∨C(A∨C)∧(B∨C)(A∨B)∧C(A∧C)∨(B∧C)(6)德·摩根律(A∨B)A∧B(A∧B)A∨B(7)吸收律A∨(A∧B)A;A∧(A∨B)A(8)零一律A∨11;A∧00(9)同一律A∨0A;A∧1A(10)排中律A∨A1(11)矛盾律A∧A0(12)蕴涵等值式A→BA∨B(13)假言易位A→BB→A(14)等价等值式AB(A→B)∧(B→A)(15)等价否定等值式ABABBA(16)归缪式(A→B)∧(A→B)(置换规则)设(A)是一个含有子公式A的命题公式,(B)是用公式B置换了(A)中的子公式A后得到的公式,如果AB,那么(A)(B)。Ø、∧、∨的命题公式A中,将联结词∧换成∨,将∨换成∧,如果A中含有特殊变元0或1,就将0换成1,1换成0,所得的命题公式A*称为A的对偶式。例:公式(P∨Q)∧(P∨Q)的对偶式为:(P∧Q)∨(P∧Q)定理设A和A*互为对偶式,P1,P2,…,Pn是出现在A和A*中的所有原子变元,若将A和A*写成n元函数形式,则(1)A(P1,P2,…,Pn)A*(P1,P2,…,Pn)(2)A(P1,P2,…,Pn)A*(P1,P2,…,Pn)定理(对偶原理)设A、B是两个命题公式,若AÛB,则A*B*,其中A*、B*分别为A、B的对偶式。,仅由有限个命题变元及其否定构成的合取式称为简单合取式。定义仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。定理(范式存在定理)任何命题公式都存在着与之等价的析取范式和合取范式。,P1,P2,…,Pn为G中的所有命题变元,若G的析取范式中每一个合取项都是P1,P2,…,Pn的一个极小项,则称该析取范式为G的主析取范式。矛盾式的主析取范式为0。定理任意的命题公式都存在一个唯一的与之等价的主析取范式。定义设G为公式,P1,P2,…,Pn为G中的所有命题变元,若G的合取范式中每一个析取项都是P1,P2,…,Pn的一个极大项,则称该合取范式为G的主合取范式。通常,主合取范式用∏表示。重言式的主合取范式中不含任何极大项,用1表示。定理任意的命题公式都存在一个唯一的与之等价的主合取范式。、H是两个