《離散數(shù)學及應用》課后習題參考答案孫志海張蒙V1.0[2024-01-10]

內(nèi)容提要教材“孫志海、張蒙.《離散數(shù)學及應用》，西安電子科技大學出版社，2023.5.”的課后習題參考答案。由于水平有限，難免有錯誤，有問題請您協(xié)助反饋（szh@）。

目錄第1章命題邏輯 51.1命題和邏輯聯(lián)結(jié)詞 51.2命題公式及其真值表 141.3命題公式的等價演算 231.4命題公式的范式 301.5聯(lián)結(jié)詞的完備集 431.6命題公式的推理演算 49第2章謂詞邏輯 602.1個體詞、謂詞與量詞 602.2謂詞公式及其解釋 642.3謂詞公式的等價演算 662.4謂詞公式前束范式 682.5謂詞公式的推理演算 70第3章集合與關系 753.1集合及其運算 753.2二元關系及其運算 823.3二元關系的性質(zhì)與閉包 873.4等價關系與劃分 913.5偏序關系與拓撲排序 933.6函數(shù) 953.7集合的等勢與基數(shù) 98第4章圖論 1004.1圖的基本概念 1004.2通路與回路 1024.3圖的連通性 1034.4圖的矩陣表示 1054.5歐拉圖和哈密爾頓圖 1084.6樹 110綜合練習一 114綜合練習二 116

