matdis 1.1-1.2 teknik informatika

43
Discrete Mathematics 3 SKS Buku: Discrete Mathematics and Its Applications, Kenneth H Rosen, McGraw-Hill Penilaian: tugas : 25% tes : 25% ets : 25% eas : 25% 1

Upload: bang-satria-hafizhuddin

Post on 14-Jul-2016

33 views

Category:

Documents


3 download

DESCRIPTION

Teknik Informatika

TRANSCRIPT

Page 1: matdis 1.1-1.2 Teknik informatika

Discrete Mathematics3 SKS

Buku:Discrete Mathematics and Its Applications, Kenneth H Rosen, McGraw-Hill

Penilaian:tugas : 25%

tes : 25%ets : 25%eas : 25%

1

Page 2: matdis 1.1-1.2 Teknik informatika

discrete mathematics1. The foundations : Logic and Proofs2. Basic Structures: sets, functions, sequences, sums3. The Fundamentals: algorithms, the integers, matrices4. Induction and Recursion5. Counting6. Discrete Probability7. Advanced Counting Techniques8. Relations9. Graphs10. Trees11. Boolean Algebra12. Modeling Computation13. Appendices

2

Page 3: matdis 1.1-1.2 Teknik informatika

Non-numeric example: Relations:

Anna is taller than Doni Doni is taller than Roy

Anna and Doni have a common grandparent Doni and Roy have a common grandparent

3

Page 4: matdis 1.1-1.2 Teknik informatika

bukan matematika diskrit Koordinator kelas ini: ……………….

Pekerjaan Rumah (homework) harus dikumpulkanpada tanggal yang telah ditentukan; diminta atau tidak. Yang terlambat tanpa pemberi-tahuan tidak diterima. Kertas kerja ukuran folio.

Tidak ada tes susulan, kecuali pada hari tes ada tugas lain (tugas dari jurusan/fakultas/institut)

Semua “permasalahan” diselesaikan sebelum EAS4

Page 5: matdis 1.1-1.2 Teknik informatika

discrete mathematics

TES 1 : 29 September 2014Materi :Waktu : 30 menitSifat : Berdua –

boleh melihat buku

5

Page 6: matdis 1.1-1.2 Teknik informatika

Chapter 1 The Foundations: Logic and Proofs1.1. Propositional Logic1.2. Propositional Equivalences1.3. Predicates and Quantifiers1.4. Nested Quantifiers1.5. Rules of Inference1.6. Introduction to Proofs1.7. Proof Methods and Strategy End-of-Chapter-Material

6

Page 7: matdis 1.1-1.2 Teknik informatika

Propositional Logic

Chapter 1.1.

7

Page 8: matdis 1.1-1.2 Teknik informatika

Proposition A proposition is a declarative sentence

It is either true (1) or false (0), but not both

Propositional variables are denoted by the letters p, q, etc.

Examples : today is Monday1 + 1 = 22 + 2 = 3

Not a proposition: you may be seated a + b = 10

8

Page 9: matdis 1.1-1.2 Teknik informatika

Compound Propositionscompound statements

Let p, q, r be simple propositions

A compound proposition is obtained by “connecting” p, q, r using logical operators

Example: we are studying and it is rainingSurabaya is a city or Malang is an ocean

9

Page 10: matdis 1.1-1.2 Teknik informatika

Logical Operators NOT (negation) Symbol AND (conjunction) Symbol Inclusive OR (disjunction) Symbol v EXclusive OR (XOR) Symbol Conditional statement Symbol (implication) Biconditional (iff) Symbol

10

Page 11: matdis 1.1-1.2 Teknik informatika

Compound Propositions

Example: we are studying and it is rainings = we are studyingr = it is raining“coded” sentence : s r

Surabaya is a city or Malang is an ocean s = Surabaya is a citym = Malang is an ocean “coded” sentence : s v m

11

Page 12: matdis 1.1-1.2 Teknik informatika

Level of Precedence

NEGATION (NOT) CONJUNCTION (AND) DISJUNCTION (OR, XOR) CONDITIONAL BICONDITIONAL

Example: p q r

(p q) r

(p q) (r) 12

Page 13: matdis 1.1-1.2 Teknik informatika

Level of Precedence

NEGATION (NOT) CONJUNCTION (AND) DISJUNCTION (OR, XOR) CONDITIONAL BICONDITIONAL

Example: p q r

1. determine the truth value of r 2. then find the truth value of q r 3. finally find the truth value of p q r

13

Page 14: matdis 1.1-1.2 Teknik informatika

Level of Precedence

NEGATION (NOT) CONJUNCTION (AND) DISJUNCTION (OR, XOR) CONDITIONAL BICONDITIONAL

Example: (p q) r

1.2.3.

14

Page 15: matdis 1.1-1.2 Teknik informatika

Level of Precedence

NEGATION (NOT) CONJUNCTION (AND) DISJUNCTION (OR, XOR) CONDITIONAL BICONDITIONAL

Example: p q r

p (q r)

(p q) r

(p q) (r)15

Page 16: matdis 1.1-1.2 Teknik informatika

more examples

consider these compound propositions:

(p q) r

p (q r)

(p) (q)

p (q r)16

Page 17: matdis 1.1-1.2 Teknik informatika

Truth TableNegation

example: p = today is Tuesday

p = today is not Tuesday

(today is Monday)

p p0 1

1 0

17

Page 18: matdis 1.1-1.2 Teknik informatika

Truth Tableconjunction

p q p q0 0 00 1 01 0 01 1 1

example: p = today is Monday

q = it is raining

p q = today is Monday and it is raining 18

Page 19: matdis 1.1-1.2 Teknik informatika

