Meeting with Prof Ulle Endris

I have just met with Prof Ulle Endris, who is my academic mentor, here in ILLC UvA. I will study Logic.

We decide a plan on what courses to take this semester. In the first semester, I will take a little bit more than 30 credits. Some candidates of the course are:

  • Logic, Language, and Computation (3 credits) – block 1 & 2
  • Introduction to Modal Logic (6 credits) – block 1 & 2
  • Intuitionistic Mathematics (8 credits) – block 1 & 2
  • Information Theory (6 credits) – block 2
  • Knowledge Representation (6 credits) – block 1 XOR Functional Specification of Algorithm (6 credits) – block 1
  • Proof Theory (6 credits) – block 2 XOR Dynamic Epistemic Logic (6 credits) –  block 2
  • Research Project (6 credits) – block 3

Moreover, I will sit in the  Lambda Calculus and Concurrency Theory for a while. Probably I will also come to see some classes in linguistics and philosophy for fun and refreshments.🙂

I think I have almost settled the courses for block 1 (4 courses is good enough), but not yet for block 2. For block 1, I will come to 4 courses, including Intuitionistic Mathematics (which will not be offered next year). In block 2, I might need to take 5 courses as there is a compulsory course called Information Theory. In total,  it will be like 41 credits. It sounds like disaster. I will probably just drop either

Intuitionistic Logic

or

Proof Theory as well as Dynamic Epistemic Logic

Here comes the first week of my Master study. The first class will be on Monday, 5 September 2016. I hope everything will be fine.

 

Raja

 

 

Membangun kombinator lain dari kombinator S dan K (Bagian 1)

Kombinator S dan K dalam CL (combinatory logic) didefinisikan dengan

SXYZ \equiv XZ(YZ)

dan

KXY \equiv X

untuk sembarang CL-term X,Y,Z.

Secara makna, kombinator K dapat dipandang sebagai fungsi yang menerima dua masukan X dan Y, kemudian memberikan keluaran berupa parameter pertama X. Kombinator S sendiri dapat dipandang sebagai fungsi komposisi (saya baru paham cara menggunakannya setelah membaca buku Lambda Calculus and Combinators – an Introduction oleh J. Roger Hindley dan Jonathan P. Seldin). Fungsi komposisinya kurang lebih begini secara simbol:

(S(f,g))x = f(x,g(x)).

Jika Anda mempelajari logika melalui jalur lain, pasti cukup familiar dengan fungsi f(x,g(x)) ini. Dapat dilihat bahwa makna S yang berbentuk SXYZ \equiv XZ(YZ) ini sesuai dengan makna fungsi rekursif ini.

Sekarang, fungsi-fungsi kombinator lain dapat dibangun hanya menggunakan kombinator S dan K ini. Berikut adalah contoh dan cara mencari bentuk ekivalennya.

Contoh 1. Kombinator identitas

Kombinator I identitas memenuhi sifat IX \equiv X. Kombinator I ini dapat ditulis sebagai SKK. Mudah diverifikasi bahwa SKKX \rhd_w KX(KX) \rhd_w X. Namun, bagaimana cara mendapatkan bentuk SKK ini?

Contoh 2. Kombinator komposisi

Kombinator komposisi B berfungsi sebagai berikut:

(B(f,g))x \equiv f(g(x))

atau dalam bahasa CL, ditulis BXYZ = X(YZ). Mudah diverifikasi bahwa B \equiv S(KS)K:

S(KS)KXYZ \rhd_w (KSX)(KX)YZ \rhd_w S(KX)YZ \rhd_w (KXY)(YZ) \rhd_w X(YZ).

Nah, bagaimana pula mendapatkan bentuk S(KS)K ini?

Contoh 3. Fungsi suka-suka seperti [x,y,z].y(xz) atau [x,y].xyy

Kita juga bisa mencari bentuk CL-term dalam S dan K untuk fungsi di atas, misalnya

[x,y,z].y(xz) \equiv S(S(KS)(K(S(KS)K)))K

