离散数学 第一章 逻辑与证明

逻辑--研究--推理
研究推理过程是否正确
研究语句之间的联系

下面的语句中，哪一个是真的或者假的(但不能二者都是)?
(a)能整除7的整数只有1和7本身。
(b)在宇宙中，地球是唯一有生命的星球。
(c)请买两张星期五音乐会的票!
命题的定义：一个语句，如果或真或假(但不是既真又假），称为一个命题。

p,q命题
p and q,p∧q,合取 (并且)
p or q,p∨q, 析取 （或者）
复合命题p∧q的真值由下列 真值表 来表示:

复合命题p∨q的真值由下列 真值表 来表示:

p的否定，表示为：¬p，是命题 非p的意思。 真值表 为：

例：如果数学系得到额外的2万元,就再聘用一个教师。
如果 p 则q 称为条件命题并表为p→q
命题 p 称为 假设 (或前件)，命题q称为 结论 (或后件)。
p：数学系得到额外的两万块钱
q：数学系再聘用一个教师
条件命题的真值由下面的 真值表 定义

例：当A，B。
A→B，A是B的充分条件
B→A，A是B的必要条件
A←→B，A是B的充分必要条件

命题：p→q，q→p则称为逆命题。读作：p蕴含q，
p当且仅当q称为双条件命题,表示为：

设复合命题p和q是由p1 ... pn组成,如果不管p1 ... pn取什么值,p和q总是同时为真或同时为假，就说p和q逻辑上是等价的,表为 p≡q 。
德·摩根定律
¬(p∨q)≡(¬p)∧(¬q) 和 ¬(p∧q)≡(¬p)∨(¬q)

常用表：

—个条件命题 p→q 的逆反式(或转置）是命题 (¬q)→(¬p) 。
条件命题 p→q 的逆反式 (¬q)→(¬p) 是逻辑等价的。

例: p: n是一个奇数，p不是一个命题。因为真假值取决于n 。

令p(x)为包括变量x的语句,令D是一个集合。
如果对于D中的每一个x，p(x)是一个命题，我们称p是一个 命题函数 （对于D,而称D是p的个体域(定义域)。

命题函数,本身既不为真，也不为假,而对于每个个体×,p(×)是一个命题。

语句:所有x, p(x)可以写为 ∀ x，p(x)
语句:存在x, p(x)可以写为 ∃ x，p(x)

语句:对于每个实数x,x²>=0，是一个全称量词语句。
个体域是实数集合。该语句为真。
语句：对于每一个实数×，如× >1,则×＋1 >1。该语句为真。
语句：对于 某些 正整数n，如n是素数,则n+1，n+2,n+3,n+4都不是素数。该语句为真。
例：命题p：对于所有的实数x,x²-1 >0 ，那么x=1呢?
要证明对于所有的x,p(×)为假。找出一个或一些x使 p不满足就可以了。

* ∃ x P(×) =F ≡ 不存在 x,P(×) ≡ ∀ x，P(×)

如：p 是一个命题函数,(a)和(b)中的每一对命题总有同样的真假值(即同为真或同为假）。
(a) ¬(∀ x，P(×))；∃ x, ¬P(×)。
(b) ¬(∃ x, ¬P(×))；∀ x，P(×)。

设个体域是实数集合,语句
对于每个x，存在y，x十y=0为真
而把语句倒过来
存在y，对于每个x，X十y=0为假
不可随意更换位置

数学系统
公理----定义----未定义项
论证一个定理为真的过程称为证明
定理的通常形式为:
对于所有的x1,X×n，如
p(x1,×,----n),则q(x1,×r------n)

必须看到三步，归纳基础，归纳假设，归纳证明。
设对于每个正整数n，我们有一个陈述s(n)，假设s(1)为真;
如对于所有的i<n+1，s(i)为真,s(n+1)也为真。
则对于所有正数n，s(n)为真。
数学归纳法的两种形式:
强形式：i<n+1,s(i),s(n+1)
—股：若S(n)为真则S(n+1)

例：用归纳法证明5 ^n-1 能被4整除。
n=1时显然为真，设5 ^n-1 可被4整除
5 ⁿ⁺¹ -1=5·5 ^n-1 =(5 ^n-1 )＋4- 5 ⁿ 可被4整|除
所以对于n=1,2... ,5n-1能被4整除。
对任意的自然数×和n,x ^n-1 能被×-1除尽

前n个自然数之和为n(n+1)/2。证明:对n进行归纳。
当n=1时，有S(1)=1=1×(1+1)/2，故命题成立。
假设前n个自然数之和S(n)为n(n+1)/2。接着证前n＋1个自然数之和S(n+1)=(n+1)(n+2)/2。
根据S(n)的定义，有S(n+1)=S(n)+n+1，
又由假设S(n)= n(n+1)/2，
于是可以推得S(n+1)=n(n+1)/2+n+1=(n+2)(n+1)/2，命题得证。