判断以下符号串是不是公式

一． 填空题（每空2分,共20分)1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。

2. 规范规约是最（3）规约。

3。

编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。

另外还有（6)和出错处理。

4．表达式x+y ＊z/(a+b ）的后缀式为 （7） 。

5．文法符号的属性有综合属性和 (8）。

6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15，1。

20]某个元素a ［i ，j ］的地址计算公式为（9)。

7．局部优化是局限于一个（10）范围内的一种优化。

二． 选择题（1-6为单选题,7-8为多选题，每问2分，共20分）1. 一个上下文无关文法G 包括四个组成部分：一组终结符,一组非终结符，一个（ ）,以及一组（ ）。

A ． 字符串B ． 产生式C ． 开始符号D ． 文法 2.程序的基本块是指（ )。

A ． 一个子程序B ． 一个仅有一个入口和一个出口的语句C ． 一个没有嵌套的程序段D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3。

高级语言编译程序常用的语法分析方法中，递归下降分析法属于( )分析方法。

A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析. A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。

A ． 四元式序列B ． 间接三元式序列C ． 二元式序列D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。

A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一7． 如果在文法G 中存在一个句子,当其满足下列条件（ )之一时，则称该文法是二义文法. A ． 其最左推导和最右推导相同 B ． 该句子有两个不同的最左推导C ． 该句子有两个不同的最右推导D ． 该句子有两棵不同的语法树E ． 该句子对应的语法树唯一8． 下面( )语法制导翻译中，采用拉链—回填技术.A. 赋值语句 B 。

《离散数学》复习题一、填空题1、若P ，Q 为二命题，Q P ↔真值为1，当且仅当 。

