Skip to content

Latest commit

 

History

History
276 lines (212 loc) · 3.52 KB

第1章 基础:逻辑和证明 2.md

File metadata and controls

276 lines (212 loc) · 3.52 KB

1.5 嵌套量词

即量词作用域的叠加。如 $$ \forall x \exists y\ (x+y=0) $$ 即对于所有x,都存在一个y,使得x+y=0。

再来对于我们熟悉的加法交换律,可以采用下面的形式来表示: $$ \forall x \forall y\ (x+y=y+x) $$

注意事项:量词的顺序

$$ 式子1\ \forall x \forall y\ (x+y=y+x) \\ 式子2\ \forall y \forall x\ (x+y=y+x) $$

在上面的式子1和式子2中,前面量词的交换是不会产生影响的,两个命题都为真。但是下面这种就不行了: $$ 式子1\ \forall x \exists y (x+y=0) \ 式子2\ \exists y \forall x (x+y=0) $$

式子1是真命题,对于所有x,都存在一个y,使得x+y=0。

但是式子2的含义则是,存在一个y,使得所有x能满足y+x=0,就我目前的知识水平来说,感觉这种数不存在。

也有一种常见表现形式: $$ P(x,y)代表x+y=0,\forall x \exists y P(x,y) $$

1.6 推理规则

$$ \frac{ p \rightarrow q \\ p }{ \therefore q } $$

在推理过程中,需要保证前提都为真,在前提为真的情况下,结论必定为真。


假言推理

$$ \frac{ p\\ p \rightarrow q }{ \therefore q } $$

取拒式

$$ \frac{ \neg q \\ p \rightarrow q }{ \therefore \neg p } $$

假言三段论

$$ \frac{ p \rightarrow q \\ q \rightarrow r }{ \therefore p \rightarrow r } $$

析取三段论

$$ \frac{ p \vee q \\ \neg p }{ \therefore q } $$

附加论

$$ \frac{p}{\therefore p \vee q} $$

化简率

$$ \frac{p \wedge q}{\therefore p} $$

合取率

$$ \frac{p\q}{\therefore p \wedge q} $$

消解率

$$ \frac{ p \vee q \\ \neg p \vee r }{ \therefore q \vee r } $$

量化命题的推理规则

全称实例

$$ \frac{ \forall x P(x) }{ \therefore P({x}_{0}) } $$

全称引入

$$ \frac{ P(c),c为任意值 }{ \therefore \forall x P(x) } $$

存在实例

$$ \frac{ \exists x P(x) }{ \therefore p(c),c为某一特定值 } $$

存在引入

$$ \frac{ P(c),对于某个值c }{ \exists x P(x) } $$

1.7 证明导论

直接证明

$$ \frac{ p \\ q }{ \therefore p \rightarrow q } $$

例子: $$ p:n是奇数时 \ q: {n}^{2} 也是是奇数 $$ 只需要证明在p为真的情况下,q也肯定为真,就能证明上面的命题为真。

间接证明

$$ p \rightarrow q \equiv \neg q \rightarrow \neg p $$

这里补充一下上面的内容的真值表:

p q 逆q 逆p p蕴含q 逆q蕴含逆p
0 0 1 1 1 1
0 1 0 1 1 1
1 0 1 0 0 0
1 1 0 0 1 1

$$ \frac{ \neg q\\ \neg p \\ \neg q \rightarrow \neg p }{ \therefore p \rightarrow q } $$

例子: $$ p:3n+2 是奇数 \ q:n是奇数 $$ 换个思路: $$ \neg q:n不是奇数 \ \neg p:3n+2 不是奇数 $$ 证明: $$ k \in \textbf{N} \ 3n+2 = 2k \ n+2n = 2(k-1) \ 2n 不是奇数,2(k-1)也不是奇数,所以n肯定不是奇数 \ $$

归谬证明

$$ \frac{ \neg p \rightarrow (r \wedge \neg r) }{ \therefore p } $$

这个我也没搞懂。

1.8 证明的方法和策略

穷举证明

例子: $$ n \in {N}_{+},n <=4 时,{(n+1)}^{3}>={3}^{n} $$ 不用管,直接拿n=1,2,3,4往里代就行了。

分情形证明

例子: $$ n \in \textbf{N},\ {n}^{2}>=n $$ 证明: $$ \begin{cases} n=0&,0=0 \ n>0&,n>=1 \ n<0&,{n}^{2}>0 \end{cases} $$

存在性证明

唯一性证明