Persamaan logika untuk membangun pohon. Memecahkan persamaan logika. Elemen logika komputer. Konstruksi diagram fungsional

Anda dapat memilih berbagai cara solusi sistem persamaan logis. Ini adalah reduksi menjadi satu persamaan, pembuatan tabel kebenaran, dan dekomposisi.

Tugas: Memecahkan sistem persamaan logika:

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 berikutnya kami menggabungkan persamaan menjadi satu, setara dengan sistem, menggunakan operasi logis"DAN". Setelah ini, Anda harus mengubah persamaan yang dihasilkan berdasarkan hukum aljabar logis dan mendapatkan solusi spesifik sistem.

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 logika hanya mempunyai dua nilai, Anda cukup menelusuri semua opsi dan menemukan nilai yang mana di antara opsi tersebut sistem ini persamaan. Artinya, kami sedang membangunnya tabel umum kebenaran untuk semua persamaan sistem dan temukan garis dengan nilai yang diperlukan.

Solusi 2: Mari kita buat tabel kebenaran untuk sistem:

0	0	1	1	0	1

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 Unified State Examination dalam ilmu komputer, seringkali diperlukan untuk menentukan banyaknya 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 tersebut dengan variabel baru dan menentukan jumlah solusinya. 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. Jadi, total solusi yang memungkinkan persamaan yang diberikan 3+9=15.

Cara menentukan banyaknya penyelesaian suatu sistem persamaan logika selanjutnya adalah pohon biner. Mari kita pertimbangkan metode ini Misalnya.

Tugas: Berapa banyak berbagai solusi memiliki sistem persamaan logika:

Sistem persamaan yang diberikan setara dengan persamaan:

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

Mari kita berpura-pura seperti 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.

	Pohon	Jumlah solusi
x 1
x 2
x 3
		…

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:

x 1	x 2	(x 1 → x 2)

Mari kita buat tabel kebenaran untuk dua persamaan:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) * (x 2 → x 3)

Anggaran kota lembaga pendidikan

"Rata-rata sekolah yang komprehensif Nomor 18"

distrik perkotaan kota Salavat Republik Bashkortostan

Sistem persamaan logika

dalam masalah Unified State Examination dalam ilmu komputer

Bagian "Dasar-Dasar Logika Aljabar" di Tugas Ujian Negara Bersatu dianggap sebagai salah satu yang paling sulit dan paling sulit dipecahkan. Persentase rata-rata penyelesaian tugas pada topik ini paling rendah yaitu sebesar 43,2.

Bagian kursus	Persentase penyelesaian rata-rata menurut kelompok tugas
Mengkodekan informasi dan mengukur kuantitasnya
Pemodelan Informasi
Sistem bilangan
Dasar-dasar Aljabar Logika
Algoritma dan pemrograman
Dasar-dasar informasi dan Komunikasi teknologi

Berdasarkan spesifikasi CMM 2018, blok ini mencakup empat tugas tingkat yang berbeda kesulitan.

№ tugas	Dapat diverifikasi elemen konten	Tingkat kesulitan tugas
	Kemampuan untuk membuat tabel kebenaran dan logika
	Kemampuan untuk mencari informasi di Internet
	Pengetahuan tentang konsep dasar dan hukum logika matematika
	Kemampuan untuk membangun dan mengubah ekspresi logis

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%, kelompok siswa lainnya 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 seterusnya.

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

Meja kebenaran:

				x 1  kamu 1	x 2  kamu 2	(x 1  kamu 1)  (x2  kamu2)	(x 1  x2)	(kamu 1  kamu2)	(x 1  x2)  (kamu 1  kamu2)

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.

(X1 , kamu1 )	(X2 , kamu2 )

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).

(X1 , kamu1 )	(X2 , kamu2 )

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

							0

Mempertimbangkan solusi persamaan terakhir X 7  kamu 7 = 1, mari kita kecualikan pasangan (10). Kami menemukan jumlah total penyelesaian 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)

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

Pelajaran #3. Logika. Fungsi logika. Memecahkan persamaan

Sejumlah besar Masalah Ujian Negara Bersatu didedikasikan 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 fungsi menggunakan rumus tertentu, menggunakan rumus yang cukup diketahui fungsi 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 tugas-tugas sederhana berhubungan dengan fungsi logis.

Masalah 15:

Sebuah fragmen dari tabel kebenaran diberikan. Manakah dari tiga fungsi berikut yang sesuai dengan fragmen ini?

