Discrete mathematics and its app

2019-08-25 本文已影响0人赫尔特

Discrete mathematics and its applications笔记
第一章
1.The conditional statement p-->q is false when p is true and q is false,and true otherwise.

2.p-->q is called a conditional statement .A conditional statement is also called an implication.(蕴含)

3. $p\rightarrow q \ can\ be\ read\ as$ "if p,then q", "q if p" or "p only if q"...(注意p only if q和 p if q的区别，可以拿 $p:n\geq0与q:n>0作验证$ )

"p only if q" $=$ "p cannot be true when q is not true."

4.A disjunction of conjunctions where every variable or its

negation is represented once in each conjunction is called a

minterm.

An expression which is the disjunction of minterms is called

Disjunctive Normal Form (DNF)

A conjunction of disjunctions where every variable or its negation

is represented once in each disjunction is called a maxterm.

An expression which is the conjunction of maxterms is called

Conjunctive Normal Form (CNF).

p NAND q is denoted by p|q.

q NOR q is denoted by p $\downarrow$ q.

6.Find a compound proposition logically equivalent to p-->q using

only the logical operator $\downarrow$ .

因为(p $\downarrow$ p) $\equiv!p$
p-->q:

p	q	?
T	T	T
T	F	F
F	T	T
F	F	T

而 $(p\downarrow q)\downarrow q:$

p	q	?
T	F	T
T	T	F
F	T	F
F	F	F

故答案可以是:
$((p\downarrow q)\downarrow q)\downarrow ((p\downarrow q)\downarrow q)$
还可以是
$((p\downarrow p)\downarrow q)\downarrow ((p\downarrow p)\downarrow q)$
同理也有(p|p)=!p,也可以只用|作为命题的等价形式。

7.对于只有命题p,q参与的表达式，其真值表可能有16种（ $2^4$ ）

8. $\forall 与\exists的优先级比其他逻辑运算符号的优先级都要高。$

9.量词传递规则:

存在量词可以在disjunction中传递，不能在consjunction传递。

全称量词可以在consjunction传递，不能在disjunction传递。
比如:
$\forall x(P(x)\land Q(x))\equiv \forall xP(x)\land \forall xQ(x)$

3
11.把"For every person x,if x is a student in this class then x has studied calculus."改写成逻辑表达式。
用S(x)表示x在班里，用C(x)表示x学了微积分。则：

注意不能写成

"Every student in this class has visited either Canada or Mexico."
用x表示所有人，S(x)表示x在这个班上，M(x)表示x去过墨西哥，则：
$\exist x(S(x)\land M(x))$
注意这里不能写成 $\exist x(S(x)\rightarrow M(x))$ ，因为F-->T和F-->F也是对的。

12.In logic, statements $p$ and $q$ are logically equivalent if they have the same logical content. That is, if they have the same truth value in every model

13.推理（inference）
All but the final proposition in the argument are called premises(前提)
and the final proposition is called the conclusion.An argument is valid if the truth of all its premises implies that the conclusion is true.
(The conclusion is true if the premises are all true.)

14.推理规则

上述规则可以简化推理步骤，不然用比较真值表的办法，需要写的式子是呈指数增长的。

15.Some Terminology（一些术语）
theorem定理 lemma引理 corollary推论 conjecture推测

16.证明方法
证明 $p\rightarrow q$
direct proofs( $p\rightarrow q$ )
proof by contraposition( $^\rightharpoondown q\rightarrow {^\rightharpoondown p})$
vacuous proof (p $\equiv$ false)
trivial proof (q $\equiv$ true)
proofs by contradiction(反证法)

17.证明多个命题等价(equivalence)，可以用下面这个恒等式证明

18.更多的证明方法
（1）（proof by cases）证明

6
可以利用

exhaustive proof(穷举法)

(2)Without Loss of Generality(不失一般性)
$证明：\forall x,y>0,0<r<1,有(x+y)^r<x^r+y^r$
$\begin{aligned} &不失一般性，我们假设x+y=1\\ &(因为当x+y=t不等于1时,有(x/t)+(y/t)=1\\ &这时证明(x+y)^r<x^r+y^r\\ &\Leftrightarrow((x/t)+(y/t))^r<(x/t)^r+(y/t)^r)\\ &0<x<1,0<y<1...\\ &x^r+y^r>x+y=1 \end{aligned}$

(3)证明存在性问题有两种办法
Constructive Existence（找到一个特例）
Nonconstructive Existence(有点类似反证法)
比如： $证明存在无理数x,y,x^y是有理数$
$\begin{aligned} &令x=\sqrt2,y=\sqrt2.\\ &若{\sqrt2}^{\sqrt2}不是有理数，\\ &设x={\sqrt2}^{\sqrt2},y=\sqrt2\\ &则({\sqrt2}^{\sqrt2})^{\sqrt2}=2是有理数。 \end{aligned}$
（4）策梅洛定理,表明在二人参与的游戏/博弈中，如果满足：
--------游戏的步骤数有限
--------信息完备(二人都了解游戏规则，了解游戏曾经所发生过的信息)
--------不会产生平局
--------确定性(游戏中不会加入随机因素)
则先行一方有必胜策略，或者后行一方有必胜策略。
（Chomp游戏必定有先手必赢的策略。）
（5）backforward reasoning(由果索因)