命题逻辑和命题演算.pptVIP

第一章 命题逻辑;概述和计算机科学联系 ;学习离散数学的重要性; 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”????请问这个人说得对吗？他是怎么推导出来的呢？ ; 要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程： ????(1) 什么是前提？有哪些前提？ ????(2) 结论是什么？ ????(3) 根据什么进行推理？ ????(4) 怎么进行推理？ ;二、命题与联结词;定义：命题---具有唯一真值的陈述句。;表示方法：命题（ ），真（1） 假（0）。;例： 2是偶数是不对的；2是偶素数；2或4是; p;（2）合取式：（ conjunction ）两个命题P和Q的 合取是一个复合命题，记作P∧Q。当且仅当P、 Q同时为T时， P∧Q 为T，其他情况下， P∧Q 的真值都是F。合取联结词“∧”表示自然语言 中的 “并且” 。 ;（3）析取式：两个命题P和Q的析取是一个复合 命题，记作P ∨ Q。当且仅当P、Q同时为F时， P ∨ Q 为F，其他情况下， P ∨ Q的真值都 是T。析取联结词 “∨ ”表示自然语言中的 “ 或”（or ）。 ;（4）蕴涵式：给定两个命题P和Q，其条件命题 是一个复合命题，记作P → Q。当且仅当P的真 值为T，Q的真值为F时， P → Q 的真值为F，其 他情况下， P → Q的真值都是T。条件联结词 “→ ”表示自然语言中的“如果…，那么…”。 ;（5）等价式：给定两个命题P和Q，其复合命 题P ? Q称作双条件命题。当P和Q的真值相同时， P ? Q 的真值为T，否则， P ? Q的真值都是F。 双条件联结词 “? ”表示自然语言中的“当且仅当”。 ;1-1.2 复合命题的符号化;1-1.2 复合命题的符号化;1-1.2 复合命题的符号化;1-1.2 复合命题的符号化;1-1.2 复合命题的符号化;四、命题公式及其赋值;定义： （1）单个命题变项可被称为合式公式； （2）若 是合式公式，则 也是合式公式； （3）若 是合式公式，则 也是合式公式； （4）将1-3有限次的联结起来也是合式公式。;五、合式公式的真值;例：利用真值表求 的成真赋值和成假赋值;第二章 命题逻辑等值演算;练习：1） 与 ;德·摩根律 : ?(A?B)??A??B ?(A?B)??A??B 吸收律: A?(A?B)?A, A?(A?B)?A 零律: A?1?1, A?0?0 同一律: A?0?A, A?1?A 排中律: A??A?1 矛盾律: A??A?0;蕴涵等值式: A?B??A?B 等价等值式: A?B?(A?B)?(B?A) 假言易位: A?B??B??A 等价否定等值式: A?B??A??B 归谬论: (A?B)?(A??B) ??A 注意: A,B,C代表任意的命题公式 ;等值演算的用途一：证明等值式。 例1.10 验证 p?( q? r) ? (p ∧ q) ? r 右? ? (p ∧ q) ∨ r 蕴涵等值式 ? ? p ∨ ? q ∨ r 德摩根律 ? ? p ∨ (? q ∨ r) 结合律