2、对公式),()),(),((y x xR z x zQ y x yP ∀∨∃∧∀中自由变元进行代入的公式为 。

3、))(()(x xG x xF ∃⌝∧∀的前束范式为 。

4、设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的，则 被称为全称量词消去规则，记为US 。

5、与非门的逻辑网络为 。

6、}0|{>∧∈=+x Z x x Z ，*表示求两数的最小公倍数的运算（Z 表示整数集合），对于*运算的幺元是 ，零元是 。

7、代数系统<A,*>中，|A|>1，如果θ和e 分别为<A,*>的幺元和零元， 则θ和e 的关系为 。

8、设<G,*>是一个群，<G,*>是阿贝尔群的充要条件是 。

9、图的完全关联矩阵为 。

10、一个图是平面图的充要条件是 。

二、选择题1、下列各符号串，不是合式公式的有（ ）。

A 、R Q P ⌝∧∧)(；B 、)()((S R Q P ∧→→；C 、R Q P ∧∨∨；D 、S R Q P ∨∧∨⌝))((。

2、下列语句是命题的有（ ）。

A 、2是素数；B 、x+5 > 6；C 、地球外的星球上也有人；D 、这朵花多好看呀！。

3、下列公式是重言式的有（ ）。

A 、)(Q P ↔⌝；B 、Q Q P →∧)(；C 、P P Q ∧→⌝)(；D 、P Q P ↔→)(4、下列问题成立的有（ ）。

若C B C A ∨⇔∨，则B A ⇔； B 、若C B C A ∧⇔∧，则B A ⇔； C 、若B A ⌝⇔⌝，则B A ⇔； D 、若B A ⇔，则B A ⌝⇔⌝。

5、命题逻辑演绎的CP 规则为（ ）。

A 、在推演过程中可随便使用前提；B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；D 、设)(A Φ是含公式A 的命题公式，A B ⇔，则可用B 替换)(A Φ中的A 。

题号:1 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2设P：天下大雨，Q：他乘公共汽车上班。

命题“只有天下雨，他才乘公共汽车上班”符号化为（）•A、P→Q•B、Q→P•C、P<->Q•D、┑P→Q。

学员答案：b说明：本题得分：2题号:2 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2设P：我将去镇上，Q：我有时间，命题“我将去镇上，仅当我有时间”，符号化为（）•A、P→Q•B、Q→P•C、P<->Q•D、┑P→┑Q。

学员答案：a说明：本题得分：2题号:3 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）•A、P→┑Q•B、P∨┑Q•C、P∧Q•D、P∧┑Q学员答案：d说明：本题得分：2题号:4 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2设P：天下钉子，Q：我去B城。

命题“除非天下钉子，否则我去B城”符号化为（）•A、P→Q•B、Q→P•C、┑P→Q•D、Q→┑P。

学员答案：c说明：本题得分：2题号:5 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2设P：我们划船，Q：我们跳舞，命题“我们不能计划船又跳舞”符号化为（）•A、P∨Q•B、┑（P∧Q）•C、┑P∧┑Q•D、┑P∧Q。

学员答案：b说明：本题得分：2题号:6 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2设A，B为集合，A∩B=A∪B成立的充分必要条件是（）•A、A=B=φ•B、A=φ•C、B=φ•D、A=B学员答案：d说明：本题得分：2题号:7 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2一个公式在等价意义下，下面哪一个写法是唯一的（）•A、析取范式•B、合取范式•C、主析取范式•D、以上答案都不对。

学员答案：c说明：本题得分：2题号:8 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2 设集合A={1，a}，则A的幂集P（A）=（）•A、{{1}，{a}}•B、{φ，{1]，{a}•C、{φ，{1]，{a}，{1，a}•D、{{1]，{a}，{1，a}学员答案：c说明：本题得分：2题号:9 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2 设A=φ，B={φ，{φ}}，则B-A是（）•A、{{φ}}•B、{φ}•C、{φ，{φ}}•D、φ学员答案：c说明：本题得分：2题号:10 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2 下列命题公式是可满足（可真可假）公式的是（）•A、P∧┑P•B、P∨┑P•C、(Q→P)∧(┑P∧Q)•D、（P∧Q）∨（┑P∧R)学员答案：d说明：本题得分：2题号:11 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2 设A={a，b}，则A的幂集P（A）为（）•A、{a，b}•B、{φ，{a}，{b}}•C、{φ，{a}}•D、{φ，{a}，{b}，{a，b}}学员答案：d说明：本题得分：2题号:12 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2 下列命题与B-A为同一集合的是（）•A、(A的补集)∪B•B、(A∪B)∩B•C、B∩(A的补集)•D、((A∩B)的补集)∪B学员答案：c说明：本题得分：2题号:13 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2 下面哪一组命题公式不是等价的（）•A、(P→Q)∧(Q→P)，P<->Q•B、┑(P<->Q),(P∧┑Q)∨(┑P∧Q)•C、P→(Q∨R),┑P∧(Q∨R)•D、P→(Q∨R),(P∧┑Q)→R学员答案：c说明：本题得分：2题号:14 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2 下列命题公式是主析取范式的是（）•A、P∧(P→Q)→Q)•B、P<->Q•C、P∨Q•D、(P∧Q)∨(P∧┑Q)学员答案：d说明：本题得分：2题号:15 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2 下面哪个联接词运算不可交换（）•A、∧•B、→•C、∨•D、<->学员答案：b说明：本题得分：2题号:16 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:2 下列语句，哪一个是真命题（）.•A、我正在说谎•B、如果1+1=0，那么雪是黑的•C、9+5>18•D、存在最大的质数。

离散数学第一章1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。

A1:我是一名大学生.[10]：我是一名大学生。

R：我是一名大学生。

1.2命题联结词1.2.1 否定联结词﹁PP P0 11 01.2.2 合取联结词∧P∧P Q Q0 0 00 1 01 0 01 1 11.2.3 析取联结词∨P∨P Q Q0 0 00 1 11 0 11 1 11.2.4 条件联结词→P Q Q0 0 10 1 11 0 01 1 11.2.5 双条件联结词?P?P Q Q0 0 10 1 01 0 01 1 11.2.6 与非联结词↑P↑P Q Q0 0 10 1 11 0 11 1 0性质：（1）P↑P?﹁（P∧P）?﹁P；（2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。

1.2.7 或非联结词↓P↓P Q Q0 0 10 1 01 0 0性质：（1）P↓P?﹁（P∨Q）?﹁P；（2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q；（3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。

1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。

例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）?（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。

在命题逻辑中，命题是最基本的单位，对简单命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。

因而命题逻辑具有局限性，甚至无法判断一些简单而常见的推理。

考虑下面的推理:凡偶数都能被2整除；6是偶数。

所以，6能被2整除。

这个推理是我们公认的数学推理中的真命题，但是在命题逻辑中却无法判断它的正确性。

因为在命题逻辑中只能将推理中出现的三个简单命题依次符号化为p，q，r，将推理的形式结构符号化为(p∧q)→r由于上式不是重言式，所以不能由它判断推理的正确性。

为了克服命题逻辑的局限性，就应该将简单命题再细分，分析出个体词，谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这就是一阶逻辑所研究的内容。

一阶逻辑也称一阶谓词逻辑或谓词逻辑。

4.1 一阶逻辑的符号化下面直接仿照1.1来对谓词逻辑进行符号化。

个体词，谓词和量词是一阶逻辑命题符号化的三个基本要素。

下面讨论这三个要素。

一、个体词个体词是指所研究对象中可以独立存在的具体的或抽象的客体。

例如，小王，小李，中国，，3等都可以作为个体词。

将表示具体或特定的客体的个体词称作个体常项，一般用小写英文字母a，b，c…表示；而将表示抽象或泛指的个体词称为个体变项，常用x，y，z…表示。

称个体变项的取值范围为个体域(或称论域)。

个体域可以是有穷集合，例如，{1，2，3}，{a，b，c，d}，{a，b，c，…，x，y，z}，…；也可以是无穷集合，例如，自然数集合N={0，1，2，…}，实数集合R={x|x是实数}…。

有一个特殊的个体域，它是由宇宙间一切事物组成的，称它为全总个体域。

本书在论述或推理中如没有指明所采用的个体域，都是使用全总个体域。

二、谓词谓词是用来刻画个体词性质及个体词之间相互关系的词。

考虑下面四个命题(或命题公式):(1)是无理数。

(2)x是有理数。

(3)小王与小李同岁。

(4)x与y具有关系L.在(1)中，是个体常项，“…是无理数”是谓词，记为F，并用F()表示(1)中命题。

如何在Excel中快速辨别两列数据是否一致的四种方法介绍哎呀，今天小智就来给大家普及一下如何在Excel中快速辨别两列数据是否一致的四种方法。

别看这是个小小的技能，但在我们的日常生活和工作中可是大有裨益哦！让我们一起来看看吧！我们来说说第一种方法：使用IF函数。

IF函数是Excel中的一个非常实用的逻辑函数，它可以根据一个条件是否成立来返回两个不同的结果。

比如说，我们想要判断A 列和B列的数据是否相等，就可以在C列输入以下公式：```=IF(A1=B1, "相等", "不相等")```这个公式的意思是：如果A1单元格的数据等于B1单元格的数据，那么C1单元格就显示“相等”，否则显示“不相等”。

这样一来，我们就可以轻松地看出A列和B列的数据是否一致了。

不过，这种方法有一个缺点，就是我们需要逐行输入公式，比较繁琐。

我们来说说第二种方法：使用VLOOKUP函数。

VLOOKUP函数是Excel中的一个查找函数，它可以根据一个关键字在一个区域中查找对应的值。

比如说，我们想要判断A列和B列的数据是否相等，但是A列的数据比B列的数据多一列，这时候我们可以使用VLOOKUP函数来实现。

在C列输入以下公式：```=IF(VLOOKUP(A1, B:B, 1, FALSE) = A1, "相等", "不相等")```这个公式的意思是：在B列中查找A1单元格的数据，然后返回对应的值。

如果这个值等于A1单元格的数据，那么C1单元格就显示“相等”，否则显示“不相等”。

这种方法的优点是操作简便，缺点是需要事先知道数据的范围。

再来说说第三种方法：使用EXACT函数。

EXACT函数是Excel中的一个文本比较函数，它可以比较两个文本字符串是否完全相同。

比如说，我们想要判断A列和B列的数据是否相等，但是这两个列的数据都是以#符号开头的数字，这时候我们可以使用EXACT函数来实现。

一． 填空题（每空2分，共20分）1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。

2. 规范规约是最（3）规约。

3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。

另外还有（6）和出错处理。

4．表达式x+y*z/(a+b)的后缀式为 （7） 。

5．文法符号的属性有综合属性和 （8）。

6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址计算公式为（9）。

7．局部优化是局限于一个（10）范围内的一种优化。

二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分）1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组（ ）。

A ． 字符串B ． 产生式C ． 开始符号D ． 文法 2.程序的基本块是指（ ）。

A ． 一个子程序B ． 一个仅有一个入口和一个出口的语句C ． 一个没有嵌套的程序段D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。

A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。

A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。

A ． 四元式序列B ． 间接三元式序列C ． 二元式序列D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。

A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一7．如果在文法G中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。

离散结构命题公式及真值表教学目标基本要求（1）会判断命题公式及其层次；（2）真值表；（3）公式类型；重点难点真值表的应用。

命题中的符号命题中的符号：(1) 命题常元：真值唯一确定。

例如：T、F(2) 命题变元：真值可变化。

例如：P、Q、R(3) 联接词：优先级按¬, ∧, ∨, →, ↔递减(4) 辅助符号如括号（）。

命题中的符号任意组成的符号串是否都有意义？例：(∧p ¬q) pq →(思考：按什么规律组成的符号串才有意义？合式公式合式公式：合法的命题公式。

（简称公式）（1）命题常元或变元是合式公式（2）若A, B是合式公式，(¬A),(A∧B),(A∨B),(A→B),(A↔B)也是合式公式（3）只有有限次地应用(1)、(2)形成的符号串才是合式公式注意这个定义是递归的。

(1)是递归的基础，由(1)开始，使用规则(2)，可以得到任意的合式公式。

公式简写的约定1) 最外层括号可以省略；2) 省略括号后, 运算顺序与联结词的优先级一致，则可以省略；3) 相同联结词按从左到右的顺序计算，则可以省略。

公式的层次定义：（1）若公式A 是单个的命题变项，则称A 为0层公式。

（3）若公式的层次为k ，则称A 是k 层公式。

（2）若有下面情况之一的，称A 为n+1层公式:A 是¬B ，B ∧C ，B ∨C ，B→C ，B↔C ，其中B 、C 分别是i 层、j 层公式，且n=max(i,j)； 例：((¬p ∧q)∨(p ∧ ¬q))→r1层 2层 3层 4层公式的解释命题公式代表一个命题，但只有当公式中的每一个命题变元都用一个确定的命题代入时，命题公式才有确定值，成为命题。

解释（I）：给公式A（ P1，P2，…,Pn ）中的命题变元P1，P2，…,Pn指定一组真值称为对A的一个解释（赋值）。

成真赋值: 使公式为真的赋值。

成假赋值: 使公式为假的赋值。

用真值表法判断命题公式命题公式是数理逻辑中的基本概念，它是由命题符号和逻辑连接词组成的符号串，用于表示命题之间的逻辑关系。

在数理逻辑中，我们通常使用真值表法来判断命题公式的真假性。

本文将介绍真值表法的基本概念和应用。

一、真值表的定义和构造方法真值表是一种用来表示命题公式真假性的表格。

一般地，真值表的每一行代表了命题符号的一种取值情况，真值表的最后一列代表了整个命题公式的真假情况。

真值表的构造方法可以按照以下步骤进行： 1. 确定命题符号的取值情况，例如，若有命题符号P和Q，则可以分别取真和假两种情况，得到四种可能的取值情况：P=T,Q=T;P=T,Q=F;P=F,Q=T;P=F,Q=F。

2. 根据命题公式中的逻辑连接词，计算出整个命题公式在每种取值情况下的真假情况。

例如，若命题公式为P∨Q，则在第一行的情况下，P∨Q的真假情况为真；在第二行和第三行的情况下，P∨Q的真假情况为真；在第四行的情况下，P∨Q的真假情况为假。

3. 将每种情况下的真假情况填入真值表中，得到完整的真值表。

二、真值表法的应用真值表法可以用来判断命题公式的真假性，以及推导命题公式的逻辑等价式。

下面将分别介绍这两种应用。

1. 判断命题公式的真假性通过真值表法，我们可以得到命题公式在所有可能情况下的真假情况，从而判断命题公式的真假性。

如果在所有情况下，命题公式都为真，则该命题公式为重言式；如果在所有情况下，命题公式都为假，则该命题公式为矛盾式；如果在某些情况下，命题公式为真，而在其他情况下，命题公式为假，则该命题公式为可满足式。

例如，对于命题公式P∨P，可以通过真值表法判断其为重言式，因为在所有情况下，命题公式都为真。

2. 推导命题公式的逻辑等价式通过真值表法，我们还可以推导命题公式的逻辑等价式。

两个命题公式是逻辑等价的，当且仅当它们在所有情况下的真假情况完全相同。

因此，如果两个命题公式在真值表中的真假情况完全相同，则它们是逻辑等价的。