[x,y].xyy \equiv S(S(KS)(S(S(KS)K)(K(SKK))))(K(SKK)).

Sepertinya ribet sekali, ya? Padahal setelah paham cara menggunakan kombinator S ini sama sekali tidak susah ternyata. Kalau mau coba-coba latihan, coba kerjakan ini dulu:

Latihan 1. [x].xx

Latihan 2. [x,y,z].xzy

Pada bagian selanjutnya, saya akan mencoba menjelaskan cara mendapatkan kombinator ekivalen dalam S dan K saja.

(bersambung…)

 

 

Ketaksamaan kompleks ekivalen

Misalkan $a,b\in \mathbb{C}$. Buktikan bahwa $\left| az+b\bar{z} \right|\le 1$, untuk setiap $z\in \mathbb{C}$, dengan $\left| z \right|=1$, jika dan hanya jika$\left| a \right|+\left| b \right|\le 1$.

Bukti.

(Jika)

Jika $|a|+|b| \le 1$, maka dengan ketaksamaan segitiga, berlaku $|az+b\overline{z}| \le |a||z|+|b||\overline{z}| = |a|+|b| \le 1$.

(Hanya jika)

Asumsikan bahwa $|az+b\overline{z}| \le 1$ untuk setiap $z$ dengan $|z|=1$. Jika $a=0$ atau $b=0$, ketaksamaan $|a|+|b| \le 1$ terpenuhi. Asumsikan $ab \ne 0$. Dengan manipulasi aljabar, berlaku $|az^2+b| \le 1$. Ini juga berakibat $|az+b| \le 1$ untuk setiap $|z|=1$. Akibatnya
$|a|^2+|b|^2+a\overline{b}z+\overline{a}b\overline{b} \le 1 \quad (*)$.
Ambil $z=\dfrac{|a||b|}{a\overline{b}}$, perhatikan bahwa $|z|=1$ dan ketaksamaan $(*)$ menjadi $|a|^2+|b|^2+2|a||b| \le 1$ yang berakibat $|a|+|b| \le 1$.

Terbukti.

Refleksi.

Soal yang cukup rutin kecuali ide untuk kalimat terakhir yang mengambil $z=\dfrac{|a||b|}{a\overline{b}}$ harus sedikit licik.🙂

 

Kronologi peradaban Islam & pertanyaan yang belum terjawab

Saat ini saya sedang mencoba mengikuti course An Introduction to Islamic Civilization dari Bibliotecha Alexandrina di MIT edX. Kuliah pertamanya adalah tentang kronologi singkat peradaban Islam, sehingga bisa “meraba-raba” posisi waktu dan jarak antar kejadian-kejadian penting selama peradaban Islam. Saya juga tuliskan beberapa pertanyaan saya di sini untuk further research yang secara berangsur-angsur akan saya jawab sendiri selama belajar. Sepertinya tidak sulit untuk dicari dengan pencarian sederhana di Google tapi kalau ada yang mengetahui jawabannya (dan sumbernya), bolehlah dibantu jawab hehehe.

Berikut adalah lini waktu peradaban Islam.

570 M: Birth of Prophet Muhammad
Sepertinya, sejarawan sepakat bahwa kelahiran Nabi Muhammad sebagai penanda mulainya peradaban Islam. Saya jadi bertanya mengapa ya? Kemudian jika memang dimulainya sejak Nabi Muhammad, apa bisa saya simpulkan kejadian-kejadian sebelum kelahiran Nabi Muhammad tidak ada sangkut pautnya dengan agama Islam? Artinya, Islam dapat dianggap “totally unknown” sebagai sebuah set ajaran agama sebelum masa ini? Apakah ini berarti sejarawan menganggap bahwa nabi-nabi sebelum Nabi Muhammad pada dasarnya mengajarkan nilai-nilai yang bukan Islam (maksudnya, nilai-nilai tidak dipandang sebagai satu kesatuan dalam Islam) namun lebih ke nilai-nilai yang terpisah? Mungkin tidak ada historical evidence tentang pewahyuan yang diperoleh nabi-nabi sebelumnya berkaitan dengan Islam.
610 M: Muhammad’s call to be the Seal of the Prophets on Mount Hira, and the beginning of Revelation of the Qur’an
Berarti panggilan ini ada saat Nabi Muhammad berumumr 40 tahun. Kemudian Gunung Hira, menurut Wikipedia, jaraknya hanya 3 km dari Mekah. Ga jauh ya hehehe. Ini fotonya:

