mat disk 2014 bab 1.4 + 1.5.pptx
TRANSCRIPT
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 1/65
bilqis 1
Bab 1.4 + 1.5
Predicates & Quantifiers
Nested quantifiers
2014
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 2/65
Tujuan
• Dari bahasa anusia diterjeah!an !e
sib"l ateatis
• Dari sib"l ateatis diterjeah!an !e
bahasa anusia
bilqis 2
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 3/65
bilqis #
PREDICATE & QUANTIFIER
SUB-BAB 1.4
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 4/65
bilqis 4
Predi!at dan $un%si Pr""sisi'
P(x) : x > 5Perhati!an ern(ataan P(x)) n"tasi sib"li! dari x > 5
•
X disebut subje! • > 5 disebut redi!at
• P*, belu eun(ai nilai !ebenaran selaa belu
di!etahui- disebut fun%si r""sisi P untu!
• P*, a!an enjadi r""sisi ji!a !eada telah
diberi!an nilai tertentu !eadan(a
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 5/65
bilqis 5
P(x) : x > 5
• !an enjadi r""sisi ji!a telah diberi nilai
tertentu * telah dii!at / bound den%an nilai tertentu,
• Nilai (an% diberi!an !eada diabil darihiunan nilai (an% disebut seesta *universe of
discourse, atau domain
• Dala c"nt"h di atas domain daat berua
hiunan bilan%an bulat / integer
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 6/65
bilqis
Pr""si"nal $uncti"n• Pr""si"nal $uncti"n '
– ebuah !andidat r""sisi
– al. 3% bl jd r"s) !rn terdiri dr satu "r lebih
ar
– N"tas P*,) P*)(, . . . . . .
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 7/65
bilqis
6 ' Pr""si"nal $uncti"n
• 6 '
– P*, 7 2 8 adalah bil %ena) 7 inte%er
– B% nilai !ebenarann(a 9
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 8/65
bilqis :
6 ' Pr""si"nal $uncti"n
• 6 '
– P*, 7 2 8 adalah bil %ena) 7 inte%er
– B% nilai !ebenarann(a 9
– ;<b '
• D"ain 8 7 inte%er ) 7 =1) 2) # . . . .>
• ?"ba diasu!!an seua nilai 8 !e dala P*,
•Tern(ata benar)
• @! nilai !ebenarann(a adalah true
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 9/65
bilqis A
?ara erubah P.$ enjadi
r""sisi• ?ara erubah P.$ enjadi r""sisi '
– Tia ar diberi nilai) atau
– @enjadi!an P.$ enjadi Quantifier
• 6' eberi nilai ada ar
– P*, 7 #) ba%aiana nilai !ebenarann(a
untu! P*4, dan P*2, 9
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 10/65
bilqis 10
?ara erubah P.$ enjadi
r""sisi• ?ara erubah P.$ enjadi r""sisi '
– Tia ar diberi nilai) atau
– @enjadi!an P.$ enjadi Quantifier
• 6' eberi nilai ada ar
– P*, 7 #) ba%aiana nilai !ebenarann(a
untu! P*4, dan P*2, 9 – ;<b '
• P*4, 7 4# nilai !ebenarann(a ' true
• P*2, 7 2# nilai !ebenarann(a ' false
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 11/65
bilqis 11
?ara erubah P.$ enjadi
r""sisi *lanjutan..,• 6' eberi nilai ada ar
– Q*)(, 7 ( + #) ba%aiana nilai
!ebenarann(a untu! Q*1)2, dan Q*#)0, 9
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 12/65
bilqis 12
?ara erubah P.$ enjadi
r""sisi *lanjutan..,• 6' eberi nilai ada ar
– Q*)(, 7 ( + #) ba%aiana nilai
!ebenarann(a untu! Q*1)2, dan Q*#)0, 9 – ;<b '
• Q*1)2, 1 7 2 + # nilai !ebenarann(a ' false
• Q*#)0, # 7 0 + # nilai !ebenarann(a ' true
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 13/65
bilqis 1#
Quant!"#
• elain en%i!at den%an suatu nilai dari domain
tertentu) daat ju%a dii!at den%an quantifier
• Pr"sesn(a disebut quantification
• da # aca quantifiers'
1. Cniersal quantifier
2. 6istential quantifier
#. Cnique quantifier
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 14/65
bilqis 14
Quantifiers•
Quantifiers – Cniersal quantifier ∀
– 6istential quantifier ∃
• Cniersal quantifier ∀
– Artinya :• For all
• For every
–
Ex:∀
x P (x) artinya :• Untuk semua nilai x membuat p(x) menjadibenar
• Untuk setiap nilai x membuat p(x) menjadibenar
• P(x) benar untuk semua nilai x
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 15/65
bilqis 15
Cniersal quantifier ∀
• 6'
– P*n, 7 n2 + 2 n adalah bil %anjil inte%er) ba%aiana
nilai !ebenaran dari ∀ n P(n), dimana
n={inteer!
–
"#b :• P(n) is $alse karena jika n enap, maka %asilnya
jua akan enap & ex' = ($alse)& n = * (true)
• Ex: P(x) = x + - x , bm nilai kebenaran dari
∀ x P(x), dimana x=bil inteer
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 16/65
bilqis 1
Cniersal quantifier ∀
• 6'
– P*n, 7 n2 + 2 n adalah bil %anjil inte%er) ba%aiana
nilai !ebenaran dari ∀ n P(n), dimana
n={inteer!
–
"#b :• P(n) is $alse karena jika n enap, maka %asilnya
jua akan enap & ex' = ($alse)& n = * (true)
• Ex: P(x) = x + - x , bm nilai kebenaran dari
∀ x P(x), dimana x=bil inteer – "#b :
• Apaka% benar untuk semua x membuat P(x)
menjadi benar.
• /ernyata benar, maka ∀ x P(x) bernilai true
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 17/65
bilqis 1
?"untereale
• ?"untereale
– Nilai (% eb P*, enj salah
•
6' – P*n, 7 n2 + 2 n adalah bil %anjil inte%er ) b% nilai
!ebenaran dari ∀ n P(n), dimana n=inteer
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 18/65
bilqis 1:
?"untereale
• ?"untereale
– Nilai (% eb P*, enj salah
•
6' – P*n, 7 n2 + 2 n adalah bil %anjil inte%er ) b% nilai
!ebenaran dari ∀ n P(n), dimana n=inteer
– "#b :
•
= p(n)=0, ternyata pernyataan ini sala%,• 1k n= adala% 2ounterexample untuk P(n)
• 1k ∀ n P(n) bernilai sala%
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 19/65
bilqis 1A
UNI$ERSA% QUANTIFIER
P(x) : x > 5
x P(x) dibahasa!an dei!ian'
Euntu! seua nilai dala domain) 5F
Euntu! seua nilai ebuat P*, enjadi benarF
EP*, benar untu! seua nilai F
a!ah nilai !ebenaran dari ∀ P*, ji!a domain adalah
1. = 1) 2) #) 4) 5 > alah2. = 1..10 > alah
#. = G #) 2) 1) 0) 1) 2) #) G > alah
4. = >
Benar
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 20/65
bilqis 20
UNI$ERSA% QUANTIFIER
• 6 ' Q*, 7 H 2) ba%aiana nilai !ebenaran
quantifier ∀ Q*,) diana d"ain *, adalah real
nuber 9• ;a<ab '
– 8 7 = GG2)#)4)5GGG,
– Q*, tida! benar untu! setia real nuber
– @isal Q*#, false)
– a!a 7# adalah c"untereale untu! ∀ Q*,
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 21/65
bilqis 21
6istential quantifier ∃
•
6istential quantifier ∃ – Artinya :
• For some
• 1inimal ada satu nilai yan membuat menjadibenar
– Ex: ∃ x P (x) artinya :
• 1inimal ada satu nilai x membuat p(x) menjadibenar
• Ex: P(x) = x + - x , bm nilai kebenaran dari ∃ x P(x),
dimana x=bil inteer
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 22/65
bilqis 22
6istential quantifier ∃
•
6istential quantifier ∃ – Artinya :
• For some
• 1inimal ada satu nilai yan membuat menjadibenar
– Ex: ∃ x P (x) artinya :
• 1inimal ada satu nilai x membuat p(x) menjadibenar
• Ex: P(x) = x + - x , bm nilai kebenaran dari ∃ x P(x),
dimana x=bil inteer – "#b :
• Apaka% benar minimal ada satu nilai x membuatP(x) menjadi benar.
•
/ernyata benar, maka ∃ x P(x) bernilai true
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 23/65
bilqis 2#
6istential quantifier ∃
•
Ex: P(x) = x - 3 , bm nilai kebenaran dari ∃ x P(x),dimana x=bil inteer
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 24/65
bilqis 24
6istential quantifier ∃
•
Ex: P(x) = x - 3 , bm nilai kebenaran dari ∃ x P(x),dimana x=bil inteer
– "#b :
• Apaka% benar minimal ada satu nilai x membuatP(x) menjadi benar.
• /ernyata benar, maka ∃ x P(x) bernilai true
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 25/65
bilqis 25
6istential quantifier ∃
•
Ex: P(x) x = x + , bm nilai kebenaran dari∃ xP(x), dimana x=bil inteer
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 26/65
bilqis 2
6istential quantifier ∃
•
Ex: P(x) x = x + , bm nilai kebenaran dari∃ xP(x), dimana x=bil inteer
– "#b :
• Apaka% benar minimal ada satu nilai x membuatP(x) menjadi benar.
• /ernyata tidak ada satu nilaipun untuk x yanbenar, maka ∃ x P(x) bernilai $alse
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 27/65
bilqis 2
EXISTENTIA% QUANTIFIER
P(x) : x > 5
x P(x) dibahasa!an dei!ian'
Einial ada satu nilai (an% ebuat P*, enjadi benarF
a!ah nilai !ebenaran dari P*, ji!a domain adalah
1. = 1) 2) #) 4) 5 > salah
2. = 1..10 > benar #. = G #) 2) 1) 0) 1) 2) #) G > benar
4. = > benar
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 28/65
bilqis 2:
UNIQUE QUANTIFIER
P(x) : x > 5
! x P(x) dibahasa!an dei!ian'
Ehan(a ada 1 nilai (an% ebuat P*, enjadi benarF
a!ah nilai !ebenaran dari ! P*, ji!a domain adalah
1. = 1) 2) #) 4) 5) > benar
2. = 1..10 > salah#. = G #) 2) 1) 0) 1) 2) #) G > salah
4. = > benar
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 29/65
bilqis 2A
$ARIABE% TERIAT' $ARIABE% BEBAS' SCOPE
?"nt"h 1' P(x) : x > 5
dala r""sisi P*4,) ∀ P*,) ∃ P*,
ariabel disebut ariabel teri!at
P(4) ' dii!at "leh nilai 4
x P(x) ' dii!at "leh x
x P(x) ' dii!at "leh x
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 30/65
bilqis #0
$ARIABE% TERIAT' $ARIABE% BEBAS' SCOPE
?"nt"h 2' P(x' ) : x > 5
P(4' ) adalah ariabel teri!at *"leh 4,( disebut ariabel bebas
P(x' ) disebut ariabel bebas ( dii!at "leh ∀(
x P(x' ) dii!at "leh ∃( disebut ariabel bebas
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 31/65
bilqis #1
$ARIABE% TERIAT' $ARIABE% BEBAS' SCOPE
?"nt"h #' x * P(x)∨
Q(x) +∧
x R(x)
scope dari x adalah I P*,∨
Q*, J
scope dari x adalah K*,
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 32/65
bilqis #2
NE,ASI
Cnt:1. eua ahasis<a di !elas ini lulus dala ata!uliah
$isi!a.
2. Tida! seua ahasis<a di !elas ini lulus dala
ata!uliah $isi!a.
D"ain *, 7 = ahasis<a di !elas ini >
$*, ' lulus dala ata!uliah $isi!a
1. ∀ $*,2. ¬∀ $*, e!ialen den%an ∃ I¬ $*,J
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 33/65
bilqis ##
NE,ASI
Cnt:
1. da ahasis<a dari @ala(sia di !elas ini.
2. Tida! ada ahasis<a dari @ala(sia di !elas ini.
D"ain *, 7 = ahasis<a di !elas ini >
@*, ' dari @ala(sia
1. ∃ @*,
2. ¬ ∃ @*, e!ialen den%an ∀ I¬ @*,J
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 34/65
6. 20 hal 4
• What are the negations of thestatements
– “There is an honest politician” and – “All Americans eat cheeseburgers”?
bilqis #4
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 35/65
;a<ab
• D"ain *, 7 "litician
• L *, 7 is h"nest
• ∃ 8 L *, 7 there is an h"nest "litician
• Ne%atif
• M ∃ 8 L *, e!ialen ∀ I¬ L*,J
• 7 6er( "litician is dish"nest
bilqis #5
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 36/65
;a<ab
• D"ain *, 7 aericans
• ? *, 7 eat bur%ers
• ∀ 8 ? *, 7 ll aericans eat bur%ers
• Ne%atif
• M ∀ 8 ? *, e!ialen ∃ I¬ ?*,J
• 7 there is aericans d"es n"t eat bur%ers
bilqis #
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 37/65
bilqis #
NE,ASI
Ne%asi Pr""sisie!ialen
TKC6 $6*ne%asi,
¬∃ P*,
¬∀
P*,
∀ *¬
P*,,
∃
*¬
P*,,
untu! seua )P*, salah
ada suatu nilai (an% ebuatP*, salah
ada suatu nilai (an% ebuatP*, benar
untu! seua )P*, benar
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 38/65
bilqis #:
r""sisi TKC6 $6 *ne%asi,
∀ ∀( P*) (,
∀( ∀ P*) (,
P*) (, benar untu! seua asan%an dan (
da asan%an dan ( (an%ebuat P*) (, salah
∀ ∃( P*) (, Cntu! tia ada suatu ( (an%ebuat P*) (, benar
da (an% ebuatP*) (, salah untu! tia (
∃ ∀( P*) (, da (an% ebuat P*) (, benar untu! tia (
Cntu! tia ada suatu ((an% ebuat P*) (, salah
∃ ∃( P*) (,
∃ ∃( P*) (,
da asan%an dan ( (an%ebuat P*) (, benar
P*) (, salah untu! seua asan%an dan (
Kin%!asan untu! 2 quantifiers
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 39/65
6 ' 2# hal 4:
• 6ress the stateent E6er( student in this
class has studied calculusF usin% redicates
and quantifiers.
bilqis #A
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 40/65
;a<ab
• 8 7 student in this class subject
• ? * , 7 studied calculus
• ∀ ? *, 7 eer( student in this class has
studied calculus
bilqis 40
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 41/65
;a<aban lain
• 8 7 student
• *, 7 in this class
• ? * , 7 studied calculus
• ∀ * *, ? *,, 7 eer( student) if in
this class then has studied calculus
bilqis 41
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 42/65
6. 2 hal 50
• ?"nsider these stateents. The first t<" are
called premises and the third is called the
conclusion. The entire set is called anargument .
– Ell li"ns are fierce.F
–
E"e li"ns d" n"t drin! c"ffee.F – E"e fierce creatures d" n"t drin! c"ffee.F
bilqis 42
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 43/65
;a<ab
• D"ain *, 7 anial
• P *, 7 is li"n
• Q *, 7 is fierce
• K *, 7 drin!s c"ffee
• Oe can eress these stateents as'
– ∀ x(P(x) Q(x)).
– ∃ x(P(x) ∧ ¬ R(x)).
– ∃ x(Q(x) ∧ ¬ R(x)).
bilqis 4#
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 44/65
6. 2 hal 51
• ?"nsider these stateents) "f <hich the first
three are reises and the f"urth is a alid
c"nclusi"n. – Ell huin%birds are richl( c"l"red.F
– EN" lar%e birds lie "n h"ne(.F
–
EBirds that d" n"t lie "n h"ne( are dull inc"l"r.F
– ELuin%birds are sall.F
bilqis 44
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 45/65
;a<ab
• D"ain *, 7 all creature
• P *, 7 is li"n
• Q *, 7 is fierce
• K *, 7 drin!s c"ffee
• Oe can eress the stateents in the ar%uent as
• ∀ x(P(x) S(x)).
• ¬∃ x(Q(x) ∧ R(x)).
• ∀ x( ¬ R(x)¬ S(x)).
• ∀ x(P(x)¬ Q(x)).
– all 7 n"t lar%e
–Dull in c"l"r 7 n"t richl( c"l"red bilqis 45
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 46/65
bilqis 4
1.5 N"/t"0 Quant!"#/
PRPSISI DEN,AN
BEBERAPA QUANTIFIER
n%%a domain adalah hiunan bilan%an n(ata*real numbers,
1.
x * + ( 7 ( +,
2. x * + ( 7 0,
3.
x * + ( 7 0,
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 47/65
bilqis 4
D"uble ariable•
6' P*)(, +( 7 (+ – B% nilai !ebenaran untu! ∀ x ∀ y P(x,y),
dimana x,y = inteer .
– "#b :• Cntu! seua dan untu! seua () aa!ah ebuat
P*)(, benar 9 a!ah +(7(+ adalah benar 9
• Tern(ata benar) a!a r""sisi ini berniali benar
•
6' Q*)(, +( 7 0 – B% nilai !ebenaran untu! '
• ∃ ( ∀ x 4(x,y)
• ∀ x ∃ ( 4(x,y)
• 5imana x,y adala% inteer
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 48/65
bilqis 4:
• ;<b ' – ∃ ( ∀ x 4(x,y) :
• 1in ada nilai y untuk semua6setiap nilai xyan membuat 4(x,y) benar
• Ada y yan membuat 4(x,y) benar untuk tiap x
• 1is y=, mk x = 7 , pada%al se%arusnya ini
bisa untuk sembaran nilai x, maka• Proposisi ini bernilai $alse
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 49/65
bilqis 4A
• ;<b ' – ∀ x ∃ ( 4(x,y)
• Untuk semua nilai x min ada nilai y ymembuat 4(x,y) benar
• Untuk tiap nilai x ada satu y yan membuat4(x,y) benar
• 1is x=, mk y=7• 1is x=3, mk y=73
• 1k =- proposisi ini bernilai true
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 50/65
bilqis 50
Trile ariable•
6' Q*)(), +( 7 – B% nilai !ebenaran untu! '
• ∀ x ∀ y ∃ 4(x,y,8)
• ∃ x ∀ y ∀ 4(x,y,8)
• 5imana x,y,8 adala% inteer
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 51/65
bilqis 51
• ;<b ' – ∀ x ∀ y ∃ 4(x,y,8) :
• 1in ada nilai 8 untuk semua6setiap nilai x dany yan membuat 4(x,y,8) benar
• 1is y= dan x = 3 , maka 8 = *
• Proposisi ini bernilai benar
– ∃ x ∀ y ∀ 4(x,y,8)• 1in ada nilai x untuk semua nilai y dan 8 yan
membuat 4(x,y,8) benar
• 1Emba2a dari kiri ke kanan,
• "adi x = apaka% bisa untuk sembaran nilai ydan 8 , ja#aban tidak
• 1k =- proposisi ini bernilai $alse
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 52/65
@enerjeah!an bhs in%%ris
l"%ical eressi"n• E6er( student in this class has studied
calculusF
• ;a<ab – D"ain *, 7 student in this class
– ? *, 7 has studied calculus
–"%ical 6ressi"n *6, ∀ x 9 (x)
bilqis 52
• Ell li"ns are Rerce.F
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 53/65
ll li"ns are Rerce.
• E"e li"ns d" n"t drin! c"ffee.F
• E"e Rerce creatures d" n"t drin! c"ffee.F
• ;a<ab '
– D"ain *, 7 anial
– P*, 7 is a li"n
– Q*, 7 is fierce
– K *, 7 drin!s c"ffee
– 6
• ∀ x ( p(x) (x)• ∃ * *, S M r*8,, tida! b"leh ∃ **8, Mr*8,) !arena
a!an true ji!a bu!an li"n) seharusn(a inial ada 1 li"n
• ∃ * q*, S M K*8,,
bilqis 5#
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 54/65
6.
Translate the stateent
EThe su "f t<" "sitie inte%ers is al<a(s
"sitieFint" a l"%ical eressi"n.
bilqis 54
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 55/65
;a<aban ertaa
• E$"r eer( t<" inte%ers) if these inte%ers are b"th "sitie) then the su "f
these inte%ers is "sitie.F
• Net)<e intr"duce the ariables and ( t" "btain
• E$"r all "sitie inte%ers and () +( is "sitie.F
• ?"nsequentl()
• D"ain all inte%er
• ∀ (** 0, *( 0, * +(0,,) ∀ ∧
bilqis 55
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 56/65
;a<aban !edua
–D"ain "sitie inte%ers.
– EThe su "f t<" "sitie inte%ers is
al<a(s "sitieF bec"es – E$"r eer( t<" "sitie inte%ers) the su
"f these inte%ers is "sitie.
– ∀ (*+(0, ∀
bilqis 5
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 57/65
6. A
• Translate the stateent
• ∀*?*, (*?*(, $*)(,,, int" 6n%lish)∨∃ ∧
• Ohere – d"ain f"r b"th and ( all students in ("ur sch""l.
– ?*,is E has a c"uter)F
– $*)(,is E and ( are friends)F and the
• "luti"n'
• f"r eer( student in ("ur sch""l) has a c"uter "r
there is a student ( such that ( has a c"uter and and (are friends. atau
• eer( student in ("ur sch""l has a c"uter "r has a friend
<h" has a c"uter. bilqis 5
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 58/65
6. 10• Translate the stateent
• ∃ ( **$*)(, $*), *( ,,U$*(),,∀ ∀ ∧ ∧ en%lish• <here
– d"ain f"r ) () and "f all students in ("ur sch""l
– $*a)b,eans a and b are friends and the.
•"luti"n'
• *$*)(, $*), *( ,,U$*(),.∧ ∧ if students and ( are
friends) and students and are friends) and further"re) if ( and
are n"t the sae student) then ( and are n"t friends.
•;a<abann(a there is a student such that f"r all students ( andall students "ther than () if and ( are friends and and are
friends) then ( and are n"t friends.
• Vn "ther <"rds) there is a student n"ne "f <h"se friends are als"
friends <ith each "ther. bilqis 5:
6 11
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 59/65
6. 11• 6ress the stateent
• EVf a ers"n is feale and is a arent) then this ers"n is s"e"neWs
"therF.• "luti"n'
• aa artin(a den%an $"r eer( ers"n ) if ers"n is feale and
ers"n is a arent) then there eists a ers"n ( such that ers"n is
the "ther "f ers"n (.F
• r""siti"nal functi"ns – D"ain 7 ers"n
– $*,E is feale)F
– P*, E is a arent)F and
– @*)(, E is the "ther "f (.F
• ∀**$*, P*,, (@*)(,,.∧ ∃
• <e can "e ( t" the left) because ( d"es n"t aear in∃
$*, P*,.∧
•
Lasil a!hir (**$*, P*,, @*)(,,.∀ ∃ ∧ bilqis 5A
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 60/65
6. 12
• 6ress the stateent E6er("ne has eactl( "ne best friendF as a
l"%ical eressi"n in"lin% redicates) quantiRers <ith a d"ain
c"nsistin% "f all e"le) and l"%ical c"nnecties.
• "luti"n' The stateent E6er("ne has eactl( "ne best friendF can be
eressed as E$"r eer( ers"n ) ers"n has eactl( "ne bestfriend.F Vntr"ducin% the uniersal quantiRer) <e see that this stateent
is the sae as E *ers"n has eactl( "ne best friend,)F <here the ∀
d"ain c"nsists "f all e"le. T" sa( that has eactl( "ne best friend
eans that there is a ers"n ( <h" is the best friend "f ) and
further"re) that f"r eer( ers"n ) if ers"n is n"t ers"n () then is n"t the best friend "f . Ohen <e intr"duce the redicate B*)(, t"
be the stateent E( is the best friend "f )F the stateent that has
eactl( "ne best friend can be reresented as (*B*)(, ** 7∃ ∧∀
(,UB*),,,. ?"nsequentl() "ur "ri%inal stateent can be eressed
as (*B*)(, ** 7 (,UB*),,, ∀ ∃ ∧∀ bilqis 0
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 61/65
6. 1#
• Cse quantiRers t" eress the stateent EThere is a
<"an <h" has ta!en a Xi%ht "n eer( airline in the
<"rld.F
• "luti"n' et P*<)f,be E< has ta!en fF and Q*f)a, be Ef is a
Xi%ht "n a.F Oe can eress the stateent as
< a f*P*<)f, Q*f)a,,)∃ ∀ ∃ ∧
<herethed"ains"fdisc"ursef"r<)f)anda
c"nsist"fallthe<"eninthe<"rld)allairlane Xi%hts) and all
airlines) resectiel(. The stateent c"uld als" beeressed as < a fK*<)f)a,) <here K*<)f)a,is E< has∃ ∀ ∃
ta!en f "n a.Flth"u%h this is "re c"act) it s"e<hat
"bscures the relati"nshis a"n% the ariables.
?"nsequentl() the Rrst s"luti"n is usuall( referable. Y bilqis 1
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 62/65
6. 14• 6ress the ne%ati"n "f the stateent (*( 7 1,∀ ∃
s" that n" ne%ati"n recedes a quantiRer. "luti"n'
B( successiel( al(in% De @"r%anWs la<s f"r
quantiRers in Table 2 "f ecti"n 1.4) <e can "ethe ne%ati"n in U (*( 7 1, inside all the∀ ∃
quantiRers. Oe Rnd thatU (*( 7 1, is∀ ∃
equialent t" U (*( 7 1,) <hich is equialent∃ ∃
t" (U*( 7 1,. Because U*( 7 1, can be∃ ∀eressed "re sil( as ( 7 1) <e c"nclude that
"ur ne%ated stateent can be eressed as (*(∃ ∀
7 1,. bilqis 2
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 63/65
6. 15• Cse quantiRers t" eress the stateent that EThere d"es n"t eist a
<"an <h" has ta!en a Xi%ht "n eer( airline in the <"rld.F
• "luti"n' This stateent is the ne%ati"n "f the stateent EThere is a
<"an <h" has ta!en a Xi%ht "n eer( airline in the <"rldF fr"
6ale 1#. B( 6ale 1#) "ur stateent can be eressed asU < a f*P*<)f, Q*f)a,,) <here P*<)f,is E< has ta!en fF and Q*f)a, is∃ ∀ ∃ ∧
Ef is a Xi%ht "n a.F B( successiel( al(in% De @"r%anWs la<s f"r
quantiRers in Table 2 "f ecti"n 1.4 t" "e the ne%ati"n inside
successie quantiRers and b( al(in% De @"r%anWs la< f"r ne%atin% a
c"njuncti"n in the last ste) <e Rnd that "ur stateent is equialent t"
each "f this sequence "f stateents' <U a f*P*<)f, Q*f)a,, ∀ ∀ ∃ ∧
Z < aU f*P*<)f, Q*f)a,, Z < a fU*P*<)f, Q*f)a,, ∀ ∃ ∃ ∧ ∀ ∃ ∀ ∧
Z < a f*UP*<)f, UQ*f)a,,. This last stateent states E$"r eer( ∀ ∃ ∀ ∨
<"an there is an airline such that f"r all Xi%hts) this <"an has n"t
ta!en that Xi%ht "r that Xi%ht is n"t "n this airline.F bilqis #
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 64/65
• Tu%as el""!
– cari 2 s"al dan ja<aban di internet (an%
berhubun%an den%an ateri t ini – Tulis alaat internetn(a
– Di !iri !e bilqis[itssb(.edu) tera!hir
• @in%%u) 21 eteber 2014 ja 1.00
• $"rat subject + naa file
– atdis!?tu%as\1a<ar
– Bentu! t inf"rasi naa !el""! +
an%%"ta bilqis 4
7/16/2019 mat disk 2014 bab 1.4 + 1.5.pptx
http://slidepdf.com/reader/full/mat-disk-2014-bab-14-15pptx 65/65
PK
• ?ari di internet catat alaatn(a
• 1 c"nt"h s"al ' ada beberaa !aliat
*inial #, (an% salin% berhubun%an danterjeah!an !e dala quantifier
• Bentu! file PPT + naa !el""!
• Di!uul!an di freeshare