Formal Method Makalah

7/26/2019 Formal Method Makalah

1/12

MAKALAH

FORMAL

Disusun guna memenuhi tugas Mata Kuliah Matematika Model

Dosen Pengampu: Prof. Dr. Marsigit, M.A

Disusun oleh:

BURHANUDDIN

NIM. 15709259007

PROGRAM !UDI P2!K P"NDIDIKAN MA!"MA!IKA

PROGRAM PA#A AR$ANA

UNI%"RI!A N"G"RI &OG&AKAR!A

201'


2/12

LOGIKA "N!"NIAL P"NUH

Pen()hulu)n

Ide perkembangan terpisah dari logika implikasional murni tampaknya berasal

dari Alfred Tarski sebelum tahun 1!"# pada tahun itu, kompilasi hasil oleh $.

%ukasie&i'(, Tarski, dan beberapa logika&an lain terpublikasi. )ubyeknya

didiskusikan kemudian oleh M. *a+sberg 1!-, %. /enkin 10, dan K. )'hr ter

12. Pengenalan urutan3barisan, dengan moti4asi teori dedusinya, se'ara bebas

merupakan hak untuk 5. 5ent(en 10! dan ). $asko&ski 10!# moti4asi

semantik tersebut nampak asli. )uatu kema+uan, seperti dibandingkan dengan teknik

5ent(en dan $asko&ski, terlihat men+adi konsepsi dari aturan6aturan inferensi

mereka sebagai aturan reduksi.

Ini mungkin terlihat asing bah&a begitu banyak perhatian telah diberikan di

sini untuk perlakuan agak 'anggih dari suatu logika quite embryonic fragment, dan

beberapa kata dari pen+elasan mungkin dalam urutan. Di tempat pertama, dari

a&alnya manusia harus berkenalan dengan teori dedusi, semantik, dan logika

konsepsi aksiomatik# karena +ika di salah satu pertama dihadapkan dengan hanya

satu konsepsi ini, hasilnya akan bah&a nanti konsepsi lain akan mun'ul baik suara

kurang atau lebih +elas, sedangkan logika se'ara keseluruhan akan terlihat buatan

atau setidaknya terlalu 'anggih. 7amun, +ika tiga konsepsi yang berbeda telah

disa+ikan sekaligus dalam konteks 4ersi yang lebih 'anggih dari logika, pembahasan

di 8ab I akan men+adi tidak perlu dilibatkan. )elan+utnya, logika implikasional

murni ini tidak berarti seperti embrio yang tampak. 9elatifnya harus ditambahkan

sedikit +ika ingin dikembangkan men+adi seperti 4ersi logika yaitu, logika klasik,

tidak ada perlakuan sistematis logika intuitionisticyang sedang di'obakan dalam

buku ini sebagai memberikan dasar untuk penalaran deduktif seperti yang

ditemukan dalam matematika dan ilmu pengetahuan. Dan segera setelah elemen

pelengkap yang diperlukan telah diperkenalkan, keuntungan akan didapatkan

dengan perlakuan yang agak besar dari logika implikasional murni dalam 8ab I.


3/12

Dalam diskusi dari bagian6bagian yang lebih ma+u dari logika, konsepsi teori

deduksi tidak lagi diperhitungkan. Dari sudut pandang formalistik yang ditandai

dengan menghindari setiap referensi untuk makna simbol atau kebenaran ataukepalsuan dari rumus, itu bisa 'ukup diganti dengan konsepsi aksiomatik logika.

Pen()hulu)n Pen*hu+un* en,ensi)l el)n-u,n)

Pada 8agian ini, dapat diperkenalkan dengan baik dis+ungsi, kon+ungsi, dan

negasi yang diekspresikan se'ara berturut6turut, dengan simbol ;, dan )1 pada 8agian 1 harus

diperluas sebagai berikut:

=> $ika Udan Vadalah rumus, maka U? V, U V, dan U< V +uga

merupakan rumus, dan +ika U adalah sebuah rumus, maka U +uga

merupakan rumus. @Dalam prakteknya, kurung terluar dari rumus gabungan

akan dihilangkan.

)1 $ika baik Usalah atau Vbenar, maka U? V benar dan +ika B benar dan C

salah maka U?V salah# $ika baik Uatau Vbenar, maka U Vbenar dan

+ika baik Udan Vsalah, maka U V salah# $ika baik Udan Vbenar, maka

U< Vbenar dan +ika baik Uatau Vsalah, maka U


4/12


5/12

)ebuah perbandingan dari dua fragmen pertama mengarah ke pengertian

bah&a dalam pembangunan tableau semantik untuk urutan /Z setiap

aplikasi skema reduksi ii+a dapat digantikan oleh aplikasi yang sesuai dari

closuredan skema reduksi i, i+a, dan i+b, disediakan rumus yang sesuai:

(U'V')[(U' V') V']

dapat ditambahkan ke antecedent. )ebuah perbandingan dari dua fragmen lain

menun+ukkan bah&a, +uga, setiap aplikasi dari skema reduksi ii+b dapat

