Metode penyelesaian sistem persamaan logika. Metode penyelesaian sistem persamaan logika

Noskin Andrey Nikolaevich,
guru ilmu komputer
kategori kualifikasi tertinggi,
Kandidat Ilmu Militer, Associate Professor
GBOU Lyceum No. 1575, Moskow

Metode pemetaan yang dioptimalkan untuk menyelesaikan masalah 23 dari KIM Unified State Examination dalam ilmu komputer dan ICT

Salah satu tugas tersulit dalam Ujian Negara Bersatu KIM adalah soal 23, di mana Anda perlu mencari jumlah himpunan nilai variabel logika berbeda yang memenuhi kondisi yang ditentukan.
Tugas ini mungkin merupakan tugas tersulit dari KIM Unified State Examination di bidang ilmu komputer dan TIK. Biasanya, tidak lebih dari 5% peserta ujian yang mengatasinya (1).
Kecilnya persentase siswa yang menyelesaikan tugas ini dijelaskan sebagai berikut:
- siswa mungkin bingung (lupa) tanda-tanda operasi logika;
- kesalahan matematika dalam proses melakukan perhitungan;
- kesalahan dalam penalaran saat mencari solusi;
- kesalahan dalam proses menyederhanakan ekspresi logika;
- guru merekomendasikan untuk menyelesaikan masalah ini setelah menyelesaikan semua pekerjaan, karena kemungkinannya besar
kesalahannya sangat besar, dan “bobot” tugas hanya satu poin utama.
Selain itu, beberapa guru sendiri mengalami kesulitan dalam memecahkan masalah jenis ini dan oleh karena itu mencoba memecahkan masalah yang lebih sederhana dengan anak-anak.
Yang juga memperumit situasi adalah bahwa di blok ini terdapat banyak tugas berbeda dan tidak mungkin untuk memilih solusi templat apa pun.
Untuk memperbaiki situasi ini, komunitas pedagogis sedang menyelesaikan dua metode utama untuk memecahkan masalah jenis ini: penyelesaian menggunakan rantai bit (2) dan metode pemetaan (3).
Perlunya penyempurnaan (pengoptimalan) metode-metode ini disebabkan oleh kenyataan bahwa tugas terus berubah baik dalam struktur maupun jumlah variabel (hanya satu jenis variabel X, dua jenis variabel X dan Y, tiga jenis: X, Y , Z).
Sulitnya menguasai metode pemecahan masalah ini ditegaskan oleh fakta bahwa di situs web K.Yu. Polyakov ada 38 analisis untuk masalah jenis ini (4). Beberapa analisis memberikan lebih dari satu jenis solusi terhadap suatu masalah.
Baru-baru ini, pada KIM Unified State Examination bidang ilmu komputer, terdapat permasalahan pada dua jenis variabel X dan Y.
Saya telah mengoptimalkan metode tampilan dan mendorong siswa saya untuk menggunakan metode yang ditingkatkan.
Ini memberikan hasil. Persentase siswa saya yang menyelesaikan tugas ini bervariasi hingga 43% dari mereka yang lulus. Biasanya, setiap tahun 25 hingga 33 orang dari seluruh kelas 11 mengikuti Ujian Negara Terpadu dalam ilmu komputer.
Sebelum munculnya soal dengan dua jenis variabel, siswa menggunakan metode pemetaan dengan sangat sukses, tetapi setelah munculnya Y dalam ekspresi logis, saya mulai memperhatikan bahwa jawaban anak-anak tidak lagi sesuai dengan tes. Ternyata mereka kurang paham cara membuat tabel pemetaan dengan variabel tipe baru. Kemudian muncul pemikiran di benak saya bahwa untuk kenyamanan, seluruh ekspresi harus direduksi menjadi satu jenis variabel, sesuai keinginan anak-anak.
Saya akan memberikan teknik ini lebih detail. Untuk kenyamanan, saya akan mempertimbangkannya menggunakan contoh sistem ekspresi logika yang diberikan pada (4).
Berapa banyak solusi berbeda yang dimiliki sistem persamaan logika?

(x 1 ^ kamu 1)=(¬x 2 V ¬ kamu 2 )
(x 2 ^ kamu 2)= (¬ X 3 V ¬ kamu 3 )
...
(x 5 ^ kamu 5) = (¬ X 6 V ¬ kamu 6 )

(z 1 ^ z 2)= (¬z 3V¬ z 4 )
(z 3 ^ z 4)= (¬ z 5 V¬ z 6 )
...
(z 9 ^ z 10) = (¬ z 11 V¬ z 12)

5. Isilah tabel dengan menghitung jumlah pasangan variabel yang solusinya dimiliki sistem.

6. Jumlahkan semua hasilnya: 9+9+9+27=54
7. Jawaban: 54.
Metode yang dioptimalkan di atas untuk memecahkan masalah 23 dari Ujian Negara Bersatu KIM memungkinkan siswa untuk mendapatkan kembali kepercayaan diri dan berhasil memecahkan masalah jenis ini.

Literatur:

1.FIPI. Rekomendasi metodologis untuk guru, disusun berdasarkan analisis kesalahan umum peserta UN Unified State tahun 2015 bidang ILMU INFORMASI dan TIK. Mode akses: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

Ada berbagai cara untuk menyelesaikan sistem persamaan logika. Ini adalah reduksi menjadi satu persamaan, pembuatan tabel kebenaran, dan dekomposisi.

Tugas: Memecahkan sistem persamaan logis:

Mari kita pertimbangkan metode reduksi menjadi satu persamaan . Metode ini melibatkan transformasi persamaan logika sehingga ruas kanannya sama dengan nilai kebenarannya (yaitu 1). Untuk melakukan ini, gunakan operasi negasi logis. Kemudian, jika persamaan tersebut mengandung operasi logika yang kompleks, kami menggantinya dengan persamaan dasar: “DAN”, “ATAU”, “TIDAK”. Langkah selanjutnya adalah menggabungkan persamaan menjadi satu persamaan ekuivalen sistem menggunakan operasi logika “DAN”. Setelah ini, Anda harus mengubah persamaan yang dihasilkan berdasarkan hukum aljabar logis dan mendapatkan solusi spesifik untuk sistem tersebut.

Solusi 1: Terapkan inversi pada kedua ruas persamaan pertama:

