discrete mathematics

Kuantor
1.      Semesta  Pembicaraan
Definisi :
Semesta pembicara itu menguraikan sifat-sifat dari, dan hubungan antara obyek-obyek. Obyek-obyek ini dapat berupa apa saja, seperti orang-orang, benda- benda, binatang, bilangan dan lain sebagainya. Keseluruhan obyek-obyek yang dibicarakan disebut “semesta pembicara ” disingkat semesta saja.
Pada setiap pembicaraan matematika, orang selalu mulai dengan menetapkan lebih dahulu semesta pembicara nya. Sebab benar atau salahnya suatu ucapan tergantung pada semesta pembicara nya. 

Contoh:
Suatu pernyataan  x2  + 1 = 0 mempunyai penyelesaian” tidak mempunyai nilai benar atau salah sebelum terlebih dahulu ditentukan semesta pembicara nya. Jika semesta pembicaranya himpunan bilangan-bilangan riil (nyata), maka pernyataan di atas bernilai salah. Tetapi jika semesta pembicaranya himpunan bilangan-bilangan kompleks, maka pernyataan bernilai benar.

2.      Variabel dan konstanta

Definisi :

Variabel adalah simbol yang menunjukan suatu anggota yang belum spesifik dalam semesta pembicaraan. Sedangkan konstanta adalah simbol yang menunjukan suatu anggota tertentu (yang sudah spesifik) dalam semesta pembicaraan Untuk dapat berbicara tentang anggota tertentu dari semestanya, diperlukan suatu simbol atau tanda yaitu suatu nama dari anggota tersebut.
 
Contoh:
Misalnya ada pernyataan “Niken”, “Ais”, “Aji” adalah nama orang, dimana
semestanya adalah himpunan orang-orang. 

Jika semestanya himpunan bilangan-bilangan, maka angka 5, angka 211 adalah
suatu simbol untuk bilangan-bilangan yang disajikan. 


Simbol seperti itu disebut Konstanta. Jadi  konstanta adalah suatu simbol atau tanda yang diucapkan atau ditulis untuk menunjukkan tentang anggota tertentudarisemestanya.

Jika hendak berbicara tentang anggota sembarang dari semestanya, maka diperlukan suatu tanda-tanda lain dari konstanta. Tanda demikian yang dimaksud
adalah  variabel (atau perubah). Jadi variabel adalah suatu simbol atau tanda yang
digunakan untuk menunjuk pada anggota sembarang dari semesta pembicaranya.

3.      Pernyataan Terbuka

Pernyataan-pernyataan dalam contoh  di atas disebut kalimat (pernyataan) terbuka. Jika variabel dalam kalimat terbuka sudah diganti dengan
konstanta yang sesuai, maka pernyataan yang terjadi dikatakan sebagai pernyataan tertutup.

Definisi :

Pernyataan terbuka adalah suatu pernyataan yang memuat variabel, dan jika variabel tersebut diganti konstanta yang sesuai dengan semestanya maka pernyataanya akan bernilai benar saja atau salah saja.
Jadi pernyataan terbuka merupakan pernyataan yang belum mempunyai nilai kebenaran, belum bernilai benar atau salah. 

Kita misalkan pernyataan terbuka ini dengan  simbol/notasi “p(x)”. Huruf “p”, “q” , ….dan seterusnya disini hanyalah sebuah simbol/notasi dalam pengkajian suatu sifat, hanya untuk mempermudah dalam pembicaraan selanjutnya. Misalnya:
“p (x)” ini merupakan kalimat terbuka, dan diucapkan sebagai “obyek x mempunyai sifat p”. Variabel yang terdapat dalam rangkaian tanda “p(x)” disebut variabel bebas.  Disini “p(x)” , tidak bernilai benar atau salah. Pernyataan ini disebut pernyataan terbuka.

Agar pernyataan terbuka “p(x)” ini mempunyai nilai  salah atau benar (yaitu
menjadi pernyataan deklaratif), maka jika perlu semua variabel bebas di dalamnya
diganti dengan suatu konstanta. Ada cara yang lazim digunakan untuk merubah.
pernyataan terbuka ini menjadi pernyataan deklaratif, yaitu dengan membubuhkan
suatu kuantor. Yang dimaksud kuantor disini adalah kuantor universal atau kuantor eksistensial di depan pernyataan “p(x)”.

