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

1.1 命题

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

1.1.1 命题的定义

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

p	q	p∧q
T	T	F
T	F	F
F	T	F
F	F	F

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

p	q	p∨q
T	T	T
T	F	T
F	T	T
F	F	F

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

p	¬p
T	F
F	T

1.1.2 条件命题和逻辑等价

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

p	q	p→q
T	T	T
T	F	F
F	T	T
F	F	T

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

1.2命题和逆命题

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

p	q	p←→q
T	T	T
T	F	F
F	T	F
F	F	T

定义1.2.1

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

p	q	¬(p∨q)	(¬p)∧(¬q)
T	T	F	F
T	F	F	F
F	T	F	F
F	F	T	T

常用表：

p	q	p←→q	p→q	q→p	(p→q)∧(q→p)
T	T	T	T	T	T
T	F	F	F	T	F
F	T	F	T	F	F
F	F	T	T	T	T

定义1.2.2

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

p	q	p→q	(¬q)→(¬p)
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

1.3量词

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

1.3.1 定义

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

1.3.2命题和命题函数

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

所有/有些

• 所有学生都能拿到学位
• 有些学生可能不能毕业

全称量词/存在量词

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

约束变量/自由变量

• 约束变量和自由变量的定义
• 有自由变量的语句不是命题
• 没有自由变量的语句可以是命题
  例如：∀ x p(x,y)中，x就是约束变量，y就是自由变量。
  常用量词

全称量词	存在量词
所有	有些
对于每一个	对于至少一个
对于任何	存在

1.3.3 例子

语句:对于每个实数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为假
不可随意更换位置

1.4 证明

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

1.5 数学归纳法

必须看到三步，归纳基础，归纳假设，归纳证明。
设对于每个正整数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，命题得证。