Mari kita bayangkan implikasinya melalui operasi dasar “OR” dan “NOT”:

Karena ruas kiri persamaan sama dengan 1, kita dapat menggabungkannya menggunakan operasi “DAN” menjadi satu persamaan yang ekuivalen dengan sistem asal:

Kita buka tanda kurung pertama menurut hukum De Morgan dan ubah hasilnya:

Persamaan yang dihasilkan memiliki satu solusi: A =0, B=0 dan C=1.

Cara selanjutnya adalah membangun tabel kebenaran . Karena besaran logis hanya mempunyai dua nilai, Anda cukup menelusuri semua opsi dan menemukan di antara opsi tersebut yang memenuhi sistem persamaan tertentu. Artinya, kita membuat satu tabel kebenaran umum untuk semua persamaan sistem dan menemukan garis dengan nilai yang diperlukan.

Solusi 2: Mari kita buat tabel kebenaran untuk sistem:

Garis yang memenuhi kondisi tugas ditandai dengan huruf tebal. Jadi A=0, B=0 dan C=1.

Jalan penguraian . Idenya adalah untuk menetapkan nilai salah satu variabel (mengaturnya sama dengan 0 atau 1) dan dengan demikian menyederhanakan persamaannya. Kemudian Anda bisa memperbaiki nilai variabel kedua, dan seterusnya.

Solusi 3: Misalkan A = 0, maka:

Dari persamaan pertama kita mendapatkan B = 0, dan dari persamaan kedua - C = 1. Solusi sistem: A = 0, B = 0 dan C = 1.

Dalam Ujian Negara Bersatu dalam ilmu komputer, sering kali diperlukan untuk menentukan jumlah solusi suatu sistem persamaan logika, tanpa menemukan solusinya sendiri; Cara utama untuk mencari banyak solusi suatu sistem persamaan logika adalahmengganti variabel. Pertama, Anda perlu menyederhanakan setiap persamaan sebanyak mungkin berdasarkan hukum aljabar logika, lalu mengganti bagian kompleks persamaan dengan variabel baru dan menentukan jumlah solusi untuk sistem baru. Selanjutnya, kembali ke penggantian dan tentukan jumlah solusinya.

Tugas: Berapa banyak solusi yang dimiliki persamaan (A →B) + (C →D) = 1? Dimana A, B, C, D adalah variabel logika.

Larutan: Mari kita perkenalkan variabel baru: X = A →B dan Y = C →D. Dengan memperhitungkan variabel baru, persamaannya akan ditulis sebagai: X + Y = 1.

Disjungsi tersebut benar dalam tiga kasus: (0;1), (1;0) dan (1;1), sedangkan X dan Y merupakan implikasi, yaitu benar dalam tiga kasus dan salah dalam satu kasus. Oleh karena itu, kasus (0;1) akan berhubungan dengan tiga kemungkinan kombinasi parameter. Kasus (1;1) – akan sesuai dengan sembilan kemungkinan kombinasi parameter persamaan asli. Artinya total penyelesaian persamaan ini adalah 3+9=15.

Cara menentukan banyaknya penyelesaian suatu sistem persamaan logika selanjutnya adalah pohon biner. Mari kita lihat metode ini menggunakan sebuah contoh.

Tugas: Berapa banyak solusi berbeda yang dimiliki sistem persamaan logika:

Sistem persamaan yang diberikan setara dengan persamaan:

(X 1 → X 2 )*(X 2 → X 3 )*…*(xm -1 → xm) = 1.

Mari kita asumsikan itu X 1 – benar, maka dari persamaan pertama kita peroleh bahwa X 2 juga benar, dari yang kedua - X 3 =1, dan seterusnya sampai xm= 1. Artinya himpunan (1; 1; …; 1) yang terdiri dari m satuan merupakan solusi sistem. Biarkan sekarang X 1 =0, maka dari persamaan pertama yang kita miliki X 2 =0 atau X 2 =1.

Kapan X 2 benar, kita memperoleh bahwa variabel-variabel yang tersisa juga benar, yaitu himpunan (0; 1; ...; 1) adalah solusi sistem. Pada X 2 =0 kita mengerti X 3 =0 atau X 3 =, dan seterusnya. Melanjutkan ke variabel terakhir, kita menemukan bahwa solusi persamaan tersebut adalah himpunan variabel berikut (m +1 solusi, setiap solusi berisi m nilai variabel):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Pendekatan ini diilustrasikan dengan baik dengan membangun pohon biner. Banyaknya solusi yang mungkin adalah jumlah cabang berbeda dari pohon yang dibangun. Sangat mudah untuk melihat bahwa itu sama dengan m +1.

Jika terjadi kesulitan dalam penalaran penelitian dan konstruksisolusi yang dapat Anda cari solusinya menggunakan tabel kebenaran, untuk satu atau dua persamaan.

Mari kita tulis ulang sistem persamaannya menjadi:

Dan mari kita buat tabel kebenaran secara terpisah untuk satu persamaan:

Mari kita buat tabel kebenaran untuk dua persamaan:

Bagaimana menyelesaikan beberapa soal pada bagian A dan B ujian ilmu komputer

Pelajaran #3. Logika. Fungsi logika. Memecahkan persamaan

Sejumlah besar soal Ujian Negara Bersatu dikhususkan untuk logika proposisional. Untuk menyelesaikan sebagian besarnya, cukup mengetahui hukum dasar logika proposisional, pengetahuan tentang tabel kebenaran fungsi logika satu dan dua variabel. Saya akan memberikan hukum dasar logika proposisional.

1. Komutatifitas disjungsi dan konjungsi:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Hukum distributif mengenai disjungsi dan konjungsi:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a^(b˅c) ≡(a^b)˅(a^c)
3. Negasi dari negasi:
   ¬(¬a) ≡ a
4. Konsistensi:
   a ^ ¬а ≡ salah
5. Eksklusif ketiga:
   a ˅ ¬а ≡ benar
6. Hukum De Morgan:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Penyederhanaan:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ benar ≡ a
   a ˄ salah ≡ salah
8. Penyerapan:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Penggantian implikasi
   a → b ≡ ¬a ˅ b
10. Penggantian identitas
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Representasi fungsi logis

