1.1. 命题逻辑

逻辑规则给出数学语句的准确含义。这些规则可以用来区分数学论证的有效或无效。逻辑不仅对理解数学推理十分重要，而且在计算机科学中有许多应用。这些逻辑规则用于计算机电路设计、计算机程序构造、程序正确性验证以及许多其他方面。

命题

DEFINITION 1命题

命题是一个陈述语句（即陈述事实的语句），它或真或假，但不能既真又假。

我们用字母来表示命题变元，它是代表命题的变量。习惯上用字母$p,\enspace q,\enspace r,\enspace s,\enspace \dots$表示命题。如果一个命题是真命题，它的真值为真，用$T$表示；如果它是假命题，其真值为假，用$F$表示。

涉及命题的逻辑领域称为命题演算或命题逻辑。许多数学陈述都是有一个或多个命题组合而来。称为复合命题的新命题是由已知命题用逻辑运算符组合而来。

命题逻辑中的命题公式(well formed formula 简记为wff)递归地定义为：

1. 单个命题变项$p,\enspace q,\enspace r,\enspace s,\enspace \dots$是命题公式
2. 如果$A$是命题公式，则($\sim A$)也是命题公式；
3. 如果$A$和$B$是命题公式，则有逻辑联结词联结$A$和$B$的符号串也是命题公式，如$A \land B, ~ A \lor B, ~ A \to B$等。
4. 有限次应用(1)~(3)构成的符号串才是命题公式。

DEFINITION 2非

令$\:p\:$为一个命题，则$\:p\:$的否定记作$\:\lnot p\:$（也可记作$\:\overline{p}\:$），指“不是$\:p\:$所指的情形”。命题$\:\lnot p\:$读作“非$\:p\:$”。$\:p\:$的否定$\:\lnot p\:$的真值和$\:{p}\:$的真值相反。

非也可以用符号$\sim$表示，$\sim p$与$\lnot p$表示的意思相同。

命题之否定的真值表

$p$	$\lnot p$
$T$	$F$
$F$	$T$

DEFINITION 合取(and)

令$\:p\:$和$\:q\:$为命题。$\:p\:$、$\:q\:$的合取即命题“$\:p\:$并且$\:q\:$”，记作$\:p\land{q}\:$。当$\:p\:$和$\:q\:$都是真时$\:p\land{q}\:$命题为真，否则为假

DEFINITION 析取(or)

令$\:p\:$和$\:q\:$为命题。$\:p\:$、$\:q\:$的析取即命题“$\:p\:$或$\:q\:$”，记作$\:p\lor{q}\:$。当$\:p\:$和$\:q\:$均为假时，$\:p\lor{q}\:$命题为假，否则为真。

DEFINITION 异或

令$\:p\:$和$\:q\:$为命题。$\:p\:$、$\:q\:$的异或（记作$p\oplus q$）是这样一个命题： 当$\:p\:$和$\:q\:$中恰好只有一个为真命题时为真，否则为假。

DEFINITION 蕴含

令$\:p\:$和$\:q\:$为命题条件语句$p \to q$是命题“如果$p$，则$q$”。当$p$为真而$q$为假时，条件语句$p \to q$为假，否则为真。在条件语句$p \to q$中，$p$称为假设（前件、前提），$q$称为结论（后件）。

$p$	$q$	$p\land q$	$p\lor q$	$p\oplus q$	$p \to q$
$T$	$T$	$T$	$T$	$F$	$T$
$T$	$F$	$F$	$T$	$T$	$F$
$F$	$T$	$F$	$T$	$T$	$T$
$F$	$F$	$F$	$F$	$F$	$T$

条件语句

语句$p \to q$称为条件语句，因为$p \to q$可以断定在条件$p$成立的时候$q$为真。条件语句也称为蕴含。$p \to q$，则$p$是$q$的必要条件。

充分条件、必要条件、充分必要条件

• 充分条件： 如果A能推出B，那么A就是B的充分条件。其中A为B的子集，即属于A的一定属于B，而属于B的不一定属于A，具体的说若存在元素属于B的不属于A，则A为B的真子集；若属于B的也属于A，则A与B相等。
• 必要条件： 必要条件是数学中的一种关系形式。如果没有A，则必然没有B；如果有A而未必有B，则A就是B的必要条件，记作$B→A$，读作“B含于A”。数学上简单来说就是如果由结果B能推导出条件A，我们就说A是B的必要条件。
• 充分必要条件： 也称充要条件 如果$\:p\:$是$\:q\:$的充要条件，则通过$\:p\:$可以推导出$\:q\:$，通过$\:q\:$也可以推导出$\:p\:$，$p \leftrightarrow q$。当且仅当即指充要条件。

