Algebra Boolean. Algebra logik. Elemen logik matematik

Isi kandungan:

Algebra Boolean. Algebra logik. Elemen logik matematik
Algebra Boolean. Algebra logik. Elemen logik matematik
Anonim

Dalam dunia hari ini, kita semakin menggunakan pelbagai jenis kereta dan gajet. Dan bukan sahaja apabila perlu untuk menggunakan kekuatan yang tidak berperikemanusiaan secara literal: gerakkan beban, angkat ke ketinggian, gali parit yang panjang dan dalam, dll. Kereta hari ini dipasang oleh robot, makanan disediakan oleh multicooker, dan pengiraan aritmetik asas adalah dilakukan oleh kalkulator. Semakin kerap kita mendengar ungkapan "algebra Boolean". Mungkin sudah tiba masanya untuk memahami peranan manusia dalam mencipta robot dan keupayaan mesin untuk menyelesaikan bukan sahaja masalah matematik, tetapi juga masalah logik.

Logik

Diterjemahkan daripada bahasa Yunani, logik ialah sistem pemikiran tersusun yang mewujudkan hubungan antara keadaan yang diberikan dan membolehkan anda membuat kesimpulan berdasarkan premis dan andaian. Agak kerap kami bertanya antara satu sama lain: "Adakah logik?" Jawapan yang diterima mengesahkan andaian kita atau mengkritik aliran pemikiran. Tetapi proses itu tidak berhenti: kami terus membuat alasan.

Kadang-kadang bilangan syarat (pengenalan) adalah sangat besar, dan hubungan antara mereka sangat rumit dan kompleks sehingga otak manusia tidak dapat "mencerna" semuanya sekaligus. Ia mungkin mengambil masa lebih daripada satu bulan (minggu, tahun) untuk memahami apa yang berlaku. Tetapikehidupan moden tidak memberi kita selang masa sedemikian untuk membuat keputusan. Dan kami menggunakan bantuan komputer. Dan di sinilah algebra logik muncul, dengan undang-undang dan sifatnya sendiri. Dengan memuat turun semua data awal, kami membenarkan komputer mengenali semua perhubungan, menghapuskan percanggahan dan mencari penyelesaian yang memuaskan.

Gambar
Gambar

Matematik dan Logik

Gottfried Wilhelm Leibniz yang terkenal merumuskan konsep "logik matematik", yang masalahnya hanya boleh difahami oleh kalangan saintis yang sempit. Arah ini tidak menimbulkan minat tertentu, dan sehingga pertengahan abad ke-19, hanya sedikit orang yang mengetahui tentang logik matematik.

Minat besar dalam komuniti saintifik menyebabkan pertikaian di mana orang Inggeris George Boole mengumumkan hasratnya untuk mencipta cabang matematik yang langsung tidak mempunyai aplikasi praktikal. Seperti yang kita ingat dari sejarah, pengeluaran perindustrian sedang giat membangun pada masa itu, semua jenis mesin tambahan dan peralatan mesin sedang dibangunkan, iaitu semua penemuan saintifik mempunyai fokus praktikal.

Melihat ke hadapan, katakan algebra Boolean ialah bahagian matematik yang paling banyak digunakan dalam dunia moden. Jadi Bull kehilangan hujahnya.

George Buhl

Keperibadian pengarang patut diberi perhatian khusus. Walaupun memandangkan pada masa lalu orang membesar sebelum kita, masih mustahil untuk tidak menyedari bahawa pada usia 16 tahun, J. Buhl mengajar di sekolah kampung, dan pada usia 20 tahun dia membuka sekolahnya sendiri di Lincoln. Ahli matematik itu fasih dalam lima bahasa asing, dan pada masa lapang dia membaca karyaNewton dan Lagrange. Dan semua ini adalah tentang anak seorang pekerja sederhana!

Gambar
Gambar

