计算机科学导论-计算思维程序实践 课件 第3、4讲-从加法自动计算看机器硬件实现-逻辑运算与逻辑门电路、从多项式计算规则变化看自动计算-规则与迭代

第3讲从加法自动计算看机器硬件实现

—逻辑运算与逻辑门电路哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣计算机是怎样完成计算的？示例计算机器是怎样完成加法运算的，你知道吗？0+0=00+1=11+0=11+1=10逻辑是指事物因果之间所遵循的规律，是现实中普适的思维方式逻辑的基本表现形式是命题与推理，推理即依据由简单命题的判断推导得出复杂命题的判断结论的过程。【命题】一个命题由语句表述，即内容为“真”或为“假”的一个判断语句！【命题的运算】如果命题由X,Y,Z等表示，其值可能为“真”或为“假”，则两个命题X,Y之间是可以进行运算的：【与】运算(AND):当X和Y都为真时,XANDY也为真;其他情况,XANDY均为假。【或】运算(OR):当X和Y都为假时,XORY也为假;其他情况,XORY均为真。【非】运算(NOT):当X为真时,NOTX为假;当X为假时,NOTX为真。【异或】运算(XOR):当X和Y都为真或都为假时,XXORY为假;否则,XXORY为真。“与”运算：两把钥匙都有才能开门“或”运算：只要有任何一把钥匙便能开门计算机的本质是逻辑【逻辑】与基本逻辑运算用0和1来表示逻辑运算【AND】：“与”运算有0为0，全1为1【OR】：“或”运算有1为1，全0为0【NOT】：“非”运算非0则1，非1则0【XOR】：“异或”运算相同为0，不同为1注:1表示真，0表示

假

0AND 0 0 0AND 1 0

1AND 0 0 1AND 1 1

1OR 1 1

1OR 0 1 0OR 1 1

0OR 0 0NOT 0 1NOT 1 0

1XOR 1 0

1XOR 0 1

0XOR 1 1

0XOR 0 0计算机的本质是逻辑0和1的计算：基本逻辑运算二进制的加法运算规则

Ai+BiCi+1SiSi=(AiXORBi)XORCiCi+1=((AiXORBi)ANDCi)OR(AiANDBi)Si=AiXORBiCi+1=Ai

ANDBi不考虑进位考虑进位AiBi+CiCi+1Si用基本逻辑运算实现复杂计算【示例】二进制加法运算可用逻辑计算来实现你能证明一下吗？Si=(AiXORBi)XORCiCi+1=((AiXORBi)ANDCi)OR(AiANDBi)考虑进位AiBi+CiCi+1Si用基本逻辑运算实现复杂计算【枚举-计算-验证】证明复杂逻辑运算的正确性AiBiCi

加法规则的Si

逻辑运算规则的Si

加法规则的Ci+1

逻辑运算规则的Ci+1

00000000011100010110001100111001100101001111000111111111电信号：0V（低电平）

和5V（高电平）01用二极管、三极管实现基本逻辑运算的电路【与门】电路【或门】电路【非门】电路F

=A

ANDBF

=A

ORBF

=NOTA这些电路被封装成集成电路(芯片)，即所谓的逻辑门：【与门】、【或门】和【非门】。用电子技术实现基本逻辑运算基本逻辑运算的电子实现：逻辑门1Y

=1A

AND1B2Y

=2A

AND2B3Y

=3A

AND3B4Y

=4A

AND4B【与门】电路F

=A

ANDB&【与门】电路符号左侧是输入，右侧是输出用电子技术实现基本逻辑运算集成电路示意=1&≥11【与门】电路符号【或门】电路符号【非门】电路符号【异或门】电路符号≥1注意：左侧是输入，右侧是输出输入是电信号的0或者1，输出是对输入做相应的运算，也是电信号的0或者1用电子技术实现基本逻辑运算逻辑门的符号表示注意门电路符号的左输入右输出一位加法器的示例加法运算是这样实现的二进制加法运算用逻辑门电路的组合来实现疑问1：这个电路符号是什么？疑问2：为什么前面1个非门后面又有一个非门，有意义吗？疑问3：这个电路正确吗？怎样验证其正确性呢？101101001AiBi+CiCi+1Si枚举-计算-验证：通过枚举所有可能的输入，可验证一位加法器实现的正确性1加法运算是这样实现的二进制加法运算用逻辑门电路的组合来实现多位加法器的实现用已验证正确的一位加法器，来实现更为复杂的多位加法器用已验证正确的多位加法器，来实现更为复杂的乘法器/除法器等(略)

