···························································· 第3章
chapter3
逻辑思维
计算机科学是逻辑的继续,只是换了载体。
ComputerScienceisthecontinuationofLogicbyothermeans.
———乔治·戈特洛布(GeorgGottlob),2011
第1章讲述了计算机科学的发展概貌。我们看到,自ENIAC数字电子计算机发明以
来,计算机的能力(计算速度)进入了随时间指数增长的轨道。历史发展还验证了巴贝扬断
言:计算速度是像黄金一样的硬通货,可以兑换成其他产品和服务。计算能力的指数增长
使得计算机、计算机科学、计算思维日益渗透到人类社会生产生活的各个方面,产生了许许
多多的使用模式和计算机应用。它们都是通过运行在计算机上的计算过程体现的。
但是,我们尚未讨论计算机科学的一个根本问题:计算过程可以用来解决什么问题?
这个问题还可以有多个变种与细化。
(1)计算过程可以用来解决哪些问题? 这些问题称为可计算问题。
(2)存不存在计算过程不可解的问题?
(3)存不存在一种通用的计算机? 什么是通用计算机? 通用是何含义?
我们可以将计算过程理解为在计算机上通过操作数字符号变换信息的过程。操作数字
符号的最基本的理论模型是布尔逻辑,需要考虑系统状态时的基本理论模型是图灵机。本
章将讨论布尔逻辑和图灵机,并对上述问题给出明确的回答。
(1)计算过程可以用来解决图灵可计算问题。
(2)存在任何计算过程都不可解的问题。
(3)存在通用计算机,即任何合理定义的计算机都可被该通用计算机模拟。
逻辑思维是一种普遍的能力和思维方式,在其他学科也有体现,尤其在数学中体现最为
明显。计算机科学的逻辑思维有别于其他科学的逻辑思维,强调比特精准以及能够机械地
自动执行的特点。
3.1 布尔逻辑
3.1.1 命题逻辑
我们先用一个实例直观地了解命题逻辑,随后再讨论它的基本概念,包括命题、连接词、
真值表、基本性质、范式,以及布尔函数和布尔表达式。
◆
第
3
章 逻辑思维95
1】
【实例3.探险者难题。
一位探险者在奥斯仙境旅行,他想要去翡翠城,但路上必须经过说谎国。说谎国的人永
远说谎话,而诚实国的人永远讲真话。一天探险者走到了一个岔路口,两条路分别通向诚实
国和说谎国,他不知道哪一条路是去往说谎国的路。正在他犹豫不决的时候,路上来了两个
人,已知其中一人来自诚实国,另一人来自说谎国。探险者需要问这两个人哪一条是去往说
谎国的路,请问他应该如何进行询问?
为了体现逻辑的作用,这里我们提出如下要求:探险者只能问一次问题,而且问题的答
案只能是“是”或者“否”。
解答:为了叙述方便,我们将这两个人分别称为
A
和B,两条路分别记为
s
和t。探险者
的一种提问方法如下:提问A,“你对于‘你来自诚实国’和‘路
s
通往说谎国’这两个问题的回
答是相同的吗?” 若
A
回答“是”,则应该走s这条路;若
A
回答“否”,则应该走t这条路。
上面的提问方式的表述有一些复杂,下面我们给上述解答一个简单的证明,希望能从中
体现出逻辑的作用。其中会用到一些逻辑的符号和推理规则,其含义在后面的章节中会做
具体介绍,暂时不能完全看懂也没有关系。
我们用A=1表示
A
来自诚实国,A=0表示
A
来自说谎国。同理,用B=1表示
B
来
自诚实国,B=0表示
B
来自说谎国。用s=1表示路
s
通往说谎国,路s=0通往诚实国(即
另一条路
t
通往说谎国)。
注意,无论探险者问
A
或者B:“ 你来自诚实国吗?”,回答总是“是”,无论他们真正来自
哪个国家。但是,如果问A:A..s=? 其结果是,无论
A
的值是1或0,其回答总是..s(
的非)。这里的A..
s
表示
A
与
s
的异或,即
A
与
s
的值是否相等:若相等,A..
s
的值为0,(s) 否则值为1。这里我们使用了如下性质:1..s=..s,0..s=s,另外要注意到在
A
=0时他
将说谎。
因此,如果A..s=0,即
A
回答“是”,或者说“你来自诚实国”和“路
s
通往说谎国”这两
个问题的回答相同,那么说明s=1,因此应该走
s
这条路。相反,如果
A
回答“否”,则应该
走
t
这条路。
1.
命题
命题分为简单命题和复合命题。“今天下雨”“ x2≥0”“π是超越数”都是简单命题。“y<
”
a
是素数, mod4)
3,并且y>0“ 或者a≡1(”都是复合命题。
计算机科学使用布尔逻辑(Booleanlogic)表征命题逻辑(propositionlogic), 在布尔逻
辑中只有两个值:“ 真(True,T)”和“假(False,F)”。在布尔逻辑中我们假定所有的命题,或
者为真命题,或者为假命题,用1表示“真”,0表示“假”。
2.
连接词
简单命题可以通过连接词组合成复合命题,常见的连接词有与、或、非、蕴含、异或等。
(1)合取符号∧,即“与”(conjunction,and):x∧y=1当且仅当x=y=1,也就是说只
要
x
和
y
中有一个为假,那么x∧
y
为假。例如:x>-1并且x<1( 1<x<
1)可以记作(x<1 )。
x2<1 的解,即
x>-1)∧(
(2)析取符号∨,即“或”(disjunction,or):x∨y=0当且仅当x=y=0,也就是说只要
◆
96
计算机科学导论———以计算思维为舟
x
和
y
中有一个为真,那么x∨
y
为真。例如:x2≥1 的解,x≤-1或者x≥1 可以记作
(x≤-1)∨(x≥1 )。
(3)非符号..(negation,not):..x=0当且仅当x=1,即非
x
为假当且仅当
x
为真。
-
通常我们也用
x
表示命题
x
的非,例如:x∨y=..(x∨y)。由于布尔逻辑中只有0和1
两个值,因此..(..x)=x,即否定之否定即为肯定。
implicatiox→y=
(4)蕴含符号→(n):1当且仅当x=0或者y=1,即前提为假或者结
论为真。这里要特别注意,当前提为假的时候,不管结论是否正确,此命题都是真命题。一
个例子:山无陵,江水为竭,冬雷震震,夏雨雪,天地合,乃敢与君绝。
(5)异或符号..(exclusiveor):x..y=1当且仅当x≠y,即异或能用来判断
x
与
y
是
否相等。如果把
x
和
y
都当作数值来看,那么x..y=d2 )。需要特别注意1..
1=0,因此异或常被用来做取补的运算。
x+y(mo
3.
真值表
对于每一个布尔函数,可以将所有变量的全部可能取值以及所对应的最终函数值都列
在一个表里,每一行对应所有变量的一种取值,1列出了
此即一个布尔函数的真值表。表3.
合取、析取、蕴含以及异或操作的真值表
。
表3.析取、异或操作的真值表
1 合取、蕴含、
x y
x∧
y
x∨
y
x→
y
x..
y
0 0 0 0 1 0
0 1 0 1 1 1
1 0 0 1 0 1
1 1 1 1 1 0
4.
布尔逻辑的若干基本性质
下面列出了关于合取、析取、非、异或操作的一些基本性质,我们在此略去这些性质的证
明过程,请读者利用真值表自行验证。
(1)交换律:x∧y=y∧x,y∨x,y..x。
x∨y=x..y=
(2)结合律:x∧(y∧z)=(x∧y)∧z,x∨(y∨z)=(x∨y)∨z,x..(y..z)=(x..
y)..z。
=(x∨(x∨z
(3)分配律:x∧(y∨z)x∧y)∨(x∧z),y∧z)=(x∨y)∧()。
(4)幺元律:x∨0=x∧1x,=。0是∨和..的幺元,1是∧的幺元。针对
x,=x..0x
-
异或操作,有x..1=x,1不是..的幺元。
(5)极元律:x∧0=0,x∨1=1。0是∧的极元,1是∨的极元。
(6)幂等律:x∨x=x,x∧x=x。
(7)吸收律:x∨(x∧y)=x,x∧(x∨y)=x
。
(--=1
。
8)互补律:x∧x=0,x∨
x
-
(9)双重否定律:x=x,即..(..x)=x。
◆
第
3
章 逻辑思维97
-
(n律(德摩根定律):-∨y,-。
-∧y
10)DeMorgax∧y=xx∨y=
x
借助德摩根定律,我们可以推出x∧y=-∨y,以及x∨y=,因此我们可以将一
个命题中的所有“与”都去掉,替换成为“或”和“非”。同样,我们可以把一个命题中所有的
“或” 而替换成“ 和“非”。例如:x∧(y∨z)=xy∨z)。
xx∧
y
去掉, 与” -∨(
对于“蕴含”和“异或”,我们也可以将它们表示成关于“与”“或”“非”的命题,进而可以只
用“与”和“非”(或者“或”和“非”)来表示,得到下列性质。
(11)x→y=-∨y。
(12)(-(x) ∧y)∨(x∧yx..y=(
x
-)。
x..y=
x
-),x∨y)∧(-∨
y
5.
析取范式和合取范式
对于一些更加复杂的命题,例如(x..y)→z,我们是否能够也将其写成只包含“与”“或”
“非”的命题呢? 给定任意的复合命题,能否写成只包含“与”“或”“非”的命题呢? 答案是肯
定的! 一种方式是反复借助上述基本性质进行展开。另外一种重要的方法是借助真值表来
进行展开。让我们先用一个例子说明。表3.x..y)→
z
的真值表。
2是(
表3.x..y)→
z
的真值表
2(
x y z
(x..y)→
z
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
从表3.2中可以看出,当(x,y,的取值分别是(0,0),(0,1),(0,1),(1,1),
z) 0,0,1,0,
(1,1,0),(1,1,1)时,命题(x..y)→
z
的取值为真。对于(0,0,0), 我们可以用一个由“与”
和“非” -∧
y
-与之对应, ---为真当且仅当(
连接的命题
x
-∧
z
命题
x
∧
y
∧zx,y,z)的取值为
(0,0,0)。对于其他5项,我们同样可以写出相应的由“与”和“非”连接的命题:x∧y∧z,
x∧y∧z,∧z,和x∧y∧z。最后我们将这6个命题用“或”连接如下:
x∧yx∧y∧
z
(-∧
y
-)∨(∧yx∧yx∧y∧
z
x
-∧zx
∧z)∨(x∧y∧z)∨(∧z)∨(-)∨(x∧y∧z)
这就给出了(x..y)→
z
的表示,或者说,上述由“或”连接起来的“与”“非”式的真值表
就是表3.2。这里的道理是因为:上述式子是若干个命题的析取连接(“或”)在一起。根据
“或”的性质,上式值为“真”当且仅当其中至少某一个子命题为“真”。而每一个子命题都是
若干命题变元(或者它们的“非”)的合取(“与”), 其值为真当且仅当(x,y,取我们要的某
一个值
(
。所以
x
-∧
y
-∧
z
-)∨(-∧
y
-∧z)∨(xx∧
y
-∧z)∨(
z-
)
)∨(x∧y∧z)
x..y)→z=(
x
-∧y∧z)∨(x∧y∧
z
◆
98
计算机科学导论———以计算思维为舟
上述这种通过将真值表中的每一个取值为1的行对应到一个“与”(合取)连接式,最后
用“或”(析取)将所有各行对应的命题连接起来的表示,称为这一命题的“析取范式”。
【定理3.析取范式。
1】
任何一个有
n
个变元的命题F(x2,…,), 一定可以表示成如下析取范式:
x1,xn
F(x1,xn
=Q1∨Q2∨…∨Qm
x2,…,)
其中,每一个Qi
都是这
n
个变元或其“非”的合取(“与”)连接式,即Qi=l1∧l2∧…∧ln
,其
-
中lj
=xj
或者xj
。■
整个析取范式的长度
m
是命题
F
的真值表中函数值为1的行数,每一个Qi
恰好对应
其中一行,在Qi
中每一个变量都会出现,如果这一行中对应的变量xj
取值是1,则lj
=xj
,
如果对应的xj
取值是0,则lj
=-
j
。
读到这里善于思考的读者自然(x) 会问一个问题:如果我们从真值表里的0出发,我们是
否也能够写出(x..y)→
z
的表示? 这个问题的答案也是肯定的。我们可以为值为0的两
行(0,1,0)和(1,0,0)写出其用“或”连接的表示:x∨y∨
z
和
x
∨y∨z,注意这里写的方式
和之前是有区别的。最后使用“与”将两项连接起来,
-
(x..y)x∨
y ((即) ∨y∨z)
→z=(-∨z)∧
x
对于这样一个表示,我们称之为(x..y)→
z
的合取范式
。
【定理3.合取范式
。
2】
任何一个有
n
个变元的命题F(x2,…,), 一定可以表示成如下合取范式:
x1,xn
F(x1,xn
=Q1∧Q2∧…∧Qm
x2,…,)
其中,每一个
-
Qi
。
都是这
n
个变元或其“非”的析取(“或”)连接式,即Qi
=l1∨l2∨…∨ln
,
lj
=xj
或者xj
■
整个析取范式的长度
m
是
F
的真值表中值为0的行数,每一个Qi
对应其中一行,在
Qi
中每一个变量都会出现,如果这一行中对应的变量xj
取值是0,则lj
=xj
,如果对应的
xj
取值是1,则lj
=-
j
。
【实例3.试分(x) y..z)的合取范式和析取范式。
2】别写出x→
(
解:首先写出x→(y..z)3所示
。
的真值表如表3.
表3.的真值表
3 x→(y..z)
x y z
x→(y..z)
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
第◆3 章 逻辑思维9 9
分别根据真值表中0的行和1的行,可以写出相应的合取范式和析取范式如下:
x→(y..z)=(x-∨y∨z)∧(x-∨y-
∨z-)
x→(y..z)=(x-∧y-
∧z-)∨(x-∧y-
∧z)∨(x-∧y∧z-)∨
(x-∧y∧z)∨(x∧y-
∧z)∨(x∧y∧z-)
6. 布尔函数与布尔表达式
任意命题事实上定义了一个布尔函数,从给定的n 个变量值,映射到特定函数值。
【定义3.1】 布尔函数。
一个n 变量的布尔函数是一个数学函数f:{0,1}n →{0,1},函数映射f 由其真值表
确定。 ■
命题x→(y..z)定义了一个3变量布尔函数,它的函数映射f 由上述真值表确定,或
等价地表达为下述函数定义
f(x,y,z)=
0 x=1,y=0,z=0
0 x=1,y=1,z=1
1 其他组合
ì
.
í
..
..
【实例3.3】 n 个变量的布尔函数一共有多少个?
让我们从简单的情形开始。
零个变元的布尔函数(常函数)有1和0,一共2个,即函数值恒等于1或恒等于0两个。
一个变元的布尔函数有:1、0、x 和x-,一共4个。
二个变元的布尔函数有:1、0、x、x-、y、y-
、x∧y、x∨y、x..y,…
这样一个一个地去数很容易遗漏,下面从另一个角度来看这个问题。考虑函数的真值
表,二元函数真值表一共有22=4行,每一行的值可以是0,也可以是1,一共两种选择。因
此根据乘法原理,所有不同的可能性有24=16种,即不同的布尔函数有16个。如果我们要
一一列出所有的这些函数,可以通过真值表的方式,也可以通过写出它们的合取(析取)范式
的形式。
仿照上面的推理,我们可以从2元布尔函数推广到一般的n 元布尔函数:n 元布尔函
数的真值表一共有2n 行,每一行对应的函数取值可以有0和1两种,因此不同的布尔函数
一共有22n 个。
上述刻画布尔函数的方式是一种枚举方式,将每一种输入组合对应的输出组合一一枚
举列出。这种方式的优点是完备,不会漏掉任一个映射。它的明显缺点是烦琐,当输入变量
n 较大时很花时间。另一个不太明显的缺点是,枚举定义没有揭示函数的特点。采用布尔
表达式刻画布尔函数,常常可以避免这两个缺点。事实上我们在描述命题时,已经用了这种
方式。例如,奇偶函数y=x1..x2..…..xn 很容易用布尔表达式表示。
【定义3.2】 布尔表达式。
0、1称为布尔常量。只能取值0或1的变量x1,x2,…,xn 称为布尔变量。用逻辑连接
词连接布尔常量或逻辑变量形成的表达式称为n 变量布尔表达式,简称布尔表达式。■
逻辑连接词也称为逻辑运算或逻辑算子。常见的逻辑连接词是逻辑与(即合取∧,也可
写作逻辑乘·)、逻辑或(即析取∨,也可写作逻辑加+)、逻辑非(..,也可将..x 记为x-)、异
或(..)、蕴含(→)。
◆
100
计算机科学导论———以计算思维为舟
算。
例如
它也可被记为
,(
x
(x+yx
+z)·(
∨
xz
+y+
z
-)。
采用了与、非3种运
-∨y∨z)∧(∨
y
-)就是一个3变量布尔表达式, 或、
要注意的是,布尔函数有唯一性,即每一个布尔函数都有唯一的真值表;但是,同一个布
尔函数可用多个不同的布尔表达式表示。例如,x→(y..z)、(
x
∨y∨z)∧(
x
∨
y
∨z)是
两个不同的布尔表达式,但它们都表示同样的布尔函数,对应同样的真值表。我们说两个布
尔表达式是等价的,如果它们对应同样真值表。反之,x→(y..z)、(y..z)→
x
这两个不同
的布尔表达式则不是等价的,因为它们不对应于相同的真值表。
【实例3.
n
个变量的互不等价的布尔表达式一共有多少个?
4】
有22n
个
。
【实例3.假如不考虑是否等价
,
5】
n
个变量的布尔表达式一共有多少个?
有无穷多个。
【实例3.列出2个变量的互不等价的布尔表达式。
6】
我们提出一条思路,完整答案留作练习。
2个变量的互不等价的布尔表达式一共有222=16 个。写出每一个的真值表,再根据真
值表写出析取范式。
通过3.1节的布尔逻辑的12 条基本性质,我们可以从一个布尔表达式得到另一个等
1.
价的布尔表达式。这往往相当于中小学数学中的化简操作
。
【实例3.列出2个变量的互不等价的布尔表达式
,
7】采用最简表达式形式。
2个变量的互不等价的布尔表达式一共有222=16 个。按照逻辑连接词的个数从小到
大逐级覆盖等价布尔表达式。每一步可先写出一个布尔表达式,再根据布尔逻辑的10 条基
本性质试图化简,从而写出最简表达式。记2变量布尔函数为y=x1,)。
f(x2
第一步:逻辑连接词的个数为0的表达式。列出所有布尔常量和布尔变量。得到4个
布尔表达式:0、1、x1、x2。它们对应的真值表列举如图3.
1所示。
图3.
1 逻辑连接词个数为0表达式的真值表
第二步:逻辑连接词的个数为1的表达式。将一个连接词作用于一个或多个布尔常量
和布尔变量,得到下述新的7个布尔表达式,即
y
等于xxx1+x2,x1..x2,x1→
x2,。它们对应的真值表列举如图3.2所示。
1,2,x1· x2,
x2→x1
第三步:逻辑连接词的个数为2的表达式。我们已经得到4+7=11 个最简表达式了。
还剩下5个最简表达式,每个包含2个连接词。作为练习,请同学们写出剩余的5个最简布
尔表达式。可能在第三步就完成了,也可能还需要更多步。
命题往往对应单输出布尔函数,简称布尔函数。简单的扩展可得到多输出布尔函数。
◆
第
3
章 逻辑思维101
图3.
2 逻辑连接词个数为1表达式的真值表
3】
【定义3.
n
个输入
m
个输出的布尔函数。
一个
n
输入
m
输出的布尔函数是一个数学函数f:{0,1}0,1}
m
,函数映射
f
由其
真值表确定。
n
→{
■
实例3.全加器的真值表与布尔函数。【
全加器是二进制加法的基本单元
8】
,其真值表如表3.4所示。给定3个输入变量的值,全
加器产生对应的2个输出值。3个输入变量X、Y、Cin分别代表2个本位输入和进位输入,2
个输出变量Z、Cout分别代表本位输出和进位输出。
表3.
4 全加器的真值表
X Y
Cin
Z
Cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
3→{2,
全加器是一个3输入2输出的布尔函数f:{0,1}0,1}函数映射
f
是
1 02 ◆计算机科学导论———以计算思维为舟
f(X ,Y,Cin)=
(0,0) X =0,Y=0,Cin=0
(0,1) X =0,Y=1,Cin=1
(0,1) X =1,Y=0,Cin=1
(0,1) X =1,Y=1,Cin=0
(1,1) X =1,Y=1,Cin=1
(1,0) 其他组合
ì
.
í
....
....
【实例3.9】 n 个输入m 个输出的布尔函数一共有多少个? 留作练习。
【实例3.10】 全加器的布尔表达式。
全加器有2个输出,可用2个布尔表达式刻画。假设3个输入变量X 、Y、Cin分别代表
2个本位输入和进位输入,2个输出变量Z、Cout分别代表2个本位输出和进位输出。那么,
全加器的2个布尔表达式是Z=X ..Y..Cin以及Cout=(X ·Y)+(X ..Y)·Cin。
可以看出,这种布尔表达式刻画比真值表枚举更加简洁,且体现了全加器的特点。
7. 布尔逻辑的应用
布尔逻辑主要关注针对布尔常数和布尔变量的逻辑运算。在应用中,往往体现为针对
单个比特的运算。我们做几个练习,通过动手动脑进一步理解布尔逻辑。
【实例3.11】 比特、字节与整数的异同。
理解比特、字节类型与整数类型的最简途径是编写运行一个短小程序。我们特别注意
Go语言的按位与运算&、按位或|、按位异或运算^。
给定下列Numbers.go程序,先心算或手算一下输出结果是什么,然后再运行程序
验证。
package main //Numbers.go
import "fmt"
func main() {
X := byte(63) //可将此行换成X := 63,理解整数类型
fmt.Printf("2+X=%d; 2-X=%d; X/2=%d; X%%2=%d\n",2+X,2-X,X/2,X%2)
fmt.Printf("X>>1=%d; X<<1=%d; ",X>>1,X<<1)
fmt.Printf("X&1=%d; X|1=%d; X^1=%d\n",X&1,X|1,X^1)
fmt.Printf("X>>1=%08b; X<<1=%08b; ",X>>1,X<<1)
fmt.Printf("X&1=%08b; X|1=%08b; X^1=%08b\n",X&1,X|1,X^1)
X++
fmt.Printf("X++ =%d\n",X)
X--
fmt.Printf("X-- =%d\n",X)
}
上述程序呈现了字节变量的算术逻辑运算。有两处需要注意的细节。第一,求余运算
的字符'%'已经被用于标记%d等占位符了,如何打印出表示求余运算的'%'字符? 答案是使
用%%。这是第一个打印语句出现了X%%2的原因。第二,如果一个字节类型的表达式
值超过了[0,255],即产生了溢出,系统会报错吗? 不会报错! 避免错误是程序员的责任。
第◆3 章 逻辑思维1 03
程序Numbers.go的输出结果如下:
> go run Numbers.go
2+X=65; 2-X=195; X/2=31; X%2=1
X>>1=31; X<<1=126; X&1=1; X|1=63; X^1=62
X>>1=00011111; X<<1=01111110; X&1=00000001; X|1=00111111; X^1=00111110
X++ =64
X-- =63
>
注意几个结果:①错误结果2-X=195,产生溢出但没有报错;②正确结果X/2=31,
而不是31.5;③X右移1位相当于X 除以2(X>>1=31);④X 左移1位相当于X 乘以
2(X<<1=126);⑤按位与X &1=00111111&00000001=00000001=1;⑥按位或
X|1=00111111|00000001=00111111;⑦按位异或X ^1=00111111^00000001=
00111110。
【实例3.12】 奇偶值。
一个数的奇偶值是看它有奇数个还是偶数个1比特。如有偶数个,奇偶值为0;如有奇
数个,则奇偶值为1。下列Go程序parity.go计算出parityValue=X0.. X1.. X2..…..
X63,给定64比特整数X =(X63X62…X0)2。注意,按位异或运算在Go语言中的符号是^。
package main //parity.go
import "fmt"
func parity(X int) int {
parityValue := 0
for i := 0; i<64; i++ { //X is a 64-bit integer
parityValue ^= X & 1 //parityValue = parityValue ^ (X & 1)
X = X >> 1 //shift X right one bit
}
return parityValue
}f
unc main() {
a := 63 //63 = 00111111,有6 个1,即偶数个1,奇偶值为0
fmt.Println(parity(a))
a = 127 //127 = 01111111,有7 个1,即奇数个1,奇偶值为1
fmt.Println(parity(a))
}
程序的执行结果如下。
> go run parity.go
01>
上述程序中,parityValue^= X&1语句是parityValue=parityValue^ (X&1)语句
1 04 ◆计算机科学导论———以计算思维为舟
的简写。其中,& 是按位与运算,^ 是按位异或运算。如X = (X63X62…X0)2 且Y =
(Y63X62…Y0)2,有X&Y=(X63∧Y63,X62∧Y62,…,X0∧Y0)2 且X^Y =(X63..Y63,X62..
Y62,…,X0..Y0)2。表达式X & 1保持最右1比特不变,将其他比特清零,即X&1=
(00…00X0)2。表达式X >>1将X 右移1比特,即X >>1=(0X63X62…X2X1)。
【实例3.13】 奇偶校验。
奇偶值可用作奇偶校验,即根据奇偶值报错。例如,ASCII 码只需要7 比特
D6D5D4D3D2D1D0,多出来的最高比特D7 可用作奇偶比特(paritybit)。大写字母A 的7
比特码是D6D5D4D3D2D1D0=1000001。假设规定奇偶值为0,我们有
D7..D6..D5..D4 ..D3..D2..D1..D0=0
D7..1..0..0..0..0..0..1=0
得到D7=0。A 加了奇偶比特之后的8比特码是D7D6D5D4D3D2D1D0=01000001。假
设硬件出错,使得某个比特翻转了,即0变成1或1变成0,奇偶校验可报错。例如,假如D6
变成了0,则有0..0..0..0..0..0..0..1=1,奇偶值是1,奇偶校验报错。
【实例3.14】 三模块冗余容错。
上述奇偶校验只能针对单比特故障报错。它不能指出是哪个比特错了,更不能纠错。
能够自动纠错的系统称为容错系统(faulttolerantsystem)。一种常用的容错技术是三
模块冗余(triplemodularredundancy,TMR)技术,如图3.3所示。
图3.3 三模块冗余容错技术示意
假设我们已经设计了一个系统Y=f(X63,X62,…,X0),想得到一个容错系统F。一个
简单的方法是将f 复制成3份(3个模块,其输出记为f1、f2、f3),并将f1、f2、f3 连到一
个多数票决模块(majorityvotingmodule),即可得到容错系统F。多数票决模块的功能是:
输出F=f1、f2、f3 的多数,即如果f1、f2、f3 的2个或3个为0,则F =0;反之F =1。这
个系统可以容忍模块1、模块2、模块3任一出错。
【实例3.15】 汉明码。
三模块冗余技术需要将一个系统视为模块完整复制成3份,大大增加了成本。有些技
术不需要完整复制整个系统。汉明码(Hammingcode)就是比三模块冗余成本低得多的容
错技术,由图灵奖得主理查德·汉明(RichardHamming)教授发明。
考虑单比特纠错的场景,汉明码的主要思想如下。假设一个系统产生m 个数据比特
(databits),其中某个比特可能出错。我们添加k 个奇偶校验比特(paritybits),形成总共
◆
第
3
章 逻辑思维105
m+
k
个比特的码字(codeword)。校验比特的巧妙设计,使得码字的任何比特出错,总会让
k
个校验比特形成的值指向码字中出错比特的位置。
由于码字一共有m+
k
个比特,加上未出错的1种情况,总共需要区分
m
+k+1 种情
=k=
况。因此,校验比特的个数
k
必须满足2k
≥
m
+k+1 。当
m
4时,3,冗余度(
m
+k)/
m=7/41.即需要75% 的额外比特用作校验。当m=k=冗余度降低到(
=75, 64 时,7,
m
+
k)/=1094,即需要10.512 时,
m=71/641.94% 的额外比特。当m=k=10,冗余度仅为71/
1.即仅需要1.64=0195, 95% 的额外比特。
5所示。4个数据比特记为
让我们仔细看看当
m
=4 与
k
=3 的情况,如表3.
D3D2D1D0,3个奇偶校验比特记为P2P1P0。注意码字中7个比特D3D2D1P2D0P1P0
的特定位置。
表3.
5 汉明码校验比特的编码原理示意
码字比特D3 D2 D1 P2 D0 P1 P0
位置7 6 5 4 3 2 1
二进制111 110 101 100 011 010 001
P0 √ √ √ √
P1 √ √ √ √
P2 √ √ √ √
表3.3个奇偶校验比特P2P1P0 按照下列汉明码规则求出。
5中,
(1)校验比特P0 对应其位置的二进制表示最低位(最右位)为1的比特。有4个位置
的二进制表示末位为1,即001 、011 、101 、111,对应的比特是P0、D0、D1、D3。这4个比特
的奇偶校验值应为0,即P0..D0..D1..D3。换言之,P0=D0..D1..D3。
(2)校验比特P1 对应其位置的二进制表示中间一位为1的比特。这4个位置是010 、
011 、110 、111,对应的比特是P1、D0、D2、D3。因此,P1=D0..D2..D3。
(3)校验比特P2 对应其位置的二进制表示最高位为1的比特。这4个位置是100 、
101 、110 、111,对应的比特是P2、D1、D2、D3。因此,P2=D1..D2..D3。
可以验证,当码字D3D2D1P2D0P1P0 的任何单个比特出错时,3个校验比特的值将
指向出错比特的位置。
例如,给定数据比特D3D2D1D0=1101,我们
有
P0=D0..D1..D3=1..0..1=
0
P1=D0..D2..D3=1..1..1=
1
P2=D1..D2..D3=0..1..1=
0
即,正确的原始码字是D3D2D1P2D0P1P0=1100110 。
当D1(码字位置5)出错,有错的数据比特D'3D'2D'1D'0=1111,我们从
D'
3D'
2D'
1D'
0 计算新的3个校验比特:
P″
0=D'
0..D'
1..D'
3=1..1..1=1
P″1=D'0..D'2..D'3=1..1..1=1
P″2=D'1..D'2..D'3=1..1..1=1
1 06 ◆计算机科学导论———以计算思维为舟
由于只考虑单比特纠错情况,当D1 出错时,码字的其他比特是正确的。因此,可能有
错的码字D'3D'2D'1P'2D'0P'1P'0 中的校验比特P'2P'1P'0 应与原来的校验比特一样,
即P'2P'1P'0 =P2P1P0 =010。对新校验比特P″2P″1P″0 与可能出错的校验比特
P'2P'1P'0 做按位异或操作,得出3个症状比特(syndromebits)S2S1S0:
S0=P″0..P'0=1..0=1
S1=P″1..P'1=1..1=0
S2=P″2..P'2=1..0=1
因此,S2S1S0=101=5,即第5号位置出错。系统只需翻转第5号比特即可纠错。
小结一下,汉明码的单比特纠错过程有下述主要事件。
(1)给定数据比特D3D2D1D0,按照汉明码规则计算出3个校验比特P2P1P0,形成原
始码字D3D2D1P2D0P1P0。
(2)原始码字的任何单个比特可能出错,即任何数据比特或任何校验比特可能出错,形
成可能有错码字D'3D'2D'1P'2D'0P'1P'0,其中包括可能有错数据比特D'3D'2D'1D'0,以
及可能有错校验比特P'2P'1P'0。
(3)按照汉明码规则从可能有错数据比特D'3D'2D'1D'0 计算出3 个新校验比
特P″2P″1P″0。
(4)从新校验比特P″2P″1P″0 与可能有错的校验比特P'2P'1P'0 得出3个症状比特
S2S1S0。当S2S1S0=000时,系统没有出错;当S2S1S0≠000时,S2S1S0 指向出错比特的
位置。例如,当S2S1S0=101=5时,第5号位置(即数据比特D1)出错;当S2S1S0=100=
4时,第4号位置(即校验比特P2)出错。
上述(7,4)汉明码在计算机内存中广泛使用,也称为ECC校验码,其中ECC是Error
CorrectionCode的缩写。
添加了ECC模块的内存纠错原理如图3.4所示,可分3种情况。
情况1:内存没有错误,则图3.45个步骤行为如下。
① 将4个数据比特D3D2D1D0 写入内存,同时算出校验比特P2P1P0 并写入内存。
例如,假设数据比特D3D2D1D0 =1101,则校验比特P2P1P0 =010。因此,原始码字为
D3D2D1P2D0P1P0=1100110。
② 若干时间后,从内存读出可能有错码字D'3D'2D'1P'2D'0P'1P'0。内存没有错误,
因此可能有错码字等于原始码字,即D'3D'2D'1P'2D'0P'1P'0 =D3D2D1 P2D0P1P0 =
1100110。
③ 算出新校验比特P″2P″1P″0=010。
④ 算出症状比特S2S1S0=000。
⑤ 因为S2S1S0=000,无须翻转任何码字比特。内存读出数据比特1101。
情况2:内存的某个数据比特出错,则图3.45个步骤行为如下。
① 同情况1。
② 从内存读出可能有错码字D'3D'2D'1P'2D'0P'1P'0。假设第5号位置(D1)出错,
则有错码字D'3D'2D'1P'2D'0P'1P'0=D3D2D'1P2D0P1P0=1110110。
③ 算出新校验比特P″2P″1P″0=111。
④ 算出症状比特S2S1S0=101。
第◆3 章 逻辑思维1 07
⑤ 由于S2S1S0≠000,翻转S2S1S0=101指向位置(5)的码字比特(D'1)。翻转D'1=
1后得到D1=0。因此,内存读出正确的数据比特1101。
情况3:内存的某个校验比特出错,则图3.45个步骤行为如下。
① 同情况1。
② 从内存读出可能有错码字D'3D'2D'1P'2D'0P'1P'0。假设第4号位置(P2)出错,
则有错码字D'3D'2D'1P'2D'0P'1P'0=D3D2D1P'2D0P1P0=1101110。
③ 算出新校验比特P″2P″1P″0=P2P1P0=010。
④ 算出症状比特S2S1S0=100。
⑤ 由于S2S1S0≠000,翻转S2S1S0=100指向位置(4)的码字比特(P'2)。因此,我们
依然看到内存读出正确的数据比特1101。
图3.4 (7,4)汉明码例子:ECC内存示意
【实例3.16】 在程序中使用掩码操作一字节的特定比特。
如何操作一字节中的特定比特? 使用掩码(mask)是一种常见方式。
让我们看一个具体例子:用字符'K'的每两比特替换掉数组A 的相应比特。
假设我们想在字节数组A = [0xD1,0xC9,0xDA,0xDA]中隐藏ASCII字符'K'=75=
01001011。一个做法是用'K'的每两比特替换掉目标字节的最低两比特。Go代码如下。
package main //replace.go
import "fmt"
func main() {
A := [4]byte{0xD1,0xC9,0xDA,0xDA}
fmt.Printf("Before: \tA = [%b %b %b %b]\n",A[0],A[1],A[2],A[3])
data := byte('K')
for i := 0; i < len(A); i++ {
1 08 ◆计算机科学导论———以计算思维为舟
v := data & 0x3 / /r etain last 2 bits of 'K' 使用掩码0x3
A[i] = A[i] & 0xFC / /c lear last 2 bits of A[i] 使用掩码0xFC
A[i] = A[i] | v / /s et last 2 bits of A[i] with those of 'K'
data = data >> 2 / /repeat with the next 2 bits of 'K'
}
fmt.Printf("After: \t\tA = [%b %b %b %b]\n",A[0],A[1],A[2],A[3])
}
程序执行结果如下。注意,字符'K' = 75 = 01001011。其中,'K'的11两比特藏在
A[0],10两比特藏在A[1],00两比特藏在A[2],01两比特藏在A[3]。
> go run replace.go
Before: A = [11010001 11001001 11011010 11011010]
After: A = [11010011 11001010 11011000 11011001]
>
该程序采用了制表符\t,使得两行输出对齐,便于比较替换前后数组A 的二进制值。
可以看出,每个数组元素只改变了最右2比特。我们聚焦for循环,只考虑i=0,其他i值是
类似的。当i=0时,data='K'=01001011且A[i]=A[0]=11010001。循环体的执行细节
如下。循
环体的第一条语句采用了掩码3,即0x3=00000011。按位与的结果是,变量data的
最右2比特保留下来,其他比特清零。
v := data & 0x3 //v= 01001011 & 00000011 = 00000011
//保留'K'的最右2 比特
循环体的第二条语句采用了掩码0xFC,即0xFC = 11111100。按位与的结果是,变量
A[0]=11010001的左边6个比特保留下来,最右2比特清零,A[0]=11010000。
A[i] = A[i] & 0xFC //A[i]=11010001 & 11111100 = 11010000
//将A[i] 的最右2 比特清零,左边6 比特不变
第三条语句采用按位或,将两个掩码操作结果拼起来,即将A[0]保留下来的左边6比
特,与'K'保留下来的最右2比特,拼在一起。这就实现了“将'K'最右2比特替换A[0]的相应
比特”的操作。
A[i] = A[i] | v / /A[i]=11010000 | 00000011 = 11010011
//用'K'最右2 比特替换A[0]的相应比特
3.1.2 谓词逻辑
谓词逻辑(predicativelogic)也称为一阶逻辑(first-orderlogic)。它拓展了命题逻辑。
与简单命题逻辑相比,谓词逻辑还额外包含了断言和量化。
第◆3 章 逻辑思维1 09
所谓断言是一个会传回“真”或“假”的函数。考虑下列句子:“苏格拉底是哲学家”“柏
拉图是哲学家”。在命题逻辑里,上述两句被视为两个不相关的命题,分别记为p 及q。在
一阶逻辑里,上述两句可以使用断言以更加相似的方法来表示:如果用Phil(x)表示x 是哲
学家,那么,若a 代表苏格拉底,则Phil(a)为第一个命题p;若b 代表柏拉图,则Phil(b)为
第二个命题q。
所谓量化通过量词来体现。在自然语言中我们常常会使用“所有”“某些”等量词,在谓
词逻辑中有两个量词,分别是全称量词.和存在量词.。前者等同于“每一个”“所有”“一
切”等,后者等同于“存在着”“至少有一个”。
【实例3.17】 任何一个自然数,要么它本身为偶数,要么加1后为偶数。
.n[Even(n)∨Even(n+1)],其中断言Even(n)表示n 是偶数。
【实例3.18】 存在末4位是9999的素数。
.n[Prime(n)∧(n≡9999(mod104))],其中断言Prime(n)表示n 是素数。
一个命题中可以存在多个量词。有多个量词的命题中,量词的顺序将可能表达完全不
同的含义,因此不能随意修改量词的顺序。请看下面的例子,其中第一个是真命题,第二个
是假命题。
【实例3.19】 对于任意x,都存在y,使得y=x+1。
.x,.y(y=x+1)。
【实例3.20】 存在一个y,对于任意的x,都有y=x+1。
.y,.x(y=x+1)。
量词的范围。我们可以为每个量词后面的变量指定一个特定的取值范围,这个范围被
称为这个变量的论域或量化范围。
【实例3.21】 任意有理数都可以写成两个整数的商。
.x∈Q,.p,q∈Z x=p
q
é
. êê
ù
. úú
(Q、Z分别代表有理数集合和整数集合,下同)。
其中,变量x 的论域为有理数,p 和q 的论域为整数。
【实例3.22】 存在无穷多个素数。
.n∈N,.m ∈N,.p,q∈N,p,q>1[(m >n)∧(m ≠pq)](N代表自然数集合,
下同)。
解释:这里用m 表示所论述的素数。一个自然数是素数意味它不能写成两个大于1
的自然数的乘积。因此,在表达式中,将其写为任意两个大于1的自然数p 和q 的乘积都不
等于m 。为了表达出这样的m 有无穷多个,我们引入一个中间变量n,不论n 有多大,总是
有比它更大的素数m 存在。
【实例3.23】 对于n>2,丢潘图方程xn +yn =zn 不存在非平凡整数解。
.a,b,c,n∈Z[(abc≠0)∧(n>2)→(an +bn ≠cn)]。
解释:丢潘图方程的平凡解是指x、y、z 中有一个变量为0的整数解,对于这里讨论的
费马方程xn +yn =zn 这类解总是存在的,例如x=0,y=z,因此我们更关心一个丢潘图方
程是否存在非平凡的整数解。“不存在”等价于“任意……都不”,上述式子用“任意a、b、c
都不”来替代“不存在a、b、c”,上式中我们用abc≠0来表示a、b、c 都不等于0。
上述例子中我们使用了如下性质。
1 10 ◆计算机科学导论———以计算思维为舟
性质:..(.xF(x))=.x..F(x),..(.xF(x))=.x..F(x)。
【实例3.24】 存在无穷多对孪生素数。
.n∈N,.m ∈N,.p,q∈N[(m >n)∧((p,q>1)→(pq≠m )∧(pq≠m +2))]。
解释:孪生素数是指差为2的两个素数。在上式中,对于任意两个大于1的正整数p
和q,m 和m +2都不能表示成它们的乘积,也就是说m 和m +2是一对孪生素数。而对于
任意大的n,总是存在比它大的m ,保证m 和m +2是一对孪生素数,这样就刻画了孪生素
数有无穷多对。注:此猜想被称为“孪生素数猜想”。
【实例3.25】 对于任何一个正整数n,如果是奇数则乘3并加1,如果是偶数则除于2,
重复此过程最终总可以得到1。
.n,.m ,[f(m)(n)=1],其中f(n)=
3n+1, n≡1(mod2)
n2
, n≡0(mod2)
ì
.
í ..
..
解释:这里f(m)(n)表示将f 复合作用在n 上m 次,即f(f(…f(n)…))。这个猜想
被称之为“角谷猜想”,或者“奇偶归一猜想”“3n+1猜想”等,目前这个猜想还未被解决。
3.2 图灵机模型
3.2.1 定理机器证明与吴方法
机器证明,又称数学机械化,要求在证明过程中,每前进一步之后,都有一个确定的规则
来选择下一步,沿着这一路径前进,最终到达需要的结论。通过这样方式,人们希望回避开
那些技巧性极强的数学证明,用现代计算机强大的计算能力来取而代之。
机器证明的思想可以回溯到17世纪法国数学家笛卡儿(ReneDescartes,1596—1650)。
笛卡儿曾经有过一个伟大的设想:“一切问题都可以化为数学问题,一切数学问题都可以化
为代数问题,一切代数问题都可以化为代数方程的求解问题。”笛卡儿并没有只停留在空想,
他所创立的解析几何,建立了空间形式和数量关系之间的桥梁,实现了初等几何问题的代数
化求解。
20世纪初希尔伯特(DavidHilbert,1862—1943)更明确地提出了公理系统的机械化判
定问题:给定一个公理系统,是否存在一种机械的方法(即现在所谓的算法),可以验证每一
个命题是否为真? 在下面章节我们将会看到,希尔伯特的要求太高了。哥德尔不完备性定
理指出:能对所有的命题进行机械化判定的方法是不存在的。
虽然希望使用一个算法来对所有的命题进行判定是做不到了,但是针对一些特定领域
的具体的问题,使用机械化的方法仍然是可行的。例如,吴文俊先生提出的以多项式组零点
集为基本点的消元方法(吴方法)可以应用于大量几何定理的机器证明。
图论中著名的四色定理断言:任何平面图都可以4染色,使得任何相邻的顶点都不同
色。四色定理最早由格斯里(FrancisGuthrie,1831—1899)在1852年提出,这个问题困扰
了数学家一百多年,最终在1976由阿佩尔(KennethAppel)和哈肯(WolfgangHaken)利用
计算机所证明。他们证明的思路是这样的:如果在一张平面图中出现了某种特定的结构,
那么他们就可以把这一个局部用一个更小的结构替代(即对原图进行约简),同时保持4染
◆
第
3
章 逻辑思维111
色性质的不变。也就是说,如果新的图能够被4染色,那么原来大的图也可以被4染色。例
如,一个度不大于3的顶点就要可以被去掉,因为它不会影响整张图是否可以被4染色。阿
佩尔和哈肯证明,一共有1936 张互相不可约简的平面图,对于其他任何一张平面图,总可以
通过不停地约简图中特定的结构,最终到达这1936 张图中的某一张。最后他们借助计算机
的帮助,经过超过1000 小时的计算,终于验证了所有这1936 张图都可以被4染色,进而证
明了四色定理。四色定理是第一个用计算机辅助证明的数学定理。
2.有穷自动机
3.2
在介绍图灵机之前,让我们从一个简单的自动售卖机开始:一台自动售卖机可以售卖
多种商品,可以接受多种币值的纸币或者硬币,同时还可以找零。为了简化问题,我们假设
自动售卖机只卖两种商品———可乐和饼干,可乐的价格是5元1听,饼干的价格是10 元一
包,假设售卖机只能接受5元和10 元的纸币,同时任何时刻售卖机内部剩余的金额最多不
超过10 元。
让我们用一种数学化的语言来描述自动售卖机的工作原理,我们用一些状态来表示自
动售卖机的状态。首先售卖机有一个初始状态,我们将其记作q0。如果此时用户塞入一张
5元的纸币,售卖机将进入一个新的状态,为了区分该状态与q0 的区别,我们将这一个状态
记作q1。如果在状态q1 下用户选择购买一听可乐,那么售卖机将吐出一听可乐,并回到状
态q0。另一方面,如果在q1 状态下用户再塞入5元,那么售卖机内一共有10 元,从而进入
另外一个状态q2,现在用户可能会选择购买可乐(或者饼干), 那么售卖机将吐出可乐(或者
饼干), 并根据剩余的金额进入相应的状态q1(或者q0)。在任何状态下,如果用户选择“终
止交易”,则售卖机会退回剩余金额,并回到q0 状态。
相比于上面的状态转移规则,状态转移图(图3.更加清晰并简洁描述了售卖机的
功能。
5)
图3.
5 售卖机的状态转移图
其中,箭头(→)前面表示售卖机的输入,箭头后面表示售卖机的动作。例如,在q2 到
q1 的路径上的“买可乐→可乐”表示如果售卖机在q2 状态,用户选择购买可乐,则售卖机跳
◆
112
计算机科学导论———以计算思维为舟
到q1 状态并吐出一听可乐。
自动售卖机所对应的计算模型被称为“有穷自动机”,也称为有限状态自动机(finite
stateautomata)。这一计算模型基本上可以看作和我们计算机的CPU对应,但它的一个重
要不足是该模型没有计算机的“内存”,也就是说没有存储器,只能通过自动机的状态来做
存储。
2.图灵机
3.3
在前面的章节中我们通过介绍布尔逻辑和一阶逻辑,使得大家对逻辑有了初步的了解,
我们看到所有的数学问题、所有的计算和证明推导过程都可以使用逻辑的语言来精确地描
述,我们也看到了使用“机器”可以自动地来证明一些数学定理,我们也提到了希尔伯特的
“公理系统机械化判定的思想”,到底希尔伯特心目中的通用的“机器”是什么样子?1936年
图灵给出了他的回答———图灵机。
图灵机既有处理器(CPU)也有存储器(内存)。下面我们严格定义图灵机。
【定义3.图灵机。
4】
图灵机是一个七元组:{Q,Γ,q0,apqeet},其中,Q、Σ、
Γ
都是有限集合,
B
是
空白字符(Blank)的记号。
Σ,δ,qcet,rjc
(1)状态集合:Q。
(2)输入字母表:Σ。
(3)带字母表:Γ,其中B∈Γ。
(4)转移函数:Q-{apqejc})×Σ→Q×Γ×{→,←}。
δ:(qcet,ret
(5)起始状态:q0∈Q。
(6)接受状态:qacep。
(7)拒绝状态:qreject。(t)
图灵机(单带)是这样完成计算任务的:给定一个写有输入的右端无限长纸带,图灵机
从纸带上输入的最左端出发,从初始状态开始,按照转移函数进行状态转移以及左右移动和
写操作,最终进入接受状态或者拒绝状态。■
也可以用状态转移图来描述图灵机(下面的讨论中,我们都用状态转移图来描述图灵机)。
【26】
实例3.判定一个0-1字符串中包含1的个数是奇数还是偶数
。
分析:可以用两个状态来区分当前已经读过的
串
中1的个数是奇数还是偶数,如图3.
6所示
。
其中,表示目前读到了偶数个1;dd表示目
前
qqo读到了奇数个(e) 1(n) 。自动机初始状态为q(e) (v) even。任意状
态
下,读到1就会跳到另一个状态
。
【实例3.m0n
,判断
m
是否等于图3.6 状态转移图:已经读过的串中
27】给定字符串
1
n,如果m=
n
输出Yes,否则输出No 。1的个数是奇数还是偶
数
分析:最容易想到的方法是先统计1和0的个数,
然后再比较。但是图灵机只有有限的存储(控制器中的状态),不可能只使用内部状态来记
录下字符串中所有的1或者0(事实上可以证明,如果只用内部状态做记录,即不能对纸带
◆
第
3
章 逻辑思维113
进行写操作的话,图灵机是不可能完成这个任务的)。所以如果想统计字符串中1和0的个
数,可以开辟纸带上某个空白的地方做计数器。但是这样的图灵机的状态转移图画出来太
复杂。
方案1:一种不需要统计1和0的个数,直接来判断1的个数和0的个数是否相同的方
法。具体的做法是:将0和1进行配对(即建立一个1-1对应), 如果能够完全配对,则0和
1一样多,否则不一样多。图灵机的设计如图3.
7所示。
图3.
7 方案1图灵机状态转移图
图灵机读写头初始在纸带的最左端,然后往右移动,如果读到1,置为#,然后继续往右
移动直到读到0,替换为$,或者没有读到0,这时就可以断定1的个数和0的个数不相等,
输出No(N)。然后读写头再回到纸带的左端重复上述过程,直到最后如果纸带上只剩下1
或者0,则输出No(N), 如果纸带上既没有0也没有1,那么输出Yes(Y)。
不难看出,如果输入的字符串为1n0n
, n2)。
图灵机的运行步数为O(
方案2:采用二分法的思想,将判断“
m
=n?” 转化为比较
m
和
n
在二进制下的每一比
特是否都相等。这里有一个问题,如何才能够得到
m
和
n
在二进制表示下的某一位是什
么? 图3.它不需要把
m
和
n
先算出来,
8给出了一个巧妙的方法, 就可以给出每一位。具
图3.
8 方案2图灵机状态转移图