Fungsi logis apa pun dari n variabel - F(x 1, x 2, ... x n) dapat ditentukan dengan tabel kebenaran. Tabel seperti itu berisi 2n himpunan variabel, yang masing-masingnya menentukan nilai fungsi pada himpunan ini. Metode ini bagus jika jumlah variabelnya relatif kecil. Sudah untuk n > 5 representasi menjadi kurang terlihat.

Cara lain adalah dengan mendefinisikan suatu fungsi dengan beberapa rumus menggunakan fungsi yang cukup sederhana. Suatu sistem fungsi (f 1, f 2, ... f k) disebut lengkap jika suatu fungsi logika dapat dinyatakan dengan rumus yang hanya memuat fungsi f i.

Sistem fungsi (¬, ˄, ˅) selesai. Hukum 9 dan 10 adalah contoh yang menunjukkan bagaimana implikasi dan identitas diungkapkan melalui negasi, konjungsi, dan disjungsi.

Faktanya, sistem dua fungsi – negasi dan konjungsi atau negasi dan disjungsi – juga lengkap. Dari hukum De Morgan muncul ide-ide yang memungkinkan seseorang untuk mengekspresikan konjungsi melalui negasi dan disjungsi dan, oleh karena itu, untuk mengekspresikan disjungsi melalui negasi dan konjungsi:

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

Paradoksnya, sistem yang hanya terdiri dari satu fungsi saja sudah lengkap. Ada dua fungsi biner - antikonjungsi dan antidisjungsi, yang disebut panah Peirce dan guratan Schaeffer, yang mewakili sistem berongga.

Fungsi dasar bahasa pemrograman biasanya meliputi identitas, negasi, konjungsi, dan disjungsi. Dalam soal-soal Unified State Examination, beserta fungsi-fungsi tersebut, sering ditemukan implikasinya.

Mari kita lihat beberapa masalah sederhana yang melibatkan fungsi logika.

Masalah 15:

Sebuah fragmen dari tabel kebenaran diberikan. Manakah dari tiga fungsi berikut yang sesuai dengan fragmen 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 nomor 3.

Untuk mengatasi masalah tersebut, Anda perlu mengetahui tabel kebenaran fungsi dasar dan mengingat prioritas operasi. Izinkan saya mengingatkan Anda bahwa konjungsi (perkalian logis) memiliki prioritas lebih tinggi dan dieksekusi lebih awal daripada disjungsi (penjumlahan logis). Selama penghitungan, mudah untuk melihat bahwa fungsi dengan angka 1 dan 2 pada himpunan ketiga memiliki nilai 1 dan oleh karena itu tidak sesuai dengan fragmen.

Masalah 16:

Manakah dari angka-angka berikut yang memenuhi kondisi:

(angka, mulai dari angka paling penting, berurutan menurun) → (angka - genap) ˄ (digit rendah - genap) ˄ (digit tinggi - ganjil)

Jika ada beberapa angka seperti itu, sebutkan yang terbesar.

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

Syaratnya dipenuhi oleh angka nomor 4.

Dua bilangan pertama tidak memenuhi syarat karena angka terendahnya ganjil. Suatu konjungsi kondisi dikatakan salah jika salah satu suku dari konjungsi tersebut salah. Untuk bilangan ketiga, syarat angka tertinggi tidak terpenuhi. Untuk bilangan keempat, syarat-syarat yang dikenakan pada angka rendah dan tinggi dari bilangan tersebut terpenuhi. Suku pertama konjungsi juga benar, karena implikasinya benar jika premisnya salah, seperti halnya dalam kasus ini.

Soal 17: Dua orang saksi memberikan keterangan sebagai berikut:

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

Saksi kedua: Dua orang bersalah. Dan salah satu yang tersisa pasti bersalah dan bersalah, tapi saya tidak bisa menyebutkan siapa sebenarnya.

Kesimpulan apa tentang kesalahan A, B dan C yang dapat diambil dari kesaksian tersebut?

Jawaban: Dari keterangan tersebut diketahui bahwa A dan B bersalah, dan C tidak bersalah.

Solusi: Tentu saja jawabannya bisa diberikan berdasarkan akal sehat. Namun mari kita lihat bagaimana hal ini dapat dilakukan secara ketat dan formal.

Hal pertama yang harus dilakukan adalah memformalkan pernyataan. Mari kita perkenalkan tiga variabel logis - A, B dan C, yang masing-masing memiliki nilai true (1) jika tersangka yang bersangkutan bersalah. Kemudian keterangan saksi pertama diberikan dengan rumus:

SEBUAH → (B ˄ ¬C)

Keterangan saksi kedua diberikan dengan rumus:

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

Kesaksian kedua saksi tersebut diasumsikan benar dan merupakan gabungan rumus-rumus yang bersesuaian.

Mari kita buat tabel kebenaran untuk pembacaan ini:

Bukti ringkasan hanya benar dalam satu kasus, sehingga menghasilkan jawaban yang jelas - A dan B bersalah, dan C tidak bersalah.

Dari analisa tabel ini juga dapat disimpulkan bahwa keterangan saksi kedua lebih informatif. Dari kebenaran kesaksiannya, hanya ada dua pilihan yang mungkin terjadi - A dan B bersalah, dan C tidak bersalah, atau A dan C bersalah, dan B tidak bersalah. Kesaksian saksi pertama kurang informatif - ada 5 pilihan berbeda yang sesuai dengan kesaksiannya. Secara bersama-sama, keterangan kedua saksi memberikan jawaban yang jelas tentang kesalahan para tersangka.

Persamaan logika dan sistem persamaan

Misalkan F(x 1, x 2, …x n) merupakan fungsi logika dari n variabel. Persamaan logisnya terlihat seperti:

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

Konstanta C bernilai 1 atau 0.

Persamaan logis dapat memiliki 0 hingga 2 n solusi berbeda. Jika C sama dengan 1, maka solusinya adalah semua himpunan variabel dari tabel kebenaran yang fungsi F bernilai benar (1). Himpunan sisanya adalah solusi persamaan dengan C sama dengan nol. Anda selalu dapat mempertimbangkan hanya persamaan bentuk:

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

Memang, biarkan persamaannya diberikan:

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

Dalam hal ini, kita dapat menuju ke persamaan ekuivalen:

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

Pertimbangkan sistem persamaan logika 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

