DM02-命题演算
四计算命题演算公式的真值 一．实验题目 所谓命题演算公式是指由逻辑变量（其值为TRUE或FALSE）和逻辑运算符∧（AND）、∨（OR）和┐（NOT）按一定规则所组成的公式（蕴含之类的运算可以用∧、∨和┐来表示）。公式运算的先后顺序为┐、∧、∨，而括号（）可以改变优先次序。已知一个命题演算公式及各变量的值，要求设计一个程序来计算公式的真值。 要求： （1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。 （2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。 （3）根据用户的要求显示表达式的真值表。 二．实验设计 1. 设计思想 （1）数据结构设计 a 建立一个链式堆栈，实现括号的匹配问题。 b建立一个顺序堆栈，来实现中缀转后缀并实现二叉树的打印。 （2）算法设计 a.括号匹配 b中缀转后缀 c打印二叉树和真值表 2. 设计表示 自定义和调用的函数如下所示： #include"" #include"" #include<> #include<>
#include<> #include<> #include<> 函数说明如下 SeqStack1; /*定义一个堆栈SeqStack1*/ void StackInitiate1(SeqStack1 *S) /*初始化堆栈1，栈底为‘#’*/ void StackPush1(SeqStack1 *S,DataType x) /*将元素压入堆栈1*/ void StackPop1(SeqStack1 *S,DataType *x) /*弹出堆栈1的栈顶元素*/ int StackTop1(SeqStack1 S,DataType *d) /*取堆栈1的栈顶元素*/ SeqStack2; /*定义一个顺序堆栈SeqStack2*/ void StackInitiate2(SeqStack2 *S) /*初始化堆栈2*/ BiTreeNode * StackPop2(SeqStack2 *S) /*从堆栈2中弹出栈顶元素*/ BiTreeNode; /*定义二叉树的结点*/ void Initiate(BiTreeNode **root) /*初始化树的根结点*/ void print(BiTreeNode *bt,int n) /*逆时针打印二叉树*/ void StackPush2(SeqStack2 *S,BiTreeNode *x) /*将二叉树结点压入堆栈2*/ int Convert(char a[500],char b[500][100],SeqStack1 *S,int n) /*将待求表达式转换为后缀形式*/ BiTreeNode * BuildTree(char b[500][100],int n)/*根据表达式的后缀形式，构造相应的二叉树*/ LSNode; /*定义了链式堆栈用于下面检测表达式的括号匹配*/ void StackInitiate(LSNode** head) /*初始化堆栈*/ int StackNotEmpty(LSNode* head) /*检测堆栈是否为空的函数*/ int StackPush(LSNode* head,DataType x) /*将元素入栈*/
---------------------------------------------------------------最新资料推荐------------------------------------------------------ 6 逻辑代数(上)：命题演算习题答案 练习 6.1 1. 判断下列语句哪些是命题，若是命题其真值是什么？（1） a+b+c。 （2） x 0 。 （3）请进！（4）离散数学是计算机科学与技术专业的基础课程。 （5） 2009 年 7 月我们去意大利的米兰旅游。 （6）啊！这里真漂亮。 （7）今天是星期四吗？（8）我明天或者后天去天津。 （9）如果买不到飞机票，我就去不了海南。 （10）除非你陪我，否则我不去。 （11）本命题是假的。 （12）如果雪是黑的，太阳从北边升起。 解： （1）不是命题。 （2）不是命题。 （3）不是命题。 （4）是命题。 真值是 1。 （5）是命题。 真值是 0。 1 / 17
（6）不是命题。 （7）不是命题。 （8）是命题。 真值是 0。 （9）是命题。 真值是 1。 （10）是命题。 真值是 1。 （11）不是命题，是悖论。 （12）是命题。 真值是 1。 2. 指出下列语句哪些是原子命题，哪些是复合命题？并将复合命题形式化。 （1）他去了教室，也去了机房。 （2）今晚我去书店或者去图书馆。 （3）我昨天没有去超市。 （4）我们不能既看电视又看电影。 （5）如果买不到飞机票，我就去不了海南。 （6）小王不是坐飞机去上海，就是坐高铁去上海。 （7）喜羊羊和懒羊羊是好朋友。 （8）除非小李生病，否则他每天都会练习书法。 （9）侈而惰者贫，而力而俭者富。
1.7 推 理 理 论 从假设前提利用推理规则得到其他命题，即形成结论的过程就是推理，这是研究逻辑的主要目标。 1.7.1 蕴含与论证 1．推理的含义与形式 [定义1-22] 当且仅当p →q 为永真式时，称为p 蕴含q （logical implication ），记作p q ?，或p q 。此时，称p 为前提，q 为p 的有效结论或逻辑结论，也称为q 可由p 逻辑推出。得出此逻辑关系的过程称为论证。 [辨析] 由于仅在p 为1而q 为0时公式p q →为0，可见，p q →永真意味着不可能存在前件p 为1而后件q 为0的情况，或者说，若p q ?，则只要前件p 为1，后件q 也一定为1。因此，p q ?也称为“永真蕴含” ，即p 永真蕴含q 。 [延伸] 通常，定理（theorem ）被解释为“经过受逻辑限制的证明为真的陈述”，就是指对“在一定条件成立的情况下必然产生某个（些）结论”的陈述。因此，定理证明也就是对蕴含关系的论证。当然，通常只有重要或有趣的陈述才被视为定理。 所有逻辑推理的实质就是证明p q ?，也就是证明p q →为永真式。例如，以下是一个简单的初等数学证明题目： 已知a 、b 、c 为实数，且22a b bc -=，0c ≠，则有2/(/1)a c b b c =+。 如果记 p ：22a b bc -=，q ：0c ≠，r ：2/(/1)a c b b c =+ 则上述论证要求可描述为： p q r ∧? 证明的目的就是说明：若前提p q ∧正确，则结论r 也正确，即证明p q r ∧→为永真式。 通常的逻辑推理问题都会由一组前提来推断一个逻辑结论，此时的多个前提可写成合取式12n H H H ∧∧∧ ，或写成用逗号分隔的命题序列H 1, H 2, ..., H n ，即论证要求可写作： 12n H H H C ∧∧∧? ，或12,...,n H H H C ?，，或 12n H H H C ∧∧∧ ，或12,...,,n H H H C 可见，论证A C 、A C ?或A C →是永真式都是同义的，且前提也可以用集合表示，如： 12{,..,},.n H H H C 在数学上，总是要求前提为真，从而推导出有效的结论，并不需要研究从假的前提能得到什么结论，且推理形式与前提的排列次序无关。尽管由前提A 到结论C 的推理一般记作A C ，如
逻辑判断推理中常用的 逻辑公式 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】
逻辑命题与推理 必然性推理（演绎推理）：对当关系推理、三段论、复合命题推理、关系推理和模态推理 可能性推理：归纳推理（枚举归纳、科学归纳）、类比推理 命题 直言命题的种类：（AEIOae） ⑴全称肯定命题：所有S是P（SAP） ⑵全称否定命题：所有S不是P（SEP） ⑶特称肯定命题：有的S是P（SIP） ⑷特称否定命题：有的S不是P（SOP） ⑸单称肯定命题：某个S是P（SaP） ⑹单称否定命题：某个S不是P（SeP） 直言命题间的真假对当关系： 矛盾关系、（上）反对关系、（下）反对关系、从属关系 矛盾关系：具有矛盾关系的两个命题之间不能同真同假。主要有三组： SAP与SOP之间。“所有同学考试都及格了”与“有些同学考试不及格” SEP与SIP之间。“所有同学考试不及格”与“有些同学考试及格” SaP与SeP之间。“张三考试及格”与“张三考试不及格” 上反对关系：具有上反对关系的两个命题不能同真（必有一假），但是可以同假。即要么一个是假的，要么都是假的。存在于SAP与SEP、SAP与SeP、SEP与SaP之间。 下反对关系：具有下反对关系的两个命题不能同假（必有一真），但是可以同真。即要么一个是真的，要么两个都是真的。存在于SIP与SOP、SeP与SIP、SaP与SOP之间。 从属关系（可推出关系）：存在于SAP与SIP、SEP与SOP、SAP与SaP、SEP与SeP、SaP与SIP、SeP与SOP
六种直言命题之间存在的对当关系可以用一个六角图形来表示，“逻辑方阵图” SAP SEP SaP SeP SIP SOP 直言命题的真假包含关系 全同关系、真包含于关系、真包含关系、交叉关系、全异关系 复合命题：负命题、联言命题、选言命题、假言命题 负命题的一般公式：并非P 联言命题公式：p并且q “并且、…和…、既…又…、不但…而且、虽然…但是…” 选言命题：相容的选言命题、不相容的选言命题 相容的选言命题公式：p或者q“或、或者…或者…、也许…也许…、可能…可能…” 【一个相容的选言命题是真的，只有一个选言支是真的即可。只有当全部选言支都假时，相容的选言命题才是假的】 不相容选言命题公式：要么p要么q
第二章作业 评分要求： 1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分 2. 给出每小题得分(注意: 写出扣分理由) 3. 总得分在采分点1处正确设置. 一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次): 说明 证 1. p ?(p ∧q)∨(p ∧?q) 解逻辑方程法 设 p ?((p ∧q)∨(p ∧?q)) =0, 分两种情况讨论: ???=?∧∨∧=0 )()(1)1(q p q p p 或者 ? ??=?∧∨∧=1)()(0)2(q p q p p (1)(2)两种情况均无解, 从而, p ?(p ∧q)∨(p ∧?q)无成假赋值, 为永真式. 等值演算法 (p ∧q)∨(p ∧?q) ? p ∧(q ∨?q) ∧对∨的分配率 ? p ∧1 排中律 ? p 同一律 真值表法
2. (p→q)∧(p→r)?p→(q∧r) 等值演算法 (p→q)∧(p→r) ?(?p∨q)∧(?p∨r)蕴含等值式 ??p∨(q∧r)析取对合取的分配律 ?p→(q∧r)蕴含等值式 3. ?(p?q)?(p∨q)∧?(p∧q) 等值演算法 ?(p?q) ??( (p→q)∧(q→p) )等价等值式 ??( (?p∨q)∧(?q∨p) )蕴含等值式 ??( (?p∧?q)∨(p∧q) )合取对析取分配律, 矛盾律, 同一律 ?(p∨q)∧?(p∧q)德摩根律 4. (p∧?q)∨(?p∧q)?(p∨q)∧?(p∧q) 等值演算法 (p∧?q)∨(?p∧q) ?(p∨q)∧?(p∧q)析取对合取分配律, 排中律, 同一律 说明: 用真值表法和解逻辑方程法证明相当于证明为永真式. 等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得. 二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次): 1. 2. 3. 4. 1. (?p→q)→(?q∨p) 解 (?p→q)→(?q∨p)
第一章引论 内容提要 第一节普通逻辑的对象 一、普通逻辑是研究思维的逻辑形式及其基本规律和简单逻辑方法的科学。 二、思维是人脑的机能，是人脑对于客观事物间接的、概括的反映。思维属于认识过程中的理性认识，由概念、判断和推理所构成。 1 概念是反映事物本质属性或特有属性的思维形式，是思维结构的基本组成要素。 2 判断是对思维对象有所断定（即肯定或否定）的思维形式，它是由概念组成的，同时，它又为推理提供前提和结论。 3 推理是由一个或几个判断推出一个新判断的思维形式，它是思维形式的主体，人们的思维活动主要是靠它来实现的。 4 思维与语言有着不可分割的联系，没有语词和语句，也就没有概念，判断和推理，因而也就不可能有人的思维活动。 5 思维具有两个基本特征：一是思维具有概括性，二是思维具有间接性。 三、任何思维都有具体内容，又有逻辑形式。反映在概念、判断和推理中的特定对象及其属性，叫做思维的具体内容。思维内容各部分之间的联系方式（或形式结构），叫做思维的逻辑形式。 1 思维的逻辑形式与思维的具体内容是紧密联系在一起的，但是，思维的逻辑形式又有其自身的相对独立性。普通逻辑不研究思维的具体内容，也不去研究那些个别的逻辑形式，它只研究各种不同类型的思维形式所共同具有的逻辑形式。 2 思维的逻辑形式由两部分组成，一是逻辑常项，二是变项。逻辑常项是指逻辑形式中固定不变的部分，变项是指逻辑形式中可变的部分。 3 逻辑常项是判定一种逻辑形式为何种逻辑形式的惟一根据，也是区别不同种类逻辑形式的惟一依据。变项不管代入何种不同的具体内容，终究不能改变其逻辑形式。 四、思维的基本规律是任何人进行思维活动（即运用概念进行判断和推理）时都必须遵守的最起码的逻辑规律。思维的基本规律有四条，即：同一律、矛盾律、排中律和充足理由律。 五、简单的逻辑方法主要包括：定义、划分、限制和概括、寻找现象间因果联系的方法等。 第二节学习普通逻辑的意义 学习普通逻辑的根本意义在于：训练和提高人们的逻辑思维能力，促进智力的发展，提高全民族的逻辑修养和文化素质，推动我国社会主义物质文明和精神文明建设。具体说来，学习普通逻辑的意义有五个方面：
3 命题逻辑形式系统（FSPC ） 3.1 命题逻辑与命题演算 Leibniz 提出逻辑推理变成符号演算不久，英国数学家BOOL 提出了布尔代数。布尔代数把逻辑命题与逻辑推理归结为代数计算。把命题看作是计算对象；把联结词看作算子；讨论计算的性质。 1、 命题（Propositions ）：可以判断真假的陈述句。不涉及任何联结词的命题称为原 子命题。 2、 联结词：?, →, ?, ∨, ∧为联结词，用于联结一个或者多个命题。 ->如果A 成立则B 成立，<->如果A 成立则B 成立，并且如果B 成立则A 成立；A ∨B ，或者A 成立或者B 成立；A ∧B ，A 成立并且B 成立。 3、 真值表：命题的真假称为命题的真值，用0表示假；用1表示真。 True(?A)，如果True(A)＝0，True(?A)=1：True(A)=1, True(?A)＝0 A ＝0,1；如果True(A)=1,则 True （ B ）=1,True(A->B)=1:或者True(A)=0或者True(B)=1：或者A 不成立，或者B 成立=?A ∨B ；如果True(A)=0,则 True （B ）=0，1；True(A)=
第二章作业 1 评分要求： 2 1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48 3 分 4 2. 给出每小题得分(注意: 写出扣分理由) 5 3. 总得分在采分点1处正确设置. 6 一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方 7 法每种方法至少使用一次): 8 说明 9 证 10 1. p ?(p ∧q)∨(p ∧?q) 11 解逻辑方程法 12 设 p ?((p ∧q)∨(p ∧?q)) =0, 分两种情况讨论: 13 ?? ?=?∧∨∧=0)()(1 )1(q p q p p 或者 14 ?? ?=?∧∨∧=1 )()(0 )2(q p q p p 15 (1)(2)两种情况均无解, 从而, p ?(p ∧q)∨(p ∧?q)无成假赋值, 为永真式. 16 等值演算法 17 (p ∧q)∨(p ∧?q) 18 ? p ∧(q ∨?q) ∧对∨的分配率 19 ? p ∧1 排中律 20
? p 同一律 21 真值表法 22 即 p? ((p∧q)∨(p∧?q))为永真式, 得证23 2. (p→q)∧(p→r)?p→(q∧r) 24 等值演算法 25 (p→q)∧(p→r) 26 ? (?p∨q)∧(?p∨r)蕴含等值式 27 ??p∨(q∧r)析取对合取的分配律 28 ? p→(q∧r)蕴含等值式 29 3. ?(p?q)?(p∨q)∧?(p∧q) 30 等值演算法 31 ?(p?q) 32 ??( (p→q)∧(q→p) )等价等值式 33 ??( (?p∨q)∧(?q∨p) )蕴含等值式 34
幻灯片1 逻辑学 Logic 政法系：刘惠珍 幻灯片2 第一章绪论 : 逻辑学的研究对象 逻辑学的几个基本概念 幻灯片3 第一节逻辑、逻辑科学 一、逻辑一词的含义： 我们要研究历史发展的“逻辑”。（“事物的逻辑”、“革命的逻辑”） 规律，客观事物发展的规律 把侵略说成是‘友谊’，这是地地道道的强盗“逻辑”。（“荒谬的逻辑”、“霸权主义者的逻辑”） 某种特殊的理论、观点或看问题的方法 概念要明确，判断要恰当，推理要合乎“逻辑”。（“逻辑性强”、“不合逻辑”） 思维的规律、规则 提高能力，首先要提高思维能力，因此，学习逻辑是十分必要的。（“逻辑知识”、“逻辑讲座”） 指逻辑学这门学科 幻灯片4 二、思维规律与逻辑科学 ●思维规律就是逻辑经验、思维经验，是人们日常思维的概括，也就是我们在学习逻辑 学之前所不自觉地学习的类似逻辑知识、所受的类似逻辑思维训练的内容。 幻灯片5 三、逻辑学发展的主要阶段 古代世界的三大逻辑传统： 中国古代的名辩之学 古印度的因明 古希腊的形式逻辑 幻灯片6 1、中国古代的“名辩”之学 ●先秦时期是中国逻辑发端、形成、系统化并空前昌盛的时期。 ●自两汉起，经魏晋、唐、宋、明，热烈研讨古代逻辑之风虽逐渐冷落下来，但仍有一些 学者坚持逻辑问题的研究。 ●明末清初，西方逻辑开始传入中国。 ●自20世纪20年代起，中国逻辑的发展表现为西方传统逻辑的普及和数理逻辑的传入与
理论探索。 幻灯片7 2、古印度的因明 例如： 宗：这山有火； 宗是由辩论一方提出来加以证明的命题； 因是用来说明宗的理由； 喻是例证，分为同喻例证和异喻例证两种，同喻所举的事例与论题具有同一性质，异喻所举事例与论题的性质相反； 合是喻例的运用； 结是对论题的重述，是被因、喻证实了的命题。 因：因为有烟； 喻：凡有烟者有火， 如灶； 合：这山如此（有烟）； 结：因此，这山有火。 幻灯片8 3、古希腊的逻辑学及其发展 ●公元前４世纪时的亚里士多德被公认为逻辑学的创始人（词项逻辑） ●麦加拉——斯多噶学派研究了亚氏逻辑中欠缺的有关复合命题的问题，奠定了命题逻辑 的基础。 ●１７世纪英国哲学家弗兰西斯?培根系统总结和研究了实验科学方法，奠定了归纳逻辑 的基础，被公认为归纳逻辑的创始人。 ●１７世纪未，著名德国数学家、哲学家莱布尼兹提出了用数学方法处理逻辑推理的宏伟 设想，被称为现代逻辑的首创者。 ●２０世纪初，罗素与怀特海合著的《数学原理》，总结了前人的研究成果，建立了一个 完全的命题演算与谓词演算系统，标志着数理逻辑作为一门独立的科学达到了成熟阶段。 幻灯片9 四、逻辑学的分类 逻非形式逻辑 辑形式逻辑：传统形式逻辑：词项逻辑（亚里士多德） 命题逻辑（斯多噶学派） 归纳逻辑（培根） 现代形式逻辑：标准逻辑：两个演算：命题演算基础 （二值逻辑）谓词演算逻辑 四论：集合论逻 证明论辑 递归论基 模型论础 非标准逻辑：多值逻辑、模态逻辑、
题号：第一题 题目：电梯模拟 1，需求分析： 计算命题演算公式的真值 所谓命题演算公式是指由逻辑变量（其值为TRUE或FALSE）和逻辑运算符∧（AND）、∨（OR）和┐（NOT）按一定规则所组成的公式（蕴含之类的运算可以用∧、∨和┐来表示）。公式运算的先后顺序为┐、∧、∨，而括号（）可以改变优先次序。已知一个命题演算公式及各变量的值，要求设计一个程序来计算公式的真值。 要求： （1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。 （2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。 （3）根据用户的要求显示表达式的真值表。 2，设计： 设计思想： <1>，数据结构设计： (1) 线性堆栈1的数据结构定义 typedef struct { DataType stack [MaxStackSize]; int top; /* 当前栈的表长*/ } SeqStack; 用线性堆栈主要是用来存储输入的字符，它的作用就是将中缀表达式变成后缀表达式。 (2) 线性堆栈2的数据结构定义 typedef struct { BiTreeNode *stack [MaxStackSize]; int top; /* 当前栈的表长*/ } TreeStack; 这个堆栈和上面的堆栈的唯一不同就是它们存储的数据的类型不同，此堆栈存储的是树节点，它的作用是将后缀表达式构成一棵二叉树。
(3)树节点数据结构定义 typedef struct Node { DataType data; struct Node *leftChild; struct Node *rightChild; }BiTreeNode; <2>算法设计详细思路如下： 首先实现将中缀表达式变成后缀表达式： 在将中缀表达式变成后缀表达式的时候会用到堆栈，因此首先需要初始化一个堆栈。又由于逻辑变元可能是字符也可能是字符串，所以它又不同于将单字符的逻辑变元的中缀表达式变成后缀表达式。我的设计是这样的，我将中缀表达式变成后缀表达式的过程分成了两部：化简（将一维的复杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元存放在二维数组中），转化（将化简后的中缀表达式变成后缀表达式）。 （1）化简：先用一个字符数组存放输入的中缀表达式（表达式以‘#’号结束），然后将一维的中缀表达式中的字符串逻辑变元用一个字符进行标识，这样我们就可以将原来复杂的中缀表达式变成熟悉而又简单的中缀表达式，同时用二维数组存放那些字符串逻辑变元。实现的过程就是首先扫描一维中缀表达式，如果遇到逻辑符号，那么记住这个逻辑符号在数组中的相对位置用一个变量存放，然后继续扫描中缀表达式直到再次遇到逻辑符号，再一次记住它在中缀表达式中的相对位置，这两个逻辑符号之间的部分就是一个完整的逻辑变元，将这个字符串逻辑变元用一个字符代替并将这个字符串逻辑变元保存在二维数组中。这个过程的实现我把它放在change()函数中。 （2）转化：在实现该功能时，首先需要定义各符号的优先级，即：'(' 和 ')' 的优先级最高；'!'（逻辑非号）的优先级次之；'&'（逻辑与号）的优先级又低一级，'|'（逻辑或号）的优先级跟低；'#' （他不是逻辑符号，只是为了方便使用堆栈而设置）的优先级最低，接着将 '#'压入堆栈。在这之后就是正式的转化了，其过程为：当读到的是逻辑变元时直接输出，并保存到保存后缀表达式的数组中，当读到的单词为运算符时，令x1为当前栈顶运算符的变量，x2为当前扫描到的简单中缀表达式的运算符的变量，把当前读入的单词赋予变量x2，然后比较x1和x2的优先级。若x1的优先级高于x2的优先级，将x1退栈作为后缀表达式的一个单词输出，然后接着比较新的栈顶运算符x1的优先级与x2的优先级；若x1的优先级低于x2的优先级，将x2的值进栈，然后接着读下一个单词；若x1的优先级等于x2的优先级且x1为“（”，x2为“）”，将x1退栈，然后接着读下一个单词；若x1的优先级等于x2的优先级且x1为“#”，x2为“#”，算法结束。这个过程我把它放在InToPost()函数中。 然后用后缀表达式构造出二叉树： 在这个过程中，我用到了之前所定义的存放树的堆栈。具体实现为：扫描后缀表达式，如果遇到逻辑变元然后将这个变元变成一个树节点，它的实现就是将该逻辑变元赋给树的data域，然后将它的左右子树赋为NULL，然后将这个树节点压入相应的堆栈；接着继续扫描，如果遇到的是单目运算符（非号“！”）也将它构造成一个树节点然后从堆栈里面弹出一个树形节点，将弹出的元素的作为它的左子树，右子树设置为NULL，然后将这个树节点压入相应的堆栈；如果扫描到的是双目运算符（与号“&”或者或号“|”）将它也构造成一棵树，然后将这个树节点压入相应的堆栈，然后从栈中弹出两个元素，一个作为它的左子树，一个作为它的右子树，如此重复n（n为后缀表达式的长度）次。这个过程我把它放在
ljlj 逻 辑 学 论 文 数学科学学院 09级3班 吴洁琼 学号2009040288
命题逻辑中几种常见的推理证明方法 吴洁琼 哈尔滨师范大学 （黑龙江·哈尔滨 150025） 【摘 要】：命题逻辑的推理证明是《离散数学》课程的重点难点内容，其主要原因有两个： 一是内容比较抽象且方法较独特，其灵活性很大, 故很难掌握；二是题型以证明题居多, 大多数题的知识面涉及较广, 故习题较难。而命题逻辑又是数理逻辑的基础, 熟练而灵活地掌握好命题逻辑中推理证明的方法既是学习命题逻辑的重点, 又会为进一步学习谓词逻辑打下良好的基础。本文结合适当的例题讲解，总结了命题逻辑中几种常见的推理证明方法，并进行了分析和探讨,以加深学生的理解，以及知识的灵活使用。 以期在帮助学生掌握命题逻辑的推理证明方法的同时, 又能对学生进行逻辑思维能力的训练,培养学生分析问题和解决问题的能力。 【关键词】：命题逻辑；推理；证明方法 数理逻辑是《离散数学》课程的主要内容之一，它主要包括命题逻辑和谓词逻辑两大部分, 而命题逻辑又是谓词逻辑的基础,其中的内容也比较抽象，所以学好命题逻辑又是学好数理逻辑的关键。学好数理逻辑既能加强学生的逻辑思维能力，又同时能够帮助同学学习数字电路和人工智能等其它课程。数理逻辑中关于命题逻辑证明题比较多，学好数理逻辑的关键是能不能很好的掌握这些证明题。 一、命题逻辑中推理的相关概念 定义1：一个命题公式序列1α，2α， ，n α；β，即βααα→ΛΛΛ)(21n 称为推理形式，其中序列最后一项β称为推理的结论，1α，2α， ，n α称为推理的条件。 定义2：对于命题公式序列1α，2α， ，n α；β的命题变元组);,,,(21p p p p n 的任意指派);,,,(21t t t t n 存在使n αααΛΛΛ 21为真，而β为假，则称此推理为无效推理，否则是有效推理。 证明命题公式β为有效结论的过程就是命题逻辑推理证明的过程。而证明推理形式1α， 2α， ，n α；β是有效的充要条件是βααα→ΛΛΛ)(21n 为重言式。 二、常见证明方法 命题逻辑的推理证明有六种常用证明方法，分别是直接证明法，真值表法,范式法，间接证明法。其中间接证明法里面常见的是CP 规则证明法和反证法，本文就这几种方法进行论述。
、必然性推理 概念间关系 直言命题的对当关系 直言命题的变形推理 三段论推理 联言命题与选言命题 假言命题 模态命题 智力推理 ? 概念间关系（概念，是构成命题与推理的基础，只有表达了一类事物的词语才是概念） 直言命题（简单命题），是断定对象是否具有某种性质的单句 ? 直言命题的对当关系（不同直言命题之间在真假方面所存在的制约关系） 所有 A 是 B 反对 ........... 所有 A 不是 B 推出 推出 有的 A 是 B. “所有A 是B ” 与“有的A 不是B ”、“.所有A 不是B ”与“有的A 是 B ”必有一真一假 “所有A 是B ”与“.所有A 不是 B ” 必有一假（可以同假） “有的 A 不是B ”与“有的 A 是 B ” 必有一真（可以同真） 一个命题前面+“并非”=这个命题的矛盾命题 所有与有的互换，有“不”的去掉，没“不”的加上 ? 直言命题的变形推理（通过改变前提中直言命题的联项或主项与谓项的关系 结论） ①换质推理 双重否定表示肯定 将“不是”改为“是”或将“是”改为“不是” ②换位推理（倒过来说） 所有A 是B 有些B 是 A 所有 A 不是 B 所有 B 不是 A 有些 A 是 B 有些 B 是 A 有些 A 不是 B 特殊词量（少数，大部分，一半）作为量项引导命题，不能换位 ? 三段论推理（两个直言命题作为前提/ 一个直言命题作为结论） （两个前提包含三个概念/ 前提和结论中，每个概念都出现两次） 两条常用规则 一特得特：两个前提不能都是特称命题（含有“有的”命题） 只有一个前提是特称，结论也是特称 一否得否：两个前反对 矛盾 . 有的A 不是 B 下反对
1 . 设A 与B 均为含n 个命题变项的公式, 判断下列命题是否为真？ （1）A B 当且仅当 A B 是可满足式. 该命题为真 该命题为假 （2）A B 当且仅当 A 与B 有相同的主析取范式. 该命题为真 该命题为假 （3）若A 为重言式, 则A 的主析取范式中含有2n 个极小项. 该命题为真 该命题为假 （4）若A 为矛盾式, 则A 的主析取范式为1. 该命题为真 该命题为假 （5）若A 为矛盾式, 则A 的主合取范式为1. 该命题为真 该命题为假 （6）任何公式A 都能等值地化为联结词集{∧、∨} 中的公式. 该命题为真 该命题为假 （7）任何公式A 都能等值地化为联结词集{┐、→、∧}中的公式. 该命题为真 该命题为假 2. 用等值演算法来判断下列公式的类型. （1）(p→q)→(┐q→┐p) （2）┐(p→q)∧r∧q （3）(p→q)∧┐p 3. 用主析取范式法判断题2中3个公式的类型, 并求公式的成真赋值. 题2中三个公式如下： （1）(p→q)→(┐q→┐p) （2）┐(p→q)∧r∧q （3）(p→q)∧┐p 4求题2中3个公式的主合取范式, 并求公式的成假赋值.
. 题2中三个公式如下： （1）(p→q)→(┐q→┐p) （2）┐(p→q)∧r∧q （3）(p→q)∧┐p 5 . 已知命题公式A中含3个命题变项p, q, r, 并知道它的成真赋值分别为001, 010, 111, 求A 的主析取范式和主合取范式. 6. 用等值演算法证明下面等值式. （1） (┐p∨q)∧(p→r)p→(q∧r) （2）(p∧q)∨┐(┐p∨q)p 7 . 求公式(p→┐q)∧r在以下各联结词完备集中与之等值的一个公式： （1）{┐,∧, ∨} （2）{┐,∧} （3）{┐,∨} （4）{┐, →} （5）{↑} 8 . 用等值演算法求解下面问题. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件： （1）若赵去, 则钱也去 （2）李、周中至少去一人 （3）钱、孙中去且仅去一人 （4）孙、李两人都去或都不去 （5）若周去, 则赵、钱也同去 问该公司应选派哪些人出国？ 例题分析
自考离散数学命题演算笔记 本章的重点是命题概念及其表示、命题公式化简、主范式及其互化、P规则、T规则以及CP规则。难点是推理理论及应用。 一、命题概念(领会) 学习本章首先要深刻理解命题的概念。理解原子命题与复合命题的关系，在了解复合命题的基础上，理解联结词的定义。 命题：具有唯一真值的陈述句称为命题，又简称语句。注意，这里有两个条件，首先它是一个陈述句，其次，它具有唯一的一个真值。 真值：就是语句为真或假的性质。一个语句的真值可以为真也可以为假。真值不是说该语句的值必为真。 任一命题必有其真值，也称这个命题的值。既然是命题了，那它必有一个确定的真值，不管这个真值为真还是为假。当一个陈述句能够分辩其值的真假时(也就是说，总可以肯定是其中的某一个)，它就是命题，即使我们不知道它是真还是假。 另外要理解命题常量、命题变元及指派的含义。 复合命题就是一些原子命题经过一些联结词复合而成的命题。常用的联结词有：(1)否定、(2)合取、(3)析取、(4)条件、(5)双条件 复合命题与联系词是密切相关的，不包含联结词的命题就是原子命题，至少包含一个联结词的命题才是复合命题。 复合命题的真值只取决于构成它们的各原子命题的真值，而与它们的内容含义无关。对联结词所联结的两原子命题之间有无关系无关。(这一条很重要，因为一个命题用自然语言表达时，我们往往会受到自然逻辑的影响，比如"我如果不上班，那么天下雨"这种命题，在自然的逻辑里，是不成立的，一个人不上班怎么会导致天下雨呢? 但是在这里，这个复合命题的值实际上是由两个原子命题的真值决定的，与它的含义无关，这个复合命题是|P->Q ,前一个原子命题的真值为假，后一命题值为真，根据条件的定义，这个复合命题值为真)
第1章逻辑代数（上）：命题演算 1.1 逻辑联结词与命题公式 1.1.1 逻辑联结词 否定词(negation)“并非”(not)，用符号?（或~）表示。设p表示一命题，那么?p表示命题p的否定。当p真时?p假，而当p假时?p真。?p读作“并非p”或“非p”。用类似表1.1的真值表(truth table)规定联结词的意义。 表1.1 p ?p 1 1 0 合取词(c onjunction)“并且”(and)，用符号∧表示。设p，q表示两命题，那么p∧q 表示合取p和q所得的命题，即当p和q同时为真时p∧q真，否则p∧q为假。p∧q读作“p并且q”或“p且q”。合取词∧的意义和命题p∧q的真值状况可由表1.2来刻划。 表1.2 p q p∧q 0 0 1 1 0 1 1 1 析取词(disjunction)“或”(or)用符号∨表示。设p，q表示两命题，那么p∨q表示p和q的析取，即当p和q有一为真时，p∨q为真，只有当p和q均假时p∨q为假。p∨q 读作“p或者q”，“p或q”。析取词∨的意义及复合命题p∨q的真值状况由表1.3描述。 表1.3 p q p∨q 0 0 1 1 0 1 1 1 1 1 蕴涵词(implication)“如果……，那么……”(if…then…)，用符号→表示。设p，q 表示两命题，那么p→q表示命题“如果p，那么q”，它常被称作条件命题。当p真而q
假时，命题p→q为假，否则均认为p→q为真。p→q中的p称为蕴涵前件，q称为蕴涵后件。p→q的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p 的必要条件”，“q当p”，“p仅当q”等等。数学中还常把q→p，?p→?q，?q→?p分别叫做p→q的逆命题，否命题，逆否命题。蕴涵词→的意义及复合命题p→q的真值状况规定见表1.4。 表1.4 p q p→q 0 0 1 1 0 1 1 1 1 1 双向蕴涵词(two-way implication)“当且仅当”（if and only if），用符号?表示之。设p，q为两命题，那么p?q表示命题“p当且仅当q”，“p与q等价”，即当p与q 同真值时p?q为真，否则为假。p?q读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。由于“当且仅当”“等价”常在其它地方使用，因而用第一种读法更好些。双向蕴涵词的意义及p?q的真值状况由表1.5给出。 表1.5 p q p?q 0 0 1 1 0 1 1 1 1 1.1.2 命题公式 定义1.1 归纳定义命题公式（简称公式proposition formula）： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么(?A)，(A∧B)，(A∨B)，(A→B)，(A?B)也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。 定义1.2设公式A含有命题变元p1，p2，…，p n（有时用A(p1，p2，…，p n)表示这一状况），称p1，p2，…，p n每一取值状况为一个指派(assignments)，用希腊字母α，β等表示，
逻辑命题与推理 必然性推理（演绎推理）：对当关系推理、三段论、复合命题推理、关系推理和模态推理 可能性推理：归纳推理（枚举归纳、科学归纳）、类比推理 命题 直言命题的种类：（AEIOae） ⑴全称肯定命题：所有S是P（SAP） ⑵全称否定命题：所有S不是P（SEP） ⑶特称肯定命题：有的S是P（SIP） ⑷特称否定命题：有的S不是P（SOP） ⑸单称肯定命题：某个S是P（SaP） ⑹单称否定命题：某个S不是P（SeP） 直言命题间的真假对当关系： 矛盾关系、（上）反对关系、（下）反对关系、从属关系 矛盾关系：具有矛盾关系的两个命题之间不能同真同假。主要有三组： SAP与SOP之间。“所有同学考试都及格了”与“有些同学考试不及格” SEP与SIP之间。“所有同学考试不及格”与“有些同学考试及格” SaP与SeP之间。“张三考试及格”与“张三考试不及格” 上反对关系：具有上反对关系的两个命题不能同真（必有一假），但是可以同假。即要么一个是假的，要么都是假的。存在于SAP与SEP、SAP与SeP、SEP与SaP之间。 下反对关系：具有下反对关系的两个命题不能同假（必有一真），但是可以同真。即要么一个是真的，要么两个都是真的。存在于SIP与SOP、SeP与SIP、SaP与SOP之间。 从属关系（可推出关系）：存在于SAP与SIP、SEP与SOP、SAP与SaP、SEP与SeP、SaP与SIP、SeP与SOP 六种直言命题之间存在的对当关系可以用一个六角图形来表示，“逻辑方阵图” SAP SEP SaP SeP
SIP SOP 直言命题的真假包含关系 全同关系、真包含于关系、真包含关系、交叉关系、全异关系 复合命题：负命题、联言命题、选言命题、假言命题 负命题的一般公式：并非P 联言命题公式：p并且q “并且、…和…、既…又…、不但…而且、虽然…但是…” 选言命题：相容的选言命题、不相容的选言命题 相容的选言命题公式：p或者q“或、或者…或者…、也许…也许…、可能…可能…” 【一个相容的选言命题是真的，只有一个选言支是真的即可。只有当全部选言支都假时，相容的选言命题才是假的】不相容选言命题公式：要么p要么q “要么…要么…、不是…就是…、或者…或者…二者必居其一、或者…或者…二者不可兼得” 【一个不相容的选言命题是真的，有且只有一个选言支是真的。当选言支全真或全假时，此命题为假】 假言命题：充分条件假言命题、必要条件假言命题、充要条件假言命题 充分条件假言命题公式：如果p，那么q“如果…就…、有…就有…、倘若…就…、哪里有…哪里有…、一旦…就…、假若…、只要…就…” 【有前件必然有后件。如果有前件却没有后件，这个充分条件假言命题就是假的。因此，对于一个充分条件的假言命题来说，只有当其前件真而后件假时，命题才假。】 必要条件假言命题公式：只有p，才q “没有…就没有…、不…不…、除非…不…、除非…才…” 【没有前件必然没有后件。如果没有前件也有后件，这个必要假言命题为假。对于一个必要条件的假言命题来说，只有当其前件假而后件真时，命题才假。】 充要条件假言命题公式：当且仅当p，才q 【有前件必然有后件，没有前件必然没有后件。充要条件假言命题在前件与后件等值即前件真并且后件真，或者前件假并且后件假时，命题为真，在前件与后件不等值即前真后假，或前假后真时，命题为假】
第五章复合命题及其推理 一、分析下列语句各表达什么复合命题？请写出其逻辑式。 1.书山有路巧为径，学海无涯乐作舟。 答：这是一个二支联言命题，可表示为：p∧q 2．只有发展外向型经济，才能打入国际市场。 答：这是一个必要条件假言命题，可表示为：p←q 3．但凡家庭之事，不是东风压倒西风，就是西风压倒东风。 答：这是一个二支不相容选言命题，可表示为：p q 4．并不是每一个科学家都是上过大学的。 答：这是个负A 命题，它等值一个O 命题：?(SAP) ←→ SOP 5．足球的进攻方式，主要是中路突破，此外或边线进攻，或长传短切，或单刀直入。 答：这是一个四支不相容选言命题：p q r s 6．法律如果并且只有推开特权的大门，才能跨进人民的心。 答：这是一个充分必要条件假言命题：p←→ q 二、下列语句是否表达选言命题？如表达，各表达什么选言命题？请 写出逻辑式。 1．身体不好，或者是由于有病，或者是由于锻炼差，或者是由于营养 不良。 答：表达一个三支相容选言命题：p∨q∨r 2．这堂课是你上，还是我上？ 答：表达一个二支不相容选言命题：p q 3．这次围棋名人赛，要么小林光一取得胜利，要么马晓春取得胜利。答：表达一个二支不相容选言命题：p q 4．雇用的女工大抵非馋即懒，或者馋而且懒。 答：表达一个二支相容选言命题，用p 表示“女工馋”，用q 表示“女 工懒”，其逻辑式为：p∨q，也可理解为三支不相容选言命题：（?p∧q）(p∧?q) (p∧q),二者等值。 三、下列语句是否表达假言命题？如表达，各表达哪种假言命题？请 写出它们的逻辑式。 1．一人抽烟，大家受害。 答：表达一个充分条件假言命题：如果一人抽烟，那么大家受害，p →q 2．人们首先必须吃、喝、住、穿，然后才能从事政治、科学、艺术、 宗教等等。 答：表达一个必要条件假言命题：p←q 3．如果说幼年时期的无知是天真的表现的话，那么，成年以后还满足 于自己的无知就是愚蠢的表现了。 答：这个假设句不表达假言命题，而表达转折联言命题。 4．人不犯我，我不犯人；人若犯我，我必犯人。 答：表达一个充分必要条件假言命题，用p 表示"人犯我"，用q 表示 “我犯人”：p←→q 5．没有共产党，就没有新中国。 答：可有两种理解：一是充分条件假言命题，一是必要条件假言命题。