Sumber: Wikipedia

Mungkin yang sudah pernah umroh ke sana mengunjungi tempat ini.Tapi kok sepertinya banyak vandalisme ya di batu-batu gunung ini. Hadeh. Udah kayak Indonesia aja. Kemudian, pertanyaan saya terkait masa ini adalah kalau wahyu Al-Quran dimulai saat Nabi Muhammad berumur 40 tahun, apa saja yang dilakukan Nabi Muhammad selama 40 tahun? Jika ia mengajarkan sesuatu, bersumber dari mana?
622 M: Prophet’s Hijrah from Makkah (Mecca) to Madina (Medina), whose importance is commemorated by the Islamic calendar, which counts years from this point (A.H.)
Jadi ini saat Nabi Muhammad berumur 50-an dan sepertinya Islam sudah memiliki pengikut dan sepertinya pengikutnya juga ikut hijrah. Pertanyaan yang muncul adalah penyebab hijrahnya apa ya? Terus kok ini kuliahnya kontradiktif dengan yang dibilang di Wikipedia ya karena kata Wikipedia kalendar Islam tidak dimulai sejak hijrah ini. Hmmm. Jadi bagaimana sebenarnya penentuan kalender Islam? Berapa lama? Kenapa lebaran dan mulai puasa tiap tahun harus dirapatkan dulu?
Oh ya Medinah katanya nama asli kotanya adalah Yathrib yang kemudian diberi nama “the city of the prophet” kemudian the prophet-nya dihilangkan sehingga jadinya “the city” aja. Cool.
630 M: Muhammad’s conquest of Mecca, and rededication of the Ka’ba to monotheistic worship
Wow. Jadi tidak sampai 10 tahun kemudian, Mekah sudah kembali di bawah kekuasaan umat Islam. Kemudian, jadi bertanya lagi, siapa sebenarnya yang menguasai Mekah waktu itu dan Kabah digunakan sebagai apa ya?
632 M: Death of Muhammad
Berarti Nabi Muhammad meninggal saat berumur sekitar 60 tahun ya.
632-661 M: Period of the “Rightly Guided Caliphs” (Abu Bakr, Umar, Uthman, Ali), when the Umma (Islamic community) was led by the Companions of the Prophet. This period is marked by Muslims consolidating their power in Arabia, and the conquests of Syria, Palestine, Egypt, Iraq, Persia—all of which would come to constitute the heart of the Islamic Empire.
Setelah Nabi Muhammad meninggal, katanya ada empat khalifah pertama, yang biasa disebut Rashidun. Yang dipilih oleh lembaga tertentu atau pendahulunya. Ini berlangsung sampai 661 M yang berarti berjalan selama 30 tahun. Pendek juga ya.
Kemudian, katanya ada juga Rashidun di Baghdad. Apa bedanya ya? Kemudian, apa yang terjadi setelah keempat Rashidun ini selesai memimpin? Kalaupun masih ada khalifah, apa yang berbeda dengan keempat khalifah ini? Apa mereka ini yang ada saat Nabi Muhammad masih hidup kali ya?
Oh ya lini waktunya kurang lebih seperti ini:

Sumber: Wikipedia