4.      Kuantor dengan dua variabel atau lebih


Kerap kali ditemukan suatu pernyataan berkuantor yang melibatkan beberapa variabel.

Contoh:
"x"y, x+y=y+x identik dengan "y"x, x+y=y+x
"x"y, xy=yx identik dengan "y"x, xy=yx
"x"y"z, x+(y+z)=(x+y)+z
$x$y bilangan bulat, x+y=6, identik dengan $y$x bilangan bulat, x+y=6

Pertukaran letak kuantor tidak selalu identik.
Soal: Benarkah yang berikut, apakah identik?
"x$y bilangan bulat, x+y=17
$y"x bilangan bulat, x+y=17

Contoh:
Misalkan himpunan semesta adalah {1, 2, 3}.
Periksa kebenaran setiap pernyataan berikut:
1.      $x "y, x2 < y + 1
2.      "x $y, x2 + y2 < 12
3.      "x "y, x2 + y2 < 12



Pernyataan
Bilamana benar?
Bilamana salah?

"x"y P(x,y)
P(x,y) benar untuk setiap pasang x,y
Ada sepasang x,y yang menyebabkan P(x,y) salah
"x$y P(x,y)
Untuk setiap x ada y sehingga P(x,y) benar
Ada x sedemikian sehingga P(x,y) salah untuk setiap y
$x"y P(x,y)
Ada x sehingga P(x,y) benar untuk setiap y
Untuk setiap x ada y sehingga P(x,y) salah
$x$y P(x,y)
$y$x P(x,y)

Ada sepasang x,y sehingga P(x,y) benar
P(x,y) salah untuk setiap pasang x,y

Pengertian Kuantor
Banyak teorema dalam matematika, khususnya teori bilangan, dimulai dengan “Untuk setiap n bilangan bulat, berlaku ..... “.
Untuk membuktikan bahwa suatu kuantor universal adalah BENAR, biasanya digunakan metode induksi lengkap. Yakni: buktikan benar untuk n=1; anggap benar untuk n=k; dan akhirnya buktikan benar untuk n=k+1.
            Untuk membuktikan bahwa suatu kuantor universal adalah SALAH, cukup diberikan sebuah contoh yang menyangkal pernyataan tersebut. Contoh penyangkalan ini disebut counter example.
Perhatikan dua pernyataan berikut:
  1. Semua planet dalam sistem tata surya mengelilingi matahari.
  2. Ada ikan di laut yang menyusui.
Pernyataan yang mengandung kata semua atau setiap seperti pada pernyataan (1) disebut pernyataan berkuantor universal (kuantor umum). Ungkapan untuk semua atau untuk setiap, disebut kuantor universal atau kuantor umum. Sedangkan pernyataan yang mengandung kata ada atau beberapa seperti pada pernyataan (2) disebut pernyataan berkuantor eksistensial (kuantor khusus). Ungkapan beberapa atau ada disebut kuantor eksistensial atau kuantor khusus. 
Negasi Pernyataan Berkuantor

