链接版第一章真值表、逻辑和证明

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：公理postulate：公设rules of reference：推理规则modus ponens：肯定律m odus tollens：否定律reductio ad absurdum：归谬律proof by contradiction：反证法counterexample：反例minterm：极小项disjunctive normal form：主析取范式maxterm：极大项conjunctive normal form：主合取范式本章内容及教学要点：1.1 Statements and Connectives教学内容：statements(propositions)，compound statement，connectives：negation，conjunction，disjunction，truth tables1.2 Conditional Statements教学内容：implications(conditional statements)，biconditional，equivalent，and quantifications1.3Equivalent 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 contradiction1.5 Normal Forms教学内容：minterm，disjunctive normal form，maxterm，conjunctive normal form定理证明及例题解答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 S 和L p)、公理化集合论、模型论、构造主义与证明论. 数理逻辑在电子线路、机器证明、自动化系统、编译理论、算法设计方法方面有广泛的应用.The rules of logic specify the meaning of mathematical statements. 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.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 simplestatement. 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 replaced by 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代替一个命题变元.常用的有五种命题联结词，先介绍三种：(1) negation connective否定联结词（⌝）～p(否定式)：非p (not p)If p is a statement, the negation of p is the statement not p, denoted by ～p.～p：不，非，没有规定～p 是T当且仅当p是F.(2) conjunction connective合取联结词∧p∧q(合取式) ：p并且q，p合取q∧：并且，且，既…又…，不仅…而且…If p and q are statements, the conjunction of p and q(p和q的合取) is the compound statement “p and q”, denoted by p∧q. The proposition p∧q is true when both p and q are true and is false otherwise. (规定p∧q 是T当且仅当p和q都是T.)(3) disjunction connective析取联结词∨p ∨q(析取式)：p 或者q ，p 析取q∨:或，或者说，不是…就是，要么…要么If p and q are statements, the disjunction of p and q(p 和q 的析取) is the compound statement “p or q”, denoted by p ∨q. The proposition p ∨q is true when p or q are true and is false when both p and q are false. This is used in an inclusive sense. (规定p ∨q 是T 当且仅当p ，q 中至少一个是T 或者p ∨q 是F 当且仅当p ，q 都是F).Now we will introduces truth table to decide how the truth of a compound proposition is determined by the truth or falsity of the component parts.A truth table lists all possible combinations (cases ) of the truth and falsity of the component propositions.The truth table(真值表) of a compound proposition is as follows: The left columns are the component parts and their truth values, and the right column are the truth value of the compound proposition(左边部分是组成复合命题的各简单命题的真值指派；右边部分是复合命题的相应真值).例1.1.2 The truth tables of p ∧q, p ∨q and ～p.例1.1.3The truth table of p ∨(～q ∧r).T F F F T T F T F F F T F F F T T T F F F F F F T F T F F F T F F F T T F T TF F T F F F1 *2 13 1ASSIGNMENTS：PP6-9：12，14，28，30，34，40，58，601.2 Conditional Statements（条件式）(4) conditional connective条件（蕴含）联结词→（⇒）p→q(条件式、蕴涵式)：如果p则qIn the implication p→q, p is called the hypothsis(antecedent or premise) and q is called the conclusion(consequence). The implication p→q is the proposition that is false when p is true and q is false, and is true otherwise. (规定p→q是F当且仅当p是T，q是F. p称为条件式的前件(前提)，q称为条件式的后件(结论))→:如果(若)…就(则)，只要…就，若…才能例1.2.1 The truth table of p→q.The conditional is expressed in English in several ways:If p, then q.p is sufficient for q.p is a sufficient condition for q.q is necessary for p.q is a necessary condition for p.p only if q(or only if q then p)(5) biconditional connective双条件(等值)联结词↔（⇔）p↔q (双条件式) ：p当且仅当qThe biconditional p↔q is the proposition that is true when p and q have the same truth values, and is false otherwise. (规定p↔q是T当且仅当p，q或者都是T，或者都是F.)例1.2.2 The truth table of p↔q.The biconditional is also expressed in English in several ways:p if and only if q.p is necessary and sufficient for q.p is a necessary and sufficient condition for q.Translating sentences into logical expressions removes ambiguity. Once we have translated sentences from English(Chinese,etc.) into logical expressions we can analyze them to determine their truth values, manipulate them, and use rules of reference to reason abut them. (命题符号化的目的在于用五个联结词将日常语言中的命题转化为数理逻辑中的形式命题，其关键在于使用适当的联结词. 对自然语言中语句之间的逻辑关系以及命题联结词的含义要有正确的理解：(1) 确定语句是否是一个命题；(2) 找出句中连词，用适当的命题联结词表示.）例1.2.3 试将下列命题符号化：(1) 若你不看电影，则我也不看电影.(2) 小王一边吃饭，一边看书.(3) 只有在生病时，我才不去学校.(4) 当且仅当我生病时，我才不去学校.解例1.2.3例1.2.4 Change each of the following to the form p→q or q→p：(1) He will succeed only if he works hard.(2) Having money is sufficient for being happy.(3) Sam will play golf if and only if it is warm.(4) Having money is necessary for being happy.(5) Sam will play golf if and only if it is warm.(6) Being lucky is a necessary and sufficient condition for being successful.命题表达式(logical expression)一个命题越复杂，符号化该命题所需的命题变元和联结词就越来越多. 如何安排这么多的东西使之有意义呢？一个命题表达式是由下列方式递归定义的：(1) 命题常元或命题变元是一个命题表达式；(2) 若A是一个命题表达式，则(～A)也是一个命题表达式；(3) 若A、B是命题表达式，则(A∧B)、(A∨B)、(A→B)和(A↔B)均为命题表达式；(4) 只有经过有限次地应用(1)、(2)、(3)所得的结果才是命题表达式.注：1、对于一个命题表达式，数理逻辑的目的在于利用这些形式化的表达式来研究命题之间的逻辑关系. 这种逻辑关系是用真假来表示的；只有对其所有的变元指派以确定的真值后，它才有真值;2、命题表达式无限多；3、Precedence of logical connectives(命题联结词的优先级)在一个复杂的命题表达式中，常常有许多括号和联结词，为了简便起见，规定下列运算顺序：～，∧，∨，→，↔. 从而外层括号可以省略；在不会引起混淆的情形中，可以省略命题表达式中的一些括号.若命题表达式A1是命题表达式A 的一部分，则称A1是A的子命题表达式.例1.2.5 求命题表达式(p→(q∧s))∨～(p∧s)的子命题表达式.定义1.2.1设命题表达式A(p1, p2, …, p n)含有n个命题变元p1, p2, …, p n，p j1, p j2, …, p jr是其中的r个不同命题变元. 用命题表达式B1, B2, …, B r同时分别代替p j1, p j2, …, p jr在A中每一次出现所得到的命题表达式B称为A的一个代入实例.例1.2.6 设命题表达式A(p,q,s)为(p→q∧s)∨～(p∧s)，B为p→q，则用B 代入A中的p所得的代入实例为命题表达式((p→q)→(q∧s))∨～((p→q)∧s).若C为q→p，则用B和C分别取代A中的p和s所得的代入实例为命题表达式((p→q)→(q∧(q→p)))∨～((p→q)∧(q→p)).在命题逻辑中，还有一种所谓的替换. 但代入是对命题变元来进行的. 而替换则是对某一子命题表达式来进行的，它只要求对该子命题表达式的某一处出现或某几处出现进行替换.例1.2.7 设公式A(p，q)为(p→(q∧s))∨～(p∧s)，B为～p∨～s，则用B 代入A中的子公式～(p∧s)所得的公式为(p→(q∧s))∨(～p∨～s).Assignments:PP11-13：6，8，40，44，481.3 Equivalent Statements（等价命题）If two compound statements p and q are true in exactly the same cases, then they are said to be logically equivalent(逻辑等价的或等价的), or we say that p is equivalent to q. We will denote this by p≡q. We can establish their equivalence by constructing truth tables for them and then comparing the two truth tables. Or by using the tautologies, which we will introduce in the following text.例 1.3.1 ～p∧～q and ～(p∨q)are logically equivalent, i.e. ～p∧～q≡～(p∨q).Associated with the conditional statement p→q are three other statements: its converse, inverse, and contrapositive.q→p is the converse(逆命题) of p→q.～q→～p is the contrapositive(逆否命题) of p→q.～p→～q is the inverse(否命题) of p→q.例1.3.2 Let the implication be “If it is raining, then I get wet.” Give its converse, inverse and contrapositive.A statement that is true in every case is called a tautology.A statement that is always false in every case is called a contradiction or an absurdity. And a statement that can be true or false, depending on the truth values of its component parts, is called a contingency(设A 是一个命题表达式，若A在任何指派下都为T，则称为永真式(重言式)；若A 在任何指派下都为F，则称A为永假式(矛盾式)；若至少存在一个指派使A为T，则称A为可满足式).例1.3.3 判断下列几个公式的类型：p∨～p，p∧～p，p∨q.例1.3.4 用真值表决定公式～(～p→q)∧p的类型.解例1.3.4注: 1、永真式必为可满足式，反之则不然；永真式的否定是永假式，反之亦然；2、决定一个公式是否是一个永真式、永假式或可满足式有两种方法：真值表法(适用于变元少而简单的公式)和公式推理（等价取代）法；3、共有n22个不同的n元真值表；4、永真式的合取、析取、蕴含和等值式都是永真式.定理1.3.1 p is equivalent to q if and only if p↔q is a tautology.定理1.3.2p↔q是永真式当且仅当条件式p→q和q→p都是永真式.定理 1.3.3 The connectives for propositions have the following properties (命题运算满足下列性质)：Idempotent laws(等幂律):p∧p≡p, p∨p≡pDouble negation law(双否律):～(～p)≡pDe Morgan’s laws(德.摩根律):～(p∧q)≡～p∨～q, ～(p∨q)≡～p∧～qCommutative laws(交换律):p∧q≡q∧p, p∨q≡q∨pAssociative laws(结合律):p∧(q∧r)≡(p∧q)∧r, p∨(q∨r)≡(p∨q)∨rDistributive laws(分配律):p∧(q∨r)≡(p∧q)∨(p∧r), p∨(q∧r)≡(p∨q)∧(p∨r) Identity laws(同一律):p∧T≡p, p∨F≡pDomination laws(零一律):p∨T≡T, p∧F≡FAbsorption laws(吸收律):p∧(p∨q)≡p, p∨(p∧q)≡pNegation laws(有补律):p∨～p≡T, p∧～p≡FLogical equivalences involving implications:p→q≡～p∨q(条件式转化律), p→q≡～q→～p (逆否律),(p→q)∧(p→r)≡p→(q∧r)(p→r)∧(q→r)≡(p∨q)→rLogical equivalences involving biconditionals:p↔q≡(p→q)∧(q→p),p↔q≡(p∧q)∨(～p∧～q) (双条件式转化律)where T can represent any tautology and F can represent any contradiction.Any component of a compound statement can be replaced by any statement logically equivalent to that statement without changing the truth value of the statement.定理1.3.4(代入原理)永真(假)式的代入实例是永真(假)式.定理1.3.5(替换原理)设A为命题公式C的子命题公式，若A≡B，且将C中A的一处或若干处出现用B代替得到D，则C≡D.替换和代入虽都是从一个命题公式变换得到另一个新的命题公式，但代入是对命题变元进行的，且必须同时替换某变元的所有出现(处处代入)；而替换的对象则是子命题公式，且只需取代某子命题公式的一处或若干处出现(部分替换). 例1.3.5 Establishes the equivalence:(q∨r)∨(p∧～r) ≡(p∨q)∨rAssignments:PP17-19：8，10，12，14，28，30，40，48，52，54，561.4 Axiomatic Systems: Arguments and ProofsMuch of mathematics deals with theorems and proofs of theorems. Theorems are “true” statements about the mathematical system being considered.A theorem is a statement that can be shown to be true. We demonstrate that a theorem is true with a sequence of statements that form an argument (证明，推理).Two important questions will arise in the study of mathematics are: (1) When is a mathematical argument valid(correct)? (2) What methods can be used to construct a valid mathematical argument?An argument consists of a collection of statements called hypotheses and a statement called its conclusion. A valid argument is an argument whose conclusion true whenever all the hypotheses are true.To construct proofs, methods are needed to derive new statements from old ones. The statements used in a proof can include axioms(公理)or postulates(公设), the hypotheses of the theorem to be proved, and previously proved theorems. The rules of inference(推理规则), which are means used to draw conclusions from other assertions, tie together the steps of a proof.In a mathematical system, all of the information necessary to prove a theorem must be contained in axioms and previously proven theorems.推理就是从一组已知的命题出发，按照一组推理规则推出新的命题的过程. 已知命题称为推理的前提，推出的命题称为推理的结论.推理过程是一个有限公式序列，它以一个前提开始. 它的最后一个公式是结论，其余的公式或者是一个公理、公设或给定的前提，或者是由若干个在它前面出现的公式的有效结论.定义 1.4.1Suppose that the implication H1∧H2∧…∧H n→C is atautology, we say that C logically follows from H1,H2,…,H n.Virtually all mathematical theorems are composed of implications of the typeH1∧H2∧…∧H n→CThe H s'are called the hypotheses(假设)or premises(前提),iand C is called the conclusion.To prove the theorem, we are trying to show that C will be true if all the H i are true.The first method of showing that an argument is valid is to construct a truth table and show that whenever all of the hypotheses are true, then the conclusion is true too.例1.4.1 Determine whether the following argument are valid or not: (1) p∨qp→rq→r∴r(2) p→qq→rr∴p解例1.4.1The second is to use the rules of inference to prove the validity of the conclusion. The various steps in a mathematical proof of a theorem must follow from the use of various rules of inference, and a mathematical proof of a theorem must begin with the hypotheses, proceed through various steps, each justified by some rule of inference,and arrive at the conclusion.In fact, in order to prove a theorem of the typical form H1∧H2∧…∧H n→C, we begin with the hypotheses H1,H2,…,H n and show that some result C1 logically follows. Then, using H1,H2,…,H n,C1, we show that some other result C2logically follows. We continue this process, producing intermediate statements C1,C2,…,C k, called steps in the proof, until we can finally show that the conclusion C logically follows H1,H2,…,H n, C1,C2,…,C k. Each logical step must be justified by some valid proof technique, based on the rules of inference or some other rules that come from tautological implications（永真蕴涵式）.In all, a valid argument is formally a sequence of statements each of which is(1) A hypothesis(2) An axiom or postulate(3) A previously proven theorem or proposition(4) A statement implied by previous statements as a conclusion ofa valid argument(5) Logically equivalent to a previous statement前面讲过的逻辑等价式和永真蕴含式都可以适当地变成可用的推理规则. 常用的有：(1) Addition rule(附加规则)p∴p∨q(2) Specialization rule(化简规则)qp∧∴p(3) Modus ponens (law of detachment,假言推理,肯定律)pp→q∴q(4) Modus tollens (拒取式,否定律)～qqp→∴～p(5) Disjunctive syllogism (析取三段论)～pp∨q∴～q(6) Syllogism(假言三段论)p→qq→r∴p→r(7) Conjunction rule(合取引入)pq∴p∧q例1.4.2Is the following argument valid?If you invest in the stock market, then you will get rich.If you get rich, then you will be happy.∴If you invest in the stock market, then you will be happy.例1.4.3Is the following argument valid?Smoking is healthy.If smoking is healthy, then cigarettes are prescribed by physicians. ∴Cigarettes are prescribed by physicians.例1.4.4Is the following argument valid?If taxes are lowered, then income rises.Income rises.∴Taxes are lowered.There are several different proof techniques: direct method(直接证明法), indirect method(间接证明法), proof by contradiction(反证法), and mathematical induction(数学归纳法).An important proof techniques is indirect method(间接证明法).It based on the tautology (p→q)↔(～q→～p), which means that an implication is equivalent to its contrapositive.例1.4.5Let n be an integer. Prove that if n2 is odd, then n is odd.Another important proof technique is proof by contradiction(反证法). It is based on the tautology ((p→q)∧～q)→～p. To prove that C logically follows from H1,H2,…,H n, we show that H1∧H2∧…∧H n∧～C implies a contradiction.例1.4.6Prove there is no rational number whose square is 2. In other words, show that 2is irrational.定义1.4.2Let A be a logical expression that includes only ～，∧and ∨. Interchanging ∧and ∨, T and F(if there are some) in A, we will have the antithesis of A, and we denote it A*.(设A是仅含～，∧和∨这三种命题联结词的公式，在A中将∧和∨互换、T和F(若有的话)所得到的公式称为A的对偶式（antithesis），记为A*.)例1.4.7Construct the antithesis of (p→q)→s(求(p→q)→s的对偶式). 解例1.4.7定理1.4.1Let A be a logical expression that includes only ～，∧and ∨. Then ～A(p1, p2, …, p n) ≡A*(～p1, ～p2, …, ～p n)(设A(p1, p2, …, p n)是仅含～，∧和∨这三种命题联结词的公式，则～A(p1, p2, …, p n) ≡A*(～p1, ～p2, …, ～p n).)定理1.4.2(对偶原理)Let A and B be logical expressions that includesonly ～，∧and ∨. If A≡B，then A*≡B*.(设A和B都是仅含～，∧和∨这三种命题联结词的公式，若A≡B，则A*≡B*.)定义1.4.3Let A and B are logical expressions. If A→B is a tautology, then we say that B logically follows from A.(设A，B是两个公式，若A→B 是永真式，则称A永真蕴含B)永真蕴含关系的性质：(1)(Reflexivity,自反性) A logically follows from A（A→A是永真式）；(2)(Transitivity,传递性) If B logically follows from A and C logically follows from B, then C logically follows from A(若A→B和B→C是永真式，则A→C是永真式)；(3) If both B and C logically follow from A, then B∧C logically follows from A(若A→B和A→C是永真式，则A→(B∧C)是永真式)；(4) If A logically follows from B and C, then A logically follows from B∨C(若B→A和C→A是永真式，则B∨C→A是永真式)；(5) A↔B is a tautology if and only if A→B and B→A are tautologies(A↔B是永真式当且仅当A→B和B→A都是永真式)；(6) If A→B is a tautology, then ～B→～A is a tautology too(若A→B是永真式则～B→～A是永真式).永真蕴含关系的证明:(1) Using truth tables(真值表法)；(2) Suppose that the premise be true and show that the consequence is true(前件真推出后件也真法)；(3) Suppose that the consequence be false and show that the premise is false(后件假推出前件也假法)；(4) Using the transitivity of the relation(利用永真蕴含关系的传递性).例1.4.8Show that (p∧(p→q))→q is a tautology.证明例1.4.8定理1.4.3Let A and B be logical expressions that includes only ～，and ∨. IF A→B is a tautology, then B*→A*is a tautology too.(设A ∧和B都是仅含～，∧和∨这三种命题联结词的公式，若A→B是永真式，则B*→A*是永真式.)例1.4.9Prove：(1)(p→q)→(p→(p∧q)) is a tautology；(2)(q∨～(((～p)∨(～q))∧p))→((～p)∨q) is a tautology.证明例1.4.9例1.4.10Use the alternative to the truth table method to determine which of the following arguments are valid:(1) p→q～q→～ss→tt∨q∴p∨s(2) s∨tt→rs→w∴r∨w例1.4.11Determine which of the following arguments are valid: (1) p→qp→rq∨r∴p(2) p→qp→r～(p∧q)∴～p例1.4.12Use the rules of reference and equivalent statements to show that the following arguments are valid:(1) ～(～p∨q)～z→～s(p∧～q)→s～z∨r∴r(2) p∨qq→r～s→～rs→t～t∴pUsing premises(P规则,前提引入): We can use premises wherever(在推导过程中，前提可视需要引入使用).Using rules of inference(T规则,结论引入): We can produce intermediate conclusions from previous statements(在推导过程中，利用推理定律可引入前面已导出的结论的有效结论).Using complementary premises (CP规则,附加前提引入): If The conclusion is expressed as S→C, then we will show H1,H2,…,H n，S⇒C instead of showing H1,H2,…,H n⇒S→C(若结论是形为S→C的公式，则要证H1,H2,…,H n⇒S→C，只需证H1,H2,…,H n，S⇒C).Proof by contradiction(反证法)：Show that H1∧H2∧…∧H n∧～C is a contradiction(即证H1∧H2∧…∧H n∧～C是永假式).例1.4.13Prove:(1) a，a→～b，～b→c，c→d ⇒d;(2) p→(q→s)，q，p∨～s，s ⇒r;(3) (u∨v)→(m∧n)，u∨p，p→(q∨s)，～q∧～s ⇒m;证明例1.4.13例1.4.14Prove:(1) p→q，～(q∨r) ⇒～p;(2) (p∨q)→s ⇒(p∧q)→s;(3) ～p↔q，s→～q，～r，r∨s ⇒p证明例1.4.14例 1.4.15为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效?前提:(1) 若A队得第一，则B队或C队获亚军;(2) 若C队获亚军，则A队不能获冠军;(3) 若D队获亚军，则B队不能获亚军;(4) A 队获第一;结论: (5) D队不是亚军.证明例1.4.15例1.4.16 Prove:1. a→(b→c)，c→～d∨e)，～f→(d∧～e)，a ⇒b→f2. (p→q)∧(r→s)，(q→w)∧(s→x)，～(w∧x)，p→r ⇒～p证明例1.4.16例 1.4.17Using the rules of inference, find conclusions for the following:1. All mermaids are strange.They read fiction only if they are literate.Those who don’t read fiction are not strange.All literate people have been to college.Conclusion: All mermaids have been to college.2. Smoking is sufficient for being unhealthy.If one swims, then one is healthy.Only if one is a fish then one is in a school.To be a fish, it is necessary to swim.Conclusion: If one is in a school, then one doesn’t swim.Assignments:PP27-29：10，12，14，18，20，22，24，32，34，36，441.5 Normal FormsNormal form(公式标准型——范式)maxterm(极大项), conjunctive normal form(主合取范式) 范式使千变万化的公式有了一个统一的表示方式，从而为实现公式的机器判断提供了基础. 范式也在电子线路技术、自动机理论和人工智能方面有重要的应用.定义 1.5.1 A propositional variable( its negation) is called a positive(negative) word.(命题变元及其否定称为文字，命题变元称正文字，命题变元的否定称为负文字.)定义 1.5.2Simple disjunctive expression is defined recursively as follows(基本和，又称简单析取式的递归定义是）：(1) A word is a simple disjunctive expression(文字是基本和)；(2) If A and B are simple disjunctive expressions, then A∨B is too (若A，B是基本和，则A∨B也是基本和);(3) 只有经过有限次地应用(1)、(2)所得的结果才是公式.即基本和是这样的一个公式: 除∨外无其他的二元联结词，且∨的所有运算对象或者是某个命题变元或者是它的否定.例 1.5.1p，～p，p∨(～p)，p∨q∨(～s) are simple disjunctive expressions.定理1.5.1 A simple disjunctive expression is a tautology if and only if it includes both a propositional variable and its negation.(一个基本和是永真式⇔它同时含有某命题变元与它的否定.)定义 1.5.3Conjunctive normal form is defined recursively as follows(合取范式的递归定义如下)：(1) A simple disjunctive expression is a conjunctive normal form(基本和是合取范式)；(2) If A and B are conjunctive normal forms, then A∧B is too.(若A和B 是合取范式，则A∧B也是合取范式.)(3) 只有经过有限次地应用(1)、(2)所得的结果才是合取范式.A conjunctive normal form is the conjunction of several simple disjunctive expressions(即合取范式是若干基本和的合取).定义 1.5.4Let B be a conjunctive normal form and A be a logical expression. If A≡B, then we call B a conjunctive normal form of A.(若B是合取范式，A是一个公式. 若A⇔B是永真式（逻辑等价于B, A≡B），则称B是A的合取范式.)例 1.5.2(p∨q)∧(～p∨q) and (p∨q)∧(～p∨q)∧(p∨～q∨q∨s) are both conjunctive normal forms of q.Every logical expression always has its conjunctive normal form(任一个命题公式总是存在合取范式).How to find a conjunctive normal form of a logical expression(下面是求一个公式的合取范式的方法)：Step1: Using the logical equivalences involving implications and biconditionals to transform it into a logical expression which includes only ～，∧and ∨(首先将公式中的条件式和双条件式转化为只含∧，∨，～)；Step2: Using De Morgan’s laws and double negation law to arrange the logical connective ～(利用De Morgan 律和双否律将括号外的～转化到括号内)；Step3: Using commutative laws, associative laws and distributive laws to arrange the logical connectives ∧and ∨(利用交换、分配以及结合律按相应范式的要求安排∧，∨).例1.5.3 Find a conjunctive normal form of (p→(q→s))∧(～p∧q). (求(p→(q→s))∧(～p∧q)的合取范式.)解例1.5.3从例1.5.2中可以看出，一个公式的合取范式是不唯一的，这就给用形式化的方法(特别是用计算机作为工具)来判断两公式是否等价带来了困难. 为此我们在下面引入主合取范式(principal conjunctive normal form).定义1.5.5 An n-maxterm is a simple disjunctive expression that it must include each propositional variable or its negation, but notboth.(n元极大项是这样一种基本和：每个变元与其否定不同时出现，但二者之一必须恰好出现一次. 极大项用M或带下标的M表示.)注1:极大项的形式非常规范；2:基本和可能是一个永真式，但极大项不可能是一个永真式；3: 共有2n个不同的n元极大项；4: 任两个不同的n元极大项的析取式是永真式；5: 所有n元极大项的合取为永假式(即一个永假式的n元主合取范式为所有n元极大项的合取) ；6: 若规定n元极大项中n个变元或它的否定的出现顺序，可构造一个n 位二进制数：若第k个变元(否定)出现在该n元极大项中，则b的第k位为0(1). 则可用M b表示该n元极大项；7: 任两个不同n元极大项不等价；8: 每一个n元极大项只有一个成假指派，其余2n–1个指派均为成真指派.定义 1.5.6 An n-principal conjunctive normal form is defined recursively as follows(n元主合取范式的递归定义是)：(1) An n-maxterm is one(n元极大项是n元主合取范式)；(2) If A and B are n-principal conjunctive normal forms, then so is (A∧B).(若A，B是n元主合取范式，则(A∧B)也是n元主合取范式.)(3) 只有经过有限次地应用(1)、(2)所得的结果才是n元主合取范式.定义1.5.7Let B be a principal conjunctive normal form and A be a logical expression. If A≡B, then we call B the principal conjunctive normal form of A.(若B是主合取范式，A是一个公式. 若A≡B，则称B是A 的主合取范式.)规定永真式的主合取范式是T. 一个永假式的n元主合取范式为所有极大项的合取. 任一不是永真式的公式A都存在与其等价的主合取范式；且在不计极大项出现的顺序情形下，这样的主合取范式是唯一的.How to find the principal conjunctive normal form of a logical expression(求主合取范式的方法):Step1Find a conjunctive normal form(先将公式化为合取范式);Step2 For every simple disjunctive expression(对每一个基本和): (1) If it includes a propositional variable and its negation, delete it(若其中既有某个变元又有它的否定，则去掉该基本和);(2) If it includes several instances of a propositional variable(or its negation), simplify it to include only one instance of the propositional variable(or its negation) using idempotent laws(若某个变元(或其否定)在式中同时出现二次或二次以上，则用等幂律化简，直至只保留一次);(3) If it doesn’t include a propositional variable and its negation, add it using identity laws, domination laws, negation laws and distributive laws(若其中既无某个变元又无它的否定，则用同一律、零一律、有补律和分配律使变元或它的否定出现在该和中).例1.5.4Find the principal conjunctive normal forms of (p∧q)∨(～p∧s) and (p→(q→s))∧(～p∧q). (求(p∧q)∨(～p∧s)和(p→(q→s))∧(～p∧q)的主合取范式.)解例1.5.4minterm(极小项), principal disjunctive normal form(主析取范式) Similarly, we can define other kind of normal forms: (principal) disconjunctive normal form(类似地，我们可以定义另一种范式：析取范式和主析取范式).定义1.5.8Simple conjunctive expression is defined recursively as follows(基本积，又称简单合取式)的递归定义是）：(1) A word is a simple conjunctive expression(文字是基本积)；(2) If A and B are simple conjunctive expressions, then A∧B is too.(若A，B是基本积，则A∧B也是基本积.)(3) 只有经过有限次地应用(1)、(2)所得的结果才是基本积.即基本积是这样的一个公式: 除∧外无其他的二元联结词，且∧的所有运算对象或者是某个命题变元或者是它的否定.例1.5.5p，～p，p∧～p，p∧q∧～s are simple conjunctive expressions. 定理1.5.2 A simple conjunctive expression is a contradiction if andonly if it includes both a propositional variable and its negation.(一个基本积是永假式⇔它同时含有某命题变元与它的否定.)定义 1.5.9Disjunctive normal form is defined recursively as follows(析取范式的递归定义如下)：(1) A simple conjunctive expression is a disjunctive normal form(基本积是析取范式)；(2) If A and B are disjunctive normal forms, then A∨B is too.(若A和B 是析取范式，则A∨B是析取范式.)(3) 只有经过有限次地应用(1)、(2)所得的结果才是析取范式.A disjunctive normal form is the disjunction of several simple conjunctive expressions(即析取范式是若干基本积的析取).定义1.5.10Let B be a disjunctive normal form and A be a logical expression. If A≡B, then we call B a disjunctive normal form of A.(若B 是析取范式，A是一个公式. 若A≡B，则称B是A的析取范式.)例 1.5.6(p∧q)∨(～p∧q) and (p∧q)∨(～p∧q)∨(p∧～q∧q∧s) are both disjunctive normal forms of q.(公式q的析取范式是(p∧q)∨(～p∧q)和(p∧q)∨(～p∧q)∨(p∧～q∧q∧s).)Similarly, every logical expression always has its disjunctive normal form(同样任一个命题公式总是存在析取范式).How to find a disjunctive normal form of a logical expression(下面是求一个公式的析取范式的方法)：Step1:Using the logical equivalences involving implications and biconditionals to transform it into a logical expression which includes only ～，∧and ∨(首先将公式中的条件式和双条件式转化为只含∧，∨，～); Step2: Using De Morgan’s laws and double negat ion law to arrange the logical connective ～(利用De Morgan 律和双否律将括号外的～转化到括号内);Step3: Using commutative laws, associative laws and distributive laws to arrange the logical connectives ∧and ∨(利用交换、分配以及结合律按相应范式的要求安排∧，∨).。