第1章命題邏輯1.1命題和邏輯聯(lián)結(jié)詞一、選擇題1．“4是質(zhì)數(shù)?！保ǎ?。A．是真命題B．是假命題C．是不是命題解析：B質(zhì)數(shù)又稱素數(shù)。一個大于1的自然數(shù)，除了1和它自身外，不能被其他自然數(shù)整除的數(shù)叫做質(zhì)數(shù)；4不是質(zhì)數(shù)。該語句是陳述句，且為假命題。2．“中國有四大發(fā)明。”（）。A．是真命題B．是假命題C．不是命題解析：A該語句是陳述句，且為真命題。3．“只有6是偶數(shù)，3才能是2的倍數(shù)?！保ǎ．是真命題B．是假命題C．不是命題解析：A用p表示6是偶數(shù)，用q表示3是2的倍數(shù)。則該語句可符號化表示為qp，p的真值為1，q的真值為0，根據(jù)蘊涵式的真值情況可知該命題真值為1。4．“π大于2嗎？”（）。A．是命題B．不是命題解析：A該語句是疑問句，不是陳述句，所以不是命題。5．下列選項中，（）不是命題。A．天氣好熱啊!B．后天是陰天。C．2是偶數(shù)。D．地球是方的。解析：AA選項中的語句不是陳述句，所以不是命題。B、C、D的語句均為陳述句且能判斷出真假，所以都是命題。6．下列選項中，（）是命題。A．水燒開了嗎？B．x>1.5。C．再過5000年，地球上就沒有水了。D．請回答這個問題！解析：CA選項中該語句不是陳述句，所以不是命題。x的取值存在不確定性，B選項沒有唯一的真值，所以不是命題。C選項中是陳述句，其真值現(xiàn)在還不知道，但到這一年真正到來時候，該真值可以唯一確定，所以是命題。D選項不是陳述句，不是命題。7．下列選項中，（）不是復合命題？A．劉曉月跑得快，跳得高。B．他一邊吃飯，一邊聽音樂。C．吳穎雖然聰明，但不用功。D．因為天氣冷，所以我穿羽絨服。E．張輝與張南是兄弟。解析：EA選項中該命題可以拆分成兩個簡單的原子命題分別為“劉曉月跑得快”和“劉曉月跳得高”且兩個原子命題間用合取聯(lián)結(jié)詞連接，所以該命題是復合命題。B選項該命題可拆分成兩個原子命題“他一邊吃飯”和“他一邊聽音樂”以合取聯(lián)結(jié)詞連接，所以該命題是復合命題。C選項該命題可以拆分成兩個原子命題“吳穎聰明”，“吳穎（不）用功”以及邏輯聯(lián)結(jié)詞合取詞，所以該命題是復合命題。D選項可以拆分成兩個原子命題“天氣冷”，“我穿羽絨服”，兩個原子命題間具有因果關系，用蘊涵詞連接，所以該命題是復合命題。E中該命題本身為原子命題且無法再拆分成原子命題與邏輯聯(lián)結(jié)詞，所以該命題不是復合命題。8．設p：吳穎用功，q：吳穎聰明，則“吳穎雖然聰明，但不用功?！笨杀硎緸椋ǎ?。A．p∧qB．p∨qC．q∧pD．p解析：C該命題為復合命題，分別用p和q表示兩個原子命題“吳穎用功”和“吳穎聰明”，則“吳穎不用功”可以表示為p?！皡欠f聰明”和“吳穎不用功”是同時成立的，所以用合取聯(lián)結(jié)詞連接，即符號化為q∧p，所以C正確。9．設p：張曉靜愛唱歌，q：張曉靜愛聽音樂，則“張曉靜愛唱歌或愛聽音樂”可符號化為（）。A．p∧qB．p∨qC．pD．p∧q解析：B該命題為復合命題，分別用p和q分別表示兩個原子命題“張曉靜愛唱歌”和“張曉靜愛聽音樂”，則“張曉靜愛唱歌”或“張曉靜愛聽音樂”用析取聯(lián)結(jié)詞連接，即符號化為p∨q，所以B正確。10．“2與5都是質(zhì)數(shù)?！保ǎ?。A．是真命題B．是假命題C．不是命題解析：A該命題為復合命題，其含義是“2是質(zhì)數(shù)且5是質(zhì)數(shù)”。先將其用符號化表示出來，p：2是質(zhì)數(shù)，q：5是質(zhì)數(shù)，則符號化表示為p∧q。由于p和q的真值都為1，所以p∧q真值為1，即該命題為真命題。11．“不但π是無理數(shù)，而且自然對數(shù)的底e也是無理數(shù)?！保ǎ?。A．真命題B．假命題C．不是命題解析：A該命題為復合命題，“不但……而且……”表示兩件事情同時成立，所以對應合取聯(lián)結(jié)詞。符號化表示為，p：π是無理數(shù)，q：自然對數(shù)的底e是無理數(shù)，則符號化表示為p∧q。由于p和q的真值都為1，所以p∧q真值為1，即該命題為真命題。12．“雖然2是最小的質(zhì)數(shù)，但2不是最小的自然數(shù)。”（）。A．真命題B．假命題C．不是命題解析：A“雖然……但……”表示兩件事情同時成立，所以對應合取聯(lián)結(jié)詞。符號化表示，p：2是最小的質(zhì)數(shù)，q：2不是最小的自然數(shù)，則符號化表示為p∧q。由于p和q的真值都為1，所以p∧q真值為1，即該命題為真命題。13．“3是偶質(zhì)數(shù)。”（）。A．是真命題B．是假命題C．不是命題解析：B“3是偶質(zhì)數(shù)”等同于“3是偶數(shù)且3是質(zhì)數(shù)”表示兩件事情同時成立，所以對應合取聯(lián)結(jié)詞。符號化表示為，p：3是偶數(shù)，q：3是質(zhì)數(shù)，則符號化表示為p∧q。由于p的真值為0，q的真值為1，所以p∧q真值為0，即該命題為假命題。14．下列選項中，（）是命題。A．青山湖校區(qū)好美啊！B．后天是陰天嗎？C．2是偶質(zhì)數(shù)D．這里不能吸煙！解析：CA、B和D都不是陳述句，所以不是命題。C選項中是陳述句，且為復合命題。15．下列選項中，（）是命題。A．你喜歡計算機專業(yè)嗎？B．打籃球去！C．種瓜得瓜，種豆得豆。D．這句話是錯的。解析：CA、B都不是陳述句，所以不是命題。D選項中雖然是陳述句，但是真值無法確定。假設該語句真值為“真”，即“這句話是錯的”是真的，則這句話是對的，那么該語句的真值應為“假”，由“真”推出“假”矛盾；反之，也能由“假”推出“真”。所以D的真值無法確定。16．下列選項中，（）不是復合命題。A．吳穎既用功又聰明B．吳穎不僅用功而且聰明C．吳穎雖然聰明，但不用功。D．張輝與王麗是同學E．張輝與王麗都是三好生解析：DA、B、C都可以拆分為兩個簡單命題，p：吳穎用功；q：吳穎聰明，A和B符號化為：p∧q。C符號化為：p∧q。D中語句雖然也有“與”聯(lián)結(jié)詞，但這里用于連接主語中的兩個人的，整個句子仍為一個簡單命題，不是復合命題。E中語句可以拆分成兩個簡單命題，p：張輝是三好生；q：王麗是三好生，符號化為：p∧q。17．已知：p：2+3=5，q：大熊貓產(chǎn)在中國，r：太陽從西邊升起，則(r(p∧q))p的真值為（）。A．1B．0解析：B“p：2+3=5”，則p的真值為1；“q：大熊貓產(chǎn)在中國”，則q真值為1；“r：太陽從西邊升起”，則r真值為0。則p真值為0，所以p∧q的真值為1，r(p∧q)的真值為1，則(r(p∧q))p的真值為0。18．已知p：太陽從西邊升起，q：我不姓孫，則“如果太陽從西邊出來，我就不姓孫?！笨煞柣癁椋ǎ?。A．p∧qB．p∨qC．pqD．p∧q解析：C“如果……就……”對應蘊涵聯(lián)結(jié)詞，所以符號化表示為：pq。二、填空題1．命題：5是有理數(shù)。該命題否定式的真值為______（填0或1）。解析：0因為“5是有理數(shù)”真值為1，所以該命題否定式真值為0。2．命題：2.5是自然數(shù)。該命題否定式的真值為______（填0或1）。解析：1因為“2.5是自然數(shù)”真值為0，所以該命題否定式真值為1。3．命題：5不是無理數(shù)。該命題否定式真值為______（填0或1）。解析：1因為“5不是無理數(shù)”真值為0，所以該命題否定式真值為1。4．命題：12>8。該命題否定式真值為______（填0或1）。解析：0因為“12>8”真值為1，所以該命題否定式真值為0。5．命題：加拿大位于亞洲。該命題否定式真值為______（填0或1）。解析：1因為“加拿大位于亞洲”真值為0，所以該命題否定式真值為1。6．命題：雪不是黑色的。該命題否定式真值為______（填0或1）。解析：0因為“雪不是黑色的”真值為1，所以該命題否定式真值為0。三、判斷題1．“2是無理數(shù)。”是命題。（）解析：√2．“面積相等的兩個三角形全等?！笔钦婷}。（）解析：×3．“3是質(zhì)數(shù)或4是質(zhì)數(shù)?！笔窃用}。（）解析：×該命題是復合命題。4．“你去圖書館嗎？”是命題。（）解析：×疑問句不是命題。5．“2與3都是偶數(shù)?！笔呛唵蚊}。（）解析：×該命題是復合命題。6．“請務必認真學習！”是命題。（）解析：×祈使句不是命題。7．“這朵玫瑰花多么美麗呀！”是命題。（）解析：×感嘆句不是命題。8．“除非2<1，否則3<2?！笔羌倜}。（）解析：√p：2<1，q：3<2；則該命題符號化表示為qp，由于p真值為0，q真值為0，則q真值為1。由于蘊涵聯(lián)結(jié)詞的前件為真后件為假時，蘊含式的真值為假。所以，蘊含式qp真值為0，故該命題為假命題。9．“吸煙請到吸煙室去！”是真命題。（）解析：×非陳述句，不是命題。10．“圓的面積等于半徑的平方乘π?！笔钦婷}。（）解析：√11．“若2+2=4，則地球是靜止不動的?！笔钦婷}。（）解析：×p：2+2=4；q：地球是靜止不動的；則符號化表示為pq，由于p真值為1，q真值為0，所以蘊含式pq真值為0，故該命題為假命題。12．“8是偶數(shù)的充分必要條件是8能被3整除。”是命題。（）解析：√13．“2055年元旦杭州下大雪?！辈皇敲}。（）解析：×是命題，但真值要到2055年才確定。14．“你畢業(yè)了嗎？”是命題。（）解析：×疑問句不是命題。15．“地球上沒有水?！辈皇敲}。（）解析：×是命題，假命題。16．“3是質(zhì)數(shù)或4是質(zhì)數(shù)。”是復合命題。（）解析：√17．“王強和劉威英語四級考試通過了?！笔呛唵蚊}。（）解析：×是復合命題。18．“下雪路滑，他遲到了?！笔呛唵蚊}。（）解析：×是復合命題。19．“2與3都是偶數(shù)。”是真命題：（）解析：×假命題。20．“劉紅與魏新是同學。”是命題。（）解析：√是簡單命題。21．“2<1僅當3<2?！笔羌倜}。（）解析：×p：2<1，p的真值為0；q：3<2，q的真值為0?！?<1僅當3<2?！笨煞柣癁閜q，蘊含式pq前件是0，pq真值為真。22．“這朵花很漂亮！”是命題。（）解析：×感嘆句不是命題。23．“只要2<1，就有3<2?！笔钦婷}。（）解析：√p：2<1，p的真值為0；q：3<2，q的真值為0。“只要2<1，就有3<2。”可符號化為pq，蘊含式pq前件是0，pq真值為真。24．“3是2的倍數(shù)?！笔敲}。（）解析：√假命題。25．“如果2<1，則3≥2?！闭婷}。（）解析：√p：2<1，p的真值為0；q：3≥2，q的真值為1?！叭绻?<1，則3≥2?！笨煞柣癁閜q，蘊含式pq前件是0，pq真值為真。四、綜合題1．當p和q的真值為0，r和s的真值為1時，求下列復合命題的真值。（1）p∨(q∧r)解析：因為p和q的真值為0，r的真值為1。所以q∧r真值為0，所以p∨0的真值為0。（2）(pq)r解析：因為p和q的真值為0，r的真值為1。pq真值為1，所以(pq)r的真值為1。（3）(pr)∧(q∨s)解析：因為p和q的真值為0，r和s的真值為1。所以pr真值為0，q∨s真值為1，所以(pr)∧(q∨s)的真值為0。（4）(r(p∧q))p解析：因為p和q的真值為0，r的真值為1，p真值為1。所以p∧q真值為0，r(p∧q)真值為0，所以(r(p∧q))p的真值為0。（5）r(p∨q∨r)解析：因為p和q的真值為0，r的真值為1。p∨q∨r的真值為1，r的真值為0，所以r(p∨q∨r)的真值為1。（6）(p∧q∧r)((p∨q)r)解析：因為p和q的真值為0，r的真值為1。所以p∧q∧r的真值為0，p∨q的真值為1，(p∨q)r的真值為1，所以(p∧q∧r)((p∨q)r)的真值為0。（7）(p∧q∧r)(p∧q∧r)解析：因為p和q的真值為0，r的真值為1。p∧q∧r的真值為1，p∧q∧r的真值為0，所以(p∧q∧r)(p∧q∧r)的真值為0。（8）(r∧s)(p∧q)解析：因為p和q的真值為0，r和s的真值為1。所以r∧s的真值為0，p∧q的真值為0，所以(r∧s)(p∧q)的真值為1。2．設原子命題p：氣溫在零度以下，q：正在下雪。用p、q和邏輯聯(lián)結(jié)詞將下列復合命題符號化。（1）氣溫在零度以下且正在下雪。解析：符號化表示為p∧q（2）氣溫在零度以下，但不在下雪。解析：符號化表示為p∧q（3）氣溫不在零度以下，也不在下雪。解析：符號化表示為p∧q（4）也許在下雪，也許氣溫在零度以下，也許既下雪，氣溫又在零度以下。解析：符號化表示為(p∨q)∨(p∧q)（5）若氣溫在零度以下，那一定在下雪。解析：符號化表示為pq（6）也許氣溫在零度以下，也許在下雪，但如果氣溫在零度以上就不下雪。解析：符號化表示為(p∨q)∧(pq)（7）氣溫在零度以下是下雪的充分必要條件。解析：符號化表示為pq3．設原子命題p：你的車速超過80km/h，q：你接到一張超速罰單。用p、q和邏輯聯(lián)結(jié)詞將下列復合命題符號化。（1）你的車速沒有超過80km/h。解析：符號化表示為p（2）你的車速超過了80km/h，但沒有接到超速罰單。解析：符號化表示為：p∧q（3）你的車速若超過80km/h，將接到一張超速罰單。解析：符號化表示為：pq（4）你的車速不超過80km/h，就不會接到超速罰單。解析：符號化表示為：pq（5）你接到一張超速罰單，但你的車速沒超過80km/h。解析：符號化表示為：p∧q（6）只要你接到一張超速罰單，你的車速就肯定超過了80km/h。解析：符號化表示為：qp

