第一章逻辑和证明

1.命题逻辑

1.1命题

命题是一个陈述语句（即陈述事实的语句），它或真或假，但不能既真又假
如：华盛顿特区是美利坚合众国的首都；1+1=3
可以用字母来表示命题变量，通常用p，q，r，s，···表示
如果命题是真命题，则它的真值为真，用T表示；如果它是假命题，则真值为假，用F表示
不能用简单的命题来表示（不可拆分）的命题称为原子命题
由已知命题用逻辑运算符组合而来的新命题被称为复合命题
否定运算符
令p为一命题，则p的否定记作$\lnot p$（也可记作$\bar p$），读作“非p”，指“不是p所指的情形”，p的否定的真值和p的真值相反
真值表

- 从两个或多个已知命题构造新命题的逻辑运算符也称为联结词 - 合取 - 令p和q为命题，p、q的合取即命题“p并且q”，记作$p\land q$。当p和q都为真时$p\land q$为真，否则为假 - 析取 - 令p和q为命题，p、q的析取即命题“p或q”，记作$p\lor q$。当p和q都为假时$p\lor q$为假，否则为真 - 异或 - 令p和q为命题，p、q的异或（记作$p\oplus q$）是这样一个命题：当p和q中恰好只有一个为真时时命题为真，否则为假

1.2条件语句

定义
令p和q为命题，条件语句$p\rightarrow q$是命题“如果p，则q”。当p为真而q为假时，条件语句$p\rightarrow q$为假，否则为真。在条件语句$p\rightarrow q$中，p称为假设（前件、前提），q称为结论（后件）
语句$p\rightarrow q$称为条件语句，因为$p\rightarrow q$可以断定在条件p成立的时候q为真。条件语句也称为蕴含。
逆命题、逆否命题和反命题
对于$p\rightarrow q$：
- $q\rightarrow p$（逆命题）
- $\lnot q\rightarrow \lnot p$（逆否命题）
- $\lnot p\rightarrow \lnot q $（反命题）
双条件语句
定义
- 令p和q为命题，双条件语句$p\leftrightarrow q$是命题“p当且仅当q”。当p和q有同样的真值时，双条件语句为真，否则为假。双条件语句也称为双向蕴含

1.3复合命题的真值表

例：$(p\lor \lnot q)\rightarrow (p\land q)$

1.4逻辑运算符的优先级

1.5逻辑运算和比特运算

2.命题逻辑的应用

2.1语句翻译

把自然语言语句翻译成由命题变量和逻辑联结词组成的表达式（可用来消除歧义）
例：“你可以在校园访问因特网，仅当你主修计算机科学或者你不是新生。”
令a、c和f分别表示“你可以在校园访问因特网”、“你主修计算机科学”和“你是个新生”
即$a\rightarrow (c\lor \lnot f)$

2.2系统规范说明

同语句翻译

2.3布尔搜索

逻辑联结词广泛用于海量信息如网页索引的搜索中。由于搜索采用命题逻辑的技术，所以被称为布尔搜索。
在布尔搜索中，联结词AND用于匹配同时包含两个搜索项的记录，联结词OR用于匹配两个搜索项之一或两项均匹配的记录，而联结词NOT(有时写作AND NOT)用于排除某个特定的搜索项。

2.4逻辑谜题

n皇后问题、数独等

2.5逻辑电路

命题逻辑可应用于计算机硬件的设计
由克劳德·香农（Claude Shannon）于1938年首次发现并写在他的MIT硕士论文中

3.命题等价式

3.1永真式（重言式）、矛盾式和可能式

定义
一个真值永远是真的复合命题（无论其中出现的命题变量的真值是什么），称为永真式(tautology)，也称为重言式
一个真值永远为假的复合命题称为矛盾式 (contradiction)
既不是永真式又不是矛盾式的复合命题称为可能式(contingency)

3.2逻辑等价式

定义：如果$p\leftrightarrow q$是永真式，则复合命题p和q称为是逻辑等价的。记为$p \equiv q$
有时用$\Leftrightarrow$来代替$\equiv$
例：$\lnot (p\lor q)\equiv \lnot p \land\lnot q$（德·摩根律之一）

一些等价式

3.3德·摩根律的运用

例：
令p为“我有一部手机”，令q为“我有一个便携式计算机”，那么“我有一部手机且我有一台便携式计算机”可表示为$p\land q$
那么根据德·摩根律，$\lnot (p \land q)$等价于$\lnot p \lor\lnot q$，即原命题的否定形式为“我没有一部手机或我没有一台便携式计算机”

3.4构造新的逻辑等价式

例：证明$\lnot (p\rightarrow q)和p \land\lnot q$是逻辑等价的
证明：

\[ \begin{gather} \lnot (p \rightarrow q)\equiv\lnot(\lnot p \lor q)··········由条件-析取等价式\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \equiv \lnot(\lnot p)\land\lnot q··········由德·摩根第二定律\\ \equiv p\land\lnot q··········由双重否定律 \end{gather} \]

3.5可满足性

一个复合命题称为是可满足的，如果存在一个对其变量的真值赋值使其为真（即当它是一个永真式或可满足式时)。
这样一个赋值称为这个特定的可满足性问题的一个解
当不存在这样的赋值时，即当复合命题对所有变量的真值赋值都是假的，则复合命题是不可满足的。
注意一个复合命题是不可满足的当且仅当它的否定对所有变量的真值赋值都是真的，也就是说，当且仅当它的否定是永真式。

第一章 逻辑和证明