X 1	X 2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

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 nomor keempat, syarat-syarat dikenakan pada anak di bawah umur dan angka tertinggi angka. Suku pertama konjungsi juga benar, karena implikasinya benar jika premisnya salah, seperti yang terjadi di sini.

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 kewajaran. 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:

A	B	C	F 1	F 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

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. Hanya ada dua hal yang mengikuti kebenaran kesaksiannya: pilihan yang memungkinkan- A dan B bersalah, dan C tidak bersalah, atau A dan C bersalah, dan B tidak bersalah. Kesaksian saksi pertama kurang informatif - ada 5 berbagai pilihan, 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 merupakan penyelesaian persamaan untuk 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, …x n) = 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, …xn) = 1

F 2 (x 1, x 2, …xn) = 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 sewenang-wenang tidak ada persamaan metode umum, berbeda dengan brute force, yang memungkinkan pemecahan masalah seperti itu.

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 fungsi Φ memiliki nilai 1. Daripada membangun meja penuh sebenarnya, kami akan membangun 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 tampilannya gambar grafis pohon ini:

Pohon itu terdiri dari dua tingkat sesuai dengan jumlahnya variabel 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 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

Pindah ke bentuk tradisional, sistemnya kita tulis 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. Penerimaan 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 mengambil nilai 1 (benar). Seringkali dalam permasalahan yang diajukan tidak perlu membangun pohon keputusan yang lengkap, karena sudah ada tahap awal dimungkinkan untuk membentuk pola kemunculan cabang-cabang baru pada masing-masing cabang tingkat selanjutnya, 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 tugas-tugas yang jumlah variabelnya 20-30, tetapi komputer akan mulai memikirkan masalah untuk waktu yang lama ukuran 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, salah satunya karena dapat digunakan untuk memeriksa kebenarannya keputusan sendiri masalah tes 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 Unified State Examination.

Ide membangun sebuah program itu sederhana - didasarkan pada pencarian lengkap semuanya set yang mungkin 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 yang sulit memperoleh sekumpulan nilai variabel dengan menetapkan angka bermuara pada tugas terkenal yaitu mengubah angka menjadi sistem biner.

Seperti inilah fungsi di C# yang memecahkan masalah kita:

///

/// program untuk menghitung jumlah solusi

/// persamaan logis (sistem persamaan)

///

///

/// 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 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 logis yang sesuai dengan persamaan atau sistem persamaan yang sedang diselesaikan. Parameter n menentukan nomornya variabel fungsi seru. 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 masukan x yaitu aritmatika, string, atau tipe boolean. Dalam kasus kami, desain yang lebih kuat digunakan. Fungsi SolveEquations termasuk dalam fungsi tersebut tatanan yang lebih 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:

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

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 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)

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, dimana J, K, L, M, N adalah variabel logika?

Penjelasan.

Oleh karena itu, ekspresi (N ∨ ¬N) berlaku untuk N apa pun

J ∧ ¬K ∧ L ∧ ¬M = 0.

Mari kita terapkan negasi pada kedua ruas persamaan logika dan gunakan hukum De Morgan ¬ (A ∧ B) = ¬ A ∨ ¬ B. Kita peroleh ¬J ∨ K ∨ ¬L ∨ M = 1.

Suatu jumlah logis sama dengan 1 jika setidaknya salah satu pernyataan penyusunnya sama dengan 1. Oleh karena itu, persamaan yang dihasilkan dipenuhi oleh kombinasi variabel logis apa pun kecuali jika semua besaran yang termasuk dalam persamaan sama dengan 0. Masing-masing besaran yang termasuk dalam persamaan tersebut sama dengan 0. keempat variabel tersebut bisa sama dengan 1 atau 0, oleh karena itu semua kombinasi yang mungkin adalah 2·2·2·2 = 16. Oleh karena itu, persamaan tersebut mempunyai 16 −1 = 15 penyelesaian.

Perlu dicatat bahwa 15 solusi yang ditemukan sesuai dengan salah satu dari dua kemungkinan nilai variabel logika N, sehingga persamaan aslinya memiliki 30 solusi.

Jawaban: 30

Berapa banyak solusi berbeda yang dimiliki persamaan tersebut?

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

dimana J, K, L, M, N adalah variabel logika?

Jawabannya tidak perlu mencantumkan semua himpunan nilai J, K, L, M, dan N yang berbeda yang memiliki persamaan ini. Sebagai jawabannya, Anda perlu menunjukkan jumlah set tersebut.

Penjelasan.

Kita menggunakan rumus A → B = ¬A ∨ B dan ¬(A ∨ B) = ¬A ∧ ¬B

Mari kita pertimbangkan subrumus pertama:

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Mari kita pertimbangkan subrumus kedua

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Mari kita pertimbangkan subrumus ketiga