Truth tabledisjunction (inclusive or)

example: p = John is a student q = Mita is a lawyer

p v q = John is a student or Mita is a lawyer

p q p v q0 0 00 1 11 0 11 1 1

19

Page 20: matdis 1.1-1.2 Teknik informatika

Truth table

p q p q0 0 00 1 11 0 11 1 0

example: p = John is a student q = Mita is a lawyer

p q = either John is a student or Mita is a lawyer

exclusive or

20

Page 21: matdis 1.1-1.2 Teknik informatika

Truth Table (p r)qp q r (p r) q0 0 0 (0 1) 0 = 00 0 1 (0 0) 0 = 00 1 0 (0 1) 1 = 10 1 1 (0 0) 1 = 11 0 0 (1 1) 0 = 11 0 1 (1 0) 0 = 01 1 0 (1 1) 1 = 11 1 1 (1 0) 1 = 1

21

Page 22: matdis 1.1-1.2 Teknik informatika

Truth Table p (r q)p q r p ( r q )0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

22

Page 23: matdis 1.1-1.2 Teknik informatika

Truth Table

implication

p q p q

0 0 1

0 1 1

1 0 0

1 1 1

23

Page 24: matdis 1.1-1.2 Teknik informatika

consistency

Statements / specifications are consistent :

all statements are true one statement should not conflict another

see page 104

24

Page 25: matdis 1.1-1.2 Teknik informatika

Example 15 p. 12

b : the diagnostic message is stored in the buffer t : the diagnostic message is transmitted

Determine whether these system specifications are consistent:

The diagnostic message is stored in the buffer (b)or it is transmitted (t) b t

The diagnostic message is not stored in the buffer bIf the diagnostic message is stored in the buffer,

then it is transmitted b t

25

Page 26: matdis 1.1-1.2 Teknik informatika

Example 15 p. 12

let’s say the three specifications are consistent (all true) b tb

b t

since b is true, b must be false (b = 0)from b t (true) t is true (t = 1)

finally b t (0 1) is true

therefore the system specifications are consistent 26

Page 27: matdis 1.1-1.2 Teknik informatika

Implication Notation : p q

Examples : 1. if 2 + 2 = 4 then x := x + 1

2. if m > 0 then y := 2 * y3. if it is raining then we will not go

Let s denote 2 + 2 = 4 and a denote x := x + 1

The symbolic notation for example 1 : s a27

Page 28: matdis 1.1-1.2 Teknik informatika

Hypothesis & Conclusion

In the implication p q

p is called the antecedent, hypothesis, premise

q is called the consequence, conclusion

28

Page 29: matdis 1.1-1.2 Teknik informatika

Ways to express p q

jika p maka q if p then q jika p, q if p, q q jika p q if p p hanya jika q p only if q p mengimplikasikan q p implies q

see page 6

29

Page 30: matdis 1.1-1.2 Teknik informatika

Necessary & Sufficient conditions p q

is necessary for p

is a sufficient condition for q

30

Page 31: matdis 1.1-1.2 Teknik informatika

Conversion & Inversion The conversion of p q is q p The inversion of p q is p q p q is not equivalent to q p p q is not equivalent to p q

p

q p q q p p q

0 0 1 1 10 1 1 0 01 0 0 1 11 1 1 1 1 31

Page 32: matdis 1.1-1.2 Teknik informatika

contrapositive The contrapositive of p q is q p. p q and q p are equivalent

p q p q q p0 0 1 10 1 1 11 0 0 01 1 1 1

32

Page 33: matdis 1.1-1.2 Teknik informatika

Biconditional p if and only if q

p q

p q p q (p q) (q p)0 0 1 10 1 0 01 0 0 01 1 1 1

33

Page 34: matdis 1.1-1.2 Teknik informatika

Propositional Equivalence

Chapter 1.2.

34

Page 35: matdis 1.1-1.2 Teknik informatika

TautologyA proposition that is always true example: p p v q

p q p p v q

0 0 1

0 1 1

1 0 1

1 1 135

Page 36: matdis 1.1-1.2 Teknik informatika

Contradiction a proposition that is always false

example : p ( p )

p p ( p)0 0

1 0

36

Page 37: matdis 1.1-1.2 Teknik informatika

Logical EquivalenceNotation p q ( p and q are compound propositions )

Example : p q is logically equivalent to p q

p q p q p q

0 0 1 10 1 1 11 0 0 01 1 1 1

37

Page 38: matdis 1.1-1.2 Teknik informatika

Logical Equivalence

See pages 24, 25 Table 6 Table 7 Table 8

38

Page 39: matdis 1.1-1.2 Teknik informatika

De Morgan’s Law (p q) ( p) ( q)

(p q) ( p) ( q)

p q p q pq (pq) (p)(q)

0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 39

Page 40: matdis 1.1-1.2 Teknik informatika

What to do & what not to doExample 6:

show that (p q) and p q are logically equivalent

(p q) ( p q) see slide no. 35 ( p) ( q) De Morgan ( p ) ( q)

p q

40

Page 41: matdis 1.1-1.2 Teknik informatika

What to do & what not to doExample 6: show that (p q) and p q are logically equivalent

(p q) p q ( p q) p q ( p) ( q) p q ( p ) ( q) p q

p q p q

41

Page 42: matdis 1.1-1.2 Teknik informatika

Make sure you read and understand

Examples 7 and Example 8

42

Page 43: matdis 1.1-1.2 Teknik informatika

Homework : hand in September 15, 2014

Chapter 1.1. no. 1-5, 13, 35 – 41

Chapter 1.2. no. 10, 16, 32, 60

You may work in pairs

43