pengenalan matematika komputasi dan matematika diskrit

matematika diskrit

1. Matematika Komputasi Pertemuan II “Logika” By : Arnoldus Yansen Friska Danar Yudhistira, M.Kom [email protected]

2. Logika Perhatikan argumen di bawah ini: Jika anda mahasiswa Informatika maka Anda tidak sulit belajar Bahasa Java. Jika anda tidak suka begadang maka anda bukan mahasiswa Informatika. Tetapi, anda sulit belajar Bahasa Java dan anda tidak suka begadang. Jadi, Anda bukan mahasiswa Informatika. Apakah kesimpulan dari argumen di atas valid? Alat bantu untuk memahami argumen tsb adalah Logika

3. Logika Banyak teorema dalam ilmu Komputer/Informatika yang membutuhkan pemahaman logika Contoh : jika dan hanya jika Bahkan logika adalah jantung dari algoritma dan pemrograman Contoh : if x mod 2 = 0 then x:=x + 1 else x:=x – 1  

4. Logic – For What ? Logic is the basis of all mathematical reasoning, and of all automated reasoning .

5. Proof – For What ? It has practical applications to the design of computing machines, to the specification of systems, to artificial intelligence, to computer programming, to programming languages, and to other areas of computer science, as well as to many other fields of study.

6. LOGIC-PROPOSITION The following are not proposition Instruction ( Kalimat perintah) Question ( Kalimat pertanyaan) Amazement ( Kalimat keheranan) Expectancy ( Kalimat harapan)

7. LOGIC-PROPOSITION No.1 and 4 That is not a statement Statement True (T) False (F) Where is the capital city of Indonesia? Jakarta is the capital city of indonesia 1 + y = x 1 + 2 = 3

8. LOGIC-PROPOSITION We use propositional variables to refer to propositions Usually are lower case letters starting with p (i.e. p, q, r, s, etc.) A propositional variable can have one of two values: true ( T) or false (F) A proposition can be… A single variable: p An operation of multiple variables: p Λ ( q V r )

9. LOGIC-PROPOSITION Statement True (T) False (F) Los Angeles is the capital of the United States of America Nanga Bulik is the capital of Lamandau 1 + 1 = 2 2 + 2 = 3 √ √ √ √ Propositions 2 and 3 are true, whereas 1 and 4 are false.

10. LOGIC-PROPOSITION T ruth Table of Statement (Q) Statement (Q) F T T F

11. LOGIC-OPERATOR Many mathematical statements are constructed by combining one or more propositions. New propositions, called compound propositions (pernyataan gabungan/ pernyataan majemuk), are formed from existing propositions using logical operators. Consider the following examples: p = “Today is Sep, 11” q = “Today is my birthday”

12. NEGATION-PROPOSITION Negation is the opposite (negative value) of the proposition Devoted by “  ” Statement (P) P (Value)  P Ottawa is the capital of the United States of America Nanga Bulik is the capital of Lamandau 1 + 1 = 5 2 + 2 = 4 F T F T T F F T

13. Conjunction-Proposition Conjunction is the proposition from two or more existing proposition who has same value Devoted by “ Λ ” It has True Value when both statement is true, otherwise is false

14. Conjunction-Proposition - Example P Q P Λ Q F F T T F T T F F T F F

15. Disjunction-Proposition Disjunction is the proposition from two or more existing proposition who one of they have true value Devoted by “V”

16. Disjunction-Proposition P Q P V Q F F T T F T T F F T T T

17. Exclusive Or-Proposition Proposition that one of them is true (not both of them are true) Devoted by “ Θ ”

18. Exclusive Or-Proposition P Q P Q F F T T F T T F F F T T

19. Exclusive nor-Proposition Proposition that both of them are true Devoted by “ Θ ”

20. Exclusive Nor-Proposition P Q P Θ Q F F T T F T T F T T F F

21. Implication-Proposition Proposition that means a conditional statement Devoted by “  ” Concept : If.... (PREMISE/ANTECEDENT , Then .... (CONCLUSION)

22. Exclusive Nor-Proposition P Q P  Q F F T T F T T F T T T F

23. Joint denial-Proposition Proposition that means negation from disjunction proposition Devoted by “ ”

24. Joint Denial-Proposition P Q P V Q P Q F F T T F T T F F T T T T F F F

25. Not AND-Proposition Proposition that means negation from conjunction proposition Devoted by “  (.... Λ ...)”

26. Not AND-Proposition P Q P Λ Q  ( P Λ Q) F F T T F T T F F T F F T F T T

27. Biimplikasi-Proposition Proposition that means negation from conjunction proposition Devoted by “  ”

28. Biimplication-Proposition P Q P <> Q F F T T F T T F T T F F

29. Summary Try to understand what they meant, d0 not just memorize the table

30. Translating English “I have neither given nor received help on this exam” Let p = “I have given help on this exam” Let q = “I have received help on this exam” ¬ p Λ ¬q

31. Proposition-Law – Aljabar Proposition Logically Equivalent Proposition that logically equivalent, ex : (p Λ q)  p Λ q p Λ q pq

32. Proposition-Law – Aljabar Proposition

33. Proposition-Law – Aljabar Proposition Tautology Proposition that always have TRUE value, ex : (p Λ q)  p Λ q, pv p Kontradiksi Proposition that always have FALSE value Converse Opposite of proposition p q = qp Inverse Negative proposition p  q = p  q Kontrapositive Opposite of inverse p  q = qp

34. Proof P roof is collection of theorems ( true or correct mathematical statements ) Moreover, because knowing the proof of a theorem often makes it possible to modify the result to fit new situations, proofs play an essential role in the development of new ideas.

35. Proof proofs play essential roles when : we verify that computer programs produce the correct output for all possible input values, we show that algorithms always produce the correct result, W e establish the security of a system, and when we create artificial intelligence.

36. Proof Automated reasoning systems have been constructed that allow computers to construct their own proofs

37. Proof Logically Equivalent-Ex.

38. Proof Logically Equivalent-Ex.

39. Proposition-Law – Aljabar Proposition Example : Proof this statement are logically equivalent using aljabar proposition  ( p) dan p  ( pq) dan pv q P Λ (p v q ) dan P