下载文档原格式
《离散数学》双语教学第一章真值表，逻辑和证明《离散数学》双语教学第一章真值表，逻辑和证明CHAPTER 1TRUTH TABLES, LOGIC, AND PROOFSGlossarystatement, proposition:命题 logical connective:命题联结词compound statement:复合命题 propositional variable:命题变元negation:否定(式)truth table:真值表conjunction:合取 disjunction:析取 propositional function:命题公式fallacy: 谬误syllogism:三段论universal quantification:全称量词化 existential quantification:存在量词化 hypothesis(premise): 假设～前提～前件 conditional statement, implication:条件式～蕴涵式 consequent, conclusion:结论～后件 converse:逆命题contrapositive:逆否命题biconditional, equivalence:双条件式～等价(逻辑)等价的 logically equivalent:contingency:可满足式tautology:永真式(重言式)contradiction, absurdity:永假(矛盾)式 logically follow:是…的逻辑结论 argument:论证axioms:公理第 1 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明 postulate:公设rules of reference:推理规则modus ponens:肯定律 modus tollens:否定律reductio ad absurdum:归谬律proof by contradiction:反证法counterexample:反例 minterm:极小项disjunctive normal form:主析取范式maxterm:极大项conjunctive normal form:主合取范式第 2 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明本章内容及教学要点:1.1 Statements and Connectives教学内容:statements(propositions)～compound statement～connectives:negation～conjunction～disjunction～truth tables 1.2 Conditional Statements教学内容:implications(conditional statements)～biconditional～equivalent～and quantifications1.3 Equivalent Statements教学内容:logical equivalence～converse～inverse～contrapositive～tautology～contradiction(absurdity)～contingency～properties of logical connectives1.4 Axiomatic Systems: Arguments and Proofs教学内容:rules of reference～augument～valid argument～hypotheses～premises～law of detachment(modus ponens)～syllogism～modus tollens～addition～proof by contradiction 1.5 Normal Forms教学内容:minterm～disjunctive normal form～maxterm～conjunctive normal form定理证明及例题解答第 3 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明Logic, developed by Aristotle, has been used through the centuries in the development of many areas of learning including theology, philosophy, and mathematics. It is the foundation on which the whole structure of mathematics is built. Basically it is the science of reasoning, which may allow us to determine statements about mathematics whether are true or false based on a set of basic assumptions called axioms. Logic is also used in computer science to construct computer programs and to show that programs do what they are designed to do.逻辑学是研究人的思维形式的科学. 而数理逻辑是逻辑学的一个重要分支～是用数学形式化的方法研究思维规律的一门学科. 由于它使用了一套符号来简洁地表达出各种推理的逻辑关系～故它又称符号逻辑.数理逻辑用数学方法研究推理、利用符号体系研究推理过程中前提和结论之间的关系. 数理逻辑的主要内容:逻辑演算(L和L)、公理化集合论、模型论、S p构造主义与证明论. 数理逻辑在电子线路、机器证明、自动化系统、编译理论、算法设计方法方面有广泛的应用.The rules of logic specify the meaning of mathematicalstatements. Logic is the basis of all mathematical reasoning, and it has practical applications to the design of computing machines, to system specifications, to artificial intelligence(AI), to computer programming, to programming languages, and to other areas of computer science, as well as to many other fields of study.第 4 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明1.1 Statements and Connectivess(命题和联结词)命题逻辑研究的对象是命题及命题之间的逻辑关系.Propositions are the basic building blocks of logic. Many mathematical statements are constructed by combining one or more propositions.定义1.1.1 A proposition is a statement or declarative sentence that is either true or false, but not both,命题是一个非真即假的陈述句,.因此不能判断真假的陈述句、疑问句、祈使句和感叹句都不是命题.,1, The true or false value assigned to a statement is called its truth value; (一个命题的真或假称为命题的真值. 真用T或1表示～假用F或0表示),2, 一个陈述句有真值与是否知道它的真假是两回事.例1.1.1 判断下列语句是不是命题,若是～给出命题的真值: (1) 陕西师大不是一座工厂.(2) 你喜欢唱歌吗,(3) 给我一块钱吧:(4) 我不是陕西师大的学生.(5) 我正在说谎.Logical connectives(命题联结词)数理逻辑的特点是并不关心具体某个命题的真假～而是将逻辑推理变成类似数学演算的形式化过程, 关心的是命题之间的关联性. 因此需要进行命题符号化.命题联结词的作用是为了将简单命题组合成复合命题.We will now introduce the logical connectives that are used to form new propositions from existing propositions. And once truth values have been assigned to simple propositions, we can progress to more complicated compound statements.A statement that contains no connectives is called a simple第 5 页共 47 页 2010-12-27《离散数学》双语教学第一章真值表，逻辑和证明statement. We will use p,q,r…to represent simple statements(简单命题就是简单陈述句～用字母p,q,r…(或带下标)表示),Sometimes, the letters p,q,r,s,…are used to denote propositional variables that can be replacedby statements(命题变元:可以用命题代替的变元).A statement that contains logical connectives(命题联结词) is called compound statements(复合命题). In general, a compound statement may have many component parts, each of which is itself a statement, represented by some propositional variable. The truth of a compound proposition is determined by the truth or falsity of the component parts.propositional constant(命题常元):T(1)或F(0)～或者表示一个确定的命题,propositional variable(命题变元):可用一个特定的命题取代。
逻辑符号及真值表
这些逻辑符号可以用于构建命题逻辑中复杂命题的逻辑结构，从而方便我们进行推理和论证。
在使用逻辑符号时，通常会用到真值表来验证命题的逻辑结构。
真值表是一种用来列出命题不同取值组合的表格。
在真值表中，每一行代表一种取值组合，每一列代表一个命题变量或逻辑符号。
通过对每个命题变量进行相应的逻辑运算，可以得出最终命题的真值（T 或F）。
例如，在合取命题p ∧ q中，p和q为命题变量，∧为逻辑符号。
我们可以列出如下的真值表：
p | q | p ∧ q
--|---|------
T | T | T
T | F | F
F | T | F
F | F | F
从表中可以看出，在p为真、q为真的情况下，p ∧ q的真值为真（T）。
而在其他情况下，其真值为假（F）。
通过使用逻辑符号和真值表，我们可以更加清晰地理解和分析命题逻辑中的复杂结构，从而更加准确地进行推理和论证。
- 1 -。
作者◆一剑钻神一、判断（一）1.SAP是指所有的S是P； SEP是指所有的S不是P;SIP是指有的S是P; SOP是指有的S不是P。
2.A与E是反对关系（不能同真，可以同假）；I与O时下反对关系（不能同假，可以同真）；A与O和E与I是矛盾关系（不能同假，已不能同真）；A与I和E与O是差等关系逻辑方阵全同真包含于真包含交叉全异A 1 1 0 0 0E 0 0 0 0 1I 1 1 1 1 0O 0 0 1 1 1A、E、I、O四种判断的真假情况列表注：1代表“真”；0代表“假”(下同)。
4.普通逻辑是研究思维的逻辑形式及其基本规律和简单逻辑方法的科学。
任何一种逻辑形式都是由逻辑常项和逻辑变项两部分组成。
普通逻辑所研究的思维是指抽象思维中的知性思维。
现代形式逻辑主要是指数理逻辑。
知觉是感觉的综合。
感性认识的基本特征是直接感受性。
人们平常提到逻辑学时，通常指的是形式逻辑。
在感性认识阶段，人们对客观事物的认识的三种存在形式人别是感觉、知觉、表象。
在理性认识阶段，人们对事物的认识的三种存在形式人别是概念、判断、推理。
5.概念是反映对象特有属性或本质属性的思维形式，概念有两个逻辑特征，他们是内涵和外延。
概念的内涵是指反映到概念中的对象中的特有属性或本质属性。
具有概念所反映的特有属性或本质属性的对象，称为概念的外延。
从逻辑的角度讲，所谓明确概念，指的就是要明确概念的内涵和外延。
普通逻辑不去研究概念在具体内容上的关系，而是把概念作为思维形式，从内涵或外延方面来研究概念间的关系。
根据概念的外延大小，概念分为单独概念和普通概念。
根据概念反映的对象是否为集合体，概念分为集合概念和非集合概念。
根据概念所反映对象是否具有某种性质，概念分为正概念和负概念。
6.定义的规则？（1）定义项的外延和被定义项的外延应是相同的（违反这条规则，就会犯“定义过宽”或“定义过窄”的逻辑错误）。
（2）定义项中不能直接或间接地包括被定义项（违反这条规则，就会犯“同语反复”或“循环定义”的逻辑错误）。
3、利用真值表判断公式（（P Q）(Q R)）(P R)是否为重言式。
解:P Q R P R P Q Q R P R(P R)(P Q)( Q R)（（P Q）(Q R)）(P R)0 0 0 1 1 1 1 1 0 1 00 0 1 1 0 1 1 0 1 1 10 1 0 1 1 1 0 1 0 0 10 1 1 1 0 1 1 0 1 1 11 0 0 0 1 0 1 1 0 0 11 0 1 0 0 0 1 1 0 0 11 1 0 0 1 1 0 1 0 0 11 1 1 0 0 1 1 1 0 1 0 由真值表得：（（P Q）(Q R)）(P R)在它的各种赋值下取值不全为真。
故（（P Q）(Q R)）(P R)不是重言式。
6、构造下列推理的证明：只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。
A曾到过受害者房间，如果在11点以前离开，看门人会看见他。
看门人没看见他，所以A犯了谋杀罪。
解：令P：A曾到过受害者房间；Q：11点以前离开；R ：看门人看见了A ；S ：A 犯了谋杀罪；前提：PR QS QP ,,结论：RS证明：（1）P前提引入（2）PQS前提引入（3）Q S (1)(2)析取三段论（4）Q 附加前提引入（5）S （3）（4）析取三段论（6）RS（5）附加7、构造下列推理的证明：如果小张和小明，去看电影，则小李也去看电影。
小赵不去看电影或小张去看电影，小王去看电影。
所以，当小赵去看电影时，小李也去。
解：令P ：小张去看电影；Q ：小王去看电影；R ：小李去看电影；S ：小赵去看电影；前提：P Q R ，S P ，Q结论：SR证明：（1）Q前提引入（2）P Q R前提引入（3）PR（1）（2）析取三段论（4）S P前提引入（5）S R （3）（4）假言三段论。