1) M → J = 1 oleh karena itu,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Mari kita gabungkan:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 sehingga terdapat 4 penyelesaian.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Mari kita gabungkan:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L maka ada 4 penyelesaian.

c) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Jawaban: 4 + 4 = 8.

Jawaban: 8

Berapa banyak solusi berbeda yang dimiliki persamaan tersebut?

((K ∨ L) → (L ∧ M ∧ N)) = 0

dimana K, L, M, N adalah variabel logika? Jawabannya tidak perlu mencantumkan semua himpunan nilai K, L, M, dan N yang berbeda yang memiliki persamaan ini. Sebagai Jawaban, Anda perlu menunjukkan jumlah set tersebut.

Penjelasan.

Mari kita tulis ulang persamaan tersebut menggunakan notasi operasi yang lebih sederhana:

((K + L) → (L M N)) = 0

1) dari tabel kebenaran operasi “implikasi” (lihat soal pertama) maka persamaan ini benar jika dan hanya jika pada saat yang sama

K + L = 1 dan L M N = 0

2) dari persamaan pertama dapat disimpulkan bahwa paling sedikit salah satu variabel, K atau L, sama dengan 1 (atau keduanya bersama-sama); jadi mari kita pertimbangkan tiga kasus

3) jika K = 1 dan L = 0, maka persamaan kedua terpenuhi untuk sembarang M dan N; karena ada 4 kombinasi dua variabel Boolean (00, 01, 10 dan 11), kita mempunyai 4 solusi berbeda

4) jika K = 1 dan L = 1, maka persamaan kedua berlaku untuk M · N = 0; ada 3 kombinasi seperti itu (00, 01 dan 10), kami memiliki 3 solusi lagi

5) jika K = 0, maka L = 1 (dari persamaan pertama); dalam hal ini persamaan kedua terpenuhi jika M · N = 0; ada 3 kombinasi seperti itu (00, 01 dan 10), kami memiliki 3 solusi lagi

6) total kita mendapatkan 4 + 3 + 3 = 10 solusi.

Jawaban: 10

Berapa banyak solusi berbeda yang dimiliki persamaan tersebut?

(K ∧ L) ∨ (M ∧ N) = 1

Penjelasan.

Pernyataan tersebut benar dalam tiga kasus, ketika (K ∧ L) dan (M ∧ N) masing-masing sama dengan 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N sama dengan 1, dan K dan L adalah bilangan apa pun kecuali 1 secara bersamaan. Jadi, ada 3 penyelesaian.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 solusi.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 solusi.

Jawaban: 7.

Jawaban: 7

Berapa banyak solusi berbeda yang dimiliki persamaan tersebut?

(X ∧ Y ∨ Z) ​​​​→ (Z ∨ P) = 0

dimana X, Y, Z, P adalah variabel logika? Jawabannya tidak perlu mencantumkan semua rangkaian nilai berbeda yang dianut oleh kesetaraan ini. Sebagai jawabannya, Anda hanya perlu menunjukkan jumlah set tersebut.

Penjelasan.

