§4. Setara, rumus TI dan TL aljabar logika. Kesetaraan dasar. (Hukum operasi logis). Hukum dualitas.
Definisi.
Dua rumus aljabar logika A dan B disebut SETARA jika keduanya mengambil nilai logika yang sama pada himpunan pernyataan dasar mana pun yang termasuk dalam rumus tersebut. Kesetaraan rumus akan kita nyatakan dengan tanda º, dan notasi A ºB berarti rumus A dan B ekuivalen.
Rumus A disebut BENAR IDENTIK (atau TAUTOLOGI) jika mengambil nilai 1 untuk semua nilai variabel yang termasuk di dalamnya.
Suatu rumus disebut IDENTIK SALAH (atau KONTRADISI) jika mengambil nilai 0 untuk semua nilai variabel yang ada di dalamnya.
Terdapat hubungan antara konsep kesetaraan dan kesetaraan sebagai berikut: jika rumus A dan B ekuivalen, maka rumus A"B merupakan tautologi, dan sebaliknya, jika rumus A"B merupakan tautologi, maka rumus A dan B setara.
Kesetaraan aljabar logika yang paling penting dapat dibagi menjadi tiga kelompok.
1. Kesetaraan dasar.
Hukum idempotensi.
Hukum kontradiksi
Hukum kelompok menengah yang dikecualikan
Hukum Penghapusan Negasi Ganda
hukum penyerapan
2. Persamaan yang menyatakan beberapa operasi logis melalui yang lain.
Di sini 3, 4, 5, 6 adalah hukum Morgan.
Jelas bahwa persamaan 5 dan 6 masing-masing diperoleh dari persamaan 3 dan 4, jika kita mengambil negasi dari kedua bagian yang terakhir dan menggunakan hukum menghilangkan negasi ganda.
Jadi, empat persamaan pertama memerlukan pembuktian. Mari kita buktikan salah satunya: yang pertama.
Karena dengan nilai logika yang sama x dan y rumus https://pandia.ru/text/78/396/images/image018.gif" width="124" height="21"> adalah benar. Oleh karena itu, dalam dalam hal ini kedua bagian ekivalensi mempunyai nilai sebenarnya yang sama.
Sekarang misalkan x dan y memiliki nilai logika yang berbeda. Maka kesetaraan dan salah satu dari dua implikasi tersebut atau akan salah. Namun konjungsinya juga salah 
.
Jadi, dalam hal ini kedua sisi kesetaraan mempunyai makna logis yang sama.
Kesetaraan 2 dan 4 dibuktikan dengan cara yang sama.
Dari persamaan kelompok ini dapat disimpulkan bahwa rumus apa pun dalam aljabar logika dapat diganti dengan rumus ekuivalen yang hanya berisi dua operasi logika: konjungsi dan negasi atau disjungsi dan negasi.
Tidak ada lagi penghapusan operasi logis yang mungkin dilakukan. Jadi, jika kita hanya menggunakan konjungsi, maka rumus negasi tidak dapat dinyatakan dengan operasi konjungsi.
Namun, ada operasi yang dapat diekspresikan dengan salah satu dari lima operasi logika yang kita gunakan. Operasi semacam itu, misalnya, operasi “Schaeffer's stroke”. Operasi ini ditunjukkan dengan simbol ½ kiri " style="border-collapse:collapse;border:none;margin-left:6.75pt;margin-right: 6.75pt">
Hukum aljabar proposisional
Aljabar proposisional (aljabar logika) adalah bagian logika matematika yang mempelajari operasi logika pada pernyataan dan aturan untuk mentransformasikan pernyataan kompleks.
Saat menyelesaikan banyak hal masalah logis Seringkali rumus yang diperoleh perlu disederhanakan dengan memformalkan kondisinya. Penyederhanaan rumus dalam aljabar proposisional dilakukan atas dasar transformasi ekuivalen berdasarkan hukum logika dasar.
Hukum aljabar proposisional (aljabar logika) - ini adalah tautologi.
Terkadang hukum-hukum ini disebut teorema.
Dalam aljabar proposisional, hukum logika dinyatakan dalam bentuk persamaan rumus yang setara. Di antara hukum-hukum tersebut, hukum-hukum yang memuat satu variabel menonjol.
Empat hukum pertama di bawah ini adalah hukum dasar aljabar proposisional.
Hukum identitas:
SEBUAH = SEBUAH
Setiap konsep dan penilaian identik dengan dirinya sendiri.
Hukum identitas berarti bahwa dalam proses berpikir seseorang tidak dapat menggantikan suatu pemikiran dengan pemikiran lain, konsep yang satu dengan konsep yang lain. Jika undang-undang ini dilanggar, kesalahan logika mungkin terjadi.
Misalnya, alasannya benar bahwa mereka mengatakan bahwa bahasa akan membawa Anda ke Kyiv, tetapi saya membeli lidah asap kemarin, yang berarti sekarang saya dapat salah pergi ke Kyiv dengan aman, karena kata pertama dan kedua "bahasa" memiliki arti konsep yang berbeda.
Dalam penalaran: Gerakan itu abadi. Berjalan ke sekolah adalah gerakan. Oleh karena itu, di sekolah selamanya, kata "gerakan" digunakan dalam dua pengertian yang berbeda (yang pertama - dalam pengertian filosofis- sebagai atribut materi, yang kedua - dalam arti biasa - sebagai tindakan bergerak di ruang angkasa), yang mengarah pada kesimpulan yang salah.
Hukum non-kontradiksi :
Pada saat yang sama, suatu pernyataan bisa benar atau salah, tidak ada pilihan ketiga. Benar atau tidaknya A. Contoh pemenuhan hukum tengah yang dikecualikan:
1. Angka 12345 genap atau ganjil, tidak ada pilihan ketiga.
2. Perusahaan beroperasi dalam keadaan rugi atau impas.
3. Cairan ini mungkin asam atau bukan.
Hukum pengecualian tengah bukanlah hukum yang diakui oleh semua ahli logika sebagai hukum logika universal. Hukum ini berlaku ketika kognisi berhubungan dengan situasi yang kaku: "salah satu - atau", "benar-salah". Ketika ketidakpastian terjadi (misalnya, dalam memikirkan masa depan), hukum bagian tengah yang dikecualikan sering kali tidak dapat diterapkan.
Perhatikan pernyataan berikut: Kalimat ini salah. Itu tidak mungkin benar karena dinyatakan salah. Tapi itu juga tidak bisa salah, karena itu benar. Pernyataan ini tidak benar atau salah, dan karena itu melanggar hukum bagian tengah yang dikecualikan.
Paradoks (Yunani paradoxos - tak terduga, aneh) dalam contoh ini muncul karena kalimat tersebut mengacu pada dirinya sendiri. Paradoks terkenal lainnya adalah masalah penata rambut: Di suatu kota, seorang penata rambut memotong rambut semua penduduknya, kecuali mereka yang memotong rambutnya sendiri. Siapa yang memotong rambut tukang cukur? Secara logika, karena formalitasnya, tidak mungkin diperoleh bentuk pernyataan yang merujuk pada diri sendiri tersebut. Ini sekali lagi menegaskan gagasan bahwa dengan bantuan aljabar logika tidak mungkin mengungkapkan semua pemikiran dan argumen yang mungkin. Mari kita tunjukkan bagaimana, berdasarkan definisi kesetaraan proposisional, hukum aljabar proposisional lainnya dapat diperoleh.
Sebagai contoh, mari kita tentukan apa yang setara dengan A (setara dengan) (negasi ganda dari A, yaitu negasi dari negasi A). Untuk melakukannya, kita akan membuat tabel kebenaran:
Menurut definisi kesetaraan, kita harus mencari kolom yang nilainya sesuai dengan nilai kolom A. Ini akan menjadi kolom A.
Dengan demikian, kita dapat merumuskan hukum negasi ganda:
Jika Anda meniadakan suatu pernyataan dua kali, hasilnya adalah pernyataan asli. Misalnya pernyataan A = Matroskin - kucing setara dengan pernyataan A = Tidak benar Matroskin bukan kucing.
Dengan cara yang sama, hukum-hukum berikut dapat diturunkan dan diverifikasi:
Sifat-sifat konstanta:
Hukum idempotensi:
Tidak peduli berapa kali kita mengulanginya: TV menyala atau TV menyala atau TV menyala... arti dari pernyataan tersebut tidak akan berubah. Demikian pula, jika diulangi, di luar hangat, di luar hangat,... tidak akan menjadi lebih hangat satu derajat pun.
Hukum komutatifitas:
A v B = B v A
A & B = B & A
Operan A dan B dapat dipertukarkan dalam operasi disjungsi dan konjungsi.
Hukum asosiatif:
A v(B v C) = (A v B) v C;
SEBUAH & (B & C) = (A & B) & C.
Jika ekspresi hanya menggunakan operasi disjungsi atau operasi konjungsi saja, maka Anda dapat mengabaikan tanda kurung atau menyusunnya secara sembarangan.
Hukum distributif:
A v (B & C) = (A v B) &(A v C)
(distribusi disjungsi
relatif terhadap konjungsi)
A & (B v C) = (A & B) v (A & C)
(distribusi konjungsi
tentang disjungsi)
Hukum distributif konjungsi relatif terhadap disjungsi mirip dengan hukum distributif dalam aljabar, namun hukum distributif disjungsi relatif terhadap konjungsi tidak mempunyai analogi; hukum distributif hanya berlaku dalam logika. Oleh karena itu perlu dibuktikan. Pembuktiannya paling mudah dilakukan dengan menggunakan tabel kebenaran:
Hukum penyerapan:
A v (A & B) = A
SEBUAH & (A v B) = SEBUAH
Buktikan sendiri hukum serapan.
Hukum De Morgan:
Rumusan verbal hukum De Morgan:
Aturan mnemonik: di sisi kiri identitas, operasi negasi berada di atas seluruh pernyataan. Di sisi kanan, tampaknya putus dan negasinya berdiri di atas setiap pernyataan sederhana, tetapi pada saat yang sama operasinya berubah: disjungsi menjadi konjungsi dan sebaliknya.
Contoh penerapan hukum De Morgan:
1) Pernyataan Saya tidak tahu bahasa Arab atau Cina sama dengan pernyataan saya tidak tahu bahasa Arab dan tidak tahu bahasa Cina.
2) Pernyataan Tidak benar bahwa saya mempelajari suatu pelajaran dan mendapat nilai buruk di dalamnya sama dengan pernyataan Saya tidak mempelajari pelajaran tersebut, atau saya tidak mendapat nilai buruk di dalamnya.
Mengganti operasi implikasi dan kesetaraan
Operasi implikasi dan kesetaraan terkadang tidak termasuk dalam operasi logis komputer tertentu atau penerjemah dari bahasa pemrograman. Namun, untuk menyelesaikan banyak masalah, operasi ini diperlukan. Terdapat aturan untuk mengganti operasi ini dengan rangkaian operasi negasi, disjungsi, dan konjungsi.
Dengan demikian, operasi implikasi dapat diganti sesuai dengan aturan berikut:
Ada dua aturan untuk mengganti operasi ekuivalen:
Validitas rumus ini mudah untuk diverifikasi dengan membuat tabel kebenaran untuk sisi kanan dan kiri kedua identitas.
Pengetahuan tentang aturan penggantian operasi implikasi dan kesetaraan membantu, misalnya, menyusun negasi implikasi dengan benar.
Perhatikan contoh berikut.
Biarkan pernyataan diberikan:
E = Tidak benar jika saya memenangkan kompetisi maka saya akan mendapat hadiah.
Membiarkan A = Saya akan memenangkan kompetisi,
B = Saya akan menerima hadiah.
Kemudian
Dari sini, E = Saya akan memenangkan kompetisi, namun saya tidak akan menerima hadiah.
Matematika Diskrit: Logika Matematika
Kuliah 8
Minimalkan fungsi Boolean. Metode Quine-McCluskey
Hukum aljabar Boole
DI DALAM logika matematika aljabar khusus didefinisikan, aljabar Boole, berisi operasi perkalian logika, penjumlahan logika, dan negasi ( , +, - ), yang memungkinkan transformasi ekspresi logika yang identik. Undang-undang ini mencakupHukum idempotensi (kesamaan)
Hukum komutatifitas
ab = ba
Hukum asosiatif
a + (b + c) = (a + b) + c
a (b c) = (a b) c
Hukum distribusi
Distribusi konjungsi relatif terhadap disjungsi
A (b + c) = a b + a c
Distribusi disjungsi relatif terhadap konjungsi
A + b c = (a + b) (a + c)
hukum negasi ganda
hukum De Morgan
Hukum penyerapan
a + a b = a
a (a + b) = a
Hukum yang mendefinisikan tindakan dengan konstanta logika 0 dan 1
| sebuah + 0 = sebuah a 0 = 0 | sebuah+1=1 a 1 = a |
| 1 = 0 |
|
Keabsahan seluruh undang-undang yang dibahas di atas dapat dibuktikan dengan mudah, misalnya dengan menggunakan tabel kebenaran.
Hukum tambahan
Hukum tambahan aljabar Boole merupakan konsekuensi dari hukum dasar dan sangat berguna dalam menyederhanakan penulisan fungsi logika.
Hukum Ikatan
Pembuktian identitas ini dilakukan dengan menggunakan hukum distribusi pertama:
Pembuktian identitas ini dilakukan dengan menggunakan hukum distribusi kedua:
Hukum Blake-Poretsky
Menerapkan hukum aksi dengan konstanta logika, idempotensi dan perekatan, identitas tersebut dapat dibuktikan sebagai berikut:
Hukum konvolusi ekspresi logis
Identitas ini dapat dibuktikan dengan secara konsisten menggunakan hukum bekerja dengan konstanta logika, distributifitas, idempotensi, dan perekatan:
Menyederhanakan Fungsi Logika
Untuk bentuk representasi fungsi normal, konsep kompleksitas fungsi didefinisikan sebagai jumlah suku primer dalam representasi tersebut. Transformasi bentuk normal untuk mengurangi kompleksitas suatu fungsi disebut penyederhanaan . Untuk menyederhanakan fungsi logika, semua hukum aljabar logika digunakan.Tugas.
Sederhanakan SDNF dengan fungsi berikut:
1. (A B) C
2. (A B) C
Mari kita nyatakan fungsi tersebut dalam bentuk disjungtif sempurna dan sederhanakan menggunakan hukum aljabar logika:
3.
Mari kita nyatakan fungsi tersebut dalam bentuk disjungtif sempurna dan sederhanakan menggunakan hukum aljabar logika:
SDNF = 
Tidak ada penyederhanaan lebih lanjut yang mungkin dilakukan.
4. 
Mari kita nyatakan fungsi tersebut dalam bentuk disjungtif sempurna dan sederhanakan menggunakan hukum aljabar logika:
SDNF =
5. 
Mari kita nyatakan fungsi tersebut dalam bentuk disjungtif sempurna dan sederhanakan menggunakan hukum aljabar logika:
Metode Quine-McCluskey
Minimalkan fungsi logika dapat dilakukan dengan menggunakan metode Quine-McCluskey yang terdiri dari empat langkah:
Mari kita nyatakan himpunan (konstituen) yang fungsinya benar dalam bentuk ekuivalen biner.
Mari kita susun ekuivalen biner ke dalam tingkatan (sesuai dengan jumlah unit ekuivalen biner) dan rekatkan (terapkan aturan pengeleman pada konstituen yang sesuai) himpunan dalam tingkatan yang berdekatan, dapatkan interval maksimum selama mungkin; Kami menandai setiap set yang terlibat dalam perekatan. Hanya himpunan atau interval tersebut yang digabungkan, perbedaannya hanya pada nilai satu digit: 001 dan 000, 001- dan 101-, dst.
Mari kita buat tabel Quine, kolom-kolomnya sesuai dengan himpunan kebenaran biner dari fungsi tersebut, dan baris-barisnya sesuai dengan interval maksimum. Jika himpunan ke-i ditutupi oleh interval ke-j, maka kita letakkan 1 pada perpotongan baris dan kolom yang bersesuaian, jika tidak kita masukkan 0 atau tidak sama sekali.
Kami menemukan cakupan minimum dari tabel Quine, yang terdiri dari jumlah minimum interval maksimal yang mencakup (mencakup) semua tupel yang fungsinya benar.
Setara biner dari himpunan sebenarnya adalah:
| 1 | 0001 |
| 3 | 0011 |
| 5 | 0101 |
| 7 | 0111 |
| 11 | 1011 |
| 13 | 1101 |
| 15 | 1111 |
Mari kita susun kumpulan biner menjadi beberapa tingkatan dan lakukan pengeleman selama mungkin
| 0001 | 00-1 | 0-1 |
| 0011 | 0-01 | --11 |
| 0101 | -011 | -1-1 |
| 0111 | 0-11 | |
| 1101 | -101 | |
| 1011 | 01-1 | |
| 1111 | 11-1 | |
| -111 | ||
| 1-11 |
Lalu kita membuat tabel Quine:
| 0001 | 0011 | 0101 | 0111 | 1011 | 1101 | 1111 |
|
| 0--1 | 1 | 1 | 1 | 1 | |||
| --11 | 1 | 1 | 1 | 1 | 1 |
||
| -1-1 | 1 | 1 | 1 | 1 |
Dalam tabel kita, himpunan 0001 dan 1011 tercakup dalam satu-satunya cara yang memungkinkan; oleh karena itu, interval minimum yang mencakup himpunan tersebut disebut wajib dan bentuk inti pelapis, Karena harus disertakan dalam lapisan apa pun. Dalam tabel, unit-unit terkait digarisbawahi; interval (0- -1,- -11) tidak hanya membentuk cakupan inti, tetapi juga mencakup seluruh tabel Quine.
Dengan demikian, diperoleh bentuk minimal dari fungsi yang diteliti berupa:
MDNF = (0 - - 1, - - 1 1) = 
Mari kita lihat beberapa contoh.
Tugas.
1. Temukan fungsi MDNFF1 =
f1
| x1 x2 x3 x4 | |
| 0 0 0 0 | 0 |
| 0 0 0 1 | 1 |
| 0 0 1 0 | 1 |
| 0 0 1 1 | 1 |
| 0 1 0 0 | 1 |
| 0 1 0 1 | 0 |
| 0 1 1 0 | 0 |
| 0 1 1 1 | 1 |
| 1 0 0 0 | 0 |
| 1 0 0 1 | 1 |
| 1 0 1 0 | 1 |
| 1 0 1 1 | 1 |
| 1 1 0 0 | 0 |
| 1 1 0 1 | 1 |
| 1 1 1 0 | 0 |
| 1 1 1 1 | 1 |
DNF sempurna dari fungsi yang diteliti berbentuk:
| 0001 | 00-1 | -0-1 |
| 0010 | -001 | -01- |
| 0100 | 001- | --11 |
| 0011 | -010 | 1-1 |
| 1010 | 0-11 | |
| 1001 | -011 | |
| 0111 | 101- | |
| 1011 | 10-1 | |
| 1101 | 1-01 | |
| 1111 | -111 | |
| 1-11 | ||
| 11-1 |
Kolom pertama berisi himpunan yang tidak terlibat dalam penggabungan apa pun - himpunan itu sendiri adalah interval maksimum 0100. Di kolom ketiga, empat interval maksimum lagi ditambahkan ke dalamnya: (-0-1, -01-, --11, 1 --1 ).
Kami membuat tabel Quine:
| 0001 | 0010 | 0100 | 0011 | 1010 | 1001 | 0111 | 1011 | 1101 | 1111 |
|
| 0100 | 1 | |||||||||
| -0-1 | 1 | 1 | 1 | 1 | ||||||
| -01- | 1 | 1 | 1 | 1 | ||||||
| --11 | 1 | 1 | 1 | 1 |
||||||
| 1--1 | 1 | 1 | 1 | 1 |
Mari kita tentukan inti cakupan, yang akan mencakup interval wajib:
(0100, -0-1, -01-, --11). DI DALAM pada kasus ini, kernel cakupan mencakup seluruh tabel secara keseluruhan.
Bentuk normal disjungtif minimal f1 adalah:
2. Temukan fungsi MDNF F 2( X 1, X 2, X 3), yang mengambil nilai tunggal pada himpunan 0,2,3,6 dan 7.
Mari kita buat tabel kebenarannya F2
| x1 x2 x3 | F2 |
| 0 0 0 | 1 |
| 0 0 1 | 0 |
| 0 1 0 | 1 |
| 0 1 1 | 1 |
| 1 0 0 | 0 |
| 1 0 1 | 0 |
| 1 1 0 | 1 |
| 1 1 1 | 1 |
SDNF =
Mari kita susun kumpulan biner ke dalam tingkatan dan lakukan perekatan:
| 000 | 0-0 | --0 |
| 010 | -00 | |
| 100 | -10 | |
| 110 | 1-0 | |
| 111 | 11- |
Sebagai hasil pengeleman, kami hanya mendapat dua interval maksimum: (11-, --0). Tanpa membuat tabel Quine, jelas bahwa mereka membentuk cakupan minimum, karena menghapus salah satu interval ini akan mengakibatkan hilangnya himpunan yang fungsi f2(x1, x2, x3 ) BENAR. MDNF = x1 x2 +x3.
LITERATUR
Guseva A.I. Pembelajaran ilmu komputer: masalah dan cara penyelesaiannya - M.: DIALOG-MEPhI, 2003.
Gorbatov V.A. Dasar-dasar matematika diskrit. - M.: Sains. Fizmatlit, 1999.-544s
Komputer modern, berdasarkan komputer elektronik “kuno”, mengandalkan postulat tertentu sebagai prinsip dasar pengoperasiannya. Hukum-hukum tersebut disebut hukum aljabar logika. Untuk pertama kalinya disiplin ilmu seperti itu dijelaskan (tentu saja, tidak sedetail pada bentuk modern) oleh ilmuwan Yunani kuno Aristoteles.
Mewakili cabang matematika yang terpisah, di mana kalkulus proposisi dipelajari, aljabar logika memiliki sejumlah kesimpulan dan kesimpulan yang terstruktur dengan jelas.
Untuk lebih memahami topik ini, kami akan menganalisis konsep-konsep yang akan membantu mempelajari hukum aljabar logika di masa depan.
Mungkin istilah utama dalam disiplin ilmu yang dipelajari adalah pernyataan. Ini adalah pernyataan tertentu yang tidak bisa salah sekaligus benar. Dia selalu hanya memiliki satu dari karakteristik ini. Dalam hal ini, secara konvensional diterima untuk memberikan nilai 1 pada kebenaran, 0 pada kepalsuan, dan menyebut pernyataan itu sendiri sebagai A, B, C tertentu. Dengan kata lain, rumus A = 1 berarti pernyataan A benar. Anda dapat menangani pernyataan secara maksimal dalam berbagai cara. Mari kita pertimbangkan secara singkat tindakan yang dapat dilakukan dengan mereka. Kami juga mencatat bahwa hukum aljabar logika tidak dapat dipelajari tanpa mengetahui aturan-aturan ini.
1. Disjungsi dua pernyataan - hasil dari operasi "atau". Bisa salah atau benar. Simbol "v" digunakan.
2. Konjungsi. Hasil dari tindakan yang dilakukan pada dua pernyataan akan menjadi baru hanya jika kedua pernyataan awal benar. Operator “dan” yang digunakan, simbol “^”.
3. Implikasi. Operasi “jika A maka B”. Hasilnya adalah pernyataan yang salah hanya jika A benar dan B salah.Simbol “->” digunakan.
4. Kesetaraan. Operasi “A jika dan hanya jika B kapan.” Pernyataan ini berlaku jika kedua variabel mempunyai skor yang sama. Simbol yang digunakan adalah “<->».
Ada juga sejumlah operasi yang mendekati implikasinya, tetapi tidak akan dibahas dalam artikel ini.
Sekarang mari kita pertimbangkan secara rinci hukum dasar aljabar logika:
1. Komutatif atau komutatif menyatakan bahwa perubahan tempat suku-suku logika dalam operasi konjungsi atau disjungsi tidak mempengaruhi hasil.
2. Konjungtif atau asosiatif. Menurut hukum ini, variabel-variabel dalam operasi konjungsi atau disjungsi dapat digabungkan menjadi beberapa kelompok.
3. Distributif atau distributif. Inti dari hukum ini adalah bahwa variabel-variabel yang identik dalam persamaan dapat dikeluarkan dari tanda kurung tanpa mengubah logikanya.
4. Hukum De Morgan (inversi atau negasi). Negasi operasi konjungsi sama dengan disjungsi negasi variabel asal. Negasi suatu disjungsi, pada gilirannya, sama dengan konjungsi negasi variabel-variabel yang sama.
5. Negatif ganda. Negasi suatu pernyataan tertentu dua kali menghasilkan pernyataan asli, dan tiga kali - negasinya.
6. Hukum idempotensi terlihat seperti ini untuk penjumlahan logis: x v x v x v x = x; untuk perkalian: x^x^x^=x.
7. Hukum non-kontradiksi mengatakan: dua pernyataan, jika bertentangan, tidak mungkin benar pada saat yang bersamaan.
8. Hukum pengecualian yang ketiga. Di antara dua pernyataan yang bertentangan, yang satu selalu benar, yang lain salah, dan yang ketiga tidak diberikan.
9. Hukum serapan dapat dituliskan sebagai berikut untuk penjumlahan logika: x v (x^y)=x, untuk perkalian: x^ (x v y)=x.
10. Hukum perekatan. Dua konjungsi yang berdekatan dapat bersatu membentuk konjungsi yang tingkatannya lebih rendah. Dalam hal ini, variabel yang digunakan untuk merekatkan konjungsi asli menghilang. Contoh penjumlahan logis:
(x^y) v (-x^y)=y.
Kami hanya membahas hukum aljabar logika yang paling banyak digunakan, yang sebenarnya mungkin masih banyak lagi, karena persamaan logika sering kali berbentuk panjang dan penuh hiasan, yang dapat dipersingkat dengan menerapkan sejumlah hukum serupa.
Biasanya, untuk kemudahan penghitungan dan identifikasi hasil, tabel khusus digunakan. Semua hukum aljabar logika yang ada, tabel yang memiliki struktur umum kotak persegi panjang, dituliskan, mendistribusikan setiap variabel ke dalam sel terpisah. Semakin besar persamaannya, semakin mudah untuk menanganinya menggunakan tabel.
Ada lima hukum aljabar logis:
1. Hukum unsur tunggal
1 * X = X
0 * X = 0
1 + X = 1
0 + X = X
Hukum aljabar logika ini mengikuti langsung ekspresi aksioma aljabar logika di atas.
Dua ekspresi di atas dapat berguna saat membuat saklar, karena dengan menerapkan logika nol atau satu ke salah satu masukan elemen “2I”, Anda dapat meneruskan sinyal ke keluaran atau membentuk potensial nol pada keluaran.
Pilihan kedua untuk menggunakan ekspresi ini adalah kemungkinan untuk secara selektif memusatkan perhatian pada digit-digit tertentu dari bilangan multi-digit. Saat menerapkan operasi “DAN” sedikit demi sedikit, Anda dapat membiarkan nilai bit sebelumnya atau menyetel ulang ke nol dengan menerapkan potensi satuan atau nol ke bit yang sesuai. Misalnya, Anda perlu mereset angka 6, 3 dan 1. Kemudian:
Dalam contoh penggunaan hukum aljabar logika di atas, terlihat jelas bahwa untuk mengatur ulang angka-angka yang diperlukan dalam topeng (angka yang lebih rendah), angka nol ditulis sebagai pengganti angka yang sesuai, dan angka yang tersisa dituliskan satu. Pada bilangan asli (angka atas) terdapat angka 6 dan 1 yang menggantikan angka tersebut. Setelah melakukan operasi "DAN", angka nol muncul di tempat-tempat ini. Di tempat angka ketiga pada bilangan asli ada angka nol. Angka yang dihasilkan juga mengandung angka nol di tempat ini. Digit yang tersisa, seperti yang disyaratkan oleh kondisi soal, tidak diubah.
Dengan cara yang sama, dengan menggunakan hukum unsur tunggal, salah satu hukum dasar aljabar logika, kita dapat menulis satuan dalam angka yang kita perlukan. Dalam hal ini, perlu menggunakan dua ekspresi terbawah dari hukum unsur tunggal. Saat menerapkan operasi “ATAU” sedikit demi sedikit, Anda dapat membiarkan nilai bit sebelumnya atau menyetel ulang ke nol dengan menerapkan potensial nol atau satu ke bit terkait. Misalkan Anda ingin menulis satuan ke dalam bit ke-7 dan ke-6 suatu bilangan. Kemudian:
Di sini, di mask (angka bawah) kami menulis bit ketujuh dan keenam. Bit yang tersisa mengandung angka nol, dan oleh karena itu tidak dapat mengubah keadaan asli dari angka aslinya, seperti yang kita lihat pada angka yang dihasilkan di bawah garis.
Ekspresi pertama dan terakhir dari hukum gerbang tunggal memungkinkan penggunaan sejumlah besar masukan sebagai gerbang logika dengan jumlah masukan yang lebih sedikit. Untuk melakukan ini, input yang tidak terpakai pada rangkaian AND harus dihubungkan ke sumber listrik, seperti yang ditunjukkan pada Gambar 1:
Gambar 1. Sirkuit "2I-NOT", diimplementasikan pada elemen logika "3I-NOT"
Pada saat yang sama, input yang tidak digunakan dalam rangkaian OR, sesuai dengan hukum elemen tunggal, harus dihubungkan ke kabel umum rangkaian, seperti yang ditunjukkan pada Gambar 2.
Gambar 2. Rangkaian “NOT” yang diimplementasikan pada elemen “2I-NOT”.
Hukum aljabar logika selanjutnya yang mengikuti aksioma aljabar logika adalah hukum negasi.
2. Hukum negasi
A. Hukum Unsur Tambahan
Ekspresi hukum aljabar logika ini banyak digunakan untuk meminimalkan rangkaian logika. Jika Anda dapat mengisolasi subekspresi tersebut dari ekspresi umum fungsi logika, maka Anda dapat mengurangi jumlah input elemen rangkaian digital yang diperlukan, dan terkadang bahkan mereduksi seluruh ekspresi menjadi konstanta logika.
Hukum aljabar logika lain yang banyak digunakan adalah hukum negasi ganda.
B. Dua kali tidak
Hukum negasi ganda digunakan untuk menyederhanakan ekspresi logika (dan sebagai konsekuensinya untuk menyederhanakan dan mengurangi biaya rangkaian kombinatorial digital), dan untuk menghilangkan inversi sinyal setelah elemen logika seperti “2AND-NOT” dan “2OR-NOT” . Dalam hal ini, hukum aljabar logika memungkinkan penerapan rangkaian digital tertentu menggunakan sekumpulan elemen logika terbatas.
C. Hukum Logika Negatif
Hukum logika negatif berlaku untuk sejumlah variabel berapa pun. Hukum aljabar logika ini memungkinkan Anda mengimplementasikan “OR” menggunakan elemen logika dan sebaliknya: mengimplementasikan fungsi logika “OR” menggunakan elemen logika “AND”. Hal ini sangat berguna dalam sirkuit TTL, karena gerbang logika “AND” mudah diimplementasikan, namun gerbang logika “OR” cukup sulit untuk diimplementasikan. Berkat hukum logika negatif, elemen “ATAU” dapat diimplementasikan pada elemen logika “DAN”. Gambar 3 menunjukkan implementasi elemen logika "2OR" pada elemen " " dan dua inverter.
Gambar 3. Elemen logika "2OR", diimplementasikan pada elemen "2I-NOT" dan dua inverter
Hal yang sama dapat dikatakan tentang rangkaian pengkabelan "ATAU". Jika perlu, dapat diubah menjadi “DAN” pemasangan dengan menggunakan inverter pada input dan output rangkaian ini.
3. Hukum kombinasi
Hukum kombinasi aljabar logika sebagian besar sesuai dengan hukum kombinasi aljabar biasa, namun terdapat juga perbedaan.
A. hukum tautologi (pengulangan berulang kali)
X + X + X + X = XX * X * X * X = X
Hukum aljabar logika ini memungkinkan gerbang logika dengan masukan lebih banyak digunakan sebagai gerbang logika dengan masukan lebih sedikit. Misalnya, Anda dapat mengimplementasikan rangkaian dua input “2I” pada elemen logika “3I”, seperti yang ditunjukkan pada Gambar 4:
Gambar 4. Rangkaian “2I-NOT” diimplementasikan pada elemen logika “3I-NOT”.
atau gunakan rangkaian “2AND-NOT” sebagai inverter biasa, seperti terlihat pada Gambar 5:
Gambar 5. Rangkaian "NOT" diimplementasikan pada elemen logika "2I-NOT"
Namun, perlu diingat bahwa menggabungkan beberapa masukan akan meningkatkan arus masukan elemen logika dan kapasitansinya, yang meningkatkan konsumsi arus elemen sebelumnya dan berdampak negatif pada kecepatan rangkaian digital secara keseluruhan.
Untuk mengurangi jumlah input dalam elemen logika, lebih baik menggunakan hukum aljabar logika lain - hukum elemen tunggal, seperti yang ditunjukkan di atas.
Mari kita lanjutkan pembahasan kita tentang hukum aljabar logika:
B. hukum mobilitas
A + B + C + D = A + C + B + DC. hukum kombinasi
A + B + C + D = A + (B + C) + D = A + B + (C + D)D. hukum distribusi
X1(X2 + X3) = X1X2 + X1X3 X1 + X2X3 = (X1 + X2)(X1 + X3) = /kita buktikan dengan membuka tanda kurung/ == X1X1 + X1X3 + X1X2 + X2X3 = X1(1 + X3 + X2) + X2X3 = X1 + X2X3
4. Aturan penyerapan (satu variabel menyerap variabel lainnya)
X1 + X1X2X3 =X1(1 + X2X3) = X15. Aturan pengeleman (hanya menjalankan satu variabel)
Sama seperti dalam matematika biasa, dalam aljabar logika terdapat operasi yang diutamakan. Dalam hal ini, hal pertama yang harus dilakukan adalah:
- Tindakan dalam tanda kurung
- Operasi dengan satu operan (operasi satu tempat) - "TIDAK"
- Konjungsi - "Dan"
- Disjungsi - "ATAU"
- Modulo dua jumlah.
Operasi dengan pangkat yang sama dilakukan dari kiri ke kanan sesuai urutan penulisan ekspresi logika. Aljabar logika adalah linier dan prinsip superposisi berlaku untuk itu.
Literatur:
Baca bersama artikel “Hukum Aljabar Logika”:
Setiap rangkaian logika tanpa memori sepenuhnya dijelaskan oleh tabel kebenaran... Untuk mengimplementasikan tabel kebenaran, cukup dengan mempertimbangkan baris-baris tersebut saja...
http://situs/digital/SintSxem.php
Decoder (decoder) memungkinkan Anda mengubah beberapa jenis kode biner menjadi kode biner lainnya. Misalnya...
http://situs/digital/DC.php
Tak jarang, pengembang peralatan digital dihadapkan pada masalah sebaliknya. Anda perlu mengonversi kode linier oktal atau desimal ke...
http://situs/digital/Coder.php
Multiplexer adalah perangkat yang memungkinkan Anda menghubungkan beberapa input ke satu output...
http://situs/digital/MS.php
Demultiplexer adalah perangkat... Perbedaan yang signifikan dari multiplexer adalah...
http://situs/digital/DMS.php