Pada tahun 1839 Boole mula-mula menyerahkan kertas saintifiknya ke Cambridge Mathematical Journal. Ahli sains itu berumur 24 tahun. Karya Boole begitu menarik minat ahli Royal Society sehingga pada tahun 1844 dia menerima pingat atas sumbangannya kepada pembangunan analisis matematik. Beberapa lagi karya yang diterbitkan, yang menerangkan unsur-unsur logik matematik, membenarkan ahli matematik muda itu mengambil jawatan profesor di Kolej Cork County. Ingat bahawa Buhl sendiri tidak mempunyai pendidikan.

Idea

Pada dasarnya, algebra Boolean adalah sangat mudah. Terdapat pernyataan (ungkapan logik) yang, dari sudut pandangan matematik, boleh ditakrifkan hanya dengan dua perkataan: "benar" atau "salah". Sebagai contoh, pada musim bunga pokok-pokok mekar - benar, pada musim panas ia salji - satu pembohongan. Keindahan matematik ini ialah tidak perlu menggunakan nombor sahaja. Mana-mana pernyataan dengan maksud yang tidak jelas agak sesuai untuk algebra penghakiman.

Oleh itu, algebra logik boleh digunakan secara literal di mana-mana: dalam penjadualan dan menulis arahan, menganalisis maklumat yang bercanggah tentang peristiwa dan menentukan urutan tindakan. Perkara yang paling penting ialah memahami bahawa adalah tidak penting sama sekali bagaimana kita menentukan kebenaran atau kepalsuan kenyataan itu. "Bagaimana" dan "mengapa" ini perlu diketepikan. Hanya pernyataan fakta yang penting: benar-salah.

Sudah tentu, untuk pengaturcaraan, fungsi algebra logik adalah penting, yang ditulis oleh yang sepadantanda dan simbol. Dan mempelajarinya bermakna menguasai bahasa asing yang baharu. Tiada yang mustahil.

Konsep dan definisi asas

Tanpa pergi ke mendalam, mari kita berurusan dengan istilah. Jadi algebra Boolean menganggap:

  • penyataan;
  • operasi logik;
  • fungsi dan undang-undang.

Pernyataan ialah sebarang ungkapan afirmatif yang tidak boleh ditafsirkan secara samar-samar. Ia ditulis sebagai nombor (5 > 3) atau dirumuskan dalam perkataan biasa (gajah ialah mamalia terbesar). Pada masa yang sama, frasa "zirafah tidak mempunyai leher" juga mempunyai hak untuk wujud, hanya algebra Boolean akan mentakrifkannya sebagai "palsu."

Semua pernyataan mestilah jelas, tetapi ia boleh menjadi asas dan gabungan. Yang terakhir menggunakan penghubung logik. Iaitu, dalam algebra pertimbangan, pernyataan majmuk dibentuk dengan menambah pernyataan asas melalui operasi logik.

Gambar
Gambar

Operasi algebra Boolean

Kita sudah ingat bahawa operasi dalam algebra pertimbangan adalah logik. Sama seperti algebra nombor menggunakan aritmetik untuk menambah, menolak atau membandingkan nombor, unsur logik matematik membolehkan anda membuat pernyataan yang kompleks, menafikan atau mengira hasil akhir.

Operasi logik untuk pemformalkan dan kesederhanaan ditulis oleh formula yang biasa kepada kita dalam aritmetik. Sifat algebra Boolean memungkinkan untuk menulis persamaan dan mengira yang tidak diketahui. Operasi logik biasanya ditulis menggunakan jadual kebenaran. Lajurnyatentukan elemen pengiraan dan operasi yang dilakukan ke atasnya, dan garisan menunjukkan hasil pengiraan.

Tindakan logik asas

Operasi yang paling biasa dalam algebra Boolean ialah penolakan (NOT) dan logik DAN dan ATAU. Hampir semua tindakan dalam algebra penghakiman boleh diterangkan dengan cara ini. Mari kaji setiap satu daripada tiga operasi dengan lebih terperinci.

Negasi (tidak) digunakan pada satu elemen sahaja (operand). Oleh itu, operasi penafian dipanggil unary. Untuk menulis konsep "bukan A" gunakan simbol berikut: ¬A, A¯¯ atau !A. Dalam bentuk jadual ia kelihatan seperti ini:

Gambar
Gambar

Fungsi penolakan dicirikan oleh pernyataan berikut: jika A adalah benar, maka B adalah palsu. Contohnya, Bulan beredar mengelilingi Bumi - benar; Bumi beredar mengelilingi bulan - palsu.

Pendaraban dan penambahan logik

Logik DAN dipanggil operasi kata hubung. Apakah maksudnya? Pertama, ia boleh digunakan pada dua operan, iaitu Dan ialah operasi binari. Kedua, hanya dalam kes kebenaran kedua-dua operan (kedua-dua A dan B) adalah ungkapan itu sendiri benar. Peribahasa "Kesabaran dan kerja akan menggiling segala-galanya" menunjukkan bahawa hanya kedua-dua faktor akan membantu seseorang menghadapi kesukaran.

Simbol yang digunakan untuk menulis: A∧B, A⋅B atau A&&B.

Konjungsi adalah serupa dengan pendaraban dalam aritmetik. Kadang-kadang mereka mengatakan bahawa - pendaraban logik. Jika kita mendarabkan elemen baris jadual dengan baris, kita akan mendapat hasil yang serupa dengan penaakulan logik.

Disjunction ialah operasi ATAU logik. Ia memerlukan nilai kebenaranapabila sekurang-kurangnya satu daripada pernyataan adalah benar (sama ada A atau B). Ia ditulis seperti ini: A∨B, A+B atau A||B. Jadual kebenaran untuk operasi ini ialah:

Gambar
Gambar

Pencacahan adalah seperti penambahan aritmetik. Operasi tambah logik hanya mempunyai satu had: 1+1=1. Tetapi kita ingat bahawa dalam format digital, logik matematik dihadkan kepada 0 dan 1 (di mana 1 adalah benar, 0 adalah palsu). Sebagai contoh, pernyataan "di muzium anda boleh melihat karya agung atau bertemu dengan teman bicara yang menarik" bermakna anda boleh melihat karya seni, atau anda boleh bertemu dengan orang yang menarik. Pada masa yang sama, kemungkinan kedua-dua peristiwa berlaku serentak tidak diketepikan.

Fungsi dan undang-undang

Jadi, kita sudah tahu operasi logik yang digunakan oleh algebra Boolean. Fungsi menerangkan semua sifat unsur-unsur logik matematik dan membolehkan anda memudahkan keadaan kompaun masalah yang kompleks. Sifat yang paling mudah difahami dan mudah nampaknya adalah penolakan operasi terbitan. Derivatif adalah eksklusif ATAU, implikasi dan kesetaraan. Memandangkan kami telah mengkaji hanya operasi asas, kami juga akan mempertimbangkan sifatnya sahaja.

Associativity bermaksud bahawa dalam pernyataan seperti "dan A, dan B, dan C," susunan operan tidak penting. Formula 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 ciri bukan sahaja konjungsi, tetapi juga disjungsi.

Gambar
Gambar

Komutativity menyatakan bahawa hasilnyakata hubung atau percanggahan tidak bergantung pada unsur mana yang dipertimbangkan dahulu:

A∧B=B∧A; A∨B=B∨A.

Pengagihan membenarkan mengembangkan kurungan dalam ungkapan logik yang kompleks. Peraturannya serupa dengan membuka kurungan dalam pendaraban dan penambahan dalam algebra:

A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).

Sifat satu dan sifar, yang boleh menjadi salah satu operan, juga serupa dengan pendaraban algebra dengan sifar atau satu dan penambahan dengan satu:

A∧0=0, A∧1=A; A∨0=A, A∨1=1.

Idempotency memberitahu kita bahawa jika, berkenaan dengan dua operan yang sama, hasil operasi ternyata serupa, maka kita boleh "membuang" operan tambahan yang merumitkan perjalanan penaakulan. Kedua-dua konjungsi dan disjungsi ialah operasi idempoten.

B∧B=B; B∨B=B.