(X ∧ Y ∨ Z) ​​​​→ (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ​​​​∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Logis OR salah hanya dalam satu kasus: ketika kedua ekspresi salah.

Karena itu,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; kamu = 1.

Oleh karena itu, hanya ada satu solusi untuk persamaan tersebut.

Jawaban 1

Berapa banyak solusi berbeda yang dimiliki persamaan tersebut?

(K ∨ L) ∧ (M ∨ N) = 1

dimana K, L, M, N adalah variabel logika? Jawabannya tidak perlu mencantumkan semua himpunan nilai K, L, M, dan N yang berbeda yang memiliki persamaan ini. Sebagai jawabannya, Anda hanya perlu menunjukkan jumlah set tersebut.

Penjelasan.

Logis Dan hanya benar dalam satu kasus: ketika semua ekspresi benar.

K ∨ L = 1, M ∨ N = 1.

Setiap persamaan memberikan 3 solusi.

Perhatikan persamaan A ∧ B = 1, jika A dan B masing-masing bernilai benar dalam tiga kasus, maka total persamaan tersebut mempunyai 9 penyelesaian.

Oleh karena itu jawabannya adalah 9.

Jawaban: 9

Berapa banyak solusi berbeda yang dimiliki persamaan tersebut?

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

dimana A, B, C, D adalah variabel logika?

Jawabannya tidak perlu mencantumkan semua himpunan nilai A, B, C, D yang memiliki persamaan ini. Sebagai jawabannya, Anda perlu menunjukkan jumlah set tersebut.

Penjelasan.

Logikanya "ATAU" benar jika setidaknya salah satu pernyataannya benar.

(D ∧ ¬D)= 0 untuk sembarang D.

Karena itu,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, yang menghasilkan 3 kemungkinan solusi untuk setiap D.

(D ∧ ¬ D)= 0 untuk sembarang D, sehingga menghasilkan dua solusi (untuk D = 1, D = 0).

Oleh karena itu: penyelesaian total 2*3 = 6.

Total 6 solusi.

Jawaban: 6

Berapa banyak solusi berbeda yang dimiliki persamaan tersebut?

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

dimana K, L, M, N adalah variabel logika? Jawabannya tidak perlu mencantumkan semua himpunan nilai K, L, M, dan N yang berbeda yang memiliki persamaan ini. Sebagai jawabannya, Anda hanya perlu menunjukkan jumlah set tersebut.

Penjelasan.

Mari kita terapkan negasi pada kedua ruas persamaan:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Logis OR benar dalam tiga kasus.

Pilihan 1.

K ∧ L ∧ M = 1, maka K, L, M = 1, dan ¬L ∧ M ∧ N = 0. N bersifat arbitrer, yaitu 2 solusi.

Pilihan 2.

¬L ∧ M ∧ N = 1, maka N, M = 1; L = 0, K sembarang, yaitu 2 solusi.

Oleh karena itu jawabannya adalah 4.

Jawaban: 4

A, B, dan C adalah bilangan bulat yang pernyataannya benar

¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).

Berapakah nilai B jika A = 45 dan C = 43?

Penjelasan.

1) ¬(A = B); (A > B)→(B > C); (B > SEBUAH)→(C > B);

2) pernyataan-pernyataan sederhana ini dihubungkan dengan operasi (DAN, konjungsi), yaitu harus dijalankan secara bersamaan;

3) dari ¬(A = B)=1 maka A B;

4) misalkan A > B, maka dari kondisi kedua diperoleh 1→(B > C)=1; ungkapan ini benar jika dan hanya jika B > C = 1;

5) oleh karena itu kita mempunyai A > B > C, hanya angka 44 yang sesuai dengan kondisi ini;

6) untuk berjaga-jaga, mari kita periksa juga opsi A 0 →(B > C)=1;

ungkapan ini berlaku untuk semua B; sekarang lihat kondisi ketiga yang kita dapatkan

ungkapan ini benar jika dan hanya jika C > B, dan di sini kita mempunyai kontradiksi, karena tidak ada bilangan B yang C > B > A.

Jawaban: 44.

Jawaban: 44

Buatlah tabel kebenaran untuk fungsi logis

X = (A ↔ B) ∨ ¬(A → (B ∨ C))

dimana kolom nilai argumen A merupakan representasi biner dari angka 27, kolom nilai argumen B adalah angka 77, kolom nilai argumen C adalah angka 120. Angka tersebut pada kolom tersebut ditulis dari atas ke bawah dari yang paling signifikan hingga yang paling tidak signifikan (termasuk himpunan nol). Ubah representasi biner yang dihasilkan dari nilai fungsi X menjadi sistem desimal Perhitungan.

Penjelasan.

Mari kita tulis persamaannya menggunakan notasi operasi yang lebih sederhana:

1) ini adalah ekspresi dengan tiga variabel, sehingga akan ada garis pada tabel kebenaran; oleh karena itu, representasi biner dari angka-angka yang digunakan untuk membuat kolom tabel A, B dan C harus terdiri dari 8 digit

2) ubah bilangan 27, 77 dan 120 ke dalam sistem biner, segera jumlahkan hingga 8 digit angka nol di awal bilangan

3) kecil kemungkinan Anda dapat langsung menuliskan nilai fungsi X untuk setiap kombinasi, sehingga akan lebih mudah untuk menambahkan kolom tambahan ke tabel untuk perhitungan hasil antara(lihat tabel di bawah)

X0

A	DI DALAM	DENGAN
0	0
0	1	1
0	0	1
1	0	1
1	1	1
0	1	0
1	0	0
1	1	0

4) isi kolom tabel:

A	DI DALAM	DENGAN					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

nilainya 1 hanya pada garis yang A = B

nilainya adalah 1 pada baris yang B atau C = 1

nilainya 0 hanya pada garis yang A = 1 dan B + C = 0

nilainya kebalikan dari kolom sebelumnya (0 diganti 1, dan 1 diganti 0)

hasil X (kolom terakhir) adalah penjumlahan logis dari dua kolom dan

