Fungsi logik F diberikan oleh ungkapan. Logik dan set benar. Penyelesaian 1 Fungsi logik f diberikan oleh x

Katalog tugas.
Bilangan program dengan peringkat wajib

Isih Asas Pertama mudah Pertama kompleks Populariti Pertama baru Pertama lama
Ambil ujian untuk tugasan ini
Kembali ke katalog tugas
Versi untuk mencetak dan menyalin dalam MS Word

Pelaku A16 menukar nombor yang ditulis pada skrin.

Penghibur mempunyai tiga pasukan, yang diberi nombor:

1. Tambah 1

2. Tambah 2

3. Darab dengan 2

Yang pertama meningkatkan nombor pada skrin sebanyak 1, yang kedua menambahnya dengan 2, yang ketiga mendarabkannya dengan 2.

Program untuk pelaku A16 ialah urutan arahan.

Berapa banyak program yang ada yang menukar nombor asal 3 kepada nombor 12 dan pada masa yang sama laluan pengiraan program mengandungi nombor 10?

Trajektori pengiraan program ialah urutan hasil daripada pelaksanaan semua arahan program. Sebagai contoh, untuk program 132 dengan nombor awal 7, trajektori akan terdiri daripada nombor 8, 16, 18.

Penyelesaian.

Bilangan program yang diperlukan adalah sama dengan produk bilangan program yang memperoleh nombor 10 daripada nombor 3 dengan bilangan program yang memperoleh nombor 12 daripada nombor 10.

Biarkan R(n) ialah bilangan atur cara yang menukar nombor 3 kepada nombor n, dan P(n) ialah bilangan atur cara yang menukar nombor 10 kepada nombor n.

Untuk semua n > 5 hubungan berikut adalah benar:

1. Jika n tidak boleh dibahagikan dengan 2, maka R(n) = R(n - 1) + R(n - 2), kerana terdapat dua cara untuk mendapatkan n - dengan menambah satu atau menambah dua. Begitu juga P(n) = P(n - 1) + P(n - 2)

2. Jika n boleh dibahagi dengan 2, maka R(n) = R(n - 1) + R(n - 2) + R(n / 2). Begitu juga P(n) = P(n - 1) + P(n - 2) + P(n / 2)

Mari kita hitung secara berurutan nilai R(n):

R(5) = R(4) + R(3) = 1 + 1 = 2

R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4

R(7) = R(6) + R(5) = 4 + 2 = 6

R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11

R(9) = R(8) + R(7) = 11 + 6 = 17

R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30

Sekarang mari kita hitung nilai P(n):

P(11) = P(10) = 1

P(12) = P(11) + P(10) = 2

Oleh itu, bilangan program yang memenuhi syarat masalah ialah 30 · 2 = 60.

Jawapan: 60.

Jawapan: 60

Sumber: Versi demo Peperiksaan Negeri Bersepadu 2017 dalam sains komputer.

1. Tambah 1

2. Tambah 3

Berapa banyak program yang ada, memandangkan nombor awal 1, hasilnya adalah nombor 17 dan pada masa yang sama trajektori pengiraan mengandungi nombor 9? Trajektori pengiraan program ialah urutan hasil daripada pelaksanaan semua arahan program. Sebagai contoh, untuk program 121 dengan nombor awal 7, trajektori akan terdiri daripada nombor 8, 11, 12.

Penyelesaian.

Kami menggunakan kaedah pengaturcaraan dinamik. mari buat dp tatasusunan, dengan dp[i] ialah bilangan cara untuk mendapatkan nombor i menggunakan arahan tersebut.

Asas dinamik:

Formula peralihan:

dp[i]=dp + dp

Ini tidak mengambil kira nilai untuk nombor yang lebih besar daripada 9, yang boleh diperoleh daripada nombor kurang daripada 9 (dengan itu melangkau trajektori 9):

Jawapan: 169.

Jawapan: 169

Sumber: Kerja latihan dalam SAINS KOMPUTER, gred 11 29 November 2016 Pilihan IN10203

Pelaku Mei17 menukar nombor pada skrin.

Pelaku mempunyai dua pasukan, yang diberi nombor:

1. Tambah 1

2. Tambah 3

Perintah pertama meningkatkan nombor pada skrin sebanyak 1, yang kedua meningkatkannya sebanyak 3. Program untuk pelaku Mei17 ialah urutan arahan.