~($x, p(x)) º "x, ~p(x)
~("x, p(x)) º $x, ~p(x)
Contoh:
Carilah negasi dari:
a.         Jika dosen tidak hadir, maka semua mahasiswa merasa senang.
b.        Jika peraturan tidak dilaksanakan secara adil, maka ada sejumlah mahasiswa yang tidak puas.

Bilamanakah kuantor universal bernilai benar/salah? Bilamanakah kuantor eksistensial bernilai benar/salah?


Contoh :
Bayangkan Anda sedang berada di pinggir kolam yang tenang, banyak binatang berada di sekitar Anda. Ada tupai meloncat, serangga berbunyi, dan burung beterbangan. Lalu perhatian Anda tertuju ke sekelompok angsa. Dalam benak Anda terpikir, "semua angsa berwarna putih". Pernyataan Anda bisa disangkal kalau ternyata ada satu saja angsa yang
tidak berwarna putih. Ketika ternyata ada satu saja angsa yang tidak berwarna putih, pernyataan Anda mengenai "semua angsa berwarna putih" akan disangkal dengan "ada angsa yang tidak berwarna putih". Dan itulah contoh negasi dari sebuah pernyataan berkuantor.

Kuantor Universal Dan Kuantor Eksistensial.
  1. Fungsi Pernyataan
             Suatu fungsi pernyataan adalah suatu pernyataan terbuka di dalam
semesta pembicaraannya. Fungsi pernyataan merupakan suatu kalimat terbuka
yang dinyatakan sebagai “p(x)” yang bersifat bahwa  p(a) bernilai benar atau salah
tetapi tidak keduanya untuk setiap a    semesta pembicaraannya. Ingat disini p(a)
suatu pernyataan. 

Contoh  :

Misalnya: fungsi pernyataan “p(x) = 1+ x > 5 ”

Disini p(x) akan merupakan fungsi pernyatan pada A = himpunan bilangan
asli. Tetapi p(x) bukan merupakan fungsi pernyataan pada K = himpunan bilangan
kompleks.

Contoh  :

a)  Jika  p(x) = 1 + x > 5 didefinisikan pada A = himpunan bilangan asli, maka
p(x) bernilai benar untuk x = 5,6,7, ...

b) Jika  q(x) = x + 3 < 1 didefinisikan pada A = himpunan bilangan asli, tidak
ada x yang menyebabkan q(x) bernilai benar.

c) Jika  r(x) = x + 3 > 1 didefinisikan pada A = himpunan bilangan asli, maka
r(x) bernilai benar untuk x = 1,2,3, ...  

Dari contoh di atas terlihat bahwa fungsi pernyataan p(x) yang didefinisikan
pada suatu himpunan tertentu akan bernilai benar untuk  semua anggota semesta
pembicaraan,  beberapa  anggota semesta pembicaraan, atau  tidak ada  anggota
semesta pembicaraan yang memenuhi.

  1. Kuantor Umum (Universal)