Solusi suatu sistem adalah sekumpulan variabel yang memenuhi semua persamaan sistem. Dalam kaitannya dengan fungsi logika, untuk mendapatkan solusi suatu sistem persamaan logika, kita harus mencari himpunan yang fungsi logikanya benar, yang mewakili konjungsi dari fungsi asli F:

= F 1 ˄ F 2 ˄ … Fk

Jika jumlah variabelnya kecil, misalnya kurang dari 5, maka tidak sulit untuk membuat tabel kebenaran untuk fungsi tersebut, yang memungkinkan kita mengetahui berapa banyak solusi yang dimiliki sistem dan himpunan apa yang memberikan solusi.

Dalam beberapa soal USE dalam mencari solusi sistem persamaan logika, jumlah variabel mencapai 10. Kemudian menyusun tabel kebenaran menjadi tugas yang hampir mustahil. Pemecahan masalah memerlukan pendekatan yang berbeda. Untuk sistem persamaan arbitrer, tidak ada metode umum selain enumerasi yang memungkinkan penyelesaian masalah tersebut.

Dalam soal-soal yang diajukan pada ujian, penyelesaiannya biasanya didasarkan pada memperhatikan kekhususan sistem persamaan. Saya ulangi, selain mencoba semua opsi untuk sekumpulan variabel, tidak ada cara umum untuk menyelesaikan masalah. Solusinya harus dibangun berdasarkan spesifikasi sistem. Seringkali berguna untuk melakukan penyederhanaan awal suatu sistem persamaan dengan menggunakan hukum logika yang diketahui. Teknik lain yang berguna untuk memecahkan masalah ini adalah sebagai berikut. Kami tidak tertarik pada semua himpunan, tetapi hanya himpunan yang fungsinya memiliki nilai 1. Daripada membuat tabel kebenaran lengkap, kami akan membuat analoginya - pohon keputusan biner. Setiap cabang pohon ini berhubungan dengan satu solusi dan menentukan himpunan di mana fungsi Ф memiliki nilai 1. Jumlah cabang pada pohon keputusan bertepatan dengan jumlah solusi sistem persamaan.

Saya akan menjelaskan apa itu pohon keputusan biner dan bagaimana pohon itu dibangun dengan menggunakan contoh beberapa masalah.

Masalah 18

Berapa banyak himpunan nilai variabel logika x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 yang memenuhi sistem dua persamaan?

Jawaban: Sistem ini memiliki 36 solusi berbeda.

Penyelesaian: Sistem persamaan mencakup dua persamaan. Mari kita cari banyak solusi untuk persamaan pertama, bergantung pada 5 variabel - x 1, x 2, ...x 5. Persamaan pertama pada gilirannya dapat dianggap sebagai sistem 5 persamaan. Seperti yang telah ditunjukkan, sistem persamaan sebenarnya mewakili konjungsi fungsi logika. Kebalikannya juga benar: konjungsi kondisi dapat dianggap sebagai sistem persamaan.

Mari kita buat pohon keputusan untuk implikasinya (x1→ x2) - suku pertama konjungsi, yang dapat dianggap sebagai persamaan pertama. Seperti inilah representasi grafis dari pohon ini:

Pohon tersebut terdiri dari dua tingkatan sesuai dengan jumlah variabel dalam persamaan. Tingkat pertama menggambarkan variabel pertama X 1 . Dua cabang pada tingkat ini mencerminkan nilai yang mungkin dari variabel ini - 1 dan 0. Pada tingkat kedua, cabang-cabang pohon hanya mencerminkan nilai yang mungkin dari variabel X 2 yang persamaannya benar. Karena persamaan tersebut menentukan implikasinya, maka cabang yang X 1 bernilai 1 mensyaratkan bahwa pada cabang tersebut X 2 bernilai 1. Cabang yang X 1 bernilai 0 menghasilkan dua cabang yang bernilai X 2 sama dengan 0 dan 1 Pohon yang dibangun mendefinisikan tiga solusi, yang implikasinya X 1 → X 2 mengambil nilai 1. Pada setiap cabang, sekumpulan nilai variabel yang sesuai dituliskan, memberikan solusi persamaan.

Himpunan tersebut adalah: ((1, 1), (0, 1), (0, 0))

Mari kita lanjutkan membangun pohon keputusan dengan menambahkan persamaan berikut, implikasi berikut X 2 → X 3 . Kekhasan sistem persamaan kita adalah setiap persamaan baru dari sistem tersebut menggunakan satu variabel dari persamaan sebelumnya, sehingga menambah satu variabel baru. Karena variabel X 2 sudah mempunyai nilai di pohon, maka pada semua cabang yang variabel X 2 bernilai 1 maka variabel X 3 juga akan bernilai 1. Untuk cabang seperti itu, konstruksi pohon berlanjut ke tingkat berikutnya, namun cabang baru tidak muncul. Cabang tunggal yang variabel X 2 bernilai 0 akan bercabang menjadi dua cabang yang variabel X 3 akan bernilai 0 dan 1. Jadi, setiap penambahan persamaan baru, mengingat kekhususannya, menambah satu solusi. Persamaan pertama yang asli:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
memiliki 6 solusi. Berikut tampilan pohon keputusan lengkap untuk persamaan ini:

Persamaan kedua dari sistem kami mirip dengan yang pertama:

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

Satu-satunya perbedaan adalah persamaan tersebut menggunakan variabel Y. Persamaan ini juga memiliki 6 solusi. Karena setiap solusi untuk variabel X i dapat digabungkan dengan setiap solusi untuk variabel Y j , maka jumlah solusinya adalah 36.

Harap dicatat bahwa pohon keputusan yang dibangun tidak hanya memberikan jumlah solusi (sesuai dengan jumlah cabang), tetapi juga solusi itu sendiri yang tertulis pada setiap cabang pohon.

Soal 19

Berapa banyak himpunan nilai variabel logis x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 yang memenuhi semua kondisi di bawah ini?

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

Tugas ini merupakan modifikasi dari tugas sebelumnya. Bedanya, ditambahkan persamaan lain yang menghubungkan variabel X dan Y.

Dari persamaan X 1 → Y 1 dapat disimpulkan bahwa jika X 1 bernilai 1 (ada satu solusi seperti itu), maka Y 1 juga bernilai 1. Jadi, ada satu himpunan yang X 1 dan Y 1 bernilai ​​1. Ketika X 1 sama dengan 0, Y 1 dapat memiliki nilai apa pun, baik 0 maupun 1. Oleh karena itu, setiap himpunan dengan X 1 sama dengan 0, dan ada 5 himpunan tersebut, sesuai dengan keenam himpunan dengan variabel Y. Jadi, jumlah penyelesaiannya adalah 31 .