661-750 M: Muawiyah, founder of the Umayyad dynasty, becomes the caliph and moves the capital from Mecca to Damascus
Belum pernah dengan Muawiyah sama sekali. Jadi, ini benar-benar informasi baru hehehe. Apa ya signifikansi dinasti Umayyad? Sepertinya ini masa-masa Islam menyebar hingga ke Eropa kali ya?
669 M: The Muslim conquest reaches Morocco in North Africa
Kenapa Maroko perlu dimasukkan lini waktu ini? Apa signifikansinya?
672 M: Muslims under Muawiyah capture the Island of Rhodes
Hmmm ini pulau di Yunani. Apa ya yang mereka lakukan di pulau ini? Sepenting apakah pulau ini? Maklum saya nubitol nih belajar sejarah hehe.
711 M: With the conquest of Egypt, Spain and North Africa, the Persian empire and most of the old Roman world came under the Islamic rule. Muslims began the conquest of Sindh in Afghanistan.
Oh saya baru tahu kerajaan Islam pernah menguasai daerah-daerah Kerajaan Romawi ya. Keren. Anyway, kayaknya Sindh itu adanya di Pakistan deh bukan Afghanistan.
750 M: Fall of the Umayyads and the rise of the Abbasid Dynasty, which conquered the Umayyads and ruled from Baghdad until the Mongol conquest in 1258 CE
Berarti dinasti Umayyad sudah berdiri selama 89 tahun. Tidak terlalu panjang ya, ternyata. Kemudian bagaimana Abbasid bisa menguasai dinasti Umayyad, ya? Kemudian, sepertinya dinasti Abbasid ini panjang sekali hidupnya, yaitu sekitar 508 tahun. Wow.
968-1171 M: The Fatimids, a “Sevener” Shi’ite Dynasty, founds the city of Cairo and rules Egypt
Wah, ada muncul Syiah di masa ini. Lumayanlah nanti belajar sejarah hubungan Islam Sunni dan Syiah hehe dan kontribusi apa kedua aliran ini berikan bagi dunia. Bagaimana daerah kekuasaan Fatimid dan juga Umayyad tersebar dan bagaimana efek geografisnya bagi masing-masing? Bagaimana konflik-konflik dari zaman ke zaman bisa terselesaikan? Jangan-jangan dari dulu permasalahannya masih sama saja?🙂
1099 M: The Crusaders take Jerusalem
Katanya perang salib terjadi berkali-kali sejak abad ke-11 hingga ke-15. Kadang menang dan kadang kalah. Apa saja ya dampaknya bagi peradaban Islam?
1187 M: Saladin (the most famous of the Ayyubids, the dynasty that toppled the Fatimids in Egypt in 1169 CE) retakes Jerusalem at Battle of Hattin
Yerusalem kembali lagi di bawah kekuasaan pemerintahan Islam. Sepertinya Saladin merupakan orang hebat karena berhasil menghentikan kekuasaan Fatimid di Mesir kemudian mengambil kembali Yerusalem. Terus, kenapa dinasti Ayyubid tiba-tiba muncul ya tapi tidak di-mention di kronologi ini. Apa hubungannya dengan dinasti Abbasid?
1258 M: The Mongol conquest causes the fall of the Abbasid Dynasty
Wah Mongolia bisa mengganggu juga, ya. Daerah mana yang menerima dampak serangan dari Mongolia ini? Bagaimana pemerintahan Islam berlanjut setelah dinasti Abbasid berlangsung? Padahal kan baru benar-benar selesai tahun 1492 yang artinya masih 234 tahun. Bagaimana bentuk pemerintahannya?
1492 M: End of the Period of the Islamic rule of Spain
Katanya Andalusia  (Al-Andalus) adalah daerah di Spanyol, Portugis, dan sekitarnya yang saat itu di bawah pemerintahan Islam namun tetap terdapat harmoni dalam masyarakatnya berupa kemajemukan masyarakat non-Muslim di dalam Andalusia. Ini menghasilkan karya-karya seni misalnya yang merupakan perpaduan budaya barat dan timur. Wah, saya jadi penasaran pengen ke sana.🙂 Katanya Andalusia berakhir karena serangan dari kerajaan Eropa yang mulai bangkit lagi.

Lukisan orang Yahudi dan orang Islam bermain catur. (Sumber: Wikipedia)

 

Refleksi

