Логічна функція F задається виразом
Каталог завдань.
Кількість програм із обов'язковим етапом
Пройти тестування за цими завданнями
Повернутись до каталогу завдань
Версія для друку та копіювання в MS Word
Виконавець А16 перетворює число записане на екрані.
Виконавець має три команди, яким присвоєно номери:
1. Додати 1
2. Додати 2
3. Помножити на 2
Перша з них збільшує число на екрані на 1, друга збільшує його на 2, третя збільшує його на 2.
Програма для виконавця А16 – це послідовність команд.
Скільки існує таких програм, які вихідне число 3 перетворять на число 12 і при цьому траєкторія обчислень програми містить число 10?
Траєкторія обчислень програми – це послідовність результатів виконання всіх команд програми. Наприклад, для програми 132 при вихідному числі 7 траєкторія складатиметься з чисел 8, 16, 18.
Рішення.
Кількість програм, що шукається, дорівнює добутку кількості програм, що отримують з числа 3 число 10, на кількість програм, що отримують з числа 10 число 12.
Нехай R(n) - кількість програм, які число 3 перетворять на число n, а P(n) - кількість програм, які число 10 перетворять на число n.
Для всіх n > 5 вірні такі співвідношення:
1. Якщо n не ділиться на 2, тоді R(n) = R(n - 1) + R(n - 2), оскільки існує два способи отримання n - додаванням одиниці або додаванням двійки. Аналогічно P(n) = P(n – 1) + P(n – 2)
2. Якщо n ділиться на 2, то R(n) = R(n - 1) + R(n - 2) + R(n / 2). Аналогічно P(n) = P(n - 1) + P(n - 2) + P(n/2)
Послідовно обчислимо значення 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
Тепер обчислимо значення P(n):
P(11) = P(10) = 1
P(12) = P(11) + P(10) = 2
Таким чином, кількість програм, що задовольняють умові задачі, дорівнює 30 · 2 = 60.
Відповідь: 60.
Відповідь: 60
Джерело: Демонстраційна версія ЄДІ-2017 з інформатики.
1. Додати 1
2. Додати 3
Скільки існує програм, для яких при вихідному числі 1 результатом є число 17 і траєкторія обчислень містить число 9? Траєкторія обчислень програми – це послідовність результатів виконання всіх команд програми. Наприклад, для програми 121 при вихідному числі 7 траєкторія складатиметься з чисел 8, 11, 12.
Рішення.
Використовуємо метод динамічного програмування. заведемо масив dp, де dp[i] - кількість способів отримати число i з допомогою таких команд.
База динаміки:
Формула переходу:
dp [i] = dp + dp
При цьому не враховуються значення чисел більше 9, які можна отримати з чисел менше 9 (перескочивши тим самим траєкторію 9):
Відповідь: 169.
Відповідь: 169
Джерело: Тренувальна робота з ІНФОРМАТИКИ 11 клас 29 листопада 2016 року Варіант ІН10203
Виконавець Май17 перетворює число на екрані.
Виконавець має дві команди, яким присвоєно номери:
1. Додати 1
2. Додати 3
Перша команда збільшує число на екрані на 1, друга збільшує його на 3. Програма для виконавця Май17 – це послідовність команд.
Скільки існує програм, для яких при вихідному числі 1 результатом є число 15 і траєкторія обчислень містить число 8? Траєкторія обчислень програми – це послідовність результатів виконання всіх команд програми. Наприклад, для програми 121 при вихідному числі 7 траєкторія складатиметься з чисел 8, 11, 12.
Рішення.
Використовуємо метод динамічного програмування. Заведемо масив dp де dp[i] - кількість способів отримати число i за допомогою таких команд.
База динаміки:
Формула переходу:
dp [i] = dp + dp
Але при цьому не враховуються такі числа, які більше 8, але в них ми можемо дістатися зі значення менше 8. Далі буде наведено значення в осередках dp від 1 до 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 .
Джерело завдання: Рішення 2437. ЄДІ 2017. Інформатика. В.Р. Ліщинер. 10 варіантів.
Завдання 2.Логічна функція F задається виразом. Визначте, якому стовпцю таблиці істинності функції F відповідає кожна зі змінних x, y, z.
У відповіді напишіть літери x, y, z у тому порядку, в якому йдуть відповідні їм стовпці (спочатку - літера, що відповідає 1-му стовпцю, потім - літера, що відповідає 2-му стовпцю, потім - літера, що відповідає 3-му стовпцю) . Літери у відповіді пишіть поспіль, жодних роздільників між літерами ставити не потрібно.
Рішення.
Перепишемо вираз для F з урахуванням пріоритетів операцій заперечення, кон'юнкції та диз'юнкції:
.
Розглянемо 4-ту строчку таблиці (1,1,0)=0. Звідси видно, що у третьому місці має стояти або змінна y чи змінна z, інакше у другій дужці вийде 1, що призведе до значення F=1. Тепер розглянемо 5-й рядок таблиці (0,0,1) = 1. Так як на першому або другому місці повинна стояти x, то перша дужка дасть 1 тільки тоді, коли y стоятиме на 3-му місці. Враховуючи, що друга дужка завжди дорівнює 0, F=1 виходить завдяки 1 в першій дужці. Отже, отримали, що у 3-му місці стоїть y. Нарешті, розглянемо 7-му рядок таблиці (1,0,1)=0. Тут y = 1 і щоб F = 0 необхідно z = 0 і x = 1, отже, x стоїть на 1-му місці, а z - на другому.
№1
(x / y / z / w) / (x / y y / z / w) / (x / y y / z / w).
Рішення
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 y / z / w - x = 1, y = 0, z = 0, w = 0.
У результаті одержуємо 6 одиниць.
Відповідь:
6.
№2 Логічна функція F задається виразом
(x / y / z / w) / (x / y / z / w) / (x / y y / z / w).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення аналогічно рішенню.
№3 Логічна функція F задається виразом
(x /\ y/z/w) (x / y/z/w) / (x / y/z/w).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення аналогічно рішенню.
№4 Логічна функція F задається виразом
(¬x /\ ¬y/\z/\w)/ (¬x /\ ¬y/\z/w)\/ (¬x /\ y/\ z/w).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення аналогічно рішенню.
№5 Логічна функція F задається виразом
(¬x /\ y/z/w) / (x / y y / z / w) / (x / y y / z / w).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення аналогічно рішенню.
№6 Логічна функція F задається виразом
(x / \ y / w) / (x / y y / z / w).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення
Логічна функція F – істина тога, коли істинно хоча б один вираз у дужках. Оскільки всі змінні в них з'єднані кон'юнкцією, то кожен член повинен бути істинним. Випишемо справжні набори кожної диз'юнкції.
x /\ y/w - (x = 1, y = 1, z = 1, w = 0) і (x = 1, y = 1, z = 0, w = 0);
x / y y / z / w - x = 1, y = 1, z = 0, w = 0.
У результаті одержуємо 6 одиниць.
№7 Логічна функція F задається виразом
(x /\ y/\z/w) / (x / z/w).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення аналогічно рішенню.
№8 Логічна функція F задається виразом
(¬x /\ ¬y/\z/w)\/ (x /z/w).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення аналогічно рішенню.
№9 Логічна функція F задається виразом
(y /\ ¬z /\ ¬w) \/ (¬x /\ ¬y/\z/w).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення аналогічно рішенню.
№10 Логічна функція F задається виразом
(x /\ y /\ ¬z) \/ (¬x /\ ¬y/\z).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення аналогічно рішенню.
№11 Логічна функція F задається виразом
¬((¬w/\x) → (y /\ z)) \/ ¬((x /\ y)→ (¬z/w)).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення
¬((¬w/\x) → (y /\ z)) – (x=1, y=1, z=0, w=0) та (x=1, y=0, z=1, w =0);
¬((x / y y)→ (z/w)) – (x=1, y=0, z=1, w=1).
У результаті одержуємо 5 одиниць.
№12 Логічна функція F задається виразом
¬((¬x\/¬y) → (z \/ w)) \/ ¬((x \/ y)→ (z\/¬w)).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення
Логічна функція F – істина тога, коли істинно хоча б один вираз у дужках. Оскільки всі змінні в них імплікацією, то умова її хибності дає істинність дужок. Наслідуючи приклад, випишемо справжні набори для кожної дужки.
¬((¬x\/¬y) → (z \/w)) – (x=1, y=0, z=0, w=0) і (x=0, y=1, z=0, w=0);
¬((x / y y)→ (z/w)) – (x=1, y=0, z=0, w=0).
У результаті одержуємо 3 одиниць.
№13 Логічна функція F задається виразом
¬(¬(x\/y) → (¬z/ w)) \/ ¬(¬(x /\ y)→ (z/w)).
Степан виписав усі набори змінних, котрим цей вираз істинний. Скільки одиниць написав Степан? У відповіді запишіть лише ціле число – кількість одиниць.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x та y. Це вираз істинно для трьох наборів: (0, 0), (0, 1) та (1, 1). Степан написав 3 одиниці.
Рішення
Логічна функція F – істина тога, коли істинно хоча б один вираз у дужках. Оскільки всі змінні в них імплікацією, то умова її хибності дає істинність дужок. Наслідуючи приклад, випишемо справжні набори для кожної дужки.
¬(¬(x/y) → (¬z/ w)) – (x=0, y=0, z=1, w=0);
¬(¬(x /\ y)→ (z/w)) – (x=1, y=0, z=0, w=1), (x=0, y=1, z=0, w=1) та
(x = 0, y = 0, z = 0, w = 1).
У результаті одержуємо 6 одиниць.
Давайте спочатку визначимося з тим, що ми маємо завдання:
- логічна функція F, задана деяким виразом. Елементи таблиці істинності цієї функції також представлені задачі у вигляді таблиці. Таким чином, при підстановці конкретних значень x, y, z з таблиці вираз результат повинен збігтися з тим, який дано в таблиці (див. пояснення нижче).
- Змінні x, y, z та три стовпці, які їм відповідають. При цьому ми в цьому задачі не знаємо, який стовпець який змінній відповідає. Тобто в стовпці Перем. 1 може бути як x, так і y чи z.
- Нас просять якраз визначити, який стовпець якійсь змінній відповідає.
Розглянемо приклад.
Рішення
- Повернемося тепер до вирішення. Давайте уважно подивимося на формулу: \((\neg z) \wedge x \vee x\wedge y\)
- У ньому є дві конструкції з кон'юнкцією, з'єднані диз'юнкцією. Як відомо, найчастіше диз'юнкція істинна (для цього достатньо, щоб один із доданків був істинним).
- Давайте розглянемо тоді уважно рядки, де вираз F - хибно.
- Перший рядок нам нецікавий, тому що в ньому не визначити, де що (всі значення однакові).
- Розглянемо тоді передостанній рядок, у ньому найбільше 1, але результат дорівнює 0.
- Чи може z бути у третьому стовпці? Ні, тому що в цьому випадку у формулі будуть скрізь 1, а, отже, і результат дорівнюватиме 1, але згідно з таблицею істинності значення F в цьому рядку дорівнює 0. Отже, z не може бути Перем. 3.
- Аналогічно для попереднього рядка маємо, що z не може бути Перем. 2.
- Отже, z – це Перем. 1.
- Знаючи, що z — у першому стовпці, розглянемо третій рядок. Чи може x бути у другому стовпці? Підставимо значення:
\((\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\) - Однак, згідно з таблицею істинності, результат повинен дорівнювати 0.
- Отже, х не може бути Перем. 2.
- Отже, x – це Перем. 3.
- Отже, за методом виключення, y – це Перем. 2.
- Таким чином, відповідь звучить наступним чином: zyx (z - Перем. 1, y - Перем. 2, x - Перем. 3).
Розбір 2 завдання ЄДІ 2017 з інформатики з проекту демоверсії. Це завдання базового рівня складності. Орієнтовний час виконання завдання 3 хвилини.
Перевірювані елементи змісту: вміння будувати таблиці істинності та логічні схеми. Елементи змісту, що перевіряються на ЄДІ: висловлювання, логічні операції, квантори, істинність висловлювання.
Завдання 2:
Логічна функція Fзадається виразом x /\¬ y /\ (¬ z \/ w).
На малюнку наведено фрагмент таблиці істинності функції F, що містить Усе Fістинна.
Визначте, якому стовпцю таблиці істинності функції Fвідповідає кожна зі змінних w, x, y, z.
У відповіді напишіть літери w, x, y, zв тому порядку, в якому йдуть відповідні їм стовпці (спочатку – буква, що відповідає першому стовпцю; потім – буква, що відповідає другому стовпцю, і т.д.).
приклад. Якби функція була задана виразом ¬ x \/ y, що залежать від двох змінних: xі y, і було наведено фрагмент її таблиці істинності, що містить Усенабори аргументів, за яких функція Fістинна.
Тоді першому стовпцю відповідала б змінна y, а другому стовпцю – змінна x. У відповіді слід написати: yx.
Відповідь: ________
x /\¬ y /\ (¬ z \/ w)
Кон'юнкція (логічне множення) істинна і тоді, коли істинні всі висловлювання. Отже змінної х 1 .
Таким чином, змінною xвідповідає стовпець зі змінною 3.
Змінною ¬yповинен відповідати той стовпець, у якому стоїть значення 0 .
Диз'юнкція (логічне додавання) двох висловлювань істинна і тоді, коли істинно хоча б одне висловлювання.
Диз'юнкція ¬z \/ wу даному рядку буде дійсна тільки якщо z=0, w=1.
Таким чином, змінною ¬zвідповідає стовпець зі змінною 1 (1 стовпець), змінною wвідповідає стовпець зі змінною 4 (4 стовпець).