Soal 20

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

Solusi: Mengingat persamaan dasar, kita menulis persamaan kita sebagai:

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

Implikasi rantai siklik berarti variabel-variabelnya identik, sehingga persamaan kita ekuivalen dengan persamaan:

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

Persamaan ini memiliki dua solusi jika semua X i bernilai 1 atau 0.

Soal 21

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

Solusi: Seperti pada soal 20, kita beralih dari implikasi siklik ke identitas, menulis ulang persamaannya dalam bentuk:

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

Mari kita buat pohon keputusan untuk persamaan ini:

Soal 22

Berapa banyak solusi yang dimiliki 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

Jawaban: 64

Solusi: Mari kita beralih dari 10 variabel menjadi 5 variabel dengan memasukkan perubahan variabel 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);

Maka persamaan pertama akan berbentuk:

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

Persamaannya dapat disederhanakan dengan menuliskannya sebagai:

(Y 1 ≡ Y 2) = 0

Beralih ke bentuk tradisional, kami menulis sistem setelah disederhanakan dalam bentuk:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Pohon keputusan untuk sistem ini sederhana dan terdiri dari dua cabang dengan nilai variabel bergantian:

Kembali ke variabel X awal, perhatikan bahwa untuk setiap nilai pada variabel Y terdapat 2 nilai pada variabel X, sehingga setiap solusi pada variabel Y menghasilkan 2 5 solusi pada variabel X. Kedua cabang tersebut menghasilkan 2 * 2 5 penyelesaian, jadi jumlah penyelesaiannya adalah 64.

Seperti yang Anda lihat, setiap masalah dalam menyelesaikan sistem persamaan memerlukan pendekatannya sendiri. Teknik yang umum adalah melakukan transformasi ekuivalen untuk menyederhanakan persamaan. Teknik yang umum adalah dengan membangun pohon keputusan. Pendekatan yang digunakan sebagian mengingatkan pada pembuatan tabel kebenaran dengan kekhasan bahwa tidak semua himpunan nilai yang mungkin dari variabel dikonstruksi, tetapi hanya himpunan yang fungsinya bernilai 1 (benar). Seringkali dalam permasalahan yang diajukan tidak perlu membangun pohon keputusan yang lengkap, karena sudah pada tahap awal sudah dimungkinkan untuk menetapkan pola munculnya cabang baru di setiap level berikutnya, seperti yang dilakukan, misalnya pada soal 18. .

Secara umum, permasalahan yang melibatkan pencarian solusi terhadap sistem persamaan logika merupakan latihan matematika yang baik.

Jika permasalahan sulit diselesaikan secara manual, maka Anda dapat mempercayakan penyelesaiannya kepada komputer dengan menulis program yang sesuai untuk menyelesaikan persamaan dan sistem persamaan.

Tidak sulit untuk menulis program seperti itu. Program seperti itu akan dengan mudah mengatasi semua tugas yang ditawarkan dalam Ujian Negara Bersatu.

Anehnya, tugas mencari solusi sistem persamaan logika sulit dilakukan oleh komputer, dan ternyata komputer ada batasnya. Komputer dapat dengan mudah mengatasi masalah yang jumlah variabelnya 20-30, tetapi komputer akan mulai berpikir lama untuk masalah yang berukuran lebih besar. Faktanya adalah bahwa fungsi 2 n, yang menentukan jumlah himpunan, adalah eksponensial yang tumbuh dengan cepat seiring bertambahnya n. Begitu cepatnya sehingga komputer pribadi biasa tidak dapat menangani tugas yang memiliki 40 variabel dalam sehari.

Program dalam bahasa C# untuk menyelesaikan persamaan logika

Menulis program untuk menyelesaikan persamaan logika berguna karena berbagai alasan, jika hanya karena Anda dapat menggunakannya untuk memeriksa kebenaran solusi Anda sendiri terhadap soal ujian Ujian Negara Bersatu. Alasan lainnya adalah bahwa program semacam itu merupakan contoh yang sangat baik dari tugas pemrograman yang memenuhi persyaratan untuk tugas kategori C dalam Ujian Negara Bersatu.

Ide membangun sebuah program sederhana - ini didasarkan pada pencarian lengkap semua kemungkinan kumpulan nilai variabel. Karena untuk suatu persamaan logika atau sistem persamaan tertentu diketahui banyaknya variabel n, maka banyaknya himpunan juga diketahui - 2 n yang perlu diurutkan. Dengan menggunakan fungsi dasar bahasa C# - negasi, disjungsi, konjungsi, dan identitas, tidak sulit untuk menulis sebuah program yang, untuk sekumpulan variabel tertentu, menghitung nilai fungsi logika yang sesuai dengan persamaan logika atau sistem persamaan. .

Dalam program seperti itu, Anda perlu membuat perulangan berdasarkan jumlah himpunan, di badan perulangan, menggunakan jumlah himpunan, membentuk himpunan itu sendiri, menghitung nilai fungsi pada himpunan ini, dan jika ini bernilai 1, maka himpunan tersebut memberikan solusi terhadap persamaan tersebut.

Satu-satunya kesulitan yang muncul ketika mengimplementasikan program ini terkait dengan tugas menghasilkan himpunan nilai variabel itu sendiri berdasarkan nomor yang ditetapkan. Keindahan dari masalah ini adalah bahwa tugas yang tampaknya sulit ini sebenarnya bermuara pada masalah sederhana yang telah muncul berkali-kali. Memang cukup dipahami bahwa himpunan nilai variabel yang bersesuaian dengan bilangan i, terdiri dari nol dan satu, mewakili representasi biner dari bilangan i. Jadi tugas kompleks untuk memperoleh sekumpulan nilai variabel dengan bilangan tertentu direduksi menjadi tugas biasa yaitu mengubah bilangan menjadi biner.

Seperti inilah fungsi di C# yang memecahkan masalah kita:

///

///

/// fungsi logis - metode,

/// yang tanda tangannya ditentukan oleh delegasi DF

///

/// jumlah variabel

/// sejumlah solusi

static int SolveEquations(DF menyenangkan, int n)