1.2命題公式及其真值表一、選擇題1．以下選項中，（）符合從左（高）到右（低）的優(yōu)先級次序。A．，()，，∧，∨，B．()，，，∧，∨，C．，∧，∨，，，()D．()，，∧，∨，，解析：D邏輯聯(lián)結(jié)詞的優(yōu)先級順序，()優(yōu)先級最高，其次是否定詞、合取詞∧、析取詞∨、蘊涵詞和等值詞。2．公式(p∧q)r為（）。A．永真式B．永假式C．非永真式的可滿足式解析：C公式(p∧q)r的真值表如表1.2.1所示，由真值表可知，該公式為非永真式的可滿足式。表1.2.1公式(p∧q)r的真值pqrpp∧qr(p∧q)r000101100110010101111011110010000111010001110001111100013．公式(p∧p)(q∧q)為（）。A．永真式B．永假式C．非永真式的可滿足式解析：A公式(p∧p)(q∧q)的真值表如表1.2.2所示，由真值表可知，該公式為永真式。表1.2.2(p∧p)(q∧q)的真值表pqpqp∧pq∧q(p∧p)(q∧q)00110010110001100100111000014．設A為任意的公式，B為永真式，則A∨B為（）。A．永真式B．永假式C．非永真式的可滿足式解析：A由于B是永真式，所以B的真值為1，析取運算中，有一個為1，該析取運算結(jié)果就為1，所以A∨B的真值為1，即A∨B為永真式。5．設p、q均為命題，當（）時，p與q的排斥或也可以寫成p與q的相容或。A．p與q同時為真B．p與q任意取值C．p與q不同時為真解析：Cp與q不同時為真時，可以將p與q的排斥或形式(p∧q)∨(p∧q)寫成相容或形式(p∨q)。6．“7不是無理數(shù)是不對的”可符號化為（）。A．p（其中p：7是無理數(shù)）B．p（其中p：7是無理數(shù)）解析：B這里p：7是無理數(shù)，“7不是無理數(shù)是不對的”可符號化為(p)與p等價。7．借助真值表可知公式(pr)(qr)類型為（）。A．永真式B．永假式C．非永真式的可滿足式解析：C公式(pr)(qr)的真值表如表1.2.3所示，由真值表可知，該公式為非永真式的可滿足式。表1.2.3公式(pr)(qr)的真值pqrrprqr(pr)(qr)000101100101000101001011011110011111010001110110011100108．借助真值表可知公式(p∧(qp))∧(r∧q)為（）。A．永真式B．永假式C．非永真式的可滿足式解析：B公式(p∧(qp))∧(r∧q)的真值表如表1.2.4所示，由真值表可知，該公式為永假式。表1.2.4公式(p∧(qp))∧(r∧q)的真值pqrqp(qp)p∧(qp)r∧q(p∧(qp))∧(r∧q)00010000001100000100100001101010100100001011000011010000111100109．借助真值表可知公式((pq)((p∧q)∨(p∧q)))∨r為（）。A．永真式B．永假式C．非永真式的可滿足式解析：A公式((pq)((p∧q)∨(p∧q)))∨r的真值表如表1.2.5所示，由真值表可知，該公式為永真式。表1.2.5公式((pq)((p∧q)∨(p∧q)))∨r的真值pqr(pq)p∧qp∧q(pq)((p∧q)∨(p∧q))((pq)((p∧q)∨(p∧q)))∨r000000110010001101010111011101111001101110111011110000111110001110．(pq)∨p是永真式，則公式((p∨q)q)∨(p∨q)為（）。A．永真式B．永假式C．非永真式的可滿足式解析：A由于(pq)∨p是永真式，用(p∨q)代替永真式中p即可得到公式((p∨q)q)∨(p∨q)，由代替規(guī)則可知該公式也為永真式。11．設簡單命題p：2+3=5，q：大熊貓產(chǎn)在中國，r：杭州電子科技大學在廣州，則復合命題(p∧q∧r)((p∨q)r)的真值為（）。A．1B．0解析：A公式(p∧q∧r)((p∨q)r)的真值表如表1.2.6所示，由真值表可知，該公式為非永真式的可滿足式。表1.2.6公式(p∧q∧r)((p∨q)r)的真值pqrrp∧q∧rp∨q(p∨q)r(p∧q∧r)((p∨q)r)0001010100100110010101010110011010010101101001101101101111100010由于p的真值為1，q真值為1，r真值為0，對真值表的第7行，所以可知在該解釋下，公式(p∧q∧r)((p∨q)r)的真值為1。12．公式(p∧q)∨(p∧q)的成真賦值為（）。（多選）A．00B．01C．10D．11解析：B、C公式(p∧q)∨(p∧q)的真值表如表1.2.7所示。由公式(p∧q)∨(p∧q)的真值表可知，該公式的成真賦值為：01和10。表1.2.7(p∧q)∨(p∧q)的真值表pqpqp∧qp∧q(p∧q)∨(p∧q)001100001100111001101110000013．公式(pq)與(p∧q)∨(p∧q)共同的成真賦值為（）。（多選）A．00B．01C．10D．11解析：B、C公式(pq)與(p∧q)∨(p∧q)的真值表如表1.2.8所示，公式(pq)與(p∧q)∨(p∧q)共同的成真賦值為：01和10。表1.2.8(pq)與(p∧q)∨(p∧q)的真值表pqpq(pq)p∧qp∧q(p∧q)∨(p∧q)0011000001101011100111011100000014．無論是否下雨，我都去上學?？煞柣癁椋ǎ＃ǘ噙x）p：天下雨，q：我去上學。A．qB．pC．(pq)∧(pq)D．(p∧q)∧(p∧q)解析：A、D15．設p、r為真命題，q、s為假命題，則復合命題(pq)(rs)的真值為（）。A．1B．0解析：B由已知p=1，q=0，r=1，s=0，故r=0，所以pq=0，rs=1，則復合命題(pq)(rs)=0二、判斷題1．命題變項是命題。（）解析：×命題變項在不同的解釋下真值不確定，所以命題變項不是命題。2．pqr寫法符合命題公式規(guī)范。（）解析：×缺少聯(lián)結(jié)詞。3．p(rq寫法符合命題公式規(guī)范。（）解析：×括號不完整。4．可滿足式可分為：永真式和非永真式的可滿足式。（）解析：√根據(jù)可滿足式定義，如果命題公式X不是永假式，則命題公式X是可滿足式。因此，可滿足式可分為永真式和非永真式的可滿足式。三、綜合題1．設p：1+4=5，q：北京是中華人民共和國的首都，r：杭州電子科技大學在廣州，求下列復合命題的真值。（1）(pq)r解析：0由已知p=1，q=1，r=0，所以pq=1，于是(pq)r=0（2）(r(p∧q))p解析：0由已知p=1，q=1，r=0，所以p∧q=1，r(p∧q)=1，p=0，于是(r(p∧q))p=0。（3）r(p∨q∨r)解析：0由已知p=1，q=1，r=0，所以r=1，p∨q∨r=0，于是r(p∨q∨r)=0。（4）(p∧q∧r)((p∨q)r)解析：1由已知p=1，q=1，r=0，所以r=1、(p∧q∧r)=1。(p∨q)=0，(p∨q)r=1，于是(p∧q∧r)((p∨q)r)=1。2．用真值表判斷下列公式的類型。（1）p(p∨q∨r)解析：永真式公式p(p∨q∨r)的真值表如表1.2.9所示，由真值表可知，該公式為永真式。表1.2.9公式p(p∨q∨r)的真值pqrp∨q∨rp(p∨q∨r)0000100111010110111110011101111101111111（2）(pp)q解析：非永真式的可滿足式公式(pp)q的真值表如表1.2.10所示，由真值表可知，該公式為非永真式的可滿足式。表1.2.10公式(pp)q的真值pqpqpp(pp)q001111011010100101110001（3）(qr)∧r解析：永假式公式(qr)∧r的真值表如表1.2.11所示，由真值表可知，該公式為永假式。表1.2.11公式(qr)∧r的真值qrqr(qr)(qr)∧r00100011001001011100（4）(pq)(qp)解析：永真式公式(pq)(qp)的真值表如表1.2.12所示，由真值表可知，該公式為永真式。表1.2.12公式(pq)(qp)的真值pqpqpqqp(pq)(qp)0011111011011110010011100111（5）(p∧r)(p∧q)解析：非永真式的可滿足式公式(p∧r)(p∧q)的真值表如表1.2.13所示，由真值表可知，該公式為非永真式的可滿足式。表1.2.13公式(p∧r)(p∧q)的真值pqrp∧rp∧q(p∧r)(p∧q)000010001010010001011001100001101100110001111100（6）((pq)∧(qr))(pr)解析：永真式公式((pq)∧(qr))(pr)的真值表如表1.2.14所示，由真值表可知，該公式為永真式。表1.2.14公式((pq)∧(qr))(pr)的真值pqrpqqrpr(pq)∧(qr)((pq)∧(qr))(pr)0001111100111111010101010111111110001001101011011101000111111111（7）(pq)(rs)解析：非永真式的可滿足式公式(pq)(rs)的真值表如表1.2.15所示，由真值表可知，該公式為非永真式的可滿足式。表1.2.15公式(pq)(rs)的真值pqrspqrs(pq)(rs)00001110001100001010000111110100111010110001101000111111100001010010011010001101101011001111101100111010011111113．上機實踐：編程輸出由命題變元p，q和r組成的任意命題公式的真值表，并判斷公式的類型。解析：為了創(chuàng)建真值表，我們需要為命題變元p，q和r賦予真值，然后計算公式的真值。假設命題公式是(p∧q)∨(q∧r)，那么真值表如表1.2.16所示：表1.2.16公式(p∧q)∨(q∧r)的真值pqrp∧qq∧r(p∧q)∨(q∧r)000000001000010000011011100000101000110101111111以下是一個使用C++語言創(chuàng)建此真值表的程序：#include<iostream>usingnamespacestd;//定義函數(shù)計算公式的真值boolformula(boolp,boolq,boolr){return(p&&q)||(q&&r);}intmain(){//對于p，q和r的每個可能組合，打印公式的真值for(boolp:{false,true}){for(boolq:{false,true}){for(boolr:{false,true}){cout<<boolalpha<<p<<"|"<<q<<"|"<<r<<"|"<<formula(p,q,r)<<endl;}}}return0;}程序成功編譯運行后輸出結(jié)果如下：false|false|false|falsefalse|false|true|falsefalse|true|false|falsefalse|true|true|truetrue|false|false|falsetrue|false|true|falsetrue|true|false|truetrue|true|true|true

1.3命題公式的等價演算一、選擇題1．設A為含命題變項p、q和r的永真式，則公式A∨((p∧q)r)的類型為（）。A．永真式B．永假式C．非永真式的可滿足式解析：A由于A為永真式，所以A的真值為1，所以公式A∨((p∧q)r)?1∨((p∧q)r)?1（零律）即公式A∨((p∧q)r)為永真式。2．設B為含命題變項p、q和r的永假式，則公式B∧((pq)r)的類型為（）。A．永真式B．永假式C．非永真式的可滿足式解析：B由于B為永假式，所以B的真值為0，所以公式B∧((pq)r)?0∧((pq)r)?0（零律）即公式B∧((pq)r)為永假式。3．設p、q為真命題，r、s為假命題，則復合命題(pr)(qs)的真值為（）。A．1B．0解析：B由于p、q為真命題，r、s為假命題，所以p與q的真值為1，r與s的真值為0，所以pr真值為0，qs真值為1，所以公式(pr)(qs)真值為0。4．如果網(wǎng)絡安全問題不能得到很好的解決，那么歐美乃至世界的和平將失去保障。由此可見（）。A．網(wǎng)絡安全問題沒有得到很好解決。B．只要很好地解決了網(wǎng)絡安全問題，世界和平就可以得到保障。C．因為恐怖主義盛行，歐美的和平已經(jīng)失去保障。D．若世界和平得到了保障，那么網(wǎng)絡安全問題就能得到很好的解決。解析：D先將簡單命題符號化表示：p：網(wǎng)絡安全問題不能得到很好解決；q：歐美乃至世界的和平將失去保障；r：恐怖主義盛行。則原命題符號化表示為：pq。A選項可符號化表示為：p；B選項可符號化表示為：pq；C選項可符號化表示為：r∧q；D選項可符號化表示為：qp。利用命題公式等價演算，pq?p∨q?q∨p，而qp?q∨p，所以可知原命題與D選項中命題等價。5．用等價演算法判斷公式p(p∨q∨r)類型為（）。A．永真式B．永假式C．非永真式的可滿足式解析：Ap(p∨q∨r)?p∨(p∨q∨r)（蘊涵律）?(p∨p)∨q∨r?1∨q∨r?1（結(jié)合律）（否定律）（零律）所以該公式類型為永真式。6．用等價演算法判斷公式(pq)((p∧q)∨(p∧q))的類型為（）。A．永真式B．永假式C．非永真式的可滿足式解析：A(pq)((p∧q)∨(p∧q))?((pq)∧(qp))((p∧q)∨(p∧q))?((p∨q)∧(q∨p))((p∧q)∨(p∧q))?((p∧q)∨(q∧p))((p∧q)∨(p∧q))?((p∧q)∨(q∧p))((p∧q)∨(q∧p))?1所以該公式類型為永真式。7．用等價演算法判斷公式((p∨q)∧pq)的類型為（）。A．永真式B．永假式C．非永真式的可滿足式解析：B((p∨q)∧pq)?((p∧p)∨(q∧p)q)（分配律）?((q∧p)q)?((q∧p)∨q)?(q∧p)∧q?0（否定律）所以該公式類型為永假式。8．用等價演算法判斷公式((pq)∧q)∧r類型為（）。A．永真式B．永假式C．非永真式的可滿足式解析：B((pq)∧q)∧r?((p∨q)∧q)∧r（蘊涵律）?(p∧q)∧q∧r?0（德?摩根律）（否定律）所以該公式類型為永假式。9．用等價演算法判斷公式(p∨q)(p∧r)類型為（）。A．永真式B．永假式C．非永真式的可滿足式解析：C(p∨q)(p∧r)?(p∨q)∨(p∧r)?(p∧q)∨(p∧r)?(p∨p)∧(p∨r)∧(q∨p)∧(q∨r)?(p∨r)∧(q∨p)∧(q∨r)（蘊涵律）（德?摩根律）（分配律）（否定律）所以該公式類型為非永真式的可滿足式。10．(AB)∧(AB)與（）等價。A．ABB．BC．AD．AB解析：C利用等價演算方法：(AB)∧(AB)?(A∨B)∧(A∨B)?A∨(B∧B)?A∨0?A（蘊涵律）（分配律）（否定律）（同一律）11．(p∨q)∧(p∧q)與（）等價。A．(pq)∧(qp)B．(pq)C．(pq)∨(qp)解析：A利用等價演算方法：(p∨q)∧(p∧q)?(p∨q)∧(p∨q)?(p∧p)∨(p∧q)∨(q∧p)∨(q∧q)?(p∧q)∨(q∧p)（德?摩根律）（分配律）（否定律、同一律）A選項中：(pq)∧(qp)?((p∨q)∧(q∨p))?(p∧q)∨(q∧p)（蘊涵律）（德?摩根律）所以可知該命題公式與A選項公式等價。12．只使用命題變項p和q能構造（）個不同的命題公式真值表。A．1B．4C．8D．16解析：D在含有n（n≥1）個命題變項的命題公式X中，共有(2n)n種可能的真值表形式。本題共2個命題變項，共有(22)2=16種不同真值表形式。13．A與（）公式等價。（多選）A．A∨(A∧B)B．A∧(A∨B)C．A∨BD．A∧B解析：AB由吸收律可知A∨(A∧B)?A，A∧(A∨B)?A，所以選項A、B正確。二、判斷題1．AB與A∨B等價。（）解析：√根據(jù)蘊涵律可知AB與A∨B等價。2．AB與(AB)∧(BA)等價。（）解析：√根據(jù)等值律可知AB與(AB)∧(BA)等價。3．等價演算是布爾代數(shù)或邏輯代數(shù)的重要組成部分。（）解析：√4．當命題變項較多時，用真值表法判斷任意兩個命題公式是否等價，工作量可能會比較大。（）解析：√5．A為永真式當且僅當A與1等價，A為永假式當且僅當A與0等價。（）解析：√6．(p∧q)∨(p∧q)與p等價。（）解析：√(p∧q)∨(p∧q)?p∧(q∨q)?p∧1?p，所以(p∧q)∨(p∧q)與p等價。三、綜合題1．用真值表法證明下列的等價式。（1）(A∧B)?A∨B解析：公式(A∧B)和A∨B的真值表如表1.3.1所示，由真值表可知，公式(A∧B)與公式A∨B等價。表1.3.1公式(A∧B)和A∨B的真值ABAB(A∧B)A∨B001111011011100111110000（2）A∧(A∨B)?A解析：公式A∧(A∨B)和A的真值表如表1.3.2所示，由真值表可知，公式A∧(A∨B)和公式A等價。表1.3.2公式A∧(A∨B)和的真值ABA∨BA∧(A∨B)0000011010111111（3）AB?A∨B解析：公式AB和A∨B的真值表如表1.3.3所示，由真值表可知，公式AB與公式A∨B等價。表1.3.3公式AB和A∨B的真值ABAABA∨B00111011111000011011（4）AB?(AB)∧(BA)解析：公式AB和(AB)∧(BA)的真值表如表1.3.4所示，由真值表可知，公式AB與公式(AB)∧(BA)等價。表1.3.4公式AB和(AB)∧(BA)的真值ABABBA(AB)∧(BA)AB001111011000100100111111（5）A∧(B∨C)?(A∧B)∨(A∧C)解析：公式A∧(B∨C)與(A∧B)∨(A∧C)的真值表如表1.3.5所示，由真值表可知，公式A∧(B∨C)與公式(A∧B)∨(A∧C)等價。表1.3.5公式A∧(B∨C)和(A∧B)∨(A∧C)的真值ABCA∧BA∧CA∧(B∨C)(A∧B)∨(A∧C)000000000100000100000011000010000001010111110101111111112．用等價演算法證明下列的等價式。（1）p?(p∧q)∨(p∧q)解析：利用等價演算方法右邊=(p∧q)∨(p∧q)?p∧(q∨q)?p∧1?p（分配律）（否定律）（同一律）所以，p?(p∧q)∨(p∧q)成立。（2）(p∧q)∨(p∧q)?(p∨q)∧(p∧q)解析：利用等價演算方法左邊=(p∧q)∨(p∧q)?(p∨p)∧(p∨q)∧(q∨p)∧(q∨q)?(p∨q)∧(q∨p)?(p∨q)∧(p∧q)（分配律）（否定律、同一律）（德?摩根律、交換律）所以，(p∧q)∨(p∧q)?(p∨q)∧(p∧q)成立。（3）p(qp)?p(pq)解析：利用等價演算方法左邊=p(qp)?p∨(q∨p)?p∨p∨q?1右邊=p(pq)?p∨(p∨q)?1∨q?1（蘊涵律）（交換律）（否定律、零律）（蘊涵律、雙重否定律）（否定律）（零律）所以，p(qp)?p(pq)成立。（4）(pq)?(p∨q)∧(p∧q)解析：利用等價演算方法左邊=(pq)?((pq)∧(qp))?((p∨q)∧(q∨p))?(p∧q)∨(q∧p)?(p∨q)∧(p∨p)∧(q∨q)∧(q∨p)?(p∨q)∧(q∨p)?(p∨q)∧(p∧q)（等值律）（蘊涵律）（德?摩根律）（分配律）（否定律、同一律）（德?摩根律）所以，(pq)?(p∨q)∧(p∧q)成立。（5）(pq)∧(pr)?p(q∧r)解析：利用等價演算方法左邊=(pq)∧(pr)?(p∨q)∧(p∨r)?p∨(q∧r)右邊=p(q∧r)?p∨(q∧r)（蘊涵律）（分配律）（蘊涵律）所以，(pq)∧(pr)?p(q∧r)成立。（6）(pr)∧(qr)?(p∨q)r解析：利用等價演算方法左邊=(pr)∧(qr)?(p∨r)∧(q∨r)?(p∧q)∨r右邊=(p∨q)r?(p∨q)∨r?(p∧q)∨r（蘊涵律）（分配律）（蘊涵律）（德?摩根律）所以，(pr)∧(qr)?(p∨q)r成立。（7）p(qr)?(p∧q)r解析：利用等價演算方法左邊=p(qr)?p∨(q∨r)?(p∨q)∨r?(p∧q)∨r?(p∧q)r（蘊涵律）（結(jié)合律）（德?摩根律）（蘊涵律）所以，p(qr)?(p∧q)r成立。（8）p(qr)?q(pr)解析：利用等價演算方法左邊=p(qr)?p∨(q∨r)?p∨q∨r右邊=q(pr)?q∨(p∨r)?p∨q∨r（蘊涵律）（蘊涵律）所以，p(qr)?q(pr)成立。

1.4命題公式的范式一、選擇題1．p((p∧q)∨(p∧q))標準析取范式為（）。A．m2∨m3B．m1∨m2∨m3C．m0∨m1∨m3D．m0∨m1∨m2∨m3解析：Dp((p∧q)∨(p∧q))?p(p∧(q∨q))?p(p∧1)?pp?p∨p?1因為永真式的標準析取范式包含全部極小項。本題含2個命題變項，共含有22個極小項，因此標準析取范式可表示為：m0∨m1∨m2∨m3。2．(p∨q)(qp)標準析取范式為（）。A．m0B．m2∨m3C．m0∨m2∨m3D．m0∨m1∨m2∨m3解析：C(p∨q)(qp)?(p∨q)∨(q∨p)?(p∨q)∨(q∨p)?(p∧q)∨q∨p?(p∧q)∨(q∧(p∨p))∨(p∧(q∨q))?(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)?(p∧q)∨(p∧q)∨(p∧q)?m00∨m10∨m11（二進制下標）?m0∨m2∨m3（十進制下標）3．(pr)∧r∧q標準析取范式為（）。A．0B．m0∨m1∨m2∨m3∨m4C．m2∨m3∨m4D．m0∨m1∨m2∨m4解析：A(pr)∧r∧q?(p∨r)∧r∧q?p∧r∧r∧q?0永假式的標準析取范式為命題常項0。4．(pq)∨r可用{，∧}表示為（）。A．p∧(q∧r)B．p∧q∧rC．p∨q∨rD．(p∧q∧r)解析：D(pq)∨r?p∨q∨r?(p∧q∧r)所以，(pq)∨r可用{，∧}表示為(p∧q∧r)。5．(pq)∧r可用{，∨}表示為（）。A．(p∨q)∧rB．((p∨q)∨r)C．(p∨q)∨rD．p∨q∨r解析：B(pq)∧r?((p)∨q)∧r?(p∨q)∧r?((p∨q)∨r)所以，(pq)∧r可用{，∨}表示為((p∨q)∨r)。6．用等價演算等方法求解實際問題。討論派遣方案：某公司派小李或小張去上海出差。若派小李去，則小趙要加班。若派小張去，小王也得去。小趙沒加班。問公司該如何派遣？令p：派小李去上海。q：派小張去上海。r：小趙要加班。s：派小王去上海。命題公式A=(p∨q)∧(p→r)∧(q→s)∧(r)，則（）。A．派小李去上海B．派小張去上海C．派小王去上海D．派小張、小王去上海解析：D用等價演算法求命題公式A的成真賦值：(p∨q)∧(p→r)∧(q→s)∧(r)?(p∨q)∧(p∨r)∧(q∨s)∧(r)?(p∨q)∧(p∨r)∧(r)∧(q∨s)?(p∨q)∧((p∧r)∨(r∧r))∧(q∨s)?(p∨q)∧(p∧r)∧(q∨s)?((p∨q)∧(p∧r))∧(q∨s)?((p∧p∧r)∨(q∧p∧r))∧(q∨s)?(q∧p∧r)∧(q∨s)?(q∧p∧r∧q)∨(q∧p∧r∧s)?q∧p∧r∧s?p∧q∧r∧s?m0101（二進制下標）?m5（十進制下標）所以，化簡結(jié)果為主析取范式，對應的成真賦值為0101，即只有一個派遣方案為：派小張和小王一起去上海出差。7．永假式（矛盾式）的標準析取范式為（）。A．1B．0C．m0∨m1∨m2D．m0∧m1∧m2解析：B8．設公式X含命題變項p、q和r，X的標準合取范式為M0∧M2∧M3∧M5，則X的標準析取范式為（）。A．m0∨m2∨m3∨m5B．m0∧m2∧m3∧m5C．M1∨M4∨M6∨M7D．m1∨m4∨m6∨m7解析：DX含3個命題變項，所有可能極小項為：m0、m1、m2、m3、m4、m5、m6、m7，由于X的標準合取范式為M0∧M2∧M3∧M5，所以X的標準析取范式為m1∨m4∨m6∨m7。9．要設計由1個燈泡和3個開關A、B、C組成的電路，要求僅在下述4種情況下燈亮：（1）C的扳鍵向上，A、B的扳鍵向下。（2）A的扳鍵向上，B、C的扳鍵向下。（3）B、C的扳鍵向上，A的扳鍵向下。（4）A、B的扳鍵向上，C的扳鍵向下。設X為1表示燈亮，p、q、r分別表示A、B、C的扳鍵向上，則X的標準析取范式為（）。A．m0∨m3∨m4∨m6B．M1∨M3∨M4∨M6C．m1∧m3∧m4∧m6D．m1∨m3∨m4∨m6解析：D（1）C的扳鍵向上，A、B的扳鍵向下。對應極小項p∧q∧r（2）A的扳鍵向上，B、C的扳鍵向下。對應極小項p∧q∧r（3）B、C的扳鍵向上，A的扳鍵向下。對應極小項p∧q∧r（4）A、B的扳鍵向上，C的扳鍵向下。對應極小項p∧q∧rX的標準析取范式表示為：(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)?m001∨m011∨m100∨m110（二進制下標）?m1∨m3∨m4∨m6（十進制下標）10．設p與q為真命題，r與s為假命題，則復合命題(pr)(qs)的真值為（）。A．1B．0解析：Bp與q的真值為1，r與s的真值為0。(pr)真值為0，(qs)真值為1，所以(pr)(qs)真值為0。11．設p與q為命題變項，則(pq)的成真賦值為（）。（多選）A．00B．01C．10D．11解析：B、C將(pq)化為標準合取范式：(pq)?((p)q)∧(q(p))?((p)∨q)∧(q∨(p))?(p∨q)∧(q∨p)?(p∨q)∧(p∨q)?M00∨M11（標準合取范式，二進制下標，成假賦值為00、11）?M0∨M3（標準合取范式，十進制下標）?m1∨m2（標準析取范式，十進制下標）?m01∨m10（標準合取范式，二進制下標，成真賦值為01、10）12．永真式的標準合取范式為（）。A．1B．0解析：A二、綜合題1．下列命題公式哪些是析取范式，哪些是合取范式？（1）(p∧q)∨(q∧r)解析：析取范式（2）(p∨q)∧(p∨q)解析：合取范式（3）(p∧r)∨q解析：析取范式（4）(p∨q)∧q解析：合取范式（5）p∨q解析：既是析取范式又是合取范式（6）p∧q∧r解析：既是析取范式又是合取范式（7）p解析：既是析取范式又是合取范式（8）q解析：既是析取范式又是合取范式（9）1解析：既是析取范式又是合取范式（10）0解析：既是析取范式又是合取范式2．在下列由3個命題變項p、q和r組成的命題公式中，哪些是標準析取范式，哪些是標準合取范式？（1）(p∧q∧r)∨(p∧q∧r)解析：標準析取范式（2）(p∨q∨r)∧(p∨q∨r)解析：標準合取范式（3）(p∧q∧r)∨q解析：既不是標準析取范式也不是標準合取范式，是析取范式。（4）(p∨q)∧(p∨r)∧(q∨r)解析：既不是標準析取范式也不是標準合取范式，是合取范式。（5）p∨q∨r解析：標準合取范式（6）p∧q∧r解析：標準析取范式（7）1解析：標準合取范式（8）0解析：標準析取范式3．找出一個只含命題變項p、q和r的命題公式，當p和q為真而r為假時，命題公式為真，否則為假。解析：p∧q∧r當命題公式的標準析取范式只含有1個極小項p∧q∧r時，符合題目要求。4．找出一個只含命題變項p、q和r的命題公式，在p、q和r中恰有兩個為假時，命題公式為真，否則為假。解析：(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)當命題公式的標準析取范式只含有3個極小項(p∧q∧r)、(p∧q∧r)、(p∧q∧r)時，符合題目要求。5．利用等價演算法求下列命題公式的標準析取范式，并求其成真賦值。（1）(pq)(q∨p)解析：00、10、11利用等價演算方法求標準析取范式(pq)(q∨p)?(p∨q)∨(q∨p)?(p∧q)∨(q∨p)?(p∧q)∨(q∧(p∨p))∨(p∧(q∨q))?(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)?(p∧q)∨(p∧q)∨(p∧q)所以，命題公式(pq)(q∨p)的成真賦值為00、10、11（2）(pq)∧q∧r解析：無成真賦值利用等價演算方法求標準析取范式(pq)∧q∧r?(p∨q)∧q∧r?(p∧q)∧q∧r?0所以，命題公式(pq)∧q∧r為永假式，它的標準析取范式為0，沒有成真賦值。（3）(p∨(q∧r))(p∨q∨r)解析：永真式利用等價演算方法求標準析取范式(p∨(q∧r))(p∨q∨r)?(p∨(q∧r))∨(p∨q∨r)?(p∧(q∨r))∨(p∨q∨r)?(p∧q)∨(p∧r)∨(p∨q∨r)?(p∧q∧(r∨r))∨(p∧r∧(q∨q))∨(p∨q∨r)?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧qr)∨(p∧q∧r)∨(p∧qr)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧qr)∨(p∧q∧r)?m000∨m001∨m010∨m011∨m100∨m101∨m110∨m111命題公式(p∨(q∧r))(p∨q∨r)為永真式。6．利用等價演算法求下列命題公式的標準合取范式，并求其成假賦值。（1）(pq)∧p解析：成假賦值為00、01、10、11利用等價演算方法求標準合取范式(pq)∧p?(p∨q)∧p?(p∧q)∧p?0命題公式(pq)∧p為矛盾式，標準合取范式包含全部極大項，標準合取范式為：(p∨q)∧(p∨q)∧(p∨q)∧(p∨q)?M00∨M01∨M10∨M11（2）(p∧q)∨(p∨r)解析：100利用等價演算方法求標準合取范式(p∧q)∨(p∨r)?((p∧q)∨p)∨r?((p∨p)∧(q∨p))∨r?p∨q∨r?M100所以，命題公式(p∧q)∨(p∨r)的成假賦值為100。（3）(p(p∨q))∨r解析：永真式，無成假賦值。利用等價演算方法求標準合取范式(p(p∨q))∨r?(p∨(p∨q))∨r?1命題公式(p(p∨q))∨為永真式，標準合取范式為1，沒有成假賦值。7．利用真值表法求下列命題公式的標準析取范式和標準合取范式。（1）(pq)解析：公式(pq)的真值表如表1.4.1所示，由真值表可知，公式(pq)的成真賦值為：10，所以該公式的標準析取范式為：m10?p∧q。公式(pq)的成假賦值為：00、01、11，對應的標準合取范式為：M00∧M01∧M11?(p∨q)∧(p∨q)∧(p∨q)表1.4.1(pq)的真值表pqpq(pq)0010011010011110（2）(p∨q)(pq)解析：公式(p∨q)(pq)的真值表如表1.4.2所示，由真值表可知，公式(p∨q)(pq)的成真賦值為01、10，所以該公式的標準析取范式為：m01∨m10?(p∧q)∨(p∧q)公式(p∨q)(pq)的成假賦值為：00、11，所以該公式的標準合取范式為：M00∧M11?(p∨q)∧(p∨q)表1.4.2(p∨q)(pq)的真值表pqp∨qpq(p∨q)(pq)00100011111001111100（3）(p∧q)r解析：公式(p∧q)r的真值表如表1.4.3所示，由真值表可知，公式(p∧q)r的成真賦值為：000、001、010、011、100、101、111，所以該公式的標準析取范式為：m000∨m001∨m010∨m011∨m100∨m101∨m111?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)公式(p∧q)r的成假賦值為：110，所以該公式的標準合取范式為：M110?p∨q∨r表1.4.3(p∧q)r的真值表pqrp∧q(p∧q)r0000100101010010110110001101011101011111（4）(p(q∧r))∧(p(q∧r))解析：公式(p(q∧r))∧(p(q∧r))的真值表如表1.4.4所示，由真值表可知，公式(p(q∧r))∧(p(q∧r))的成真賦值為000、111，所以該公式的標準析取范式為：m000∨m111?(p∧q∧r)∨(p∧q∧r)公式(p(q∧r))∧(p(q∧r))的成假賦值為：001、010、011、100、101、110，所以該公式的標準合取范式為：M001∧M010∧M011∧M100∧M101∧M110?(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)表1.4.4(p(q∧r))∧(p(q∧r))的真值表pqrp(q∧r)p(q∧r)(p(q∧r))∧(p(q∧r))0001110011000101000111001000101010101100101111118．求下列命題公式的標準析取范式，再根據(jù)標準析取范式求標準合取范式。（1）(p∧q)∨r解析：利用等價演算方法，公式(p∧q)∨r的標準析取范式為：(p∧q)∨r?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)?m001∨m011∨m101∨m110∨m111?m1∨m3∨m5∨m6∨m7所以，則該公式標準合取范式為：M0∧M2∧M4?M000∧M010∧M100?(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)（2）(pq)r解析：根據(jù)真值表1.4.5，公式(pq)r的標準析取范式為：m1∨m2∨m3∨m4∨m5∨m7?m001∨m010∨m011∨m100∨m101∨m111?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)則該公式的標準合取范式的極大項下標取值分別為000和110，所以該公式的標準合取范式為：M0∧M6?M000∧M110?(p∨q∨r)∧(p∨q∨r)表1.4.5(pq)r的真值表pqrpq(pq)r00010001110100101101100011010111010111119．求下列命題公式的標準合取范式，再根據(jù)標準合取范式求標準析取范式。（1）(p∧q)q解析：利用等價演算方法，公式(p∧q)q的標準合取范式為(p∧q)q?(p∧q)∨q?p∨q∨q?1所以，公式(p∧q)q為永真式，標準合取范式為1。對應的標準析取范式為：(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)（2）(pq)∧(qr)解析：利用等價演算方法，公式(pq)∧(qr)的標準合取范式為(pq)∧(qr)?(p∨q)∧(q∨r)?(p∨q∨(r∧r))∧((p∧p)∨q∨r)?(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)?(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)?M010∧M100∧M101∧M110則標準析取范式的極小項下標分別為000、001、011和111，所以標準析取范式為：m000∨m001∨m011∨m111?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)（3）(rp)∧p∧q解析：利用等價演算方法，公式(rp)∧p∧q的標準合取范式為：(rp)∧p∧q?(r∨p)∧p∧q?(r∧p)∧p∧q?0所以，該公式的標準合取范式為：M000∧M001∧M010∧M011∧M100∧M101∧M110∧M111標準析取范式為：010．已知公式X含3個命題變項p、q和r，并且它的成真賦值為000、011、110，求X的標準合取范式和標準析取范式。解析：公式X的標準析取范式為：m000∨m011∨m110?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)公式X的標準合取范式為：M001∧M010∧M100∧M101∧M111?(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)11．已知公式X含3個命題變項p、q和r，并且它的成假賦值為010、011、110、111，求X的標準析取范式和標準合取范式。解析：公式X的標準合取范式為：M010∧M011∧M110∧M111?(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)公式X的標準析取范式為：m000∨m001∨m100∨m101?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)12．已知公式X含n個命題變項p1，p2，?，pn，并且無成假賦值，求X的標準合取范式。解析：1公式X含n個命題變項p1，p2，?，pn，并且無成假賦值，則公式X為永真式，由于永真式無法由極大項的合取式來表示，所以該公式的標準合取范式為命題常項1。13．用標準析取范式判斷下列公式是否等價。（1）(pq)r與q(pr)解析：公式(pq)r的標準析取范式為：(pq)r?(p∨q)∨r?(p∧q)∨r?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)?m001∨m011∨m100∨m101∨m111公式q(pr)的標準析取范式為：?q∨(p∨r)?p∨q∨r?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)?m000∨m001∨m010∨m011∨m100∨m101∨m111對比兩個公式的標準析取范式可知，(pq)r與q(pr)不等價。（2）(p∧q)與(p∨q)解析：公式(p∧q)的標準析取范式為(p∧q)?p∨q?(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)?(p∧q)∨(p∧q)∨(p∧q)?m00∨m01∨m10公式(p∨q)的標準析取范式為(p∨q)?p∧q?m00對比兩個公式的標準析取范式可知，(p∧q)與(p∨q)不等價。14．用標準合取范式判斷下列公式是否等價。（1）p(qr)與(p∧q)∨r解析：公式p(qr)的標準合取范式為p(qr)?p∨(q∨r)?p∨q∨r公式(p∧q)∨r的標準合取范式為(p∧q)∨r?p∨q∨r對比兩個公式的標準合取范式可知，p(qr)與(p∧q)∨r等價。（2）p(qr)與(pq)r解析：公式p(qr)的標準合取范式為p(qr)?p∨(q∨r)?p∨q∨r?M110公式(pq)r的標準合取范式為(pq)r?(p∨q)∨r?(p∧q)∨r?(p∨r)∧(q∨r)?(p∨r∨(q∧q))∧(q∨r∨(p∧p))?(p∨r∨q)∧(p∨r∨q)∧(q∨r∨p)∧(q∨r∨p)?(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)?(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)?(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)?M000∧M010∧M110對比兩個公式的標準合取范式可知，p(qr)與(pq)r不等價。

