離散數(shù)學(xué)第3章命題邏輯.ppt

《離散數(shù)學(xué)第3章命題邏輯.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第3章命題邏輯.ppt（192頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第3章命題邏輯 3 1命題的有關(guān)概念 本講內(nèi)容 命題之間的還有些什么關(guān)系 認(rèn)知關(guān)系 我知道 偏好關(guān)系 他喜歡 邏輯關(guān)系 Chapter3命題邏輯 邏輯學(xué)是研究思維形式及思維規(guī)律尤其是推理的學(xué)科 邏輯推理無處不在 亞里士多德 Aristotle 公元前384 公元前322 是形式邏輯的創(chuàng)始人 數(shù)學(xué) 物理學(xué) 化學(xué) 天文學(xué) 地學(xué) 生物學(xué) 邏輯學(xué) MBA MPA 招聘等 萊布尼茨 G Leibniz 1647 1716 是數(shù)理邏輯的創(chuàng)始人 傳統(tǒng)的數(shù)理邏輯 內(nèi)容包括邏輯演算 公理化集合論 模型論 遞歸論和證明論 應(yīng)用邏輯 如多值邏輯 模態(tài)邏輯 歸納邏輯 時序邏輯 動態(tài)邏輯 模糊邏輯 非單調(diào)邏輯 缺省邏輯 數(shù)字邏輯 電路邏輯 算法邏輯及程序邏輯等 這些都與計算機(jī)科學(xué)密切相關(guān) 計算機(jī)如何進(jìn)行邏輯思維的 計算思維培養(yǎng) 命題邏輯與謂詞邏輯是數(shù)理邏輯的基礎(chǔ)部分 本章學(xué)習(xí)命題邏輯 命題邏輯的研究對象是命題 3 1命題的有關(guān)概念 計算機(jī)的計算過程就是推理過程 而每一步推理離不開判斷 判斷的對象就是命題 1 什么是命題 命題是能判斷出真假的語句 從三個方面去理解 1 命題必須是一個完整的句子 包括用數(shù)學(xué)式子如代表的語句 2 所給語句具有真假意義 即有是否符合客觀實際或是否合理之分 一般來說 只有陳述句才具有真假意義 祈使句 疑問句和感嘆句不具有真假意義 3 能判斷出真假 要是將來某時候能判斷出真假也行 例3 1判斷下列語句是否是命題 1 遼寧艦是中國的第一首航空母艦 2 我喜歡智能手機(jī)和平板電腦 3 x 3 4 立正 5 這朵花真漂亮 6 你要我的手機(jī)號碼是想給我充話費 7 火星上有生物 美國Discovery號 火星上有水 2012年著陸火星的Curiosity號 1 1 2 8 我說的都是假話 9 小王和小李是同學(xué) 10 你只有刻苦學(xué)習(xí) 才能取得好成績 歌德巴赫猜想 至今已200多年 1 1 1 2 大于4的偶數(shù)是兩個奇素數(shù)之和 6 3 3 8 3 5 10 3 7 5 5 12 5 7 2 任何大于7的奇數(shù)是三個奇素數(shù)之和 9 3 3 3 11 3 3 5 13 3 3 7 15 3 5 7 陳景潤 1966 的 陳式定理 1 2 3 任何充分大的偶數(shù)是一個素數(shù)與兩個素數(shù)乘積之和 2007年11月15日重慶商報 大坪67歲羅仁德破解 1935年出生的河北的何寶起自稱破解 奔波8年無人理 2 命題的真值 truth 命題的真值就是命題的邏輯取值 經(jīng)典邏輯值只有兩個 1和0 它們是表示事物狀態(tài)的兩個量 若一個命題是真命題 其真值為1 若一個命題是假命題 其真值為0 實際上在數(shù)理邏輯中 更多時候邏輯真是用T True 或t 邏輯假用F False 或f表示的 3 原子命題與復(fù)合命題若一個命題不包含有更小的命題 則稱其為原子命題 atom 當(dāng)時認(rèn)為原子最小 或簡單命題 否則稱為復(fù)合命題 compoundproposition 原子命題是命題邏輯研究的基本單位 區(qū)分原子命題在后面命題的符號化時是很重要的 通常用小寫英文字母p q r s 或帶下標(biāo)p1 p2 p3 等來表示原子命題 如用p 2 3 5 q 今天我們上課 4 邏輯常量與邏輯變量把1和0稱為邏輯常量 logicalconstant 在邏輯表達(dá)式中出現(xiàn)的p q r或p1 p2 p3等稱為命題變元 propositionvariable 或邏輯變量 logicalvariable 命題變元可以代表任意命題 從取值的角度看 命題變元既可以取1又可以取0 課堂練習(xí)習(xí)題3 11 2 小結(jié) 第3章命題邏輯 3 2邏輯聯(lián)結(jié)詞 本講內(nèi)容 p q p q p q 3 2邏輯聯(lián)結(jié)詞 邏輯聯(lián)結(jié)詞就是邏輯運算 復(fù)合命題是由原子命題構(gòu)成的 它需要聯(lián)結(jié)詞 給定了原子命題 使用邏輯聯(lián)結(jié)詞可以構(gòu)成復(fù)合命題 邏輯聯(lián)結(jié)詞類似于自然語言中的連詞 1 否定 not 聯(lián)結(jié)詞 pp 2 3 5 p 2 3 5 p是數(shù)理邏輯中的標(biāo)準(zhǔn)符號 也可記為 p C語言 p 在計算機(jī)其他課程中用 對應(yīng)于邏輯門電路中的 非門 2 合取 and 聯(lián)結(jié)詞 p qp 小李能歌 q 小李善舞 p q 小李能歌且善舞 合取 相當(dāng)于 并且 和 與 以及 等 Remark 1 小王和小李是同學(xué) 中的 和 沒有合取之意 2 在數(shù)理邏輯中 合取聯(lián)結(jié)詞可以將任意兩個命題聯(lián)結(jié)起來以構(gòu)造出新的命題 如用p 2 3 5 q 今天上課 則p q 2 3 5且今天上課 下面要介紹的其他聯(lián)結(jié)詞都是這樣理解 3 p 小李結(jié)婚了q 小李有小孩了p q q p p q p q p q p q pq 對應(yīng)于 與門 3 析取 or 聯(lián)結(jié)詞 p qp 這學(xué)期我選修人工智能課程 q 這學(xué)期我選修模式識別課程 p q 這學(xué)期我選修人工智能課程或者模式識別課程 析取 相當(dāng)于 或者 p q p q p q 或門 本講內(nèi)容 p q p q p q 4 異或 exclusiveor XOR 聯(lián)結(jié)詞 p q自然語言中的 或 1 可兼或 inclusiveor 它表示兩者可同時為真 用析取表示即可 2 不可兼或 它表示兩者不能同時為真 換句話說 兩者同時為真是假命題 這就需要異或聯(lián)結(jié)詞 p 明天去深圳的飛機(jī)是上午八點起飛 q 明天去深圳的飛機(jī)是上午八點半起飛 p q 明天去深圳的飛機(jī)是上午八點或上午八點半起飛 本學(xué)期張三或李四當(dāng)選為班長 今天晚上在寢室上自習(xí)或去電影院看3D電影 都在寢室 7 30 與異或聯(lián)結(jié)詞對應(yīng)的門電路為 異或門 一般來說 只要不是非常明顯的不可兼就使用 5 條件 conditional 聯(lián)結(jié)詞 p qp 我有時間 q 我去看望我的父母 p q 如果我有時間 那么我去看望我的父母 相當(dāng)于 如果 那么 若 則 等 p q可讀作 若 p則q 蘊涵聯(lián)結(jié)詞也可以稱為條件聯(lián)結(jié)詞 在p q中 p稱為前件 q稱為后件 當(dāng)p 1 q 1時p q 1 當(dāng)p 1 q 0時p q 0 這是比較好理解的兩種情形 規(guī)定的合理性見下面的例子 1 如果太陽從西邊出來 那么2 3 5 2 如果太陽從西邊出來 那么2 3 4 實際上 在根據(jù)子集的定義證明1 1節(jié)的定理 對于任意集合A 有 A時 就要用到上述實質(zhì)蘊涵的定義 同樣 在理解關(guān)系的自反 反自反 對稱 反對稱及傳遞性質(zhì)時 也要用到上述實質(zhì)蘊涵的定義 當(dāng)然 在現(xiàn)代邏輯中 對蘊涵的不同理解會得到不同的邏輯系統(tǒng) 如由嚴(yán)格蘊涵得出模態(tài)邏輯系統(tǒng) 6 雙條件 biconditional 聯(lián)結(jié)詞 p qp 四邊形是平行四邊形 q 四邊形的對邊平行 p q 四邊形是平行四邊形當(dāng)且僅當(dāng)四邊形的對邊平行 p q 可讀作 p當(dāng)且僅當(dāng)q 雙條件聯(lián)結(jié)詞 相當(dāng)于自然語言中的 當(dāng)且僅當(dāng) 充分必要條件 其英文為ifandonlyif 縮寫為iff p當(dāng)且僅當(dāng)q 有兩層含義 1 p當(dāng)q 是指q p 2 p僅當(dāng)q 是指p q 正因為此 等價聯(lián)結(jié)詞又可以稱為雙蘊涵聯(lián)結(jié)詞或雙條件聯(lián)結(jié)詞 數(shù)字邏輯等課程的 同 并用 表示 本講內(nèi)容 p q p q p q 7 與非 NOTAND 聯(lián)結(jié)詞 p q在數(shù)字邏輯以及計算機(jī)組成原理中 沒有專用的運算符號 p與非q 直接記為 對應(yīng)的門電路為 與非門 8 或非 NOTOR 聯(lián)結(jié)詞 p q在數(shù)字邏輯以及計算機(jī)組成原理中 沒有專用的運算符號 p或非q 直接記為 對應(yīng)的門電路為 或非門 9 條件否定 NOT IF THEN 聯(lián)結(jié)詞 讀作 p條件否定q 其中n表示否定not p條件否定q 可直接記為 上面介紹了1個一元邏輯運算 8個二元邏輯運算 后面將證明 不同的一元邏輯運算和二元邏輯運算共9個 要求理解記憶上述9個 特別是最前面的6個聯(lián)結(jié)詞的運算表 思考如何定義三元邏輯運算 課堂練習(xí)習(xí)題3 21 6 小結(jié) 第3章命題邏輯 3 3命題公式及其真值表 本講內(nèi)容 3 3命題公式及其真值表 有了前面的兩節(jié)內(nèi)容 就可以得到命題邏輯的符號體系 1 命題公式 propositionformula 的定義邏輯函數(shù) logicalfunction 邏輯表達(dá)式 logicalexpression 其中的常量是邏輯常量1和0 其中的變元是命題變元或邏輯變量 命題公式是由命題常量 命題變元 邏輯聯(lián)結(jié)詞 左圓括號及右圓括號構(gòu)成的有意義 well formed 的符號串 其嚴(yán)格定義需借助于遞歸定義方式給出 Definition 1 1 0 p q r 2 A A 3 A B 4 有限次應(yīng)用 1 2 3 所得到的符號串是僅有的命題公式 命題公式可稱為合式公式 Well FormedFormula WFF 或簡稱為公式 其全稱為命題合式公式 是書寫正確 含義清楚的表達(dá)式或者說符號串 借助于函數(shù)給命題公式下定義 可以省略括號的約定 1 最外層的括號可以省略 在形成最終的命題公式時 所有的中間過程得到的命題公式 包含其本身 都稱為該命題公式的子公式 2 9個聯(lián)結(jié)詞運算的優(yōu)先順序依次為 符合本約定的有些括號可以不寫 如命題公式Remark這種規(guī)定不是唯一的 3 同級運算從左至右依次進(jìn)行 如實際上 在對命題進(jìn)行符號化時 只要書寫正確的邏輯函數(shù)都是命題公式 2 命題的符號化命題的符號化就是使用符號 命題變元 邏輯聯(lián)結(jié)詞和括號將所給出的命題表示出來 符號體系來源于實際問題 給出進(jìn)一步學(xué)習(xí)邏輯演算系統(tǒng)的語義解釋時的一種標(biāo)準(zhǔn)模型 命題的符號化的步驟 Step1找出所給命題的所有原子命題 并用小寫英文字母或帶下標(biāo)表示 Step2確定應(yīng)使用的聯(lián)結(jié)詞 進(jìn)而將原命題用符號表示出來 例3 7將下列命題符號化 1 天氣很好或很熱 2 如果張三和李四都不去 那么我就去 3 僅當(dāng)你走 我留下 4 我今天進(jìn)城 除非天下雨 5 你只有刻苦學(xué)習(xí) 才能取得好成績 Solution 1 用p 天氣很好 q 天氣很熱 天氣很好或很熱 可符號化為 2 用p 張三去 q 李四去 r 我去 則原命題可符號化為 3 用p 你走 q 我留下則 僅當(dāng)你走 我留下 可符號化為 4 p 我今天進(jìn)城 q 天下雨 除非 如果不 5 p 你刻苦學(xué)習(xí) q 你取得好成績 只有p 才q 本講內(nèi)容 3 命題公式的真值表命題公式的真值表就是命題公式的取值情況表 若對中出現(xiàn)的每個命題變元都指定一個真值1或者0 就對命題公式A進(jìn)行了一種真值指派或一個解釋 而在該指派下會求出公式A的一個真值 將A的所有可能的真值指派以及在每一個真值指派下的取值列成一個表 就得到命題公式A的真值表 truthtable 例3 8寫出命題公式的真值表 要求大家能準(zhǔn)確寫出一個命題公式的真值表 這是本節(jié)的重點內(nèi)容 當(dāng)然必須牢記聯(lián)結(jié)詞的運算表才行 由表知 含3個命題變元的命題公式有8 23種不同的真值指派 很顯然 含2個命題變元的命題公式有4 22種不同的真值指派 含n個命題變元的命題公式的不同的真值指派有2n種 4 命題公式的類型 1 在任何指派下均取真的命題公式稱為永真式或重言式 tautology 2 在任何指派下均取假的命題公式稱為永假式或矛盾式 contradiction 3 至少有一種指派使其為真的命題公式稱為可滿足式 satisfactableformula 4 至少有一種指派使其為真同時至少有一種指派使其為假的命題公式稱為中性式 偶然式 contingency 例3 9真值表法 例3 10Proof由A 1可推出B 1 則A B永真 由B 0可推出A 0 則A B永真 取值法 本質(zhì)上是真值表法 最后介紹永真式的代入定理RS RuleofSubstitution Theorem3 1 永真式的代入定理 如何使用 小結(jié)與作業(yè) 第3章命題邏輯 3 4邏輯等值的命題公式 本講內(nèi)容 3 4邏輯等值的命題公式 命題 四邊形的對邊平行 與命題 四邊形的對邊相等 是邏輯等值的 它們在邏輯上說的是同一回事 上述兩個命題的真值是相同的 下面討論兩個命題公式邏輯等值 1 邏輯等值的定義Def給定兩個命題公式A和B 若在任何真值指派下A和B的真值都相同 則稱命題公式A和B邏輯等價或邏輯等值 logicallyequal 或簡稱為等值或相等 記為A B Remark 是命題公式之間的關(guān)系符號 A B Theorem3 2A B的充要條件是A B永真 ProofClearly 下面的例子說明如何利用真值表 第一種方法 證明兩個命題公式等值 例3 11證明 Theorem3 3例如 Theorem邏輯等值是命題公式間的等價關(guān)系 1 自反 2 對稱 3 傳遞 Problem等價類是什么 2 基本等值式 I 與 有關(guān)的等值式Theorem3 5 1 2 3 4 5 6 7 8 9 10 Remarks 1 與集合的有關(guān)性質(zhì)類似 2 每條性質(zhì)均可證明 II 其他重要的等值式Theorem 1 2 3 4 5 6 Proof 3 等值演算法基本等值式有很多用途 如化簡命題公式 判斷命題公式的類型 證明等值式 計算命題公式的范式 命題邏輯中的推理等 要求大家要熟記 特別是定理3 5中的等值式 在使用等值式時 常用下列的等值置換定理RR RuleofReplacement 等值置換定理設(shè)C是命題公式A的子公式 若C D 則將A中的C部分或全部替換為D所得到的命題公式與A等值 利用基本等值式以及等值置換定理求解問題的方法稱為 等值演算法 例3 13化簡 下列命題公式并將最后結(jié)果用只含 和 表示 1 2 Solution 1 數(shù)字邏輯 計算機(jī)組成中經(jīng)?；唵?利用等值演算法 判斷一個命題公式的類型是比較方便的 例3 14設(shè)A B C是任意的命題公式 判斷下列命題公式的類型 1 2 Solution 2 證明兩個命題公式等值的第二種方法 等值演算法 例3 15設(shè)A B C是任意的命題公式 證明下列等值式 1 2 Proof 2 4 對偶原理在與 有關(guān)的基本等值式中 除性質(zhì) 1 外 其它性質(zhì)都是成對出現(xiàn)的 兩者間有一定的聯(lián)系 先給出命題公式的對偶式的定義 Def3 4設(shè)命題公式A中至多含有3個邏輯聯(lián)結(jié)詞 1 將A中的 換成 2 A中的 換成 3 A中的1換成0 4 A中的0換成1 所得到的命題公式稱為是A的對偶式 dualformula 記為A 例如Remark一般來說 對偶原理設(shè)A和B是命題公式 若A B 則A B 有了對偶原理后 定理3 5中除性質(zhì) 1 外的等值式 只需要記住其中一個就可以了 有了對偶原理 我們可以求出任意命題公式的對偶式 小結(jié)與作業(yè) 第3章命題邏輯 3 5命題公式的范式 本講內(nèi)容 3 5命題公式的范式 命題公式的范式就是其標(biāo)準(zhǔn)形式或規(guī)范形式 有了命題公式的范式 就可以不用寫出真值表就能確定在何真值指派下取真以及在何真值指派下取假 1 命題公式的析取范式及合取范式 1 析取范式及合取范式的定義Def3 5設(shè)A是命題公式 若A A1 A2 An n 1 其中Ai 1 i n 是由命題變元或其否定組成的合取式 則稱A1 A2 An為A的析取范式 disjunctivenormalform RemarksAi p q r p q q r q r n 1 如A p q r p q r Def3 6設(shè)A是命題公式 若A A1 A2 An n 1 其中Ai 1 i n 是由命題變元或其否定組成的析取式 則稱A1 A2 An為A的合取范式 conjunctivenormalform RemarksAi p q r p q q r q r n 1 如A p q r p q r 若A p q r 則 p q r也是A的析取范式 2 析取范式及合取范式的計算Step1使用等值式 將命題公式中的聯(lián)結(jié)詞歸約為 Step2利用DeMorgan律將 移到命題變元的前面 Step3根據(jù)分配律得到命題公式的析取范式及合取范式 A B C A B A C 求析取范式用 A B C A B A C 求合取范式用 例3 17設(shè)p q和r是命題變元 求命題公式A p q r的析取范式及合取范式 Solution求命題公式的析取范式及合取范式的Step1和Step2是相同的 析取范式 合取范式 3 析取范式及合取范式的應(yīng)用根據(jù)命題公式的析取范式及合取范式可分別得出該命題公式取真 假的指派 例3 18從p q r s四人中選派2人出差 求滿足下列3個條件的選派方法有哪幾種 1 若p去 則r和s中只去1人 2 q和r不能都去 3 若r去 則s不能去 Solutionp p去出差 q q去出差 r r去出差 s s去出差 則 1 2 3 a p s去 b q s去 c p r去 2 命題公式的主析取范式及主合取范式一般來說 命題公式的析取范式及合取范式不是唯一的 如A p q p q p都是A的析取范式 下面討論 給定命題公式的唯一的標(biāo)準(zhǔn)形式 主析取范式以及主合取范式 給定命題公式 從A中命題變元產(chǎn)生的最小項和最大項的角度來討論A的主析取范式及主合取范式 在邏輯電路中也會討論其相應(yīng)的標(biāo)準(zhǔn)形式 1 主析取范式Def對于給定的命題變元 若由命題變元或其否定組成的合取式滿足 1 每個命題變元或其否定二者之一只出現(xiàn)一次 2 按字典順序或按下標(biāo)從小到大順序出現(xiàn) 稱這樣的合取式為由所給命題變元產(chǎn)生的最小項 對于每一個最小項只有一種指派使其取1 可以根據(jù)這個結(jié)論對最小項編碼 最小項用表示mi 其下標(biāo)是由成真指派得到的二進(jìn)制數(shù)或?qū)?yīng)的十進(jìn)制數(shù) 對于最小項p q r 成真指派得到的二進(jìn)制數(shù)為110 因為 110 2 6 所以p q r m110 m6 表3 15 Def對于命題公式A 若A等值于由A中所有命題變元產(chǎn)生的若干個最小項的析取 則把后者稱為A的主析取范式 majordisjunctiveform 含n個命題變元的命題公式 若干個 最大為2n 最小為0 所有最小項的析取為永真式1 而0個最小項的析取意味著A為永假式0 這時的主析取范式不存在 除這兩種極端情形外 A均為中性式 顯然 主析取范式是析取范式 但反過來不成立 根據(jù)這個分析 我們得到求A的主析取范式的第一種方法 等值演算法 利用等值演算法求A的主析取范式的步驟為Step1求出A的析取范式 Step2利用分配律補(bǔ)充所缺少的命題變元 由上面的主析取范式可知 使A取1的真值指派為 p q r 1 0 0 0 1 1 0 0 1 1 1 1 實際上 我們可以利用A的真值表求A的主析取范式 利用真值表求主析取范式的3個步驟為Step1寫出命題公式A的真值表 Step2對于使A取1的指派 寫出對應(yīng)的最小項 使該最小項在該指派下也為1 Step3 可以證明 A等值于所有這樣寫出的最小項的析取 例3 20設(shè)p q和r是命題變元 求命題公式 p q r的主析取范式 2 主合取范式主合取范式的討論與主析取范式是類似的 為了方便自學(xué) 我們還是進(jìn)行完整的討論 Def3 9對于給定的命題變元 若由命題變元或其否定組成的析取式滿足 1 每個命題變元或其否定二者之一只出現(xiàn)一次 2 按字典順序或按下標(biāo)從小到大順序出現(xiàn) 稱這樣的析取式為由所給命題變元產(chǎn)生的最大項 maximalterm 對于每一個最大項只有一種指派使其取0 可以根據(jù)這個結(jié)論對最大項編碼 最大項用表示Mi 其下標(biāo)是由成假指派得到的二進(jìn)制數(shù)或?qū)?yīng)的十進(jìn)制數(shù) 對于最大項p q r 成真指派得到的二進(jìn)制數(shù)為001 因為 001 2 1 所以p q r M001 M1 Def3 10對于命題公式A 若A等值于由A中所有命題變元產(chǎn)生的若干個最大項的合取 則把后者稱為A的主合取范式 含n個命題變元的命題公式 若干個 最大為2n 最小為0 所有最大項的合取為永假式0 而0個最大項的合取意味著A為永真式1 這時的主合取范式不存在 除這兩種極端情形外 A均為中性式 主合取范式是合取范式 但反過來不成立 根據(jù)這個分析 我們得到求A的主合取范式的第一種方法 等值演算法 利用等值演算法求A的主合取范式的步驟為Step1求出A的合取范式 Step2利用分配律補(bǔ)充所缺少的命題變元 由上面的主合取范式可知 使A取0的真值指派為 p q r 0 0 0 0 1 0 1 1 0 1 0 1 實際上 我們可以利用A的真值表求A的主合取范式 下面介紹求的主合取范式的第二種方法 真值表法 Step1寫出命題公式A的真值表 Step2對于使A取0的指派 寫出對應(yīng)的最大項 使該最大項在該指派下也為0 Step3 可以證明 A等值于所有這樣寫出的最大項的合取 例3 22設(shè)p q和r是命題變元 求命題公式 p q r的主合取范式 Theorem3 9任意非永假命題公式都存在唯一的主析取范式 任意非永真命題公式都存在唯一的主合取范式 1 命題公式的主析取范式和主合取范式是等值的 2 主析取范式中所含的最小項個數(shù)加上主合取范式中所含的最大項個數(shù)等于該命題公式的真值指派數(shù)目 3 可以從主析取范式求出主合取范式 反過來亦然 A 利用命題公式的主析取范式及主合取范式判定其類型 例3 23設(shè)p和q是命題變元 利用主范式判斷命題公式p p q 的類型 Solution B 利用命題公式的主析取范式及主合取范式可以判斷兩個命題公式是否等值 例3 24 1 2 C 在數(shù)字邏輯等后繼課程中的應(yīng)用 例3 25設(shè)公式A的真值表如下 求A 將A化簡 門電路實現(xiàn) 解法1比解法2好 因為最小項的個數(shù)為3而最大項的個數(shù)為5 所以在電路實現(xiàn)時對A進(jìn)行的化簡要容易些 一般原則是 若取1的個數(shù)小于取0的個數(shù) 求出主析取范式 若取0的個數(shù)小于取1的個數(shù) 求出主合取范式 同一個命題公式的主析取范式與其主合取范式是等值的 只要給出了一個命題公式的真值表 就可以將該命題公式 的表達(dá)式 求出來 這一點在3 6節(jié)中也會用到 另外 根據(jù)真值表法可知 若得出了命題公式的主析取范式 則可以得出使為真的所有指派 進(jìn)而得出使為假的所有指派 因此可以得出命題公式的主合取范式 反過來亦然 小結(jié)與作業(yè) 第3章命題邏輯 3 6聯(lián)結(jié)詞集合的功能完備性 本講內(nèi)容 3 6聯(lián)結(jié)詞集合的功能完備性 前面介紹了9個聯(lián)結(jié)詞 我們想知道 1 1元和2元 聯(lián)結(jié)詞一共有多少個 2 哪些聯(lián)結(jié)詞集合具有功能完備性 這些內(nèi)容可以從一定的理論高度幫助理解邏輯門電路的種類及其按一定要求化簡邏輯函數(shù)等問題 1 聯(lián)結(jié)詞的個數(shù) 由p和q可構(gòu)成不等值的命題公式共222 16個 記為Ai i 1 2 16 集合運算與邏輯運算之間有緊密的聯(lián)系 問題1能否類似于真值表形式給出集合運算的定義 若能 如何給出 前面已經(jīng)說明了 不同的1元和2元邏輯運算共9種 3元邏輯運算更多 而集合運算只介紹了5種 問題2給出另外4種集合運算的定義 問題39種邏輯運算與9種集合運算是如何對應(yīng)的 2 聯(lián)結(jié)詞集合的功能完備性有些邏輯運算可以借助于其他聯(lián)結(jié)詞加以定義 有些聯(lián)結(jié)詞如 就不能由 和 加以定義 這涉及到聯(lián)結(jié)詞集合的功能完備性 Def3 11對于若干個聯(lián)結(jié)詞組成的非空集合S 若任意的命題公式都可由僅含S中的聯(lián)結(jié)詞等值地表示出來 則稱S為功能完備聯(lián)結(jié)詞集 completegroupofconnectives 將S中的聯(lián)結(jié)詞理解為門電路 則S是完備的是指任何的組合邏輯電路都可以由這些門電路實現(xiàn) 任意命題公式都存在唯一的主析取范式或主合取范式 于是任意的命題公式都可以由 等值表示出來 因此 有Theorem 是功能完備聯(lián)結(jié)詞集 Corollary 1 2 3 4 5 Proof 1 例3 26Solution 例3 27Solution 下面考慮不具有功能完備性的聯(lián)結(jié)詞集 例3 28 Proof首先證明 對于只含有聯(lián)結(jié)詞的任意命題公式A 在所有命題變元均取1時 A的真值為1 對A中所含的聯(lián)結(jié)詞個數(shù)n使用數(shù)學(xué)歸納法 n 0 A B A B 其次說明p p Def3 12設(shè)S是功能完備的聯(lián)結(jié)詞集 而S的任意非空真子集都不是功能完備的聯(lián)結(jié)詞集 則稱S為最 極 小的功能完備的聯(lián)結(jié)詞集 Theorem3 11下列聯(lián)結(jié)詞集是最小功能完備的 1 2 3 4 5 知道了邏輯運算的個數(shù)以及最小的功能完備的聯(lián)結(jié)詞集 對于我們進(jìn)一步學(xué)習(xí) 研究邏輯演算形式系統(tǒng)是有幫助的 在實際應(yīng)用中 聯(lián)結(jié)詞 以及 可推廣到多個命題變元上去 如 與或非門 等 小結(jié) 第3章命題邏輯 3 7命題邏輯中的推理 本講內(nèi)容 3 7命題邏輯中的推理 邏輯學(xué)的主要內(nèi)容是研究推理 推理是從一些前提推出結(jié)論的思維過程 數(shù)理邏輯主要是用數(shù)學(xué)的方法研究邏輯中的推理 它關(guān)心的是推理形式的有效性問題 下面兩個不同的推理 a 若兩直線平行 則同位角相等 這兩直線是平行的 所以 同位角相等 b 若兩個三角形全等 則其對應(yīng)邊相等 這兩個三角形全等 所以 它們的對應(yīng)邊相等 都具有如下的推理形式 由p q p得出q 所謂推理形式的有效性是指 如果前提全為真 那么所得結(jié)論必然真 而不考慮前提和結(jié)論的真實含義 有效的推理形式是四海皆準(zhǔn)的推理規(guī)則 1 推理形式有效性的定義Def3 13 logicallyfollows Theorem的充要條件由上述定理 知 是關(guān)系符號 它與蘊涵聯(lián)結(jié)詞 是不同的 從推理的角度看 將 寫成 更適合 Theorem3 13設(shè)A和B是命題公式 則A B的充要條件是A B且B A Hint 命題公式間的永真蘊涵關(guān)系是偏序關(guān)系 1 A A 自反性 2 若A B且B A 則A B 反對稱性 3 若A B且B C 則A C 傳遞性 命題公式間的 關(guān)系還具有下面兩條性質(zhì) Theorem3 15 1 若A C且B C 則A B C 2 若C A且C B 則C A B Theorem3 16設(shè)A B是命題公式 則對于命題公式間的 關(guān)系 1 sup A B A B 2 inf A B A B 2 基本推理規(guī)則下面舉例說明 證明推理形式有效性的4種方法 例3 29設(shè)A和B是命題公式 證明 A B A B 分析 p q p q永真 Proof1真值表法 Proof2取值法 p q p 1 q 1 Proof3等值演算法 p q p q 1 Proof4主范式法 主析取范式 主合取范式 不存在 基本推理規(guī)則或基本蘊涵式I 1 2 3 4 5 6 7 8 基本等值式E 表3 24 3 命題邏輯的自然推理系統(tǒng)作為推理系統(tǒng) 原則上有以下四個部分 第一 它應(yīng)有初始符號 它是系統(tǒng)中允許出現(xiàn)的字符 自然推理系統(tǒng)的初始符號有3類 1 命題變元 2 5個聯(lián)結(jié)詞 3 左右圓括號 第二 定義推理系統(tǒng)中的公式 它是按一定的形成規(guī)則得到的有意義的符號串 粗略地說 它就是命題公式 但它原則上不出現(xiàn)除 外的其它聯(lián)結(jié)詞 同時原則上不出現(xiàn)命題常量1和0 第三 確定公理 就是推理系統(tǒng)中不加推導(dǎo)就承認(rèn)的公式 從語義的角度看 它就是永真式 自然推理系統(tǒng)中沒有公理 這一點是與公理推理系統(tǒng)截然不同的 第四 確定推理規(guī)則 在自然推理系統(tǒng)中 把所有與5個聯(lián)結(jié)詞有關(guān)的基本邏輯蘊涵式都作為推理規(guī)則 見表1 同時 一個基本等值式 見下表2 相當(dāng)于兩個基本邏輯蘊涵式 兩個最基本的推理規(guī)則 P規(guī)則所給的前提在證明過程中隨時可以引用 T規(guī)則已經(jīng)推出的公式在以后的證明過程中可以隨時引用 自然推理系統(tǒng)的顯著特點是沒有公理 作為推理依據(jù)的只有推理規(guī)則 這似乎更符合人們?nèi)粘Ｋ季S的推理習(xí)慣 因此稱為自然推理 在進(jìn)行自然推理時 采用構(gòu)造性證明方法 簡稱 構(gòu)造法 更準(zhǔn)確地應(yīng)該說是數(shù)理邏輯中的演繹 deduction 法 通過一個例子了解證明的書寫格式 例3 30使用構(gòu)造法證明 Proof 1 p sP 2 pT 1 I 3 sT 1 I 4 p q r P 5 q rT 2 4 I 6 s qP 7 qT 3 6 I 8 rT 5 7 I 從證明過程可以看出 每一行由3部分組成 第一部分是編號 說明它是證明的第幾步 第二部分僅寫一個命題公式 實際上編號也說明了它是第幾個命題公式 第三部分是寫理由 交代該命題公式是怎樣得來的 初學(xué)者最感困難的是 如何一步一步的構(gòu)造出從前提到結(jié)論的證明過程 與其它證明題一樣 可以先進(jìn)行分析 一個推理形式是有效的 實際上是指符號推理是正確的 要證明一個推理形式是有效的 首先將所給的前提和結(jié)論符號化 再證明這個符號推理是正確的 例3 32用構(gòu)造法證明下列推理形式的有效性 如果小趙和小錢去上自習(xí) 則小孫也去 小李不去自習(xí)或小趙去自習(xí) 由于小錢和小李已經(jīng)去自習(xí)了 所以小孫也去上自習(xí)了 下面介紹兩種間接的構(gòu)造性證明方法 1 反證法要證明 將結(jié)論C否定得到 C 然后推出一個矛盾 如S S即可 例3 33反證法 Proof 1 p P 附加 2 pT 1 E 3 r qP 4 qT 3 I 5 p qT 2 4 I 6 p q rP 7 rT 5 6 I 8 rT 3 I 9 r rT 7 8 I 2 CP規(guī)則 條件證明規(guī)則 對于如下形式的推理只需要證明因為 例3 34使用CP規(guī)則證明 Proof 1 p q r P 2 pP 附加 3 q rT 1 2 I 4 q pP 5 q pT 4 E 6 qT 2 5 I 7 rT 3 6 I 8 s rP 數(shù)理邏輯的主要研究任務(wù)是建立一個嚴(yán)密的邏輯推理系統(tǒng) 公理推理系統(tǒng)來刻劃人類的思維規(guī)律 如PC formalsystemofPropositionCalculus 在理論上證明了該邏輯系統(tǒng)合理性 一致性 完備性等與語法和語義有關(guān)的重要結(jié)論 PC能得出人類思維的所有推理規(guī)則 所提供的邏輯推理框架能保證在前提真的條件下 總能得出正確的結(jié)論 對邏輯演算形式系統(tǒng)感興趣 特別是做計算機(jī)軟件工作的讀者請參閱有關(guān)文獻(xiàn) 小結(jié)與作業(yè) 離散數(shù)學(xué) 第26講第3章復(fù)習(xí)小結(jié) 1 命題的有關(guān)概念 能判斷出真假的語句稱為命題 真命題真值為1 假命題真值為0 不能分成更小的命題是原子命題 通常用小寫英文字母或帶下標(biāo)表示 否則是復(fù)合命題 命題常量與命題變元 2 邏輯聯(lián)結(jié)詞 1元或2元邏輯運算共有9個最基本的聯(lián)結(jié)詞是 例1下列聯(lián)結(jié)詞中 不滿足交換律的是 A B C D 3 命題公式 命題公式就是邏輯函數(shù)或邏輯表達(dá)式 其中出現(xiàn)命題常量0和1 命題變元和邏輯運算 但含義要清楚 將一個命題符號化后所得到的式子均為命題公式 命題符號化的步驟 第一步 找出所給命題的所有原子命題 并用小寫英文字母或帶下標(biāo)表示 第二步 確定應(yīng)使用的聯(lián)結(jié)詞 進(jìn)而將原命題用符號表示出來 例2令p 我將去上網(wǎng) q 我有時間 則 我將去上網(wǎng) 僅當(dāng)我有時間 可符號化為 A p q B p q C q p D p q 例3設(shè)p 我們劃船 q 我們跑步 則命題 我們不能既劃船又跑步 符號化為 A p q B p q C p q D p q 命題公式的真值表就是該命題公式的取值情況表 要求能準(zhǔn)確寫出給定命題公式的真值表 當(dāng)然記住邏輯運算表是至關(guān)重要的 含n個命題變元的命題公式的真值指派有2n 例4命題公式p q r 的成假賦值 p q r 為 Answer 0 1 1 0 0 1 0 0 0 成真賦值 例5 判斷題 命題公式 p q q是永真式 4 邏輯等值的命題公式 兩個命題公式等值討論的是它們之間的一種邏輯關(guān)系 給定兩個命題公式和 是指在任何真值指派下和的邏輯取值都相同 基本等值式除與集合運算性質(zhì)類似的那些外 特別要記住 例6下列 組命題公式是等值的 A A B A B B A B A A A B C B A B B A B D A A B B 由于等值關(guān)系是等價關(guān)系 可以按通常方式進(jìn)行等值演算 特別在等值演算過程中可以使用 等值置換定理 理解命題公式的對偶式 了解對偶原理 設(shè)A和B是命題公式 若A B 則A B 例7設(shè)A B C是任意的命題公式 化簡命題公式 A B C A B C 并將最后結(jié)果僅用 表示 Solution A B C A B C A C A C A C A A C C 例8 1 列出與非聯(lián)結(jié)詞 的運算表 2 僅使用與非聯(lián)結(jié)詞 分別表示 5 命題公式的范式 由于等值關(guān)系是等價關(guān)系 需要考慮其等價類及其代表元 命題公式的范式就是命題公式的標(biāo)準(zhǔn)形式或規(guī)范形式 作為代表元 要求能熟練得出給定命題公式的范式 若A等值于由A中所有命題變元產(chǎn)生的若干個最小項的析取 則把后者稱為A的主析取范式 若A等值于由A中所有命題變元產(chǎn)生的若干個最大項的合取 則把后者稱為A的主合取范式 例9n個命題變元p1 p2 pn的 稱為最小項 其中每個變元與它的否定不能同時出現(xiàn) 但兩者必須一次 A A p q A A p q r 要求掌握利用等值演算法和真值表法求出命題公式的范式 尤其是命題公式的主范式 例10分別利用 1 等值演算法和 2 真值表求命題公式A r q p p q r 的主析取范式和主合取范式 HintA的主合取范式 p q r A的主析取范式為 6 聯(lián)結(jié)詞集合的功能完備性 由等值命題公式知道 1元邏輯運算和2元邏輯運算的個數(shù)共9個 是功能完備聯(lián)結(jié)詞集 進(jìn)而 和 是功能完備的 例11 判斷題 非空1元及2元聯(lián)結(jié)詞集合的個數(shù)為29 1 例12 判斷題 任意最小功能完備聯(lián)結(jié)詞集至少有2個聯(lián)結(jié)詞 例13 填空題 聯(lián)結(jié)詞集合 功能完備的 7 命題邏輯的推理 在進(jìn)行推理時 采用的方法是構(gòu)造法 是一種形式證明方法 只在符號之間進(jìn)行 需要通過一些訓(xùn)練才能熟練掌握 同時 還要掌握兩種間接的構(gòu)造性證明方法 1 反證法 2 CP規(guī)則 條件證明規(guī)則 例14使用CP規(guī)則證明 p q r q r s p q s Proof 1 qP 附加 2 q r s P 3 r sT 1 2 I 4 pP 5 p q r P 6 q rT 4 5 I 7 rT 1 6 I 8 q sCP 例15構(gòu)造下面推理的證明 如果小張和小王去看電影 則小李也去看電影 小趙不去看電影或小張去看電影 小王去看電影 所以 當(dāng)小趙去看電影時 小李也去 Hint令p 小張去看電影 q 小王去看電影 r 小李去看電影 s 小趙去看電影 p q r s p q s r AnyQuestions