命题逻辑

命题

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

我们用字母来表示命题变元，它是代表命题的变量。习惯上用字母 $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$ 为非重言的可满足式。

重言式一定是可满足式

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,185评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,445评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,684评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,564评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,681评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,874评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,025评论 3赞 408
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,761评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,217评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,545评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,694评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,351评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,988评论 3赞 315
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,778评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,007评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,427评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,580评论 2赞 349

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