南京大学：《计算机问题求解》课程教学资源（课件讲稿）什么样的推理是正确的

计算机问题求解-论题1-2 一什么样的推理是正确的？ Logic-The discipline that deals with the methods of reasoning

计算机问题求解-论题1-2 --什么样的推理是正确的？ Logic--The discipline that deals with the methods of reasoning

计算机解题与数学 * 对问题的理解必须用严格的数学语言描述。 *其前提是必须建立问题的数学模型。 *可用的数学模型必须是计算机能对其进行操作的。 *让计算机能理解的解题plan必须建立在严密的数学基础上 *将plan表示为计算机能执行的“指示”的语言必须建立在严密的数学基础上 *分析计算机计算的结果必须使用数学方法： *用逻辑证明结果正确； *动用必要的数学手段分析解法的效率

计算机解题与数学  对问题的理解必须用严格的数学语言描述。  其前提是必须建立问题的数学模型。  可用的数学模型必须是计算机能对其进行操作的。  让计算机能理解的解题plan必须建立在严密的数学基础上  将plan表示为计算机能执行的“指示”的语言必须建立在严密的数学基础上  分析计算机计算的结果必须使用数学方法：  用逻辑证明结果正确；  动用必要的数学手段分析解法的效率

命题符号化及其逻辑代数推演 We know that Bill,Jim and Sam are from Boston,Chicago and Detroit,respectively.Each of following sentence is half right and half wrong: Bill is from Boston,and Jim is from Chicago. Sam is from Boston,and Bill is from Chicago. Jim is from Boston,and Bill is from Detroit. Tell the truth about their home town

命题符号化及其逻辑代数推演 We know that Bill, Jim and Sam are from Boston, Chicago and Detroit, respectively. Each of following sentence is half right and half wrong: Bill is from Boston, and Jim is from Chicago. Sam is from Boston, and Bill is from Chicago. Jim is from Boston, and Bill is from Detroit. Tell the truth about their home town

寻找答案 *尽可能精确的表述问题 *例如：采用符号，用P *尽可能列出已经确定的信息，例如 *如果Bil来自波士顿，Jim就不会来自波士顿 *如果Sam来自波士顿，那么Bi训就不会来自芝加哥 剩下的是就是：“猜”+“推理

寻找答案  尽可能精确的表述问题  例如：采用符号，用P  尽可能列出已经确定的信息，例如  如果Bill来自波士顿，Jim就不会来自波士顿  如果Sam来自波士顿，那么Bill就不会来自芝加哥  ……  剩下的是就是：“猜”+“推理

可能的推理过程 如果第一句话的前半句是正确的，那么： 米〉 *Bill来自波士顿and *im不是芝加哥人and *Jim也不是波士顿人and *Bi训就是底特律人 *因此矛盾； *因此，Jim一定是芝加哥人=》Sam是波士顿人=》Bi训是底 特律人

可能的推理过程  如果第一句话的前半句是正确的，那么：  Bill来自波士顿 and  Jim不是芝加哥人 and  Jim也不是波士顿人 and  Bill就是底特律人  因此矛盾；  因此，Jim一定是芝加哥人=》Sam是波士顿人=》Bill是底 特律人

问题1： 如果这个题目中需要猜测的东 能否借用数学的 有效 应对？ 力量？ 推理过程中，显然有些规律和 没有关 系，我们应该从中得出什么启发？

问题1： 如果这个题目中需要猜测的东西很多，我们该如何有效 应对？ 推理过程中，显然有些规律和被推理的具体内容没有关 系，我们应该从中得出什么启发？ 能否借用数学的 力量？

为阅读和构造证明而必须掌握的若干基本逻辑要 素：形式化 *基本元素： *命题及其命题变元p *逻辑连接符及其逻辑含义 *特殊的命题表达式 *可能式、永真式、永假式； *逻辑等价 *谓词与变元 *量词

为阅读和构造证明而必须掌握的若干基本逻辑要 素：形式化  基本元素：  命题及其命题变元p  逻辑连接符及其逻辑含义  特殊的命题表达式  可能式、永真式、永假式；  逻辑等价  谓词与变元  量词

为阅读和构造证明而必须掌握的若干基本逻辑要 素：形式化 *基本操作： *符号化自然语言表达的命题 *精确表达 *进行有效的推理，得到正确的结论 *正确推理 *进行高效的、可验证的证明 *证明方法

为阅读和构造证明而必须掌握的若干基本逻辑要 素：形式化  基本操作：  符号化自然语言表达的命题  精确表达  进行有效的推理，得到正确的结论  正确推理  进行高效的、可验证的证明  证明方法

命题 *命题指可以判断真假的陈述句 *判断下列句子是否为命题 √*我的收入上升了 √*今天是星期二，在下雨 x*你会说英语吗？ ×*3-x=5 √*任一足够大的偶数一定可以表示为两个素数之和。 x*“我现在说的是假话

命题  命题指可以判断真假的陈述句  判断下列句子是否为命题  我的收入上升了  今天是星期二，在下雨  你会说英语吗?  3-x=5  任一足够大的偶数一定可以表示为两个素数之和。  “我现在说的是假话。”      

命题变元 *常用小写字母表示命题变元，如：卫，q,” *命题变元的取值范围为：{工，F) *命题也可以表示为命题变元的形式，可以理解为该变元 “已赋值” *p:今天是周五(p=F) *q:2+2=4(q=T)

命题变元  常用小写字母表示命题变元，如： p, q, r  命题变元的取值范围为： {T, F}  命题也可以表示为命题变元的形式，可以理解为该变元 “已赋值”  p: 今天是周五（p=F）  q: 2+2=4 （q =T）