Sangat menarik untuk dipelajari lebih lanjut. Mohon koreksinya jika Anda kebetulan membaca dan menemukan kesalahan (dan peduli).🙂

 

Soal OSN 2016 Hari Kedua Soal 5

Ini adalah salah satu dari tiga soal saya yang diterima menjadi soal OSN 2016 di Palembang, Sumatera Selatan. Sama seperti soal kedua hari pertama, aslinya soal ini diajukan untuk OSP (tingkat provinsi), namun saya coba ajukan lagi dan ternyata diterima. Yeah.

Soal. Andaikan $x$ merupakan bilangan real sehingga barisan bilangan bulat yang didefinisikan dengan $a_n=\lfloor nx \rfloor$ untuk setiap bilangan asli $n$ merupakan barisan aritmetika. Haruskah $x$ merupakan bilangan bulat?

Solusi. Ya. Misalkan $x=a+r$ dengan $a$ bilangan bulat dan $0 \le r < 1$. Perhatikan bahwa berlaku untuk setiap bilangan asli $n$:

$2\lfloor nx \rfloor = \lfloor (n-1)x \rfloor + \lfloor (n+1)x \rfloor$

$2na + 2\lfloor nr \rfloor = (n-1)a+\lfloor (n-1)r \rfloor + (n+1)a+\lfloor (n+1)r \rfloor$

$2\lfloor nr \rfloor = \lfloor (n-1)r \rfloor + \lfloor (n+1)r \rfloor$.

Asumsikan $r>0$, maka terdapat bilangan asli $k$ sehingga $\dfrac{1}{k+1} \le r < \dfrac{1}{k}$. Ini akan berakibat $(k-1)r<kr<1$ dan $(k+1)r \ge 1$. Artinya, $\lfloor (k-1)r \rfloor=\lfloor kr \rfloor=0$ dan $\lfloor (k+1)r \rfloor = 1$. Dengan mensubstitusi $n=k$ pada persamaan terakhir, diperoleh persamaan $2 (0)=0+1$ yang tidak valid.

Dengan demikian, haruslah $r=0$. Ini berarti $x$ haruslah berupa bilangan bulat.

Refleksi.

Soal ini sebenarnya harapannya mudah, makanya dijadikan soal pertama di hari kedua OSN. Namun, sepertinya soal ini tidak bisa dikatakan immediate juga bagi peserta OSN yang sebagian besar masih belum terbiasa menuangkan ide matemtis ke dalam tulisan yang runut. Alhasil, soal nomor 7, yaitu soal teori bilangan yang lebih terlihat “menghitung” memberikan nilai rata-rata yang lebih tinggi dibandingkan soal nomor 5 ini.

Hal yang paling sulit dari soal ini adalah memilih bilangan asli $k$ yang memenuhi $\dfrac{1}{k+1} \le r < \dfrac{1}{k}$. Mengapa sulit? Perhatikan bahwa untuk $r$ yang semakin mendekati $0$, nilai $k$ yang dipilih pun akan semakin besar agar memenuhi pertidaksamaan tersebut. Dengan demikian, pengambilan nilai $k$ yang cukup besar ini adalah langkah yang perlu (necessary) untuk menyelesaikan soal. Di nilai batas $k$ inilah titik kritis di mana barisan tersebut akan gagal menjadi barisan aritmetika untuk $r>0$. Menggunakan manipulasi aljabar biasa tidak membantu menyelesaikan soal ini. Ada properti analisisnya sedikit-sedikit. Oh ya properti ini dikenal juga dengan Archimedian Property.

Selain itu, hanya menggunakan informasi bahwa berhingga suku dari $a_n=\lfloor nx \rfloor$  merupakan barisan aritmetika tidak akan berhasil. Hal ini karena pada dasarnya ada $x$ yang tidak bulat yang membuat berhingga suku tersebut barisan aritmetika. Jadi, mengambil nilai  $k$ yang cukup besar adalah jalan yang “harus dilewati” untuk menyelesaikan soal ini. Tidak harus sama persis argumennya, namun begitulah kurang lebih struktur solusinya.