Post on 14-Jul-2016
description
Discrete Mathematics3 SKS
Buku:Discrete Mathematics and Its Applications, Kenneth H Rosen, McGraw-Hill
Penilaian:tugas : 25%
tes : 25%ets : 25%eas : 25%
1
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
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
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
discrete mathematics
TES 1 : 29 September 2014Materi :Waktu : 30 menitSifat : Berdua –
boleh melihat buku
5
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
Propositional Logic
Chapter 1.1.
7
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
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
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
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
Level of Precedence
NEGATION (NOT) CONJUNCTION (AND) DISJUNCTION (OR, XOR) CONDITIONAL BICONDITIONAL
Example: p q r
(p q) r
(p q) (r) 12
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
Level of Precedence
NEGATION (NOT) CONJUNCTION (AND) DISJUNCTION (OR, XOR) CONDITIONAL BICONDITIONAL
Example: (p q) r
1.2.3.
14
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
more examples
consider these compound propositions:
(p q) r
p (q r)
(p) (q)
p (q r)16
Truth TableNegation
example: p = today is Tuesday
p = today is not Tuesday
(today is Monday)
p p0 1
1 0
17
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
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
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
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
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
Truth Table
implication
p q p q
0 0 1
0 1 1
1 0 0
1 1 1
23
consistency
Statements / specifications are consistent :
all statements are true one statement should not conflict another
see page 104
24
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
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
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
Hypothesis & Conclusion
In the implication p q
p is called the antecedent, hypothesis, premise
q is called the consequence, conclusion
28
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
Necessary & Sufficient conditions p q
is necessary for p
is a sufficient condition for q
30
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
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
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
Propositional Equivalence
Chapter 1.2.
34
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
Contradiction a proposition that is always false
example : p ( p )
p p ( p)0 0
1 0
36
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
Logical Equivalence
See pages 24, 25 Table 6 Table 7 Table 8
38
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
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
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
Make sure you read and understand
Examples 7 and Example 8
42
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