逻辑规则给出数学语句的准确含义，这些规则用来区分有效和无效的数学论证。
命题是一个陈述句（即陈述事实的语句），它或真或假，但不能既真又假。
我们用字母来表示命题变元，它是代表命题的变量。习惯上用字母p,q,r,s,...表示命题。如果一个命题是真命题，它的真值为真，用T表示；如果它是假命题，其真值为假，用F表示。
涉及命题的逻辑领域称为命题演算或命题逻辑。
许多数学陈述都是由一个或多个命题组合而来。称为复合命题的新命题是由已知命题用逻辑运算符组合而来。
定义1：令p为一命题，则p的否定记作$\lnot$p。命题$\lnot$p读作『非p』。p的否定（$\lnot$p）的真值和p的真值相反。
表1 命题之否定的真值表
| p | $\lnot$p |
|---|---|
| T | F |
| F | T |
命题的否定也可以看作否定运算符作用在命题上的结构。否定运算符从一个已知命题构造出一个新命题。这些逻辑运算符也称作联接词。
定义2：令p和q为命题。p、q的合取即命题『p并且q』，记作$p \land q$。当p和q都是真时，$p \land q$命题为真，否则为假。
表2 俩命题合取的真值表
| p | q | $p \land q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
定义3：令p和q为命题。p和q的析取即命题『p或q』，记作$p \lor q$。当p和q均为假时，合取命题$p \lor q$为假，否则为真。
表3 俩命题析取的真值表
| p | q | $p \lor q$ |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
定义4：令p和q为命题。p和q的异或（记作$p \oplus q$）是这样一个命题：当p和q中恰好只有一个为真时命题为真，否则为假。
表4 俩命题异或的真值表
| p | q | $p \oplus q$ |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
定义5：令p和q为命题。条件语句p->q是命题『如果p，则q』。当p为真而q为假时，条件语句p->q为假，否则为真。在条件语句p->q中，p称为假设（前件、前提），q称为结论（后件）。
表5 条件命题p->q的真值表
| p | q | p->q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
逆命题、逆否命题与反命题 由条件语句p->q可以构成一些新的条件语句。命题q->p称为 p->q 的逆命题，而p->q的逆否命题是命题$\lnot q \to \lnot p$ 。命题$\lnot p \to \lnot q$称为$p \to q$的反命题。
当两个复合命题总是具有相同真值时，我们称它们是等价的。因此一个条件语句与它的逆否命题是等价的。条件语句的逆与反也是等价的。
定义6（双条件语句）：令p和q为命题。双条件语句p<->q是命题『p当且仅当q』。当p和q有同样的真值时，双条件语句为真，否则为假。双条件语句也称为双向蕴含。
表6 双条件语句p<->q的真值表
| p | q | p<->q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
可以用缩写符号『iff』代替『当且仅当』（if and only if）。注意，p<->q与$(p \to q) \land (q \to p)$ 有完全相同的真值。
通过上述四个逻辑联接词——合取、析取、条件、双条件可以构造含有一些命题变元的结构复杂的复合命题。如 ：构造复合命题$(p \lor \lnot q \to (p \land q))$
表8 逻辑运算符的优先级
| 运算符 | 优先级 |
|---|---|
| $\lnot$ | 1 |
| $\land$ | 2 |
| $\lor$ | 3 |
| $\to$ | 4 |
| $\leftrightarrow$ | 5 |
习惯上，我们用1表示真，用0表示假。即，1表示T（真），0表示F（假）。如果一个变量的值或为真或为假，则此变量就称为布尔变量。一个布尔变量可以用一位表示。
我们还会用符号OR、AND和XOR表示运算符$\lor$,$\land$,$\oplus$。
信息一般用位串（即由0和1构成的序列）表示。这时，对位串的运算即可用来处理信息。
定义7：位串是0位或多位的序列。位串的长度就是它所含位的数目。
定义1：一个真值永远是真的复合命题（无论其中出现的命题变元的真值是什么），称为永真式（tautology），也称为重言式。一个真值永远为假的复合命题称为矛盾式（contradiction）。既不是永真式又不是矛盾式的复合命题称为可能式（contingency）。
表1 永真式和矛盾式的例子
| p | $\lnot p$ | $p \lor \lnot p$ | $p \land \lnot p$ |
|---|---|---|---|
| T | F | T | F |
| F | T | T | F |
在所有可能得情况下都有相同真值的两个复合命题称为逻辑等价的。
定义2：如果p<->q是永真式，则复合命题p和q称为是逻辑等价的。用记号$p \equiv q$表示。
注：符号$\equiv$不是逻辑联结词，$p \equiv q$不是一个复合命题，而是代表『p<->q是永真式』这一语句。
判定两个复合命题是否等价的方法之一是使用真值表。
表2 德摩根律（逻辑等价例子）
表6中的逻辑等价式以及已建立起来的其他（如表7和表8所示的那些）等价式，可以用于构造其他等价式。能这样做的原因是复合命题中的一个命题可以用与它逻辑等价的复合命题替换而不改变原复合命题的真值。
一个复合命题称为是可满足的，如果存在一个对其变元的真值赋值使其为真。当不存在这样的赋值时，即当复合命题对所有变元的真值赋值都是假的，则复合命题是不可满足的。
当我们找到一个特定的使得复合命题为真的真值赋值时，就证明了它是可满足的。这样的一个赋值称为这个特定的可满足性问题的一个解。可是，要证明一个复合命题是不可满足的，我们需要证明每一组变元的真值赋值都使其为假。尽管我们总是可以用真值表来确定一个复合命题是否是可满足的，但通常有更有效的方法，如例9所示。
『x大于3』：第一部分即变量x是语句的主语。第二部分（谓词『大于3』）表明语句的主语具有一个性质。我们可以用P(x)表示语句『x大于3』，其中P表示谓词『大于3』，而x是变量。语句P(x)也可以说成是命题函数P在x的值。一旦给变量x赋一个值，语句P(x)就成为命题并具有真值。
一般地，涉及n个变量$x_1,x_2,...,x_n$的语句可以表示成$P(x_1,x_2,...,x_n)$形式为$P(x_1,x_2,...,x_n)$的语句是命题函数P在n元祖$(x_1,x_2,...,x_n)$的值，P也称为n位谓词或n元谓词。
前置条件和后置条件：描述合法输入的语句叫做前置条件，而程序运行的输出应该满足的条件称为后置条件。
量化表示在何种程度上谓词对于一定范围的个体成立。这里讨论两类量化：全称量化，它告诉我们一个谓词在所考虑范围内对每一个体都为真；存在量化，它告诉我们一个谓词对所考虑范围内的一个或多个个体为真。处理谓词和量词的逻辑领域称为谓词演算。
定义1：P(x)的全称量化是语句『P(x)对x在其论域的所有值为真。』符号$\forall xP(x)$表示P(x)的全称量化，其中$\forall$称为全称量词。命题$\forall xP(x)$读作『对所有x，P(x)』或『对每个x，P(x)』。一个使P(x)为假的个体称为$\forall xP(x)$的反例。
定义2：P(x)的存在量化是命题『论域中存在一个个体x满足P(x)。』我们用符号$\exists xP(x)$表示P(x)的存在量化，其中$\exists$称为存在量词。
在要限定一个量词的论域时经常采用简写的表示法。在这个表示法里，变量必须满足的条件直接放在量词的后面。
注意，
量词$\forall$和$\exists$比命题演算中的所有逻辑运算符都具有更高的优先级。
当量词作用于变量x时，我们说此变量的这次出现为约束的。一个变量的出现被称为是自由的，如果没有被量词约束或设置为等于某一特定值。命题函数中的所有变量出现必须是约束的或者被设置为等于某个值得，才能把它转变为一个命题。这可以通过采用一组全称量词、存在量词和赋值来实现。
逻辑表达式中一个量词作用到的部分称为这个量词的作用域。
定义3：涉及谓词和量词的语句是逻辑等价的当且仅当无论用什么谓词代入这些语句，也无论为这些命题函数里的变量指定什么论域，它们都有相同的真值。我们用$S \equiv T$表示涉及谓词和量词的两个语句S和T是逻辑等价的。
$\lnot \forall x P(x) \equiv \exists x \lnot P(x)$
$\lnot \exists x Q(x) \equiv \forall x \lnot Q(x)$
量词否定的规则称为量词的德摩根律。
例24 用谓词和量词表达语句“这个班上的某个学生去过墨西哥”和“这个班上的每个学生或去过加拿大，或去过墨西哥。”
解 引入变量x，“这个班上的某个学生去过墨西哥” 即 “在这个班上有个学生x，x去过墨西哥。”引入谓词M(x)表示“x去过墨西哥”，
令C（先）表示“x去过加拿大”，类似地，第二句可以表示成：
还可以使用两个变量谓词V(x,y)表示“x去过y国家”。这样，V(x,墨西哥)和V(x,加拿大)具有与M(x)和C(x)相同的意思。如果我们要处理的语句涉及人们去过不同的国家，我们可以倾向于使用这种双变量的方法。否则为了简单起见，我们可以用一个变量的谓词C(x)和M(x)。
例25 用谓词和量词表达系统规范说明“每封大于1MB的邮件会被压缩”和“如果一个用户处于活动状态，那么至少有一条网络链路是有效的”。
解 令S(m,y)表示“邮件m大于yMB”，其中变量m的论域是所有邮件，变量y是一个正实数；令C(m)表示“邮件m会被压缩”。那么规范说明“每封大于1MB的邮件会被压缩”可以表达为$\forall m(S(m,1) \to C(m))$。
令A(u)表示“用户u处于活动状态”，其中变量u的论域是所有用户；令S(n,x)表示“网络链路n处于x状态”，其中n的论域是所有网络链路，x的论域是网络链路所有可能得状态。那么规范说明“如果用户处于活动状态，那么至少有一个网络链路有效”可以表达为$\exists u A(u) \to \exists n S(n,有效)$
有一类重要的程序设计语言使用谓词逻辑的规则进行推理。Prolog(Programming in Logic)就是其一。Prolog程序包括一组声明，其中包括两类语句：Prolog事实和Prolog规则。Prolog事实通过指定那些满足谓词的元素来定义谓词。Prolog规则使用Prolog事实定义好的那些谓词来定义新的谓词。
例28 考虑一个Prolog程序，它给出的事实是每门课程的教室和学生注册的课程。程序使用这些事实来回答有关给特定学生上课的教授的查询。这样的程序可使用谓词instructor(p,c)和enrolled(s,c)分别表示教授p是讲授课程c的老师及学生s注册课程c。例如，此程序中的Prolog事实可能包含：
instructor(chan,math273)
instructor(patel,ee222)
instructor(grossman,cs301)
enrolled(kevin,math273)
enrolled(juana,ee222)
enrolled(juana,cs301)
enrolled(kiko,math273)
enrolled(kiko,cs301)一个新的谓词teaches(p,s)表示教授p教学生s没可以用Prolog规则来定义：
eaches(P,S): - instructor(P,C),enrolled(S,C)查询：
? enrolled(kevin,math273)
yes
? enrolled(X,math273)
kevin
kiko
? teaches(X, juana)
patel
grossman嵌套量词：一个量词出现在另一个量词的作用域内，如$\forall x \exists y(x+y=0)$
量词范围内的一切都可以认为是一个命题，上面表达式与$\forall x Q(x)$是一样的，其中Q(x)表示$\exists y P(x,y)$，而P(x,y)表示x+y=0。
将量化当做循环：
嵌套量词语句的否定可以通过连续地应用单个量词语句的否定规则得到。
定义1：命题逻辑中的一个论证是一连串的命题。除了论证中最后一个命题外都叫做前提(premise)，最后那个命题叫做结论(conclusion)。一个论证(argument)是有效的(valid)，如果它的所有前提为真蕴涵着结论为真。
命题逻辑中的论证形式是一连串涉及命题变元的复合命题。无论用什么特定命题来替换其中的命题变元，如果前提均真时结论为真，则称该论证形式是有效的。
永真式$(p \land (p \to q)) \to q$是称为假言逻辑(modus ponens)或分离逻辑(law of detachment)的推理规则的基础。
已经开发出的计算机程序能够将定理的推理和证明任务自动化。许多这类程序利用称为消解律（resolution）的推理规则。这个推理规则基于永真式：$((p \lor q) \land (\lnot p \lor r)) \to (q \lor r)$
消解规则最后的析取式称为消解式(resolvent)。当在此永真式中令q=r时，可得$(p \lor q) \land (\lnot p \lor q) \to q$。而且，当令r=F时，可得$(p \lor q) \land (\lnot p) \to q$（因为 $q \lor F \equiv q$），这是永真式，析取三段论规则就基于此式。
消解律在基于逻辑规则的编程语言中扮演着重要的角色，如在Prolog中。而且，可以用消解律来构建自动定理正面系统。要使用消解律作为仅有的推理规则来够早命题逻辑中的证明，假设和结论必须表示为子句(clause)，这里子句是指变量或其否定的一个析取式。
肯定结论的谬误(fallacy of affirming the conclusion):$((p \to q) \land q) \to p$,因为当p为假而q为真时，它为假。
否定假设的谬误(fallacy of denying the hypothesis):$((p \to q) \land \lnot q) \to \lnot p$,因为当p为假而q为真时，它为假。
全称实例(universal instantiation):是从给定前提$\forall x P(x)$得出P(c)为真的推理规则，其中c是论域里的一个特定的成员。全称引入(universal generalization):是从对论域里所有元素c都有P(c)为真的前提条件推出$\forall x P(x)$为真的推理规则。存在实例(existential instantiation):是允许从“如果我们知道$\exists x P(x)$为真，得出在论域中存在一个元素c使得P(c)为真”的推理规则。存在引入(existential generalization):是用来从“已知有一特定的c使P(c)为真时得出$\exists x P(x)$为真”的推理规则。全称假言推理(universal modus ponens):
全称取拒式(universal modus tollens):
一个定理（theorem）是一个能够被证明是真的语句。不太重要的定理有时称为命题（定理也可以称为事实(fact)或结论(result)）。我们用一个证明(proof)来展示一个定理是真的。证明就是建立定理真实性的一个有效论证。证明中用到的语句可以包括公理(axiom)（或假设(postulate）），这些是我们假定为真的语句、定理的前提（如果有的话）和以前已经被证明的定理。
一个不太重要但有助于证明其他结论的定理称为引理(lemma)。推论(corollary)是从一个已经被证明的定理可以直接建立起来的一个定理。猜想(conjecture)是一个被提出认为是真的命题，通常是基于部分证据、启发式论证或者专家的直觉。当猜想的一个证明被发现时，猜想就变成了定理。许多时候猜想被证明是假的，因此它们不是定理。
证明的第一步通常涉及选择论域里的一个一般性元素。随后的步骤是证明这个元素具有所考虑的性质。最后，全称引入蕴含着定理对论域里所有元素都成立。
条件语句$p \to q$的直接证明法的构造：第一步假设p为真；第二步用推理规则构造，而第三步表明q必须也为真。直接证明法是通过证明如果p为真，那么q也肯定为真，这样p为真且q为假的情况永远不会发生从而证明条件语句$p \to q$为真。
证明形如$\forall x(P(x) \to Q(x))$的定理，不从前提开始以结论结束来证明这类定理的方法叫做间接证明法。一类非常有用的间接证明法称为反证法(proof by contraposition)。反证法利用了这样一个事实：条件语句$p \to q$等价于它的逆否命题$\lnot q \to \lnot p$。
假设我们要证明命题p是真的。再假定我们能找到一个矛盾式q使得$\lnot p \to q$为真。因为q是假的，而$\lnot p \to q$是真的，所以我们能够得出结论$\lnot p$为假，这意味着p为真。怎样才能找到一个矛盾式q以这样的方式帮助我们证明p是真的呢？
因为无论r是什么，命题$r \lor \lnot r$就是矛盾式，所以如果我们能够证明对某个命题r，$\lnot p \to (r \land \lnot r)$为真，就能证明p是真的。这种类型的证明称为归谬证明法(proof by contradiction)。归谬证明法是另一种间接证明法。
分情形证明法：$(p_1 \lor p_2 \lor \cdots \lor p_n) \to q$ 可以用永真式：$((p_1 \to q) \land (p_2 \to q) \land \cdots \land (p_n \to q))$作为推理规则。
穷举证明法：穷尽所有的可能性。
$\exists x P(x)$这类命题的证明称为存在性证明（existence proof）。
构造性的(constructive)：找到一个元素a，使得P(a)为真。
非构造性的(nonconstructive)：一种常用方法是归谬证明，证明该存在量化式的否定式蕴含一个矛盾。
唯一性证明(uniqueness proof)两个部分组成：
In [ ]: