Chapter 1 - Logic and Proofs

写在前面

离散数学的笔记对翁老师分享的前辈的笔记有所参考，所以放在前面，文章中讲的不详细的地方，大家可以去阅读学长的笔记

定义

注意

补充、解释

其他

术语对照

参考这就来了(

• conjunction 合取
• disconjunction 析取
• exclusive or 异或
• precedence 优先级

1 Propositional Logic

1.1 Proposition

Definition

A proposition is a declarative sentence that is either true or false,but not both.

• Beijing is the captial of China.
• He shouted, “Stop!”(光看这句话我们不知道真假，但是在那一刻地点那一时刻，他要么说了，要么没说，一定可以确定真假)
• x+1=2(这不是命题，因为我们无法判断真假，注意与上一个区别，上一个是我们不知道真假，但可以确定真假，譬如问一下在场的人，而这一个无法确定，因为我们不知道x的取值)
• Open the door.(祈使句，不是陈述句)
  Anyway,it doesn’t matter.

Propositional Logic is the area of logic that deals with propositions.

• Propositional variables: each represents a proposition like “Today is Friday.”
• Truth value:T(if a proposition is true),F
• Logical operators(Connectives) :be used to form compound propositions from existing propositions

1.2 Logical Operators

• Negation
• Conjunction (p和q都真才为真)
• Disjunction (p和q至少有一个为真即为真)
• Exclusive OR (p和q真值不同时为真)

1.2.1 Conditional Operator

Definition

Let and be propositions.The conditional statement(implication),is the proposition “if ,then .”

The conditional statement is false only when is true and is false.

Equivalent Forms

• If p,then q
• p implies q
• q if p
• q when p
• q whenever(every time that,每当，只要) p
• p is sufficient condition for q
• p only if q
  (只有q为真时，p才能是真的，也就是说p can’t be true when q isn’t true,q为假时p为假(事实上，这个命题就只规定了这一件事)，所以p为真q为假时这个命题为假；如果p是假的，那么q是真是假这个命题都是对的，因为这个命题只要求p是真的时，q必须是真的)
• 让我们举个例子，我去上课only if我醒了，即只有我醒了，我才会去上课，但这并不说明我一定去上课了，其实就是在说我醒了是我去上课的必要条件，一定要我醒了，我才能去上课，而不是如果我醒了我就去上课(如果你因此更晕了，那就记住它或者忘掉我所说的orz)
• unless (q是真的，除非p是假的，也就是p为真时q一定为真，p为假时这个命题一定正确，因为没说p是假的时对q有什么要求，而p是假的但q是真的时这个命题就是假的，因此它与implication等价)

Converse of Conditional Statement :

二者不一定等价

Inverse of Conditional Statement :

二者不一定等价

Contrapositive of Conditional Statement :

二者等价
When two compound propositions always have the same truth value in all possible cases we call them equivalent

1.2.2 Biconditional Operator

is the position “p if and only if q.”
即

p和q同时为真或同时为假时，为真

如果是永真式，那么称p和q是逻辑等价的，其中p和q是复合命题
注意一定要求是永真式，如果说：如果是真的，那么p和q等价，这样是不对的
例如，p:今年是2026年，q:我今天喝了水
那么在2026年，有一天我喝了水，那么那一天就是真的，我就可以得到今年是2026年等价于我今天喝了水，即如果我今天喝了水，那么今年是2026年，这是不合理的，(而且根据上面的定义，这意味着我今天喝水和今年是2026年一定同时成立或同时不成立)我们必须要求是恒真的，即p和q只可能同时为真或者同时为假，不能有其他情况，而这个例子中，完全可以是今年是2027年而我今天喝了水，就是假的了

如果你还是很晕，那么记住下面这点：
我们说复合命题p和复合命题q等价，只是在陈述“p和q的真值一定一样”或“永远是真的”，并不是一个复合命题，虽然确实可能为真可能为假，但更多时候我们把它看作一种关系的描述“p和q的真值一定一样”

另一方面，是真的只是说明p是真的，q是真的，或p是假的，q是假的，它就像是真值表中某一行的各种值，并没有说明“p和q只能同时真或同时假”，而更多是一种对p和q真值的限制的陈述

1.2.3 Precedence of Logical Operators

Operator	Precedence
	1
	2
	3

1.3 Translation

You can access the Internet from campus only if you are a computer science major or you are not a freshman.
Let
a:”you can access the Internet from campus”
c:”you are a cs major”
f:”you are a freshman”

1.4 Consistent System Specifications

Definition

A list of propositions is consistent if it is possible to assign truth values to the proposition variables so that each proposition is true.

2 Propositional Equivalences

2.1 Classification of Compound Propositions

• Tautology:compound proposition that is always true
• Contradiction:compound proposition that is always false
• Contingency neither a tautology nor a contradiction
  For example, is a tautology

2.2 Logical Equivalences

Definition

The compound propositions and are called logically equivalent if is a tautology.
Notation:

Name	Equivalence
Identity laws
Domination laws
Idempotent laws(幂等律)
Commutative laws
Associative laws
Distributive laws
De Morgan’s laws
Absorption laws
Implication law
Equivalence law

2.3 Propositional Satisfiability

A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true.When no such assignments exist,the compound proposition is unsatisfiable.

3 Predicates and Quantifiers

3.1 Predicate

Definition

A predicate (propositional function) is a statement that contains variables.Once the values of the variables are specified,the function has a truth value.

• ””,and is false
• ” is the ’s best friend”

3.2 Quantifiers

Predicate Logic:the area of logic that deals with predicate and quantifiers.

3.2.1 Universal Quantification

Definition

A universal quantification of ,denoted by ,is the statement “P(x) for all values of x in the domain.”

Domain:range of the possible values of the variable x
An element for which P(x) is false is called a counterexample(反例) of

Example

1. The truth value of is false if the domain consists of all real numbers.

2. Express the following statement as a universal quantification:
   “All lions are fierce.”

Let Q(x) denote the statement “x is fierce.”
(1) Assuming that the domain is the set of all lions.

(2) Assuming that the domain is the set of all creatures.
P(x): “x is a lion.”

3.2.2 Existential Quantification

Definition

An existential quantification of P(x),denoted by ,is the statement “There exists an element x in the domain such that P(x).”

Example

Express the following statement as an existential quantification.
“Some real numbers are rational numbers.”

Let Q(y): y is a rational number
(1) Assuming that the domain is the set of all real numbers.

(2) Assuming that the domain is the set of all complex numbers.Let R(y): y is a real number

存在唯一：

3.2.3 Quantifiers with Restricted Domains

Example

Domain: the real numbers
means for every real number with > 0,
It’s logically equivalent to

3.2.4 Precedence of Quantifiers

The quantifiers have higher precedence than all logical operators from propositional calculus.

3.2.5 Binding Variables

When a quantifier is used on the variable x,we say that this occurence of the variable is bound(受约束的).

A variable neither quantified nor specified with a value is said to be free.

All the variables in a propositional function must be quantified or set equal to a particular value to turn it into a proposition.
例如中x被存在量词作用，是约束变元，y是自由变元，当然这不是命题，可以是谓词，根据上面所述，y也必须被赋值或者被量词作用才能变成命题
(一般默认x和y的取值范围是一样的，但是约束x和y的domain其实可以不一样)

Scope of a quantifier:the part of a logical expression to which the quantifier is applied.
这里或操作符左右的x是不一样的，比如左边可以存在x=1，这时右边是要任意的x属于论域，这两个x不是一个东西

3.3 Logical Equivalences Involving Quantifiers

Definition

Statements involving predicates and quantifiers are logically equivalent iff they have the same truth value for every predicate substituted into these statements and for every domain of discourse used for the variables iin the expressions.

(The domain is same，这里如果等式右侧A的x的domain和B的x的domain不一样，是不等价的)

x is not occurring in A

Equivalence	Proof
	分A为T或F两种情况证明
上式任意或存在选一个，与变成或或者或变成与，四种情况都成立
上式任意变成存在仍成立
	先去掉箭头，再利用第三行
上式任意、存在互换仍成立

3.4 Translation

Example

All lions are fierce.
Some lions do not drink coffee.

P(x):x is a lion
Q(x):x is fierce
R(x):x drinks coffee
Assume the domain consists of all creatures.

(1)
(2)
注意不能是，这样的话并不是说有些狮子不喝咖啡，事实上如果x不是狮子，这个命题也是真的，就不是原来的意思了
同理(1)中不能用与，那样就变成所有的生物都是狮子而且很凶狠

3.5 Nested Quantifiers

Two quantifiers are nested if one is within the scope of the other.
可理解为遍历论域中每个x，都要存在一个y满足C(x,y)

这里是在的scope里的,体现在C(x,y)里的x受前面量词的论域限制

也可以理解成，其中为，P(x)里的x在量词的scope里

Example

Everyone has exactly one best friend.
Domain:All people

B(x,y): “y is the best friend of x.”

注意x后的括号要一直括到最后，否则B(x,z)里的x就没被量词作用，也没赋值，就不是命题
同理y,z右侧的括号也要括到最后
也可以写成嵌套量词

过程是先遍历论域中的x，对每一个x要找到一个y满足：遍历论域中的z，即成立

3.5.1 The Order of Quantifiers

The order of nested quantifiers matters if quantifiers are of different types.

Example

论域：实数

存在一个x，使得对所有y，x+y=1，这是假命题

对任意y，都存在一个x使得x+y=1，这是真命题

3.5.2 Negating Nested Quantifiers

Successively apply the rules for negating statements involving a single quantifier.
这时这样理解的好处就凸显了
可理解为遍历论域中每个x，都要存在一个y满足Q(x,y),这里是在的scope里的，也可以理解成，其中为，P(x)里的x在量词的scope里

例如
等价于
等价于
等价于

4 Functionally Complete

Definition

A set of logical operators is called functionally complete if every compound proposition is logically equivalent to a compound proposition involving only this set of logical operators.

比如与、或、非构成的逻辑操作符集合就是functionally complete的
与非也可以(跟数逻联动了)

5 Propositional Normal Forms

Literal(字面量):或者

Disjunctions (conjunctions) with one or more literals as disjuncts (conjuncts) are called disjunctive (conjunctive) clauses.

例如
是析取子句
是析取子句，也可以是合取子句
不是clause(子句)

5.1 Normal Forms(CNF&DNF)

A conjunction with one or more disjunctive clauses is said to be in conjunctive normal form.

A disjunction with one or more conjunctive clauses is said to be in disjunctive normal form.

例如
是CNF
如果看作disjunctive clause就是CNF，看作conjunctive clause就是DNF
是CNF(两个disjunctive clause)，也可以是DNF(看作一个conjunctive clause)

5.2 How to Obtain Normal Forms

1. 利用和和去掉箭头
2. 德摩根律去掉非
3. 利用分配律统一符号

例 求full DNF

注意这里是用的两个箭头那个

自己做，full DNF要化成最小项之和
如果不会了，可以尝试用数逻的那种表达做hh

5.3 Prenex Normal Form

所有量词提前，那么这个statement is in prenex normal form

是全称量词或者存在量词，是不含量词的谓词
没有量词的命题也是prenex normal form

方法：

1. 外面的箭头去掉
2. 量词德摩根律把非放到量词里面
3. 重新命名变量
   例如这两个变量是独立的，它们的domain可能不一样，不能写成而应写成
   

第二问利用step4最后两条，z、u、v可以随意交换，但不能把v放到x、y前面，因为和不一样，不过z和u可以放最前面，因为可以随意交换

为什么step4最后两条是合理的？
例如
我们把看作
那么原式等价于
现在对于括号内的式子，我们再把看作(因为P中没有y)
那么
所以原式等价于
即
这跟我们上面所说的如何理解嵌套量词是相符的

6 Rules of Inference

argument: 一系列proposition(称作premises)，有一个conclusion
proof: 证明某个argument是valid的
valid: 如果preceding statements(propositions)都为真，那么结论是真的，我们称这样的argument是valid的

例
前提：如果今天是晴天，那么今天是周五；今天是晴天(p)
结论：今天是周五(q)
如果是tautology，那么这个argument就是valid的
事实上，这个argument确实是valid的，尽管它看上去并不对(因为它的前提事实上是假的，但我们判断时会假设前提都是真的)

argument form: 形式上的argument，也就是它的前提和结论可能并不是具体的命题，而是命题变量
如果不论命题变量取值是啥，即是什么命题，对应的具体的argument都是valid的，那么称这个argument form是valid的
也就是说argument form更偏向一种模板、规范

比如有这么一个argument form
前提是
结论是
如果是tautology，那么这个argument form是valid的

接下来我们介绍一些有用的模板(valid argument forms)，不论命题变量取什么值，只要是这个形式的argument都是valid的，这些模板构成了Rules of Inference

Rule of Inference	Name
——	Modus ponens
——	Modus tollens
——	Hypothetical syllogism
——	Disjunctive syllogism
——	Addition
——	Simplification
——	Conjunction
——	Resolution

6.1 Using Rules of Inference to Build Arguments

如何证明一个argument是valid的？
假设前提是真的
利用逻辑等价和推理规则，推出结论是真的

Example

Premises:
It is not sunny this afternoon
We will go swimming only if it is sunny
If we do not go swimming, then we will take a canoe trip
If we take a canoe trip, then we will be home by sunset

Conclusion:
We will be home by sunset

p: “It’s sunny this afternoon.”
r: “We will go swimming.”
s: “We will take a canoe trip.”
t: “We will be home by sunset.”

那么假设就是

1. (Premise)
2. (Premise)
3. (Modus tollens 1,2)
   这里我们已经用了一次推理规则，我们假设前提是真的，根据推理规则，上述三步是一个有效论证，那么我们就得到是真的，这又可以作为我们证明的条件
4. (Premise)
5. (Modus ponens 3,4)
6. (Premise)
7. (Modus ponens 5,6)

如果结论是这样的形式，我们可以把作为假设
因为
(读者可以自己证明)

6.2 Rules of Inference for Quantified Statements

Rule of Inference	Name
——	Universal instantiation
for an arbitrary c ——	Universal generalization
—— for some element c	Existential instantiation
for some element c ——	Existential generalization
, where a is a particular element in the domain ——	Universal modus ponens

错在哪？

c只对应那一个a，并不是随便取一个a都对应的c
比如G(x,y): x+y=0
我随便取一个a，确实
于是有一个c，我们知道c=-a，G(a,-a)，要注意a是一个具体的值(我们所谓的任取一个a，这个a都是一个具体的值，只是我们强调它可以是任何值)也就是说这个c只对这一个a成立
但是对任意的x，G(x,-a)都对吗？取x=a+1就错了

7 Proofs

术语	译文
axiom	公理
lemma	引理
corollary	推论
conjecture	猜想

定理是怎么描述的

1. Implied universal quantifiers
   e.g. For all positive real numbers and , if , then
2. Implicit implications
   e.g. “The square of an odd integer is odd.”
   “For all integer , if is odd, then is odd.”

7.1 Methods of Proving Theorems

7.1.1 Direct Proofs

对于
假设前提P(c)是真的，然后证明Q(c)是真的

我的理解依然是，证明就是证明一个论证是有效论证
看似只有结论，但是其实是有前提的，很多我们知道的知识、数学公理都是前提；另一方面，也不能说是没前提，由我们前面的知识，P(c)可以是前提，这时结论变成Q(c)，这时上面说的方法其实就是在证明这是个有效论证

7.1.2 Proof by Contraposition

例 “完美数”是它所有除自己外的因数之和等于自身的数，如6=1+2+3，证明“完美数”不是素数

也就是说，对任意正整数s，如果s是完美数，那么s不是素数
这等价于证明对任意正整数s，如果s是素数，那么s不是完美数
如果s是素数，那么除去它自己的因数之和为1，而s不等于1，所以s不是完美数
我们证明了是真的
由逻辑等价，是真的
Q.E.D

7.1.3 Vacuous Proof

前提是错的，那么是真的
这看上去和我的理解“证明就是展示一个论证是有效的的过程”有些矛盾

例 证明“对任意实数x，如果x的平方小于0，那么x大于1”
证明：

只需证明任意c，
for an arbitrary c, (Additional Premise)
(Premise 数学公理)

爆炸原理(ex contradictione quodlibet) 矛盾推出任何命题的形式都是有效论证，即 is tautology.

上面好像有点复杂，其实可以不把p推q的p作为假设
任意的c， (Premise 数学公理)
由implication的定义，为真
由UG

7.1.4 Trivial Proof

如果q是真的，那么是真的
何意味

7.1.5 Proof by Contradiction

1. 证明时，可以假设，如果得到了矛盾
   即得到
   也就是说我们先证明，作为premise
   证明完这个，这个又可以成为我们的premise(我们已经证明的东西可以作为premise)
   这等价于
   由implication的定义，

2. 证明，其实上面证明时也是有前提的，如数学公理等，所以也可以理解成的形式
   依旧先证明推出矛盾，通常这个矛盾就是(与题意矛盾)
   我们已经证明的东西可以作为premise，和上面一样就能得到是真的

我讲的可能有些啰嗦，因为我试图把“证明就是证明一个论证是有效的”这个理解贯彻到底，所以在解释各种证明方法到底是在干嘛。如果你已经理解了，可以不用看我写的东西。我想大多数人应该都不用看。

证明没有最大的素数
假设有最大的素数s
对于r=2×3×5×…×s
r+1要么是素数要么是合数，如果是素数，那么s不是最大的素数
如果r+1是合数，由算术基本定理，它可以分解为若干个素数的乘积，而这些素数不能是2到s的素数(nk+1不是k的倍数)，所以r+1的因数应该有一个比s大的素数
: s是最大的素数
我们假设得到
所以为真

7.1.6 Proofs of Equivalence

怎么证明是等价的
即证明

7.1.7 Proof by Cases

把拆成

例 证明：如果整数n不被2整除也不被3整除，那么被24整除
或，然后分别证明即可