數(shù)理邏輯復習題

v1.0可編輯可修改v1.0可編輯可修改PAGEPAGE10v1.0可編輯可修改PAGE一、選擇題1、永真式的否定是（2）(1)永真式(2)永假式(3)可滿足式(4)(1)--(3)均有可能2、設(shè)P：2×2=5，Q：雪是黑的，R：2×4=8，S：太陽從東方升起，則下列真命題為(1)(1)(2)(3)(4)。3、設(shè)P：我聽課，Q：我看小說，則命題R“我不能一邊聽課，一邊看小說”的符號化為=2\*GB2⑵=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷提示：4、下列表達式錯誤的有=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵=3\*GB2⑶=4\*GB2⑷5、下列表達式正確的有=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵=3\*GB2⑶=4\*GB2⑷6、下列聯(lián)接詞運算不可交換的是(3)=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷6、設(shè)D：全總個體域，F(xiàn)（x）：x是花，M(x)：x是人，H(x,y)：x喜歡y，則命題“有的人喜歡所有的花”的邏輯符號化為=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷7、設(shè)L(x)：x是演員，J(x)：x是老師，A(x,y)：x欽佩y，命題“所有演員都欽佩某些老師”的邏輯符號化為=2\*GB2⑵=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷8、謂詞公式中的x是=3\*GB2⑶=1\*GB2⑴自由變元=2\*GB2⑵約束變元=3\*GB2⑶既是自由變元又是約束變元=4\*GB2⑷既不是自由變元又不是約束變元9、下列表達式錯誤的有=1\*GB2⑴=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷10、下列推導錯在=3\*GB2⑶① P② US①③ ES②④ UG③=1\*GB2⑴②=2\*GB2⑵③=3\*GB2⑶④=4\*GB2⑷無11、下列推理步驟錯在=3\*GB2⑶① P② US①③ ES②④ UG③⑤ EG④=1\*GB2⑴①→②=2\*GB2⑵②→③=3\*GB2⑶③→④=4\*GB2⑷④→⑤12、設(shè)個體域為{a,b}，則去掉量詞后，可表示為=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷提示：原式二、填充題1、一個命題含有n個原子命題，則對其所有可能賦值有種。2、n個命題變元可產(chǎn)生個互不等價的極小項，其中，任意兩個不同極小項的合取式為矛盾式（永假式），而全體極小項的析取式為重言式（永真式），n個命題變元可構(gòu)造包括F的不同的主析取范式類別為。3、n個命題變元可產(chǎn)生個互不等價的極大項，其中，任意兩個不同極大項的析取式為重言式（永真式），而全體極小項的合取式為矛盾式（永假式），n個命題變元可構(gòu)造包括T的不同的主合取范式類別為。5、公式的對偶公式為。6、設(shè)P：它占據(jù)空間，Q：它有質(zhì)量，R：它不斷運動，S：它叫做物質(zhì)。命題“占據(jù)空間的，有質(zhì)量的而且不斷運動的叫做物質(zhì)”的邏輯符號可化為。7、P：你努力，Q：你失敗?！俺悄闩?，否則你將失敗”的翻譯為；“雖然你努力了，但還是失敗了”的翻譯為。8、令：x會叫，：x是狗，：x會咬人，則命題“會叫的狗未必會咬人”的符號化為。9、設(shè)P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，則命題“大象比老鼠重”的符號化為。10、令A（x）:x是自然數(shù)，B（x,y）：x小于y，則命題“存在最小的自然數(shù)”的符號化為。三、計算題1、用真值表方法判斷下列公式的類型，并求（3）的主析取范式與主合取范式（1）（PQ）（P∨Q）；（2）（PQ）∧Q；（3）（PQ）∧R；解（1）、（2）和（3）的真值表如表1、表2和表3所示：表1PQPQP∨Q（PQ）（P∨Q）00011011110111011111表2PQPQ（PQ）（PQ）∧Q00011011110100100000表3PQRPQR（PQ）∧R000001010011100101110111111100111010101010100010由上述真值表可知，（1）為永真式，（2）為永假式，（3）為可滿足式。（3）的主析取范式為：；其主合取范式為。2、給定解釋I：D={2，3}，L（x,y）為L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,求謂詞合式公式的真值。解：。3、個體域為{1，2}，求xy（x+y=4）的真值。解：xy（x+y=4）x（（x+1=4）∨（x+2=4））（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4））（0∨0）∧（0∨1）0∧10。四、證明題1、證明下列邏輯恒等式：（1）ＰＱ(ＰＱ)(ＱＰ)證明、用真值表法證明PQPQ（PQ）（QP）FFFTTFTTTTFFFFTT由定義可知，這兩個公式是等價的。（2）P(QP)P(PQ)證明、P(QP)P(QP)P(PQ)P(PQ)P(PQ)P(PQ)（3）證明：左右（4）求證：x(A(x)B(x))xA(x)xB(x)（5）求證：x(P(x)Q(x))∧xP(x)x(P(x)∧Q(x))證明：左x((P(x)Q(x)∧P(x))x((P(x)∨Q(x))∧P(x))x(P(x)∧Q(x))右（6）求證：xy(P(x)Q(y))xP(x)yQ(y)證明：xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)xP(x)yQ(y)（7）求證：證明：左右2、用推理規(guī)則證明下列各結(jié)論是各前提的有效結(jié)論：（1）P→Q，QR，R，SP=>S證明：(1)RP(2)QRPQT（1），（2）(析取三段論)P→QPPT（3），（4）(拒取式)SPP(7)ST（5），（6）(析取三段論)（2）A→(B→C)，C→(DE)，F(xiàn)→(DE),A=>B→F證明：(1)AP(2)A→(B→C)P(3)B→CT（1），（2）(假言推理)(4)BP（附加前提）CT（3），（4）(假言推理)C→(DE)前提DET（5），（6）(假言推理)F→(DE)前提FT（7），（8）(拒取式)B→FCP（3）(P→Q)(R→S)，(Q→W)(S→X)，(WX)，P→R=>P證明：（1）PP（假設(shè)前提）（2）P→RP（3）RT（1），（2）(假言推理)（4）(P→Q)(R→S)P（5）P→QT（4）(化簡律)（6）R→ST（4）(化簡律)（7）QT（1），（5）(假言推理)（8）ST（3），（6）(假言推理)（9）(Q→W)(S→X)P（10）Q→WT（9）(化簡律)（11）S→XT（9）(化簡律)（12）WT（7），（10）(假言推理)（13）XT（8），（11）(假言推理)（14）WXT（12），（13）(合取引入)（15）(WX)P（16）(WX)(WX)T（14），（15）(合取引入)由（16）得出矛盾式，故P為原前提的有效結(jié)論（4）x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))證明(1)xP(x)P(2)P(a)T(1)，ES(3)x(P(x)Q(y)∧R(x))P(4)P(a)Q(y)∧R(a)T(3)，US(5)Q(y)∧R(a)T(2)(4)(假言推理)(6)Q(y)T(5)(化簡律)(7)R(a)T(5)(化簡律)(8)P(a)∧R(a)T(2)(7)(合取引入)(9)x(P(x)∧R(x))T(8)，EG(10)Q(y)∧x(P(x)∧R(x))T(6)(9)(合取引入)（5）證明：①xP(x)P（ 附加前提）②P(e) T①ES③ P④ T③US⑤Q(e) T②④(假言推理)⑥ T⑤EG⑦ CP（6）證明：⑴ P⑵ P⑶ T⑴⑵(假言推理)⑷ T⑵ES⑸ P⑹ T⑸ES⑺ T⑶US⑻ T⑹（附加律）⑼ T⑺⑻(假言推理)⑽ T⑷⑼(合取引入)⑾ T⑽EG⑿ T⑾EG（7）證明：（1）P（假設(shè)前提）（2）T（1）（3）T（2）(化簡律)（4）T（3）ES（5）P（6）T（5）（7）T（6）US（8）T(4).(7)(假言推理)(9)T(2)(化簡律)(10)T(9)US(11)T(8)(10)(合取引入)由（11）得出矛盾式，故為原前提的有效結(jié)論五、將下列命題形式化，并證明結(jié)論的有效性：1、為慶祝九七香港回歸祖國，四支足球隊進行比賽，已知情況如下，問結(jié)論是否有效前提:(1)若A隊得第一，則B隊或C隊獲亞軍;若C隊獲亞軍，則A隊不能獲冠軍;若D隊獲亞軍，則B隊不能獲亞軍;A隊獲第一;結(jié)論:(5)D隊不是亞軍。證明、設(shè)A：A隊得第一;B:B隊獲亞軍;C:C隊獲亞軍;D:D隊獲亞軍;則前提符號化為A（BC），CA，DB，A；結(jié)論符號化為D。本題即證明A（BC），CA，DB，AD。（1）AP（2）A（BC）P（3）BCT（1），（2）(假言推理)（4）CAP（5）CT（1），（4）(拒取式)（6）BT（3），（5）(析取三段論)（7）DBP（8）DT（6），（7）(拒取式)故該結(jié)論有效2、只要今天天氣不好，就一定有考生不能提前進入考場，當且僅當所有考生提前進入考場，考試才能準時進行。所以，如果考試準時進行，那么天氣就好。解設(shè)P：今天天氣好，Q：考試準時進行，A(e)：e提前進入考場，個體域：考生的集合，則命題可符號化為：PxA(x)，xA(x)QQP。(1)PxA(x)P(2)P