命題邏輯

命題

命題
: 命題是一個陳述預計（即陳述事實的語句）弧腥，它或真或假，但不能既真又假捻悯。

我們用字母來表示命題變元匆赃，它是代表命題的變量。習慣上用字母 $p,\enspace q,\enspace r,\enspace s,\enspace \dots$ 表示命題今缚。如果一個命題是真命題算柳，它的真值為真，用 $T$ 表示姓言；如果它是假命題瞬项，其真值為假，用 $F$ 表示何荚。

涉及命題的邏輯領域稱為命題演算或命題邏輯囱淋。許多數(shù)學陳述都是有一個或多個命題組合而來。稱為復合命題的新命題是由已知命題用邏輯運算符組合而來餐塘。

命題邏輯中的命題公式(well formed formula 簡記為wff)遞歸地定義為：

單個命題變項 $p,\enspace q,\enspace r,\enspace s,\enspace \dots$ 是命題公式
如果 $A$ 是命題公式妥衣，則( $\sim A$ )也是命題公式；
如果 $A$ 和 $B$ 是命題公式戒傻，則有邏輯聯(lián)結詞聯(lián)結 $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相等俺榆。

必要條件： 必要條件是數(shù)學中的一種關系形式感昼。如果沒有A，則必然沒有B罐脊；如果有A而未必有B定嗓，則A就是B的必要條件蜕琴，記作 $B→A$ ，讀作“B含于A”宵溅。數(shù)學上簡單來說就是如果由結果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$

邏輯運算符的優(yōu)先級

$\lnot,\land,\lor,\to,\leftrightarrow$

運算符	優(yōu)先級
$\lnot$	1
$\land$	2
$\lor$	3
$\to$	4
$\leftrightarrow$	5

邏輯運算和位運算

真值	位
$T$	1
$F$	0

計算機的位運算對應于邏輯聯(lián)結詞（ $\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$ 為非重言的可滿足式厕妖。

重言式一定是可滿足式

?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末首尼，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子言秸，更是在濱河造成了極大的恐慌软能，老刑警劉巖，帶你破解...
沈念sama閱讀 217,542評論 6贊 504
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件举畸，死亡現(xiàn)場離奇詭異查排，居然都是意外死亡，警方通過查閱死者的電腦和手機抄沮，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,822評論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門跋核，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人叛买，你說我怎么就攤上這事砂代。” “怎么了率挣？”我有些...
開封第一講書人閱讀 163,912評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵刻伊，是天一觀的道長。經(jīng)常有香客問我椒功，道長捶箱，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,449評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任蛾茉，我火速辦了婚禮，結果婚禮上撩鹿，老公的妹妹穿的比我還像新娘谦炬。我一直安慰自己，他們只是感情好，可當我...
茶點故事閱讀 67,500評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布键思。她就那樣靜靜地躺著础爬，像睡著了一般。火紅的嫁衣襯著肌膚如雪吼鳞。梳的紋絲不亂的頭發(fā)上看蚜，一...
開封第一講書人閱讀 51,370評論 1贊 302
城市分裂傳說
那天，我揣著相機與錄音赔桌，去河邊找鬼供炎。笑死，一個胖子當著我的面吹牛疾党，可吹牛的內(nèi)容都是我干的音诫。我是一名探鬼主播，決...
沈念sama閱讀 40,193評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼雪位，長吁一口氣：“原來是場噩夢啊……” “哼竭钝！你這毒婦竟也來了？” 一聲冷哼從身側響起雹洗，我...
開封第一講書人閱讀 39,074評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤香罐，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后时肿，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體庇茫，經(jīng)...
沈念sama閱讀 45,505評論 1贊 314
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,722評論 3贊 335
?白月光啟示錄
正文我和宋清朗相戀三年嗜侮，在試婚紗的時候發(fā)現(xiàn)自己被綠了港令。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 39,841評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡锈颗，死狀恐怖顷霹，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情击吱，我是刑警寧澤淋淀，帶...
沈念sama閱讀 35,569評論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站覆醇，受9級特大地震影響朵纷，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜永脓，卻給世界環(huán)境...
茶點故事閱讀 41,168評論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一袍辞、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧常摧，春花似錦搅吁、人聲如沸威创。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,783評論 0贊 22
一樁弒父案谎懦，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽肚豺。三九已至，卻和暖如春界拦，著一層夾襖步出監(jiān)牢的瞬間吸申，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,918評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工享甸，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留截碴，地道東北人。一個月前我還...
沈念sama閱讀 47,962評論 2贊 370
代替公主和親
正文我出身青樓枪萄，卻偏偏與公主長得像隐岛，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子瓷翻，可洞房花燭夜當晚...
茶點故事閱讀 44,781評論 2贊 354

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

命題邏輯

命題

條件語句

復合命題的真值表

邏輯運算符的優(yōu)先級

邏輯運算和位運算

永真式

推薦閱讀更多精彩內(nèi)容

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