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

论题1-2： 什么样的推理是正确的？ Logic--The discipline that deals with the methods of reasoning majun@nju.edu.cn 2017.10.12

论题1-2： 什么样的推理是正确的？ majun@nju.edu.cn 2017.10.12 Logic--The discipline that deals with the methods of reasoning

What is Logic? 。Logic The discipline that deals with the methods of reasoning The study of the principles and criteria of valid inference and demonstration Ma hematical lo IC Philosophical logic a brana cs that the application of formal logic to grew ut of symboli logic philosophical problems

What is Logic？ • Logic • The discipline that deals with the methods of reasoning • The study of the principles and criteria of valid inference and demonstration Mathematical logic a branch of mathematics that grew out of symbolic logic Philosophical logic the application of formal logic to philosophical problems

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

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

An Example 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

An Example • 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

How to solve it? Understanding the problem! 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. Bill is from Boston,if and only if Jim is NOT from Chicago. Jim is from Chicago,if and only if Bill is NOT from Boston. Guess and Reasoning Sam is from Boston,and Bill is from Chicago. Sam is from Boston,if and only if Bill is NOT from Chicago. Bill is from Chicago,if and only if Sam is NOT from Boston. Jim is from Boston,and Bill is from Detroit. Jim is from Boston,if and only if Bill is NOT from Detroit. Bill is from Detroit,if and only if Jim is NOT from Boston

How to solve it? • Understanding the problem! • 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. • Bill is from Boston, if and only if Jim is NOT from Chicago. • Jim is from Chicago, if and only if Bill is NOT from Boston. • Sam is from Boston, and Bill is from Chicago. • Sam is from Boston, if and only if Bill is NOT from Chicago. • Bill is from Chicago, if and only if Sam is NOT from Boston. • Jim is from Boston, and Bill is from Detroit. • Jim is from Boston, if and only if Bill is NOT from Detroit. • Bill is from Detroit, if and only if Jim is NOT from Boston. Guess and Reasoning

One Possible Reasoning ·Guessing that“Bill is from Boston'"is Bill,Jim and Sam are from Boston,Chicago and Detroit, respectively true,then Jim is NOT from Chicago Bill is from Boston,if and only if Jim is NOT from Chicago. ·Jim is NOT from Boston Jim is from Chicago,if and only if Bill is NOT from Boston. 。Bill is from Detroit CONFLICT 日 Sam is from Boston,if and only if Bill is NOT from Chicago. Bill is from Chicago,if and only if Sam is NOT from Boston. So the guessing is wrong,and Jim is from Boston,if and only if Bill is NOT from Detroit. .Bill is from Detroit,if and only if Jim is NOT from Boston. ·Jim is from Chicago ·Bill is from Detroit ·Sam is from Boston

One Possible Reasoning • Guessing that “Bill is from Boston” is true, then • Jim is NOT from Chicago • Jim is NOT from Boston • Bill is from Detroit • So the guessing is wrong, and • Jim is from Chicago • Bill is from Detroit • Sam is from Boston • Bill, Jim and Sam are from Boston, Chicago and Detroit, respectively • Bill is from Boston, if and only if Jim is NOT from Chicago. • Jim is from Chicago, if and only if Bill is NOT from Boston. • Sam is from Boston, if and only if Bill is NOT from Chicago. • Bill is from Chicago, if and only if Sam is NOT from Boston. • Jim is from Boston, if and only if Bill is NOT from Detroit. • Bill is from Detroit, if and only if Jim is NOT from Boston

问题1： 能否借用数 学的力量？ ·推理过程中，显然有些规律和被推玉 小口役 有关系：我们应该从中得出什么启发？

问题1： •推理过程中，显然有些规律和被推理的具体内容没 有关系;我们应该从中得出什么启发？ 能否借用数 学的力量？

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

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

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

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

命题(Proposition) ·命题指可以判断真假（但真假未必已知）的陈述句 ·判断下列句子是否为命题 ⊙·我的收入上升了 ⊙·今天是星期二，在下雨 ⑧·你会说英语吗？ 9·3-x=5 ·任一足够大的偶数一定可以表示为两个素数之和。 ②·“我现在说的是假话

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