【分层构造】低层电路已验证正确，可被封装起来；用已封装的已验证的低层电路可构造更为复杂的高层电路；如此一层层构造。用逻辑实现加法，用硬件实现加法?(5)如何用已实现的基本逻辑运算(门电路)来实现更复杂的运算?0

01

0

1

1

100+110A3A2A1B3B2B1S3S2S1+C4C3C2C1加法运算是这样实现的二进制加法运算用逻辑门电路的组合来实现A1B1C1S1C2A2B2C2S2C3A3B3C3S3C4摩尔定律：芯片可容纳的晶体管数目大约每经过18个月便会增加一倍：2021年达到的规模一块芯片4.6万亿颗晶体管集成电路是这样复杂起来的集成电路是这样的…疑问：为什么需要这么多晶体管？语义符号化

符号计算化

计算0(和)1化0(和)1自动化

分层构造化

构造集成化计算机的本质是逻辑小结：符号化、计算化与自动化第4讲从多项式计算规则变化看自动计算

—规则与迭代哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣两个对象：数据与计算规则三个机制:表示-存储-执行数据

的表示：进位制与编码计算规则的表示：程序数据与计算规则的自动存储计算规则/程序的

自动执行两对象-三机制自动计算要解决什么问题规则越简单，越容易造出机器单一规则简单，但可重复运用能够自动计算的机器-怎样造?nn2一阶差分

n=n2-(n-1)2二阶差分

n=n-n-1

0 01 12 43 94 165 25135792222(n+1)2=n2+

n+n用简单计算规则（如加减法运算）求解复杂计算问题（如乘方运算和多项式运算）例如：求n2示例：怎样计算多项式的值-差分法计算规则nF(n)一阶差分

n=F(n)-F(n-1)二阶差分

n=n-n-1

0 31 62 113 184 275 383579112222F(n+1)=F(n)

+

n+n例如:求F(x)=x2+2x+3初始值不一样，可计算不同的多项式用简单计算规则（如加减法运算）求解复杂计算问题（如乘方运算和多项式运算）计算规则示例：怎样计算多项式的值-差分法/*类C语言表达的计算规则—程序Main(){intk,n,F[],alpha[],beta[];inputk;F[0]=3;F[1]=6;F[2]=11;alpha[1]=3;forn=2tok-1{alpha[n]=F[n]-F[n-1];beta[n]=alpha[n]-alpha[n-1];F[n+1]=F[n]+alpha[n]+beta[n];

}outputF[k]; }F[0]保存F(0)的值F[1]保存F(1)的值F[2]保存F(2)的值F[3]……F[4]F[5]…数组变量，可以按序号保存多个值能够保存数据能够完成计算能够重复进行变量，是程序执行过程中其值可发生变化的量计算规则表达与执行计算规则表达【程序】与计算规则执行【计算机器】Q：保存的数据随K值增大而增多,怎么办?T：输入不同的初始值便可计算不同的一元二次多项式的值/*类C语言表达的计算规则—程序Main(){intk,n,F_nminus1,F_n,F_nplus1,intalpha_nminus1,alpha_n,beta_n;inputk;F_nminus1=1;F_n=4;alpha_nminus1=1;forn=2tok-1{alpha_n=F_n–F_nminus1;beta_n=alpha_n–alpha_nminus1;F_nplus1=F_n+alpha_n+beta_n;F_nminus1=F_n;F_n=F_nplus1; alpha_nminus1=alpha_n;}outputF_nplus1; }F_nminus1类似的，就是一个变量名，可任意命名，可保存一个数值F[0]保存F(0)的值F[1]保存F(1)的值F[2]保存F(2)的值F[3]……F[4]F[5]…占用n个变量保存n个数值F_n只用1个变量保存当前数值计算规则表达与执行怎样用更少的变量来实现自动计算—降低机器构造的复杂性？保存的数据不随K值变化而变化轮流计算新值为下次计算保留相关数据nF_nalpha_nbeta_nF_nminus1alpha_nminus1F_nplus1294131239453216492575216516369722536925

计算规则表达与执行迭代式方法的执行过程由机械计算机到电子计算机自动计算的探索巴贝奇现代计算机：一般程序--任意可变的计算规则Pascal机械计算机:第一台机械计算机-能够自动完成计算Babbage分析机:特定程序--可有限变化的计算规则莱布尼茨机械计算机:自动计算--固定