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