Тип 6 демо-теста. Здесь два навыка: посчитать число решений логического уравнения ((A или B) → (C или D)) = 1 и пройти по рекурсивной функции, найдя значение переменной R. Ответ вписывают числом. Разберём обе части.
Часть А. Логические операции и импликация
Логическая переменная принимает всего два значения: 1 (истина) или 0 (ложь). Основные операции: И (конъюнкция, ∧) истинна, только когда истинны оба; ИЛИ (дизъюнкция, ∨) истинна, когда истинен хотя бы один; НЕ (отрицание) переворачивает значение. Отдельно стоит импликация «→» (следование, «если …, то …») — её и спрашивают в демо.
Главное про импликацию A → B: она ложна в единственном случае — когда из истины следует ложь (A = 1, B = 0). Во всех остальных случаях она истинна. Это стоит просто запомнить.
Таблица истинности импликации A → B
A │ B │ A → B
───┼───┼───────
0 │ 0 │ 1
0 │ 1 │ 1
1 │ 0 │ 0 ← единственный ложный случай
1 │ 1 │ 1
Правило: A → B ложно только при A=1 и B=0.
«Число решений уравнения» — это сколько наборов значений переменных обращают выражение в 1 (истину). Всего наборов для n переменных — 2ⁿ (для 3 переменных 8, для 4 переменных 16). Удобный приём: посчитать, в скольких наборах выражение ложно (у импликации это легко — один случай), и вычесть из общего числа.
Разбор демо: ((A∨B) → (C∨D)) = 1, 4 переменные
Всего наборов: 2⁴ = 16
Импликация P → Q ложна только при P=1, Q=0, где
P = (A∨B) = 1 во всех наборах (A,B), кроме A=B=0 → 3 из 4
Q = (C∨D) = 0 только при C=D=0 → 1 из 4
Ложных наборов: 3 · 1 = 3
Истинных (решений): 16 − 3 = 13
Контрольный вопрос. Даны логические переменные A, B, C. Сколько существует различных наборов их значений, при которых истинно выражение (A ∨ B) → C, то есть (A ∨ B) → C = 1? Введите число.
Подсказка: Всего наборов для 3 переменных 2³ = 8. Выражение — импликация P → C, где P = (A∨B). Оно ложно только при P=1 и C=0. P=(A∨B)=1 в трёх наборах (A,B) из четырёх, C=0 — значит 3 ложных набора. Истинных: 8 − 3 = 5.
Онлайн-проверка ответа появится позже
Часть Б. Трассировка рекурсии
Рекурсия — это когда функция вызывает саму себя. Чтобы она не работала бесконечно, у неё есть условие остановки (база): при определённом значении аргумента функция возвращает готовый ответ, не вызывая себя дальше. Пройти по рекурсии («трассировать») можно в два хода: сначала разворачиваем вызовы вниз до базы, потом собираем ответы обратно снизу вверх.
Разбор демо: F(x) = 1, если x ≤ 1; иначе F(x−2) − 4.
Найти R = F(5).
Вниз, до базы: Обратно, считаем:
F(5) = F(3) − 4 F(1) = 1 (база, 1 ≤ 1)
F(3) = F(1) − 4 F(3) = 1 − 4 = −3
F(1) = 1 (стоп) F(5) = −3 − 4 = −7
Ответ: R = F(5) = −7
Как трассировать без ошибок:
1) от нужного вызова спускайся вниз, каждый раз подставляя аргумент, пока не сработает условие остановки;
2) запиши значение в точке остановки (базу);
3) поднимайся обратно, подставляя уже посчитанные значения. Знаки (минус, умножение) не теряй.
Контрольный вопрос. Дано определение функции F и вызов R = F(7) (см. исходный код к заданию — на C и на Pascal, обе версии делают одно и то же). Найдите значение переменной R после выполнения вызова. Введите число.
Исходный код для этого задания:
Язык C: int F (int x) { if (x <= 1) return 1; else return F(x - 2) + 3; } Вызов: int R = F(7); Язык Pascal: function F (x: integer): integer; begin if x <= 1 then F := 1 else F := F(x - 2) + 3; end; Вызов: var R: integer; R := F(7);Подсказка: Спускаемся: F(7)=F(5)+3, F(5)=F(3)+3, F(3)=F(1)+3, F(1)=1 (база). Поднимаемся: F(3)=1+3=4, F(5)=4+3=7, F(7)=7+3=10.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Дано определение функции F и вызов R = F(6) (см. исходный код к заданию — на C и на Pascal). Найдите значение переменной R после выполнения вызова. Введите число.
Исходный код для этого задания:
Язык C: int F (int x) { if (x <= 1) return 1; else return F(x - 2) * 2; } Вызов: int R = F(6); Язык Pascal: function F (x: integer): integer; begin if x <= 1 then F := 1 else F := F(x - 2) * 2; end; Вызов: var R: integer; R := F(6);Подсказка: Аргумент уменьшается на 2 от чётного 6, поэтому база — F(0). Спускаемся: F(6)=F(4)·2, F(4)=F(2)·2, F(2)=F(0)·2, F(0)=1 (0 ≤ 1). Поднимаемся: F(2)=1·2=2, F(4)=2·2=4, F(6)=4·2=8.
Онлайн-проверка ответа появится позже
Запомни для этого типа.
— Импликация A → B ложна только при A=1, B=0; иначе истинна.
— Всего наборов для n переменных — 2ⁿ; число решений = сколько наборов дают 1. Часто быстрее сосчитать ложные и вычесть.
— Рекурсия: ищи условие остановки (базу), разворачивай вызовы вниз до неё, потом собирай ответ обратно.
— Аккуратно со знаками: −4, ·2, +3 нельзя терять при обратном ходе.
