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

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

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