5) untuk mendapatkan jawabannya, tuliskan bit-bit dari kolom X dari atas ke bawah:

6) ubah bilangan ini ke sistem desimal:

Jawaban: 171

Berapakah bilangan bulat X terbesar yang pernyataan (10 (X+1)·(X+2)) benar?

Penjelasan.

Persamaannya adalah operasi implikasi antara dua relasi:

1) Tentu saja, di sini Anda dapat menerapkan metode yang sama seperti pada contoh 2208, tetapi Anda harus menyelesaikannya persamaan kuadrat(Saya tidak mau…);

2) Perhatikan bahwa dengan syarat kita hanya tertarik pada bilangan bulat, jadi kita dapat mencoba mengubah ekspresi aslinya, mendapatkan pernyataan yang setara ( nilai yang tepat kami sama sekali tidak tertarik pada akar!);

3) Pertimbangkan pertidaksamaan: tentu saja, ini bisa berupa bilangan positif atau negatif;

4) Sangat mudah untuk memeriksa bahwa di domain pernyataan tersebut benar untuk semua bilangan bulat , dan di domain - untuk semua bilangan bulat (agar tidak bingung, akan lebih mudah menggunakan pertidaksamaan tidak ketat, dan , daripada Dan );

5) Oleh karena itu, untuk bilangan bulat dapat diganti dengan ekspresi yang setara

6) wilayah kebenaran suatu ekspresi adalah gabungan dua interval tak terhingga;

7) Sekarang perhatikan pertidaksamaan kedua: jelas bahwa pertidaksamaan tersebut juga dapat berupa bilangan positif atau negatif;

8) Di domain pernyataan tersebut benar untuk semua bilangan bulat , dan di domain - untuk semua bilangan bulat , oleh karena itu untuk bilangan bulat dapat diganti dengan ekspresi yang setara

9) daerah kebenaran ungkapan adalah interval tertutup;

10) Ekspresi yang diberikan berlaku di semua tempat, kecuali area di mana dan ;

11) Perlu diketahui bahwa nilainya sudah tidak sesuai lagi, karena disana dan , yaitu implikasinya memberikan 0;

12) Saat mensubstitusi 2, (10 (2+1) · (2+2)), atau 0 → 0 yang memenuhi kondisi.

Jadi jawabannya adalah 2.

Jawaban: 2

Berapakah bilangan bulat X terbesar yang pernyataannya benar

(50 (X+1)·(X+1))?

Penjelasan.

Mari kita terapkan transformasi implikasi dan transformasi ekspresi:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Logis OR benar jika setidaknya satu pernyataan logis benar. Setelah menyelesaikan kedua pertidaksamaan dan dengan mempertimbangkan bahwa kita melihat bahwa bilangan bulat terbesar yang memenuhi setidaknya salah satu dari pertidaksamaan tersebut adalah 7 (ditunjukkan dengan warna kuning pada gambar keputusan positif pertidaksamaan kedua, biru - yang pertama).

Jawaban: 7

Tentukan nilai variabel K, L, M, N, di mana ekspresi logikanya

(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)

PALSU. Tulis jawabannya sebagai rangkaian 4 karakter: nilai variabel K, L, M dan N (dalam urutan itu). Jadi, misalnya, baris 1101 berhubungan dengan fakta bahwa K=1, L=1, M=0, N=1.

Penjelasan.

Tugas duplikat 3584.

Jawaban: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Penjelasan.

Mari kita terapkan transformasi implikasinya:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Mari terapkan negasi pada kedua ruas persamaan:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Mari bertransformasi:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Oleh karena itu, M = 0, N = 0, sekarang perhatikan (¬K ∧ L ∨ M ∧ L):

dari kenyataan bahwa M = 0, N = 0 maka M ∧ L = 0, maka ¬K ∧ L = 1, yaitu K = 0, L = 1.

Jawaban: 0100

Tentukan nilai variabel K, L, M, N di mana ekspresi logikanya

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

PALSU. Tulis jawaban Anda sebagai rangkaian empat karakter: nilai variabel K, L, M dan N (dalam urutan itu). Jadi, misalnya, baris 1101 berhubungan dengan fakta bahwa K=1, L=1, M=0, N=1.

Penjelasan.

Mari kita tulis persamaannya menggunakan notasi operasi yang lebih sederhana (kondisi "ekspresinya salah" berarti sama dengan logika nol):

1) dari rumusan kondisi dapat disimpulkan bahwa ekspresi harus salah hanya untuk satu himpunan variabel

2) dari tabel kebenaran operasi “implikasi” maka ungkapan ini salah jika dan hanya jika pada saat yang sama

