离散数学命题符号化课件.ppt

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