下载文档原格式
2022年同等学力申硕计算机科学考试全套复习资料2022年同等学力申硕《计算机科学与技术学科综合水平考试》全套资料【考点手册＋真题精选＋题库】内容简介【全套产品】•2022年同等学力申硕《计算机科学与技术学科综合水平考试》考点手册•2022年同等学力申硕《计算机科学与技术学科综合水平考试》题库【真题精选＋专题题库】•试看部分内容第1章离散数学与组合数学【考点1】命题逻辑的等值演算与推理演算1命题逻辑的基本概念、命题逻辑联结词与真值表，重言式（1）命题逻辑的基本概念命题是一个非真即假的陈述句，与事实相符的陈述句为真语句，记为T；与事实不符的陈述句为假语句，记为F。
命题逻辑为二值逻辑。
只由一个主语和一个谓语构成的最简单的陈述句，称为简单命题或原子命题或原始命题。
若干个简单命题通过联结词联结而成的更为复杂的新命题称为复合命题或分子命题。
（2）常用的逻辑联结词常用的逻辑联结词如表1-1所示。
表1-1 常用的逻辑联结词（3）真值表把命题公式A在一切可能的赋值下取得的值列成表，该表称为A的真值表。
（4）重言式（也叫永真式）若命题公式A在任何一个赋值下的值都是真，则A称为重言式或永真式。
（5）矛盾式（也叫永假式）若命题公式A在任何一个赋值下的值都是假，则A称为矛盾式或永假式。
（6）可满足式若命题公式A在至少一个赋值下的值是真，则A称为可满足式。
即当A不是矛盾式时，A为可满足式。
2简单命题的形式化命题逻辑的自然语言形式化的基本过程分为三步：（1）确定子命题，用命题形式p，q，……表示；（2）确定联结词；（3）按照自然语言语义构成复合命题。
3等值定理、基本等值公式以及等值演算（1）等值定义设A和B是命题公式，若A↔B是重言式，则称A和B等值或逻辑等价，记作AóB，Aó称为等值式或逻辑等价式。
（2）基本等值公式一些基本等值式如表1-2所示。
表1-2 基本等值式4命题公式与真值表的关系、联结词的完备集（1）命题公式与真值表的关系含n个变元的命题公式可以视为一个n元真值函数F：{0，1}n→{0，1}。
第一章绪言第一节“逻辑”的含义一、逻辑的词源1. 逻辑一词源出于希腊文的“逻各斯”（logos，复数形式是logoi).·古希腊的哲学家赫拉克利特据说有专论逻各斯的著作《逻各斯》。
·逻各斯的基本词义是言辞、秩序和规律。
言语是这一语词的原创义，然后在此基本词义基础上派生出理性、理想、推理论证等词义.2。
逻各斯演变为“逻辑”一词·最先是由斯多葛学派使用；看作是由论辩术和修辞学两部分构成的理论。
·古罗马和欧洲中世纪的逻辑学家也在这种意义上来看待“逻辑”一词.·其后，逻辑一词的含义就一直和推理与论辩的方法和原则相关。
3。
逻辑一词传入中国·严复开始，“按逻辑此翻名学。
其名义始于希腊,为逻各斯一根之转”.·严复翻译的时间大约在19世纪末;·再过十多年后,由章士钊正式在汉语中定名，作为讨论思维、讨论推理的规范和秩序的学问4. 为什么logic要翻译为逻辑？逻辑学是有点特殊的学科。
特殊在什么地方？学科名的特殊和学科内容的特殊。
中国历史上和逻辑对应的学科?逻辑究竟研究什么?二、什么是逻辑？1. 逻辑是一门和方法、原则、规范紧密相关的人文学科。
她探索和研究的是我们进行推理（reasoning，inference）时应该使用的方法、技巧、标准和原则。
逻辑是一门讲道理的学科. 逻辑总是和语言相关.逻辑总是和论证证明推理相关。
p2 2。
三个方向的推理追寻历史:一个事件出现了，我们寻求其产生的原因，案件、历史、文物等，向后的推导.确定目标：未来可能出现的事件,这是向前的推理。
演绎推理:没有时空条件的推理，数学和逻辑。
几何证明和数学计算。
第二节逻辑历史简述一、古典逻辑1. 古希腊哲学家亚里士多德公认为是逻辑学之父.2。
亚里士多德创立逻辑学科的标志是他所撰写的逻辑专著，这些讨论逻辑问题的专著有《范畴篇》、《解释篇》、《分析前篇》、《分析后篇》、《论辩篇》和《辩谬篇》,这些篇章后来合编为《工具论》一书。
离散数学（1）复习笔记Ch1 命题逻辑的基本概念1.1 命题命题：能判断真假且⾮真即假的陈述句。
命题的真值，真命题，假命题。
* 真值待定 *简单命题 | 原⼦命题，复合命题。
1.2 常⽤的5个命题联结词否定，合取，析取，蕴涵，双蕴涵。
* 异或 | 排斥或 | 不可兼或 * 注意语义判断。
* p→q = ﹁ p∨q ** 必要条件 * 只有……才……；仅当……，……；……，仅当……。
注意命题符号化的蕴涵⽅向。
* domain * A horse is white. （×）联结词集，⼀元联结词，⼆元联结词。
* 优先顺序 * （），﹁，∧，∨，→，↔1.3 合式公式及其赋值命题常项 | 命题常元（值是确定的），命题变项 | 命题变元（真值可以变化的陈述句）。
合式公式 | 命题公式 | 命题形式 | 公式（wff）（well formed formulas），原⼦命题公式（单个命题变项），⼦公式。
* 单个命题变项是合式公式，没说命题常项。
*赋值 | 解释，成真赋值，成假赋值。
真值表。
* 真值表要点：赋值从00…0开始，按照⼆进制加法，直到11…1为⽌；按照运算的优先次序写出各⼦公式。
*命题公式的分类：重⾔式 | 永真式，⽭盾式 | 永假式，可满⾜式。
1.4 重⾔式与代⼊规则代⼊规则。
* 1. 公式中被代换的只能是命题变项（原⼦命题），⽽不能是复合命题。
2.对公式中某命题变项施以代⼊，必须对该公式中出现的所有同⼀命题变项施以相同的代换。
* 1.5 命题形式化命题形式化 | 符号化。
* 注意充分条件和必要条件的区别 ** 注意语义是否考虑完整 *1.6 波兰表达式中置式 | 中缀式，前置式 | 前缀式 | 波兰式，后置式 | 后缀式 | 逆波兰式。
Ch2 命题逻辑的等值和推理演算2.1 等值定理等值 | 等价，等值定理：设A，B为两个命题公式，A = B的充分必要条件是 A↔B为⼀个重⾔式。
形式逻辑的公理系统和形式系统形式逻辑是一种研究逻辑关系的学科，它试图通过使用形式符号和公理系统来建立逻辑推理的准确性和可靠性。
形式逻辑的公理系统是一种形式化的推理系统，它建立了一组公理和规则，用来推导逻辑论断。
一、形式逻辑的公理系统形式逻辑的公理系统是建立在形式符号和逻辑操作上的一种推理系统。
它通过公理和规则来推导逻辑论断，并确保推理的准确性和精确性。
公理是一组基本原理，它们被假定为真实并用来推导其他命题。
规则是推理过程中的操作步骤，用来控制推理的正确性和合法性。
在形式逻辑的公理系统中，通常包括以下几个要素：1. 符号系统：形式逻辑使用符号来表示逻辑关系和论断。
符号系统包括逻辑操作符、量词、谓词、变量等。
2. 公理：公理是形式逻辑公理系统的基础，它们是被假定为真实并用来推导其他命题的基本原理。
公理通常是逻辑推理的基本规则，它们被作为推理的起点。
3. 规则：规则是推理过程中的操作步骤，用来控制推理的正确性和合法性。
规则可以是代换规则、引入规则、消去规则等，它们确保推理过程中逻辑关系的保持和准确性。
二、形式系统形式系统是形式逻辑的一种表达方式，它使用符号和规则来表示逻辑关系和推理过程。
形式系统可以用来描述和分析各种逻辑概念，并进行逻辑推理。
形式系统通常包括以下几个要素：1. 符号集合：符号集合是形式系统中所使用的符号的集合。
它包括逻辑操作符、量词、谓词、变量等。
2. 公式集合：公式集合是形式系统中表示逻辑论断的集合。
公式可以使用符号集合中的符号进行组合，并通过逻辑操作符来表示逻辑关系。
3. 推演规则：推演规则是形式系统中的推理规则，它用来推导公式之间的逻辑关系。
推演规则可以是代换规则、引入规则、消去规则等，它们确保推理过程中逻辑关系的保持和准确性。
形式系统通过使用符号和规则来描述和分析逻辑关系，并进行逻辑推理。
它提供了一种形式化的方法来研究逻辑问题，确保推理的准确性和可靠性。
总结：形式逻辑的公理系统和形式系统是研究逻辑推理的基本工具。
命题逻辑▪(论域)定义：论域是一个数学系统，记为D。
它由三部分组成：•(1)一个非空对象集合S，每个对象也称为个体；•(2) 一个关于D的函数集合F；•(3)一个关于D的关系集合R。
▪（逻辑连接词）定义•设n>0,称为{0,1}n到{0,1}的函数为n元函数，真值函数也称为联结词。
•若n =0，则称为0元函数。
▪（命题合式公式）定义：•(1).常元0和1是合式公式；•(2).命题变元是合式公式；•(3).若Q,R是合式公式，则(⌝Q)、(Q∧R) 、(Q∨R) 、(Q→R) 、(Q↔R) 、(Q⊕R)是合式公式；•(4).只有有限次应用(1)—(3)构成的公式是合式公式。
▪（生成公式）定义1.5 设S是联结词的集合。
由S生成的公式定义如下：•⑴若c是S中的0元联结词，则c是由S生成的公式。
•⑵原子公式是由S生成的公式。
•⑶若n≥1，F是S中的n元联结词，A1,…,A n是由S生成的公式，则FA1…A n 是由S生成的公式。
▪（复杂度）公式A的复杂度表示为FC(A)•常元复杂度为0。
•命题变元复杂度为0，如果P是命题变元，则FC (P)=0。
•如果公式A=⌝B，则FC (A)=FC(B)+1。
•如果公式A=B1∧ B2，或A=B1∨ B2，或A=B1→B2，或A=B1↔ B2，或A=B1⊕ B2，或则FC (A)=max{FC(B1), FC(B2)}+1。
▪命题合式公式语义•论域：研究对象的集合。
•解释：用论域的对象对应变元。
•结构：论域和解释称为结构。
•语义：符号指称的对象。
公式所指称对象。
合式公式的语义是其对应的逻辑真值。
▪（合式公式语义）设S是联结词的集合是{⌝，∧，∨，⊕，→，↔}。
由S生成的合式公式Q在真值赋值v下的真值指派v(Q)定义如下：•⑴v(0)=0, v(1)=1。
•⑵若Q是命题变元p，则v(A)= pv。
•⑶若Q1,Q2是合式公式▪若Q= ⌝Q1，则v(Q)= ⌝v(Q1)▪若Q=Q1 ∧ Q2，则v(Q)=v(Q1)∧ v(Q2)▪若Q=Q1∨Q2，则v(Q)=v(Q1)∨v(Q2)▪若Q=Q1→ Q2，则v(Q)=v(Q1)→ v(Q2)▪若Q=Q1 ↔ Q2，则v(Q)=v(Q1)↔ v(Q2)▪若Q=Q1⊕ Q2，则v(Q)=v(Q1)⊕ v(Q2)▪（真值赋值）由S生成的公式Q在真值赋值v下的真值v(Q)定义如下：•⑴若Q是S中的0元联结词c，则v(Q)=c。
1.1 命题1-1-1 命题命题是一个能表达判断并具有确定真值的陈述句。
1-1-2 真值作为命题的陈述句所表达的判断结果称为命题的真值。
真值只有真和假两种，通常记为T和F。
真值为真的命题称为真命题，真值为假的命题称为假命题。
真命题表达的判断正确，假命题表达的判断错误。
任何命题的真值都是唯一的。
1-1-3 命题变项用命题标识符（大写字母）来表示任意命题时，该命题标识符称为命题变项。
1-1-4 简单命题无法继续分解的简单陈述句称为简单命题或原子命题。
(不包含任何与、或、非一类联结词的命题)1-1-5 复合命题由一个或几个简单命题通过联结词复合所构成的新的命题，称为复合命题，也称分子命题。
1.2 命题联结词及真值表1-2-1 命题联结词命题联结词可将命题联结起来构成复杂的命题，是由已有命题定义新命题的基本方法。
命题联结词又可分为一元命题联结词、二元命题联结词和多元命题联结词。
常用的命题联结词包括否定词、合取词、析取词、蕴涵词和双条件词。
其它联结词还包括异或（不可兼或）、与非和或非等。
1-2-2 否定词否定词是一元命题联结词。
设P为一命题，P的否定是一个新的命题，记作P，读作非P。
若P为T，P为T；若P为F，P为T。
1-2-3 合取词合取词是二元命题联结词。
两个命题P和Q的合取构成一个新的命题，记作P∧Q。
读作P、Q的合取（或读作P与Q，P且Q）。
当且仅当P、Q 同时为T时，P∧Q为T。
否则，P∧Q的真值为F。
1-2-4 析取词析取词是二元命题联结词。
两个命题P和Q的析取构成一个新的命题，记作P∨Q。
读作P、Q的析取（也读作P或Q）。
当且仅当P、Q同时为F 时，P∨Q的真值为F。
否则，P∨Q的真值为T。
1-2-5 蕴涵词蕴涵词是二元命题联结词。
两个命题P和Q用蕴涵词“→”联结起来，构成一个新的命题，记作P→Q。
读作如果P则Q，或读作P蕴涵Q。
当且仅当P 的真值为T，Q的真值为F时，P→Q的真值为F，否则P∨Q的真值为T。
基于 Lukasiewicz计算模型的六值命题逻辑公理体系构建∗林加华;姜华【摘要】虽然经典命题逻辑在理论上已经趋于成熟，它既是可靠的又是完备的，但在现实世界中并不是每个命题均可直接用真与假来判断。
很显然，对未来事件进行判断的命题既不真也不假。
为了改进经典命题逻辑的这种不足，本文在深入研究经典命题逻辑的基础上，以Lukasiewicz计算模型为基础，通过扩展经典命题逻辑的逻辑真值集，并采用扩展后的逻辑真值构成的赋值格对命题进行赋值。
由此本文提出六值命题逻辑系统，记为£s。
系统中否定了经典命题逻辑中的排中律，增加了对命题判断的多样性，增强了它对现实世界的表达能力。
%Although the classical propositional logic in theory has become mature, it is not only relia-ble and complete, but in the real world, not every proposition can be directly used to judge true and false. Obviously , the judgment of future events is neither true nor false proposition. In order to improve the short-comings of classical propositional logic, based on the in -depth study of classical propositional logic, based on the Lukasiewicz model, through the extension of classical propositional logic logic truth value set, and uses the extended logic truth value assignment of proposition in lattice structure assignment. This paper puts forward six valued propositional logic system £ s , system of negation in classical propositional logic law of excluded middle, increase the diversity of the proposition of judgment, it enhances the ability of express-ing the real world.【期刊名称】《楚雄师范学院学报》【年(卷),期】2015(000)006【总页数】6页(P32-37)【关键词】经典命题逻辑;Lukasiewicz计算模型;六值命题逻辑【作者】林加华;姜华【作者单位】楚雄师范学院信息学院，云南楚雄675000;楚雄师范学院信息学院，云南楚雄 675000【正文语种】中文【中图分类】O141由于人们对一个命题“非真即假，非假即真”判定的怀疑，这种怀疑是多值逻辑出现的内因。
