数理逻辑(讲义)

《数理逻辑》教案

许道云

(2011.8)

教材：《面向计算机科学的数理逻辑》(第二版)

(陆钟万著)

出版社：科学出版社

版本：2006年6月第8次印刷

绪言（课程介绍）

什么是逻辑？命题（判断）对象、以及对象间的（推理）关系。

数理逻辑：用数学的方法研究逻辑。

数理逻辑研究分支：模型论、集合论、递归论、证明论。

数理逻辑研究什么？

逻辑推理：当前提为真时，保证结论为真。

逻辑研究这样的可推理关系。即，前提和结论之间的推理关系是否正确。演绎推理---演绎逻辑。

它不同于归纳逻辑。归纳逻辑是从前提出发，使用归纳推理，得到的结论与自身协调，或与前提协调。

数理逻辑属于演绎逻辑范围。只研究推理及可推理关系，不关心前提与结论中各个命题的真假。

例1.前提：所有大于2不被自身整除的自然数为素数。

7不被自身整除。

结论：7不是素数。

例2.前提：所有中学生打网球。

王君不打网球。

结论：王君不是中学生。

命题有内容和形式：内容决定命题的真或假。决定前提和结论之间的可推导关系，是命题逻辑形式。如：

前提：集合S中的所有元素具有R性质。

a不具有R性质。

结论：a不是S中元素。

命题的陈述需要语言。

元语言：描述对象的所用的最基本语言。

如：自然语言（汉语）。

对象语言：描述“对象所用元语言”的语言。

如：形式语言（符号语言）。

自然语言中语言上的相似并不保证逻辑形式上的相同。

例1：X认识Y。（前提）

Y是足球队长。（前提）

X认识足球队长。（结论）

例2：X认识A班某学生。（前提）

A班某学生是足球队长。（前提）

X认识足球队长。（结论）

近代数理逻辑思想：

Leibniz力图建立一种精确的、普适的科学语言作为形式语言。直到1879年，Frege才建立了这样的语言。近代数理逻辑介绍的就是这种形式语言。所以，数理逻辑史从1879年算起。

在数理逻辑中要构造一种符号语言来代替自然语言，这种人工构造的符号语言称为形式语言。

对象的描述和对象间的推理关系全部用形式语言表示。

数理逻辑研究的主要内容：

（1）引入一个形式语言，以表示非结构化对象。并且要求表示公式的语言是递归生成的。（2）引入一套形式化推理规则，基于这些规则进行符号化演算。引入形式证明的一般形式。

(|A

∑-)

（3）引入一套解释系统---语义(映射)函数，赋予形式符号在给定环境下的具体含义。

（4）基于语义模型，引入逻辑推理概念。(|A ∑=)

（5）研究形式推理与逻辑推理之间的关系。

（可靠性和完备性）。

形式推理系统的可靠性：||A A ∑-?∑=。

形式推理系统的完备性：||A A ∑=?∑-。

一般，逻辑中的语言和推理是某类智能推理的抽象，语言解决表示问题(即，数据结构问题)。从某种意义上讲，应该是先有具体实例，想找一种一般描述，这就产生了形式语言和形式推理。实例数据对形式符号给出一种解释(或赋值)。两者之间的映射关系形成一个解释系统。

实例数据与形式符号有解释(或赋值)和被解释(或赋值)之分。

如：a:=0. 可以理解为：将数字0赋给符号a.

也可理解为：a 被解释为0.

其中，a 是抽象的，而0是具体的。

为什么会有各种逻辑？

由逻辑研究内容，我们可以观察下表： 语法

语义 形式语言

(表达方式和能力)

解释系统 语义(映谢)函数 形式推理：|A ∑-

逻辑推理：|A ∑=

可靠性：||A A ∑-?∑=

完备性：||A A ∑-?∑=

在表中，形式语言、解释系统、推理规则是可变的。

(1) 当形式语言的表达能力不够用时，新的语言就会出现。

(2) 不同规则系统的引入，直接关系到形式推理的能力说、有效性、以及单调性等。

(3) 不同的解释系统，给出不同的语义模型。

思考题：

1、逻辑研究的主要内容。

2、为什么会有各种逻辑？

第一章 预备知识

集合：某些对象全体。 集合表述方式：

内涵：元素具有的性质P 。 外延：所含元素的全体。

自然数集合N 上的二元关系 <（作为集合）： （内涵）m

二元关系的性质：自反，对称，等价，……。 集合等势：~||||S T S T ?= 可数无限集：与自然数集等势的集合。 可数集：有限集或可数无限集。||||S N ≤ 定理：（1）可数集的子集仍然可数。

（2）有限个可数集的并仍为可数集。 （3）可数个可数集的并仍为可数集。 自然数集合N 的归纳定义： （1） 0N ∈.

（2）如果n N ∈，则（后继）'n N ∈ 。

（3）N 只含通过（1）（2）有限次使用得到的数。 等价定义：自然数集合N 是满足如下条件的最小集合S （1）0S ∈ 。

（2）如果n S ∈，则（后继）'n S ∈ 。 设R 是一个性质，()R x 表示x 具有性质R 。

定理1（数学归纳法）如果 （1）(0)R 。