dihindari +ika ditambahkan rumus yang sesuai:

[(U' '

V

' '

) V' '

] (U' '

V

' '

)

untuk antecedent. Misalkan K3Z men+adi urutan yang dihasilkan se'ara

sistematis yang menerapkan prosedur ini.

)ekarang anggaplah bah&a Z adalah identitas logis. Kemudian tableau

semantik untuk urutan /Z yang dibangun di ba&ah skema i6ii+, harus

tertutup. Ini mengikuti bah&a tableau semantik untuk urutan K3Z yang


6/12

dibangun di ba&ah skema i dan i+ sa+a, dan +uga tertutup. Dalam

pembangunan tableau terakhir ini, rumus U Vdan U V tidak

diperlakukan# keduanya berperilaku seperti atom. $adi tableau terakhir dapat

dipandang sebagai dedusi dalam logika implikasional murni dan oleh karena itu

dapat diterapkan Teorema E dengan pengertian bah&a dalam membuktikan

tesis:

U1(U2 ( (UmZ)))

harus bergantung pada 4ersi yang diperluas dari himpunan aksioma I6III.

7amun, semua rumus Ul, U>, F, Umadalah aplikasi dari aksioma6skema IC

dan C. $adi dengan menggunakan aksioma6skema ini dan menerapkan modus

ponen dapat membuktikan bah&a Z adalah tesis. Ini mengikuti bah&a

setidaknya bagian kedua dari Teorema E tetap berlaku untuk sistem logika di

ba&ah pertimbangan. Mulai dari hasil ini, tidak sulit untuk mengadaptasi bukti

dari Teorema 610.

! Bntuk kon+ungsi, skema reduksi +elas sudah ada

i4a

8enar )alah

i4b

8enar )alah

K;

U< V

L K L

U< V

U

V

i i+ i

U

i+

V

7amun demikian, tidak mungkin untuk mendefinisikan kon+ungsi dalam

hal implikasi sendiri dan dengan demikian masalah memperluas himpunanaksioma yang sesuai akan men+adi lebih rumit daripada dalam kasus dis+ungsi.

)olusi berikut ini disebabkan oleh %. Kalmar, *a+sberg, dan /enkin.

$ika dalam beberapa 'ara dapat diungkapkan dengan simbolisme

kepalsuan rumus, maka dapat +uga diungkapkan kebenaran rumus dan

karenanya dapat pula mener+emahkan aturan )1 ke dalam simbolisme. )e'ara

khusus, misalkan Zmen+adi rumus palsu# maka dapat diambil U ? Z untuk


7/12

mengungkapkan kepalsuan dari Udan U ? Z ? Z untuk mengungkapkan

kebenarannya.

)ayangnya, ada pada tahap pembangunan simbolisme saat ini tidak adarumus Z yang diketahui pasti palsu. Ini sangat mudah untuk melihat bah&a

rumusZyang hanya berisi implikasi harus benar +ika semua atom A, B, C, F

yang mun'ul di dalamnya adalah benar# pernyataan ini +uga berlaku untuk

rumusZyang mengandung, selain implikasi, dis+ungsi dan kon+ungsi.

7amun, tidak perlu memiliki formula Zyang diketahui palsu# itu sudah

'ukup untuk memiliki rumus Zyang, dalam konteks tertentu, dianggap palsu.

Dan dalam kasus di mana ada ketertarikan, yaitu, dalam deduksi dari urutan

/Z , rumus seperti itu sudah tersedia. Mener+emahkan aturan )1 se+auh itu

berkaitan dengan kebenaran dan kepalsuan dari rumus U< V, akan diperoleh

aksioma berikut:

CI {(UV )Z}[ {(V Z)Z} {[(UV )Z ]Z}] ,

CII (UZ)[(UV)Z] ,

CIII (VZ)[(UV)Z] .

)ebenarnya, dapat dilakukan adopsi aksioma sederhana dan masih

mengadaptasi bukti dari Teorema 610# tapi, hal ini tidak terlalu penting.

0 8eralih ke negasi, se'ara +elas akan dimiliki skema reduksi berikut:

4a

8enar )alah

i4b

8enar )alah

K;

U

L K L

U

U U

Mener+emahkan bagian yang rele4an dari aturan )1 berdasarkan

ren'ana Kalmar dan /enkin, diperoleh aksioma berikut untuk negasi:

IG [(U Z) Z](U Z) ,

G (U Z)[(U Z) Z] .


8/12

8agaimanapun akan digunakan:

GI U (U Z) ,

GII (U U)U .

!eo/e) 15. $ika diakui rumus yang mengandung implikasi dan negasi dan +ika

untuk aksioma6skema I6III ditambahkan aksioma6skema IG dan G, maka

Teorema 610 tetap 4alid.

Bu,i. Tidak ada masalah dalam memperluas pernyataan dan pembuktian

Teorema 2. )eperti Teorema E, dua kali dibandingkan dua fragmen khas dari

tableausemantik untuk rumusZyang me&akili urutan K3%.

)eperti pada >, diamati bah&a aplikasi skema 4 dapat digantikan oleh

aplikasi skema i dan i+, asalkan ditambahkan rumus yang 'o'ok

U'(U' Z) dan (U

' ' U' ') U' ' pada antecendent. Misalkan U1,

U>, ..., Ummen+adi semua rumus yang ditambahkan dengan 'ara ini. Kemudian,


9/12

se'ara +elas tableau semantik untuk urutan /Z yang dibangun di ba&ah

skema i, i+, dan 4 akan tertutup, +ika dan hanya +ika tableausemantik untuk

urutan U1, U>, ..., Um3Zyang dibangun di ba&ah skema i dan i+ sa+a +uga

tertutup. Dalam pembangunan kedua, rumus U; dan U;; berperilaku seperti atom

dan karenanya tableau kedua dapat dianggap sebagai formal deduksi dalam

logika implikasional murni. Kemudian berdasarkan Teorema E dalam bentuk

aslinya, rumus:

U1(U2 ( (UmZ)))

adalah tesis logika implikasional murni impli'ationallogi'. Karena U1, U>, ...,

Umadalah aplikasi dari aksioma6skema IG dan G, dibuktikan dengan modus

ponen bah&a rumusZadalah tesis logika sentensial dalam implikasi dan negasi.

Teorema E dan 2 yang sekarang ini ditetapkan untuk 4ersi yang besar dari logika

sentensial, pembahasan teorema sisa menya+ikan tidak ada kesulitan.

Teorema 1 mengungkapkan kelengkapan teori deduksi logika sentensial dalam

implikasi dan negasi. )ekarang harus dinyatakan dan dibuktikan teorema lain

yang menyatakan kelengkapan teori definisi atau kelengkapan fungsional dari

4ersi logika sentensial dan +uga di+elaskan mengapa 4ersi ini lebih penting

daripada, katakanlah, logika sentensial pada implikasi dan kon+ungsi.


10/12

!eo/e) 1'. Misalkan men+adi penghubung sentential yang maknanya

diberikan oleh aturan semantik atau dengan tabel kebenaran. Maka adalah mungkin

untuk menemukan formulaf (A, B,... logika sentensial di implikasi dan negasi yang

memenuhi persyaratan sebagai berikut:

i di ba&ah setiap 4aluasi , !o (A, B,... H !f (A, B,...#

i+ Teorema 1 akan berlaku untuk logika sentensial di Implikasinya, negasi, dan ,

menyediakan aksioma6s'hemata yang dikenal dengan:

(U , V , ) f(U , V , ) ,

f( U , V , ) (U , V , ) ,

Bu,i. Kami pertama kali menetapkan adanya formulaf (A, B,... yang memenuhi

syarat i.

I Misalkan bah&a

adalah penghubung unary. Maka haruslah memiliki salah

satu dari empat tabel kebenaran yang di&akili dalam kolom a, b, ' dan d di

ba&ah ini :

A a

A

b

A

'

A

d

A

" " " > >

> " > " >

Dengan demikian kita mengambil rumusf (A", masing#masing$a AA , bA,

and 'A dA A%

II )ekarang, misalkan men+adi penghubung biner. Kami menganggap rumus

o (A, B B"


11/12

Karena (B B"H >, @ (A, B B"&akan tergantung hanya pada

(A"' leh karena itu, kita dapat mempertimbangkan o (A, B 8 men+adi o(A",

omen+adi penghubung unary.

Demikian +uga, kita dapat mempertimbangkan (A, B B" men+adi 2

(A". Dengan hasil kami di ba&ah I, kita sudah tahu bah&a formula f1 (A"

'o'ok dan f2 (A" akan sesuai dengan 1 (A" dan 2 (A" . 9umus ini

diberikan, maka akan +elas bah&a sebagai rumusf (A,8 yang bisa kita ambil $

[f1(A)B ][ f2(A) B ]

Kasus penghubung ternary diperlakukan sama. Kami sekarang ingin

menun+ukkan bah&a rumusf (A, B" diba&ah II +uga memenuhi syarat i+. /al ini

dilakukan dengan dua kali membandingkan dua fragmen dari tablo semantik# tidak

akan diperlukan untuk diam di masalah ini.

- )ebagai sebuah aplikasi, saya menganggap pengenalan )esetaraan atau

biconditionaldiungkapkan oleh simbol . Kita harus memperluas aturan =>

dengan 'ara langsung# )elan+utnya, kita tambahkan untuk )1 klausa: ) 1 $ika U

dan C keduanya benar atau keduanya salah, maka U Vadalah benar# +ika U

adalah benar dan Vadalah salah atau sebaliknya, maka U Vadalah salah.

)ebagai rumus f1(A ) danf2(A) kita dapat mengambil, masing6masing, A dan

A 'sesuai, kita dapat mengambil sebagai formula f A,B"$

[A B ] [ A B ]


12/12

leh karena itu, bi'onditional se'ara +elas ditandai sebagai berikut aksioma6

s'hemata:

Kami memiliki skema pengurangan:

Formal Method Makalah

Documents

Transcript of Formal Method Makalah