1.1 命题
命题 是一个陈述语句(即陈述事实的语句),它或真或假,但不能既真又假.
定义1\(\qquad\)令\(p\)为一命题.则\(p\)的否定命题记为\(\neg p\)(也可以记为\(\over p\)),指"不是\(p\)所指的情形",命题\(\neg p\)读作"非\(p\)",\(p\)的否定(\(\neg p\))的真值与\(p\)的真值相反.
| \(p\) | \(\neg p\) |
|---|---|
| T | F |
| F | T |
定义2\(\qquad\)令\(p\)和\(q\)为命题.\(p,q\)的合取即命题"\(p\)并且\(q\)",记作\(p\wedge q\).当\(p\)和\(q\)都是真时，\(p\wedge q\)命题为真,否则为假.
| \(p\) | \(q\) | \(p\wedge q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
在离散数学中,有时也用"但是"表示"而且".
定义3\(\qquad\)令\(p\)和\(q\)为命题.\(p,q\)的析取即命题"\(p\)或",记作\(p\vee q\).当\(p\)和\(q\)均为假时，\(p\vee q\)命题为假,否则为真.
| \(p\) | \(q\) | \(p\vee q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
定义4\(\qquad\) 令\(p\)和\(q\)为命题.\(p\)和\(q\)的异或(记作\(p\oplus q\))是这样一个命题:当\(p\)和\(q\)中恰好只有一个为真时命题为真,否则为假.
| \(p\) | \(q\) | \(p\oplus q\) |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
兼或 是指两命题可以同时成立,异或 指两命题只有一个成立.
条件语句
定义5\(\qquad\) 令\(p\)和\(q\)为命题.条件语句\(p\to q\)是命题"如果\(p\),则\(q\)":.当\(p\)为真而\(q\)为假时,条件语句\(p\to q\)为假,否则为真.在条件语句\(p\to q\)中,\(p\)称为假设(前件,前提),\(q\)称为结论(后件).
| \(p\) | \(q\) | \(p\to q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
条件语句的其他表示方法
逆命题、逆否命题与反命题 由条件语句可以构成一些新的条件语句.特别是三个常见的相关条件语句还拥有特殊的名称. 1. 命题\(q\to p\)称为\(p\to q\)的逆命题, 2. 而\(p\to q\)的逆否命题是命题\(\neg q\to\neg p\). 3. 命题\(\neg p\to\neg q\)称为\(p\to q\)的反命题.
双条件命题
定义6\(\qquad\) 令\(p\)和\(q\)为命题.双条件语句\(p\leftrightarrow q\)是命题"\(p\)当且仅当\(q\)".当\(p\)和\(q\)有同样的真值时，双条件语句为真,否则为假.双条件语句也称为双向蕴含.
| \(p\) | \(q\) | \(p\leftrightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
双条件命题的其他表示方法
- "\(p\)是\(q\)的充分必要条件"
- "如果\(p\),那么\(q\),反之亦然"
- "\(p\)当且仅当\(q\)"
复合命题的真值表
真值表的行数\(r\)与命题个数\(n(n\in\mathcal{Z_+})\)的关系为
其中T与F各\(\dfrac{r}2\)行
给出\((p\vee\neg q)\to(p\wedge q)\)的真值表
| \(p\) | \(q\) | \(\neg q\) | \(p\vee\neg q\) | \(p\wedge q\) | \((p\vee\neg q)\to(p\wedge q)\) |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | T | T | F | F |
| F | T | F | T | F | T |
| F | F | T | T | F | F |
逻辑运算符的优先级
| 运算符 | 优先级 |
|---|---|
| \(\neg\) | 1 |
| \(\vee\) | 2 |
| \(\wedge\) | 3 |
| \(\to\) | 4 |
| \(\leftrightarrow\) | 5 |
逻辑运算和位运算
计算机用 位 表示信息.位是一个具有两个可能值的符号,即0和1.位一词的含义来自二进制 数字,因为0和1是数的二进制表示中用到的数字.我们用1表示真,用0表示假.即,1表示T(真), 0表示F(假).如果一个变量的值或为真或为假,则此变量就称为布尔变量.
| 真值 | 位 |
|---|---|
| T | \(1\) |
| F | \(0\) |
定义7\(\qquad\) 位串 是0位或多位的序列.位串的长度就是它所含位的数目.
我们分别用符号\(\vee\),\(\wedge\)和\(\oplus\)表示 按位OR、按位AND 和 按位XOR 运算.
1.2 命题逻辑的应用
语句翻译
各种人类语言常有二义性,把语句翻译成复合命题则可以消除歧义.翻译时也许需要根据语句的含义做一些合理的假设。
例1
怎样把下面的语句翻译成逻辑表达式?
"你可以在校园访问因特网，仅当你主修计算机科学或者你不是新生。"
解: 令\(a,c\)和\(f\)分别表示"你可以在校园访问因特网"、"你主修计算机科 学"和"你是个新生",上述语句可以译为
系统规范说明
在描述硬件系统和软件系统时，将自然语言语句翻译成逻辑表达式是很重要的一部分。系 统和软件工程师根据自然语言描述的需求，生成精确而无二义性的规范说明，这些规范说明可作为系统开发的基础。
系统规范说明应该是 一致的 ，也就是说，系统规范说明不应该包含可能导致矛盾的相互冲突的需求。当规范说明不一致时，就无法开发出一个满足所有规范说明的系统。
例2
确定下列系统规范说明是否一致的。
- "诊断消息存储在缓冲区中或者被重传。"
- "诊断消息没有存储在缓冲区中。"
- "如果诊断消息存储在缓冲区中，那么它被重传。"
解
令\(p\)为"诊断消息存储在缓冲区中",\(q\)为"诊断消息被重传",则, 以上语句可以表示为\(p\vee q, \neg p, p\to q\) 使\(p\)为假,则\(\neg p\)为真,此时,\(\neg p, p\to q\)均为真. 因此,该系统规范说明是一致的.
布尔搜索
逻辑联结词广泛用于大量信息搜索中，由于搜索采用命题逻辑的技术，所以称为布尔搜索。
逻辑电路
逻辑电路(或数字电路)接受输入信号\(p_1,p_2,\cdots,p_n\)，每个信号1位[或0(关)或1(开)], 产生输出信号\(s_1,s_2,\cdots,s_n\),每个1位。
下图展示了三种基本逻辑门,分别是非门(NOT),或门(OR)以及与门(AND).
1.3 命题等价式
定义1\(\qquad\)一个真值永远是真的复合命题(无论其中出现的命题变元的真值是什么),称为 永真式 ,也称为 重言式 .一个真值永远为假的复合命题称为 矛盾式 , 既不是永真式又不是矛盾式的复合命题称为 可能式 .
逻辑等价式
定义2\(\qquad\)如果\(p\leftrightarrow q\)是永真式,则复合命题\(p\)和\(q\)称为是逻辑等价的.用记号\(p\equiv q\)表示\(p\)和\(q\)是逻辑等价的.
注意
符号\(\equiv\)不是逻辑联结词,\(p\equiv q\)不是一个复合命题,而是代表"\(p\to q\)是永真式" 这一语句. 有时候用符号\(\Leftrightarrow\)来代替\(\equiv\)表示逻辑等价。
判定两个复合命题是否等价的方法之一是使用真值表.特别地,复合命题\(p\)和\(q\)是等价的,当且仅当对应它们真值的两列完全一致
常用的逻辑等价式
定义3\(\qquad\)合取与析取 只要\(p_1,p_2,\cdots,p_n\)为命题,\(p_1\vee p_2\vee\cdots\vee p_n\)和\(p_1\wedge p_2\wedge\cdots\wedge p_n\)均有定义.除此以外,德摩根定律可以推广为
和
或简写为\(\neg(\bigvee\limits_{j=1}^{n}p_j)\equiv\bigwedge\limits_{j=1}^{n}\neg p_j\)和\(\neg(\bigwedge\limits_{j=1}^{n}p_j)\equiv\bigvee\limits_{j=1}^{n}\neg p_j\).
构造新的逻辑等价式
利用上表中逻辑等价式可以构造出新的命题.
例1
试证明 \(\neg(p\to q)\equiv p\wedge\neg q\)
证明:
例2
试证明 \(\neg(p\vee(\neg p\wedge q))\equiv\neg p\wedge\neg q\)
证明:
命题的可满足性
如果存在一个对其变元的真值赋值使其为真,则该复合命题称为是 可满足的 .反之,则称该符合命题是 不可满足的.
当我们找到一个特定的使得复合命题为真的真值赋值时，就证明了它是可满足的。这样的一个赋值称为这个特定的可满足性问题的一个 解.
由可满足性的定义可以知道,永真式和可能式是可满足的;矛盾式是不可满足的.
可满足性的应用
\(n\)皇后问题
\(n\)皇后问题要求在一个\(n\times n\)的棋盘上放置\(n\)个皇后,并且每一行,每一列以及每一对角线只存在一个皇后. 如图为一个\(8\times8\)的\(8\)皇后的解.
分析: 1. 确保每一行至少有 \(1\) 个皇后: $$ Q_1 = \bigwedge\limits_{i=1}^n \bigvee\limits_{j=1}^n p(i, j) $$
-
确保每一行至多有 \(1\) 个皇后: $$ Q_2 = \bigwedge\limits_{i=1}^n \bigwedge\limits_{j=1}^{n-1} \bigwedge\limits_{k=j+1}^n (\neg p(i, j)) \vee (\neg p(i, k)) $$
-
确保每一列至多有 \(1\) 个皇后: $$ Q_3 = \bigwedge\limits_{j=1}^n \bigwedge\limits_{i=1}^{n-1} \bigwedge\limits_{k=i+1}^n (\neg p(i, j)) \vee (\neg p(k, j)) $$
-
确保对角线不包含两个皇后:
- 左下到右上的对角线： $$ Q_4 = \bigwedge\limits_{i=2}^n \bigwedge\limits_{j=1}^{n-1} \bigwedge\limits_{k=1}^{\min(i-1, n-j)} (\neg p(i, j)) \vee (\neg p(i-k, k+j)) $$
-
左上到右下的对角线: $$ Q_5 = \bigwedge\limits_{i=1}^n \bigwedge\limits_{j=1}^{n-1} \bigwedge\limits_{k=1}^{\min(n-i, n-j)} (\neg p(i, j)) \vee (\neg p(i+k, k+j)) $$
-
综合公式: $$ Q = Q_1 \wedge Q_2 \wedge Q_3 \wedge Q_4 \wedge Q_5 $$
1.4 谓词和量词
谓词
涉及\(n\)个变量 \(x_1,x_2,\cdots,x_n\) 如的语句可以表示成,
形式为 \(P(x_1,x_2,\cdots,x_n)\) 的语句是命题函数 \(P\) 在"\(n\)元组 \((x_1,x_2,\cdots,x_n)\) 的值，\(P\) 也称为"\(n\) 位谓词"或"\(n\)元谓词".
描述合法输入的语句叫做 前置条件，而程序运行的输出应该满足的条件称为 后置条件.
量词
处理谓词和量词的逻辑领域称为 谓词演算。
许多数学命题断言某一性质对于变量在某一特定域内的所有值均为真，这一特 定域称为变量的 论域(或 全体域)时常简称为 域.
全称量词
定义1\(\qquad\)\(P(x)\)的全称量化是语句
符号\(\forall xP(x)\)表示\(P(x)\)的全称量化,其中\(\forall\)称为 全称量词。命题 \(\forall xP(x)\) 读做"对所有\(x\),\(P(x)\)"或"对每个\(x\),\(P(x)\)". 一个使\(P(x)\)为假的个体称为\(\forall xP(x)\)的反例.
存在量词
定义2\(\qquad\)\(P(x)\)的存在量化是语句
符号\(\exists xP(x)\)表示\(P(x)\)的全称量化,其中\(\exists\)称为 存在量词.
Note
"对某些","至少有一个"或"有"; 存在量词可读做 "有一个\(x\)满足\(P(x)\)" "至少有一个\(x\)满足\(P(x)\)" 或 "对某个\(x\)，\(P(x)\)".
全称量词和存在量词可以用如下的方式进行表示
如果\(P(x)\)是语句"\(x>10\)"，论域为不超过4的正整数，则\(\exists P(x)\)的真值是什么?
解: 论域为\(\{1,2,3,4\}\),则
因为\(P(4)=4^2>10\),所以\(\exists P(x)\)为假.
唯一性量词
用符号\(\exists!\)或\(\exists_1\)表示唯一性量词,这种表示法是指"存在一个唯一的\(x\)使得\(P(x)\)为真"。
优先级
量词\(\forall\)和\(\exists\)比命题演算中的所有逻辑运算符都具有更高的优先级.
\(\forall P(x)\vee Q(x)\)表示\((\forall P(x))\vee Q(x)\)而不是\(\forall (P(x)\vee Q(x))\).
变量绑定
当量词作用于变量\(x\)时，我们说此变量的这次出现为约束的。 一个变量如果没有被量词约束或设置为等于某一特定值,则它的出现被称为是自由的.
命题函数中的所有变量出现必须是约束的或者被设置为等于某个特定值的，才能把它转变为一个命题。
涉及量词的逻辑等价式
定义3\(\qquad\)涉及谓词和量词的语句是逻辑等价的当且仅当无论用什么谓词代入这些语句,也无论为这些命题函数里的变量指定什么论域,它们都有相同的真值.我们用\(S\equiv T\)表示涉及谓词和量词的两个语句\(S\)和\(T\)是逻辑等价的.
量化表达式的否定
1.5 嵌套量词
嵌套量词 是指一个量词出现在另一个量词的作用域内.
在处理多个变量的量化式时,可以借助嵌套循环的思想来理解.
- 对于 \(\forall x\forall yP(x,y)\)，当所有情况均为真时，结果为真；否则为假
- 对于 \(\forall x\exists yP(x,y)\)，对于每一趟外层循环，只要有一种子情况为真，结果为真；否则为假
- 对于 \(\exists x\forall yP(x,y)\)，如果存在一趟外层循环，其所有子情况均为真，结果为真；否则为假
- 对于 \(\exists x\exists yP(x,y)\)，只要有一种情况为真，结果为真；否则为假
1.6 推理规则
命题逻辑的有效论证
定义1
论证是一连串的命题。 前提是除了论证中最后一个命题外的其他命题 结论是论证中最后那个命题 论证形式是一连串涉及命题变量复合命
有效性(valid) 无论用什么特定命题来替换中的命题变量，如果前提均真时结论为真，则称该论证形式是有效的. 当一个论证的所有前提为真蕴含着结论为真,则这个论证是有效的.
当\((p_1\wedge p_2\wedge\cdots\wedge p_n)\to q\)是永真式时,以\(p_1,p_2,\cdots,p_n\)为前提,以\(q\)为结论的论证形式是有效的
命题逻辑的推理规则
使用推理规则建立论证
当有多个前提时，常常需要用到多个推理规则来证明一个论证是有效的,比如下面的例子
针对假设\(p\to q,\neg p\to r\),以及 \(r\to s\)和结论\(\neg q\to s\),给出一个有效论证。 解:
消解律
消解率基于以下的永真式
其中命题\(q\vee r\)被称为消解式.
谬误
常见的谬误一般是基于可能式而非永真式,例如 $$ ((p\to q)\wedge q)\to p $$ 前提为真,但结论不一定正确,这类不正确的推理称为肯定结论的谬误
量化命题的推理规则
全称假言推理
全称取拒式
1.7 证明导论
术语
定理: 是一个能够被证明是真的语句.
定理一词通通常是用来专指那些被认为至少有些重要的语句。
不太重要的定理有时称为命题(定理也可以称为事实或结论.
直接证明法
条件语句\(p\to q\)的直接证明法的构造：首先假设\(p\)为真,然后用推理规则构造，最后表明\(q\)必须也为真.
定义 1\(\qquad\)如果存在一个整数\(k\),使得\(n=2k\),那么\(n\)为偶数;如果存在一个整数\(k\)使得\(n=2k+1\),那么\(n\)为奇数
定理 1\(\qquad\)如果\(n\)是偶数,则\(n^2\)也是偶数.
证明:
假设\(n\)是偶数,则存在一个整数\(k\)使得\(n=2k\).
那么
因此\(n^2\)也是偶数.