Di dunia sekarang ini, kita semakin banyak menggunakan berbagai macam mobil dan gadget. Dan tidak hanya ketika perlu untuk menerapkan kekuatan yang benar-benar tidak manusiawi: memindahkan beban, mengangkatnya ke ketinggian, menggali parit yang panjang dan dalam, dll. Mobil saat ini dirakit oleh robot, makanan disiapkan oleh multicooker, dan perhitungan aritmatika dasar dilakukan dilakukan oleh kalkulator. Semakin sering kita mendengar ungkapan “Aljabar Boolean”. Mungkin sudah waktunya untuk memahami peran manusia dalam menciptakan robot dan kemampuan mesin untuk memecahkan tidak hanya masalah matematika, tetapi juga logika.
Logika
Diterjemahkan dari bahasa Yunani, logika adalah sistem pemikiran yang teratur yang menciptakan hubungan antara kondisi yang diberikan dan memungkinkan Anda untuk menarik kesimpulan berdasarkan premis dan asumsi. Cukup sering kita bertanya satu sama lain: "Apakah logis?" Jawaban yang diterima menegaskan asumsi kita atau mengkritik alur pemikiran. Tapi prosesnya tidak berhenti: kami terus bernalar.
Terkadang jumlah kondisi (pengantar) begitu banyak, dan hubungan di antara mereka begitu rumit dan kompleks sehingga otak manusia tidak dapat "mencerna" semuanya sekaligus. Mungkin diperlukan lebih dari satu bulan (minggu, tahun) untuk memahami apa yang terjadi. Tetapikehidupan modern tidak memberi kita interval waktu seperti itu untuk membuat keputusan. Dan kami menggunakan bantuan komputer. Dan di sinilah aljabar logika muncul, dengan hukum dan propertinya sendiri. Dengan mengunduh semua data awal, kami mengizinkan komputer untuk mengenali semua hubungan, menghilangkan kontradiksi dan menemukan solusi yang memuaskan.
Matematika dan Logika
Gottfried Wilhelm Leibniz yang terkenal merumuskan konsep "logika matematis", yang masalah-masalahnya hanya dapat dipahami oleh kalangan ilmuwan yang sempit. Arah ini tidak membangkitkan minat khusus, dan sampai pertengahan abad ke-19, hanya sedikit orang yang tahu tentang logika matematika.
Ketertarikan yang besar pada komunitas ilmiah menyebabkan perselisihan di mana orang Inggris George Boole mengumumkan niatnya untuk membuat cabang matematika yang sama sekali tidak memiliki aplikasi praktis. Seperti yang kita ingat dari sejarah, produksi industri berkembang secara aktif pada waktu itu, semua jenis mesin bantu dan peralatan mesin sedang dikembangkan, yaitu, semua penemuan ilmiah memiliki fokus praktis.
Ke depan, misalkan aljabar Boolean adalah bagian matematika yang paling banyak digunakan di dunia modern. Jadi Bull kehilangan argumennya.
George Buhl
Kepribadian penulis patut mendapat perhatian khusus. Bahkan mengingat bahwa di masa lalu orang-orang tumbuh sebelum kita, masih tidak mungkin untuk tidak mencatat bahwa pada usia 16 tahun, J. Buhl mengajar di sekolah desa, dan pada usia 20 tahun ia membuka sekolahnya sendiri di Lincoln. Matematikawan itu fasih dalam lima bahasa asing, dan di waktu luangnya dia membaca karyaNewton dan Lagrange. Dan semua ini tentang putra seorang pekerja sederhana!
Pada tahun 1839 Boole pertama kali menyerahkan makalah ilmiahnya ke Cambridge Mathematical Journal. Ilmuwan itu berusia 24 tahun. Boole bekerja sehingga tertarik anggota Royal Society yang pada tahun 1844 dia menerima medali untuk kontribusinya terhadap pengembangan analisis matematis. Beberapa karya yang diterbitkan lebih, yang menggambarkan unsur-unsur logika matematika, memungkinkan matematikawan muda untuk mengambil jabatan profesor di Cork County College. Ingatlah bahwa Buhl sendiri tidak memiliki pendidikan.
Ide
Pada prinsipnya, aljabar Boolean sangat sederhana. Ada pernyataan (ekspresi logis) yang, dari sudut pandang matematika, hanya dapat didefinisikan dengan dua kata: "benar" atau "salah". Misalnya, di musim semi pohon-pohon mekar - benar, di musim panas turun salju - bohong. Keindahan matematika ini adalah tidak perlu ketat hanya menggunakan angka. Pernyataan apa pun dengan makna yang tidak ambigu cukup cocok untuk aljabar penilaian.
Dengan demikian, aljabar logika dapat digunakan secara harfiah di mana-mana: dalam menjadwalkan dan menulis instruksi, menganalisis informasi yang saling bertentangan tentang peristiwa, dan menentukan urutan tindakan. Yang paling penting adalah memahami bahwa sama sekali tidak penting bagaimana kita menentukan benar atau salahnya pernyataan itu. "Bagaimana" dan "mengapa" ini perlu diabstraksikan. Hanya pernyataan fakta yang penting: benar-salah.
Tentu saja, untuk pemrograman, fungsi aljabar logika penting, yang ditulis oleh yang sesuaitanda dan simbol. Dan mempelajarinya berarti menguasai bahasa asing baru. Tidak ada yang tidak mungkin.
Konsep dasar dan definisi
Tanpa masuk lebih dalam, mari kita bahas terminologinya. Jadi aljabar Boolean mengasumsikan:
- pernyataan;
- operasi logika;
- fungsi dan hukum.
Pernyataan adalah ekspresi afirmatif yang tidak dapat ditafsirkan secara ambigu. Mereka ditulis sebagai angka (5 > 3) atau dirumuskan dengan kata-kata yang sudah dikenal (gajah adalah mamalia terbesar). Pada saat yang sama, frasa "jerapah tidak memiliki leher" juga memiliki hak untuk eksis, hanya aljabar Boolean yang akan mendefinisikannya sebagai "salah."
Semua pernyataan harus jelas, tetapi bisa elementer dan majemuk. Yang terakhir menggunakan penghubung logis. Artinya, dalam aljabar penilaian, pernyataan majemuk dibentuk dengan menambahkan pernyataan elementer melalui operasi logika.
Operasi aljabar Boolean
Kita sudah ingat bahwa operasi dalam aljabar penilaian adalah logis. Sama seperti aljabar bilangan yang menggunakan aritmatika untuk menambah, mengurangi, atau membandingkan bilangan, elemen logika matematika memungkinkan Anda membuat pernyataan kompleks, meniadakan, atau menghitung hasil akhirnya.
Operasi logis untuk formalisasi dan penyederhanaan ditulis dengan rumus yang kita kenal dalam aritmatika. Sifat-sifat aljabar Boolean memungkinkan untuk menulis persamaan dan menghitung yang tidak diketahui. Operasi logika biasanya ditulis menggunakan tabel kebenaran. kolomnyatentukan elemen perhitungan dan operasi yang dilakukan pada elemen tersebut, dan garis menunjukkan hasil perhitungan.
Tindakan logis dasar
Operasi yang paling umum dalam aljabar Boolean adalah negasi (NOT) dan logika AND dan OR. Hampir semua tindakan dalam aljabar penilaian dapat dijelaskan dengan cara ini. Mari kita pelajari masing-masing dari tiga operasi secara lebih rinci.
Negasi (tidak) hanya berlaku untuk satu elemen (operan). Oleh karena itu, operasi negasi disebut unary. Untuk menuliskan konsep "bukan A" gunakan simbol berikut: A, A¯¯¯ atau !A. Dalam bentuk tabel terlihat seperti ini:
Fungsi negasi dicirikan oleh pernyataan berikut: jika A benar, maka B salah. Misalnya, Bulan berputar mengelilingi Bumi - benar; Bumi berputar mengelilingi bulan - salah.
Perkalian dan penjumlahan logis
Logis AND disebut operasi konjungsi. Apa artinya? Pertama, dapat diterapkan pada dua operan, yaitu And merupakan operasi biner. Kedua, bahwa hanya dalam kasus kebenaran kedua operan (baik A dan B) ekspresi itu sendiri benar. Pepatah "Kesabaran dan kerja keras akan menggiling segalanya" menunjukkan bahwa hanya kedua faktor tersebut yang akan membantu seseorang mengatasi kesulitan.
Simbol yang digunakan untuk menulis: A∧B, A⋅B atau A&&B.
Konjungsi mirip dengan perkalian dalam aritmatika. Terkadang mereka mengatakan itu - perkalian logis. Jika kita mengalikan elemen dari baris demi baris tabel, kita mendapatkan hasil yang mirip dengan penalaran logis.
Disjunction adalah operasi logika OR. Dibutuhkan nilai kebenaranketika setidaknya satu dari pernyataan benar (baik A atau B). Ditulis seperti ini: A∨B, A+B atau A||B. Tabel kebenaran untuk operasi ini adalah:
Disjunction seperti penjumlahan aritmatika. Operasi penjumlahan logis hanya memiliki satu batasan: 1+1=1. Tapi kita ingat bahwa dalam format digital, logika matematika terbatas pada 0 dan 1 (di mana 1 benar, 0 salah). Misalnya, pernyataan “di museum Anda dapat melihat karya agung atau bertemu lawan bicara yang menarik” berarti Anda dapat melihat karya seni, atau Anda dapat bertemu orang yang menarik. Pada saat yang sama, kemungkinan kedua peristiwa tersebut terjadi secara bersamaan tidak dikesampingkan.
Fungsi dan hukum
Jadi, kita sudah mengetahui operasi logika yang digunakan aljabar Boolean. Fungsi menggambarkan semua sifat elemen logika matematika dan memungkinkan Anda untuk menyederhanakan kondisi kompleks masalah. Properti yang paling mudah dipahami dan sederhana tampaknya adalah penolakan terhadap operasi turunan. Derivatif adalah OR eksklusif, implikasi dan ekivalensi. Karena kita hanya mempelajari operasi dasar, kita juga akan mempertimbangkan sifat-sifatnya saja.
Associativity berarti bahwa dalam pernyataan seperti "dan A, dan B, dan C", urutan operan tidak menjadi masalah. Rumusnya ditulis seperti ini:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
Seperti yang Anda lihat, ini adalah karakteristik tidak hanya dari konjungsi, tetapi juga disjungsi.
Komutatif menyatakan bahwa hasilkonjungsi atau disjungsi tidak bergantung pada elemen mana yang dianggap lebih dulu:
A∧B=B∧A; A∨B=B∨A.
Distributivitas memungkinkan perluasan tanda kurung dalam ekspresi logika yang kompleks. Aturannya mirip dengan tanda kurung buka pada perkalian dan penjumlahan dalam aljabar:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
Sifat satu dan nol, yang dapat menjadi salah satu operan, juga mirip dengan perkalian aljabar dengan nol atau satu dan penjumlahan dengan satu:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotency memberi tahu kita bahwa jika, sehubungan dengan dua operan yang sama, hasil dari suatu operasi ternyata serupa, maka kita dapat "membuang" operan tambahan yang memperumit jalannya penalaran. Baik konjungsi maupun disjungsi adalah operasi idempoten.
B∧B=B; B∨B=B.
Absorpsi juga memungkinkan kita untuk menyederhanakan persamaan. Penyerapan menyatakan bahwa ketika operasi lain dengan elemen yang sama diterapkan ke ekspresi dengan satu operan, hasilnya adalah operan dari operasi penyerap.
A∧B∨B=B; (A∨B)∧B=B.
Urutan operasi
Urutan operasi tidak terlalu penting. Sebenarnya, untuk aljabar, ada prioritas fungsi yang digunakan aljabar Boolean. Rumus dapat disederhanakan hanya jika signifikansi operasi diamati. Urutan dari yang paling signifikan hingga yang paling kecil, kita mendapatkan urutan berikut:
1. Penolakan.
2. Konjungsi.
3. Disjungsi, eksklusifATAU.
4. Implikasi, kesetaraan.
Seperti yang Anda lihat, hanya negasi dan konjungsi yang tidak memiliki prioritas yang sama. Dan prioritas disjungsi dan XOR adalah sama, serta prioritas implikasi dan ekivalensi.
Fungsi implikasi dan ekivalensi
Seperti yang telah kami katakan, selain operasi logika dasar, logika matematika dan teori algoritma menggunakan turunan. Yang paling umum digunakan adalah implikasi dan ekivalensi.
Implikasi, atau konsekuensi logis, adalah pernyataan di mana satu tindakan adalah kondisi, dan yang lainnya adalah konsekuensi dari implementasinya. Dengan kata lain, ini adalah kalimat dengan preposisi "jika … maka." "Jika Anda suka naik, suka membawa kereta luncur." Artinya, untuk bermain ski, Anda perlu mengencangkan kereta luncur ke atas bukit. Jika tidak ada keinginan untuk turun gunung, maka Anda tidak perlu membawa kereta luncur. Ditulis seperti ini: A→B atau A⇒B.
Equivalence mengasumsikan bahwa aksi yang dihasilkan hanya terjadi jika kedua operan bernilai benar. Misalnya, malam berubah menjadi siang ketika (dan hanya ketika) matahari terbit di cakrawala. Dalam bahasa logika matematika, pernyataan ini ditulis sebagai berikut: A≡B, A⇔B, A==B.
Hukum lain dari aljabar Boolean
Aljabar penilaian sedang berkembang, dan banyak ilmuwan yang tertarik telah merumuskan hukum baru. Postulat matematikawan Skotlandia O. de Morgan dianggap yang paling terkenal. Dia memperhatikan dan mendefinisikan sifat-sifat seperti negasi dekat, komplemen, dan negasi ganda.
Negasi dekat berarti tidak ada negasi sebelum tanda kurung:bukan (A atau B)=bukan A atau BUKAN B.
Ketika sebuah operan dinegasikan, terlepas dari nilainya, seseorang berbicara tentang komplemen:
B∧¬B=0; B∨¬B=1.
Dan akhirnya, negasi ganda mengkompensasi dirinya sendiri. Itu. baik negasi menghilang sebelum operan, atau hanya satu yang tersisa.
Cara menyelesaikan tes
Logika matematika menyiratkan penyederhanaan persamaan yang diberikan. Sama seperti dalam aljabar, pertama-tama Anda harus membuat kondisinya semudah mungkin (singkirkan input dan operasi yang rumit dengannya), dan kemudian mulai mencari jawaban yang benar.
Apa yang bisa dilakukan untuk menyederhanakan? Ubah semua operasi turunan menjadi operasi sederhana. Kemudian buka semua kurung (atau sebaliknya, keluarkan dari kurung untuk mempersingkat elemen ini). Langkah selanjutnya adalah menerapkan sifat-sifat aljabar Boolean dalam praktik (penyerapan, sifat nol dan satu, dll.).
Pada akhirnya, persamaan harus terdiri dari jumlah minimum yang tidak diketahui yang digabungkan dengan operasi sederhana. Cara termudah untuk menemukan solusi adalah untuk mencapai sejumlah besar negatif dekat. Maka jawabannya akan muncul dengan sendirinya.