離散數學-命題邏輯

《離散數學-命題邏輯》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、什么是數理邏輯？用數學方法來研究推理的規(guī)律稱為數理邏輯。這里所指的數學方法，就是引進一套符號體系的方法，所以數理邏輯又稱為符號邏輯，它是從量的側面來研究思維規(guī)律的學科。命題邏輯謂詞邏輯第一章數理邏輯一命題邏輯命題及其表示法聯結詞命題公式與翻譯真值表與等價式重言式與蘊含式對偶與范式推理理論二謂詞邏輯謂詞的概念與表示命題函數與量詞謂詞公式與翻譯變元的約束謂詞演算的等價式與蘊含式前束范式謂詞演算的推理理論本章作業(yè)關于命題邏輯問題：傳說中有一個住在邊遠小鎮(zhèn)上的剃頭匠,這個剃頭匠只能給那些不自己剃須的人刮胡子,他能給自己剃須嗎?問題:邊遠村莊的每個人要么總說真話,那么總說謊.對旅游者的問題,村民要么回答

2、“是”,要么回答“否”.假定你在這一地區(qū)旅游,走到一個岔路口,一條岔路通向你想去的遺址,一條岔路通向叢林深處,此時恰好有一村民站在岔路口,問村民什么樣的一個問題就能決定走哪條路?>>>關于命題邏輯問題：甲、乙、丙、丁四人參加拳擊比賽，如果甲獲勝，則乙失敗；如果丙獲勝，則乙也獲勝；如果甲不獲勝，則丁不失敗。能否推出結論：如果丙獲勝，則丁不失敗問題：設計一個控制客廳照明的電路，使得分別裝在臥室和客廳的兩只開關都能控制照明。判斷：通過概念對事物是否具有某種屬性進行肯定或否定的回答。一、命題及其表示1、命題的定義命題：指能表達判斷的陳述句。一個命題，總是具有一個“值”，稱為真值。真值只有“真”和“假”

3、兩種，記作True（真）和False（假），分別用符號T和F表示。只有具有確定真值的陳述句才是命題，一切沒有判斷內容的句子，無所謂是非的句子，如感嘆句，疑問句，祈使句等都不能作為命題。2、命題類型命題有兩種類型：原子命題：不能分解為更簡單的陳述語句的命題。復合命題：由聯結詞，標點符號和原子命題復合構成的命題。所有這些命題，都應具有確定的真值。聯結詞的例子，如：“并且”、“或者”、“如果…則…”等。例：判斷下面的句子是否為命題。（1）中國人民是偉大的。（2）雪是黑的。（3）1+101=110（4）別的星球上有生物。（5）全體立正。（6）明天是否開大會？（7）天氣多好?。。?）我正在說謊。（9）我

4、學英語，或者我學日語。3、命題的表示在本課程中，我們將使用大寫字母A、B、…、P、Q、…，或帶下標的大寫字母，或方括號括起來的數字。來表示命題。如：P：太陽從西邊出來。[12]：太陽從西邊出來。即命題既可用字母也可用數字來表示命題標識符表示命題的符號。命題常量一個具體的命題。命題變元命題標識符只表示任意命題的位置。注：命題變元不是命題。指派當命題變元P用一個特定的命題取代時，P才能確定真值，稱對P進行指派。命題邏輯與程序語言的對應關系命題標識符程序語言標識符。命題常量邏輯常量。命題變元邏輯變量。指派給邏輯變量賦值。二、命題聯結詞在自然語言中，常常使用“或者”，“并且”，“不是”等一些聯結詞，對

5、于這種聯結詞的使用，一般沒有很嚴格的定義。在數理邏輯中，復合命題是由原子命題與聯結詞組合而成，聯結詞不僅是復合命題中的重要組成部分，而且起到了運算符的作用。為了便于書寫和進行推理演算，必須對聯結詞作出明確規(guī)定并符號化。下面介紹各個聯結詞。1）否定定義：設P為一命題，P的否定是一個新的命題，記作：?P。若P為T，?P為F；若P為F，?P為T?！?”是一元運算。其運算規(guī)則表如下：TFFT?PP例：P：太陽從東邊出來?P：?P：太陽不從東邊出來注意：“?”表示命題的否定。2）合取定義：兩個命題P和Q的合取是一個復合命題，記作P∧Q。當且僅當P、Q同時為T時，P∧Q為T，其他情況下P∧Q的真值都是F。

6、“合取”是一個二元運算，稱為“與”運算。其運算法則表如下：聯結詞“∧”的運算法則：FFFTP∧QFFTFFTTTQP注：合取的概念與自然語言中的“并且”意義相似。例：P：北京是中國的首都。Q：北京是一個故都。P∧Q：P∧Q：北京是中國的首都并且是一個故都。3）析取定義：兩個命題P和Q的析取是一個復合命題，記作P∨Q。當且僅當P、Q同時為F時，P?Q的真值為F，否則P∨Q的真值為T。注：從析取的定義可以看到，聯結詞?與漢語中的“或者”的意義類似?！拔鋈　币彩嵌\算，稱為“或”運算，其運算法則表如下：聯詞“∨”的運算法則：注意：“∨”為可兼或FTTTP∨QFFTFFTTTQP例：P：成都是中國的

7、首都。Q：成都是一個故都。P∨Q：P∨Q：成都是中國的首都或者是一個故都。4）條件定義：給定兩個命題P和Q，其條件命題是一個復合命題，記作P→Q,讀作：“如果P，那么Q”或“若P則Q”。當且僅當P的真值為T，Q的真值為F時，P→Q的真值為F，否則P→Q的真值為T。我們稱P為前件，Q為后件。聯給詞“→”的運算法則：TTFTP→QFFTFFTTTQP例：P：x>yQ：x-y>0P→Q：P→Q：如果x>