命题逻辑

2020-04-17 本文已影响0人乌鸦DD

命题

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

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

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

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

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

非
: 令 $\: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$

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

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

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

蕴含
: 令 $\: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$

逆命题、逆否命题与反命题
: 由条件语句 $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$

双条件语句
: 令 $\: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 \leftrightarrow {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,\leftrightarrow$

运算符	优先级
$\lnot$	1
$\land$	2
$\lor$	3
$\to$	4
$\leftrightarrow$	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$ 为非重言的可满足式。

重言式一定是可满足式

命题逻辑

命题

条件语句

复合命题的真值表

逻辑运算符的优先级

逻辑运算和位运算

永真式

猜你喜欢

热点阅读

$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$	$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$

$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$

$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$	$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$

$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$

$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$	$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$

$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$