1.5聯(lián)結(jié)詞的完備集一、綜合題1．只使用命題變項p和q能構造多少不同的命題公式真值表？解析：只使用命題變項p和q可以構造(22)2=16種不同的命題公式真值表。2．將下列公式化成與之等價且僅含{，∧，∨}中聯(lián)結(jié)詞的公式。（1）(p(q(q∧r)))解析：(p(q(q∧r)))?(p∨((q(q∧r))∧((q∧r)q)))?(p∨((q∨(q∧r))∧((q∧r)∨q)))（2）(p∧q)∨r解析：(p∧q)∨r?(p∨r)∧(q∨r)（3）p(qr)?(p(qr))∧((qr)p)?(p((qr)∧(rq)))∧(((qr)∧(rq))p)?(p∨((q∨r)∧(r∨q)))∧(((q∨r)∧(r∨q))∨p)3．將下列公式化成與之等價且僅含{，∧}中聯(lián)結(jié)詞的公式。（1）p∨q∨r解析：p∨q∨r?(p∧q∧r)（2）(pr)∧q解析：(pr)∧q?(pr)∧(rp)∧q?(p∨r)∧(r∨p)∧q?(p∧r)∧(r∧p)∧q?((p∧r))∧((p∧r))∧q（3）(p(q∧r))∨p解析：(p(q∧r))∨p?(p∨(q∧r))∨p?(p∧(q∧r))∨p?((p∧(q∧r))∧p)4．將下列公式化成與之等價且僅含{，∨}中聯(lián)結(jié)詞的公式。（1）(p∨q)∧r解析：(p∨q)∧r?((p∨q)∨r)（2）(p(q∧p))∧q∧r解析：(p(q∧p))∧q∧r?(p(q∧p))∧q∧r?(p∨(q∧p))∧q∧r?(p∨(q∨p))∧q∧r?((p∨(q∨p))∨q∨r)（3）p∧q∧r解析：p∧q∧r?(p∨q∨r)5．將下列公式化成與之等價且僅含{，}中聯(lián)結(jié)詞的公式。（1）(p∧q)∨r解析：(p∧q)∨r?(p∨q)∨r?(p∨q)r?(p(q))r（2）(pq)∧r解析：(pq)∧r?((pq)∨r)?((pq)(r))（3）(p∧q)r解析：(p∧q)r?((p∧q)r)∧(r(p∧q))?((p∨q)r)∧(r(p∨q))?((p(q))r)∧(r(p∨q))?((p(q))r)∧(r(p(q)))?(((p(q))r)∨(r(p(q))))?(((p(q))r)((r(p(q)))))6．從表1.5.2中找出與下列公式等價的真值函數(shù)。表1.5.1p↑q、p↓q、p⊕q、(p∧q)∨(p∧q)與(pq)的真值pqp↑qp↓qp⊕q(p∧q)∨(p∧q)(pq)0011000011011010101111100000表1.5.22元真值函數(shù)（教材中的表1.5.2）stHHHHHHHH0000000000010000111110001100111101010101stHHHHHHHH0011111111010000111110001100111101010101先寫出各個公式的真值表，如表1.5.1，再與表1.5.2對照，即可找到對應的函數(shù)。（1）p↑q解析：H公式真值表如表1.5.1中第3列所示，與表1.5.2中的H14（2）p↓q解析：H公式真值表如表1.5.1中第4列所示，與表1.5.2中的H8（3）p⊕q解析：H公式真值表如表1.5.1中第5列所示，與表1.5.2中的H6（4）(p∧q)∨(p∧q)解析：H公式真值表如表1.5.1中第6列所示，與表1.5.2中的H6（5）(pq)解析：H公式真值表如表1.5.1中第7列所示，與表1.5.2中的H27．在以下各聯(lián)結(jié)詞完備集中各求一個公式與A=(pq)∧r等價。（1）S1={，∧，∨}解析：如公式(p∨q)∧r，結(jié)果不唯一。(pq)∧r?(p∨q)∧r（2）S2={，∧}解析：如公式(p∧q)∧r，結(jié)果不唯一。(pq)∧r?(p∨q)∧r?(p∧q)∧r（3）S3={，∨}解析：如公式((p∨q)∨r)，結(jié)果不唯一。(pq)∧r?(p∨q)∧r?((p∨q)∨r)（4）S4={，}解析：如公式((pq)r)，結(jié)果不唯一。(pq)∧r?(pq)∧r?((pq)∨r)?((pq)r)（5）S5={↑}解析：如公式(((((p↑p)↑(p↑p))↑((q↑q)↑(q↑q)))↑r)↑((((p↑p)↑(p↑p))↑((q↑q)↑(q↑q)))↑r))，結(jié)果不唯一。(pq)∧r?(p∨q)∧r?((p∧p)∨(q∧q))∧r?((p↑p)∨(q↑q))∧r?((p↑p)∨(q↑q))∧r?((p↑p)∧(q↑q))∧r?(((p↑p))∧((q↑q)))∧r?((((p↑p)∧(p↑p)))∧(((q↑q)∧(q↑q))))∧r?(((p↑p)↑(p↑p))∧((q↑q)↑(q↑q)))∧r?(((p↑p)↑(p↑p))↑((q↑q)↑(q↑q)))∧r?((((p↑p)↑(p↑p))↑((q↑q)↑(q↑q)))∧r)?((((p↑p)↑(p↑p))↑((q↑q)↑(q↑q)))↑r)?(((((p↑p)↑(p↑p))↑((q↑q)↑(q↑q)))↑r)∧((((p↑p)↑(p↑p))↑((q↑q)↑(q↑q)))↑r))?(((((p↑p)↑(p↑p))↑((q↑q)↑(q↑q)))↑r)↑((((p↑p)↑(p↑p))↑((q↑q)↑(q↑q)))↑r))（6）S6={↓}解析：如公式((((p↓p)↓(q↓q))↓((p↓p)↓(q↓q)))↓(((p↓p)↓(q↓q))↓((p↓p)↓(q↓q))))↓(r↓r)，結(jié)果不唯一。(pq)∧r?(p∨q)∧r?((p∨p)∨(q∨q))∧r?((p↓p)∨(q↓q))∧r?((p↓p)∨(q↓q))∧r?((p↓p)↓(q↓q))∧r?(((p↓p)↓(q↓q))∨((p↓p)↓(q↓q)))∧r?(((p↓p)↓(q↓q))↓((p↓p)↓(q↓q)))∧r設A表示(((p↓p)↓(q↓q))↓((p↓p)↓(q↓q)))，則A∧r?(A∨r)?(A)↓(r)?((A∨A))↓((r∨r))?(A↓A)↓(r↓r)?((((p↓p)↓(q↓q))↓((p↓p)↓(q↓q)))↓(((p↓p)↓(q↓q))↓((p↓p)↓(q↓q))))↓(r↓r)8．一個排隊線路，輸入為A，B，C，輸出為FA，F(xiàn)B，F(xiàn)C。在同一時間只能輸出一個信號；當同時有2個或2個以上信號申請輸出時，按A，B，C的順序輸出。試寫出FA，F(xiàn)B，F(xiàn)C在聯(lián)結(jié)詞完備集{，∧}中的表達式。解析：設p：A輸入，q：B輸入，r：C輸入，根據(jù)輸出規(guī)則，可得該題的真值表如表1.5.3所示。表1.5.3第8題的真值表pqrFAFBFC000000001001010010011010100100101100110100111100根據(jù)真值表1.5.3，可得：FA?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)?((p∧q)∧(r∨r))∨((p∧q)∧(r∨r))?(p∧q)∨(p∧q)?p∧(q∨q)?pFB?(p∧q∧r)∨(p∧q∧r)?(p∧q)∧(r∨r)?p∧qFC?p∧q∧r