bool set = bool baru[n];

int m = (int)Matematika.Pow(2, n); //jumlah set

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

//Selesaikan pencarian berdasarkan jumlah set

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

//Pembentukan himpunan berikutnya – himpunan,

//ditentukan oleh representasi biner dari bilangan i

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

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

//Hitung nilai fungsi pada himpunan

Untuk memahami program ini, saya harap penjelasan yang diberikan mengenai ide program dan komentar dalam teksnya cukup. Saya hanya akan fokus menjelaskan judul fungsi yang diberikan. Fungsi SolveEquations memiliki dua parameter masukan. Parameter fun menentukan fungsi logika yang sesuai dengan persamaan atau sistem persamaan yang sedang diselesaikan. Parameter n menentukan jumlah variabel menyenangkan. Hasilnya, fungsi SolveEquations mengembalikan jumlah solusi dari fungsi logis, yaitu jumlah himpunan yang fungsi tersebut bernilai benar.

Hal yang biasa terjadi pada anak sekolah ketika beberapa fungsi F(x) memiliki parameter input x yang merupakan variabel bertipe aritmatika, string, atau logika. Dalam kasus kami, desain yang lebih kuat digunakan. Fungsi SolveEquations mengacu pada fungsi tingkat tinggi - fungsi bertipe F(f), yang parameternya tidak hanya berupa variabel sederhana, tetapi juga fungsi.

Kelas fungsi yang dapat diteruskan sebagai parameter ke fungsi SolveEquations ditentukan sebagai berikut:

delegasi bool DF(bool vars);

Kelas ini memiliki semua fungsi yang diteruskan sebagai parameter sekumpulan nilai variabel logis yang ditentukan oleh array vars. Hasilnya adalah nilai Boolean yang mewakili nilai fungsi pada himpunan ini.

Terakhir, berikut adalah program yang menggunakan fungsi SolveEquations untuk menyelesaikan beberapa sistem persamaan logika. Fungsi SolveEquations adalah bagian dari kelas ProgramCommon di bawah ini:

kelas ProgramUmum

delegasi bool DF(bool vars);

kekosongan statis Utama (argumen string)

Console.WriteLine("Dan Fungsi - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("Fungsi ini memiliki 51 solusi - " +

SolveEquations(Fun51, 5));

Console.WriteLine("Fungsi ini memiliki 53 solusi - " +

SolveEquations(Fun53, 10));

bool statis FunAnd(bool vars)

kembalikan vars && vars;

bool statis Fun51 (bool vars)

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

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

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

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

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

bool statis 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)));

Berikut hasil solusi dari program ini:

10 tugas untuk pekerjaan mandiri

1. Manakah dari ketiga fungsi tersebut yang ekuivalen:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X˄Y
2. Diberikan adalah bagian dari tabel kebenaran:

Manakah dari tiga fungsi yang sesuai dengan fragmen 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 dari tiga orang. Keputusan diambil jika ketua juri memberikan suaranya, didukung oleh setidaknya salah satu anggota juri. Jika tidak, tidak ada keputusan yang dibuat. Bangun fungsi logis yang memformalkan proses pengambilan keputusan.
5. X menang atas Y jika empat kali pelemparan koin menghasilkan gambar tiga kali. Tentukan fungsi logis yang menggambarkan hasil X.
6. Kata-kata dalam sebuah kalimat diberi nomor mulai dari satu. Sebuah kalimat dianggap dibangun dengan benar jika aturan berikut dipenuhi:
   1. Jika suatu kata genap diakhiri dengan vokal, maka kata berikutnya, jika ada, harus diawali dengan vokal.
   2. Jika suatu kata ganjil diakhiri dengan konsonan, maka kata berikutnya, jika ada, harus diawali dengan konsonan dan diakhiri dengan vokal.
      Manakah dari kalimat berikut yang dibangun dengan benar:
   3. Ibu mencuci Masha dengan sabun.
   4. Seorang pemimpin selalu menjadi teladan.
   5. Kebenaran itu baik, tapi kebahagiaan lebih baik.
7. Berapa banyak solusi yang dimiliki persamaan tersebut:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Daftar semua solusi persamaan:
   (a → b) → c = 0
9. Berapa banyak solusi yang dimiliki 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 solusi yang dimiliki persamaan tersebut:
    ((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Jawaban atas masalah:

1. Fungsi b dan c ekuivalen.
2. Fragmen tersebut sesuai dengan fungsi b.
3. Biarkan variabel logis P mengambil nilai 1 ketika ketua juri memberikan suara “untuk” keputusan tersebut. Variabel M 1 dan M 2 mewakili pendapat para juri. Fungsi logika yang menentukan pengambilan keputusan positif dapat ditulis sebagai berikut:
   P ˄ (M 1 ˅ M 2)
4. Biarkan variabel logis P i mengambil nilai 1 ketika pelemparan koin ke-i mendarat di kepala. Fungsi logika yang menentukan payoff X dapat ditulis sebagai berikut:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Kalimatb.
6. Persamaan tersebut memiliki 3 solusi: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Lembaga pendidikan anggaran kota

"Sekolah Menengah No. 18"

distrik perkotaan kota Salavat Republik Bashkortostan

Sistem persamaan logika

dalam masalah Unified State Examination dalam ilmu komputer

Bagian “Dasar-Dasar Aljabar Logika” dalam tugas-tugas Ujian Negara Terpadu dianggap salah satu yang paling sulit dan sulit untuk diselesaikan. Persentase rata-rata tugas yang diselesaikan pada topik ini adalah yang terendah yaitu 43,2.

Berdasarkan spesifikasi KIM 2018, blok ini mencakup empat tugas dengan tingkat kesulitan berbeda.

Tugas 23 memiliki tingkat kesulitan yang tinggi sehingga persentase penyelesaiannya paling rendah. Di antara lulusan yang siap (81-100 poin) 49,8% menyelesaikan tugas, cukup siap (61-80 poin) menyelesaikan 13,7%, sisanya kelompok siswa tidak menyelesaikan tugas ini.

Keberhasilan menyelesaikan sistem persamaan logika bergantung pada pengetahuan tentang hukum logika dan penerapan metode yang tepat untuk menyelesaikan sistem tersebut.

Mari kita pertimbangkan penyelesaian sistem persamaan logika menggunakan metode pemetaan.

(23.154 Polyakov K.Yu.) Berapa banyak solusi berbeda yang dimiliki sistem persamaan?

((X1  kamu1 )  (X2  kamu2 ))  (X1  X2 )  (y1  kamu2 ) =1

((X2  kamu2 )  (X3  kamu3 ))  (X2  X3 )  (y2  kamu3 ) =1

((X7  kamu7 )  (X8  kamu8 ))  (X7  X8 )  (kamu7  kamu8 ) =1

Di mana X1 , X2 ,…, X8, pada1 ,y2 ,…,kamu8 - variabel logis? Jawabannya tidak perlu mencantumkan semua kumpulan nilai variabel berbeda yang memiliki persamaan ini. Sebagai jawabannya, Anda perlu menunjukkan jumlah set tersebut.

Larutan. Semua persamaan yang termasuk dalam sistem memiliki tipe yang sama, dan setiap persamaan mencakup empat variabel. Dengan mengetahui x1 dan y1, kita dapat mencari semua kemungkinan nilai x2 dan y2 yang memenuhi persamaan pertama. Dengan alasan serupa, dari x2 dan y2 yang diketahui kita dapat menemukan x3, y3 yang memenuhi persamaan kedua. Artinya, dengan mengetahui pasangan (x1, y1) dan menentukan nilai pasangan (x2, y2), kita akan mencari pasangan (x3, y3), yang selanjutnya akan menghasilkan pasangan (x4, y4) dan sebagainya.

Mari kita cari semua solusi persamaan pertama. Hal ini dapat dilakukan dengan dua cara: menyusun tabel kebenaran, melalui penalaran dan menerapkan hukum logika.

Tabel kebenaran:

Membuat tabel kebenaran membutuhkan banyak tenaga dan waktu, jadi kami menggunakan metode kedua - penalaran logis. Hasil kali sama dengan 1 jika dan hanya jika setiap faktor sama dengan 1.

(X1  kamu1 )  (X2  kamu2 ))=1

(X1  X2 ) =1

(kamu1  kamu2 ) =1

Mari kita lihat persamaan pertama. Konsekuensinya sama dengan 1 bila 0 0, 0 1, 1 1, artinya (x1 y1)=0 untuk (01), (10), maka pasangannya (X2  kamu2 ) dapat berupa (00), (01), (10), (11), dan jika (x1 y1) = 1, yaitu (00) dan (11) pasangan (x2 y2) = 1 maka nilai yang sama (00) dan (11). Mari kita kecualikan dari solusi ini pasangan-pasangan yang persamaan kedua dan ketiganya salah, yaitu x1=1, x2=0, y1=1, y2=0.

Jumlah pasangan 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Berapa banyak solusi berbeda yang dimiliki sistem persamaan logika?

(X 1  (X 2  kamu 2 ))  (y 1  kamu 2 ) = 1

(X 2  (X 3  kamu 3 ))  (y 2  kamu 3 ) = 1

...

( X 6  ( X 7  kamu 7 ))  ( kamu 6  kamu 7 ) = 1

X 7  kamu 7 = 1

Larutan. 1) Persamaannya bertipe sama, jadi dengan menggunakan penalaran kita akan mencari semua kemungkinan pasangan (x1,y1), (x2,y2) dari persamaan pertama.

(X1  (X2  kamu2 ))=1

(kamu1  kamu2 ) = 1

Penyelesaian persamaan kedua adalah pasangan (00), (01), (11).

Mari kita cari solusi untuk persamaan pertama. Jika x1=0, maka x2, y2 - sembarang, jika x1=1, maka x2, y2 bernilai (11).

Mari kita buat hubungan antara pasangan (x1, y1) dan (x2, y2).

Mari kita buat tabel untuk menghitung jumlah pasangan pada setiap tahap.

Mempertimbangkan solusi persamaan terakhir X 7  kamu 7 = 1, mari kita kecualikan pasangan (10). Temukan jumlah total solusi 1+7+0+34=42

3)(23.180) Berapa banyak solusi berbeda yang dimiliki sistem persamaan logika?

(X1  X2 )  (X3  X4 ) = 1

(X3  X4 )  (X5  X6 ) = 1

(X5  X6 )  (X7  X8 ) = 1

(X7  X8 )  (X9  X10 ) = 1

X1  X3  X5  X7  X9 = 1

Larutan. 1) Persamaannya bertipe sama, jadi dengan menggunakan penalaran kita akan mencari semua kemungkinan pasangan (x1,x2), (x3,x4) dari persamaan pertama.

(X1  X2 )  (X3  X4 ) = 1

Mari kita kecualikan dari solusi pasangan-pasangan yang dalam barisan tersebut menghasilkan 0 (1 0), yaitu pasangan (01, 00, 11) dan (10).

Mari kita buat hubungan antar pasangan (x1,x2), (x3,x4)

Misalkan fungsi logis dari n variabel. Persamaan logisnya terlihat seperti:

Konstanta C bernilai 1 atau 0.

Persamaan logis dapat memiliki solusi dari 0 hingga berbeda. Jika C sama dengan 1, maka solusinya adalah semua himpunan variabel dari tabel kebenaran yang fungsi F bernilai benar (1). Himpunan sisanya adalah solusi persamaan dengan C sama dengan nol. Anda selalu dapat mempertimbangkan hanya persamaan bentuk:

Memang, biarkan persamaannya diberikan:

Dalam hal ini, kita dapat menuju ke persamaan ekuivalen:

Pertimbangkan sistem persamaan logika k:

Solusi suatu sistem adalah sekumpulan variabel yang memenuhi semua persamaan sistem. Dalam kaitannya dengan fungsi logika, untuk mendapatkan solusi suatu sistem persamaan logika, kita harus mencari himpunan yang fungsi logikanya benar, yang mewakili konjungsi fungsi aslinya:

Jika jumlah variabelnya kecil, misalnya kurang dari 5, maka tidak sulit untuk membuat tabel kebenaran untuk fungsi tersebut, yang memungkinkan Anda mengetahui berapa banyak solusi yang dimiliki sistem dan himpunan apa yang menghasilkan solusi tersebut.

Dalam beberapa soal USE dalam mencari solusi sistem persamaan logika, jumlah variabel mencapai 10. Kemudian menyusun tabel kebenaran menjadi tugas yang hampir mustahil. Pemecahan masalah memerlukan pendekatan yang berbeda. Untuk sistem persamaan arbitrer, tidak ada metode umum selain enumerasi yang memungkinkan penyelesaian masalah tersebut.

Dalam soal-soal yang diajukan pada ujian, penyelesaiannya biasanya didasarkan pada memperhatikan kekhususan sistem persamaan. Saya ulangi, selain mencoba semua opsi untuk sekumpulan variabel, tidak ada cara umum untuk menyelesaikan masalah. Solusinya harus dibangun berdasarkan spesifikasi sistem. Seringkali berguna untuk melakukan penyederhanaan awal suatu sistem persamaan dengan menggunakan hukum logika yang diketahui. Teknik lain yang berguna untuk memecahkan masalah ini adalah sebagai berikut. Kami tidak tertarik pada semua himpunan, tetapi hanya himpunan yang fungsinya memiliki nilai 1. Daripada membuat tabel kebenaran lengkap, kami akan membuat analoginya - pohon keputusan biner. Setiap cabang pohon ini berhubungan dengan satu solusi dan menentukan himpunan yang fungsinya bernilai 1. Jumlah cabang pada pohon keputusan bertepatan dengan jumlah solusi sistem persamaan.

Saya akan menjelaskan apa itu pohon keputusan biner dan bagaimana pohon itu dibangun dengan menggunakan contoh beberapa masalah.

Masalah 18

Berapa banyak himpunan nilai variabel logika x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 yang memenuhi sistem dua persamaan?

Jawaban: Sistem ini memiliki 36 solusi berbeda.

Penyelesaian: Sistem persamaan mencakup dua persamaan. Mari kita cari banyak solusi untuk persamaan pertama, bergantung pada 5 variabel - . Persamaan pertama pada gilirannya dapat dianggap sebagai sistem 5 persamaan. Seperti yang telah ditunjukkan, sistem persamaan sebenarnya mewakili konjungsi fungsi logika. Pernyataan sebaliknya juga benar - konjungsi kondisi dapat dianggap sebagai sistem persamaan.

Mari kita buat pohon keputusan untuk implikasi () - suku pertama dari konjungsi, yang dapat dianggap sebagai persamaan pertama. Seperti inilah representasi grafis dari pohon ini

Pohon tersebut terdiri dari dua tingkatan sesuai dengan jumlah variabel dalam persamaan. Tingkat pertama menggambarkan variabel pertama. Dua cabang pada tingkat ini mencerminkan nilai yang mungkin dari variabel ini - 1 dan 0. Pada tingkat kedua, cabang-cabang pohon hanya mencerminkan nilai-nilai yang mungkin dari variabel yang persamaannya dinilai benar. Karena persamaan tersebut menentukan implikasi, maka cabang yang bernilai 1 mengharuskan pada cabang tersebut terdapat nilai 1. Cabang yang bernilai 0 menghasilkan dua cabang dengan nilai sama dengan 0 dan 1. Konstruksinya pohon menentukan tiga solusi, yang implikasinya bernilai 1. Pada setiap cabang, sekumpulan nilai variabel yang sesuai dituliskan, memberikan solusi pada persamaan tersebut.

Himpunan tersebut adalah: ((1, 1), (0, 1), (0, 0))

Mari lanjutkan membangun pohon keputusan dengan menambahkan persamaan berikut, implikasi berikut. Kekhasan sistem persamaan kita adalah setiap persamaan baru dari sistem tersebut menggunakan satu variabel dari persamaan sebelumnya, sehingga menambah satu variabel baru. Karena variabel sudah mempunyai nilai pada pohonnya, maka pada semua cabang yang variabelnya mempunyai nilai 1, maka variabel tersebut juga akan mempunyai nilai 1. Untuk cabang yang demikian, pembangunan pohonnya dilanjutkan ke tingkat berikutnya, tetapi tidak ada cabang baru yang muncul. Satu cabang yang variabelnya bernilai 0 akan bercabang menjadi dua cabang yang variabelnya akan bernilai 0 dan 1. Jadi, setiap penambahan persamaan baru, mengingat kekhususannya, akan menambah satu solusi. Persamaan pertama yang asli:

memiliki 6 solusi. Berikut tampilan pohon keputusan lengkap untuk persamaan ini:

Persamaan kedua dari sistem kami mirip dengan yang pertama:

Satu-satunya perbedaan adalah persamaan tersebut menggunakan variabel Y. Persamaan ini juga memiliki 6 solusi. Karena setiap solusi variabel dapat digabungkan dengan setiap solusi variabel, maka jumlah solusinya adalah 36.

Harap dicatat bahwa pohon keputusan yang dibangun tidak hanya memberikan jumlah solusi (sesuai dengan jumlah cabang), tetapi juga solusi itu sendiri yang tertulis pada setiap cabang pohon.

Soal 19

Berapa banyak himpunan nilai variabel logis x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 yang memenuhi semua kondisi di bawah ini?

Tugas ini merupakan modifikasi dari tugas sebelumnya. Bedanya, ditambahkan persamaan lain yang menghubungkan variabel X dan Y.

Dari persamaan tersebut dapat disimpulkan bahwa jika bernilai 1 (ada salah satu solusi tersebut), maka bernilai 1. Jadi, ada satu himpunan yang bernilai 1. Jika sama dengan 0 maka dapat mempunyai nilai apa pun, baik 0 maupun 1. Oleh karena itu, setiap himpunan dengan , sama dengan 0, dan terdapat 5 himpunan tersebut, berkorespondensi dengan keenam himpunan dengan variabel Y. Oleh karena itu, jumlah penyelesaiannya adalah 31.

Soal 20

Solusi: Mengingat persamaan dasar, kita menulis persamaan kita sebagai:

Implikasi rantai siklik berarti variabel-variabelnya identik, sehingga persamaan kita ekuivalen dengan persamaan:

Persamaan ini memiliki dua solusi jika semuanya bernilai 1 atau 0.

Soal 21

Berapa banyak solusi yang dimiliki persamaan tersebut:

Solusi: Seperti pada soal 20, kita beralih dari implikasi siklik ke identitas, menulis ulang persamaannya dalam bentuk:

Mari kita buat pohon keputusan untuk persamaan ini:

Soal 22

Berapa banyak solusi yang dimiliki sistem persamaan berikut?