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

个人收集整理 勿做商业用途
CHAPTER 1 　
TRUTH TABLES, LOGIC, AND PROOFS

Glossary
statement, 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:肯定律
modus 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 tables
1.2 Conditional Statements
教学内容：implications（conditional statements）,biconditional，equivalent,and quantifications
1。3　Equivalent Statements
教学内容：logical equivalence，converse,inverse，contrapositive，tautology,contradiction(absurdity)，contingency，properties of logical connectives
1。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

定理证明及例题解答

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. 文档为个人收集整理，来源于网络
逻辑学是研究人的思维形式的科学。 而数理逻辑是逻辑学的一个重要分支，是用数学形式化的方法研究思维规律的一门学科。 由于它使用了一套符号来简洁地表达出各种推理的逻辑关系,故它又称符号逻辑。
数理逻辑用数学方法研究推理、利用符号体系研究推理过程中前提和结论之间的关系. 数理逻辑的主要内容:逻辑演算（LS 和Lp）、公理化集合论、模型论、构造主义与证明论。 数理逻辑在电子线路、机器证明、自动化系统、编译理论、算法设计方法方面有广泛的应用.
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 simple 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 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合取联结词
pq(合取式） ：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 pq。 The proposition pq is true when both p and q are true and is false otherwise. （规定pq是T当且仅当p和q都是T.)
（3） disjunction connective析取联结词
pq(析取式)：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 pq。 The proposition pq 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。 (规定pq是T当且仅当p，q中至少一个是T或者pq是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 pq, pq and ～p.
p q
pq
T T
T F
F T
F F
T
F
F
F
p q
pq
T T
T F
F T
F F
T
T
T
F

p
～p
T
F
F
T

例1.1。3 The truth table of p（～qr）。
p q r
p （(～ q) r）
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F

T T F T F T
T T F T F F
T T T F T T
T T T F F F
F F F T F T
F F F T F F
F T T F T T
F F T F F F
1 ＊ 2 1 3 1

ASSIGNMENTS：
PP6—9：12，14，28,30，34,40，58,60
1.2 Conditional Statements(条件式）

（4) conditional connective条件（蕴含）联结词（）
pq(条件式、蕴涵式):如果p则q
In the implication pq, p is called the hypothsis(antecedent or premise) and q is called the conclusion(consequence）。 The implication pq is the proposition that is false when p is true and q is false， and is true otherwise。 (规定pq是F当且仅当p是T，q是F。 p称为条件式的前件（前提)，q称为条件式的后件（结论））
：如果（若）…就（则)，只要…就，若…才能
例1。2。1 The truth table of pq.
p q
pq
T T
T F
F T
F F
T
F
T
T

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双条件 （等值)联结词()
pq （双条件式） ：p当且仅当q
The biconditional pq is the proposition that is true when p and q have the same truth values, and is false otherwise. （规定pq是T当且仅当p，q或者都是T,或者都是F.）
例1。2.2 The truth table of pq.
p q
pq
T T
T F
F T
F F
T
F
F
T

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 pq or qp:
(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是命题表达式,则(AB)、（AB）、(AB）和（AB）均为命题表达式；
（4) 只有经过有限次地应用(1)、(2）、（3）所得的结果才是命题表达式.
注：1、对于一个命题表达式，数理逻辑的目的在于利用这些形式化的表达式来研究命题之间的逻辑关系. 这种逻辑关系是用真假来表示的;只有对其所有的变元指派以确定的真值后，它才有真值;
2、命题表达式无限多；
3、Precedence of logical connectives(命题联结词的优先级）在一个复杂的命题表达式中，常常有许多括号和联结词,为了简便起见，规定下列运算顺序：～，，，，。 从而外层括号可以省略；在不会引起混淆的情形中，可以省略命题表达式中的一些括号.

若命题表达式 A是命题表达式A 的一部分，则称A是A的子命题表达式。
例1。2。5 求命题表达式(p（qs）)～(ps）的子命题表达式。
定义1.2.1　设命题表达式A(p1， p2， …， pn）含有n个命题变元p1, p2, …， pn， pj1， pj2， …, pjr是其中的r个不同命题变元. 用命题表达式B1， B2, …， Br同时分别代替pj1， pj2, …, pjr在A中每一次出现所得到的命题表达式B称为A的一个代入实例。
例1.2.6 设命题表达式A（p,q,s）为（pqs）~(ps),B为pq，则用B代入A中的p所得的代入实例为命题表达式（(pq）(qs））～(（pq)s）.
若C为qp，则用B和C分别取代A中的p和s所得的代入实例为命题表达式（(pq)(q（qp)））～（(pq）(qp））。
在命题逻辑中，还有一种所谓的替换. 但代入是对命题变元来进行的. 而替换则是对某一子命题表达式来进行的，它只要求对该子命题表达式的某一处出现或某几处出现进行替换。
例1。2。7 设公式A(p,q)为(p(qs))～（ps)，B为~p~s，则用B代入A中的子公式~（p∧s）所得的公式为（p（qs)）(～p～s).

Assignments：
PP11-13：6，8,40，44,48
1.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 pq。 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 ~（pq） are logically equivalent， i。e. ～p～q~(pq）.
Associated with the conditional statement pq are three other statements： its converse, inverse, and contrapositive.
qp is the converse(逆命题） of pq.
～q～p is the contrapositive（逆否命题） of pq.
~p~q is the inverse（否命题) of pq.
例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,pq。
例1。3。4 用真值表决定公式~(~pq）p的类型。
解 例1.3。4
注: 1、永真式必为可满足式,反之则不然；永真式的否定是永假式，反之亦然；
2、决定一个公式是否是一个永真式、永假式或可满足式有两种方法：真值表法(适用于变元少而简单的公式)和公式推理（等价取代)法；
3、共有个不同的n元真值表；
4、永真式的合取、析取、蕴含和等值式都是永真式.
定理1.3。1 p is equivalent to q if and only if pq is a tautology.
定理1。3。2 pq是永真式当且仅当条件式pq和qp都是永真式.
定理1。3。3 The connectives for propositions have the following properties (命题运算满足下列性质）：
Idempotent laws（等幂律):
ppp， ppp
Double negation law(双否律):
~（～p)p
De Morgan’s laws(德。摩根律):
～（pq）～p～q， ～(pq)～p~q
Commutative laws(交换律）:
pqqp， pqqp
Associative laws(结合律）：
p(qr）(pq）r， p（qr)（pq）r
Distributive laws(分配律)：
p（qr)（pq）（pr)， p(qr)(pq)(pr)
Identity laws(同一律)：
pTp， pFp
Domination laws(零一律):
pTT, pFF
Absorption laws（吸收律)：
p(pq）p, p(pq)p
Negation laws(有补律）：
p～pT, p～pF
Logical equivalences involving implications:
pq~pq（条件式转化律）， pq～q~p (逆否律）,
（pq）(pr）p(qr)
(pr)（qr）(pq）r
Logical equivalences involving biconditionals:
pq（pq）(qp），
pq（pq）(～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的子命题公式，若AB,且将C中A的一处或若干处出现用B代替得到D，则CD。
替换和代入虽都是从一个命题公式变换得到另一个新的命题公式，但代入是对命题变元进行的，且必须同时替换某变元的所有出现（处处代入)；而替换的对象则是子命题公式，且只需取代某子命题公式的一处或若干处出现(部分替换).
例1。3.5 Establishes the equivalence：
（qr)（p～r） (pq）r

Assignments：
PP17-19：8，10，12，14,28,30,40，48，52，54,56
1。4 Axiomatic Systems： Arguments and Proofs

Much 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.1 Suppose that the implication H1∧H2∧…∧Hn →C is a tautology, we say that C logically follows from H1，H2，…,Hn。
Virtually all mathematical theorems are composed of implications of the type
H1∧H2∧…∧Hn→C
The H are called the hypotheses（假设) or premises(前提）， and C is called the conclusion。

To prove the theorem， we are trying to show that C will be true if all the Hi 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 o