Ekspresikan semua 16 fungsi boolean dengan operator yang kurang dari itu

15

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<1ini tidak diperbolehkan.

Jadi ekspresi A<Bcocok dengan fungsi F4, dan A<B<1harus diubah ke (A<B)<1atau 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 xada Aatau B), yang mana ¬x, dan (((B<A)<1)<A)<1yang 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:

Hobi Calvin
sumber
8
-1, masalahnya terlalu sederhana.
isaacg
2
Yah saya kira tidak ada gunanya memposting jawaban lain , jadi inilah upaya saya .
Sp3000
7
@isaacg Anda benar. Saya akan mengatakan itu jauh dari kontes PPCG paling sederhana yang pernah ada tetapi fakta bahwa jawaban optimal akan hampir persis sama membuatnya agak membosankan sebagai sebuah kompetisi. Namun, saya lakukan pikir itu berfungsi baik-baik saja sebagai latihan pribadi, terutama bagi orang-orang yang bukan ahli dalam logika. Saya yakin setidaknya setengah dari orang-orang di PPCG ada di sini untuk bersenang-senang, bukan hanya untuk menang, atau orang tidak akan pernah menjawab pertanyaan dengan kiriman yang tidak menang.
Calvin Hobbies
Saya mungkin akan membandingkan ini dengan latihan golf yang kontroversial . Ini adalah pertanyaan yang menyenangkan dan menarik, jika agak mudah.
Sp3000
2
Jika ada yang tertarik, inilah 3 variabel. Ekspresi terpanjang sesuai dengan (0, 0, 0, 1, 0, 1, 1, 0)dan (0, 1, 1, 0, 1, 0, 0, 0).
Sp3000

Jawaban:

5

100 karakter

0
(A<1)<B
B<A
A
A<B
B
((B<A)<((A<B)<1))<1
(A<(B<1))<1
A<(B<1)
(B<A)<((A<B)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<1)<B)<1
1
jimmy23013
sumber
9

Ada beberapa opsi untuk beberapa di antaranya, jadi set 100-char ini tidak identik dengan yang diposting sebelumnya.

0
(B<A)<A
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(A<(B<1))<1
A<(B<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((B<A)<A)<1
1

Bukti yang lebih mudah yang <secara fungsional lengkap adalah yang A<(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:

  1. Jadikan skor ekspresi menjadi panjang stringnya, bukan jumlah operasi.
  2. Buat string menghindari kurung yang tidak perlu, untuk memperkecil panjangnya.
import java.util.*;

public class PPCG48193 {

    public static void main(String[] args) {
        Expr[] optimal = new Expr[16];
        int unfound = 16;

        PriorityQueue<Expr> q = new PriorityQueue<Expr>();
        q.offer(new Expr(0, "0"));
        q.offer(new Expr(15, "1"));
        q.offer(new Expr(3, "A"));
        q.offer(new Expr(5, "B"));
        while (unfound > 0) {
            Expr e = q.poll();
            if (optimal[e.val] != null) continue;

            optimal[e.val] = e;
            unfound--;
            for (Expr e2 : optimal) {
                if (e2 != null) {
                    Expr e3 = e.op(e2), e4 = e2.op(e);
                    if (optimal[e3.val] == null) q.offer(e3);
                    if (optimal[e4.val] == null) q.offer(e4);
                }
            }
        }

        for (Expr e : optimal) System.out.println(e.expr);
    }

    private static class Expr implements Comparable<Expr> {
        public final int val;
        public String expr;

        public Expr(int val, String expr) {
            this.val = val;
            this.expr = expr;
        }

        public Expr op(Expr e) {
            String l = expr.contains("<") ? String.format("(%s)", expr) : expr;
            String r = e.expr.contains("<") ? String.format("(%s)", e.expr) : e.expr;
            return new Expr((15 - val) & e.val, String.format("%s<%s", l, r));
        }

        public int compareTo(Expr e) {
            int cmp = expr.length() - e.expr.length();
            if (cmp == 0) cmp = val - e.val;
            return cmp;
        }
    }
}
Peter Taylor
sumber
Berapa jumlah total karakter?
user253751
@immibis, 100 karakter, sama seperti yang lainnya.
Peter Taylor
"hindari tanda kurung yang tidak perlu, untuk memperkecil panjangnya" tidak, kamu tidak menghindarinya sehingga kamu akan memendekkan tetapi untuk mematuhi aturan.
Erik the Outgolfer
@EriktheOutgolfer, saya tidak 100% yakin apa yang Anda maksud, tapi tebakan terbaik saya adalah bahwa Anda merujuk pada " Ini berarti bahwa tidak ada paretik dan ekspresi formulir A<B<1yang tidak diperbolehkan. " Jika demikian, periksa cap waktu: itu tadinya hasil edit dilakukan setelah jawaban ini.
Peter Taylor
2

100 karakter

0
(A<B)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(B<(A<1))<1
B<(A<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<B)<B)<1
1
isaacg
sumber
1

100 karakter

0
(A<1)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
((B<1)<A)<1
(B<1)<A
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<1)<B)<1
1

Hei, itu tidak persis sama dengan yang lain. Saya menghabiskan waktu 10 menit untuk ini, jadi ada baiknya memposting, walaupun ini sudah 2 tahun.

nog642
sumber
0

100 karakter

0
(A<1)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(A<(B<1))<1
A<(B<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((B<1)<A)<1
1
Erik the Outgolfer
sumber