Kelengkapan Fungsional dari logika 3-dihargai

Dalam konteks beberapa karya terbaru , kami telah mendefinisikan bahasa berdasarkan logika bernilai tiga à la Kleene, di mana berarti benar, untuk salah, dan untuk kesalahan atau tidak tahu. Untuk menunjukkan bahwa bahasa kami ekspresif, kami ingin membuktikan bahwa kami dapat membangun satu set operator yang secara fungsional lengkap. $1$ $0$ $\bot$

Cukup sulit untuk menemukan hasil yang ada dalam literatur. Kami menemukan satu makalah yang ditulis pada tahun 1962 oleh Jobe, yang menyatakan teorema berikut:

Jobe 1962 Theorem Paper (akses terbatas).

Logika tiga nilai diekspresikan pada set dan ditentukan oleh operator dan , yang diberikan di bawah ini, secara fungsional lengkap. $E$ $\{1, 2, 3\}$ $\bullet, E_1$ $E_2$

$\begin{array}{cccccc} ∙ & 3 & 2 & 1 & E_{1} & E_{2} \\ 3 & 3 & 2 & 1 & 3 & 1 \\ 2 & 2 & 2 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 2 & 3 \end{array}$ $\begin{array}{c|ccc|c|c} ~\bullet~ & ~3~ & ~2~ & ~1~ & ~E_1~ & ~E_2~ \\ \hline 3 & 3 & 2 & 1 & 3 & 1 \\ 2 & 2 & 2 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 2 & 3 \end{array}$

Dalam makalah kami, kami telah menggunakan hasil ini dengan menunjukkan korespondensi antara operator kami dan yang didefinisikan oleh Jobe (secara kasar, kami menggunakan konjungsi yang kuat, negasi, dan operator yang mengubah tidak-tahu salah).

Perhatian utama saya adalah bahwa saya sebenarnya tidak dapat memahami bukti kelengkapan fungsional Jobe, dan kami belum dapat menemukan hasil lain (positif atau negatif) setelah tanggal ini, yang entah bagaimana agak mengejutkan.

Jadi pertanyaan saya adalah sebagai berikut: apakah ada beberapa hasil yang lebih diketahui tentang kelengkapan fungsional logika 3-nilai? Setiap info dalam arah ini akan sangat membantu.

reference-request lo.logic Charles
sumber

3

$3$

3

$3$

@ EmilJeřábek Terima kasih, saya baru saja membaca tentang Logika Pos Ternary, dan itu sepertinya sesuai (walaupun saya juga tidak dapat menemukan banyak tentang topik ini). Apakah Anda memiliki referensi tentang bidang 3-elemen? Google agak terlalu kabur.

Charles

1 + 1 + \dots + 1

$1+1+\cdots+1$

{+, \cdot, 1}

$\{+,\cdot,1\}$

Bab 5 dan 6 buku [Fungsi aljabar pada set yang terbatas, Dietlinde Lau, 2006] berisi perlakuan mendalam tentang kelengkapan fungsional dalam banyak logika yang dihargai (termasuk bukti). Ringkasnya: Rosenbergs [1965, 1970] karakterisasi klon maksimal (juga disebut klon prakomplet) memberikan kriteria untuk kelengkapan fungsional dalam k-dihargai logika untuk setiap k.

Untuk kasus khusus dari logika bernilai 3, karakterisasi seperti itu (terdiri dari 18 kelas maksimal / prakomplet) telah diberikan oleh Jablonskij pada tahun 1954. Oleh karena itu, untuk memverifikasi bahwa set Anda dari "operator" bernilai 3 ini secara fungsional lengkap, itu sudah cukup untuk memastikan bahwa mereka tidak termasuk dalam salah satu dari 18 kelas prakualifikasi.

Gustav Nordh
sumber

Kelengkapan Fungsional dari logika 3-dihargai

Jawaban: