Ada 16 fungsi boolean yang berbeda untuk dua variabel biner, A dan B:
A B | F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 | F14 | F15
-----------------------------------------------------------------------------------------
0 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
0 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1
1 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1
1 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1
Kurang dari operator <
, yang biasanya tidak dianggap sebagai operator logika seperti BUKAN, DAN, atau ATAU, sebenarnya salah satu dari fungsi-fungsi ini (F4) ketika diterapkan pada nilai boolean:
A B | A < B
-----------
0 0 | 0
0 1 | 1
1 0 | 0
1 1 | 0
Menariknya, kita dapat mensimulasikan salah satu dari 15 fungsi lainnya menggunakan ekspresi yang hanya mengandung simbol ()<AB10
. Ekspresi ini dibaca dan dievaluasi sama seperti dalam banyak bahasa pemrograman standar, misalnya tanda kurung harus cocok dan <
harus memiliki argumen di kedua sisi itu.
Secara khusus, ekspresi ini harus mematuhi tata bahasa berikut (diberikan dalam bentuk Backus-Naur ):
element ::= A | B | 1 | 0
expression ::= element<element | (expression)<element | element<(expression) | (expression)<(expression)
Ini berarti bahwa etika dan ekspresi yang tidak berguna dari bentuk A<B<1
ini tidak diperbolehkan.
Jadi ekspresi A<B
cocok dengan fungsi F4, dan A<B<1
harus diubah ke (A<B)<1
atau A<(B<1)
.
Untuk membuktikan bahwa ke-15 fungsi lainnya dapat diubah menjadi ekspresi, cukuplah untuk membentuk seperangkat ekspresi yang secara fungsional lengkap , karena dengan demikian, menurut definisi, mereka dapat dikomposisikan menjadi ekspresi untuk fungsi apa pun.
Satu set ekspresi seperti itu adalah x<1
(di mana x
ada A
atau B
), yang mana ¬x
, dan (((B<A)<1)<A)<1
yang mana A → B
. Negasi ( ¬
) dan implikasi ( →
) diketahui lengkap secara fungsional.
Tantangan
Dengan menggunakan karakter ()<AB10
, tulis 16 ekspresi dalam bentuk yang dijelaskan di atas yang setara dengan masing-masing dari 16 fungsi boolean yang berbeda.
Tujuannya adalah untuk membuat masing-masing ekspresi sesingkat mungkin. Skor Anda adalah jumlah dari jumlah karakter di masing-masing dari 16 ekspresi Anda. Skor terendah menang. Tiebreaker pergi ke jawaban paling awal (asalkan mereka tidak mengedit jawaban mereka nanti dengan ekspresi yang lebih pendek diambil dari orang lain).
Anda tidak secara teknis perlu menulis kode nyata untuk kontes ini tetapi jika Anda memang menulis program apa pun untuk membantu Anda menghasilkan ekspresi, Anda sangat dianjurkan untuk mempostingnya.
Anda dapat menggunakan Potongan Stack ini untuk memeriksa apakah ekspresi Anda melakukan apa yang diharapkan:
sumber
(0, 0, 0, 1, 0, 1, 1, 0)
dan(0, 1, 1, 0, 1, 0, 0, 0)
.Jawaban:
100 karakter
sumber
Ada beberapa opsi untuk beberapa di antaranya, jadi set 100-char ini tidak identik dengan yang diposting sebelumnya.
Bukti yang lebih mudah yang
<
secara fungsional lengkap adalah yangA<(B<1)
memberikan NOR.Kode yang saya gunakan untuk menemukan ini adalah penyederhanaan berat dari beberapa kode optimasi Boolean yang saya gunakan pada tantangan sebelumnya, dengan dua perubahan kecil:
sumber
A<B<1
yang tidak diperbolehkan. " Jika demikian, periksa cap waktu: itu tadinya hasil edit dilakukan setelah jawaban ini.100 karakter
sumber
100 karakter
Hei, itu tidak persis sama dengan yang lain. Saya menghabiskan waktu 10 menit untuk ini, jadi ada baiknya memposting, walaupun ini sudah 2 tahun.
sumber
100 karakter
sumber