Simbol " yang dibaca “untuk semua” atau “untuk setiap”disebut kuantor
umum (universal). Jika  p(x) adalah fungsi proposional pada suatu himpunan A
(himpunan A adalah semesta pembicaraanya) maka ("x  Œ A) p(x) atau  "x, p(x)
atau  "x p(x) adalah suatu pernyataan yang dapat dibaca sebagai “Untuk setiap x
elemen dalam himpunan A,  p(x) merupakan pernyataan yang benar”. atau “Untuk
semua x, berlaku p(x)”.


Beberapa macam ucapan-ucapan yang mempunyai arti sama diantaranya:

 ("x Œ A) p(x)  dibaca :   • Untuk setiap x Œ A berlakulah x mempunyai sifat p 
     •  Semua x, berlaku p(x)
    • Tiap-tiap x, x memenuhi sifat   p(x).

Contoh:
Misalnya pernyataan p(x) = x tidak kekal
p(manusia) = Manusia tidak kekal

maka  x p(x) atau  x, p(x) atau   x x {manusia}, p(x) = semua manusia
tidak kekal (Benar).
Perhatikan:
Bahwa p(x) merupakan kalimat terbuka (tidak mempunyai nilai kebenaran). 

Tetapi  x p(x)  merupakan pernyataan (mempunyai nilai benar atau salah tetapi
tidak kedua-duanya).
Cara lain untuk menulis , Untuk setiap x,p(x) adalah Untuk semua x,p(x) dan Untuk sembarang x,p(x).
Simbol   bisa dibaca “untuk setiap ”,”untuk semua”,”untuk sembarang”.
Cara lain untuk menuliskan Untuk beberapa x,p(x) adalah Untuk paling sedikit satu x,p(x) dan terdapat x yang sedemikian sehingga p(x).
Simbol  bisa dibaca “untuk beberapa”,untuk paling sedikit”,”terdapat”.
Kadang- kadang untuk menentukan Daerah Asal D, kita tuliskan pernyataan kuantor universal sebagai Untuk setiap x di D,p(x) dan kita tuliskan pernyatan kuantor eksistensial sebagai Untuk beberapa x,di D ,p(x).

Contoh :   x r(x) =  x (x+3>1) pada A = {bilangan asli} bernilai benar.

Contoh :   x q(x) =  x (x+3<1) pada A = {bilangan asli} bernilai salah.

v   Negasi dari pernyataan kuantor universal:
~[x, p(x)] ≡ x, ~p(x)
Contoh:
Negasi dari pernyataan
"Semua planet dalam sistem tata surya mengelilingi matahari”. adalah "Ada planet dalam sistem tata surya yang tidak mengelilingi matahari."

c.  Kuantor Khusus (Eksistensial)

Simbol $ dibaca “ada” atau “untuk beberapa” atau “untuk paling sedikit
satu” disebut  kuantor khusus. Jika  p(x) adalah fungsi pernyataan pada himpunan
tertentu A (himpunan A adalah semesta pembicaraanya) maka ( x    A) p(x) atau
 x!  p(x) atau   x  p(x)  adalah suatu pernyataan yang dibaca “Ada x elemen A,
sedemikian hingga  p(x)  merupakan pernyataan benar” atau “Untuk beberapa x,
p(x)”. Ada yang menggunakan simbol   x! untuk menyatakan “Ada hanya satu”.
Contoh:
Pernyataan "Ada bunga yang bau" dapat dinyatakan sebagai
"Ada paling sedikit satu x, sedemikian sehingga berlaku p(x)."
Pernyataan terakhir ini dapat dinyatakan sebagai berikut:
x, p(x)
Lambang (dibaca: ada atau beberapa) adalah lambang kuantor eksistensial. Notasi x, p(x) (dibaca: Ada paling sedikit satu x, sedemikian sehingga berlaku p(x)) merupakan notasi dari pernyataan eksistensial.

Beberapa macam ucapan-ucapan yang mempunyai arti sama diantaranya:

($x) P(x) dibaca :   •  Terdapat x  A, x bersifat p(x)
  • Ada x   A sedemikian hingga x mempunyai sifat p.
  •  Sekurang-kurangnya satu x   A mempunyai sifat p
  • Beberapa  x, x mempunyai sifat p. 



Contoh :

Misalkan suatu pernyataan p(x) = x adalah anita
p(pewira ABRI) = perwira ABRI adalah wanita

Maka  x p(x) =  x! p(x) =  x   {perwira ABRI}, p(x) = Ada perwira ABRI
wanita (Benar).

v  Negasi dari pernyataan kuantor eksistensial:
~[x, p(x)] ≡ x, ~p(x)

Contoh:
Negasi dari pernyataan:"Ada ikan laut yang menyusui."
adalah"Semua ikan laut tidak menyusui."

Contoh pernyataan berkuantor universal:
1.      Pernyatan;
Untuk setiap bilangan real x, x2  0 adalah pernyataan berkuantor universal. Daerah asalnya adalah Himpunan Bilangan real. Pernyataan tersebut Benar, karena untuk setiap Bilangan Real x, adalah benar bahwa kuadrat x bernilai positif atau nol.
2.      Pernyataan ;
Untuk setiap bilangan real x, x2-1 >0
            Salah, karena jika x=1, proposisi  x2-1 >0
            Salah. Nilai satu adalah contoh penentang bagi pernyataan, Untuk setiap bilangan real x, x2-1 >0.
Untuk menunjukkan bahwa pernyataan berkuantor universal, Untuk setiap x, P(x)
Salah ,cukup dengan mencari satu nilai x di daerah asal yang disini proposisi P(x) salah. Metode penyangkalan pernyataan .
Untuk setiap x, P(x) agar berbeda dibandingkan dengan metode yang di gunakan untuk membuktikan bahwa pernyataan tersebut benar.
 Untuk membuktikan bahwa Untuk setiap x, P(x) benar, kita harus menguji setiap nilai x di daerah asal dan menunjukkan bahwa untuk setiap P(x) benar.


3.      Pernyataan kuantor Eksistensial ;
Untuk beberapa bilangan real x,
Adalah benar karena ada kemungkinan untuk mencari paling sedikit satu bilangan real x memebuat proposisi  =  adalah benar.
Sebagai contoh, jika x = 2, kita peroleh pernyataan yang benar  
Tidak benar bahwa setiap nilai x menghasilkan proposisi yang benar. Sebagai contoh proposisi  adalah salah.

v  Teorema : Memperumum Hukum De Morgan untuk Logika

Jika P adalah sebuah fungsi proposional, setiap pasangan pada (a) dan (b) berikut mempunyai nilai kebenaran yang sama (yakni, keduanya bisa benar ataupun salah).
(a). ; ,
(b). ; ,
            Bukti :
            (a). Andaikan bahwa proposisi  benar, maka proposisi, P(x)  salah. Menurut Definisi 1.3.4, proposisi , salah apabila P(x) salah untuk paling sedikit satu x di daerah asal. Akan tetapi, jika P(x) salah untuk paling sedikit satu x didaerah asal, maka benar untuk paling sedikit satu x di daerah asal. Menurut definisi 1.3.4 juga, apabila    benar untuk paling sedikit satu x di daerah asal, maka proposisi ,  benar. Jadi, jika proposisi   benar, proposisi ,  benar. Sama halnya, jika proposisi   salah, maka proposisi ,  juga salah.
Oleh karena itu, pasangan proposisi pada (a) selalu mempunyai nilai kebenaran yang sama.
Contoh :
a)      Misalkan P(x,y) adalah pernyataan, jika x2 < y2, maka x < y.
Daerah asal pembicaraan adalah Himpunan bilangan real.
Pernyataan, untuk setiap x, setiap y, P(x,y) adalah salah. Contoh penyangkalnya adalah
x = 1, y = -2. Pada kasus ini kita peroleh proposisi salah. Jika 12 < (-2)2 , maka 1 < -2.
Pernyataan, untuk setiap x, untuk beberapa y, P(x,y) adalah benar. Kita perlihatkan bahwa untuk setiap x, proposisi, untuk beberapa y, jika x2 < y2, maka x < y benar dengan menunujukkan sebuah nilai y sehingga, jika x2 < y2, maka x < y benar. Tentu saja, jika kita ambil y = 0, kita peroleh proposisi yang benar, jika x2 < 0, maka x < 0.
(proposisi bersyarat tersebut benar karena hipotesis  x2 < 0 salah. )
Pernyataan .
Untuk setiap y, untuk beberapa x, P(x,y) adalah benar. Kita perlihatkan bahwa untuk setiap y, proposisi untuk beberapa x, jika x2 < y2, maka x < y adalah benar dengan menunujukkan sebuah nilai x yang membuat jika x2 < y2 , maka x < y adalah benar. Tentu saja , jika kita ambil x = |y| + 1 , kita dapatkan proposisi yang benar,
 jika ( |y| + 1)2 < y2 , maka |y| + 1 < y.
( pernyataan bersyarat tersebut adalah benar karena Hipotesisnya salah)
 Kita rangkum aturan- aturan untuk membuktikan atau menyangkal pernyataan kuantor universal atau eksistensial sbb.
·         Untuk membuktikan bahwa pernyataan kuantor universal
Untuk setiap x, P(x) adalah benar, perlihatkan bahwa untuk setiap x di daerah asal, proposisi P(x) benar. Pembuktian bahwa P(x) benar untuk nilai x tertentu tidak membuktikan bahwa untuk setiap x, P(x) adalah benar.
·         Untuk membuktikan bahwa pernyataan kuantor eksistensial
Untuk beberapa x, P(x) benar, carilah satu nilai x di daerah asal sehingga P(x) adalah benar. Satu nilai suah cukup.
·         Untuk membuktikan bahwa pernyataan kuantor universal
Untuk setiap x, P(x) adalah salah , carilah satu nilai x (contoh penentang)di daerah asal yang membuat P(x) salah.
·         Untuk membuktukan bahwa pernyataan kuantor eksistensial
Untuk beberapa x, P(x) adalah salah, perlihatkan bahwa untuk setiap x di daerah asal, proposisi P(x) salah.
Pembuktian bahwa P(x) salah untuk nilai x tertentu tidak membuktikan bahwa untuk beberapa x, P(x) adalah salah.







DAFTAR PUSTAKA


C.L.LU. 1995. Dasar –dasar Matematika diskret. PT. Gramedia Pustaka Utama : jakarta