Download presentation
Presentation is loading. Please wait.
1
Unit 5 真值表法 授課教師：傅皓政 老師 【本著作除另有註明外，採取創用CC「姓名標示－非商業性－相同方式分享」台灣3.0版授權釋出】
2
Unit 5 真值表法 首先，讓我們複習一下，古典邏輯的二 值原則預設每個原子命題只可能出現兩 個真假值：即「真」和「假」。
通常以「T」代表「真」，而且以「F」 代表「假」。 1024-1(00022) 00:20:03 以T代表真、F代表假，也可以用1、0表示，有的書會用┬(真)、┴(假)。 事實上有很多不同表示語意值的用法。
3
Unit 5 真值表法 因此，如果僅出現一個命題的語句，只 需要考慮兩個可能情況，而出現兩個命 題組成的語句，則須考慮22=4 種情況。 依此類推，出現 n 個命題的語句，則需 要考慮 2n 種可能情況。 1024-1(00022) 00:21:40 如果出現一個命題，我們要考慮兩種情況；如果出現兩個命題，我們要考慮四種情況。 以此類推，如果出現N個命題，就要考慮 2n 種情況。
4
Unit 5 真值表法 所謂的可能情況就是原子命題的各種可 能的組合，我們將每個可能情況稱為 「結構(structure)」或「模型(model)」。 例如，P 代表「傅老師是男人」，那麼 有兩個可能情況，一為傅老師是男人的 世界；另一則為傅老師不是男人的世界。 在第一類可能情況中，P 為真；在第二 類可能情況中，P 為假。 1024-1(00022) 00:21:54 把每一個可能組合的情況稱為structure或model。 如：P 代表「傅老師是男人」，我們可以想像兩種世界， 一為傅老師是男人的世界；另一則為傅老師不是男人的世界， 傅老師不是男人並未推論出他是女人，可以是螞蟻、桌子、椅子等。 這是宇集的概念。
5
Unit 5 真值表法 如果出現兩個原子命題，例如 P 代表 「傅老師是男人」，Q 代表「傅老師是 好人」。那麼，會有四個結構：
P Q P Q P Q P Q T T T F F T F F 1024-1(00022) 00:23:51 如果有兩個命題，就會出現四種情況 傅老師是男人且是好人； 傅老師是男人而且不是好人； 傅老師不是男人但是好人； 傅老師不是男人且不是好人；
6
Unit 5 真值表法 不難想像，如果有三個原子命題，那麼 就會有 8 個不同的結構： P Q R P Q R P Q R P Q R
T T T T T F T F T T F F F T T F T F F F T F F F 1024-1(00022) 00:24:34 依此類推，如果有三種命題，會有八種情況。
7
Unit 5 真值表法 根據古典邏輯的外延原則，每個句式的 真假值均可由原子命題的真假值決定。
論證是一群句式的集合，其結構則為前 提與結論。 有效論證：不可能出現前提皆真而結論 為假的情況。 1024-1(00022) 00:24:46 不可能出現『前提皆真、結論為假』，只要符合這個條件，它就是有效論證。
8
Unit 5 真值表法 實例說明： 考慮下列論證的語意蘊涵關係是否成立 (a) PQ, QR, R ⊨ P
(b) PQ, RQ, R ⊨ P 1024-1(00022) 00:25:27 假設A論證成立，舉個例子，同學你覺得傅老師是好人對嗎？ 假設他對老師心存怨恨，他覺得老師不是好人，他就要設計論證。 1024-2(00023) 00:00:00 或者他不願意讓老師太驕傲，所以他不會直接回答，但有那個意思在。 所以他可以說 ，傅老師是好人，或者傅老師是男人，如果傅老師是男人，那傅老師很帥。接下來他說，傅老師一點都不帥。 上述的說法可以推論得到傅老師是好人的結論。這個是讓思考更引人入勝，不是那麼直來直往。所以第一個可以成立的話，可以推出傅老師是好人這件事。 第二個例子，傅老師是好人或傅老師是男人，如果傅老師長得很帥，則傅老師是男人，所以他說，傅老師你一點都不帥。這樣有沒有推出傅老師是好人？我們要研究的就是這些推論是否正確。
9
Unit 5 真值表法：實例(a) 原子命題 前提 結論 P Q R PQ QR R T F
1024-2(00023) 00:03:24 有效論證的基本想法是，不能出現前提皆真，結論為假。 所以，如果所有情況都沒有出現前提皆真，結論為假的情況，就證明該論證為有效論證。
10
Unit 5 真值表法 觀察實例(a)的每個結構，其中能夠符 合前提皆真的結構只有第四列，而第四 列的結構亦使得其結論為真。因此，根 據有效論證的判準，我們找不到前提皆 真而結論為假的情況，所以實例(a)的 蘊涵關係是成立的。 1024-2(00023) 00:06:30 如果是有效論證，在寫完真值表測驗結束後，你只要在最底下註明它是有效論證就可以了。
11
Unit 5 真值表法：實例(b) 原子命題 前提 結論 P Q R PQ RQ R T F
1024-2(00023) 00:06:59 第一個情況前提是「真真假」，它沒有皆真，所以通過。 第二個前提是「真真真」，它前提皆真，所以我們需要去檢查結論，結論是真，所以通過。 第三個前提是「真假假」，它沒有皆真，所以通過。 第四個前提是「真真真」，它前提皆真，結論是真，所以通過。 第五個情況前提是「真真假」，它沒有皆真，所以通過。 第六個前提是「真真真」，它前提皆真，但結論是假，所以它是無效論證。 你只要找到一個情況就可以證明它是無效論證。 第七個情況前提是「假假假」，它沒有皆真，所以通過。 第八個情況前提是「假真真」，它沒有皆真，所以通過。
12
Unit 5 真值表法 觀察實例(b)的每個結構，其中第六列 的結構使得前提皆真而且結論為假。因 此，根據有效論證的判準，有前提皆真 而結論為假的情況，所以實例(b)的蘊 涵關係是不成立的。 1024-2(00023) 00:08:19 第六個情況沒有通過test，所以我們說前提與結論之間的蘊涵關係是不成立的，或者說這個論證是無效論證。
13
Unit 5 真值表法 實例(b)的蘊涵關係不成立，表示方式 如下： PQ, RQ, R ⊭ P 其反例結構為: P Q R
F T F 1024-2(00023) 00:08:29 面對無效論證的回答方式如下： 第一個你要寫它是無效論證，然後我會要求各位將正確的sequence寫出來，劃個斜線表示這個蘊涵關係不成立。 最重要的是反例結構一定要寫，反例結構就是說明使得論證不成立的structure是什麼。 所以各位要把這個結構寫出來 P Q R ──── F T F 換言之，這個結構可以證明它是無效論證。
14
Unit 5 真值表法 基本練習：考慮下列論證的語意蘊涵關 係是否成立 (c) PQ, P ⊨ Q (d) PQ, P ⊨ Q
(e) PQ, Q ⊨ P (f) PQ, Q ⊨ P 1024-3(00024) 00:04:55 如果碰到無效論證，我們在寫答案時要出現三個東西。 第一個你要寫它是無效論證，或是它的蘊涵關係不成立。 第二個你要把它正確的sequence寫出來。 第三個你要寫出它的反例。 接下來我們來做很基本的練習。 我們可以請同學來發言，你覺得哪些是有效論證，哪些是無效論證？ C是有效論證 D是無效論證 E是無效論證 F是有效論證
15
Unit 5 真值表法 (c) (PQ), P ⊨ Q 論證(c)為有效論證，即語意蘊涵關係 成立。 原子命題 前提 結論 P Q PQ
F 1024-3(00024) 00:07:10 第一個情況，前提皆真，結論也是真，所以通過。 接下來，都沒有前提皆真，也通過，所以是有效論證。
16
Unit 5 真值表法 (d) PQ, P ⊨ Q 原子命題 前提 結論 P Q PQ P Q T F
1024-3(00024) 00:08:05 第一個前提是TF沒有皆真，所以通過。 第二個前提是FF沒有皆真，所以通過。 第三個前提是TT，前提皆真，但結論為假，所以這個論證是無效論證 最後一個雖然通過，但是第三個沒有通過，所以它仍然是無效論證。
17
Unit 5 真值表法 論證(d)為無效論證，亦即語意蘊涵關 係不成立： (d) PQ, P ⊭ Q 其反例結構為: P Q F T
1024-3(00024) 00:09:07 無效論證的表示法：第一步要寫這個論證是無效論證，或者寫蘊涵關係不成立，然後寫出正確的Sequence，接下來寫反例結構，能夠證明該論證是無效的可能情況，稱之為反例結構。 表示反例的時候只需要寫出一個反例結構即可。
18
Unit 5 真值表法 (e) PQ, Q ⊨ P 原子命題 前提 結論 P Q PQ T F
1024-3(00024) 00:09:48 這個(e)也一樣，各位可以看的出來，有一個情況前提皆真，結論為假，所以可以看的出來是無效論證。
19
Unit 5 真值表法 論證(e)為無效論證，亦即語意蘊涵關 係不成立： (e) PQ, Q ⊭ P 其反例結構為: P Q F T
1024-3(00024) 00:10:00 無效論證也一樣要寫出正確的sequence以及反例。
20
Unit 5 真值表法 (f) PQ, Q ⊨ P 論證(f)為有效論證，即語意蘊涵關係成 立。 原子命題 前提 結論 P Q PQ
1024-3(00024) 00:10:11 接下來(f)，(f)證明出來只有一個情況要考慮，前提皆真，然後結論為真，所以是有效論證。
21
Unit 5 真值表法 進階練習：考慮下列論證的語意蘊涵關 係是否成立 (g) AB, (BA)A ⊨ AB
(h) MN, N ⊨ NM (i) ⊨ P(QP) (j) (CC)D, D ⊨ 1024-3(00024) 00:10:23 那我們來看看稍微複雜的例子，
22
Unit 5 真值表法 (g) AB, (BA)A ⊨ AB 論證(e)為有效論證，即語意蘊涵關係 成立。 原子命題 前提 結論 A
T T F T F F T 1024-3(00024) 00:10:38 首先我們來看這個(g) 它是AB, (BA)A ⊨ AB 我們來看看它是不是個有效論證，我們一樣把A列出來，它是真真假假，B是真假真假，所以AB這個前提它是真假假假。 第二個BA我們會先做紅色的or，再做藍色這部分，接下來是結論，如果值一樣為真嘛、不一樣為假，所以是真真假真。 所以可以看到第一個test，前提皆真，結論為真，通過。 接下來第二個，很明顯看到都沒有前提為真的情況嘛，所以通過test，我們說是一個有效論證。所以你把真值表畫完後，只要註明它是有效論證就好。
23
Unit 5 真值表法 (h) MN, N ⊨ NM 原子命題 前提 結論 M N M N N N M T
T F T F F F F T T F T T F F F T T 1024-3(00024) 00:12:10 第二個(h)，是不是有效論證我們來看一下，對了，還有個問題，我要交代一下。我們在列structure會有個問題，雖然比如說有四種情況會先寫兩個兩個(一組)再寫一個，但還有麻煩，就是上面的原子命題，原子命題通常有兩個方法，第一個按字母順序如A.B.C.D；第二個方法，按出現順序來命名。 比如說在這題裡，M和N會倒過來，所以各位了解我意思嗎？ 有時候會字母排序比較後面的先出現，所以如果有人寫MN，有人寫NM，這樣會很困擾。所以各位比較喜歡哪一個？原則上，各位希望用哪個，我們就統一。出現的順序？好，出現(的順序)比較好，因為我怕有人會背錯字母順序。所以各位記得，各位在排列structure，請按照題目出現的順序。 那我們開始來看，這個我們先做紅色的，各位記得連接性的強度嗎？ 連接性最強的是，再來、，再來是→、。所以如果沒用括號要先做再做，如果各位很厲害會發現，兩個N會相當於它自己，比如：我不是不愛你，跟我愛你是一樣的。不過各位在講時候不要激動，激動就會口吃， 「我不是不不不不不……愛你」這樣就要去數到底是奇數還偶數。 所以這個，當然最後就是N啦，TFTF，然後這個是一樣先做M，所以是FFTT， 然後Conditional，小心前面是N，後面要紅色這個，所以原則上做出來後再去做TEST，藍色是最後結果，第一個，前提皆真，這兩個藍色是真、結論是假，所以這個structure剛好是反例。所以如果要test它是不是個有效論證，這裡就可以證明了嘛，答案它就是個無效論證。
24
Unit 5 真值表法 論證(h)為無效論證，亦即語意蘊涵關 係不成立： (h) MN, N ⊭ NM 其反例結構為: M N
T T 1024-3(00024) 00:18:42 所以它是個無效論證，反例結構只要寫一個就夠了， 道理是我們講一個人做錯，只要講一件事就好，一直講最後會變得不理性。 你要讓人維持在理性的狀態下，他比較容易認錯。
25
Unit 5 真值表法 (i) ⊨ P(QP) 論證(i)為有效論證，即語意蘊涵關係成 立。 原子命題 前提 結論 P Q
T T F T F 1024-3(00024) 00:20:39 這個sequence少了前提，如果沒有前提，你就可以假設任何情況，也就是可以假設所有前提皆真，這樣的情況結論就變得很重要，所以你只要發現結論有假，該論證就不成立，也就是說這個論證是無效論證。 不過，在這裡出現的是結論在任何情況下都為真，表示加入任何前提，也不影響它是有效論證的結果。
26
Unit 5 真值表法 (j) (CC)D, D ⊨ 論證(j)為有效論證，即語意蘊涵關係成 立。 原子命題 前提 結論 C D
T F T F T F F T T T T T F 1024-3(00024) 00:24:09 接下來，這個少了結論，表示寫什麼都可以。 那可以想像結論都是假，要看是否為有效論證，就是看前提是否都為真， 如果有出現前提皆真的情況之下，表示可能會出現前提皆真、結論為假，那麼這個論證就是一個無效論證。反之，如果在這個test裡面沒有出現前提皆真的情況，那就表示這個論證是一個有效論證。 第一個我們把他帶進來藍色的部分最後是TFTF，這個是FTFT。 所以你會發現這個連前提皆真的情況都沒有，更不用說會出現前提皆真、結論為假的情況。 所以這個論證顯然是一個有效論證。
27
Unit 5 真值表法 真值表法的重要性在於提供一個決定 命題邏輯論證有效與否的程序。
不過，真值表法的缺點在於如果命題 符號的個數過多，那麼真值表法則顯 得過分繁複。 因此，我們需要一個比較簡單的方法 ──簡易真值表法(short-cut) 1024-3(00024) 00:25:40 真值表在於提供一個有效的機械式程序，這個程序保證在任何命題邏輯或語句邏輯的論證，你都可以用真值表法證明是該論證是有效或無效論證。 因為我們通常把邏輯的特性稱之為Decidable可被決定的，所以如果我們找到一個方法，可證明所有論證是有效或是無效，那這個我們稱之為可決定的。 在真值表法前，想要證明某個論證，多少需要依靠一些天分來證明。然而真值表法在20世紀初才出現，所以20世紀以前的邏輯學家並沒有這些的機械程序可以用來證明。 但是，真值表法也不是那麼完美，如果原子命題有兩個，我們可以輕易地畫出真值表，但是，如果原子命題有十個呢？那我們顯然要考慮1024個情況。 所以，真值表雖然是一個機械性的程序，也可以讓我們證明論證是否有效，但是其缺點在於太過繁複了。 1024-4(00025) 00:00:00 所以邏輯學家找到了捷徑。
28
Unit 5 真值表法 簡易真值表法的操作方法： (1) 先假設給定的論證是無效論證，也就 是假設前提皆真而結論為假。
(2) 如果上述的假設會導致矛盾出現，那 麼該論證即為有效論證。如果沒有矛盾出 現，意思就是至少有一個結構可以使得前 提皆真而結論為假，亦即該論證為無效論 證。 1024-4(00025) 00:00:33 假設我要證明林先生是好人，那就麻煩了，要一個個列出來，但假設我說林先生是壞人，只要找到他做的一件壞事就好。所以我們準備要怎麼做？ 我們假設林先生是壞人，也就是我們先去看他有沒有做過任何壞事，如果找不到，我們大概就相信他是好人。Short-cut也是這個意思，找到反例。 先假設前提皆真，結論為假，假設完再去檢驗，如果這樣的假設會出現矛盾，就代表我假設該論證是無效論證是錯的。但如果沒有矛盾出現，就表示我可以找到一個情況讓這個論證的前提皆真，結論為假，也就是無效論證。
29
Unit 5 真值表法 實例說明： (k) PQ, QR, R ⊨ P (l) PQ, RQ, R ⊨ P
(m) PQ, QP ⊨ P (n) PQ, PQ⊨ Q (o) (PQ)R ⊨ PR 1024-4(00025) 00:05:17 我們來看這些例子
30
Unit 5 真值表法 (k) PQ, QR, R ⊨ P P Q Q R R P T T T F F F F T F
矛盾 假設前提皆真且結論為假會產生矛盾，所 以上述論證為有效論證。 1024-4(00025) 00:05:33 首先各位要把前提寫出來。 第一步假設所有前提皆真，結論為假。假設完後根據你的假設去做運算，如何運算呢？R為真，表示R為假，再來，如果如果R(第二個)為假，表示Q為假(第二個)。Q為假， P Q 要為真，唯一的情況P要為真，所以是矛盾。 表示矛盾的話，你剛假設前提皆真、結論為假，結果出現矛盾，表示假設不成立，所以是有效論證。
31
Unit 5 真值表法 (l) PQ, RQ, R ⊨ P P Q R Q R P T T T F F F T F T
假設前提皆真結論為假不會得到矛盾，因此 上述論證是無效論證。 反例結構(counterexample)： P Q R F T F 1024-4(00025) 00:09:50 第二個例子一樣，我們先假設前提皆真，結論為假，然後運算。 R 是真，R就是假，Q可以是真或假，那就先寫R為假，Q為真，可以配合後面P為假，發現這樣沒有矛盾，表示這個論證允許前提皆真、結論為假的情況，所以是無效論證。 所以各位要把counterexample寫出來，反例結構就是這個沒有矛盾的情況。
32
Unit 5 真值表法 (m) PQ, QP ⊨ P P Q Q P P T T F T T T F F 矛盾
假設前提皆真而結論為假會產生矛盾 ，所以為有效論證。 1024-4(00025) 00:12:20 第一步假設前提皆真，結論為假。 從最容易做的開始，舉個例子，有個人會有順序的偏執，他一定要從第一個開始做，那他就會遇到P Q為真，有三種情況。 所以從唯一決定的開始，非必要不要分開。 最簡單的 P為假，所以P為真。Q P 要為真，所以Q為假，那P Q 為真，所以Q要為真，所以這個假設會導致矛盾。既然假設前提皆真結論為假會導致矛盾，亦即證明前提皆真而結論為假是不成立，所以該論證是有效論證。
33
Unit 5 真值表法 (n) PQ, PQ ⊨ Q P Q P Q Q T T F T T T T T
假設前提皆真且結論為假不會導致矛盾，所 以上述論證為無效論證。 反例結構： P Q T T
34
Unit 5 真值表法 (o) (PQ)R ⊨ PR (P Q) R P R T F T F T F F
假設前提皆真且結論為假不會導致矛盾， 所以上述論證為無效論證。 反例結構： P Q R T F F
35
Unit 5 真值表法 函映完備性(functionally complete)
根據functionally complete，因為只是用到他，我們不做任何證明，只說明性質。原則上，我們其實在這裡看到的一個狀態是很難理解，這個語句的函映並不是一個二元的連接詞，是三元的連接詞，用來連接三個語句，分別是P、Q、R，大致上可以寫成這樣 #(P,Q,R) ， 有沒有一個方法，去定義 三元連接詞的方法，而且定義從二元連接詞來，對邏輯學家要證明 所有 n 元的真值函映連接詞 都可以用二元的真值函映連接詞去定義 。 只談真值函映(INPUT真假值，OUTPUT一定會有真假值)，非真值函映不在討論範圍。證明說：能不能用有限的二元的真值函映去定義 n 元的連接詞，這樣的證明稱為函映的完備性
36
Unit 5 真值表法 具備函映完備性的連接詞集合 ，，，， ，，、，、，、，
、 MP :11:44 第一個，我們在介紹命題語言時提到五個連接詞，事實上，用這五個連接詞就可以用來定義所有 n 元真值函映的連接詞。 我們的conditional其實可以用或者是來定義，也就是我們的P則Q其實可以換成PQ。所以conditional是可以不要的。 我們equipollent的符號那個其實也可以用conditional來定義，就是PQ可以定義成P則Q and Q則P，所以後面兩個符號其實是可以被定義的。因此我們會有底下，，，他也是functionally complete的連接詞。邏輯學家覺得既然三個可以，那兩個行不行？結果發現也可以，所以我們會有，、，、，。那既然兩個可以，那一個行不行？ 我們有沒有可能用一個連接詞去定義所有真值成立的連接詞？ 結果發現也是可以的，所以我們會有兩個有趣的符號、。 我們可以用這兩個符號來證明所有的語句，定義所有的連接詞。 邏輯系統跟其他東西一樣，你在某一方面變簡單，你要付出的代價就是在另外一方面會變困難。比如說，我們用的連接詞越少，我們語句的長度就會越長。以我過去所做過的問卷統計結果，通常理工農醫的同學會喜歡用連接詞少、語句較長的方式，而文法商管理的同學通常會用喜歡連接詞多、語句較短的方式，當然這不是一定的。連接詞越多就需要越多的證明，因此從證明的簡潔性來講，1個連接詞在證明上他是佔便宜的，可是他在表達上是吃虧的。這樣的思考能力他會延伸到你的日常生活。 比如說，有些同學在跟你講話的時候，他會很簡短、不浪費時間的跟你表達他的意思，但相對日後付出的代價卻是比較大的。在科學裡面有個非常重要的性質叫做簡單性，我來畫圖解釋給各位聽。 接下來我們要用函映的完備性的性質來解決下面的問題。
37
Unit 5 真值表法 DNF 與 CNF 到目前為止，我們已經知道如何利用 真值表決定語句的真假值。接下來， 我們要挑戰的問題是：是否可以經由 真值表決定語句？ MP :22:04 我們接下來要解決的問題是，我們如何運用一個真值表來找出和等值的語句？ 第一個方法我們稱為DNF，另外一個稱為CNF。 他的想法大概是這樣，我們現在要找這個語句有兩個方向。
38
Unit 5 真值表法 DNF: 選言標準形式(Disjunctive Normal Form )
MP :22:39 第一個方向是說，我們怎麼去組織一個真的語句，並且告訴別人這句話一定就是這個真值表所要表達的意思？ DNF是由真的情況去組織。而CNF剛好相反，他是由假的方向去組織。 他的基本構想大概是這樣。 假設我給你這樣一個真值表，你如要去組織這句話要表達的東西？ 想法上大概是這樣，我們只要看到這個為真的情況， 那這些為真的情況在告訴我們一件事，這個語句必須要在第一、二、四情況裡面為真，可是碰到第三個情況必須為假。 所以我們在組織這個語句的時候，我們的想法就是，把所有為真的情況找出來。 我們要讓第一、二、四情況帶進去為真，所以我們就是用Disjunction的方式把它連接起來。 Disjunction的條件是，只要有一個為真，整句話就為真。 意思就是，只要一、二、四情況帶進去其中一個為真，他整個句子就為真。 我們在找DNF的時候，我們把在Disjunction兩邊的，我們就分別稱為disjunct。 那在這個disjunct裡面，他會是個conjunction，這個conjunction是用來描述這個情況的意思是什麼。 這個conjunction裡面，他的conjunct都是quasi-atomic formula。
39
Unit 5 真值表法 準原子句式 定義：某句式稱為準原子句式，若且 唯若，該句式是原子命題或者是只包 含一個否定號的原子命題。
(1) P, Q, P, Q 等是準原子句式。 (2) P, PP, PQ 等不是準原子句式。 MP :26:41 什麼是quasi-atomic formula呢？ 他如果是quasi-atomic formula的話，這個formula本身一定是一個原子命題，或只是只有加一個negation的符號。 所以像 P, Q, P, Q 這些都是quasi-atomic formula。 像P, PP, PQ這些都不是quasi-atomic formula。
40
Unit 5 真值表法 考慮真值表中的某個可能情況，以原子 命題或其否定組合描述該狀態為真，稱 之為狀態描述。 P Q 組合的狀態描述 T
F P Q P Q P Q MP :27:34 接下來我們要如何把這個的DNF找出來呢？ 我們先把那些狀態描述先把他確定下來，他的狀態是這樣。 第一個情況是P為真Q為真，也就是P Q是成立的。 如果P代表傅老師是好人，Q代表傅老師是男人， 那在第一個事件發生什麼事？就是傅老師是好人且傅老師是男人。 第二個情況是P為真Q為假，就是在那個事件裡面，傅老師是好人，但傅老師不是男人。 那第三個事件P為假Q為真，在那個情況裡面，傅老師不是好人，但傅老師是男人。 他在描述這個事件、情況的樣子是什麼，P跟Q真假的樣子是什麼。
41
Unit 5 真值表法 決定 DNF 的程序 藉由狀態描述的觀念，我們可以輕易 地找出以該真值表描述的 DNF。
MP :29:54 決定DNF的程序， 第一個我們先把狀態描述確定好，確定好之後， 我們只要把出現真的狀態利用disjunction的方式把它連接起來，就是我們要的formula。 我們來稍微做一下練習。
42
Unit 5 真值表法 DNF 的實例(1)，假設某個真值表如下表 所列： P Q T F MP4-1031 00:30:22
首先我們來看這個真值表，我們要把找出來。 有同學剛剛很快地找出是P→Q或是Q→P。
43
Unit 5 真值表法 根據命題邏輯的語意規則，不難發現 實例(1)的句式 其實就是 QP。 句式 的 DNF 則寫成下列形式：
(PQ)(PQ)(PQ) MP :30:45 我們其實可以怎麼做呢？ 我們做出來是QP，我們的DNF就是，把剛剛為真部分的state用disjunction的方式把它連接起來。為了讓各位同學更熟悉一點，我們再帶各位做一次練習。 第一步要先找有幾個為真的情況，有三個情況第1、2、4我們把它圈起來， 然後我們用disjunction的方式把它連接起來。 接下來第二步，這裡有兩個命題符號，他需要有兩個位置來填那些formula，所以我們在這裡做conjunction是這樣。 第三步的做法，我們把這些情況裡面如果出現是真，我們就把命題符號寫上去；如果他出現的是假，我們就寫上negation。 第一個情況是P真Q真，所以是(PQ)。 第二個情況是P真Q假，所以是(PQ)。 第四個情況是P假Q假，所以是(PQ)。 這樣我們就完成了一個DNF，我們就找到了這個normal form，而這個語句就是跟若Q則P是等值的語句。
44
Unit 5 真值表法 DNF 的實例(2)，假設某個真值表如 下表所列： P Q T F MP4-1031 00:36:51
這裡有兩個state是真，所以我們把這兩個找出來。
45
Unit 5 真值表法 根據命題邏輯的語意規則，不難發現 實例(2)的句式 其實就是 (PQ) 。
句式 的 DNF 則寫成下列形式： (PQ)(PQ) MP :36:57 我們用DNF的方式， 所以我們只要把那兩個state寫出來，就是(PQ)(PQ)。
46
Unit 5 真值表法 DNF 的實例(3)，假設某個真值表如 下表所列： P Q T F MP4-1031 00:37:14
這個例子既然四個都是真，那就全部把它寫下來。
47
Unit 5 真值表法 根據命題邏輯的語意規則，不難發 現實例(3)的句式 其實就是套套句， 因此可以寫成PP 或 PP等等。
句式 的 DNF 則寫成下列形式： (PQ)(PQ)(PQ)(PQ) MP :37:37 他的DNF就是： (PQ)(PQ)(PQ)(PQ)
48
Unit 5 真值表法 DNF 的實例(4)，假設某個真值表如 下表所列： P Q T F MP4-1031 00:37:52
那如果沒有為真的情況怎麼辦？
49
Unit 5 真值表法 根據命題邏輯的語意規則，不難發 現實例(4)的句式 其實就是矛盾句， 因此可以寫成(PP) 或 PP等等。 由於沒有任何一個狀態使得句式 為真，所以我們無法挑出任何狀態 描述構成句式 的DNF。 MP :38:30 既然是這樣就沒有DNF， 你沒有任何為真的狀態可以描述，所以你就找不到相對應的DNF。
50
Unit 5 真值表法 P Q R 組合狀態描述 T P Q R F P Q ¬R P ¬Q R
MP :38:54 如果碰到三個的時候怎麼辦？
51
Unit 5 真值表法 DNF 的實例(5)，假設某個真值表如下表所列： P Q R T F MP4-1031 00:39:01
我們直接來看例子。 第一步一樣，把所有為真的情況找出來，總共有三種情況為真。 如果為真我們就填原本的命題，如果為假我們就填他的negation。 所以我們得到的DNF就是：(PQ¬R)(P¬QR)(¬PQ¬R) 你用這個方式，不管它是幾元的真值函映數，你都可以用相同的方法把他的等值語句找出來。
52
Unit 5 真值表法 DNF 的實例(5) 當連接詞符號代表的函映關係超過二 元時，我們就無法直接以命題邏輯既 有的語意規則直接找到符合該真值表 的句式 。 不過，透過決定 DNF 的程序，我們可 以找到等值句式 的DNF 。
53
Unit 5 真值表法 實例(5)句式 的 DNF 為下列形式： (PQ¬R)(P¬QR)(¬PQ¬R)
54
Unit 5 真值表法 DNF 的實例(6)，假設某個真值表如下表所列： P Q R T F MP4-1031 00:42:46
我給各位10秒鐘來練習這個題目。
55
Unit 5 真值表法 (PQR)(P¬QR)(¬PQR) (¬PQ¬R)(¬P¬QR)
實例(6)句式 的 DNF 為下列形式： (PQR)(P¬QR)(¬PQR) (¬PQ¬R)(¬P¬QR) MP :43:48 在走到CNF之前，我想跟各位說明一下這件事。
56
Unit 5 真值表法 DNF 的實例(7)，假設某個真值表如下表所列： P Q R T F MP4-1031 00:43:56
如果真值表出現的情況都是F的情況，根據我們剛剛講法是什麼？沒有相對應的DNF對吧。 可是那個我們會不會知道？雖然我們知道他沒有相對應的DNF，可是那個我們隨便寫一個contradiction進去就可以了。 現在問題來了。
57
Unit 5 真值表法 根據命題邏輯的語意規則，實例(7)的 句式 就是矛盾句，因此可以用 (PP)、 (QQ)、 (RR)的形式， 或者 PP、 QQ、 RR等表示句 式。 想想看，語句符號 S 並未出現在真值 表的原子語句中，那麼可以用、 (SS) 或 SS 表達句式 嗎？ MP :44:26 我們如果隨便寫一個contradiction進去會發生這樣的一個情況，我們可以寫成(PP)、 (QQ)、 (RR)、PP、 QQ、 RR，這些都可以對吧？那如果我們出了這樣一個題目，結果有位同學認為寫成SS可以嗎？ 請問各位，他這樣的想法是正確的嗎？ 同學A：「可以，因為符合它是矛盾句。」非常好的理由，因為它本身已經是矛盾句了。 同學B：「倒回去寫真值表。」倒回去寫真值表怎麼寫出來？ C同學找了一個非常好的方法，我們就不要看S，就隨便用P或Q帶進S的位置就好，不要把它當一個formula，把它當作是一個可以取代樣子就可以了。B同學他的回應你接受嗎？ 還是不行？沒關係，我來幫你解釋一下。在這個真值表裡面沒有出現S這個原子命題，所以我們會說S在這個真值表裡面的地位是undefined。 所以他如果沒有出現就會像B同學講的一樣，他其實是undefined。 那C同學講的對不對？好像也蠻符合我們直覺的。所以其實在這裡他會有不同的觀點，並沒有說哪個對哪個錯。
58
Unit 5 真值表法 CNF: 連言標準形式(Conjunctive Normal Form)
MP :50:08 接下來我們要走入CNF。 DNF是要從什麼情況為真來組織DNF，而CNF剛好相反，是我們要從什麼情況為假去組織CNF。 如果你要從假來組織，全部conjunction只要有一個為假，那麼整句話最後得到的真假值就是假。 其實CNF做的方式跟DNF差不多，只是從另一個方向來考慮。
59
Unit 5 真值表法 在真值表中的某行，以原子命題或 其否定組合描述該狀態為假，稱之 為狀態描述。 P Q 組合狀態描述 T
F P Q P Q P Q MP :52:07 CNF和DNF的差別在於狀態描述，剛剛是用conjunction的方式，那我們現在要組織假的部分。 第一個情況是P真Q真，那麼這個state什麼時候為假？只要其中一個為假就可以，所以是P Q。
60
Unit 5 真值表法 決定 CNF 的程序 藉由狀態描述的觀念，我們可以輕易 地找出以該真值表描述的 CNF。
MP :52:47 我們先把出現F的情況找出來，然後把所有F的情況用conjunction的方式連接起來，就是我們要的CNF。
61
Unit 5 真值表法 CNF 的實例(1)，假設某個真值表如下 表所列： P Q T F MP4-1031 00:53:14
62
Unit 5 真值表法 根據命題邏輯的語意規則，實例(1) 的句式其實就是 QP。 句式 的CNF 為： (P Q)
MP :53:31 所以與等值的CNF就是(P Q)。
63
Unit 5 真值表法 CNF 的實例(2)，假設某個真值表如下 表所列： P Q T F MP4-1031 00:53:50
64
Unit 5 真值表法 根據命題邏輯的語意規則，我們會發 現實例(2)的句式 其實就是 (PQ)。 句式 的CNF 為：
(P Q) (P Q) MP :54:05 所以與等值的CNF是(P Q) (P Q)。
65
Unit 5 真值表法 P Q R 組合狀態描述 T ¬P ¬Q ¬R F ¬P ¬Q R ¬P Q ¬R
66
Unit 5 真值表法 CNF 的實例(3)，假設某個真值表如下表所列： P Q R T F MP4-1031 00:54:05
同樣的，如果是三個的，我再帶各位練習一下。 分別有五個F的情況，所以會需要有五個conjunct，這五個conjunct裡面分別都是一個disjunction，他現在要組織的是使他為假的情況，所以我們要放的方式是，如果這個命題符號在這個情況裡面本身就是假，那就直接寫上去。 那如果他是為真的，我們就要放他的negation，跟剛剛DNF的方式剛好相反對吧。 所以第一個情況是(¬P ¬Q ¬R) 第四個情況是(¬P ¬Q R ) 第五個情況是(P ¬Q ¬R ) 第七個情況是(P Q ¬R) 第八個情況是(PQR) 這樣就完成我們所需要的CNF。
67
Unit 5 真值表法 根據實例(3)的真值表，等值於句式 的 CNF 為：
(¬P¬Q¬R)(¬PQR)(P¬Q¬R) (PQ¬R)(PQR) MP :57:14 所以基本上我們可以用這樣的方式解決的一個重要關鍵就是，我們不單單可以用真值表來決定這句話是什麼意思，我們也可以倒過來用真值表來決定這個語句是什麼。 各位如果回去看第五單元的練習，會看到這樣一個題目：(P→Q)→R 我們要找出他相對應的DNF和CNF，那我們應該要怎麼做？ 第一步先把他的真值表寫出來，再利用剛剛我們寫DNF跟CNF的方法把他找出來，那個就是與他等值的DNF跟CNF。
68
Unit 5 真值表法 CNF 的實例(4)，假設某個真值表如下表所列： P Q R T F
69
Unit 5 真值表法 根據實例(4)的真值表，等值於句式 的 CNF 為： (¬P¬QR)(¬PQR)(PQR)
70
Unit 5 真值表法 CNF 的實例(5)，假設某個真值表如下表所列： P Q R T F MP4-1031 00:58:52
71
Unit 5 真值表法 根據命題邏輯的語意規則，實例(5) 句式 是套套句，可以 PP、 QQ、 RR 或 PP、 QQ、 RR 等表達，這些句式均為句式 的等值句式。 由於沒有任何一個狀態使得句式 為假，所以沒有等值於句式 的 CNF。
Similar presentations
