Логічна функція F задається виразом. Логіка та справжні набори. Рішення 1 логічна функція f задається виразом x

Каталог завдань.
Кількість програм із обов'язковим етапом

Сортування Основна Спочатку прості Спочатку складні За популярністю Спочатку нові Спочатку старі
Пройти тестування за цими завданнями
Повернутись до каталогу завдань
Версія для друку та копіювання в 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 .

Розбір 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 стовпець).

Давайте спочатку визначимося з тим, що ми маємо завдання:

логічна функція 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).

Джерело завдання: Рішення 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).

Рішення аналогічно рішенню.

№4 Логічна функція F задається виразом

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

Рішення аналогічно рішенню.

№5 Логічна функція F задається виразом

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

Рішення аналогічно рішенню.

№6 Логічна функція F задається виразом

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

Рішення

Логічна функція 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).

Рішення аналогічно рішенню.

№8 Логічна функція F задається виразом

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

Рішення аналогічно рішенню.

№9 Логічна функція F задається виразом

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

Рішення аналогічно рішенню.

№10 Логічна функція F задається виразом

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

Рішення аналогічно рішенню.

№11 Логічна функція F задається виразом

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

Рішення

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

Рішення

Логічна функція 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)).

Рішення

Логічна функція 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 одиниць.