“$p$仅当$q$”和“$q$除非$\lnot p$”

• “$p$仅当$q$”，表达了“如果$p$，则$q$”同样的意思。
• “$q$除非$\lnot p$”，与$p \to q$拥有相同的真值。可以做下转换，$q$除非$\lnot p$”，也就是说“如果非$\lnot p$则$q$”即$\lnot\lnot p \to q= p \to q$

DEFINITION 逆命题、逆否命题与反命题

由条件语句$p \to q$可以构成一些新的条件语句。特别是三个常见的相关条件语句还拥有特殊的名称。命题$q\to{p}$称为$p\to{q}$的逆命题，而$p\to{q}$的逆否命题是命题$\lnot{q} \to \lnot{p}$。命题$\lnot{p} \to \lnot{q}$称为$p\to{q}$的反命题。三个由$p \to q$衍生出来的条件语句中，只有逆否命题总是和$p \to q$具有相同的真值。

当两个复合命题具有相同的真值时，我们称它们是等价的。前提为真，结论为假时才为假。

$p$	$q$	$p\to q$	$q\to p$	$\lnot q\to\lnot p$	$\lnot p\to\lnot q$
$T$	$T$	$T$	$T \to T = T$	$\lnot{T} \to \lnot{T} = F \to F = T$	$\lnot{T} \to \lnot{T} = F \to F = T$
$T$	$F$	$F$	$F \to T = T$	$\lnot{F} \to \lnot{T} = T \to F = F$	$\lnot{T} \to \lnot{F} = F \to T = T$
$F$	$T$	$T$	$T \to F = F$	$\lnot{T} \to \lnot{F} = F \to T = T$	$\lnot{F} \to \lnot{T} = T \to F = F$
$F$	$F$	$T$	$F \to F = T$	$\lnot{F} \to \lnot{F} = T \to T = T$	$\lnot{F} \to \lnot{F} = T \to T = T$

DEFINITION 双条件语句

令$\:p\:$和$\:q\:$为命题。双条件语句$\:p \harr q\:$是命题“$\:p\:$当且仅当$\:q\:$”。当$\:p\:$和$\:q\:$有同样的真值时，双条件语句为真，否则为假（即同为真或同为假）。双条件语句也称为双向蕴含。

$p$	$q$	$p\harr q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$T$

$p \harr{q}$与$(p\to{q}\land{q}\to{p})$有完全相同的真值。

条件的隐式使用

~

复合命题的真值表

$p$	$q$	$\lnot q$	$p\lor \lnot q$	$p\land q$	$(p\lor \lnot{q})\to(p\land q)$
$T$	$T$	$F$	$T$	$T$	$T$
$T$	$F$	$T$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$F$	$T$
$F$	$F$	$F$	$T$	$F$	$F$

逻辑运算符的优先级

$\lnot,\land,\lor,\to,\harr$

运算符	优先级
$\lnot$	1
$\land$	2
$\lor$	3
$\to$	4
$\harr$	5

逻辑运算和位运算

真值	位
$T$	1
$F$	0

计算机的位运算对应于逻辑联结词（$\land,\lor,\oplus\quad$对应与、或、异或 ）。

$x$	$y$	$x\lor y$	$x\land y$	$x\oplus q$
$0$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$1$	$0$	$1$
$1$	$1$	$1$	$1$	$0$

永真式

假设$A$是一个$n$元命题公式，

• 若其所有$2^n$个真值指派都是成真指派，则称$A$为永真式或重言式（rautology），即无论所有命题变元取何真值，命题公式的真值都为真。
• 若其所有$2^n$个真值指派都是成假指派，则称$A$为永假式或矛盾式（contradiction），即无论所有命题变元取何真值，命题公式的真值都为假。
• 若至少存在一个成真指派，则称$A$为可满足式（statisfiable formula）
• 若$A$至少存在一个成真指派及成假指派，则称$A$为非重言的可满足式。

重言式一定是可满足式