[其他] disjunctive normal form

看板Math作者 (善解人衣)時間6年前 (2019/09/23 00:30), 6年前編輯推噓5(5推 0噓 47→)
留言52則, 2人參與, 6年前最新討論串1/1
題目如下 https://i.imgur.com/FGQEq9I.jpg
完全沒有任何想法，上網找到的資料也很少，看了怎麼構造出這個函數(只看T的情況然後 寫出statements)後還是對這個證明沒有感覺，求版上大神了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.253.17 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1569169842.A.CBB.html
推
09/23 01:04, 6年前 , 1F
09/23 01:04, 1F
→
09/23 01:07, 6年前 , 2F
compound proposition 是合成命題的意思，有一個
09/23 01:07, 2F
→
09/23 01:07, 6年前 , 3F
主結構是p->q或p<->q，p和q內部還可以
09/23 01:07, 3F
推
09/23 01:10, 6年前 , 4F
再分解，你看他解答的說明，都可以拆成sum of produ
09/23 01:10, 4F
→
09/23 01:11, 6年前 , 5F
ct的型式
09/23 01:11, 5F
→
09/23 01:12, 6年前 , 6F
sum of product 就是disjunctive normal form
09/23 01:12, 6F
→
09/23 01:13, 6年前 , 7F
名稱未統一，課本應該概念說的很清楚，要看課文
09/23 01:13, 7F
→
09/23 01:15, 6年前 , 8F
sum 是或，product是且 boolean敘述一定長成
09/23 01:15, 8F
→
09/23 01:17, 6年前 , 9F
E=x且y且非z 或 t且非u且w 或 m且n
09/23 01:17, 9F
→
09/23 01:18, 6年前 , 10F
E=x* y *barz + t*baru *w + m * n 之類的樣子
09/23 01:18, 10F
我知道他的形式，但不知道如何證明。。 ※ 編輯: ben102938 (140.114.253.17 臺灣), 09/23/2019 01:29:28
推
09/23 01:31, 6年前 , 11F
網址的敘述就是證明，證明不一定是公式，是用敘述的
09/23 01:31, 11F
應該說他那個方式應該是自己定義出來的吧?我自己是無法被說服，例如他並沒有解釋為 什麼若和若且唯若可以被寫成DNF後所有的也都可以，第二是他為什麼可以把若和若且唯 若直接定義成DNF的形式?依據是什麼? ※ 編輯: ben102938 (140.114.253.17 臺灣), 09/23/2019 01:34:45
→
09/23 01:33, 6年前 , 12F
把SARAH的說明整個看懂默寫出來就是這題的答案
09/23 01:33, 12F
→
09/23 01:34, 6年前 , 13F
你要自己想一下，為什麼所有的敘述都可以拆成SUM
09/23 01:34, 13F
→
09/23 01:35, 6年前 , 14F
OF PRODUCT,
09/23 01:35, 14F
如果僅依據真假值相等就直接定義感覺很不嚴謹，比較equivalent兩邊的東西可以是完全 無關的吧 ※ 編輯: ben102938 (140.114.253.17 臺灣), 09/23/2019 01:38:03
→
09/23 01:37, 6年前 , 15F
P->Q 就是非P或Q，是標準型式。
09/23 01:37, 15F
→
09/23 01:41, 6年前 , 16F
高中有教，這裡的P和Q內部還要拆解，最後會變成一堆
09/23 01:41, 16F
→
09/23 01:42, 6年前 , 17F
和加，再用笛莫根律拉出來
09/23 01:42, 17F
→
09/23 01:43, 6年前 , 18F
P->Q 就是非P或Q是計算真值表，不是定義，P<->同理
09/23 01:43, 18F
→
09/23 01:43, 6年前 , 19F
P<->Q同理
09/23 01:43, 19F
推
09/23 01:45, 6年前 , 20F
09/23 01:45, 20F
→
09/23 01:45, 6年前 , 21F
這是高中要學的東西。
09/23 01:45, 21F
推
09/23 01:51, 6年前 , 22F
真值表相等叫邏輯等價，再BOOLEAN代數裡可看成相等
09/23 01:51, 22F
→
09/23 01:52, 6年前 , 23F
現實不一定相等呀
09/23 01:52, 23F
感覺我還是沒有get到他為什麼要這麼證明的點，或者說我可能還沒理解題目想要我證什 麼，我自己的想法是要我們證在這個規則下得出的function是對的，可以用的? ※ 編輯: ben102938 (140.114.253.30 臺灣), 09/23/2019 07:48:38
→
09/23 08:31, 6年前 , 24F
它是要你證明不管是什麼樣的真值表，都能寫出SOP
09/23 08:31, 24F
所以他預設這樣構造出來的function是可用的，一定正確的(按照題目說的規則構造出這 個函數)後，直接開始說明這種複合命題一定可以寫成DNF? ※ 編輯: ben102938 (140.114.253.30 臺灣), 09/23/2019 08:35:27
→
09/23 08:44, 6年前 , 25F
這個複合命題的真值表會跟題目相同，是要證的部份
09/23 08:44, 25F
所以他的證明並不完全，我還需自己補上是嗎？ ※ 編輯: ben102938 (140.114.253.30 臺灣), 09/23/2019 08:45:40
→
09/23 08:45, 6年前 , 26F
目的是要證明能寫出SOP，只是題目先跟你說了方向
09/23 08:45, 26F
→
09/23 08:46, 6年前 , 27F
就跟c大說的一樣，剩下的東西就是那位寫的東西
09/23 08:46, 27F
→
09/23 08:57, 6年前 , 28F
我大概懂你的疑惑是什麼了，你是想問任何真值表都有
09/23 08:57, 28F
→
09/23 08:57, 6年前 , 29F
複合命題是吧？
09/23 08:57, 29F
啊，是的，一直不知道該怎麼表達 並且昨天遇到一個問題，若我定義一個所有function出來都是false的真值表，那我就找 不到對應的function了 ※ 編輯: ben102938 (140.114.253.30 臺灣), 09/23/2019 09:05:52
→
09/23 09:19, 6年前 , 30F
全部都F，那就是F而已，或者你寫0
09/23 09:19, 30F
→
09/23 09:20, 6年前 , 31F
先問你能接受變數只有2個的時候，全都有對應的命題
09/23 09:20, 31F
→
09/23 09:20, 6年前 , 32F
嗎？
09/23 09:20, 32F
那16種可能我都試過了就ffff的不太理解 ※ 編輯: ben102938 (140.114.253.30 臺灣), 09/23/2019 09:32:23
→
09/23 09:33, 6年前 , 33F
FFFF就0，不用想太多，代表是0個東西加起來
09/23 09:33, 33F
→
09/23 09:33, 6年前 , 34F
那麼今天假設有n個變數，總共有2^n格，你都可以看作
09/23 09:33, 34F
→
09/23 09:36, 6年前 , 35F
n-1個變數函數跟剩下一個變數的組合，這樣就有相對
09/23 09:36, 35F
→
09/23 09:38, 6年前 , 36F
的複合命題，再來就依此類推拆下去
09/23 09:38, 36F
我大概懂了，最後再問一下還是有點疑惑的地方，這邊說的複合命題，然後證明是使用若 跟若且唯若來轉換成DNF，是指每種組合的複合命題都能用這個來表示嗎?能否舉個例子? ※ 編輯: ben102938 (140.114.253.30 臺灣), 09/23/2019 10:02:04
→
09/23 10:03, 6年前 , 37F
是基礎的複合命題中，只有這兩類不是直接寫成SOP的
09/23 10:03, 37F
→
09/23 10:03, 6年前 , 38F
形式，所以特別拿出來講
09/23 10:03, 38F
→
09/23 10:06, 6年前 , 39F
所以你要問的東西是，所有的命題都能用這五類寫出
09/23 10:06, 39F
→
09/23 10:07, 6年前 , 40F
實際上一樣就是變數個數為2的真值表對上去就好
09/23 10:07, 40F
啊。。越來越亂了 ※ 編輯: ben102938 (140.114.253.30 臺灣), 09/23/2019 10:11:57
→
09/23 10:13, 6年前 , 41F
就是p->q跟p<->q這兩個沒有寫成SOP啊，所以特別再說
09/23 10:13, 41F
→
09/23 10:13, 6年前 , 42F
這兩類也都可以寫成SOP而已
09/23 10:13, 42F
應該是說我沒辦法理解p->q,p<->q這兩個在題目要我做的操作裡可以放在那個部份 ※ 編輯: ben102938 (140.114.253.36 臺灣), 09/23/2019 11:08:16
→
09/23 11:13, 6年前 , 43F
是「複合命題」裡面的這兩類並沒有直接寫成SOP的型
09/23 11:13, 43F
→
09/23 11:14, 6年前 , 44F
式，所以寫出它們的SOP形式而已
09/23 11:14, 44F
→
09/23 11:17, 6年前 , 45F
正確來說，你要做的事情是把二元的真值表寫成對應
09/23 11:17, 45F
→
09/23 11:19, 6年前 , 46F
的命題，這樣就能說明都能寫成SOP了
09/23 11:19, 46F
→
09/23 11:38, 6年前 , 47F
等等，我似乎也被帶偏太多了
09/23 11:38, 47F
→
09/23 11:40, 6年前 , 48F
應該先證明二元的時候對，再數學歸納法到三元以上都
09/23 11:40, 48F
→
09/23 11:40, 6年前 , 49F
可以用題目說的方法
09/23 11:40, 49F
→
09/23 11:42, 6年前 , 50F
不過數學歸納法的部份很簡單，就是迪摩根進去而已
09/23 11:42, 50F
→
09/23 11:42, 6年前 , 51F
而證明二元的時候對，就是直接真值表跟對應命題而已
09/23 11:42, 51F
→
09/23 11:45, 6年前 , 52F
上面講錯了，不是迪摩根，是分配律
09/23 11:45, 52F
啊，我完全懂了，但寫出16個的對應命題有點。。 ※ 編輯: ben102938 (140.114.253.36 臺灣), 09/23/2019 11:45:46
‣ 更多 ben102938 的文章
文章代碼(AID): #1TXw6oox (Math)