Berapa banyak program yang ada, memandangkan nombor awal 1, hasilnya adalah nombor 15 dan pada masa yang sama laluan pengiraan mengandungi nombor 8? Trajektori pengiraan program ialah urutan hasil daripada pelaksanaan semua arahan program. Sebagai contoh, untuk program 121 dengan nombor awal 7, trajektori akan terdiri daripada nombor 8, 11, 12.

Penyelesaian.

Kami menggunakan kaedah pengaturcaraan dinamik. Mari kita cipta dp tatasusunan, dengan dp[i] ialah bilangan cara untuk mendapatkan nombor i menggunakan arahan tersebut.

Asas dinamik:

Formula peralihan:

dp[i]=dp + dp

Tetapi ini tidak mengambil kira nombor yang lebih besar daripada 8, tetapi kita boleh mendapatkannya daripada nilai kurang daripada 8. Berikut akan menunjukkan nilai dalam sel dp dari 1 hingga 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 .

Analisis tugasan 2 Peperiksaan Negeri Bersepadu 2017 dalam sains komputer daripada projek versi demo. Ini adalah tugasan tahap kesukaran asas. Anggaran masa untuk menyiapkan tugasan ialah 3 minit.

Unsur kandungan yang diuji: keupayaan untuk membina jadual kebenaran dan litar logik. Elemen kandungan yang diuji pada Peperiksaan Negeri Bersepadu: pernyataan, operasi logik, pengkuantiti, kebenaran pernyataan.

Tugasan 2:

Fungsi logik F diberikan oleh ungkapan x /\¬ y /\ (¬ z \/ w).
Rajah menunjukkan serpihan jadual kebenaran fungsi itu F mengandungi Semua F benar.
Tentukan lajur jadual kebenaran fungsi yang mana F setiap pembolehubah sepadan w, x, y, z.

Tulis huruf dalam jawapan anda w, x, y, z dalam susunan lajur yang sepadan muncul (pertama - huruf yang sepadan dengan lajur pertama; kemudian - huruf yang sepadan dengan lajur kedua, dll.) Tulis huruf dalam jawapan berturut-turut, tidak perlu meletakkan apa-apa pemisah antara huruf.

Contoh. Jika fungsi itu diberikan oleh ungkapan ¬ x \/ y, bergantung kepada dua pembolehubah: x Dan y, dan serpihan jadual kebenarannya telah diberikan, mengandungi Semua set hujah yang fungsinya F benar.

Kemudian lajur pertama akan sepadan dengan pembolehubah y, dan lajur kedua ialah pembolehubah x. Jawapannya sepatutnya menulis: yx.

Jawapan: ________

x /\¬ y /\ (¬ z \/ w)

Kata hubung (pendaraban logik) adalah benar jika dan hanya jika semua pernyataan adalah benar. Oleh itu pembolehubah X 1 .

Oleh itu, pembolehubah x sepadan dengan lajur dengan pembolehubah 3.

Pembolehubah ¬y lajur yang mengandungi nilai mesti sepadan 0 .

Pecah (tambahan logik) dua pernyataan adalah benar jika dan hanya jika sekurang-kurangnya satu pernyataan adalah benar.
Disjunction ¬z\/w dalam baris ini akan menjadi benar hanya jika z=0, w=1.

Oleh itu, pembolehubah ¬z sepadan dengan lajur dengan pembolehubah 1 (1 lajur), pembolehubah w sepadan dengan lajur dengan pembolehubah 4 (lajur 4).

Mari kita tentukan dahulu apa yang kita ada dalam masalah:

fungsi logik F yang ditakrifkan oleh beberapa ungkapan. Unsur-unsur jadual kebenaran fungsi ini juga dikemukakan dalam masalah dalam bentuk jadual. Oleh itu, apabila menggantikan nilai tertentu x, y, z daripada jadual ke dalam ungkapan, hasilnya harus bertepatan dengan yang diberikan dalam jadual (lihat penjelasan di bawah).
Pembolehubah x, y, z dan tiga lajur yang sepadan dengannya. Selain itu, dalam masalah ini kita tidak tahu lajur mana yang sepadan dengan pembolehubah mana. Iaitu, dalam lajur Pembolehubah. 1 boleh sama ada x, y atau z.
Kami diminta untuk menentukan lajur yang sepadan dengan pembolehubah mana.

Mari kita lihat satu contoh.

Penyelesaian