（2）对于任意的n N ∈，如果()R n 则 (')R n 。 则对于任意的n N ∈ 有()R n 。

设h,g 为两个N 上的己知函数。递归定义N 上一个函数f 如下： (1) (0)(0)f g =. (2) (')(())f n h f n =.

定理2（递归原理）对于给定的函数g 和h ，能唯一定义N 上一个函数f 满足上述递归条件。 一般集合S 的归纳定义：

(1) 指定一个集合M 。（基元，生成元）

(2) 指定k 个函数12,,.....,k g g g 为生成函数.分别为12,,.....,k n n n 元函数。 归纳生成集合S ：12S :,{,,.....,}k M g g g =<>。 归纳定义. 集合S 是满足如下条件的最小集合T ： （1）M T ? 。

（2）对于每个1i k ≤≤，

如果1, (i)

n x x T ∈，则1(,.....)i

i n g x x T ∈。

设1,,......,k h h h 为k+1个己知基函数：

::(1,2,...,)

i

n i h M S

h S S i k →→=.

递归原理定义S 上的一个函数f:

11():()()

((,.....)):((),.....,())(1,2,...,)i

i

i i n n f x h x x M f g x x h f x f x i k =∈==

定理3（递归原理）对于给定的函数1,,......,k h h h ，能唯一定义S 上一个函数f 满足上述递归条件。

归纳集生成系统：12:,{,,.....,}k S M g g g =<>。 递归函数生成系统：12S:,{,,,.....,}k S h h h h =<

>。

1212S :,{,,.....,};{,,,.....,}k k M g g g h h h h =<>

例：自然数（算术）系统

00N :{0},{};{,,*}.'()1,()0s c x s x x c x =<+>==+=

第二章经典命题逻辑

命题定义：具有明确真假值的（对象）陈述。

简单命题：最小命题。（最简单，不可分解，原子，……）

复杂命题：借助联结词组合后命题小命题。

组合方式：

（1）一元：否定、不、非。

（2）二元：

或；且；如果…,则…；除非；当…,才有…;

仅当…,才有…。等等。

描述缺陷：自然语言。（非通用标准语言）

形式语言：命题语言L P。（通用）

字母表：0，1，p,q,r,……。

?∨∧→?。

运算符：,,,,

真---1；假---0。

命题公式的生成：（归纳定义命题公式集()P

Form L）

（1）（归纳基）：(){,,,......}()

P P

Atom L p q r Form L

=?。

（原子命题公式集）

（2）（归纳定义）：如果,()P

A B Form L

∈，则

∈∨∧→?。

?∈。其中，*{,,,}

A A

B Form L

,(*)()P

（3）()P

Form L只含通过有限次使用（1）（2）得到的符号串。

结构归纳法：将()P

Form L类比自然数集N。

设P为一个性质，()

P x对表示x具有性质P。

类似于数学归纳法，引入关于()P

Form L上的某个性质（结论）P是否成立（真）的结构归

纳法。

（1）（归纳基） P 关于原子命题公式成立。（归纳基）

（2）（归纳步） 对,()P A B Form L ∈，假定P 关于命题公式A 、B 成立。验证：P 关于命题公式,(*)A A B ?成立。其中，*{,,,}∈∨∧→?。 语义解释：命题公式的解释(赋值)。

对原子命题公式的解释：（形式上是一个映射）

:(){0,1}P v Atom L →。称为一个赋值。

理解为：

p 在v 下被解释为{0,1}v p ∈。()v p v p =

0表示“假”。1表示“真”。

基于这样的解释系统，命题逻辑只研究具有明确真、假区分的对象。这就是命题限制到具有明确真、假意义的陈述语句的根本原因。 对联结词运算符号的解释：

对命题公式的解释：

对于一个公式A ，在一个赋值v 下总可以计算出它的真值：{0,1}v A ∈。（归纳计算）

(1){0,1}.

10(2)().0100(3)().1

..v v v

v v v v p if p p if p if A B A B o w ∈?=?=?=??==∨=?? 11(4)().0

..010(5)().1

..1(6)().0

..v v v v v v v v

v if A B A B o w if A and B A B o w if A B A B o w ?==∧=???==→=???=?=?? 命题公式A 的真值表：在所有可能的赋值v 下，将取值结果列入表中。

如： (┐p ∧q)→┐r 的真值表

可满足性：公式A 是可满足，如果至少存在一个赋值v 使A 取真。

如果公式A 含有n 个变元，验证公式A 的可满足性需要对2n

个赋值逐一验证。直观上需要指数验证时间。

可满足性判定问题（SAT 问题）：

实例：一个命题公式A 。

询问：是否存在一个赋值v 使A 取真（满足A ）？

验证算法存在！

重言式：A 每一个赋值下取值均为真。

矛盾式：A 每一个赋值下取值均为假。

SAT 问题的在计算机科学中的地位：

SAT 问题是计算机科学中的核心问题。曾被著名美籍华人数理逻辑学家王浩称为“当代数理逻辑和理论计算机的第一问题”。

计算机科学家们一直都在寻求各种快速策略和方法改进求解SAT 问题。现已证明：工程技术、军事、人工智能、并发控制、交通运输等领域中的诸多重要问题（如程控电话的自动交换，大型数据库的维护，大规模集成电路的自动布线，软件自动开发，机器人动作规划等）都涉及到SAT 问题。

SAT 问题是NP 完全问题。从理论上说，SAT 问题不能在多项式时间内解决，直观上它超出了现代计算机的能力。所以，SAT 问题是计算机科学技术发展中的“瓶颈”问题。

从理论上讲，可满足性判定问题是NP 完全的，然而在实际应用中，并非每一个CNF 公式的可满足性问题的判定都需要指数时间。根据统计分析，对于3-CNF 公式而言，出现在公式中的子句数与变元数之比是一个重要的参数，当公式的这个参数在4.25附近时，公式的可满足性的判定的确难。但是，当公式的这个参数远离4.25时，公式的可满足性的判定有可能在多项式时间内就可以完成。

约束满足性问题（CSP 问题）：W q CSP -

n 个变元：1,......,n u u 。

m 个q 元函数：1(,......,):{0,1}q q i i i u u W ?→。

可满足性：11((,......,))()[(,......,)1]q n v n i i i v a a W i a a ??=∈?=。

（CSP 问题）：W q CSP -

实例：一个约束1{,......,}m ???=。

询问：是否存在一个赋值1(,......,)n n a a W ∈使得1()[(,......,)1]q

v i i i i a a ??=？ （回到命题公式讨论）

重言式一定是可满足式，但反之不真。因而，若公式A 是可满足式，且它至少存在一个成假赋值，则称A 为非重言式的可满足式。

(1) 若真值表最后一列全为1，则公式为重言式。

(2) 若真值表最后一列全为0，则公式为矛盾式。

(3) 若真值表最后一列中至少有一个1，则公式为可满足式。

（逻辑）语义等价：若A,B 构成的等价式A B ?为重言式，则称A 与B 是等值的，或语义等价。记作A B ?。

用真值表判断公式的等值（在所有赋值下验证）

例： ()()p q p q ?∨??∧?

（逻辑）语义蕴含：若公式A B →为重言式，则称A 蕴含B 。记作A B ?。表示：若A 为真命题，则B 为真命题。

逻辑的主要任务是研究逻辑推理。

命题公式的规范表示：

合取范式： CNF 公式。

析取范式： DNF 公式。

文字：变元或变元的否定统称为文字。,x x ?

子句：文字的析取称为子句。12......n C L L L =∨∨∨。

子句C 中所含文字的个数n 称为子句长度。

CNF 公式：子句的合取称为CNF 公式。12......m F C C C =∧∧∧。

公式F 的(大小)规模定义为。12|||||......||m F C C C =+++。

k-CNF 公式: 公式F 中每个子句的长度k ≤。

Horn 子句：出现在12......n C L L L =∨∨∨中的正文字个数至多为1。

DNF 公式：

(1) 项：文字的合取称为项。12......n C L L L =∧∧∧。

(2) DNF 公式：项的析取称为DNF 公式。

定理.设F 为一个命题公式，则存在公式F1和F2， 使得1F F ?， 2F F ?. 其中，1F 为CNF 公式，2F 为DNF 公式。

范式的唯一性——主范式

p,q 形成的极小项与极大项

p,q,r形成的极小项与极大项

联结词的完备集: 能表示任意布尔函数的联结词集合。

设S是一个联结词集合，如果任何n(n≥1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。

定理. S={┐,∧,∨}是联结词完备集。

?∨∧?∨?∧。

例：{,,},{,},{,}

所有2元真值函数

逻辑推理：|A ∑=

设()P A Form L ∈，()P Form L ∑?。若对于任一赋值v, 如果1v ∑=，则1v A =， 称由∑逻辑可推A 。记为： |A ∑=。

若|A B =且|B A =，称A 与B 逻辑等价。记为：||A B =。

注意：若∑不可满足，则对任意的A ，均有|A ∑=。

证明方法：证|A ∑=。

证明：假定任意赋值v, 使得1v

∑=，验证1v A =。 反证法： 假定|A ∑≠，由存在一个赋值v, 使得1v ∑=，但0v

A =。然后导出矛盾。

定理1.(1) 112,......,|(......)|n n A A A A A A A =?∧∧∧=

(2) 112,......,||(((......()......)n n A A A A A A A =?=→→→

定理2. (等值替换定理)

设F 为一个命题公式，A 是出现在F 中的一个子公式，||A B =。'F 是将B 替换F 中的部份A 得到的公式，则 ||'F F =。

语义证明方法

一、王浩算法

原理：将1,......,|n A A B =的证明转换为证明1(......)n A A B ∧∧→为重言式。 子句格式：

()()()()()a b c d e a b c d e d e a b c ∨∨∨?∨?∨∨∨?∧∧→∨∨

串格式：,,,s d e a b c →

重言子句的串格式：,,,s d a a b c →，对应a b c d a ∨∨∨?∨?

公理格式：,,A A αβ?。

前项规则：

后项规则：

证明形式：

以一个起始串为树根，按规则消去联结词。当串为公理形式时，不再往下做。如果证明树的每个叶结点均为公理形式，则原公式为重言式（或矛盾式）。

证F 为重言式：起始串为 F ?

要证： 1,......,|n A A B =。

即证： 1:(......)n F A A B =∧∧→为重言式。

证明起始串取为： 1,......,n A A B ?。

例：证明(),|A B C A B A C →→→=→

（1）(),A B C A B A C →→→?→

（2）（1-1）(),,A B C A B A C →→→?

（3）（2-1）(),,A B C A C A →→? (公理)

（4）（2-2）(),,A B C A B C →→?（待分解）

（5）（4-1）,,A B C A ? (公理)

（6）（4-2）,,()A B B C C →?(待分解)

（7）（6-1）,,A B C B ?(公理)

（8）（6-2）,,A B C C ?(公理)

二、表方法

原理： 将1,......,|n A A B =的证明转换为证明1[(......)]n A A B ∧∧→为重言式。 标记公式：.F α（指：公式α取假）

.T α（指：公式α取真）

根结点：1.[(......)]n F A A B ∧∧→

指：假定公式1[(......)]n A A B ∧∧→取假。

分解规则：（逐步取消联结词。如果己出现矛盾路径，则不再分解） (),

,

A

B C A C A →→? (),A B C A B A C →→→?→

(),,A B C A B A C

→→?(),,A B C A B C →→?

,,A B A C ? ,,()A B B C C →?

,,A B C B ? ,,A B C C ?

.F β .T α? .F α .F α? .T α .T αβ∧ .T α .F αβ∧ .F α .T β

.F β .F αβ∨ .F α .T αβ∨ .T α .T β

最经典最简约的面向计算机科学的数理逻辑复习笔记

该笔记适用于任何版本的数理逻辑！ 绪论 一、数理逻辑研究什么？ ★研究前提和结论的可推导性关系，它是由命题的逻辑形式而非内容所决定的 二、数理逻辑如何研究？ ★形式语言 第一章预备知识 第一节集合 一、集合 1、集合的内涵和外延（所有元素的共同性质/构成集合的所有元素） 2、有序偶和笛卡儿集 二、关系 1、概念：集合S上的n元关系R 2、特殊情况：集合S上的一元关系R（集合S上的性质R） 三、函数（映射） 1、概念：函数（集合＋有序偶＋性质）、定义域dom（f）、值域ran（f） 2、概念：f（x）（函数f在x处的值） 3、概念：f：S－>T（函数f是由S到T的映射）、满射、一一映射 四、等价 1、概念：关系R是集合S上的等价关系（自反＋对称＋传递） 2、概念：元素x的R等价类 3、性质：R等价类对集合S的一个划分（两两不相交，且并为S） 五、基数 1、概念：S～T（两个集合S和T是等势的） 2、概念：集合S的基数|S|（集合中的元素个数） 3、概念：可数无限集

第二节归纳定义和归纳证明 一、归纳定义 1、集合的归纳定义 ⑴、直接生成某些元素 ⑵、给出运算，将其作用在已有元素上，以产生新的元素 ⑶、只有这样才是集合中的元素，除此之外，再也没有了 2、典例：自然数集N的两个归纳定义 二、归纳证明 1、归纳定理：设R是一个性质，如果 ⑴、R（0） ⑵、对于任何n∈N，如果R（n），则R（n’） 那么，对于任何n∈N，都有R（n） 2、概念：归纳基础、归纳步骤（包括归纳变元和归纳假设）、归纳命题、归纳证明 3、概念：串值归纳法及其变形 三、递归定义 1、递归定义（在归纳定义的集合上，定义函数） 在自然数集N上定义一个这样的函数f：g，h是N上的已知函数 f（0）＝g（0） f（n’）＝h（f（n）） 2、递归定义原理（这样的函数是存在而且唯一的）

数理逻辑复习题

一、选择题 1、永真式的否定是（2） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 2、设P ：2×2=5，Q ：雪是黑的，R ：2×4=8，S ：太阳从东方升起，则下列真命题为(1) (1)R Q P ∧→ (2)S P R ∧→ (3)R Q S ∧→ (4) )()(S Q R P ∧∨∧。 3、设P ：我听课，Q ：我看小说，则命题R “我不能一边听课，一边看小说”的符号化为⑵ ⑴ P Q → ⑵Q P ?→(3) Q P →? ⑷ P Q ?→?()P Q ?∧ 提示：()R P Q P Q ??∧?→? 4、下列表达式错误的有⑷ ⑴()P P Q P ∨∧? ⑵()P P Q P ∧∨? ⑶()P P Q P Q ∨?∧?∨ ⑷()P P Q P Q ∧?∨?∨ 5、下列表达式正确的有⑷ ⑴ P P Q ?∧ ⑵ P Q P ?∨ ⑶ ()Q P Q ???→⑷Q Q P ??→?)( 6、下列联接词运算不可交换的是(3) ⑴∧ ⑵∨ (3)→ ⑷ ? 6、设D ：全总个体域，F （x ）：x 是花，M(x) ：x 是人，H(x,y)：x 喜欢y ，则命题“有的人喜欢所有的花”的逻辑符号化为⑷ ⑴(()(()(,))x M x y F y H x y ?∧?→ ⑵(()(()(,))x M x y F y H x y ?∧?→ (3) (()(()(,))x M x y F y H x y ?∧?→ ⑷(()(()(,))x M x y F y H x y ?∧?→ 7、设L(x)：x 是演员，J(x)：x 是老师，A(x , y)：x 钦佩y ，命题“所有演员都钦佩某些 老 师”的逻辑符号化为⑵ ⑴)),()((y x A x L x →? ⑵))),()(()((y x A y J y x L x ∧?→? (3) )),()()((y x A y J x L y x ∧∧?? ⑷)),()()((y x A y J x L y x →∧?? 8、谓词公式)())()((x Q y yR x P x →?∨?中的 x 是⑶ ⑴自由变元 ⑵约束变元 ⑶既是自由变元又是约束变元 ⑷既不是自由变元又不是约束变元 9、下列表达式错误的有⑴ ⑴(()())()()x A x B x xA x xB x ?∨??∨? ⑵(()())()()x A x B x xA x xB x ?∧??∧? (3) (()())()()x A x B x xA x xB x ?∧??∧? ⑷(()())()()x A x B x xA x xB x ?∨??∨?

数学史选择题集锦知识分享

数学史选择题集锦

1、首先获得四次方程一般解法的数学家是( D )。 A. 塔塔利亚 B. 卡尔丹 C. 费罗 D.费拉里 2、最先建立“非欧几何”理论的数学家是( B )。 A. 高斯 B. 罗巴契夫斯基 C. 波约 D. 黎曼 3、提出“集合论悖论”的数学家是( B )。 A.康托尔 B.罗素 C.庞加莱 D.希尔伯特 4、( 泰勒斯 )在数学方面的贡献是开始了命题的证明，被称为人类历史上第一 位数学家 A. 阿基米德 B. 欧几里得 C. 泰勒斯 D. 庞加莱 5、数学史上最后一个数学通才是( B ) A、熊庆来 B、庞加莱 C、牛顿 D、欧拉 7、当今数学包括了约 A 多个二级学科。 A、400 B、500 C、600 D、700。 1、秦九韶是“宋元四大家”之一，其代表作是（）。 （A）九章算术（B）九章算术注（C）数书九章（D）四元玉鉴 2、下面哪位数学家最早得到了正确的球的体积公式（）。 （A）欧几里得（B）祖冲之（C）刘徽 （D）阿基米德 3、古代几何知识来源于实践，在不同的地区，不同的几何学的实践来源不尽相同，古代埃及的几何学产生于

（A）测地（B）宗教（C）天文 （D）航海 4、“零号”的发明是对世界文明的杰出贡献，它是由下列国家发明的（）。 （A）中国（B）阿拉伯（C）巴比伦（D）印度 5、最早发现圆锥曲线的是下列哪位数学家（）。 （A）欧几里得（B）阿波罗尼奥斯（C）毕达哥拉斯 （D）梅内赫莫斯 6、下列哪位数学家提出猜想：每个偶数是两个素数之和；每个奇数是三个素数之和（）。 （A）费马（B）欧拉（C）哥德巴赫（D）华林 7、下列哪位数学家首先证明了五次和五次以上的代数方程的根式不可解性（）。 （A）拉格朗日（B）阿贝尔（C）伽罗瓦（D）哈密顿 8、在非欧几何的先行者中中，最先对“第五公设能由其他公设证明”表示怀疑的数学家（）。 （A）克吕格尔（B）普罗克鲁斯（C）兰伯特（D）萨凯里 9、下列数学家中哪位数学家被称作“现代分析学之父”（）。

离散数学数理逻辑部分考试试

离散数学形成性考核作业（四） 数理逻辑部分 本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第四次作业，大家要认真及时地完成数理逻辑部分的形考作业，字迹工整，抄写题目，解答题有解答过程。 第6章命题逻辑 1．判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题． （1）8能被4整除． （2）今天温度高吗？ （3）今天天气真好呀！ （4）6是整数当且仅当四边形有4条边． （5）地球是行星． （6）小王是学生，但小李是工人． （7）除非下雨，否则他不会去． （8）如果他不来，那么会议就不能准时开始． 解：此题即是教材P.184习题6（A）1 （1）、（4）、（5）、（6）、（7）、（8）是命题，（2）、（3）不是命题。 其中（1）、（5）是简单命题，（4）、（6）、（7）、（8）是复合命题。 2．翻译成命题公式 （1）他不会做此事． （2）他去旅游，仅当他有时间． （3）小王或小李都会解这个题． （4）如果你来，他就不回去． （5）没有人去看展览． （6）他们都是学生． （7）他没有去看电影，而是去观看了体育比赛． （8）如果下雨，那么他就会带伞． 解：此题即是教材P.184习题6（A）2

会带伞。 ：如果下雨，那么他就：他会带伞。 ：天下雨。）（。是去观看了体育比赛。：他没有去看电影，而。 ：他去观看了体育比赛：他去看电影。）（：他们都是学生。 ）（：没有人去看展览。 ：有人去看展览。）（去。 ：如果你来，他就不回：他回去。：你来。）（道题。：小王或小李都会解这：小李会解这道题。 ：小王会解这道题。）（时间。 ：他去旅游，仅当他有：他有时间。 ：他去游泳。）（：他不会做此事。：他会做此事。）（Q P Q P Q P Q P P P P Q P Q P Q P Q P Q P Q P P P →∧???→∧→?87654321 3．设P ，Q 的真值为1；R ，S 的真值为0，求命题公式(P ∨Q )∧R ∨S ∧Q 的真值． 解：此题即是教材P.184习题6（A ）4（2） (P ∨Q )真值为1，(P ∨Q )∧R 真值为0，S ∧Q 真值为0， 从而(P ∨Q )∧R ∨S ∧Q 真值为0。 4．试证明如下逻辑公式 （1） ┐（A ∧┐B ）∧（┐B ∨C ）∧┐C ? ┐（A ∨C ） （2） (P →Q )∧(Q →R )∧┐R ??P （此题即是教材P.185习题6（A ）5（1）、（4）） ) 7() () 8()6)(5()7()4)(2()6()4)(3()5()4()3()1() 2()() 1()(), (),(由由由由由证明：结论：前提：T B A T B A T A T B P C P C B T B A P B A B A C C B B A ∨??∧????∨?∨??∧?∨??∨??∧? ) 4)(3() 5()4()2)(1()3() 2() 1(), (),(由由证明：结论：前提：T P P R T R P P R Q P Q P P R R Q Q P ??→→→??→→

北邮高级数理逻辑课件

形式系统由{∑, TERM, FORMULA, AXIOM, RULE}等5个部分构成，其中 称为符号表，TERM 为项集；FORUMULA 为公式集；AIXIOM 为公理集；RULE 为推理规则集。： 1、 符号表∑为非空集合，其元素称为符号。 2、 设∑* 为∑上全体字的组合构成的集合。项集TERM 为∑* 的子集，其元素称为项； 项集TERM 有子集V ARIABLE 称为变量集合，其元素称为变量。F(X) a, X, 3、 设∑* 为∑上全体字的组合构成的集合。公式结FORMULA 为∑* 的子集，其元素称为公式；公式集有子集ATOM ，其元素称为原子公式。 A(f(a,x1,y)), A →B 4、 公理集AXIOM 是公式集FROMULA 的子集，其元素称为公理。 5、 推理规则集RULE 是公式集FORMULA 上的n 元关系集合，即 RULE=)}2(|{n FORMULA r n n n r ?∧≥∧?是正整数， 其元素称为形式系统的推理规则。 其中公式集和项集之间没有交叉，即TERM ∩FORMULA =φ，公式和项统称为表达式。 由定义可知，符号表∑、项集TERM 、公式集FORMULA 是形式系统的语言部分。而公理集AXIOM 、推理规则集RULE 为推理部分 形式系统特性 1、 符号表∑为非空、可数集合（有穷、无穷都可以）。 2、 项集TERM 、公式集FORMULA 、公理集AXIOM 和推理规则集RULE 是递归集合， 即必须存在一个算法能够判定给定符号串是否属于集合（可判定的）。 3、 形式系统中的项是用来描述研究的对象，或者称为客观世界的。而公式是用来描述 这些研究对象的性质的。这个语言被称为对象语言。定义公式和项产生方法的规则称为词法。 公理： I ))((A B A →→ II ))()(())(((C A B A C B A →→→→→→ III ))())()(((A B B A →→?→? 证明：A →A (1) A →(A →A) ((A →(B →C))→((A →B)→(A →C)) ((A →(B →A))→((A →B)→(A →A)) ((A →((A →A)→A))→((A →(A →A))→(A →A)) A →((A →A)→A)) (A →(A →A))→(A →A) (A →(A →A)) A →A

数理逻辑测试题

玛 氏 食 品 ( 中国 ) 有 限 公 司 姓名：武英杰 性别：男 1-25 题均为选择题，只有一个正确答案。答案写在( ) 内 1-6 题根据下列数字规律，选择( )内应填数字： ( B ) 1、 2，9，16，23，30，（ ） A.35 B.37 C.39 D.41 ( C ) 2、 5，11，20，32，（ ） A ．43 B ．45 C ．47 D ．49 ( C )3、 1，2，3，5，（ ），13 A 9 B 11 C 8 D7 ( A )4、 5，7，（ ），19，31，50 A 12 B 13 C 10 D11 ( C )5、 8，4，2，2，（ ） A 、2 B 、3 C 、4 D 、5 ( C)6、 14，20，29，41，( ) A.45 B.49 C.56 D.72 ( A ) 7、. 15.025.053÷?的值是： A ．1 B ．1.5 C ．1.6 D ．2.0 ( C ) 8、 1994年第二季度全国共卖出汽车297600辆，与上年同期相比增长了 24%。上年同期卖出多少辆汽车?

A．714224 B．226176 C．240000 D．369024 ( D ) 9、甲、乙两地相距42公里，A、B两人分别同时从甲乙两地步行出发， A的步行速度为3公里/小时，B的步行速度为4公里/小时，问A、B步行几小时后相遇？ A. 3 B. 4 C. 5 D. 6 ( A)10、一根绳子长40米，将它对折剪断；再对剪断；第三次对折剪断，此时每根绳子长多少米？ A、5 B、10 C、15 D、20 ( B ) 11、如果一米远栽一棵树，则285米远可栽多少棵树？ A、285 B、286 C、287 D、284 (B ) 12、在一本300页的书中，数字“1”在书中出现了多少次？ A、140 B、160 C、180 D、120 ( D ) 13、自然数A、B、 C、 D的和为90，已知A加上2，B减去2，C乘以 2，D除以2之后所得结果相同，则B等于（） A、26 B、24 C、28 D、22 ( B ) 14、某人工作一年的报酬是18000元和一台全自动洗衣机,他干了7个月, 得到9500和一台全自动洗衣机,问这台洗衣机值多少元? A.8500元 B.2400元 C.2000元 D.1700元 ( B ) 15、橱窗：商品；相当于 A 电影：明星 B 书架：书籍 C 宇宙：星球 D 餐馆：厨师

简单的 逻辑推理

逻辑推理（一） 专题简析： 逻辑推理题不涉及数据，也没有几何图形，只涉及一些相互关联的条件。它依据逻辑汇率，从一定的前提出发，通过一系列的推理来获取某种结论。 解决这类问题常用的方法有：直接法、假设法、排除法、图解法和列表法等。 逻辑推理问题的解决，需要我们深入地理解条件和结论，分析关键所在，找到突破口，进行合情合理的推理，最后作出正确的判断。 推理的过程中往往需要交替运用“排除法”和“反正法”。要善于借助表格，把已知条件和推出的中间结论及时填入表格内。填表时，对正确的（或不正确的）结果要及时注上“√”（或“×”），也可以分别用“1”或“0”代替，以免引起遗忘或混乱，从而影响推理的速度。 推理的过程，必须要有充足的理由或重复内的根据，并常常伴随着论证、推理，论证的才能不是天生的，而是在不断的实践活动中逐渐锻炼、培养出来的。 例题1： 星期一早晨，王老师走进教室，发现教室里的坏桌凳都修好了。传达室人员告诉他：这是班里四个住校学生中的一个做的好事。于是，王老师把许兵、李平、刘成、张明这四个住校学生找来了解。 （1）许兵说：桌凳不是我修的。 （2）李平说：桌凳是张明修的。 （3）刘成说：桌凳是李平修的。 （4）张明说：我没有修过桌凳。 后经了解，四人中只有一个人说的是真话。请问：桌凳是谁修的？ 根据“两个互相否定的思想不能同真”可知：（2）、（4）不能同真，必有一假。 假设（2）说真话，则（4）为假话，即张明修过桌凳。 又根据题目条件了：只有1人说的是真话：可退知：（1）和（3）都是假话。由（1）说的可退出：桌凳是许兵修的。这样，许兵和张明都修过桌凳，这与题中“四个人中只有一个人说的是真话”相矛盾。 因此，开头假设不成立，所以，（2）李平说的为假话。由此可退知（4）张明说了真话，则许兵、刘成说了假话。所以桌凳是许兵修的。 练习1： 1、小华、小红、小明三人中，有一人在数学竞赛中得了奖。老师问他们谁是获奖者，小华说是小红，小红说不是我，小明也说不是我。如果他们当中只有一人说了真话。那么，谁是获奖者？ 2、一位警察，抓获4个盗窃嫌疑犯A、B、C、D，他们的供词如下： A说：“不是我偷的”。 B说：“是A偷的”。 C说：“不是我”。 D说：“是B偷的”。 他们4人中只有一人说的是真话。你知道谁是小偷吗？ 3、有500人聚会，其中至少有一人说假话，这500人里任意两个人总有一个说真话。说真话的有多少人？说假话的有多少人？ 例题2： 虹桥小学举行科技知识竞赛，同学们对一贯刻苦学习、爱好读书的四名学生的成绩作了

离散数学数理逻辑部分期末复习题

离散数学数理逻辑部分综合练习辅导 一、单项选择题 1．设P ：我将去打球，Q ：我有时间．命题“我将去打球，仅当我有时间时”符号化为( )． A ．P Q → B ．Q P → C ．Q P ? D ．Q P ?∨? 因为语句“仅当我有时间时”是“我将去打球”的必要条件，所以选项B 是正确的． 正确答案：B 一般地，当语句是由“……，仅当……”组成，它的符号化用条件联结词→． 问：如果把“我将去打球”改成“我将去学习”、“我将去旅游”等，会符号化吗？ 2．设命题公式G ：)(R Q P ∧→?，则使公式G 取真值为1的P ，Q ，R 赋值分别是 ( )． A ．0, 0, 0 B ．0, 0, 1 C ．0, 1, 0 D ．1, 0, 0 个人收集整理 勿做商业用途 当P 为真值为1时，P ?的真值为0，无论()Q R ∧的真值是1还是0，命题公式G 的真值为1．所以选项D 是正确的． 正确答案：D 3．命题公式P ∨Q 的合取范式是 ( )． A ．P ∧Q B ．（P ∧Q ）∨（P ∨Q ） C ．P ∨Q D ．?（?P ∧?Q ） 复习合取范式的定义： 定义6.6.2 一个命题公式称为合取范式，当且仅当它具有形式： A 1∧A 2∧…∧A n ， （n ≥1） 其中A 1，A 2，…，A n 均是由命题变元或其否定所组成的析取式． 由此可知，选项B 和D 是错的．又因为P ∧Q 与P ∨Q 不是等价的，选项A 是错的．所以，选项C 是正确的． 正确答案：C 4．命题公式)(Q P →?的析取范式是( )． A ．Q P ?∧ B Q P ∧? C ．Q P ∨? D ．Q P ?∨ 复习析取范式的定义： 定义6.6.3 一个命题公式称为析取范式，当且仅当它具有形式： A 1∨A 2∨…∨A n ， （n ≥1） 其中A 1，A 2，…，A n 均是有命题变元或其否定所组成的合取式． 公式)(Q P →?与Q P ?∧是等价的，Q P ?∧满足析取范式的定义，所以，

数理逻辑考试题及答案

“离散数学”数理逻辑部分考核试题答案 ━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━ 一、命题逻辑基本知识（5分） 1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分） （0）小刘既不怕吃苦，又爱钻研。 解：p∧q，其中，P：小刘怕吃苦；q：小刘爱钻研。 （1）只有不怕敌人，才能战胜敌人。 解：q→p，其中，P：怕敌人；q：战胜敌人。 （2）只要别人有困难，老张就帮助别人，除非困难已经解决了。 解：r→(p→p)，其中，P：别人有困难；q：老张帮助别人；r：困难解决了。 （3）小王与小张是亲戚。 解：p，其中，P：小王与小张是亲戚。 2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。共1分） （0）A：((p q)((p q) (p q))) r （1）B：(p(q p)) (r q) （2）C：(p r) (q r) （3）E：p(p q r) （4）F：(q r) r 解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。 3、判断推理是否正确（总共2题，完成的题号为学号尾数取2的余，完成1题。共2分） （0）设y=2|x|，x为实数。推理如下：如y在x=0处可导，则y在x=0处连续。发现y在x=0处连续，所以，y在x=0处可导。 解：设y=2|x|，x为实数。令P：y在x=0处可导，q：y在x=0处连续。由此，p为假，q为真。本题推理符号化为：(p q) q p。由p、q的真值，计算推理公式真值为假，由此，本题推理不正确。 （1）若2和3都是素数，则6是奇数。2是素数，3也是素数。所以，5或6是奇数。 解：令p:2是素数，q:3是素数，r:5是奇数，s:6是奇数。由此，p=1，q=1，r=1，s=0。本题推理符号化为： ((p q) →s) p q) →(r s)。计算推理公式真值为真，由此，本题推理正确。 二、命题逻辑等值演算（5分） 1、用等值演算法求下列公式的主析取范式或主合取范式（总共3题，完成的题号为学号尾数取3的余，完成1题。共2分） （0）求公式p→((q∧r) ∧(p∨(q∧r)))的主析取范式。 解：p→((q∧r) ∧(p∨(q∧r)))p∨(q∧r∧p) ∨(q∧r∧q∧r) p∨(q∧r∧p) ∨0 (p∧q∧r) ∨ (p∧1∧1) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨m7 (p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨m7 m0∨m1∨m2∨m3∨m7. （1）求公式((p→q)) ∨(q→p)的主合取范式。 解：((p→q)) (q→p) (p→q) (p→q) (p→q) p q M2.

数学发展简史

数学发展简史 数学发展史大致可以分为四个阶段。 一、数学形成时期（——公元前5 世纪） 建立自然数的概念，创造简单的计算法，认识简单的几何图形；算术与几何尚未分开。 二、常量数学时期（前5 世纪——公元17 世纪） 也称初等数学时期，形成了初等数学的主要分支：算术、几 何、代数、三角。该时期的基本成果，构成中学数学的主要内容。 1．古希腊（前5 世纪——公元17 世纪） 毕达哥拉斯——“万物皆数” 欧几里得——《几何原本》 阿基米德——面积、体积 阿波罗尼奥斯——《圆锥曲线论》 托勒密——三角学

丢番图——不定方程 2．东方（公元2 世纪——15 世纪） 1）中国 西汉（前2 世纪）——《周髀算经》、《九章算术》 魏晋南北朝（公元3 世纪——5 世纪）——刘徽、祖冲之出入相补原理，割圆术，算π 宋元时期（公元10 世纪——14 世纪）——宋元四大家杨辉、秦九韶、李冶、朱世杰 天元术、正负开方术——高次方程数值求解； 大衍总数术——一次同余式组求解 2）印度 现代记数法（公元8 世纪）——印度数码、有0；十进制（后经阿拉伯传入欧洲，也称阿拉伯记数法）

数学与天文学交织在一起 阿耶波多——《阿耶波多历数书》（公元499 年） 开创弧度制度量 婆罗摩笈多——《婆罗摩修正体系》、《肯特卡迪亚格》代数成就可贵 婆什迦罗——《莉拉沃蒂》、《算法本源》（12 世纪）算术、代数、组合学 3）阿拉伯国家（公元8 世纪——15 世纪） 花粒子米——《代数学》曾长期作为欧洲的数学课本 “代数”一词，即起源于此；阿拉伯语原意是“还原”，即“移项”；此后，代数学的内容，主要是解方程。 阿布尔．维法 奥马尔．海亚姆

数理逻辑怎样用于实际的应用

离散数学 期中课程设计作业 班级：10级计算机 组员：杨鑫 学号：09

数理逻辑怎样用于实际的应用 我们现在在学离散数学,对于离散数学中的数理逻辑这一部分存在很多盲点,那么这看似高深莫测的数理逻辑在实际生活中有着怎样的用处呢,下面让我们来讨论一下. 我们先看数理逻辑的定义:数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或形式逻辑的学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。数理逻辑是数学基础的一个不可缺少的组成部分。虽然名称中有逻辑两字，但并不属于单纯逻辑学范畴。数理逻辑是用数学的方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支，计算机科学，人工智能，语言学等学科有密切的联系，并且日益显示出它的主要作用和更加广泛的应用前景. 数理逻辑中的逻辑运算又称布尔运算，它是用数学的方法解决或研究逻辑问题，即用离散的符号“1”和“0”表示逻辑中的“真”和“假”再加上一套与之相关的“与”、“或”、“非”为运算基础的逻辑运算规则解决实际逻辑问题的方法，从而实现复杂逻辑运算到简单的数值计算的转化。下面我们就逻辑运算在电路设计中的运用加以探讨： 某公司王某欲搬入新房，搬迁前需要完成电路的设计安装，由于该房深处闹市，四周楼房林立，严重影响了客厅的采光，于是王某想设计一个电路，要求客厅四盏灯由一个开关控制，开关按下一次亮一盏灯，再按一下亮两盏，以此类推，直到按下第五次时所有灯熄灭。假设四个灯依次为A、B、C、D，灯亮为1，灯灭为0，开关有脉冲输入为1，否则为0，则根据题意可得真值表（如图１）： 设第ｎ号灯的上一状态为Nｎ，第ｎ＋１号灯现在在的状态为Nｎ＋１，脉冲输入状态为M，则有： Nｎ＋１=Nｎ∧M（N0与M的且运算） 其中Ｎｎ＝ＮＡ∧ＮＢ．．．∧Ｎｎ－１ 灯亮的条件为（A∧┐B∧┐C∧┐D）∨（A∧B∧┐C∧┐D）∨（A∧B∧C∧┐D）∨（A∧B∧C∧D） 如Ｂ灯亮的条件是Ａ灯亮并且有脉冲输入，C灯亮的条件是ＡＢ都亮并且有脉冲输入。该电路功能由一个与门电路和一个计数触发器连接即可完成，当开关第5次输入后计数器输出信号置0，灯全部关闭，此时设备全部复位。如图２。

数理逻辑考试题及答案

“离散数学”数理逻辑部分考核试题答案 --------------------------- ★----------------------------- 一、命题逻辑基本知识（5分） 1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分） （0）小刘既不怕吃苦，又爱钻研。 解：—p ∧q ,其中，P :小刘怕吃苦；q :小刘爱钻研。 （1）只有不怕敌人，才能战胜敌人。 解：q→-p ,其中，P :怕敌人；q :战胜敌人。 （2）只要别人有困难，老张就帮助别人，除非困难已经解决了。 解：—r→（P→P）,其中，P:别人有困难；q :老张帮助别人；r:困难解决了。 （3）小王与小张是亲戚。 解：p，其中，P:小王与小张是亲戚。 2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。共1分） （0）A ：（-（p^q）_；（（P -q）（.p^q））） r （1）B : （P 一9一；P））（r q） （2）C: （P -r）＞（q r） （3）E : p-;（P q r） （4）F ：—（q-；r） r------------------------------------------------------------------------ 解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。 3、判断推理是否正确（总共2题，完成的题号为学号尾数取.2的余，完成1题。共2分） （0）设y=2∣x∣，X为实数。推理如下：如y在x=0处可导，则y在x=0处连续。发现y在x=0处连续，所以，y在x=0处可导。 解：设y=2|x|，X为实数。令P: y在x=0处可导，q：y在x=0处连续。由此，P为假，q为真。本题推理符号化为：（p—；q） q—；P。由P、q的真值，计算推理公式真值为假，由此，本题推理不正确。 （1）若2和3都是素数，则6是奇数。2是素数，3也是素数。所以，5或6是奇数。 解：令P:2是素数，q:3是素数，r:5是奇数，S:6是奇数。由此，p=1，q=1，r=1，S=O。本题推理符号化为：（（P q）→ S） P q）→ （r S）。计算推理公式真值为真，由此，本题推理正确。 二、命题逻辑等值演算(5分) 1、用等值演算法求下列公式的主析取范式或主合取范式(总共3题，完成的题号为学号尾数取3的余，完 成1题。共2分) (0)求公式p→ ((q ∧r) ∧(P ∨(―q ∧-r)))的主析取范式。 解：p→((q ∧r) ∧(P ∨(—q ∧-「)))：= 一p∨(q ∧r∧P) ∨(q ∧r ∧一q ∧—r)二一P ∨(q ∧r∧P) ∨0 二(P ∧q∧r) ∨= (一p∧1 ∧1) ∨(q ∧r∧P) 二(—p ∧(q ∨-q) ∧(r ∨-r)) ∨(q ∧r∧P) U (~p ∧(q ∨-q) ∧(r ∨一r)) ∨m7 二(一P ∧—q ∧ F ∨ (一P ∧—q ∧r) ∨ (一P ∧q ∧_r) ∨ (一P ∧q ∧r) ∨m7 m0 ∨m1 ∨m2 ∨m3 ∨m7. (1)求公式一(一(P → q)) ∨(—q → 一P)的主合取范式。 解：一(一(P → q)) (—q →-p)二(P → q) (P →q) U (P → q)

数学发展简史

数学发展简史 IMB standardization office【IMB 5AB- IMBK 08- IMB 2C】

数学发展简史数学发展史大致可以分为四个阶段。 一、数学形成时期（——公元前 5 世纪） 建立自然数的概念，创造简单的计算法，认识简单的几何图形；算术与几何尚未分开。 二、常量数学时期（前 5 世纪——公元 17 世纪） 也称初等数学时期，形成了初等数学的主要分支：算术、几 何、代数、三角。该时期的基本成果，构成中学数学的主要内容。 1．古希腊（前 5 世纪——公元 17 世纪） 毕达哥拉斯——“万物皆数” 欧几里得——《几何原本》 阿基米德——面积、体积 阿波罗尼奥斯——《圆锥曲线论》

托勒密——三角学 丢番图——不定方程 2．东方（公元 2 世纪——15 世纪） 1）中国 西汉（前 2 世纪）——《周髀算经》、《九章算术》 魏晋南北朝（公元 3 世纪——5 世纪）——刘徽、祖冲之出入相补原理，割圆术，算π 宋元时期（公元 10 世纪——14 世纪）——宋元四大家杨辉、秦九韶、李冶、朱世杰 天元术、正负开方术——高次方程数值求解； 大衍总数术——一次同余式组求解 2）印度 现代记数法（公元 8 世纪）——印度数码、有 0；十进制

（后经阿拉伯传入欧洲，也称阿拉伯记数法） 数学与天文学交织在一起 阿耶波多——《阿耶波多历数书》（公元 499 年） 开创弧度制度量 婆罗摩笈多——《婆罗摩修正体系》、《肯特卡迪亚格》代数成就可贵 婆什迦罗——《莉拉沃蒂》、《算法本源》（12 世纪）算术、代数、组合学 3）阿拉伯国家（公元 8 世纪——15 世纪） 花粒子米——《代数学》曾长期作为欧洲的数学课本 “代数”一词，即起源于此；阿拉伯语原意是“还原”，即“移项”；此后，代数学的内容，主要是解方程。 阿布尔．维法

数理逻辑考试题及答案

“离散数学”数理逻辑部分考核试题答案━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━ 一、命题逻辑基本知识（5分） 1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分） （0）小刘既不怕吃苦，又爱钻研。 解：?p∧q，其中，P：小刘怕吃苦；q：小刘爱钻研。 （1）只有不怕敌人，才能战胜敌人。 解：q→?p，其中，P：怕敌人；q：战胜敌人。 （2）只要别人有困难，老张就帮助别人，除非困难已经解决了。 解：?r→(p→p)，其中，P：别人有困难；q：老张帮助别人；r：困难解决了。 （3）小王与小张是亲戚。 解：p，其中，P：小王与小张是亲戚。 2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。共1分） （0）A：(?(p?q)→((p∧?q) ∨(?p∧q)))∨ r （1）B：(p∧?(q→p)) ∧(r∧q) （2）C：(p??r) →(q?r) （3）E：p→(p∨q∨r) （4）F：?(q→r) ∧r 解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。 3、判断推理是否正确（总共2题，完成的题号为学号尾数取2的余，完成1题。共2分） （0）设y=2|x|，x为实数。推理如下：如y在x=0处可导，则y在x=0处连续。发现y在x=0处连续，所以，y在x=0处可导。 解：设y=2|x|，x为实数。令P：y在x=0处可导，q：y在x=0处连续。由此，p为假，q为真。本题推理符号化为：(p→q) ∧q→p。由p、q的真值，计算推理公式真值为假，由此，本题推理不正确。（1）若2和3都是素数，则6是奇数。2是素数，3也是素数。所以，5或6是奇数。 解：令p:2是素数，q:3是素数，r:5是奇数，s:6是奇数。由此，p=1，q=1，r=1，s=0。本题推理符号化为：((p ∧ q) →s) ∧p ∧q) →(r ∨ s)。计算推理公式真值为真，由此，本题推理正确。 二、命题逻辑等值演算（5分） 1、用等值演算法求下列公式的主析取范式或主合取范式（总共3题，完成的题号为学号尾数取3的余，完成1题。共2分） （0）求公式p→((q∧r) ∧(p∨(?q∧?r)))的主析取范式。 解：p→((q∧r) ∧(p∨(?q∧?r)))??p∨(q∧r∧p) ∨(q∧r∧?q∧?r) ??p∨(q∧r∧p) ∨0 ? (p∧q∧r) ∨? (?p∧1∧1) ∨(q∧r∧p) ? (?p∧(q∨?q)∧(r∨?r)) ∨(q∧r∧p) ? (?p∧(q∨?q)∧(r∨?r)) ∨m7 ? (?p∧?q∧?r)∨(?p∧?q∧r)∨(?p∧q∧?r)∨(?p∧q∧r)∨m7 ?m0∨m1∨m2∨m3∨m7. （1）求公式?(?(p→q)) ∨(?q→?p)的主合取范式。 解：?(?(p→q)) ∨ (?q→?p)?(p→q) ∨ (p→q) ? (p→q) ??p∨q ? M2. （2）求公式(p→(p∨q)) ∨r的主析取范式。

数理逻辑考试题及答案

数理逻辑考试题及答案 IMB standardization office【IMB 5AB- IMBK 08- IMB 2C】

“离散数学”数理逻辑部分考核试题答案━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━ ━ 一、命题逻辑基本知识（5分） 1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分） （0）小刘既不怕吃苦，又爱钻研。 解：p∧q，其中，P：小刘怕吃苦；q：小刘爱钻研。 （1）只有不怕敌人，才能战胜敌人。 解：q→p，其中，P：怕敌人；q：战胜敌人。 （2）只要别人有困难，老张就帮助别人，除非困难已经解决了。 解：r→(p→p)，其中，P：别人有困难；q：老张帮助别人；r：困难解决了。 （3）小王与小张是亲戚。 解：p，其中，P：小王与小张是亲戚。 2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。共1分） （0）A：((pq)((pq) (pq))) r （1）B：(p(qp)) (rq) （2）C：(pr) (qr) （3）E：p(pqr) （4）F：(qr) r 解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。

3、判断推理是否正确（总共2题，完成的题号为学号尾数取2的余，完成1题。共2分） （0）设y=2|x|，x为实数。推理如下：如y在x=0处可导，则y在x=0处连续。发现y在x=0处连续，所以，y在x=0处可导。 解：设y=2|x|，x为实数。令P：y在x=0处可导，q：y在x=0处连续。由此，p为假，q为真。本题推理符号化为：(pq) qp。由p、q的真值，计算推理公式真值为假，由此，本题推理不正确。 （1）若2和3都是素数，则6是奇数。2是素数，3也是素数。所以，5或6是奇数。 解：令p:2是素数，q:3是素数，r:5是奇数，s:6是奇数。由此，p=1，q=1，r=1，s=0。本题推理符号化为： ((p q) →s) p q) →(r s)。计算推理公式真值为真，由此，本题推理正确。 二、命题逻辑等值演算（5分） 1、用等值演算法求下列公式的主析取范式或主合取范式（总共3题，完成的题号为学号尾数取3的余，完成1题。共2分） （0）求公式p→((q∧r) ∧(p∨(q∧r)))的主析取范式。 解：p→((q∧r) ∧(p∨(q∧r))) p∨(q∧r∧p) ∨(q∧r∧q∧r) p∨(q∧r∧p) ∨0 (p∧q∧r) ∨ (p∧1∧1) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨m7 (p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨m7 m0∨m1∨m2∨m3∨m7. （1）求公式((p→q)) ∨(q→p)的主合取范式。

数理逻辑心得

数理逻辑的心得 数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。是大四接触到的，现简单介绍一下数理逻辑的发展史，算是一点感悟吧 1数理逻辑的发展前期 ·前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论 ·初创时期——逻辑代数时期（17世纪末） ·资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。 ·人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。 ·莱布尼兹(Leibniz, 1646~1716)完善三段论，提出了建立数理逻辑或者说理性演算的思想： ·提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。 ·使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。 ·布尔(G. Boole, 1815~1864)代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。 数理逻辑的奠基时期 ·弗雷格(G. Frege, 1848~1925)：《概念语言——一种按算术的公式语言构成的纯思维公式语言》(1879)的出版标志着数理逻辑的基础部分——命题演算和谓词演算的正式建立。 ·皮亚诺(Giuseppe Peano, 1858~1932)：《用一种新的方法陈述的算术原理》(1889)提出了自然数算术的一个公理系统。 ·罗素(Bertrand Russell, 1872~1970)：《数学原理》(与怀特黑合著，1910, 1912, 1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义了类和关系的概念，建立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主要是算术）中的主要概念和定理。 ·逻辑演算的发展：甘岑(G. Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等。 ·各种各样的非经典逻辑的发展：路易斯(Lewis, 1883~1964)的模态逻辑，实质蕴涵怪论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。 集合论的悖论使得人们觉得数学产生了第三次危机，提出了数学的基础到底是什么这样的问题。 ·罗素等的逻辑主义：数学的基础是逻辑，倡导一切数学可从逻辑符号推出，《数学原理》一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。 ·布劳维尔(Brouwer, 1881~1966)的直觉主义：数学是心灵的构造，只承认可构造的数学，强调构造的能行性，与计算机科学有重要的联系。坚持潜无穷，强调排中律不能用于无穷集合。海丁(Heyting)的直觉主义逻辑。 ·希尔伯特(D. Hilbert)的形式主义：公理化方法与形式化方法，元数学和证明论，提倡将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论，要数学建立在公理化基础上，将

简单逻辑推理练习(学生版)

简单逻辑推理练习 1. 丁丁、光光和园园三位小朋友分别出生在上海、北京和广州三个城市中。已知：（1）丁丁从未到过上海；（2）上海出生的小朋友不叫光光；（3）光光不出生在广州。问：三个小朋友 2. （1）每个老师只教一门课；（2）甲上课全用汉语；（3）外语老师是一个学生的哥哥；（4）丙是一位女教师，她比数学老师活泼。请问：三位老师各上什么课？ 3.图中有三个六面体，每一个六面体上A 、B 、C 、D 、E 、F 六个字母的排列顺序完全相同。判断图中A 、B 、C 三个字母的对面各是什么字母。 （1） （2） （3） A 对面是_________; B 对面是_________; C 对面是_________. 4.甲、乙、丙、丁四位同学进行一百米赛跑。赛后，甲、乙、丙三位同学说了以下几句话，丁没有说话。甲：丙第一名，我第三名；乙：我第一名，丁第四名；丙：丁第二名，我第三名。比赛成绩公布后，发现他们都只说对了一半，你能说出他们的名次是如何排列的吗？ 名次排列是_______________________________ 5. 小王、小张和小李原来是邻居，后来当了医生、 教师和战士。只知道：小李比战士年纪大，小王和教师比小张年龄小。请同学们想一想：谁是医生，谁是教师，谁是战士？ 6. 数学竞赛后，小明、小华和小强各获得一枚奖牌，其中一人得金牌，一人得银牌，一人得铜牌。老师猜测：“小明得金牌，小华不得金牌，小强不得铜牌。”结果老师只猜对了一个，那么谁得金牌，谁得银牌，谁得铜牌？ 金牌是________;银牌是________;铜牌是________。

7.三年级三个班级举行数学竞赛。小明猜想比赛的结果是：2班第一名，1班第二名，3班第三名；小华猜想的比赛名次是：1班，2班，3班。比赛结果只有小华猜的2班第二名是对的。 问比赛的名次如何排列？ 第一名是_________;第二名是_________;第三名是_________。 8.图中四个相同的正方体按相同的顺序在上面写数字1～6， 然后加图叠加，问1、2、3的对面分别是什么数字？ 1对面是_________;2对面是_________;3对面是_________ 9.甲、乙、丙、丁四人进行游泳比赛。赛前名次众说不一。 有的说：甲第二名，丁第三名。 有的说：甲第一名，丁第二名。 有的说：丙第二名，丁第四名。 实际上，上面三种说法各对了一半。问甲、乙、丙、丁各是第几名。 10.学校举行数学比赛，甲、乙、丙、丁、戊五位老师，对一贯刻苦学习的A 、B 、C 、D 、E 五位同学，事先就作了如下的估计：老师甲：B 第三名，C 第五名；老师乙：E 第四名，D 第五名；老师丙：A 第一名，E 第四名；老师丁：C 第一名，B 第二名；老师戊：A 第三名，D 第四名。比赛结束扣，这五名学生果然是前五名，且每一个名次，都有老师猜中了。试求各人的名次。 比赛名次：第一名是____;第二名是____;第三名是____第四名是____;第五名是____。 11.赵老师不在的时候，有一名同学把拾到的手表放在老师的办公桌上。大家都知道，这是冬冬、丹丹和菲菲三人中的一个人做的好事。教师找他们三人来问：“这是谁做的好事呢？” 冬冬说：“是丹丹干的。”丹丹说：“不是我干的。”菲菲也说：“不是我干的。” 如果他们三人中，有两人说的是假话，只有一个人说的是真话，你能判断出好事是谁干的吗？ _____和______的话是相互矛盾，所以他们两人的话必有一真。 那么______说的话一定是假话，所以做好事的是______。 12.有三个颜色分别是红、黄、蓝的盒子，每只盒子外面各有一句话（如下图所示），这三句话中只有一句是真的，你能判断出宝石放在哪个盒子里吗？ _____和______的盒子外面的一句话是相互矛盾，所以他们两人的话必有一真。 那么______的盒子外面的一句话一定是假话，所以宝石放是在______。 1 3 1 5 2 2 4 1 4