3) persamaan pertama (hasil kali logika sama dengan 1) terpenuhi jika dan hanya jika dan ; dari sini berikut ini (jumlah logisnya sama dengan nol), yang hanya dapat terjadi jika ; Jadi, kita telah mendefinisikan tiga variabel

4) dari kondisi kedua, , untuk dan kita peroleh .

Menggandakan tugas

Jawaban: 1000

Tentukan nilai variabel logika P, Q, S, T, di mana ekspresi logikanya

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) salah.

Tulis jawabannya sebagai rangkaian empat karakter: nilai variabel P, Q, S, T (dalam urutan itu).

Penjelasan.

(1) (P ∨ ¬Q) = 0

(2) (Q → (S ∨ T)) = 0

(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Mari kita terapkan transformasi implikasinya:

¬Q ∨ S ∨ T = 0 => S = 0, T = 0.

Jawaban: 0100

Tentukan nilai variabel K, L, M, N di mana ekspresi logikanya

(K → M) ∨ (L ∧ K) ∨ ¬N

PALSU. Tulis jawaban Anda sebagai rangkaian empat karakter: nilai variabel K, L, M dan N (dalam urutan itu). Jadi, misalnya, baris 1101 berhubungan dengan fakta bahwa K=1, L=1, M=0, N=1.

Penjelasan.

Logika OR salah jika dan hanya jika kedua pernyataan salah.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Mari kita terapkan transformasi implikasi untuk ekspresi pertama:

¬K ∨ M = 0 => K = 1, M = 0.

Perhatikan ekspresi kedua:

(L ∧ K) ∨ ¬N = 0 (lihat hasil ekspresi pertama) => L ∨ ¬N = 0 => L = 0, N = 1.

Jawaban: 1001.

Jawaban: 1001

Tentukan nilai variabel K, L, M, N di mana ekspresi logikanya

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

BENAR. Tulis jawaban Anda sebagai rangkaian empat karakter: nilai variabel K, L, M dan N (dalam urutan itu). Jadi, misalnya, baris 1101 berhubungan dengan fakta bahwa K=1, L=1, M=0, N=1.

Penjelasan.

Logikanya "DAN" benar jika dan hanya jika kedua pernyataan benar.

1) (K → M) = 1 Terapkan transformasi implikasi: ¬K ∨ M = 1

2) (K → ¬M) = 1 Terapkan transformasi implikasi: ¬K ∨ ¬M = 1

Oleh karena itu K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Terapkan transformasi implikasi: K ∨ (M ∧ ¬L ∧ N) = 1 dari fakta bahwa K = 0 kita peroleh:

M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.

Jawaban: 0011

Diketahui bahwa untuk bilangan bulat X, Y dan Z pernyataan berikut ini benar:

(Z Berapakah Z jika X=25 dan Y=48?

Penjelasan.

Setelah mensubstitusi angka-angka tersebut, diperoleh Z = 47.

Harap dicatat bahwa pernyataan kompleks ini terdiri dari tiga pernyataan sederhana

1) (Z 2) pernyataan sederhana ini dihubungkan dengan operasi (DAN, konjungsi), yaitu harus dijalankan secara bersamaan.

3) dari ¬(Z+1 24, dan dari ¬(Z+1 47.

4) dari (Z Z Jawaban: 47.

Jawaban: 47

A, B, dan C adalah bilangan bulat yang pernyataan berikut ini benar:

(C Berapakah nilai C jika A=45 dan B=18?

Penjelasan.

Logikanya "DAN" benar jika dan hanya jika kedua pernyataan benar.

Mari kita substitusikan angka-angka tersebut ke dalam ekspresi:

1) (C (C 2) ¬(C+1, C ≥ 44.

3) ¬(C+1, C ≥ 17.

Dari 2) dan 1) maka C

Jawaban: 44

¬(A = B) ∧ ((BA)) ∧ ((A 2C))

Berapakah nilai A jika C = 8 dan B = 18?

Penjelasan.

Logikanya "DAN" benar jika dan hanya jika kedua pernyataan benar.

1) ¬(A = B) = 1, yaitu A ≠ 18 = 1.

2) ((B A)) Terapkan transformasi implikasi: (18 > A) ∨ (16 > A) = 1

3) (A 2C) Terapkan transformasi implikasi: (A > 18) ∨ (A > 16) = 1

Dari 2) dan 3) maka (18 > A) dan (A > 16), karena jika tidak maka timbul kontradiksi: A = 17.

Jawaban: 17

A, B, dan C adalah bilangan bulat yang pernyataannya benar

¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))

Berapakah nilai B jika A = 45 dan C = 18?

Penjelasan.

Logikanya "DAN" benar hanya jika semua pernyataan benar.

Materi ini berisi presentasi yang menyajikan metode penyelesaian persamaan logika dan sistem persamaan logika pada tugas B15 (No. 23, 2015) Ujian Negara Bersatu bidang ilmu komputer. Diketahui bahwa tugas ini merupakan salah satu tugas tersulit di antara tugas-tugas Unified State Examination. Presentasi tersebut semoga bermanfaat ketika mengajarkan pelajaran dengan topik "Logika" di kelas khusus, serta dalam persiapan untuk lulus Ujian Negara Bersatu.

Unduh:

Pratinjau:

Untuk menggunakan pratinjau presentasi, buatlah akun sendiri ( akun) Google dan masuk: https://accounts.google.com

Keterangan slide:

Solusi tugas B15 (sistem persamaan logika) Vishnevskaya M.P., MAOU “Gymnasium No. 3” 18 November 2013, Saratov

Tugas B15 adalah salah satu tugas tersulit dalam Ujian Negara Bersatu dalam ilmu komputer!!! Keterampilan berikut diuji: mengubah ekspresi yang mengandung variabel logis; jelaskan pada bahasa alami himpunan nilai variabel logika yang himpunan variabel logikanya benar; hitung jumlah himpunan biner yang memenuhi kondisi tertentu. Hal yang paling sulit adalah karena... TIDAK aturan formal Cara melakukan ini memerlukan beberapa tebakan.

Apa yang tidak dapat Anda lakukan tanpanya!

Apa yang tidak dapat Anda lakukan tanpanya!

Konjungsi simbol: A /\ B , A  B , AB , A &B, A dan B disjungsi: A \ / B , A + B , A | Negasi B , A atau B:  A , A, bukan A ekivalensi: A  B, A  B, A  B eksklusif “atau”: A  B , A xor B

