The Sampah's Blog

Pengantar Pembuktian Formal

Posted on: June 15, 2010

Pentingnya Pembuktian

  • Setiap computer-scientist perlu (harus) memahami teknik pembuktian
    • Ekstrem1: Pembuktian formal dari kebenaran suatu program komputer berlangsung seketika program tersebut dibuat
    • Ekstrem2: Pembuktian tidak digunakan dalam membuat program komputer. Slogan: “Jika kamu ragu dengan kebenaran program yang kamu buat, jalankan dan lihat!”
    • Tengah-tengah: Ketika program Anda salah setalah dijalankan, Anda tetap harus mengkoreksinya

Pembuktian Deduktif

  • Diawali dengan suatu statement awal dan diakhiri dengan suatu hasil pembuktian
    • Statemen awal tersebut disebut Hypothesis atau given statement(s)
    • Hasilnya disebut conclusion statement
    • Setiap langkah pembuktian harus diterima oleh prinsip-prinsip logika, baik dari fakta maupun dari statement sebelumnya, ataupun dari kombinasi keduanya

Hypothesis

  • Hypothesis bisa jadi benar atau salah
    • Tergantung dari nilai-nilai parameternya
    • Dapat terdiri atas beberapa statement independen, dan dikoneksikan dengan logika AND
  • Teorema yang dibuktikan dari hypothesis H dengan kesimpulan C:
    • If H then C
    • Dikatakan dengan: C dideduksikan dari H

Hypothesis: Contoh

  • Jika x 4, maka 2x x2
    • Hypothesisnya (H) adalah “ x 4
      • Parameternya adalah x
      • Nilai x menentukan kebenaran dari hypothesis
      • H benar jika x = 6, dan H salah jika x = 2
    • Kesimpulannya (C) adalah “ 2x x2
      • Juga menggunakan parameter x
      • C salah jika x = 3, dan C benar jika x=4

Reduksi ke Definisi

  • Jika x 4, maka 2x x2
    • Hypothesisnya (H) adalah “ x 4
      • Parameternya adalah x
      • Nilai x menentukan kebenaran dari hypothesis
      • H benar jika x = 6, dan H salah jika x = 2
    • Kesimpulannya (C) adalah “ 2x x2
      • Juga menggunakan parameter x
      • C salah jika x = 3, dan C benar jika x=4

Bentuk Tambahan dari Pembuktian

  1. Pembuktian terhadap himpunan
  2. Pembuktian dengan kontradiksi
  3. Pembuktian dengan counterexample

Pembuktian Induktif

  • Prinsip Induksi:
    • Jika kita membuktikan S(i) dan kita membuktikan untuk semua n ≥ i, S(n) mengimplikasikan S(n+1), maka kita dapat mensimpulkan S(n) untuk semua n ≥ i.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


  • Mr WordPress: Hi, this is a comment.To delete a comment, just log in, and view the posts' comments, there you will have the option to edit or delete them.

Categories

%d bloggers like this: