计算机科学中创新的逻辑

1、计算机科学中计算机科学中赵沁平赵沁平 创新研究的对象创新研究的对象 已有理论已有理论 自然世界自然世界 人类活动人类活动 创新的类型创新的类型 发现发现 发明发明 发展发展 指出指出 提出提出 构造构造 证明证明 改进改进 原始创新原始创新 改进完善改进完善创新的条件创新的条件 激情、毅力、知识、智慧激情、毅力、知识、智慧 了解所研究的对象了解所研究的对象 特性特性 存在条件存在条件 与其他事物的关系与其他事物的关系 已有研究结果已有研究结果 研究对象是已有论断研究对象是已有论断 分析已知论断分析已知论断 怀疑怀疑 不满不满 猜想猜想 找反例找反例 改进改进 证明证明创新的起步创新的起步 怀疑

2、已有的论断，寻找它们与客观怀疑已有的论断，寻找它们与客观实际不符或矛盾之处，进而指出其存在实际不符或矛盾之处，进而指出其存在的问题或推翻该论断，这本身也是一种的问题或推翻该论断，这本身也是一种创新工作。创新工作。例例1 1 找到找到XXXXXX教授在可计算理论研究中提出的一条教授在可计算理论研究中提出的一条公理的反例，从而推翻了他的这一公理。公理的反例，从而推翻了他的这一公理。 XXX在计算机研究与发展1988年第11期“什么是可计算性”一文中针对丘奇-图灵论题的公理化问题，在M.Blum四条公理的基础上，提出了一条新的公理： 一组可计算函数一组可计算函数fifi 如果有最小上界如果有最小上界

3、g g，则，则g g也是可计算的。也是可计算的。注 如果两个函数 f 和 g 的值相等，而f的定义域小于g，则定义f小于g，用fg表示。设fi是一组函数，g是一个函数。满足：fig（一切i）则g叫这组函数的一个上界。如果g是fi的上界，而且对fi的任何上界h，gh，则说g是fi的最小上界。选择一个不可计算函数g，其定义域 D 是可数无限的。我们取该定义域的一个有限部分D1作为新的定义域，可以得到函数f1，f1g，由于D1是可数有限的，因此f1一定是可计算的。再将D1在D上适当扩大为D2，可得到函数f2，则有f1f2，且f2g。如此重复可以的到一组可计算函数fi，fi的最小上界显然是g，而g是一

4、个不可计算函数。因此马提出的公理是不成立的。 研究研究对象是自然世界或人类活动对象是自然世界或人类活动 了解问题了解问题 确定目标确定目标 合理假设合理假设 创新研究创新研究 计算机学科面向自然世界和人类活动，计算机学科面向自然世界和人类活动，研究内容丰富多彩，方法各种各样，是产生研究内容丰富多彩，方法各种各样，是产生原始创新的源泉。其主要创新目标有三个方原始创新的源泉。其主要创新目标有三个方面面 使计算机系统：使计算机系统： 更高效更高效 更聪明更聪明 更适人更适人创新的方法创新的方法1 1、概念形成、概念形成 概念形成、判断、推理是思维的三种基本形概念形成、判断、推理是思维的三种基本形式，

5、各自代表了理性认识的一个阶段。式，各自代表了理性认识的一个阶段。 概念的形成是人的认识过程由低级的感性认识概念的形成是人的认识过程由低级的感性认识上升到高级的理性认识的一次质的飞跃。概念不同上升到高级的理性认识的一次质的飞跃。概念不同于感觉的特征，在于概念的抽象性和概括性。于感觉的特征，在于概念的抽象性和概括性。概念的内涵与外延概念的内涵与外延 内涵和外延是概念的两个方面，是概念的基本内涵和外延是概念的两个方面，是概念的基本逻辑特征。逻辑特征。 概念的内涵是概念所反映的对象的共同属性的概念的内涵是概念所反映的对象的共同属性的总和；概念的外延是概念所反映的对象的总和。总和；概念的外延是概念所反映

6、的对象的总和。 概念的内涵与外延之间有反比关系。即增加内涵概念的内涵与外延之间有反比关系。即增加内涵（属性），其外延会缩小；减少内涵，外延会增大。（属性），其外延会缩小；减少内涵，外延会增大。定义定义 定义是认识主体使用命题的语言逻辑形式，定义是认识主体使用命题的语言逻辑形式，指指出对象的本质属性，把这一对象和其他与之相似的出对象的本质属性，把这一对象和其他与之相似的对象区别开。下定义的方法有两大类，一是逻辑方对象区别开。下定义的方法有两大类，一是逻辑方法，即属概念加种差定义；一是发生定义。法，即属概念加种差定义；一是发生定义。 定义概念是定义问题、研究问题的基础，概念定义概念是定义问题、研究

