[小學教育]ch01邏輯證明集合函數(編輯修改稿)

　

【文章內容簡介】 、 A ? B ? ? A ? ? B 2 (A ? B) ? (A ? ? B ) ? ? A 1 A ? ? A ? 1 矛盾律 等價否定等值式 等價等值式 假言易位 Institute of Computer Software 王兵 證明 (A?B)?(?A?B) ?B 74 實際問題推理 ? 執(zhí)行語句 x的條件化簡 (A?B)?(?A?B) ?((A?B)??A)?((A?B)?B)結合律 ?((A??A)?(B??A))?((A?B)?B) ?(1?(B??A))?((A?B)?B) ?(B??A)?((A?B)?B)吸收律 ?(B??A)?B吸收律 ?B Institute of Computer Software 王兵 證明 (p?q) → (p ? q)為永真式 Institute of Computer Software 王兵 2022/4/14 驗證下列等值式 (1) p ? (q ? r) ? ( p ? q) ? r 解 ： p ? (q ? r) ? 172。 p ? (q ? r ) ? 172。 p ? (172。 q ? r) ? (172。 p ? 172。 q ) ? r ? 172。 ( p ? q) ? r ? ( p ? q) ? r 蘊涵等值式 蘊涵等值式 結合律 德 摩根 律 蘊涵等值式 Institute of Computer Software 王兵 77 實際問題推理 ? 求解實際問題 –例：某單位要從 A、 B、 C三人中選派若干人出國考察 , 需滿足下述條件 ? (1)若 A去，則 C必須去 ? (2) 若 B去，則 C不能去 ? (3) A和 B必須去一人且只能去一人 –問有幾種可能的選派方案？ Institute of Computer Software 王兵 78 實際問題推理 ? 解：記 p: 派 A去， q: 派 B去， r: 派 C去 – (1)若 A去，則 C必須去 ? p?r – (2)若 B去，則 C不能去 ? q??r – (3) A和 B必須去一人且只能去一人 ? (p??q)?(?p?q) Institute of Computer Software 王兵 79 實際問題推理 ? 記 p: 派 A去， q: 派 B去， r: 派 C去 – (1)若 A去，則 C必須去： p?r – (2)若 B去，則 C不能去： q??r – (3)A和 B必須且只能去一人： (p??q)?(?p?q) ? 求下式的成真賦值 – A=(p?r)?(q??r)?((p??q)?(?p?q)) Institute of Computer Software 王兵 80 實際問題推理 ? A=(p?r)?(q??r)?((p??q)?(?p?q)) ?(?p?r)?(?q??r)?((p??q)?(?p?q)) ?((?p??q)?(?p??r)?(r??q)?(r??r)) ?((p??q)?(?p?q)) ?((?p??q)?(p??q))?((?p??r)?(p??q)) ?((r??q)?(p??q))?((?p??q)?(?p?q)) ?((?p??r)?(?p?q))?((r??q)?(?p?q)) ?(p??q?r)?(?p?q??r) Institute of Computer Software 王兵 81 實際問題推理 ? A=(p?r)?(q??r)?((p??q)?(?p?q)) –?(p??q?r)?(?p?q??r) –成真賦值 :101,010 –結論 ?方案 1：派 A、 C去 ?方案 2：派 B去 Institute of Computer Software 王兵 82 第 1章 基礎：邏輯和證明、集合、函數 ? 謂詞和量詞 Institute of Computer Software 王兵 83 引言 ? 命題邏輯有局限 ? 研究命題之間關系，基本單位是原子命題 李明是西南石油大學學生 張鵬是西南石油大學學生 劉璐是西南石油大學學生 Institute of Computer Software 王兵 命題邏輯只能進行 命題間關系 的推理，無法解決與 命題的結構和成分 有關的推理問題。 例如 (著名的蘇格拉底三段論 ) （ 1）所有的人都是要死的； P （ 2）蘇格拉底是人。 Q （ 3）蘇格拉底是要死的。 R ? 實際中經常使用 –上述推理是正確的 ? p?q?r 應為永真 –p、 q、 r 值分別為 0時， –復合命題為假 Institute of Computer Software 王兵 85 命題邏輯的局限性 –所有人要死： p，蘇格拉底是人： q，蘇格拉底要死： r ? r與 p、 q無關：獨立的命題，可以獨立賦值 –實際上 ? r與 p、 q有關，只是命題邏輯無法表示 原因： 命題邏輯不能將命題之間的內在聯系 和數量關系反映出來 。 解決辦法： 將命題進行分解 。 Institute of Computer Software 王兵 ? 命題 =主語 +謂語 “ 計算機 是現代科學技術必不可少的工具 ” Institute of Computer Software 王兵 主語 /個體詞 定義 在原子命題中，可以獨立存在的客體（句子中的主語、賓語等），稱為 個體詞(Individual)。 例 如，電子計算機、李明、玫瑰花、黑板、實數、中國、思想、唯物主義等， Institute of Computer Software 王兵 謂詞 謂詞： 用來刻劃客體的性質或客體之間的相互關系的詞 （ 1） 張明是個勞動模范 。 （ 2） 李華是個勞動模范 。 刻劃客體的性質 （ 3） 王紅 是個大學生 。 （ 4） 小李比小趙高 2cm。 （ 5） 點 a在 b與 c之間 。 刻劃客體之間的相互關系 （ 6） 阿杜與阿寺同歲 。 ??????????Institute of Computer Software 王兵 ? 刻劃 一個客體性質 的詞稱之為 一元謂詞 ,刻劃 n個客體之間關系 的詞稱之為 n元謂詞 . ? 一般我們用大寫英文字母表示 謂詞， 用小寫英文字母表示客體名稱， (1) F(a) a： 張明 (2) F(b) b： 李華 (3) G(c) c： 王紅 (4) H(s,t) s： 小李 t：小趙 (5) R(a,b,c) (6) S(a,b) a:阿杜 。 b:阿寺 。 其中 (1)、 (2)、 (3)為一元謂詞 ， (4) 、 (6)為二元謂詞 ， (5)為三元謂詞 。 Institute of Computer Software 王兵 謂詞 ? 更一般地， ? P(x)： x是西南石油大學的學生。 x：個體詞 P：謂詞 P(x):命題函數 P(x) 命題函數 =變量 +謂詞 (predicate) Institute of Computer Software 王兵 例 設有如下命題，并用 n元謂詞進行表示。 P： 王童 是一個三好學生 ； Q： 李新華 是 李蘭 的父親 ； R： 張強 與 謝莉 是好朋友 ； S： 武漢 位于 北京 和 廣州 之間 。 Institute of Computer Software 王兵 例（續(xù)） 解 定義命題函數： S(x)： x是一個三好學生； F(x, y)： x是 y的父親； T(x, y)： x與 y是好朋友； B(x,y,z)： x位于 y和 z之間； 用符號表示個體詞： a：王童； b：李新華； c：李蘭； d：張強； e：謝莉； f：武漢； g：北京； h：廣州。 則命題可表示為： P： S(a)； Q： F(b, c)； R： T(d, e)； S： B(f, g, h)。 Institute of Computer Software 王兵 93 謂詞實例 ? 程序語言中的謂詞 – if (x0) x=x+1。 – if (2+2==4) x=x+1。 Institute of Computer Software 王兵 例 :將下列命題用謂詞符號化 . (1) 2是素數且是偶數 . (2) 如果 2大于 3,則 2大于 4. (3) 如果 張明比李民高 , 李民比趙亮高 ,則張明比趙亮高 . Institute of Computer Software 王兵 ? 解 :(1) 設 F(x): x是素數 . G(x): x是偶數 . 則 命題符號化為： F(2)∧ G(2) (2) 設 L(x,y) ： x大于 y. 則 命題符號化為： L(2,3) ? L(2,4) (3) 設 H(x,y): x比 y高 . a:張明 b:李民 c：趙亮 則 命題符號化為： H(a,b)∧ H(b ,c)?H(a,c) Institute of Computer Software 王兵 量詞 例 符號化下述命題： （ 1） 所有的 老虎都要吃人； （ 2） 每一個 大學生都會說英語； （ 3） 所有的 人都長著黑頭發(fā)； （ 4） 有一些 人登上過月球； （ 5） 有一些 自然數是素數。 Institute of Computer Software 王兵 例 (續(xù) ) 解 設立如下謂詞： P(x)： x會吃人； Q(x)： x會說英語； R(x)： x長著黑頭發(fā)； S(x)： x登上過月球； T(x)： x是素數。 則有：（ 1） 所有的 x， P(x) x∈ {老虎｝； （ 2） 每一個 x， Q(x) x∈ {大學生 }； （ 3） 所有的 x， R(x) x∈ {人 }； （ 4） 有一些 x， S(x) x∈ {人 }； （ 5） 有一些 x， T(x) x∈ {自然數 }。 Institute of Computer Software 王兵 量詞含義 )( x? )( x? 有些 x； 至少有一個 x； 某一些 x； 存在 x；等等 。 所有的 x； 任意的 x； 一切的 x； 每一個 x；等等。 Institute of Computer Software 王兵 在命題函數中，客體變元的取值范圍稱為個體域 ，又稱之為論域。個體域可以是有限事物的集合，也可以是無限事物的集合。 全總個體域 ： 宇宙間一切事物組成的個體域稱為全總個體域 。 例 (續(xù) ) （ 1） (?x)P(x) x∈ {老虎 } ； （ 2） (?x)Q(x) x∈ {大學生 }； （ 3） (?x)R(x) x∈ {人 }； （ 4） (?x)S(x) x∈ {人 }； （ 5） (?x)T(x) x∈ {自然數 }。 Institute of Computer Software 王兵 101 量詞 (quantifier) ? 量化 (quanification) –命題函數的變量取值范圍的符號化表示 ? 變量取值范圍：論域 (domain) ? 量詞 (quantifier) –表示數量的詞 Institute of Computer Software 王兵 102 量詞 (quantifier) ? 全稱量詞 (universal quantifier) – ?x：論域中 “ 所有的 ” x ? 全稱量化 (universal quanification) – ?xP(x)：對論域中 “ 所有的 ” x， P(x)為真 ? ?x((x+1)2=x2+2x+1) – 反例 ()： P25，例 10