[筆記] 程式必修課!離散數學與演算法 – 13

從網路課程 程式必修課!離散數學與演算法 來淺嚐一下沒機會在課堂上所學的離散數學與演算法。或許對撰寫程式的效能提昇會有些幫助。
notes-essential-programming-discrete-math-algorithms-python-javascript-1


課程相關資訊

[連結]:https://hiskio.com/courses/1196/lectures/133668

本篇範圍:Chapter 4

請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。


內容

演繹法 Deduction Method

1.  [ ( A ^ B ) -> C ] <->  [ A -> ( B -> C )]

無論 A, B, C 的值為何,[ ( A ^ B ) -> C ] 和 [ A -> ( B -> C )] 的結果都相同,是一個 恆真式 ( Tautology )

notes-essential-programming-discrete-math-algorithms-python-javascript-13-1

範例

試證明 ( A -> B ) ^ ( B -> C ) -> ( A -> C )

僅需證明 [ ( A -> B) ^ ( B -> C ) ^ A ] -> C 即可

1. A -> B hypothesis
2. B -> C hypothesis
3. A hypothesis
4. 將 1. 和 3. 進行 mp (modus ponens) ,可推導得到 B
4. 將 2. 和 4. 進行 mp (modus ponens) ,可得到 C

因此 [ ( A -> B) ^ ( B -> C ) ^ A ] -> C 為真,故 ( A -> B ) ^ ( B -> C ) -> ( A -> C )


系列文章

  • [筆記] 程式必修課!離散數學與演算法 – 9
  • [筆記] 程式必修課!離散數學與演算法 – 8
  • [筆記] 程式必修課!離散數學與演算法 – 7
  • [筆記] 程式必修課!離散數學與演算法 – 6
  • [筆記] 程式必修課!離散數學與演算法 – 5
  • [筆記] 程式必修課!離散數學與演算法 – 4
  • [筆記] 程式必修課!離散數學與演算法 – 3
  • [筆記] 程式必修課!離散數學與演算法 – 2
  • [筆記] 程式必修課!離散數學與演算法 – 16
  • [筆記] 程式必修課!離散數學與演算法 – 15
  • [筆記] 程式必修課!離散數學與演算法 – 14
  • [筆記] 程式必修課!離散數學與演算法 – 12
  • [筆記] 程式必修課!離散數學與演算法 – 11
  • [筆記] 程式必修課!離散數學與演算法 – 10
  • [筆記] 程式必修課!離散數學與演算法 – 1
  • 按讚加入粉絲團

    延伸閱讀