Penyerapan juga membolehkan kita memudahkan persamaan. Penyerapan menyatakan bahawa apabila operasi lain dengan elemen yang sama digunakan pada ungkapan dengan satu operan, hasilnya ialah operan daripada operasi penyerapan.

A∧B∨B=B; (A∨B)∧B=B.

Jujukan operasi

Jujukan operasi adalah tidak penting. Sebenarnya, bagi algebra, terdapat keutamaan fungsi yang digunakan oleh algebra Boolean. Formula boleh dipermudahkan hanya jika kepentingan operasi diperhatikan. Kedudukan daripada yang paling penting kepada yang paling kecil, kami mendapat urutan berikut:

1. Penafian.

2. Kata hubung.

3. Disjunction, eksklusifATAU.

4. Implikasi, kesetaraan.

Seperti yang anda lihat, hanya penafian dan kata hubung tidak mempunyai keutamaan yang sama. Dan keutamaan disjungsi dan XOR adalah sama, serta keutamaan implikasi dan kesetaraan.

Fungsi implikasi dan kesetaraan

Seperti yang telah kami katakan, sebagai tambahan kepada operasi logik asas, logik matematik dan teori algoritma menggunakan derivatif. Yang paling biasa digunakan ialah implikasi dan kesetaraan.

Implikasi, atau akibat logik, ialah pernyataan di mana satu tindakan adalah syarat, dan satu lagi adalah akibat pelaksanaannya. Dalam erti kata lain, ini adalah ayat dengan kata depan "jika … maka." "Jika anda suka menunggang, suka membawa kereta luncur." Iaitu, untuk bermain ski, anda perlu mengetatkan kereta luncur ke atas bukit. Jika tidak ada keinginan untuk turun gunung, maka anda tidak perlu membawa kereta luncur. Ia ditulis seperti ini: A→B atau A⇒B.

Kesamaan mengandaikan bahawa tindakan yang terhasil berlaku hanya apabila kedua-dua operan adalah benar. Contohnya, malam bertukar menjadi siang apabila (dan hanya apabila) matahari terbit di ufuk. Dalam bahasa logik matematik, pernyataan ini ditulis seperti berikut: A≡B, A⇔B, A==B.

Undang-undang lain bagi algebra Boolean

Algebra pertimbangan sedang berkembang, dan ramai saintis yang berminat telah merumuskan undang-undang baharu. Postulat ahli matematik Scotland O. de Morgan dianggap paling terkenal. Dia melihat dan mentakrifkan sifat tersebut sebagai penafian rapat, pelengkap dan penolakan berganda.

Penolakan rapat bermakna tiada penafian sebelum kurungan:bukan (A atau B)=bukan A atau BUKAN B.

Apabila operan dinafikan, tanpa mengira nilainya, seseorang bercakap tentang pelengkap:

B∧¬B=0; B∨¬B=1.

Dan akhirnya, penafian berganda mengimbangi dirinya sendiri. Itu. sama ada penolakan hilang sebelum operan, atau hanya tinggal satu sahaja.

Cara menyelesaikan ujian

Logik matematik membayangkan pemudahan persamaan yang diberikan. Sama seperti dalam algebra, anda mesti membuat syarat semudah mungkin (buang input dan operasi yang kompleks dengannya), dan kemudian mula mencari jawapan yang betul.

Apakah yang boleh dilakukan untuk memudahkan? Tukar semua operasi terbitan kepada yang mudah. Kemudian buka semua kurungan (atau sebaliknya, keluarkannya dari kurungan untuk memendekkan elemen ini). Langkah seterusnya hendaklah menggunakan sifat algebra Boolean dalam amalan (penyerapan, sifat sifar dan satu, dsb.).

Gambar
Gambar

Akhirnya, persamaan harus terdiri daripada bilangan minimum yang tidak diketahui digabungkan dengan operasi mudah. Cara paling mudah untuk mencari penyelesaian adalah dengan mencapai sejumlah besar negatif rapat. Kemudian jawapan akan muncul dengan sendirinya.

Disyorkan: