Menyelesaikan persamaan logik. Keutamaan operasi logik

Biarkan menjadi fungsi logik bagi n pembolehubah. Persamaan logik kelihatan seperti:

Pemalar C mempunyai nilai 1 atau 0.

Persamaan logik boleh mempunyai dari 0 hingga penyelesaian yang berbeza. Jika C adalah sama dengan 1, maka penyelesaiannya ialah semua set pembolehubah dari jadual kebenaran yang mana fungsi F mengambil nilai benar (1). Set yang tinggal adalah penyelesaian persamaan dengan C sama dengan sifar. Anda sentiasa boleh mempertimbangkan hanya persamaan bentuk:

Sesungguhnya, biarkan persamaan diberikan:

Dalam kes ini, kita boleh pergi ke persamaan setara:

Pertimbangkan sistem persamaan logik k:

Penyelesaian kepada sistem ialah satu set pembolehubah di mana semua persamaan sistem dipenuhi. Dari segi fungsi logik, untuk mendapatkan penyelesaian kepada sistem persamaan logik, seseorang harus mencari satu set yang mana fungsi logik Ф adalah benar, yang mewakili gabungan fungsi asal:

Jika bilangan pembolehubah adalah kecil, contohnya, kurang daripada 5, maka tidak sukar untuk membina jadual kebenaran untuk fungsi tersebut, yang membolehkan kita menyatakan berapa banyak penyelesaian yang ada pada sistem dan apakah set yang menyediakan penyelesaian.

Dalam beberapa masalah USE untuk mencari penyelesaian kepada sistem persamaan logik, bilangan pembolehubah mencapai 10. Kemudian membina jadual kebenaran menjadi tugas yang hampir mustahil. Menyelesaikan masalah memerlukan pendekatan yang berbeza. Untuk sistem persamaan arbitrari, tidak ada kaedah umum selain penghitungan yang membolehkan menyelesaikan masalah tersebut.

Dalam masalah yang dicadangkan pada peperiksaan, penyelesaian biasanya berdasarkan mengambil kira spesifik sistem persamaan. Saya ulangi, selain daripada mencuba semua pilihan untuk satu set pembolehubah, tidak ada cara umum untuk menyelesaikan masalah. Penyelesaian mesti dibina berdasarkan spesifikasi sistem. Selalunya berguna untuk menjalankan penyederhanaan awal sistem persamaan menggunakan hukum logik yang diketahui. Satu lagi teknik yang berguna untuk menyelesaikan masalah ini adalah seperti berikut. Kami tidak berminat dengan semua set, tetapi hanya mereka yang fungsinya mempunyai nilai 1. Daripada membina jadual kebenaran yang lengkap, kami akan membina analognya - pokok keputusan binari. Setiap cawangan pokok ini sepadan dengan satu penyelesaian dan menentukan set yang mana fungsi mempunyai nilai 1. Bilangan cawangan dalam pepohon keputusan bertepatan dengan bilangan penyelesaian kepada sistem persamaan.

Saya akan menerangkan apa itu pokok keputusan binari dan bagaimana ia dibina menggunakan contoh beberapa masalah.

Masalah 18

Berapa banyak set nilai berbeza bagi pembolehubah logik x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 terdapat yang memenuhi sistem dua persamaan?

Jawapan: Sistem ini mempunyai 36 penyelesaian yang berbeza.

Penyelesaian: Sistem persamaan merangkumi dua persamaan. Mari kita cari bilangan penyelesaian untuk persamaan pertama, bergantung kepada 5 pembolehubah - . Persamaan pertama pula boleh dianggap sebagai sistem 5 persamaan. Seperti yang telah ditunjukkan, sistem persamaan sebenarnya mewakili gabungan fungsi logik. Pernyataan sebaliknya juga benar - kata hubung keadaan boleh dianggap sebagai sistem persamaan.

Mari kita bina pepohon keputusan untuk implikasi () - sebutan pertama kata sendi, yang boleh dianggap sebagai persamaan pertama. Beginilah rupa gambaran grafik pokok ini

Pokok terdiri daripada dua peringkat mengikut bilangan pembolehubah dalam persamaan. Tahap pertama menerangkan pembolehubah pertama. Dua cabang tahap ini mencerminkan nilai yang mungkin bagi pembolehubah ini - 1 dan 0. Pada tahap kedua, cabang pokok hanya mencerminkan nilai yang mungkin bagi pembolehubah yang mana persamaan dinilai sebagai benar. Oleh kerana persamaan menentukan implikasi, cawangan yang mempunyai nilai 1 memerlukan pada cawangan ini terdapat nilai 1. Cawangan yang mempunyai nilai 0 menjana dua cawangan dengan nilai sama dengan 0 dan 1. Yang dibina pokok menentukan tiga penyelesaian, yang mana implikasinya mengambil nilai 1. Pada setiap cawangan, satu set nilai pembolehubah yang sepadan ditulis, memberikan penyelesaian kepada persamaan.

Set ini ialah: ((1, 1), (0, 1), (0, 0))

Mari kita teruskan membina pepohon keputusan dengan menambah persamaan berikut, implikasi berikut. Kekhususan sistem persamaan kami ialah setiap persamaan baharu sistem menggunakan satu pembolehubah daripada persamaan sebelumnya, menambah satu pembolehubah baharu. Memandangkan pembolehubah sudah mempunyai nilai dalam pokok, maka pada semua cawangan di mana pembolehubah mempunyai nilai 1, pembolehubah juga akan mempunyai nilai 1. Bagi cawangan tersebut, pembinaan pokok diteruskan ke peringkat seterusnya, tetapi tiada cawangan baru muncul. Cawangan tunggal di mana pembolehubah mempunyai nilai 0 akan bercabang kepada dua cawangan di mana pembolehubah akan menerima nilai 0 dan 1. Oleh itu, setiap penambahan persamaan baharu, memandangkan kekhususannya, menambah satu penyelesaian. Persamaan pertama asal:

mempunyai 6 penyelesaian. Begini rupa pokok keputusan lengkap untuk persamaan ini:

Persamaan kedua sistem kami adalah serupa dengan yang pertama:

Satu-satunya perbezaan ialah persamaan menggunakan pembolehubah Y. Persamaan ini juga mempunyai 6 penyelesaian. Oleh kerana setiap penyelesaian pembolehubah boleh digabungkan dengan setiap penyelesaian pembolehubah, jumlah bilangan penyelesaian ialah 36.

Sila ambil perhatian bahawa pokok keputusan yang dibina memberikan bukan sahaja bilangan penyelesaian (mengikut bilangan cawangan), tetapi juga penyelesaian itu sendiri yang ditulis pada setiap cawangan pokok itu.

Masalah 19

Berapa banyak set nilai berbeza bagi pembolehubah logik x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 yang memenuhi semua syarat yang disenaraikan di bawah?

Tugasan ini adalah pengubahsuaian daripada tugasan sebelumnya. Perbezaannya ialah persamaan lain ditambah yang mengaitkan pembolehubah X dan Y.

Ia mengikuti daripada persamaan bahawa apabila mempunyai nilai 1 (satu penyelesaian sedemikian wujud), maka ia mempunyai nilai 1. Oleh itu, terdapat satu set di mana dan mempunyai nilai 1. Apabila sama dengan 0, ia boleh mempunyai sebarang nilai, kedua-dua 0 dan dan 1. Oleh itu, setiap set dengan , sama dengan 0, dan terdapat 5 set tersebut, sepadan dengan kesemua 6 set dengan pembolehubah Y. Oleh itu, jumlah bilangan penyelesaian ialah 31.

Masalah 20

Penyelesaian: Mengingat kesetaraan asas, kami menulis persamaan kami sebagai:

Rantaian kitaran implikasi bermakna pembolehubah adalah sama, jadi persamaan kita adalah bersamaan dengan persamaan:

Persamaan ini mempunyai dua penyelesaian apabila semuanya sama ada 1 atau 0.

Masalah 21

Berapa banyak penyelesaian persamaan itu:

Penyelesaian: Sama seperti dalam masalah 20, kita beralih daripada implikasi kitaran kepada identiti, menulis semula persamaan dalam bentuk:

Mari kita bina pepohon keputusan untuk persamaan ini:

Masalah 22

Berapakah bilangan penyelesaian yang ada pada sistem persamaan berikut?

Pada akhir tahun, ternyata hanya satu daripada tiga andaian yang benar. Bahagian manakah yang memperoleh keuntungan pada akhir tahun?

Penyelesaian. Mari kita tuliskan andaian daripada keadaan masalah dalam bentuk pernyataan logik: “Menerima keuntungan melalui bahagian B bukanlah syarat yang diperlukan untuk mendapatkan

untung mengikut bahagian A ":F 1 (A, B, C) = A → B

“Mendapat keuntungan daripada sekurang-kurangnya satu bahagian B dan C tidak mencukupi untuk bahagian A mendapat keuntungan”: F 2 (A, B, C) = (B + C) → A

“Bahagian A dan B tidak akan mendapat keuntungan pada masa yang sama”: F 3 (A, B, C) = A B

Daripada syarat itu diketahui bahawa hanya satu daripada tiga andaian yang benar. Ini bermakna kita mesti mencari yang mana antara tiga ungkapan logik berikut yang tidak sama palsu:

1) F 1F 2F 3

2) F 1F 2F 3

3) F 1F 2F 3

1) (A→ B) ((B+ C) → A) (A↔ B) = A B(B C+ A) (A B+ A B) = 0

2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C

3) (A→ B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0

Akibatnya, pada akhir tahun, andaian kedua ternyata benar, dan yang pertama dan ketiga adalah palsu.

Oleh itu, bahagian C akan menerima keuntungan, tetapi bahagian A dan B tidak akan menerima keuntungan.

Menyelesaikan Persamaan Logik

Dalam teks ujian terpusat negeri terdapat tugas (A8), yang meminta untuk mencari punca persamaan logik. Mari kita lihat cara untuk menyelesaikan tugasan tersebut menggunakan contoh.

Cari punca bagi persamaan logik: (A + B)(X AB) = B + X → A.

Penyelesaian pertama ialah membina jadual kebenaran. Mari bina jadual kebenaran untuk bahagian kanan dan kiri persamaan dan lihat pada X nilai dalam lajur terakhir jadual ini bertepatan.

F1 (A, B, X) = (A+ B)(X AB)

F2 (A, B, X) = B+ X→ A

Mari bandingkan jadual kebenaran yang terhasil dan pilih baris tersebut di mana nilai F 1 (A, B, X) dan F 2 (A, B, X) bertepatan.

Mari kita tulis semula hanya baris yang dipilih, hanya tinggalkan lajur argumen. Mari kita lihat pembolehubah X sebagai fungsi A dan B.

Jelas sekali, X = B → A.

Penyelesaian kedua ialah menggantikan tanda sama dalam persamaan dengan tanda setara, dan kemudian memudahkan persamaan logik yang terhasil.

Untuk memudahkan kerja selanjutnya, mari kita permudahkan bahagian kanan dan kiri persamaan logik dan cari penolakannya:

F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B

F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B

F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A

Mari kita gantikan tanda sama dalam persamaan logik kita dengan tanda kesetaraan:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B+ X A B+ X A+ X B) (X B+ A B) +

+ (X A B+ X A B+ X A B) (B+ X A) =

= (X A B+ X B+ X A B) + (X A B+ X A B) =

Mari kita susun semula istilah logik ungkapan ini, mengambil faktor X dan X daripada kurungan.

X(A B) + X(B+ AB) = X(A B) + X(B+ A) =

Mari kita nyatakan T = A B , kemudian

X T+ X T= X↔ T.

Oleh itu, untuk persamaan logik mempunyai penyelesaian: X = A B = B + A = B → A.

Elemen logik komputer. Pembinaan gambar rajah berfungsi

Dengan perkembangan teknologi komputer, logik matematik ternyata berkait rapat dengan isu reka bentuk dan pengaturcaraan teknologi komputer. Algebra logik didapati aplikasi luas pada mulanya dalam pembangunan hubungan geganti skim Penyelidikan asas pertama yang menarik perhatian jurutera yang terlibat dalam reka bentuk komputer kepada kemungkinan menganalisis litar elektrik menggunakan algebra Boolean diterbitkan pada Disember 1938 oleh Claude Shannon Amerika, "Analisis Simbolik Litar Tangga." Selepas artikel ini, reka bentuk komputer tidak boleh dilakukan tanpa menggunakan algebra Boolean.

Unsur logik ialah satu litar yang melaksanakan operasi logik pemecahan, konjungsi dan penyongsangan. Mari kita pertimbangkan pelaksanaan elemen logik melalui litar hubungan geganti elektrik, yang biasa kepada anda dari kursus fizik sekolah.

Sambungan bersiri kenalan

Sambungan selari kenalan

Mari kita susun jadual kebergantungan keadaan litar pada semua kemungkinan keadaan kenalan. Mari kita perkenalkan notasi berikut: 1 – sesentuh ditutup, terdapat arus dalam litar; 0 – sesentuh terbuka, tiada arus dalam litar.

Seperti yang anda lihat, litar dengan sambungan bersiri sepadan dengan operasi logik konjungsi, kerana arus dalam litar muncul hanya apabila kenalan A dan B ditutup serentak. Litar dengan sambungan selari sepadan dengan operasi logik perpecahan, kerana tiada arus dalam litar hanya pada masa kedua-dua kenalan dibuka.

Operasi logik penyongsangan dilaksanakan melalui litar hubungan geganti elektromagnet, prinsip yang dipelajari dalam kursus fizik sekolah. Kenalan x terbuka apabila x ditutup dan begitu juga sebaliknya.

Penggunaan elemen hubungan geganti untuk membina litar logik komputer tidak membenarkan dirinya sendiri kerana kebolehpercayaan yang rendah, dimensi yang besar, penggunaan kuasa yang tinggi dan prestasi yang rendah. Kemunculan peranti elektronik (vakum dan semikonduktor) telah mewujudkan kemungkinan membina elemen logik dengan kelajuan 1 juta penukaran sesaat dan lebih tinggi. Unsur logik semikonduktor beroperasi dalam mod suis serupa dengan geganti elektromagnet. Keseluruhan teori yang dibentangkan untuk litar sentuhan dipindahkan ke elemen semikonduktor. Unsur logik pada semikonduktor dicirikan bukan oleh keadaan kenalan, tetapi oleh kehadiran isyarat pada input dan output.

Mari kita pertimbangkan elemen logik yang melaksanakan operasi logik asas:

rajah yang sepadan dengan fungsi:

&F(X, Y, Z)

Menyelesaikan masalah menggunakan konjungsi normal

Dan disjungtif-normal borang

DALAM Buku masalah logik selalunya mengandungi masalah standard di mana anda perlu menulis fungsi yang melaksanakan rajah tangga, permudahkannya dan bina jadual kebenaran untuk fungsi ini. Bagaimana untuk menyelesaikan masalah songsang? Memandangkan jadual kebenaran sewenang-wenangnya, anda perlu membina gambar rajah berfungsi atau geganti. Kami akan menangani isu ini hari ini.

Mana-mana fungsi algebra logik boleh diwakili oleh gabungan tiga operasi: konjungsi, disjungsi dan penyongsangan. Mari kita fikirkan bagaimana ini dilakukan. Untuk melakukan ini, mari kita tulis beberapa definisi.

Minterm ialah fungsi yang dibentuk oleh gabungan beberapa pembolehubah tertentu atau penolakannya. Minterm mengambil nilai 1 untuk satu-satunya set yang mungkin

argumen, dan nilainya ialah 0 untuk semua yang lain. Contoh: x 1 x 2 x 3 x 4 .

Jangka maks ialah fungsi yang dibentuk oleh perpisahan bilangan pembolehubah tertentu atau penolakannya. Maxterm mengambil nilai 0 dalam salah satu set yang mungkin, dan 1 dalam semua yang lain.

Contoh: x 1 + x 2 + x 3.

Berfungsi dalam bentuk normal disjungtif(DNF) ialah jumlah logik bagi minterms.

Contoh: x 1x 2+ x 1x 2+ x 1x 2x 3.

Bentuk normal penghubung(CNF) ialah produk logik percanggahan asas (maks).

Contoh: (x 1+ x 2+ x 3) (x 1+ x 2) .

Bentuk normal disjungtif sempurna dipanggil DNF, dalam setiap minterm yang mana semua pembolehubah atau penolakannya hadir.

Contoh: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

Bentuk normal konjungsi sempurna dipanggil CNF, dalam setiap jangka maksimum yang mana semua pembolehubah atau penolakannya hadir.

Contoh: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)

Menulis fungsi logik daripada jadual

Mana-mana fungsi logik boleh dinyatakan sebagai SDNF atau SCNF. Sebagai contoh, pertimbangkan fungsi f yang dibentangkan dalam jadual.

Fungsi G0, G1, G4, G5, G7 adalah minterms (lihat definisi). Setiap fungsi ini adalah hasil darab tiga pembolehubah atau songsangannya dan mengambil nilai 1 dalam satu situasi sahaja. Ia boleh dilihat bahawa untuk mendapatkan 1 dalam nilai fungsi f, satu minterm diperlukan. Akibatnya, bilangan minterm yang membentuk SDNF bagi fungsi ini adalah sama dengan bilangan unit dalam nilai fungsi: f= G0+G1+G4+G5+G7. Oleh itu, SDNF mempunyai bentuk:

f (x 1, x 2, x 3) = x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3.

Begitu juga, anda boleh membina SKNF. Bilangan faktor adalah sama dengan bilangan sifar dalam nilai fungsi:

f (x 1, x 2, x 3) = (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) .

Oleh itu, sebarang fungsi logik yang diberikan dalam bentuk jadual boleh ditulis sebagai formula.

Algoritma untuk membina SDNF menggunakan jadual kebenaran

Jadual kebenaran bagi beberapa fungsi diberikan. Untuk membina SDNF, anda mesti melakukan urutan langkah berikut:

1. Pilih semua baris jadual di mana fungsi mengambil nilai 1.

2. Untuk setiap baris tersebut, tetapkan gabungan semua hujah atau penyongsangannya (minterm). Dalam kes ini, hujah yang mengambil nilai 0 disertakan dalam minterm dengan penolakan, dan nilai 1 disertakan tanpa penolakan.

3. Akhirnya, kami membentuk percanggahan semua minterm yang diperolehi. Bilangan minterm mesti sepadan dengan bilangan unit fungsi logik.

Algoritma untuk membina SCNF menggunakan jadual kebenaran

Jadual kebenaran bagi beberapa fungsi diberikan. Untuk membina SKNF, anda perlu melakukan urutan langkah berikut:

1. Pilih semua baris jadual di mana fungsi mengambil nilai 0.

2. Untuk setiap baris sedemikian, tetapkan percanggahan semua hujah atau penyongsangannya (jangka maksimum). Dalam kes ini, hujah yang mengambil nilai 1 disertakan dalam jangka maksimum dengan penolakan dan nilai 1 disertakan tanpa penolakan.

3. Akhir sekali, kami membentuk gabungan semua istilah maksimum yang diperolehi. Bilangan maxterms mesti sepadan dengan bilangan sifar fungsi logik.

Jika kami bersetuju daripada dua bentuk (SDNF atau SKNF) untuk memberi keutamaan kepada yang mengandungi lebih sedikit huruf, maka SDNF adalah lebih baik jika terdapat lebih sedikit antara nilai fungsi jadual kebenaran, SKNF - jika terdapat lebih sedikit sifar.

Contoh. Jadual kebenaran fungsi logik bagi tiga pembolehubah diberikan. Bina formula logik yang melaksanakan fungsi ini.

Mari kita pilih baris tersebut dalam jadual kebenaran ini dengan nilai fungsinya ialah 0.

F(A, B, C) = (A+ B+ C) (A+ B+ C)

Mari kita semak fungsi terbitan dengan mencipta jadual kebenaran.

Dengan membandingkan jadual kebenaran awal dan akhir, kita boleh membuat kesimpulan bahawa fungsi logik dibina dengan betul.

Penyelesaian masalah

1. Tiga orang guru memilih masalah untuk Olimpik. Terdapat beberapa tugas untuk dipilih. Bagi setiap tugasan, setiap guru menyatakan pendapatnya: tugasan yang mudah (0) atau sukar (1). Sesuatu tugasan dimasukkan ke dalam tugasan Olimpik sekiranya sekurang-kurangnya dua orang guru menandakannya sebagai sukar, tetapi jika ketiga-tiga guru menganggapnya sukar, maka tugas tersebut tidak termasuk dalam tugasan Olimpik sebagai terlalu sukar. Buat gambarajah logik peranti yang akan mengeluarkan 1 jika tugasan disertakan dalam tugasan Olimpik, dan 0 jika ia tidak disertakan.

Mari bina jadual kebenaran untuk fungsi yang diingini. Kami mempunyai tiga pembolehubah input (tiga guru). Oleh itu, fungsi yang diperlukan akan menjadi fungsi tiga pembolehubah.

Menganalisis keadaan masalah, kami memperoleh jadual kebenaran berikut:

Kami sedang membina SDNF. F(A, B, C) = ABC+ ABC+ ABC

Sekarang kita membina gambar rajah logik fungsi ini.

B&1F(A,B,C)

2. City Olympiad dalam kursus asas sains komputer, 2007.Bina gambar rajah litar elektrik untuk pintu masuk rumah tiga tingkat supaya suis di mana-mana tingkat boleh menghidupkan atau mematikan lampu di seluruh rumah.

Jadi, kita mempunyai tiga suis yang mesti kita gunakan untuk menghidupkan dan mematikan lampu. Setiap suis mempunyai dua keadaan: atas (0) dan bawah (1). Mari kita anggap bahawa jika ketiga-tiga suis berada dalam kedudukan 0, lampu di pintu masuk dimatikan. Kemudian, apabila anda mengalihkan mana-mana daripada tiga suis ke kedudukan 1, lampu di pintu masuk akan menyala. Jelas sekali, apabila anda mengalihkan mana-mana suis lain ke kedudukan 1, lampu di pintu masuk akan padam. Jika suis ketiga ditukar ke kedudukan 1, lampu di pintu masuk akan menyala. Kami membina jadual kebenaran.

Kemudian, F(A, B, C) = ABC+ ABC+ ABC+ ABC.

Catatan. Untuk berjaya menyelesaikan masalah ini, ingat formula logik berikut:

x → y= x+ y x y= x y+ x y

x ↔ y= x y+ x y

Kami diberi fungsi logik bagi tiga pembolehubah F 1 (A, B, C) = C → A + B = C + A B.

Mari kita tukar pembolehubah B dan C secara serentak: F 2 (A, B, C) = F 1 (A, B, C) = C + A B. Mari bina jadual kebenaran untuk dua fungsi ini:

Mari analisa jadual yang terhasil. Daripada lapan baris jadual, hanya dalam dua (ke-2 dan ke-3) fungsi tidak mengubah nilainya. Perhatikan bahawa dalam baris ini, pembolehubah A tidak membalikkan nilainya, tetapi pembolehubah B dan C melakukannya.

Kami membina fungsi SKNF menggunakan baris ini:

F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C= .

A+ (B↔ C) = A+ B C= (B C) → A

Oleh itu, jawapan yang dikehendaki ialah 4.

4. Syarat untuk menukar nilai fungsi logik F (A, B, C) = C + AB sambil menukar hujah A dan B secara serentak adalah sama dengan:

Mari analisa jadual yang terhasil. Daripada lapan baris jadual, hanya dalam dua (ke-1 dan ke-7) fungsi mengubah nilainya. Sila ambil perhatian bahawa dalam baris ini, pembolehubah C tidak mengubah nilainya, tetapi pembolehubah A dan B melakukannya.

Kami membina fungsi SDNF menggunakan baris ini:

F3 (A, B, C) = A B C+ A B C= C(A B+ A B) = C(A↔ B) = C+ (A B)

Oleh itu, jawapan yang diperlukan ialah 2.

Rujukan

1. Shapiro S.I. Menyelesaikan masalah logik dan permainan(kajian logik dan psikologi). – M.: Radio dan Komunikasi, 1984. – 152 hlm.

2. Sholomov L.A. Asas teori peranti logik dan pengkomputeran diskret. – M.: Sains. Ch. ed. fizikal - tikar. lit., 1980. - 400 p.

3. Pukhalsky G.I., Novoseltseva T.Ya. Reka bentuk peranti diskret pada litar bersepadu: Buku Panduan. – M.: Radio dan Komunikasi, 1990.

Kaedah untuk menyelesaikan sistem persamaan logik

Kirgizova E.V., Nemkova A.E.

Institut Pedagogi Lesosibirsk –

cawangan Universiti Persekutuan Siberia, Rusia

Keupayaan untuk berfikir secara konsisten, menaakul secara meyakinkan, membina hipotesis, dan menyangkal kesimpulan negatif tidak datang dengan sendiri; kemahiran ini dibangunkan oleh sains logik. Logik ialah sains yang mengkaji kaedah untuk menetapkan kebenaran atau kepalsuan beberapa pernyataan berdasarkan kebenaran atau kepalsuan pernyataan lain.

Menguasai asas sains ini adalah mustahil tanpa menyelesaikan masalah logik. Menguji perkembangan kemahiran mengaplikasikan pengetahuan dalam situasi baharu dijalankan secara lulus. Khususnya, ini adalah keupayaan untuk menyelesaikan masalah logik. Tugasan B15 dalam Peperiksaan Negeri Bersepadu adalah tugas yang lebih kompleks, kerana ia mengandungi sistem persamaan logik. Terdapat pelbagai cara untuk menyelesaikan sistem persamaan logik. Ini ialah pengurangan kepada satu persamaan, pembinaan jadual kebenaran, penguraian, penyelesaian persamaan berjujukan, dsb.

Tugasan:Selesaikan sistem persamaan logik:

Mari kita pertimbangkan kaedah pengurangan kepada satu persamaan . Kaedah ini melibatkan mengubah persamaan logik supaya bahagian kanannya adalah sama dengan nilai kebenaran (iaitu, 1). Untuk melakukan ini, gunakan operasi penafian logik. Kemudian, jika persamaan mengandungi operasi logik yang kompleks, kami menggantikannya dengan yang asas: "DAN", "ATAU", "TIDAK". Langkah seterusnya adalah untuk menggabungkan persamaan menjadi satu, bersamaan dengan sistem, menggunakan operasi logik "DAN". Selepas ini, anda harus mengubah persamaan yang terhasil berdasarkan undang-undang algebra logik dan mendapatkan penyelesaian khusus kepada sistem.

Penyelesaian 1:Gunakan penyongsangan pada kedua-dua belah persamaan pertama:

Mari kita bayangkan implikasi melalui operasi asas "ATAU" dan "TIDAK":

Oleh kerana bahagian kiri persamaan adalah sama dengan 1, kita boleh menggabungkannya menggunakan operasi "DAN" ke dalam satu persamaan yang bersamaan dengan sistem asal:

Kami membuka kurungan pertama mengikut undang-undang De Morgan dan mengubah hasil yang diperoleh:

Persamaan yang terhasil mempunyai satu penyelesaian: A= 0, B =0 dan C =1.

Kaedah seterusnya ialah membina jadual kebenaran . Memandangkan kuantiti logik hanya mempunyai dua nilai, anda boleh melalui semua pilihan dan mencari di antaranya yang mana sistem persamaan tertentu dipenuhi. Iaitu, kita membina satu jadual kebenaran sepunya untuk semua persamaan sistem dan mencari garis dengan nilai yang diperlukan.

Penyelesaian 2:Mari buat jadual kebenaran untuk sistem:

Baris yang memenuhi syarat tugasan diserlahkan dalam huruf tebal. Jadi A =0, B =0 dan C =1.

Cara penguraian . Ideanya adalah untuk menetapkan nilai salah satu pembolehubah (tetapkan ia sama dengan 0 atau 1) dan dengan itu memudahkan persamaan. Kemudian anda boleh menetapkan nilai pembolehubah kedua, dan seterusnya.

Penyelesaian 3: biarlah A = 0, maka:

Daripada persamaan pertama kita dapat B =0, dan dari yang kedua – C=1. Penyelesaian sistem: A = 0, B = 0 dan C = 1.

Anda juga boleh menggunakan kaedah tersebut penyelesaian persamaan berjujukan , pada setiap langkah menambah satu pembolehubah pada set yang sedang dipertimbangkan. Untuk melakukan ini, adalah perlu untuk mengubah persamaan supaya pembolehubah dimasukkan dalam susunan abjad. Seterusnya, kami membina pepohon keputusan, secara berurutan menambah pembolehubah padanya.

Persamaan pertama sistem bergantung hanya pada A dan B, dan persamaan kedua pada A dan C. Pembolehubah A boleh mengambil 2 nilai 0 dan 1:

Daripada persamaan pertama ia mengikutinya , jadi bila A = 0 dan kita mendapat B = 0, dan untuk A = 1 kita mempunyai B = 1. Jadi, persamaan pertama mempunyai dua penyelesaian berkenaan dengan pembolehubah A dan B.

Mari kita gambarkan persamaan kedua, dari mana kita menentukan nilai C untuk setiap pilihan. Apabila A =1, implikasi tidak boleh palsu, iaitu cabang kedua pokok itu tidak mempunyai penyelesaian. Pada A= 0 kami mendapat satu-satunya penyelesaian C= 1 :

Oleh itu, kami memperoleh penyelesaian kepada sistem: A = 0, B = 0 dan C = 1.

Dalam Peperiksaan Negeri Bersatu dalam sains komputer, selalunya perlu untuk menentukan bilangan penyelesaian kepada sistem persamaan logik, tanpa mencari penyelesaian sendiri; terdapat juga kaedah tertentu untuk ini. Cara utama untuk mencari bilangan penyelesaian kepada sistem persamaan logik ialah menggantikan pembolehubah. Pertama, anda perlu mempermudahkan setiap persamaan sebanyak mungkin berdasarkan hukum algebra logik, dan kemudian menggantikan bahagian kompleks persamaan dengan pembolehubah baharu dan tentukan bilangan penyelesaian kepada sistem baharu. Seterusnya, kembali ke penggantian dan tentukan bilangan penyelesaian untuknya.

Tugasan:Berapa banyak penyelesaian yang terdapat pada persamaan ( A → B ) + (C → D ) = 1? Di mana A, B, C, D adalah pembolehubah logik.

Penyelesaian:Mari perkenalkan pembolehubah baharu: X = A → B dan Y = C → D . Dengan mengambil kira pembolehubah baru, persamaan akan ditulis sebagai: X + Y = 1.

Disjunksi adalah benar dalam tiga kes: (0;1), (1;0) dan (1;1), manakala X dan Y adalah implikasi, iaitu benar dalam tiga kes dan palsu dalam satu. Oleh itu, kes (0;1) akan sepadan dengan tiga kemungkinan kombinasi parameter. Kes (1;1) – akan sepadan dengan sembilan kemungkinan kombinasi parameter persamaan asal. Ini bermakna jumlah penyelesaian yang mungkin untuk persamaan ini ialah 3+9=15.

Cara seterusnya untuk menentukan bilangan penyelesaian kepada sistem persamaan logik ialah pokok binari. Mari kita lihat kaedah ini menggunakan contoh.

Tugasan:Berapa banyak penyelesaian berbeza yang ada pada sistem persamaan logik:

Sistem persamaan yang diberikan adalah bersamaan dengan persamaan:

( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.

Mari kita berpura-pura itux 1 – adalah benar, maka dari persamaan pertama kita memperolehnyax 2 juga benar, dari yang kedua -x 3 =1, dan seterusnya sehingga x m= 1. Jadi set (1; 1; …; 1) daripada m unit ialah penyelesaian sistem. Biarkan sekarangx 1 =0, maka dari persamaan pertama kita adax 2 =0 atau x 2 =1.

Bila x 2 benar, kita dapati bahawa pembolehubah yang tinggal adalah juga benar, iaitu set (0; 1; ...; 1) ialah penyelesaian kepada sistem. Padax 2 =0 kita dapat itu x 3 =0 atau x 3 =, dan seterusnya. Meneruskan kepada pembolehubah terakhir, kita dapati bahawa penyelesaian kepada persamaan adalah set pembolehubah berikut ( m penyelesaian +1, dalam setiap penyelesaian m nilai pembolehubah):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Pendekatan ini digambarkan dengan baik dengan membina pokok binari. Bilangan penyelesaian yang mungkin ialah bilangan cabang yang berbeza bagi pokok yang dibina. Ia adalah mudah untuk melihat bahawa ia adalah sama m +1.

Dalam kes kesukaran dalam membuat alasan dan membina pokok keputusan, anda boleh mencari penyelesaian menggunakan jadual kebenaran, untuk satu atau dua persamaan.

Mari kita tulis semula sistem persamaan dalam bentuk:

Dan mari buat jadual kebenaran secara berasingan untuk satu persamaan:

Mari kita buat jadual kebenaran untuk dua persamaan:

Seterusnya, anda boleh melihat bahawa satu persamaan adalah benar dalam tiga kes berikut: (0; 0), (0; 1), (1; 1). Sistem dua persamaan adalah benar dalam empat kes (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). Dalam kes ini, segera jelas bahawa terdapat penyelesaian yang hanya terdiri daripada sifar dan banyak lagi m penyelesaian di mana satu unit ditambah pada satu masa, bermula dari kedudukan terakhir sehingga semua tempat yang mungkin diisi. Ia boleh diandaikan bahawa penyelesaian umum akan mempunyai bentuk yang sama, tetapi untuk pendekatan sedemikian menjadi penyelesaian, bukti diperlukan bahawa andaian itu betul.

Untuk meringkaskan semua perkara di atas, saya ingin menarik perhatian anda kepada fakta bahawa tidak semua kaedah yang dibincangkan adalah universal. Apabila menyelesaikan setiap sistem persamaan logik, seseorang harus mengambil kira ciri-cirinya, berdasarkan kaedah penyelesaian harus dipilih.

kesusasteraan:

1. Masalah logik / O.B. Bogomolov – ed ke-2. – M.: BINOM. Makmal Pengetahuan, 2006. – 271 p.: ill.

2. Polyakov K.Yu. Sistem persamaan logik / Akhbar pendidikan dan metodologi untuk guru sains komputer: Informatik No. 14, 2011.

Topik pelajaran: Menyelesaikan Persamaan Logik

perkembangan - mewujudkan keadaan untuk perkembangan minat kognitif pelajar, menggalakkan perkembangan ingatan, perhatian, dan pemikiran logik;

Pendidikan : menggalakkan keupayaan untuk mendengar pendapat orang lain, memupuk kemahuan dan ketabahan untuk mencapai keputusan akhir.

Jenis pelajaran: pelajaran gabungan

peralatan: komputer, projektor multimedia, persembahan 6.

Semasa kelas

Pengulangan dan pengemaskinian pengetahuan asas. Menyemak kerja rumah (10 minit)

Dalam pelajaran sebelum ini, kita telah mengenali undang-undang asas algebra logik dan belajar menggunakan undang-undang ini untuk memudahkan ungkapan logik.

Mari semak kerja rumah kami untuk memudahkan ungkapan logik:

1. Manakah antara perkataan berikut memenuhi syarat logik:

(konsonan huruf pertama→konsonan huruf kedua)٨ (vokal huruf terakhir → vokal huruf terakhir)? Jika terdapat beberapa perkataan sedemikian, nyatakan yang terkecil daripadanya.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Mari kita perkenalkan notasi berikut:

A – huruf pertama konsonan

B – huruf konsonan kedua

S – huruf vokal terakhir

D – huruf vokal kedua dari belakang

Mari buat ungkapan:

Mari buat jadual:

2. Nyatakan ungkapan logik yang setara dengan ungkapan tersebut

Mari kita permudahkan rakaman ungkapan asal dan pilihan yang dicadangkan:

3. Diberi serpihan jadual kebenaran ungkapan F:

Mari kita tentukan nilai ungkapan ini untuk nilai argumen yang ditentukan:

Pengenalan kepada topik pelajaran, pembentangan bahan baru (30 minit)

Kami terus mengkaji asas logik dan topik pelajaran hari ini ialah "Menyelesaikan Persamaan Logik." Selepas mempelajari topik ini, anda akan mempelajari cara asas untuk menyelesaikan persamaan logik, memperoleh kemahiran untuk menyelesaikan persamaan ini dengan menggunakan bahasa algebra logik dan kebolehan untuk menyusun ungkapan logik menggunakan jadual kebenaran.

1. Selesaikan persamaan logik

(¬K M) → (¬L M N) =0

Tulis jawapan anda sebagai rentetan empat aksara: nilai pembolehubah K, L, M dan N (dalam susunan itu). Jadi, sebagai contoh, baris 1101 sepadan dengan fakta bahawa K=1, L=1, M=0, N=1.

Penyelesaian:

Mari kita ubah ekspresi(¬K  M) → (¬L  M  N)

Ungkapan adalah palsu apabila kedua-dua istilah adalah palsu. Sebutan kedua adalah sama dengan 0 jika M =0, N =0, L =1. Dalam sebutan pertama K = 0, sejak M = 0, dan
.

Jawapan: 0100

2. Berapakah bilangan penyelesaian yang terdapat pada persamaan itu (nyatakan hanya nombor dalam jawapan anda)?

Penyelesaian: mengubah ungkapan

(A +B )*(C +D )=1

A +B =1 dan C +D =1

Kaedah 2: merangka jadual kebenaran

Mari kita ubah ungkapan asal, buka kurungan untuk mendapatkan pemecahan kata hubung:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Mari kita tambahkan kata hubung untuk melengkapkan kata hubung (hasil semua hujah), buka kurungan:

Mari kita ambil kira kata hubung yang sama:

Hasilnya, kami memperoleh SDNF yang mengandungi 9 kata hubung. Oleh itu, jadual kebenaran untuk fungsi ini mempunyai nilai 1 dalam 9 baris 2 4 =16 set nilai pembolehubah.

3. Berapakah bilangan penyelesaian yang ada pada persamaan (nyatakan hanya nombor dalam jawapan anda)?

Mari kita ringkaskan ungkapan:

,

3 cara: pembinaan SDNF

Mari kita ambil kira kata hubung yang sama:

Hasilnya, kami memperoleh SDNF yang mengandungi 5 kata hubung. Oleh itu, jadual kebenaran untuk fungsi ini mempunyai nilai 1 pada 5 baris 2 4 =16 set nilai pembolehubah.

Membina ungkapan logik menggunakan jadual kebenaran:

untuk setiap baris jadual kebenaran yang mengandungi 1, kami mengarang produk argumen, dan pembolehubah sama dengan 0 disertakan dalam produk dengan penolakan, dan pembolehubah sama dengan 1 disertakan tanpa penolakan. Ungkapan F yang dikehendaki akan terdiri daripada hasil tambah hasil. Kemudian, jika boleh, ungkapan ini harus dipermudahkan.

Contoh: jadual kebenaran bagi sesuatu ungkapan diberikan. Membina ungkapan logik.

3. Kerja rumah (5 minit)

Selesaikan persamaan:

Berapa banyak penyelesaian yang ada pada persamaan (nyatakan hanya nombor dalam jawapan anda)?

Menggunakan jadual kebenaran yang diberikan, bina ungkapan logik dan

permudahkanlah.

Bagaimana untuk menyelesaikan beberapa masalah dalam bahagian A dan B peperiksaan sains komputer

Pelajaran #3. Logik. Fungsi logik. Menyelesaikan persamaan

Sebilangan besar masalah Peperiksaan Negeri Bersepadu ditumpukan kepada logik proposisi. Untuk menyelesaikan kebanyakannya, sudah cukup untuk mengetahui undang-undang asas logik proposisi, pengetahuan tentang jadual kebenaran fungsi logik satu dan dua pembolehubah. Saya akan memberikan undang-undang asas logik proposisi.

1. Commutativity of disjunction and conjunction:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Undang-undang distributif mengenai pemecahan dan konjungsi:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Penafian penafian:
   ¬(¬a) ≡ a
4. Ketekalan:
   a ^ ¬а ≡ palsu
5. Ketiga eksklusif:
   a ˅ ¬а ≡ benar
6. Undang-undang De Morgan:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Permudah:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ benar ≡ a
   a ˄ palsu ≡ palsu
8. Penyerapan:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Penggantian implikasi
   a → b ≡ ¬a ˅ b
10. Penggantian identiti
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Perwakilan fungsi logik

Mana-mana fungsi logik n pembolehubah - F(x 1, x 2, ... x n) boleh ditentukan oleh jadual kebenaran. Jadual sedemikian mengandungi 2n set pembolehubah, untuk setiap satunya nilai fungsi pada set ini ditentukan. Kaedah ini bagus apabila bilangan pembolehubah agak kecil. Sudah untuk n > 5 representasi menjadi kurang kelihatan.

Cara lain ialah dengan mentakrifkan fungsi dengan beberapa formula menggunakan fungsi yang agak mudah diketahui. Sistem fungsi (f 1, f 2, ... f k) dipanggil lengkap jika mana-mana fungsi logik boleh dinyatakan dengan formula yang mengandungi hanya fungsi f i.

Sistem fungsi (¬, ˄, ˅) telah lengkap. Undang-undang 9 dan 10 adalah contoh yang menunjukkan bagaimana implikasi dan identiti dinyatakan melalui penolakan, konjungsi dan disjungsi.

Malah, sistem dua fungsi - penolakan dan konjungsi atau penolakan dan pemecahan - juga lengkap. Daripada undang-undang De Morgan mengikut idea yang membenarkan seseorang untuk menyatakan kata hubung melalui penolakan dan disjungsi dan, oleh itu, untuk menyatakan disjung melalui penolakan dan konjungsi:

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

Secara paradoks, sistem yang terdiri daripada satu fungsi sahaja sudah lengkap. Terdapat dua fungsi binari - anticonjunction dan antidisjunction, dipanggil anak panah Peirce dan stroke Schaeffer, mewakili sistem berongga.

Fungsi asas bahasa pengaturcaraan biasanya termasuk identiti, penolakan, konjungsi dan disjungsi. Dalam masalah Peperiksaan Negeri Bersepadu, bersama-sama dengan fungsi ini, implikasi sering dijumpai.

Mari kita lihat beberapa masalah mudah yang melibatkan fungsi logik.

Masalah 15:

Serpihan jadual kebenaran diberikan. Manakah antara tiga fungsi yang diberikan sepadan dengan serpihan ini?

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Fungsi nombor 3.

Untuk menyelesaikan masalah, anda perlu mengetahui jadual kebenaran fungsi asas dan mengingati keutamaan operasi. Izinkan saya mengingatkan anda bahawa konjungsi (pendaraban logik) mempunyai keutamaan yang lebih tinggi dan dilaksanakan lebih awal daripada disjungsi (penambahan logik). Semasa pengiraan, mudah untuk diperhatikan bahawa fungsi dengan nombor 1 dan 2 dalam set ketiga mempunyai nilai 1 dan atas sebab ini tidak sepadan dengan serpihan.

Masalah 16:

Antara nombor yang diberikan yang manakah memenuhi syarat:

(digit, bermula daripada digit paling bererti, adalah dalam susunan menurun) → (nombor - genap) ˄ (digit rendah - genap) ˄ (digit tinggi - ganjil)

Jika terdapat beberapa nombor sedemikian, nyatakan yang terbesar.

1. 13579
2. 97531
3. 24678
4. 15386

Syaratnya dipenuhi oleh nombor nombor 4.

Dua nombor pertama tidak memenuhi syarat atas sebab digit terendah adalah ganjil. Kata sendi syarat adalah palsu jika salah satu daripada istilah kata sendi adalah palsu. Untuk nombor ketiga, syarat untuk digit tertinggi tidak dipenuhi. Untuk nombor keempat, syarat yang dikenakan pada digit rendah dan tinggi nombor dipenuhi. Istilah pertama kata hubung juga benar, kerana implikasinya adalah benar jika premisnya salah, seperti yang berlaku di sini.

Masalah 17: Dua saksi memberikan keterangan berikut:

Saksi pertama: Jika A bersalah, maka B lebih bersalah, dan C tidak bersalah.

Saksi kedua: Dua orang bersalah. Dan salah satu daripada yang selebihnya pasti bersalah dan bersalah, tetapi saya tidak boleh mengatakan siapa sebenarnya.

Apakah kesimpulan tentang kesalahan A, B dan C yang boleh dibuat daripada keterangan tersebut?

Jawapan: Daripada keterangan itu menunjukkan bahawa A dan B bersalah, dan C tidak bersalah.

Penyelesaian: Sudah tentu, jawapan boleh diberikan berdasarkan akal fikiran. Tetapi mari kita lihat bagaimana ini boleh dilakukan secara ketat dan formal.

Perkara pertama yang perlu dilakukan ialah merasmikan kenyataan. Mari kita perkenalkan tiga pembolehubah logik - A, B dan C, setiap satunya mempunyai nilai benar (1) jika suspek yang sepadan bersalah. Kemudian keterangan saksi pertama diberikan dengan formula:

A → (B ˄ ¬C)

Keterangan saksi kedua diberikan dengan formula:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Keterangan kedua-dua saksi diandaikan benar dan mewakili gabungan formula yang sepadan.

Mari kita bina jadual kebenaran untuk bacaan ini:

Ringkasan bukti adalah benar hanya dalam satu kes, membawa kepada jawapan yang jelas - A dan B bersalah, dan C tidak bersalah.

Daripada analisis jadual ini juga menunjukkan bahawa keterangan saksi kedua adalah lebih bermaklumat. Daripada kebenaran keterangannya, hanya dua pilihan yang mungkin berlaku - A dan B adalah bersalah, dan C tidak bersalah, atau A dan C bersalah, dan B tidak bersalah. Keterangan saksi pertama kurang bermaklumat - terdapat 5 pilihan berbeza yang sepadan dengan keterangannya. Bersama-sama, keterangan kedua-dua saksi memberi jawapan yang jelas tentang kesalahan suspek.

Persamaan logik dan sistem persamaan

Biarkan F(x 1, x 2, …x n) menjadi fungsi logik bagi n pembolehubah. Persamaan logik kelihatan seperti:

F(x 1, x 2, …x n) = C,

Pemalar C mempunyai nilai 1 atau 0.

Persamaan logik boleh mempunyai dari 0 hingga 2 n penyelesaian yang berbeza. Jika C adalah sama dengan 1, maka penyelesaiannya ialah semua set pembolehubah dari jadual kebenaran yang mana fungsi F mengambil nilai benar (1). Set yang tinggal adalah penyelesaian persamaan dengan C sama dengan sifar. Anda sentiasa boleh mempertimbangkan hanya persamaan bentuk:

F(x 1 , x 2 , …x n) = 1

Sesungguhnya, biarkan persamaan diberikan:

F(x 1, x 2, …x n) = 0

Dalam kes ini, kita boleh pergi ke persamaan setara:

¬F(x 1 , x 2 , …x n) = 1

Pertimbangkan sistem persamaan logik k:

F 1 (x 1, x 2, …x n) = 1

F 2 (x 1, x 2, …x n) = 1

F k (x 1 , x 2 , …x n) = 1

Penyelesaian kepada sistem ialah satu set pembolehubah di mana semua persamaan sistem dipenuhi. Dari segi fungsi logik, untuk mendapatkan penyelesaian kepada sistem persamaan logik, seseorang harus mencari set yang mana fungsi logik Ф adalah benar, yang mewakili gabungan fungsi asal F:

Ф = F 1 ˄ F 2 ˄ … F k

Jika bilangan pembolehubah adalah kecil, contohnya, kurang daripada 5, maka tidak sukar untuk membina jadual kebenaran untuk fungsi Ф, yang membolehkan kita mengatakan berapa banyak penyelesaian yang ada pada sistem dan apakah set yang menyediakan penyelesaian.

Dalam beberapa masalah USE untuk mencari penyelesaian kepada sistem persamaan logik, bilangan pembolehubah mencapai 10. Kemudian membina jadual kebenaran menjadi tugas yang hampir mustahil. Menyelesaikan masalah memerlukan pendekatan yang berbeza. Untuk sistem persamaan arbitrari, tidak ada kaedah umum selain penghitungan yang membolehkan menyelesaikan masalah tersebut.

Dalam masalah yang dicadangkan pada peperiksaan, penyelesaian biasanya berdasarkan mengambil kira spesifik sistem persamaan. Saya ulangi, selain daripada mencuba semua pilihan untuk satu set pembolehubah, tidak ada cara umum untuk menyelesaikan masalah. Penyelesaian mesti dibina berdasarkan spesifikasi sistem. Selalunya berguna untuk menjalankan penyederhanaan awal sistem persamaan menggunakan hukum logik yang diketahui. Satu lagi teknik yang berguna untuk menyelesaikan masalah ini adalah seperti berikut. Kami tidak berminat dengan semua set, tetapi hanya mereka yang fungsi Ф mempunyai nilai 1. Daripada membina jadual kebenaran yang lengkap, kami akan membina analognya - pokok keputusan binari. Setiap cawangan pokok ini sepadan dengan satu penyelesaian dan menentukan set yang mana fungsi Ф mempunyai nilai 1. Bilangan cawangan dalam pepohon keputusan bertepatan dengan bilangan penyelesaian kepada sistem persamaan.

Saya akan menerangkan apa itu pokok keputusan binari dan bagaimana ia dibina menggunakan contoh beberapa masalah.

Masalah 18

Berapa banyak set nilai berbeza bagi pembolehubah logik x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 terdapat yang memenuhi sistem dua persamaan?

Jawapan: Sistem ini mempunyai 36 penyelesaian yang berbeza.

Penyelesaian: Sistem persamaan merangkumi dua persamaan. Mari kita cari bilangan penyelesaian untuk persamaan pertama, bergantung pada 5 pembolehubah - x 1, x 2, ...x 5. Persamaan pertama pula boleh dianggap sebagai sistem 5 persamaan. Seperti yang telah ditunjukkan, sistem persamaan sebenarnya mewakili gabungan fungsi logik. Sebaliknya juga benar: kata hubung keadaan boleh dianggap sebagai sistem persamaan.

Mari kita bina pepohon keputusan untuk implikasi (x1→ x2) - sebutan pertama kata sendi, yang boleh dianggap sebagai persamaan pertama. Beginilah rupa gambaran grafik pokok ini:

Pokok terdiri daripada dua peringkat mengikut bilangan pembolehubah dalam persamaan. Aras pertama menerangkan pembolehubah pertama X 1 . Dua cabang tahap ini mencerminkan nilai yang mungkin bagi pembolehubah ini - 1 dan 0. Pada peringkat kedua, cabang pokok mencerminkan hanya nilai yang mungkin bagi pembolehubah X 2 yang persamaannya adalah benar. Oleh kerana persamaan menentukan implikasi, cawangan yang X 1 mempunyai nilai 1 memerlukan pada cawangan itu X 2 mempunyai nilai 1. Cawangan yang X 1 mempunyai nilai 0 menghasilkan dua cawangan dengan nilai X 2 sama dengan 0 dan 1 Pokok yang dibina mentakrifkan tiga penyelesaian, di mana implikasi X 1 → X 2 mengambil nilai 1. Pada setiap cawangan, satu set nilai pembolehubah yang sepadan ditulis, memberikan penyelesaian kepada persamaan.

Set ini ialah: ((1, 1), (0, 1), (0, 0))

Mari kita teruskan membina pepohon keputusan dengan menambah persamaan berikut, implikasi berikut X 2 → X 3 . Kekhususan sistem persamaan kami ialah setiap persamaan baharu sistem menggunakan satu pembolehubah daripada persamaan sebelumnya, menambah satu pembolehubah baharu. Oleh kerana pembolehubah X 2 sudah mempunyai nilai dalam pokok, maka pada semua cabang yang mana pembolehubah X 2 mempunyai nilai 1, pembolehubah X 3 juga akan mempunyai nilai 1. Untuk cawangan tersebut, pembinaan pokok terus ke peringkat seterusnya, tetapi cawangan baru tidak muncul. Cawangan tunggal di mana pembolehubah X 2 mempunyai nilai 0 akan bercabang kepada dua cawangan di mana pembolehubah X 3 akan menerima nilai 0 dan 1. Oleh itu, setiap penambahan persamaan baru, memandangkan spesifiknya, menambah satu penyelesaian. Persamaan pertama asal:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
mempunyai 6 penyelesaian. Begini rupa pokok keputusan lengkap untuk persamaan ini:

Persamaan kedua sistem kami adalah serupa dengan yang pertama:

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

Satu-satunya perbezaan ialah persamaan menggunakan pembolehubah Y. Persamaan ini juga mempunyai 6 penyelesaian. Oleh kerana setiap penyelesaian bagi pembolehubah X i boleh digabungkan dengan setiap penyelesaian bagi pembolehubah Y j , jumlah bilangan penyelesaian ialah 36.

Sila ambil perhatian bahawa pokok keputusan yang dibina memberikan bukan sahaja bilangan penyelesaian (mengikut bilangan cawangan), tetapi juga penyelesaian itu sendiri yang ditulis pada setiap cawangan pokok itu.

Masalah 19

Berapa banyak set nilai berbeza bagi pembolehubah logik x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 yang memenuhi semua syarat yang disenaraikan di bawah?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1

Tugasan ini adalah pengubahsuaian daripada tugasan sebelumnya. Perbezaannya ialah persamaan lain ditambah yang mengaitkan pembolehubah X dan Y.

Daripada persamaan X 1 → Y 1 ia berikutan bahawa apabila X 1 mempunyai nilai 1 (satu penyelesaian sedemikian wujud), maka Y 1 juga mempunyai nilai 1. Oleh itu, terdapat satu set di mana X 1 dan Y 1 mempunyai nilai 1. Apabila X 1 sama dengan 0, Y 1 boleh mempunyai sebarang nilai, kedua-dua 0 dan 1. Oleh itu, setiap set dengan X 1 sama dengan 0, dan terdapat 5 set tersebut, sepadan dengan semua 6 set dengan pembolehubah Y. Oleh itu, jumlah bilangan penyelesaian ialah 31 .

Masalah 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Penyelesaian: Mengingat kesetaraan asas, kami menulis persamaan kami sebagai:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Rantaian kitaran implikasi bermakna pembolehubah adalah sama, jadi persamaan kita adalah bersamaan dengan persamaan:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Persamaan ini mempunyai dua penyelesaian apabila semua X i sama ada 1 atau 0.

Masalah 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Penyelesaian: Sama seperti dalam masalah 20, kita beralih daripada implikasi kitaran kepada identiti, menulis semula persamaan dalam bentuk:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Mari kita bina pepohon keputusan untuk persamaan ini:

Masalah 22

Berapakah bilangan penyelesaian yang ada pada sistem persamaan berikut?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Jawapan: 64

Penyelesaian: Mari kita beralih daripada 10 pembolehubah kepada 5 pembolehubah dengan memperkenalkan perubahan pembolehubah berikut:

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Kemudian persamaan pertama akan mengambil bentuk:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Persamaan boleh dipermudahkan dengan menulisnya sebagai:

(Y 1 ≡ Y 2) = 0

Beralih kepada bentuk tradisional, kami menulis sistem selepas penyederhanaan dalam bentuk:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Pepohon keputusan untuk sistem ini adalah mudah dan terdiri daripada dua cabang dengan nilai pembolehubah berselang-seli:

Kembali kepada pembolehubah X asal, ambil perhatian bahawa untuk setiap nilai dalam pembolehubah Y terdapat 2 nilai dalam pembolehubah X, jadi setiap penyelesaian dalam pembolehubah Y menjana 2 5 penyelesaian dalam pembolehubah X. Kedua-dua cawangan menjana 2 * 2 5 penyelesaian, jadi jumlah penyelesaian ialah 64.

Seperti yang anda lihat, setiap masalah untuk menyelesaikan sistem persamaan memerlukan pendekatannya sendiri. Teknik biasa ialah melakukan transformasi setara untuk memudahkan persamaan. Teknik biasa ialah membina pepohon keputusan. Pendekatan yang digunakan adalah sebahagiannya mengingatkan membina jadual kebenaran dengan keanehan bahawa tidak semua set kemungkinan nilai pembolehubah dibina, tetapi hanya mereka yang mana fungsi mengambil nilai 1 (benar). Selalunya dalam masalah yang dicadangkan tidak perlu membina pokok keputusan yang lengkap, kerana sudah pada peringkat awal adalah mungkin untuk mewujudkan corak penampilan cawangan baru pada setiap peringkat berikutnya, seperti yang dilakukan, sebagai contoh, dalam masalah 18 .

Secara amnya, masalah yang melibatkan mencari penyelesaian kepada sistem persamaan logik adalah latihan matematik yang baik.

Jika masalah sukar untuk diselesaikan secara manual, maka anda boleh mempercayakan penyelesaian kepada komputer dengan menulis program yang sesuai untuk menyelesaikan persamaan dan sistem persamaan.

Tidak sukar untuk menulis program sedemikian. Program sedemikian akan dengan mudah mengatasi semua tugas yang ditawarkan dalam Peperiksaan Negeri Bersepadu.

Anehnya, tugas mencari penyelesaian kepada sistem persamaan logik adalah sukar untuk komputer, dan ternyata komputer mempunyai hadnya. Komputer boleh dengan mudah mengatasi masalah di mana bilangan pembolehubah adalah 20-30, tetapi ia akan mula berfikir untuk masa yang lama mengenai masalah saiz yang lebih besar. Hakikatnya ialah fungsi 2 n, yang menentukan bilangan set, adalah eksponen yang berkembang pesat apabila n bertambah. Begitu pantas sehingga komputer peribadi biasa tidak dapat mengatasi tugas yang mempunyai 40 pembolehubah dalam sehari.

Program dalam bahasa C# untuk menyelesaikan persamaan logik

Menulis program untuk menyelesaikan persamaan logik berguna untuk banyak sebab, jika hanya kerana anda boleh menggunakannya untuk menyemak ketepatan penyelesaian anda sendiri untuk masalah ujian Peperiksaan Negeri Bersepadu. Sebab lain ialah program sebegitu merupakan contoh terbaik bagi tugas pengaturcaraan yang memenuhi keperluan untuk tugasan kategori C dalam Peperiksaan Negeri Bersepadu.

Idea untuk membina program adalah mudah - ia berdasarkan carian lengkap semua kemungkinan set nilai pembolehubah. Oleh kerana untuk persamaan logik atau sistem persamaan bilangan pembolehubah n diketahui, maka bilangan set juga diketahui - 2 n yang perlu diisih. Menggunakan fungsi asas bahasa C# - penolakan, percanggahan, konjungsi dan identiti, tidak sukar untuk menulis program yang, untuk set pembolehubah tertentu, mengira nilai fungsi logik yang sepadan dengan persamaan logik atau sistem persamaan .

Dalam program sedemikian, anda perlu membina gelung berdasarkan bilangan set, dalam badan gelung, menggunakan nombor set, bentuk set itu sendiri, hitung nilai fungsi pada set ini, dan jika ini nilai ialah 1, maka set memberikan penyelesaian kepada persamaan.

Satu-satunya kesukaran yang timbul semasa melaksanakan program adalah berkaitan dengan tugas menjana set nilai pembolehubah itu sendiri berdasarkan nombor yang ditetapkan. Keindahan masalah ini ialah tugas yang kelihatan sukar ini sebenarnya berpunca daripada masalah mudah yang telah timbul berkali-kali. Sesungguhnya, sudah cukup untuk memahami bahawa set nilai pembolehubah yang sepadan dengan nombor i, yang terdiri daripada sifar dan satu, mewakili perwakilan binari nombor i. Oleh itu, tugas kompleks untuk mendapatkan satu set nilai pembolehubah mengikut nombor set dikurangkan kepada tugas biasa untuk menukar nombor kepada binari.

Inilah yang kelihatan seperti fungsi dalam C# yang menyelesaikan masalah kami:

///

///

/// fungsi logik - kaedah,

/// yang tandatangannya ditentukan oleh perwakilan DF

///

/// bilangan pembolehubah

/// bilangan penyelesaian

static int SolveEquations(DF fun, int n)

set bool = bool baharu[n];

int m = (int)Math.Pow(2, n); //bilangan set

int p = 0, q = 0, k = 0;

//Lengkapkan carian mengikut bilangan set

untuk (int i = 0; i< m; i++)

//Pembentukan set seterusnya - set,

//ditentukan oleh perwakilan binari nombor i

untuk (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Kira nilai fungsi pada set

Untuk memahami program ini, saya berharap penjelasan idea program dan ulasan dalam teksnya mencukupi. Saya hanya akan fokus untuk menerangkan tajuk fungsi yang diberikan. Fungsi SolveEquations mempunyai dua parameter input. Parameter keseronokan menentukan fungsi logik yang sepadan dengan persamaan atau sistem persamaan yang sedang diselesaikan. Parameter n menentukan bilangan pembolehubah yang menyeronokkan. Akibatnya, fungsi SolveEquations mengembalikan bilangan penyelesaian fungsi logik, iaitu bilangan set yang mana fungsi dinilai kepada benar.

Ia adalah perkara biasa bagi murid sekolah apabila beberapa fungsi F(x) mempunyai parameter input x yang merupakan pembolehubah jenis aritmetik, rentetan atau logik. Dalam kes kami, reka bentuk yang lebih berkuasa digunakan. Fungsi SolveEquations merujuk kepada fungsi tertib tinggi - fungsi jenis F(f), yang parameternya bukan sahaja pembolehubah mudah, tetapi juga fungsi.

Kelas fungsi yang boleh dihantar sebagai parameter kepada fungsi SolveEquations ditentukan seperti berikut:

wakilkan bool DF(bool vars);

Kelas ini memiliki semua fungsi yang diluluskan sebagai parameter satu set nilai pembolehubah logik yang ditentukan oleh tatasusunan vars. Hasilnya ialah nilai Boolean yang mewakili nilai fungsi pada set ini.

Akhir sekali, berikut ialah program yang menggunakan fungsi SolveEquations untuk menyelesaikan beberapa sistem persamaan logik. Fungsi SolveEquations adalah sebahagian daripada kelas ProgramCommon di bawah:

kelas ProgramCommon

wakilkan bool DF(bool vars);

lompang statik Utama(args rentetan)

Console.WriteLine("Dan Fungsi - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("Fungsi mempunyai 51 penyelesaian - " +

SolveEquations(Fun51, 5));

Console.WriteLine("Fungsi mempunyai 53 penyelesaian - " +

SolveEquations(Fun53, 10));

static bool FunAnd(bool vars)

kembalikan vars && vars;

static bool Fun51(bool vars)

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

f = f && (!vars || vars);

static bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Begini rupa keputusan penyelesaian untuk program ini:

10 tugasan untuk kerja bebas

1. Antara ketiga-tiga fungsi yang manakah setara:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. Diberi adalah serpihan jadual kebenaran:

Antara tiga fungsi yang manakah sepadan dengan serpihan ini:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Juri terdiri daripada tiga orang. Keputusan dibuat jika pengerusi juri mengundinya, disokong oleh sekurang-kurangnya seorang daripada ahli juri. Jika tidak, tiada keputusan dibuat. Bina fungsi logik yang memformalkan proses membuat keputusan.
5. X menang atas Y jika empat lambungan syiling menghasilkan kepala tiga kali. Tentukan fungsi logik yang menerangkan imbuhan X.
6. Perkataan dalam ayat dinomborkan bermula dari satu. Sesuatu ayat dianggap betul dibina jika peraturan berikut dipenuhi:
   1. Jika perkataan bernombor genap berakhir dengan vokal, maka perkataan seterusnya, jika wujud, mesti dimulakan dengan vokal.
   2. Jika perkataan bernombor ganjil berakhir dengan konsonan, maka perkataan seterusnya, jika wujud, mesti dimulakan dengan konsonan dan berakhir dengan vokal.
      Antara ayat berikut, yang manakah dibina dengan betul:
   3. Ibu membasuh Masha dengan sabun.
   4. Pemimpin sentiasa menjadi model.
   5. Kebenaran itu baik, tetapi kebahagiaan itu lebih baik.
7. Berapa banyak penyelesaian persamaan itu:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Senaraikan semua penyelesaian kepada persamaan:
   (a → b) → c = 0
9. Berapa banyak penyelesaian yang ada pada sistem persamaan berikut:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Berapa banyak penyelesaian persamaan itu:
    ((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Jawapan kepada masalah:

1. Fungsi b dan c adalah setara.
2. Serpihan sepadan dengan fungsi b.
3. Biarkan pembolehubah logik P mengambil nilai 1 apabila pengerusi juri mengundi "untuk" keputusan itu. Pembolehubah M 1 dan M 2 mewakili pendapat ahli juri. Fungsi logik yang menentukan membuat keputusan positif boleh ditulis seperti berikut:
   P ˄ (M 1 ˅ M 2)
4. Biarkan pembolehubah logik P i mengambil nilai 1 apabila syiling ke-i melambung hinggap di atas kepala. Fungsi logik yang menentukan bayaran X boleh ditulis seperti berikut:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Ayat b.
6. Persamaan mempunyai 3 penyelesaian: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)