Metode penggantian variabel Berapa banyak himpunan nilai variabel logis x1, x2, ..., x9, x10 yang memenuhi semua kondisi berikut: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ ​​(¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ ​​​​(¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ ​​​​(¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ ​​​​(¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Jawabannya tidak perlu mencantumkan semua himpunan x1, x2, …, x9, x10 yang berbeda sistem kesetaraan ini berlaku. Sebagai jawabannya, Anda harus menunjukkan jumlah set tersebut (versi demo 2012)

Langkah Penyelesaian 1. Sederhanakan dengan mengubah variabel t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Setelah disederhanakan: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) // (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Perhatikan salah satu persamaan: (t1 \/ t2) // (¬t1 \/ ¬ t2) =1 Jelasnya, =1 hanya jika salah satu variabelnya adalah 0 dan variabel lainnya adalah 1 . Mari kita gunakan rumus untuk menyatakan operasi XOR melalui konjungsi dan disjungsi: (t1 \/ t2) // (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Langkah 2. Analisis sistem ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т .Ke. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), maka setiap nilai tk berhubungan dengan dua pasang nilai x2k-1 dan x2k, contoh: tk =0 berhubungan dengan dua pasangan - (0 ,1) dan (1, 0) , dan tk =1 – pasangan (0,0) dan (1,1).

Langkah3. Menghitung jumlah solusi. Setiap t mempunyai 2 penyelesaian, banyaknya ts adalah 5. Jadi. untuk variabel t ada 2 5 = 32 solusi. Tetapi untuk setiap t terdapat sepasang solusi x, yaitu. sistem asli memiliki 2*32 = 64 solusi. Jawaban: 64

Metode menghilangkan bagian dari solusi Berapa banyak himpunan nilai variabel logis x1, x2, ..., x5, y1,y2,..., 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; y5→ x5 =1. Jawabannya tidak perlu mencantumkan semua himpunan x1, x2, ..., x5, y 1 ,y2,..., y5 yang dimiliki sistem persamaan ini. Jawabannya harus menunjukkan jumlah himpunan tersebut.

Larutan. Langkah 1. Solusi berurutan persamaan x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 Persamaan pertama merupakan konjungsi beberapa operasi implikasi yang sama dengan 1, yaitu. setiap implikasinya benar. Implikasinya salah hanya dalam satu kasus, ketika 1  0, dalam semua kasus lainnya (0  0, 0  1, 1  1) operasi menghasilkan 1. Mari kita tuliskan ini dalam bentuk tabel:

Langkah 1. Solusi sekuensial persamaan T.o. Diperoleh 6 himpunan solusi untuk x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Dengan alasan yang sama, kita sampai pada kesimpulan bahwa untuk y1, y2, y3, y4, y5 terdapat himpunan solusi yang sama. Karena persamaan ini independen, yaitu mereka tidak mempunyai variabel yang sama, maka penyelesaian sistem persamaan ini (tanpa memperhitungkan persamaan ketiga) adalah 6 * 6 = 36 pasang “X” dan “Y”. Perhatikan persamaan ketiga: y5→ x5 =1 Penyelesaiannya adalah pasangan-pasangan: 0 0 0 1 1 1 Pasangan tersebut bukan penyelesaian: 1 0

Mari kita bandingkan solusi yang diperoleh. Dimana y5 =1, x5=0 tidak cocok. ada 5 pasangan seperti itu. Banyaknya solusi sistem: 36-5= 31. Jawaban: Dibutuhkan 31 Kombinatorik!!!

Metode pemrograman dinamis Berapa banyak solusi berbeda yang dimiliki persamaan logika x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, dimana x 1, x 2, …, x 6 adalah variabel logika? Jawabannya tidak perlu mencantumkan semua kumpulan nilai variabel berbeda yang memiliki persamaan ini. Sebagai jawabannya, Anda perlu menunjukkan jumlah himpunan tersebut.

Solusi Langkah 1. Analisis kondisi Di sebelah kiri persamaan, operasi implikasi ditulis berurutan, prioritasnya sama. Mari kita tulis ulang: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Setiap variabel berikutnya tidak bergantung pada variabel sebelumnya, tetapi pada hasil implikasi sebelumnya!

Langkah 2. Mengungkap suatu pola Mari kita perhatikan implikasi pertama, X 1 → X 2. Tabel kebenaran: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Dari satu 0 kita mendapat 2 satuan, dan dari 1 kita mendapat satu 0 dan satu 1. Hanya ada satu 0 dan tiga 1, ini adalah hasil operasi pertama.

Langkah 2. Mengungkap suatu pola Dengan menghubungkan x 3 dengan hasil operasi pertama, diperoleh: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Dari dua 0 – dua 1, dari masing-masing 1 (ada 3) satu 0 dan satu 1 (3+3)

Langkah 3. Penurunan rumus T.o. anda dapat membuat rumus untuk menghitung banyaknya angka nol N i dan banyaknya angka nol E i untuk persamaan dengan variabel i: ,

Langkah 4. Mengisi tabel Mari kita isi tabel dari kiri ke kanan untuk i = 6, hitung banyaknya angka nol dan satu menggunakan rumus di atas; tabel menunjukkan bagaimana kolom berikutnya dibuat dari kolom sebelumnya: jumlah variabel 1 2 3 4 5 6 Jumlah nol N i 1 1 3 5 11 21 Jumlah variabel E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Jawaban: 43

Metode yang menggunakan penyederhanaan ekspresi logika Berapa banyak solusi berbeda yang dimiliki persamaan tersebut ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 dimana J, K, L, M, N adalah variabel logika? Jawabannya tidak perlu mencantumkan semua himpunan nilai J, K, L, M, dan N yang berbeda yang memiliki persamaan ini. Sebagai jawabannya, Anda perlu menunjukkan jumlah set tersebut.

Solusi Perhatikan bahwa J → K = ¬ J  K Mari kita perkenalkan perubahan variabel: J → K=A, M  N  L =B Mari kita tulis ulang persamaan tersebut dengan memperhitungkan perubahan: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Jelasnya, A  B ketika nilai-nilai yang identik A dan B 6. Perhatikan implikasi terakhir M → J =1 Hal ini mungkin terjadi jika: M=J=0 M=0, J=1 M=J=1

Solusi Karena A  B, maka ketika M=J=0 diperoleh 1 + K=0. Tidak ada solusi. Ketika M=0, J=1 kita mendapatkan 0 + K=0, K=0, dan N dan L adalah sembarang, 4 solusi: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Solusi 10. Ketika M=J=1 kita mendapatkan 0+K=1 *N * L, atau K=N*L, 4 solusi: 11. Total mempunyai 4+4=8 solusi Jawaban: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Sumber informasi: O.B. Bogomolova, D.Yu. Usenkov. B15: tugas baru dan solusi baru // Informatika, No. 6, 2012, hal. 35 – 39. K.Yu. Polandia. Persamaan logika // Informatika, No. 14, 2011, hal. 30-35. http://ege-go.ru/zadania/grb/b15/ , [ Sumber daya elektronik] . http://kpolyakov.narod.ru/school/ege.htm, [Sumber daya elektronik].