离散数学命题符号化.ppt

4 蕴含 定义1 4由命题P和Q利用 组成的复合命题 称为蕴含式复合命题 记作 P Q 读作 如果P 则Q 当P为真 Q为假时 P Q为假 否则P Q为真 例8将命题 如果我得到这本小说 那么我今夜就读完它 符号化 解令P 我得到这本小说 Q 我今夜就读完它 于是上述命题可表示为P Q 例9若P 雪是黑色的 Q 太阳从西边升起 R 太阳从东边升起 则P Q和P R所表示的命题都是真的 蘊涵 條件 如果 就 的意义 兩個命題P Q可以用 若P則Q ifPthenQ 的蘊涵 implication 方式連接 逻辑符号的表法为P Q 中文口語上的說法則为 如果P就Q 意思是如果P是真那麼Q也一定为真 例如 如果下雨地就是溼的 若P則Q 的真偽值表如下 在這種情形之下 P稱為Q的充分條件 我們注意到 P Q 為偽只發生在P為真及Q為偽的情況下 條件否定 P Q 的真值表 于是得到 P Q 与P Q等价 換個角度來看 既然下雨地就會溼 那麼如果地是乾的 就一定是沒有下雨 下面的真偽值表可以反應這個關係 非Q則非P 為 若P則Q 之逆否命題 contrapositive 和 若P則Q 為等價之命題 我們稱Q為P之必要條件 例 算命仙的神機妙算從前 在某市住著一位算命仙 他家門口掛了一個招牌寫著 神機妙算 一回一千元 如果算得不準 保證退錢 商人們看了 都爭相來算命 第一個來算命的是賣碗的商人 算命仙收了一千元後 假裝唸了一些咒語 說 啊哈 如果碰到從東方來的人 你就會賺到錢 商人想到今天會賺錢 就開開心心地離開了 之後又有賣麥芽糖的商人 賣糕餅的商人與賣肉的商人前來算命 算命仙都對他們依樣畫葫蘆 假裝唸了一些咒語 然後說 啊哈 如果碰到從東方來的人 你就會賺到錢 當天晚上 賣碗商高興的跑來找算命仙 真是謝謝您 我真的碰到來自東方的人 結果賺了很多錢 您真是太準了 算命仙笑著說 那是當然的 以後歡迎再來算命啊 當賣碗商回去後 麥芽糖商人氣呼呼地找來了 根本就不準嘛 我今天遇到從東方來的人 卻一毛錢也沒賺到 算命仙摸著下巴說 那就奇怪了 不過既然不準 錢就還給你吧 當麥芽糖商人回去後 糕餅商人也怒氣衝天的跑進來 今天我都沒賺到錢 把我的錢還給我 算命仙停頓了一下 問說 那麼 是否有碰到來自東方的人呢 糕餅商搔著頭說 沒有耶 只碰到來自南方的人 那就對啦 我是說你如果碰到從東方來的人就會賺錢 可沒說碰到從南方來的人會賺錢啊 糕餅商聽這話似乎有理 就回去了 最後賣肉的商人也來了 今天我的確是賺到了錢 但不是碰到來自東方的人 而是來自北方的人 所以你算錯了吧 算命仙露出一付不可理喻的表情說 嘿 這位兄弟 我是說你如果碰到從東方來的人就會賺錢 何時說你碰到從北方來的人就不會賺錢啊 我可沒這麼說喔 賣肉商人覺得有理 點點頭回去了 當所有商人回去後 算命仙露出笑容 賺錢真是簡單啊 四個人來算命都給一樣的答案 竟然有三個是準確的 足足賺了三千啊 嘻嘻嘻 故事中的算命仙就是巧妙地運用了這種條件命題而賺到錢的 讓我們來研究一下他是如何辦到的 我們考慮 P 碰上來自東方的人 Q 賺到錢 有四種情形會發生 碰到來自東方的人 而賺到錢 碰到來自東方的人 但沒有賺到錢 沒有碰到來自東方的人 而賺到錢 沒有碰到來自東方的人 也沒賺到錢 然而 算命仙算不準的情形即是 如果p就q 為偽的情形 上面的真偽值表清楚的顯示只有在3的情形之下才會發生 所以 用 如果p就q 的方法幫人家算命 總會有四分之三機率是準確的 因此 即使承諾 如果算不準就退錢 算命仙仍然可能賺到錢 因為 算不準的機準只有四分之一 小心別上當哦 大人常對小孩說 如果你乖乖 我就給你糖吃 不知道有沒有小孩了解 即使不乖 還是可能有糖可吃這件事呢 说明 1 形式蕴涵与实质蕴涵 在数理逻辑中 即使P Q没有内在联系 P Q仍有意义 2 蕴涵式P Q有多种形式 若P 则QP是Q的充分条件Q是P的必要条件仅当Q则PQ每当PP仅当Q3 逆命题 反命题 逆反命题 给定P Q 则Q P P Q Q P分别叫做P Q的逆命题 反命题 逆反命题 则P Q 若月亮下山 则3 3 6 并没有实质蕴含关系 仍承认 Q P 叫做P Q的逆命题 Q P 叫做P Q的逆反命题 P Q 叫做P Q的反命题 例 P 月亮下山Q 3 3 6 5 等值 定义1 5由命题P和Q 利用 组成的复合命题 称为等值式复合命题 记作 P Q 读作 P当且仅当Q 当P和Q的真值相同时 P Q取真 否则取假 例10非本仓库工作人员 一律不得入内 解令P 某人是仓库工作人员 Q 某人可以进入仓库 则上述命题可表示为P Q 例11黄山比喜马拉雅山高 当且仅当3是素数令P 黄山比喜马拉雅山高 Q 3是素数本例可符号化为P Q 从汉语的语义看 P与Q之间并无联系 但就联结词 的定义来看 因为P的真值为假 Q的真值为真 所以P Q的真值为假 对于上述五种联结词 应注意到 复合命题的真值只取决于构成它的各原子命题的真值 而与这些原子命题的内容含义无关 三 联结词次序 1 运算符号结合力的强弱顺序为 凡符合此顺序的 括号可以省去 2 相同的运算符 按从左到右的顺序计算时 括号可以省去 3 最外层的括号可以省去 四 命题符号化利用联结词可以把许多日常语句符号化 基本步骤如下 1 从语句中分析出各原子命题 将它们符号化 2 使用合适的命题联结词 把原子命题逐个联结起来 组成复合命题的符号化表示 例12用符号形式表示下列命题 1 如果明天早上下雨或下雪 那么我不去学校 2 如果明天早上不下雨且不下雪 那么我去学校 3 如果明天早上不是雨夹雪 那么我去学校 4 只有当明天早上不下雨且不下雪时 我才去学校 解令P 明天早上下雨 Q 明天早上下雪 R 我去学校 4 R P Q 3 P Q R 2 P Q R 1 P Q R 例13将下列命题符号化 1 派小王或小李出差 2 我们不能既划船又跑步 3 如果你来了 那么他唱不唱歌将看你是否伴奏而定 4 如果李明是体育爱好者 但不是文艺爱好者 那么李明不是文体爱好者 5 假如上午不下雨 我去看电影 否则就在家里看书 解 1 令P 派小王出差 Q 派小李出差 命题符号化为P Q 2 令P 我们划船 Q 我们跑步 则命题可表示为 P Q 3 令P 你来了 Q 他唱歌 R 你伴奏 则命题可表示为P Q R 4 令P 李明是体育爱好者 Q 李明是文艺爱好者 则命题可表示为 P Q P Q 5 令P 上午下雨 Q 我去看电影 R 我在家读书 则命题可表示为 P Q P R 例14 若不是他生病或出差 我是不会同意他不参加学习 解 P 他生病Q 他出差R 我同意他不参加学习 P Q R 五 命题公式1 命题常元 一个表示确定命题真值的大写字母 T和F是命题常元 2 命题变元一个没有指定具体真值的命题符号 其值域为 T F 一个命题变元当没有对其赋予内容时 它的真值不能确定 一旦用一个具体的命题代入 它的真值就确定了 3 命题公式命题公式 或简称公式 是由F T和命题变元以及命题联结词按一定的规则产生的符号串 定义1 6 命题公式的递归定义 1 F T是命题公式 2 命题变元是命题公式 3 如果A是命题公式 则 A是命题公式 4 如果A和B是命题公式 则 A B A B A B A B 也是命题公式 有限次地利用上述 1 4 而产生的符号串是命题公式 例1下列符号串是否为命题公式 1 P Q PR 2 P Q Q R 解 1 不是命题公式 2 是命题公式 例2给出公式A P Q Q R P R 的真值表 解 公式A的真值表如下 4 命题公式的真值表的构成方法 两个命题公式 如果有相同的真值 则称为逻辑等价命题 定义 给定二个命题公式 A P1 P2 Pn B P1 P2 Pn 若给P1 Pn任一组真值指派 A B真值相同 称A和B是等价的或逻辑相等 记为A B 例3 判定公式P Q与 P Q是否逻辑等价 解列公式P Q与 P Q的真值表 练习1 11 判断下列语句哪些是命题 若是命题 则指出其真值 1 只有小孩才爱哭 2 X 6 Y 3