Apakah || dan! operator cukup untuk membuat setiap kemungkinan ekspresi logis?

Ekspresi logis ( a && b ) (keduanya adan bmemiliki nilai boolean) dapat ditulis seperti !(!a || !b), misalnya. Bukankah ini berarti &&"tidak perlu"? Apakah ini berarti bahwa semua ekspresi logis hanya dapat dibuat menggunakan ||dan !?

Ya, seperti yang ditunjukkan oleh jawaban lain, sekumpulan operator terdiri dari ||dan !secara fungsional lengkap . Berikut ini adalah bukti konstruktif dari itu, menunjukkan bagaimana menggunakannya untuk mengekspresikan semua enam belas kemungkinan koneksi logis antara variabel boolean Adan B:

• Benar :A || !A
• A NAND B :!A || !B
• B menyiratkan A :!B || A
• A menyiratkan B :!A || B
• A ATAU B :A || B
• Bukan B :!B
• Bukan A :!A
• A XOR B :!(!A || B) || !(A || !B)
• A XNOR B :!(!A || !B) || !(A || B)
• A :A
• B :B
• A NOR B :!(A || B)
• A tidak menyiratkan B :!(!A || B)
• B tidak menyiratkan A :!(!B || A)
• A DAN B :!(!A || !B)
• Salah :!(A || !A)

Perhatikan bahwa NAND dan NOR sendiri secara fungsional telah selesai (yang dapat dibuktikan menggunakan metode yang sama di atas), jadi jika Anda ingin memverifikasi bahwa satu set operator secara fungsional selesai, itu cukup untuk menunjukkan bahwa Anda dapat mengekspresikan NAND atau NOR dengan itu.

Berikut ini adalah grafik yang menunjukkan diagram Venn untuk masing-masing penghubung yang tercantum di atas:

[ sumber ]

Apa yang Anda gambarkan adalah kelengkapan fungsional .

Ini menggambarkan seperangkat operator logis yang cukup untuk "mengungkapkan semua tabel kebenaran yang mungkin". Set operator Java Anda, { ||,! }, cukup; itu sesuai dengan set {∨, ¬}, yang terdaftar di bawah bagian "Minimal set lengkap operator fungsional".

Himpunan semua tabel kebenaran berarti semua set yang mungkin dari 4 nilai boolean yang dapat merupakan hasil operasi antara 2 nilai boolean. Karena ada 2 nilai yang mungkin untuk boolean, ada 2 ⁴ , atau 16, tabel kebenaran yang mungkin.

A B | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
----+------------------------------------------------
T T | T  T  T  T  T  T  T  T  F  F  F  F  F  F  F  F
T F | T  T  T  T  F  F  F  F  T  T  T  T  F  F  F  F
F T | T  T  F  F  T  T  F  F  T  T  F  F  T  T  F  F 
F F | T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F

Berikut adalah tabel angka-angka tabel kebenaran (0-15), ||dan !kombinasi yang menghasilkannya, dan deskripsi.

Table  |  Operation(s)                    | Description
-------+----------------------------------+-------------
  0    | A || !A                          | TRUE
  1    | A || B                           | OR
  2    | A || !B                          | B IMPLIES A
  3    | A                                | A
  4    | !A || B                          | A IMPLIES B
  5    | B                                | B
  6    | !(!A || !B) || !(A || B)         | XNOR (equals)
  7    | !(!A || !B)                      | AND
  8    | !A || !B                         | NAND
  9    | !(A || !B) || !(!A || B)         | XOR
 10    | !B                               | NOT B
 11    | !(!A || B)                       | NOT A IMPLIES B
 12    | !A                               | NOT A
 13    | !(A || !B)                       | NOT B IMPLIES A
 14    | !(A || B)                        | NOR
 15    | !(A || !A)                       | FALSE

Ada banyak set lengkap yang berfungsi seperti itu, termasuk set elemen satu {NAND} dan {NOR}, yang tidak memiliki operator tunggal yang sesuai di Jawa.

Iya.

Semua gerbang logika dapat dibuat dari gerbang NOR.

Karena gerbang NOR dapat dibuat dari TIDAK dan OR, hasilnya mengikuti.

Luangkan waktu untuk membaca Hukum DeMorgan jika Anda bisa.

Anda akan menemukan jawabannya di bacaan di sana, serta referensi ke bukti logis.

Tetapi pada dasarnya, jawabannya adalah ya.

EDIT : Sebagai penjelasan, poin saya adalah bahwa seseorang dapat secara logis mengambil ekspresi ATAU dari ekspresi DAN, dan sebaliknya. Ada lebih banyak hukum juga untuk kesetaraan dan kesimpulan logis, tapi saya pikir ini yang paling tepat.

EDIT 2 : Berikut ini adalah bukti melalui tabel kebenaran yang menunjukkan kesetaraan logis dari ungkapan berikut.

Hukum DeMorgan: !(!A || !B) -> A && B

 _____________________________________________________
| A | B | ! A | ! B | ! A || ! B | ! (! A ||! B) | A && B |
-------------------------------------------------- -----
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
-------------------------------------------------- -----
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
-------------------------------------------------- -----
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
-------------------------------------------------- -----
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
_______________________________________________________

NAND dan NOR bersifat universal, mereka dapat digunakan untuk membangun operasi logis yang Anda inginkan di mana saja; operator lain tersedia dalam bahasa pemrograman untuk membuatnya mudah untuk menulis dan membuat kode yang dapat dibaca.

Juga semua operasi logis yang diperlukan untuk kabel di sirkuit juga dikembangkan menggunakan IC hanya NAND atau NOR.

Ya, menurut aljabar Boolean, fungsi Boolean apa pun dapat dinyatakan sebagai jumlah minterm atau produk maxterms, yang disebut bentuk normal kanonik . Tidak ada alasan mengapa logika seperti itu tidak dapat diterapkan pada operator yang sama yang digunakan dalam ilmu komputer.

https://en.wikipedia.org/wiki/Canonical_normal_form