7、问题的基础，概念定义的方法和水平直接影响后续的创新研究。定义的方法和水平直接影响后续的创新研究。 属概念加种差定义属概念加种差定义 由被定义概念的最邻近的属概念加种差构成的定义。由被定义概念的最邻近的属概念加种差构成的定义。 例如，堆栈是一个下限为常数，上限可变化的向量。例如，堆栈是一个下限为常数，上限可变化的向量。 发生定义发生定义 是属概念加种差定义的特殊形式。发生定义所列举的属性是属概念加种差定义的特殊形式。发生定义所列举的属性（种差）是被定义概念所反映的对象的发生过程。（种差）是被定义概念所反映的对象的发生过程。 例如，递归过程是一个直接或间接调用自身的过程。例如，递归过程是一个直接或

8、间接调用自身的过程。 定义时必须遵守的逻辑规则定义时必须遵守的逻辑规则 定义不能包含被定义概念本身或和它意义相同定义不能包含被定义概念本身或和它意义相同的概念，否则就是同语反复。的概念，否则就是同语反复。 必须采用科学的、确定的术语和概念，不能用必须采用科学的、确定的术语和概念，不能用比喻和模糊的语言。比喻和模糊的语言。 必须用肯定语，不能用否定语。必须用肯定语，不能用否定语。 聚类与分类聚类与分类 聚类：概念形成聚类：概念形成 分类：形成子概念分类：形成子概念 分类的关键是选定分类特征分类的关键是选定分类特征 分类首先要确定其分类特征，如果分类特征不分类首先要确定其分类特征，如果分类特征不明

9、确就不是好的分类法明确就不是好的分类法。 分类（子概念）要尽可能成为一种对概念外延分类（子概念）要尽可能成为一种对概念外延的划分（没有遗漏，也没有重叠）。的划分（没有遗漏，也没有重叠）。 用于分类的特征应当是所属领域的一些本质特用于分类的特征应当是所属领域的一些本质特性。对于计算机学科来说，要性。对于计算机学科来说，要从数据类型、信息流从数据类型、信息流向、计算模型等计算特性的角度进行分类向、计算模型等计算特性的角度进行分类。 科学地形成概念，本质地进行分类就是一种创新。科学地形成概念，本质地进行分类就是一种创新。例例2 2 计算机体系结构的分类计算机体系结构的分类 以指令流和数据流为分类特征

10、以指令流和数据流为分类特征 单指令流单数据流单指令流单数据流 SISD SISD 冯冯 诺依曼体系结构诺依曼体系结构 单指令流多数据流单指令流多数据流 SIMD SIMD 向量（阵列）机向量（阵列）机 多指令流单数据流多指令流单数据流 MISD MISD 流水线处理流水线处理 多指令流多数据流多指令流多数据流 MIMD MIMD 多处理机系统多处理机系统 以指令的驱动方式（计算模型）为分类特征以指令的驱动方式（计算模型）为分类特征 控制驱动控制驱动 数据驱动数据驱动 需求驱动需求驱动例例3 3 关于虚拟实体的分类关于虚拟实体的分类 动态实体动态实体 ？ 静态实体静态实体 人在环实体人在环实体

11、CGF 实况实体实况实体 上述分类就不是从计算本质的分类。上述分类就不是从计算本质的分类。问题：问题：分布式计算的分类，网络计算、网格计算、 云计算从计算角度的区别是什么？2 2、演绎法、演绎法 特殊化方法特殊化方法 证明一个对象属于某概念，因而具有该概念的内涵属性的逻辑方法。是从一般到个体的推理。是从一般到个体的推理。 在计算机科学研究中常对应用范围较宽，但效率相对较低的方法，根据具体情况增加一些约束条件，适当缩小论域，然后寻找效率较高的方法。 G(xG(x)| )| G(xG(x)| )| 一个算法程序、一个封闭的软件系统都一个算法程序、一个封闭的软件系统都是演绎系统，典型的是一个逻辑式程

12、序，如是演绎系统，典型的是一个逻辑式程序，如Prolog Prolog 程序。程序。 在虚拟现实研究中，特殊化方法是一种在虚拟现实研究中，特殊化方法是一种常用的改进或实用化创新方法。常用的改进或实用化创新方法。例例4 4 半动态对象绘制的半动态对象绘制的LOMLOM方法方法 在绘制半动态对象，如随风摆动的树林时，为在绘制半动态对象，如随风摆动的树林时，为增强实时性，对视距进行划分，不同视距范围采用增强实时性，对视距进行划分，不同视距范围采用不同的运动模型，远距离的树枝不动，中距离的树不同的运动模型，远距离的树枝不动，中距离的树枝摆动，近距离的树枝摆动加扭动。从而既提高了枝摆动，近距离的树枝摆动

13、加扭动。从而既提高了效率，又保证了视觉效果。效率，又保证了视觉效果。3 3、归纳法、归纳法 泛化（扩张）方法泛化（扩张）方法 从若干同类对象的共同属性得到该类整体属性的逻辑方法。是从个体到一般的推理。是从个体到一般的推理。 计算机科学研究中常对考虑因素较多、适用范围较窄的方法，忽略一些因素（约束），得到适用范围较宽的方法。 G(xG(x)| )| G(x G(x)| )| 对论域限定较窄的方法，根据具体应用适当扩对论域限定较窄的方法，根据具体应用适当扩大论域，然后寻求新的方法，也即得到适用范围更大论域，然后寻求新的方法，也即得到适用范围更宽的方法。宽的方法。 G(x)G(x)， x x a,b

14、a,b a,b a,b a,ba,b G(y)G(y)，y y a,ba,b例例5 5 我们扩展布尔函数的值域，得到模我们扩展布尔函数的值域，得到模糊糊逻辑函数和模糊逻辑方程逻辑函数和模糊逻辑方程 布尔函数布尔函数f f的变量值域是的变量值域是00，11，将其扩展为，将其扩展为0,10,1区间上的实数就得到模糊逻辑函数区间上的实数就得到模糊逻辑函数 。 令：令： = = 0,10,1得到模糊逻辑方程。得到模糊逻辑方程。4 4、结合法、结合法 将针对同一问题的两种不同解决方法相结合，将针对同一问题的两种不同解决方法相结合，得到新的方法。得到新的方法。 E(x),F(xE(x),F(x) G(E(

15、x),F(x) G(E(x),F(x) 将一种方法引入另一种方法，得到新方法。将一种方法引入另一种方法，得到新方法。 G(x,y),F(xG(x,y),F(x) G(x,F(z),) G(x,F(z),例例6 6 在新型程序设计语言在新型程序设计语言KLNDKLND中将逻辑式与函中将逻辑式与函数式两种程序设计风格相结合。数式两种程序设计风格相结合。 逻辑式与函数式两种风格的程序设计语言是人工智能中逻辑式与函数式两种风格的程序设计语言是人工智能中常用的两类语言，常用的两类语言，基于不同的数学模型，前者是一阶谓词演基于不同的数学模型，前者是一阶谓词演算，后者是算，后者是 演算，这演算，这使得它们使

16、得它们在知识表示和处理方面在知识表示和处理方面具备各具备各自的优点，分别适用于不同的应用领域。我们把两种程序设计自的优点，分别适用于不同的应用领域。我们把两种程序设计风格结合起来，以提高语言的表达能力。风格结合起来，以提高语言的表达能力。 两者可以有机结合，不是机械地凑在一起的基础是它们的两者可以有机结合，不是机械地凑在一起的基础是它们的计算模型是可以统一的，函数是特殊的关系，关系又是以真、计算模型是可以统一的，函数是特殊的关系，关系又是以真、假为值的函数；同时参数传递机制模式匹配与合一相容。假为值的函数；同时参数传递机制模式匹配与合一相容。 例例7 7 将类比方法引入启发式搜索，得到基于类将

17、类比方法引入启发式搜索，得到基于类比的启发式搜索方法。比的启发式搜索方法。 启发式搜索方法是启发式搜索方法是利用与待求解问题有关的信息，对搜索利用与待求解问题有关的信息，对搜索路径的取向给予一定选择的搜索方法。启发式方法提高了搜索路径的取向给予一定选择的搜索方法。启发式方法提高了搜索效率，在许多领域，特别是人工智能应用中取得了良好效果，效率，在许多领域，特别是人工智能应用中取得了良好效果，成为人工智能的主要技术之一。成为人工智能的主要技术之一。 我们将类比推理引入我们将类比推理引入启发式搜索，提出一种基于类比推理启发式搜索，提出一种基于类比推理的启发式搜索方法。该方法将与待求解问题相同或相似的

18、已知的启发式搜索方法。该方法将与待求解问题相同或相似的已知问题的求解过程作为启发信息来指导新问题的求解。问题的求解过程作为启发信息来指导新问题的求解。5 5、类比法、类比法 联想、平移方法联想、平移方法 参考与当前要研究对象具有相似性的已有对象的有关理论，将其方法平移处理为关于被研究对象的理论方法。是从一类个体到另一类个体的推理是从一类个体到另一类个体的推理 G(x)| G(x)| F(x)| F(x)| 例例8 8 我们类比我们类比LODLOD提出提出LOLLOL、LoILoI、LOMLOM方法。方法。 为降低图形系统的负载，对景物依视距不同使用为降低图形系统的负载，对景物依视距不同使用多种

19、细节水平的几何表示，这就是细节层次多种细节水平的几何表示，这就是细节层次LODLOD技术。技术。 类比这一思想，在虚拟环境光照处理中，引入了类比这一思想，在虚拟环境光照处理中，引入了光照层次光照层次LOLLOL的概念，使光源在不同空间距离中具有不的概念，使光源在不同空间距离中具有不同的表现方式；为提高半动态对象的绘制效率同的表现方式；为提高半动态对象的绘制效率, ,提出运提出运动层次动层次LOMLOM的概念；的概念；为进行分布交互仿真的网络拥塞控为进行分布交互仿真的网络拥塞控制，提出兴趣层次方法。制，提出兴趣层次方法。6 6、尝试对称思维、反向思维、尝试对称思维、反向思维 自然界的规律是简洁的

20、，对称、对偶、矛与盾是普遍的。 有意识地在研究问题时尝试从对称、反对称、反方向角度进行思考，提出猜象或想象，有时会得到灵感。例如，由数据驱动想到需求驱动。例如，由数据驱动想到需求驱动。问题：是什么决定了算法的时间和空间效率之间的对偶性，也就是说两者测度的乘积在一定水平是一个不变量。7 7、发现结构与寻找算法、发现结构与寻找算法 发现所研究对象域中的数学结构（序关系、等发现所研究对象域中的数学结构（序关系、等价类、各种代数结构等），然后寻找有关对象的数价类、各种代数结构等），然后寻找有关对象的数学性质或高速算法。学性质或高速算法。具有数学结构才有高速算法，无序的对象只有枚举。 发现类比匹配问题中

21、的等价类，因而得发现类比匹配问题中的等价类，因而得到快速匹配算法。到快速匹配算法。 一般匹配等价于子图同态问题，是一般匹配等价于子图同态问题，是NPNP难解的。难解的。我们定义了匹配的名我们定义了匹配的名集和映射名集，而且证明了存集和映射名集，而且证明了存在等价类，从而找到了快速匹配算法。在等价类，从而找到了快速匹配算法。8 8、模型化、模型化 给出所研究对象的数学模型，将其形式化、模给出所研究对象的数学模型，将其形式化、模型化，然后寻找关于所研究对象的有关公理和数学型化，然后寻找关于所研究对象的有关公理和数学解，或者将所研究对象进行计算机仿真。解，或者将所研究对象进行计算机仿真。 这类研究会

22、导致较深刻的结果和原始性创新。这类研究会导致较深刻的结果和原始性创新。例例10 10 将具有过渡过程的逻辑电路抽象为将具有过渡过程的逻辑电路抽象为三值逻辑。三值逻辑。 f:0 x1 x2 x1 x2 x1:0 1 x2:1 0 f 分析险象的传统方法是布尔差分法。该方法是判断型分析险象的传统方法是布尔差分法。该方法是判断型的，即已知一个逻辑电路的输入向量的，即已知一个逻辑电路的输入向量 ，可以判定其是否存，可以判定其是否存在险象。在险象。 我们提出一种逻辑电路的三值逻辑模型，在该模型中，我们提出一种逻辑电路的三值逻辑模型，在该模型中，逻辑电路的输出值可以是逻辑电路的输出值可以是0 0、1 1或

23、或1/21/2。输出值是。输出值是1/21/2表示电路表示电路处于过渡状态，可能产生险象。令：处于过渡状态，可能产生险象。令： f(X)= 1/2 f(X)= 1/2 通过求解上述三值逻辑方程，可以得到使逻辑电路通过求解上述三值逻辑方程，可以得到使逻辑电路f(X)f(X)可能可能产生险象的全部输入解向量产生险象的全部输入解向量 (x1,x2,xn(x1,x2,xn) )，再通过一定的，再通过一定的方法（如布尔差分等）求得会产生险象的全部输入解向量。方法（如布尔差分等）求得会产生险象的全部输入解向量。9 9、模拟人的思维方法、模拟人的思维方法 用电脑代替人脑是计算机和人工智能研究人员的用电脑代替人脑是计算机和人工智能研究人员的一个追求目标，因此模拟人的思维是计算机科学和人一个追求目标，因此模拟人的思维是计算机科学和人工智能创新的源泉。工智能创新的源泉。 例如人工智能中关于“知道”的逻辑： 人对“知道”的一种认识 公 理（1）a知道的p都是真的 KaP P（2）a知道P，则a就知道a知道P KaP KaKaP（3）a知道PQ，则a知道P时就知道Q Ka(PQ)(KaPKaQ)例例1111对类比思维进行建模。对类比思维进行建模。 人类的类比思维过程人类的类比思维过程 形式模型（形式化）形式模型（形式化） 计算模