1.6命題公式的推理演算一、選擇題1．用等價演算法判斷推理是否正確。（）若今天不下雨，我就不去圖書館。今天下雨。所以，我去圖書館。p：今天下雨；q：我去圖書館。A．推理正確B．推理不正確解析：B推理形式結(jié)構為：{(﹁pq)，p}?q，即只需要證明(﹁pq)∧pq為永真式，則推理正確。利用等價演算法：(﹁pq)∧pq?(p∨q)∧pq?pq結(jié)果不是永真式，所以推理不正確。2．用等價演算法判斷推理是否正確。（）若今天不是星期六，明天就不是星期一。明天是星期一。所以，今天是星期六。p：今天是星期六；q：明天是星期一。A．推理正確B．推理不正確解析：A推理形式結(jié)構為：{(pq)，q}?p，即只需要證明(pq)∧qp為永真式，則推理正確。利用等價演算法：(﹁pq)∧qp?(p∨q)∧qp?(p∨q)∧qp?((p∧q)∨(q∧q))p?(p∧q)p?(p∧q)∨p?(p∨q)∨p?1結(jié)果是永真式，所以推理正確。3．用標準析取范式法判斷推理是否正確。（）n不是偶數(shù)或m不是奇數(shù)。n是偶數(shù)。所以，m不是奇數(shù)。p：n是偶數(shù)；q：m是奇數(shù)。A．推理正確B．推理不正確解析：A推理形式結(jié)構為：{(p∨q)，p}?q，即只需要證明(p∨q)∧pq為永真式，則推理正確。利用等價演算法：(p∨q)∧pq?((p∨q)∧p)∨q?((p∧q)∨p)∨q?(p∧q)∨p∨q?(p∧q)∨(p∧(q∨q))∨(q∧(p∨p))?(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)?(p∧q)∨(p∧q)∨(p∧q)∨(p∧q)?m00∨m01∨m10∨m11?1結(jié)果是永真式，所以推理正確。4．用標準析取范式法判斷推理是否正確