Mari kembali sekarang kepada penyelesaian. Mari kita lihat dengan lebih dekat formula: \((\neg z) \baji x \vee x\baji y\)
Ia mempunyai dua binaan dengan kata hubung yang disambungkan oleh pencapai. Seperti yang diketahui, selalunya disjungsi adalah benar (untuk ini sudah cukup bahawa salah satu istilah adalah benar).
Mari kita lihat dengan teliti pada baris di mana ungkapan F adalah palsu.
Baris pertama tidak menarik bagi kami, kerana ia tidak menentukan di mana (semua nilai adalah sama).
Mari kita pertimbangkan baris terakhir, ia mengandungi kebanyakan 1, tetapi hasilnya ialah 0.
Bolehkah z berada di lajur ketiga? Tidak, kerana dalam kes ini akan ada 1 di mana-mana dalam formula, dan, oleh itu, hasilnya akan sama dengan 1, tetapi mengikut jadual kebenaran, nilai F dalam baris ini ialah 0. Oleh itu, z tidak boleh Pembolehubah . 3.
Begitu juga, untuk baris sebelumnya kita mempunyai bahawa z tidak boleh Pembolehubah. 2.
Oleh itu, z ialah Pembolehubah. 1.
Mengetahui bahawa z berada dalam lajur pertama, pertimbangkan baris ketiga. Bolehkah x berada di lajur kedua? Mari kita gantikan nilai:
\((\neg z) \wedge x \vee x\wedge y = \\ = (\neg 0) \wedge 1 \vee 1\wedge 0 = \\ = 1 \wedge 1 \vee 0 = \\ = 1 \vee 0 = 1\)
Walau bagaimanapun, mengikut jadual kebenaran, hasilnya mestilah 0.
Oleh itu, x tidak boleh Per. 2.
Oleh itu, x ialah Pembolehubah. 3.
Oleh itu, dengan kaedah penyingkiran, y ialah Pembolehubah. 2.
Oleh itu, jawapannya adalah seperti berikut: zyx (z - Variable 1, y - Variable 2, x - Variable 3).

Sumber pekerjaan: Penyelesaian 2437. Peperiksaan Negeri Bersepadu 2017. Sains Komputer. V.R. Leschiner. 10 pilihan.

Tugasan 2. Fungsi logik F diberikan oleh ungkapan . Tentukan lajur jadual kebenaran bagi fungsi F yang manakah sepadan dengan setiap pembolehubah x, y, z.

Dalam jawapan anda, tulis huruf x, y, z dalam susunan lajur yang sepadan muncul (pertama - huruf sepadan dengan lajur pertama, kemudian - huruf sepadan dengan lajur ke-2, kemudian - huruf sepadan dengan lajur ke-3 kolum) . Tulis huruf dalam jawapan berturut-turut; tidak perlu meletakkan sebarang pemisah antara huruf.

Penyelesaian.

Mari kita tulis semula ungkapan untuk F dengan mengambil kira keutamaan operasi penafian, kata hubung dan pemecahan:

Pertimbangkan baris ke-4 jadual (1,1,0)=0. Daripada ini kita dapat melihat bahawa tempat ketiga mestilah sama ada pembolehubah y atau pembolehubah z, jika tidak kurungan kedua akan mengandungi 1, yang akan membawa kepada nilai F=1. Sekarang pertimbangkan baris ke-5 jadual (0,0,1)=1. Oleh kerana x mesti berada di tempat pertama atau kedua, kurungan pertama akan memberikan 1 hanya apabila y berada di tempat ke-3. Memandangkan kurungan kedua sentiasa sama dengan 0, maka F=1 diperoleh kerana 1 dalam kurungan pertama. Oleh itu, kami mendapati bahawa y berada di tempat ke-3. Akhir sekali, pertimbangkan baris ke-7 jadual (1,0,1)=0. Di sini y=1 dan untuk F=0 adalah perlu untuk mempunyai z=0 dan x=1, oleh itu, x berada di tempat pertama, dan z berada di tempat kedua.

№1

(x /\ y/\z/\¬w)\/ (x /\ y/\¬z/\¬w)\/ (x /\¬ y/\¬z/\¬w).

Penyelesaian

x /\ y/\z/\¬w – x=1, y=1, z=1, w=0;
x /\ y/\¬z/\¬w – x=1, y=1, z=0, w=0;
x /\¬y/\¬z/\¬w – x=1, y=0, z=0, w=0.
Hasilnya, kami mendapat 6 unit.
Jawapan: 6.

№2 Fungsi logik F diberikan oleh ungkapan

(¬x /\ y/\¬z/\w)\/ (x /\ y/\z/\¬w)\/ (x /\¬ y/\¬z/\w).