Sistem formal

Daripada Wikipedia, ensiklopedia bebas.
Lompat ke: pandu arah, cari

Sistem formal ialah set barang-barang data niskala, yang mendefinisikan hukum-hukum sintaks dengan mana satu set simbol-simbol niskala boleh dimanipulasi.

Ia mengandungi:

  1. suatu abjad terhad simbol-simbol (“perbendaharaan kata”)
  2. suatu tatacara utk membentuk perkataan (“nahu”/ “tatabahasa”)
  3. suatu set aksiom (semuanya perkataan)
  4. suatu set terhad hukum deduksi (dengan mana suatu set perkataan tambahan boleh dideduksi daripada suatu set yang diberi):
u1 & u2 & … & upw1 & w2 & … & wn

Bukti[sunting | sunting sumber]

Ini merupakan jujukan terhad perkataan-perkataan M1 , M2 , … , Mr di mana Mi adalah samada aksiom, atau MjMi, dengan j < i.

Teorem[sunting | sunting sumber]

Teorem ialah perkataan t yang mana wujud bukti dengan Mrt. (Ini bermakna semua aksiom adalah teorem.)

Teorem di sini ialah suatu binaan sintaks semata-mata, yang membabitkan manipulasi simbol, dan tidak ada kena-mengena dengan 'kebenaran'nya.

Kebolehputusan[sunting | sunting sumber]

Diberi suatu perkataan, bolehkah ia dibuktikan sebagai teorem atau dibuktikan sebagai bukan teorem (dalam bilangan langkah terhad)? Jika ini boleh dibuat oleh sesuatu sistem formal itu, maka ia dikatakan bolehputus, dan takbolehputus jika sebaliknya.

Tafsiran (semantik)[sunting | sunting sumber]

Semantik merujuk kepada hubungan antara sistem formal dan dunia luar (yakni tafsiran makna yang diberikan kepada simbol-simbol).

Tafsiran boleh diadakan yang membabitkan nilai benar/palsu kepada perkataan-perkataan. Di sini, biasanya ingin dicari tafsiran di mana setiap teorem merupakan perkataan benar (atau dalam cakap logik, ayat benar).

Lengkap & sahih[sunting | sunting sumber]

Konsep-konsep ini membabitkan hubungan di antara sintaks dan semantik sesuatu sistem formal.

Sesuatu sistem itu dikatakan lengkap jika semua perkataan sah (ayat benar) adalah teorem. Dalam lain perkataan, setiap perkataan yang mempunyai tafsiran 'benar', boleh dibuktikan sebagai teorem secara manipulasi simbolan.

Sesuatu sistem itu dikatakan sahih jika semua teorem adalah sah. Dalam kata lain, setiap teorem yang boleh dibuktikan secara sintaks, mempunyai tafsiran semantik yang sepada dengan 'benar'.

Bagi sistem logik, yang dikehendaki ialah sistem yang lengkap dan sahih, supaya sintaksnya mencerminkan semantiknya, dan begitulah sebaliknya.