命题 命题是一个陈述句（即陈述事实的句子），它要么为真，要么为假，但不能同时为真和假。
例1 以下所有陈述句都是命题。
华盛顿是美国的首都多伦多是加拿大的首都1 + 1 = 22 + 2 = 3解 其中命题 1 和 3 为真，而命题 2 和 4 为假。
例2 判断以下句子是否为命题。
What time is it?Read this carefully.x + 1 = 2.x + y = z.解 句子 1 和 2 不是命题，因为它们不是陈述句。句子 3 和 4 不是命题，因为它们既不是真也不是假。
草莓视频在线观看APP用字母来表示命题变量（或句子变量），即代表命题的变量，就像用字母来表示数值变量一样。
现在，草莓视频在线观看APP把注意力转向从已有命题中生成新命题的方法。许多数学陈述都是通过组合一个或多个命题构建的。新命题称为复合命题，是使用逻辑运算符从现有命题中形成的。
否定 ¬ eg ¬定义 1 令 p p p 为一个命题。 p p p 的否定，记作 ¬ p eg p ¬p（也可以记作 p ‾ overline{p} p），其陈述为： “不是 p p p 的情况。” 命题 ¬ p eg p ¬p 读作“非 p p p。” ¬ p eg p ¬p 的真值是与 p p p 的真值相反的。
例3 找到命题的否定形式，并用简单的英语表达。
“Michael’s PC runs Linux”
解
“It is not the case that Michael’s PC runs Linux.”
或更简单的表达为：
“Michael’s PC does not run Linux.”
例4 找到命题的否定形式，并用简单的英语表达。
“Vandana’s smartphones has at least 32 GB of memory”
解
“It is not the case that Vandana’s smartphones has at least 32 GB of memory.”
或
“Vandana’s smartphones does not have at least 32 GB of memory”
或者更简单地表达为：
“Vandana’s smartphones has less than 32 GB of memory.”
合取 ∧ land ∧定义 2 设 p p p 和 q q q 为命题。 p p p 和 q q q 的合取，记作 p ∧ q p land q p∧q，是命题 “ p p p 和 q q q”。当且仅当 p p p 和 q q q 都为真时，合取 p ∧ q p land q p∧q 为真；否则为假。
例5 找到命题 p p p 和 q q q 的合取，其中 p p p 是命题 “Rebecca’s PC has more than 16 GB free hard disk space”， q q q 是命题 “The processor in Rebecca’s PC runs faster than 1 GHz”。
解 这些命题的合取， p ∧ q p land q p∧q，是命题 “Rebecca’s PC has more than 16 GB free hard disk space, and the processor in Rebecca’s PC runs faster than 1 GHz”。这个合取可以更简单地表达为 “Rebecca’s PC has more than 16 GB free hard disk space, and its processor runs faster than 1 GHz”。为了使这个合取为真，这两个条件都必须为真。当其中一个或两个条件为假时，该合取为假。
析取 ∨ lor ∨定义 3 设 p p p 和 q q q 为命题。 p p p 和 q q q 的析取，记作 p 或 q p 或 q p或q，是命题 “ p p p or q q q”。当且仅当 p p p 和 q q q 都为假时，析取 p ∨ q p lor q p∨q 为假；否则为真。
例6
将陈述 “Students who have taken calculus or introductory computer science can take this class” 转换为命题逻辑中的表达式，使用命题 p p p: “A student who has taken calculus can take this class” 和 q q q: “A student who has taken introductory computer science can take this class”。
解 这个陈述可以表达为 p ∨ q p lor q p∨q，即包含性或（析取）。
例7 命题 p p p 和 q q q 的析取是什么？其中 p p p 和 q q q 与例子 5 中的命题相同？
解答： 命题 p p p 和 q q q 的析取， p ∨ q p lor q p∨q，是命题：
“Rebecca’s PC has at least 16 GB free hard disk space, or the processor in Rebecca’s PC runs faster than 1 GHz.”
异或 ⊕ oplus ⊕定义 4 设 p p p 和 q q q 为命题。 p p p 和 q q q 的异或（exclusive or），记作 p ⊕ q p oplus q p⊕q（或者 p p p XOR q q q），是当且仅当 p p p 和 q q q 中有一个为真时命题为真，其他情况下为假。
例8 设 p p p 和 q q q 为命题，分别表示 “A student can have a salad with dinner” 和 “A student can have soup with dinner”。 p ⊕ q p oplus q p⊕q（ p p p 和 q q q 的异或）是什么？
解答： p p p 和 q q q 的异或是当且仅当 p p p 和 q q q 中有一个为真时的命题。也就是说， p ⊕ q p oplus q p⊕q 是命题 “A student can have soup or salad, but not both, with dinner”。注意，这通常被表述为 “A student can have soup or a salad with dinner”，没有明确说明不能同时选择两者。
例9 用命题逻辑表达陈述 “I will use all my savings to travel to Europe or to buy an electric car”，其中 p p p 表示 “I will use all my savings to travel to Europe”， q q q 表示 “I will use all my savings to buy an electric car”。
解答： 要翻译这个陈述，草莓视频在线观看APP首先注意到这里的 “or” 必须是异或，因为该学生可以用他的所有储蓄去欧洲旅行，也可以用这些储蓄买电动汽车，但不能既去欧洲旅行又买电动汽车。（这很明显，因为每种选择都需要他所有的储蓄。）因此，这个陈述可以表示为 p ⊕ q p oplus q p⊕q。
条件语句定义 5 设 p p p 和 q q q 为命题。条件语句 p → q p ightarrow q p→q 是命题 “if p p p, then q q q”。当 p p p 为真而 q q q 为假时，条件语句 p → q p ightarrow q p→q 为假，其他情况下为真。在条件语句 p → q p ightarrow q p→q 中， p p p 被称为假设（hypothesis，或 antecedent 或 premise），而 q q q 被称为结论（conclusion，或 consequence）。
该语句 p → q p ightarrow q p→q 被称为条件语句，因为 p → q p ightarrow q p→q 断言在 p p p 成立的条件下， q q q 为真。条件语句也被称为蕴涵（implication）。
由于条件语句在数学推理中扮演着如此重要的角色，使用了多种术语来表示 p → q p ightarrow q p→q。你将会遇到以下几种表达这种条件语句的方式：
“if p p p, then q q q”“if p p p, q q q”“ p p p is sufficient for q q q”“ q q q if p p p”“ q q q when p p p”“a necessary condition for p p p is q q q”“ q q q unless ¬ p eg p ¬p”“ p p p implies q q q”“ p p p only if q q q”“a sufficient condition for q q q is p p p”“ q q q whenever p p p”“ q q q is necessary for p p p”“ q q q follows from p p p”“ q q q provided that p p p”理解条件语句真值的一个有用方法是将其视为一种义务或契约。例如，许多政客在竞选时做出的承诺是：
“If I am elected, then I will lower taxes.”
如果这位政客当选，选民将期望他/她降低税收。此外，如果这位政客没有当选，那么选民将不会期望他/她降低税收，尽管这个人可能有足够的影响力促使当权者降低税收。只有当政客当选却没有降低税收时，选民才能说这位政客违背了竞选承诺。这个最后的情景对应于 p → q p ightarrow q p→q 中 p p p 为真而 q q q 为假的情况。
同样，考虑一个教授可能会做出的陈述：
“If you get 100% on the final, then you will get an A.”
如果你在期末考试中得到 100%，那么你会期望获得 A。如果你没有得到 100%，你可能会根据其他因素而可能得不到 A。然而，如果你得到了 100% 但教授却没有给你 A，你会感到被骗了。
备注： 由于表达 p → q p ightarrow q p→q 的不同方式可能会令人困惑，草莓视频在线观看APP提供一些额外的指导。记住 “ p p p only if q q q” 表达的意思与 “if p p p, then q q q” 是相同的，注意 “ p p p only if q q q” 表示如果 q q q 不为真， p p p 也不能为真。也就是说，当 p p p 为真，而 q q q 为假时，该陈述是假的。当 p p p 为假时， q q q 可能为真或假，因为该陈述没有涉及 q q q 的真值。
例如，假设你的教授告诉你：
“You can receive an A in the course only if your score on the final is at least 90%.”
那么，如果你在课程中得到了 A，表明你在期末考试中的得分至少为 90%。如果你没有得到 A，你可能得分不足 90%，也可能得分超过了 90%。注意不要使用 “ q q q only if p p p” 来表达 p → q p ightarrow q p→q，因为这不正确。“only” 这个词在这里起到了重要的作用。为了理解这一点，注意 “ q q q only if p p p” 和 p → q p ightarrow q p→q 的真值在 p p p 和 q q q 具有不同的真值时是不同的。要明白为什么 “ q q q is necessary for p p p” 等价于 “if p p p, then q q q”，观察 “ q q q is necessary for p p p” 意味着 p p p 不能为真，除非 q q q 为真，或者说如果 q q q 为假，那么 p p p 也为假。这与 “如果 p p p 为真，那么 q q q 为真” 的表述是相同的。为了理解 “ p p p is sufficient for q q q” 等价于 “if p p p, then q q q”，注意 “ p p p is sufficient for q q q” 意味着如果 p p p 为真，则 q q q 也必须为真。这与 “如果 p p p 为真，那么 q q q 也为真” 的表述是相同的。
要记住 “ q q q unless ¬ p eg p ¬p” 表达的与 “if p p p, then q q q” 是相同的条件语句，注意 “ q q q unless ¬ p eg p ¬p” 的意思是如果 ¬ p eg p ¬p 为假，那么 q q q 必须为真。也就是说，当 p p p 为真而 q q q 为假时，该语句为假，但在其他情况下为真。因此， q q q unless ¬ p eg p ¬p 和 p → q p ightarrow q p→q 总是具有相同的真值。
例10 设 p p p 表示陈述 “Maria learns discrete mathematics” 而 q q q 表示陈述 “Maria will find a good job”。将语句 p → q p ightarrow q p→q 以英文表达。
解 根据条件语句的定义，当 p p p 是陈述 “Maria learns discrete mathematics”，而 q q q 是陈述 “Maria will find a good job” 时， p → q p ightarrow q p→q 表示以下语句：
“If Maria learns discrete mathematics, then she will find a good job.”
还有很多其他方式可以表达这个条件语句，最自然的几种方式是：
“Maria will find a good job when she learns discrete mathematics.”
“For Maria to get a good job, it is sufficient for her to learn discrete mathematics.”
以及
“Maria will find a good job unless she does not learn discrete mathematics.”
例子 11
在以下语句之后，变量 x x x 的值是多少：
if 2 + 2 = 4 then x := x + 1
如果在遇到该语句之前 x = 0 x = 0 x=0？（符号 : = := := 表示赋值。语句 x : = x + 1 x := x + 1 x:=x+1 表示将 x + 1 x + 1 x+1 的值赋给 x x x。）
解 因为 2 + 2 = 4 2 + 2 = 4 2+2=4 为真，赋值语句 x : = x + 1 x := x + 1 x:=x+1 被执行。因此，在遇到该语句后， x x x 的值为 0 + 1 = 1 0 + 1 = 1 0+1=1。
逆命题、逆否命题和反命题 草莓视频在线观看APP可以从条件语句 p → q p ightarrow q p→q 开始，形成一些新的条件语句。特别是，有三个相关的条件语句非常常见，以至于它们有了特殊的名称。命题 q → p q ightarrow p q→p 称为 p → q p ightarrow q p→q 的逆命题（converse）。 p → q p ightarrow q p→q 的逆否命题（contrapositive）是命题 ¬ q → ¬ p eg q ightarrow eg p ¬q→¬p。命题 ¬ p → ¬ q eg p ightarrow eg q ¬p→¬q 称为 p → q p ightarrow q p→q 的反命题（inverse）。草莓视频在线观看APP将看到，在从 p → q p ightarrow q p→q 形成的这三个条件语句中，只有逆否命题总是具有与 p → q p ightarrow q p→q 相同的真值。
例12 找到以下条件语句的逆否命题、逆命题和反命题：
“The home team wins whenever it is raining.”
解 因为 “ q q q whenever p p p” 是表达条件语句 p → q p ightarrow q p→q 的方式之一，原语句可以改写为：
“If it is raining, then the home team wins.”
因此，这个条件语句的逆否命题是：
“If the home team does not win, then it is not raining.”
逆命题是：
“If the home team wins, then it is raining.”
反命题是：
“If it is not raining, then the home team does not win.”
只有逆否命题与原始语句等价。
双条件语句 ↔ leftrightarrow ↔定义 6 设 p p p 和 q q q 为命题。双条件语句（biconditional statement） p ↔ q p leftrightarrow q p↔q 是命题 “ p p p if and only if q q q”。当 p p p 和 q q q 的真值相同时，双条件语句 p ↔ q p leftrightarrow q p↔q 为真，否则为假。双条件语句也称为双蕴涵（bi-implications）。
注意，当条件语句 p → q p ightarrow q p→q 和 q → p q ightarrow p q→p 都为真时，语句 p ↔ q p leftrightarrow q p↔q 为真，其他情况下为假。因此，草莓视频在线观看APP使用 “if and only if” 来表示这种逻辑连接，并且它的符号表示为将符号 → ightarrow → 和 ← leftarrow ← 结合起来。有一些其他常见的方式来表达 p ↔ q p leftrightarrow q p↔q：
“ p p p is necessary and sufficient for q q q”“if p p p then q q q, and conversely”“ p p p iff q q q” 或 “ p p p exactly when q q q”最后一种表达 p ↔ q p leftrightarrow q p↔q 的方式使用了 “iff” 的缩写，表示 “if and only if”。注意， p ↔ q p leftrightarrow q p↔q 的真值与 ( p → q ) ∧ ( q → p ) (p ightarrow q) land (q ightarrow p) (p→q)∧(q→p) 的真值完全相同。
例13 设 p p p 为陈述 “You can take the flight”，设 q q q 为陈述 “You buy a ticket”。那么 p ↔ q p leftrightarrow q p↔q 表示：
“You can take the flight if and only if you buy a ticket.”
隐式使用双条件语句 你应该注意到，双条件语句在自然语言中并不总是明确表达出来的。尤其是，“if and only if” 结构在双条件语句中在日常语言中很少使用。相反，双条件语句通常通过 “if, then” 或 “only if” 结构来表达。“if and only if” 的另一部分是隐含的。比如，考虑以下英文陈述：
“If you finish your meal, then you can have dessert.”
真正的意思是 “You can have dessert if and only if you finish your meal。” 最后这个语句在逻辑上等价于两个陈述：“If you finish your meal, then you can have dessert” 和 “You can have dessert only if you finish your meal。” 因为自然语言中的这种不精确性，草莓视频在线观看APP需要假设自然语言中的条件语句是否隐含包含了它的逆命题。由于数学和逻辑中对精确性的要求，草莓视频在线观看APP将始终区分条件语句 p → q p ightarrow q p→q 和双条件语句 p ↔ q p leftrightarrow q p↔q。
复合命题的真值表草莓视频在线观看APP现在已经介绍了五个重要的逻辑联结词——合取（conjunction）、析取（disjunction）、异或（exclusive or）、蕴涵（implication）和双条件运算符（biconditional），以及否定（negation）。草莓视频在线观看APP可以使用这些联结词来构建涉及任意数量命题变量的复杂复合命题。草莓视频在线观看APP可以使用真值表来确定这些复合命题的真值，正如例子 14 所示。草莓视频在线观看APP使用单独的列来查找复合命题的每个表达式的真值，并根据构建过程中每一步的结果。复合命题在真值表中最后一列给出的真值是基于命题变量组合的真值。
例14 构造复合命题的真值表： ( p ∨ ¬ q ) → ( p ∧ q ) (p lor eg q) ightarrow (p land q) (p∨¬q)→(p∧q)
解 由于该真值表涉及两个命题变量 p p p 和 q q q，因此该真值表有四行，分别对应真值组合 TT、TF、FT 和 FF。前两列用于 p p p 和 q q q 的真值。在第三列中，草莓视频在线观看APP找到 ¬ q eg q ¬q 的真值，第四列中找到 p ∨ ¬ q p lor eg q p∨¬q 的真值。第五列给出 p ∧ q p land q p∧q 的真值。最后，第六列展示了 ( p ∨ ¬ q ) → ( p ∧ q ) (p lor eg q) ightarrow (p land q) (p∨¬q)→(p∧q) 的真值。最终的真值表如表 7 所示。
逻辑运算符的优先级草莓视频在线观看APP可以使用前面定义的否定运算符和逻辑运算符构造复合命题。草莓视频在线观看APP通常使用括号来指定逻辑运算符在复合命题中的应用顺序。例如， ( p ∨ q ) ∧ ( ¬ r ) (p lor q) land ( eg r) (p∨q)∧(¬r) 是 p ∨ q p lor q p∨q 和 ¬ r eg r ¬r 的合取。然而，为了减少括号的数量，草莓视频在线观看APP规定否定运算符在其他逻辑运算符之前应用。这意味着 ¬ p ∧ q eg p land q ¬p∧q 是 ¬ p eg p ¬p 和 q q q 的合取，即 ( ¬ p ) ∧ q ( eg p) land q (¬p)∧q，而不是 p ∧ q p land q p∧q 的否定，即 ¬ ( p ∧ q ) eg (p land q) ¬(p∧q)。（一般来说，涉及单个对象的一元运算符优先于二元运算符。）
另一个普遍的优先级规则是合取运算符优先于析取运算符。因此， p ∨ q ∧ r p lor q land r p∨q∧r 表示 p ∨ ( q ∧ r ) p lor (q land r) p∨(q∧r) 而不是 ( p ∨ q ) ∧ r (p lor q) land r (p∨q)∧r，同样地， p ∧ q ∨ r p land q lor r p∧q∨r 表示 ( p ∧ q ) ∨ r (p land q) lor r (p∧q)∨r 而不是 p ∧ ( q ∨ r ) p land (q lor r) p∧(q∨r)。因为这个规则可能难以记住，草莓视频在线观看APP将继续使用括号来确保析取和合取运算符的顺序清晰。
最后，一个公认的规则是条件和双条件运算符 → ightarrow → 和 ↔ leftrightarrow ↔ 的优先级低于合取和析取运算符 ∧ land ∧ 和 ∨ lor ∨。因此， p → q ∨ r p ightarrow q lor r p→q∨r 表示 p → ( q ∨ r ) p ightarrow (q lor r) p→(q∨r) 而不是 ( p → q ) ∨ r (p ightarrow q) lor r (p→q)∨r，而 p ∨ q → r p lor q ightarrow r p∨q→r 表示 ( p ∨ q ) → r (p lor q) ightarrow r (p∨q)→r 而不是 p ∨ ( q → r ) p lor (q ightarrow r) p∨(q→r)。当涉及条件运算符和双条件运算符的顺序时，草莓视频在线观看APP将使用括号，尽管条件运算符优先于双条件运算符。表 8 显示了逻辑运算符 ¬ eg ¬、 ∧ land ∧、 ∨ lor ∨、 → ightarrow → 和 ↔ leftrightarrow ↔ 的优先级等级。
逻辑与位运算计算机使用位（bit）来表示信息。位是具有两个可能值的符号，即 0 和 1。单词 “bit” 的含义来源于二进制数字（binary digit），因为零和一是用于表示数字的二进制数位。著名统计学家 John Tukey 在 1946 年引入了这个术语。位可以用来表示真值，因为真值有两个，即真（true）和假（false）。按照惯例，草莓视频在线观看APP将使用 1 位来表示真，用 0 位来表示假。即，1 表示 T（真），0 表示 F（假）。如果变量的值是真或假，那么这个变量被称为布尔变量（Boolean variable）。因此，布尔变量可以用一个位来表示。
计算机中的位运算（bit operations）对应于逻辑联结词。通过用真替换为 1、假替换为 0，联结词 ∧ land ∧、 ∨ lor ∨ 和 ⊕ oplus ⊕ 的真值表中的列可以得到相应的位运算结果。草莓视频在线观看APP还将使用 OR、AND 和 XOR 的符号，正如在各种编程语言中所做的一样。
定义 7 位串（bit string）是由零个或多个位组成的序列。这个串的长度是该串中位的数量。
例15 101010011 是长度为9的位串。
草莓视频在线观看APP可以将位运算扩展到位串上。草莓视频在线观看APP定义两个相同长度的位串的按位或（bitwise OR）、按位与（bitwise AND）和按位异或（bitwise XOR）为它们对应位置上的位的或、与和异或的结果。草莓视频在线观看APP使用符号 ∨ lor ∨、 ∧ land ∧ 和 ⊕ oplus ⊕ 来分别表示按位或、按位与和按位异或运算。草莓视频在线观看APP用例子 16 来展示按位运算在位串上的应用。
例16 求位串 01 1011 0110 和 11 0001 1101 的按位或、按位与和按位异或。
解答： 这两个位串的按位或、按位与和按位异或是通过分别计算对应位的 OR、AND 和 XOR 得到的。结果如下：
01 1011 0110 11 0001 1101
11 1011 1111 按位或 (bitwise OR) 01 0001 0100 按位与 (bitwise AND) 10 1010 1011 按位异或 (bitwise XOR)
