Виды 23 задания егэ информатика

Здравствуйте! Сегодня речь пойдёт о 23 задании из ЕГЭ по информатике 2023.

Двадцать третье задание является последним заданием из первой части ЕГЭ по информатике 2023.

Давайте познакомимся с примерными задачами 23 задания из ЕГЭ по информатике 2023.

Задача (классическая)

У исполнителя Удвоитель две команды, которым присвоены номера:

1. прибавить 3,
2. умножить на 2.

Первая из них увеличивает число на экране на 3, вторая — удваивает его.

Программа для Удвоителя — это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 25 ?

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+3, y) + F(x*2, y)

print(F(1, 25))

Число x, это то число, с которым мы работаем. Число y — это куда нужно прийти.

Если число x достигло пункта назначения, то возвращаем 1. Если оно перескочило y, то возвращаем 0. А если ещё не дошло до y, то продолжаем вычисления с помощью рекурсии.

Ответ получается равен 9.

2 Способ (графический, для понимания)

Начинаем рассматривать задачку с конца. Если число нечётное, то оно может быть получено только с помощью первой команды. Если число чётное, то оно может быть получено с помощью двух команд.

Видим, что количество программ получается 9!

3 Способ (С помощью таблицы)

Некоторое число i можно получить только двумя способами: либо c помощью первой команды, либо с помощью второй команды. Тогда количество программ для некоторого числа i будет складываться из двух чисел: количества программ для числа i-3 и количества программ для числа i / 2 (Если i — чётное).

В первой строке пишутся числа от 1 до 25 (до того числа, которое нужно получить).

Во второй строке пишутся числа, которые в сумме с 3 (тройкой) дают числа, написанные в первой строке. (Прим. начиная с 4, числа идут по порядку.)

В третьей строке пишутся числа, которые при умножении на 2 дают числа, написанные в первой строке. (Прим. числа так же идут по порядку через одну пустую ячейку.)

В четвёртой строке для единицы ставим 1. Для остальных ячеек: смотрим, какие числа участвуют во второй и третьей строке для конкретной ячейки. Затем, эти числа ищем в первой строке и пишем сумму количеств программ для этих чисел (Т.е. пишем сумму уже известных значений из четвёртой строки для этих чисел).

Таким образом, основная идея 23 задания из ЕГЭ по информатике заключается в том, что результат каждого шага опирается на результаты предыдущих шагов!

Получаем ответ 9!

Ответ: 9

Задача (с избегаемым узлом)

Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:

1. прибавь 1

2. сделай нечётное

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ — это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 25, причём траектория вычислений не содержит число 24? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10304

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y or x==24: return 0

    if x < y: return F(x+1, y) + F(x*2+1, y)

print(F(1, 25))

Здесь на нельзя получать число 24, поэтому, если x будет равен 24, то мы возвращаем ноль.

Ответ получается равен 10.

2 способ (Решение с помощью таблицы).

Мы не может получать число 24! Значит, единственным способом добраться до числа 25 будет вторая команда.

Получается, что сначала нужно получить число 12, тогда 2 * 12 + 1 = 25 (2x+1). Это единственный путь!

Каждое число можем получить только 2 способами (Либо с помощью первой команды, либо с помощью второй команды). Поэтому количество программ для некоторого числа i будет равно сумме количеств команд для числа i-1 и для числа (i — 1) / 2 (Если число нечётное.) Если число i — чётное, то до числа i можно добраться единственным способом (с помощью первой команды).

Если записать с помощью массива:

A[i]=A[i-1] — если i — четное.
A[i]=A[i-1] + A[(i-1)/2] — если i нечетное;

Ответ: 10

Задача (ЕГЭ по информатике, Москва, 2019)

У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Умножить на 3
3. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает его на 2.

Сколько существует программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений содержит число 9 и число 11?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x*3, y) + F(x+2, y)

print(F(2, 9)*F(9, 11)*F(11, 12))

У нас числа 9 и 1 обязательные, поэтому разбиваем функцию следующим образом F(2, 9)*F(9, 11)*F(11, 12), через умножение. Это и будет ответ. Получается 50.

2 способ (с помощью таблицы).

От числа 11 до числа 12 можно добраться единственным путём (11 + 1 = 12).

От числа 9 до числа 11 можно добраться двумя способами (9 + 1 + 1 = 11, 9 + 2 = 11).

Найдём сколькими способами можно попасть от числа 2 до числа 9.

Учитывая, что от 9 до 11 двумя способами можно добраться, то 25 * 2 = 50 — это и будет ответ.

Ответ: 50

Задача ( ЕГЭ по информатике, Москва, 2020)

У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Умножить на 3
3. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает на 2.

Сколько существует программ, которые преобразуют исходное число 3 в число 14 и при этом траектория вычислений содержит число 9?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x*3, y) + F(x+2, y)

print(F(3, 9)*F(9, 14))

Ответ получается 112.

2 способ (с помощью таблицы).

Последней командой для получении любого числа из траектории программы может быть одна из трёх выше указанных команд!

Значит, количество программ для некоторого числа будет складываться из количества программ для тех чисел, из которых это число может быть получено.

Получается, что мы будем использовать основной принцип 23 задания из ЕГЭ по информатике: результат для некоторого числа опирается на результаты предыдущих чисел. Т.к. траектория вычислений программ обязательно должна проходить через число 9, то при вычислении результата для чисел больших 9, мы не можем опираться на результаты для чисел меньших 9 (Иначе мы пропустим число 9).

Ответ: 112

Посмотрим следующую задачу из 23 задания ЕГЭ по информатике 2023

Задача (с обязательным узлом, закрепление)

Исполнитель Май17 преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1
2. Прибавить 3

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3. Программа для исполнителя Май17 — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 17 и при этом траектория вычислений содержит число 9?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 12 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x+3, y)

print(F(1, 9)*F(9, 17))

Ответ получается 169.

2 способ (с помощью таблицы).

Любое число может получится в результате двух команд! Тогда количество программ для числа i будет складываться из количеств команд для числа i — 1 и для числа i — 3.

Если написать на языке массива

A[i] := A[i-1] + A[i-3], при i > 3.

При составлении значения для числа 10, мы не имеем право «заглядывать» за число 9, иначе число 9 будет пропущено! Поэтому для следующих трёх чисел (9, 9 + 1, 9 + 1 + 1), начиная с 9, будет 13 программ.

Для числа 17 получается ответ 169.

Ответ: 169

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

За это задание ты можешь получить 1 балл. На решение дается около 10 минут. Уровень сложности: высокий.
Средний процент выполнения: 25.4%
Ответом к заданию 23 по информатике может быть цифра (число) или слово.

Задачи для практики

#include <iostream>
using namespace std;
int main(){
    const int n0 = 1, nk = 33;
    int arr[nk + 1];
    for (int i = 0; i < nk + 1; ++i) arr[i] = 0;
    arr[n0] = 1;
    for (int n = n0 + 1; n <= nk; ++n) {
        arr[n] = arr[n - 1]; // Kn-1
        if (n % 2 != 0 && (n - 1) / 2 >= n0) //K(n - 1)/2
            arr[n] += arr[(n - 1) / 2];
        if (n % 2 != 0 && (n + 1) / 2 >= n0) //K(n + 1)/2
            arr[n] += arr[(n + 1) / 2];
        if (n == 7 || n == 14)
            arr[n] = 0;
        if (n == 12)
            for (int i = n - 1; i >=0 ; --i)
                arr[i] = 0;
    }
    cout << arr[nk];
    return 0;
}

#include <iostream>
using namespace std;
int main(){
    const int n0 = 2, nk = 30;
    int arr[nk + 1];
    for (int i = 0; i < nk + 1; ++i) arr[i] = 0;
    arr[n0] = 1;
    for (int n = n0 + 1; n <= nk; ++n) {
        arr[n] = arr[n - 1]; // Kn-1
        if (n % 2 != 0 && (n - 1) / 2 >= n0) //K(n - 1)/2 - сделай нечётное
            arr[n] += arr[(n - 1) / 2];
        if (n % 2 == 0 && n / 2 >= n0) //Kn/2 - сделай чётное
            arr[n] += arr[n / 2];
        if (n == 16)
            arr[n] = 0;
        if (n == 9)
            for (int i = n - 1; i >=0 ; --i)
                arr[i] = 0;
    }
    cout << arr[nk];
    return 0;
}

В 2021 году экзамен по информатике кардинально изменился. Теперь он проходит в компьютерной форме. Полностью исчезли задания, требующие простого воспроизведения формул и терминов. В ЕГЭ нового типа нужно рассуждать и решать задачи. Часть выполняется на бумаге, в электронную форму вносится только ответ. Другая часть представляет собой работу в компьютерных программах. Изменения коснулись и номера 23 из ЕГЭ по информатике. Раньше это была задача на системы логических уравнений, которая вызывала у школьников затруднения. В нынешнем году ее убрали, заменив на вопрос с анализом результата исполнения алгоритма. Он относится к первой части и дает 1 балл. Разбираемся в теории и решении 23 задания в ЕГЭ по информатике. 

Теория

Задача 23 связана с алгоритмами. Алгоритм — полное и точное описание действий, приводящее к конечному результату. В информатике исходными и выходными данными является информация. Алгоритмы реализуются в компьютерных программах, они должны занимать определенный объем памяти и время. Алгоритм должен быть: 

• дискретным (прерывным). Состоит из последовательности простых шагов;
• детерминированным (определенным). В описании операций нет многозначности, исполнитель понимает их и может реализовать;
• массовым. Позволяет решить не одну задачу, а группу аналогичных. В качестве возможных данных используются переменные;
• результативным. Рассматривает все ситуации, дает конечный результат;
• конечным. Имеется определенное количество шагов;
• эффективным. Время выполнения алгоритма позволяет использовать его для реальных задач.

Алгоритм делят на базовые элементы (структуры). Структуры бывают трех типов: следование (последовательные действия), ветвление (программа проверяет условие и выбирает один из вариантов действия в зависимости от результата), цикл (несколько действий повторяются многократно). В задании 23 по информатике используются следующие способы записи алгоритмов: 

• обычный язык. Текст с разделением на шаги;
• блок-схема. Программа представляется графически, используются специальные блоки: 

Блок	Обозначение
	Начало, конец
	Ввод, вывод данных
	Операция
	Условие
	Цикл с параметром
	Обращение к дополнительным алгоритмам

• Блок
• Обозначение
• Начало, конец
• Ввод, вывод данных
• Операция
• Условие
• Цикл с параметром
• Обращение к дополнительным алгоритмам
• языки программирования. Имеют строгие правила записи, включающие в себя символы и зашифрованные слова;
• псевдокод. Объединение обычного языка и языка программирования. Нет строгих правил, но есть неизменяемые слова, задающие алгоритм. Например, «нач» — начало, «кон» — конец, «рез» — результат.   

Примеры из ЕГЭ

Чтобы хорошо подготовиться к экзамену, нужно решить практические задачи по 23 заданию. Номер основан на динамическом программировании — решении сложных задач путем приведения к более простым. То есть, для выполнения конечного алгоритма нужно разобраться с подзадачами. 

Для решения могут применяться графический и табличный способ. 

Пример 1. У исполнителя Удвоитель две команды:

1. прибавить 3

2. умножить на 2

Программа для Удвоителя — последовательность команд.

Сколько есть программ, преобразующих число 1 в 25?

Решение. Решим графическим способом. Начнем выполнять с конца. Итоговый результат получается двумя способами — прибавлением к числу Х тройки или умножением числа Y на 2. 25 — нечетное число, вариант с умножением отпадает. Следовательно, перед 25 в алгоритме стояло 25-3=22.

Число 22 получается и умножением, и сложением. Алгоритм разделяется на 2: в одном число 22:2=11, а в другом 22-3=19. Каждое из этих чисел анализируем по той же схеме. Нужно «разворачивать» алгоритм до тех пор, пока каждая из ветвей не закончится единицей. Рисунок выглядит так: 

Ответ: 9.

Пример 2. Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть две команды: 

1. прибавить 1

2. умножить на 2

Сколько существует программ, преобразующих исходное число 2 в число 9?

Решение. Воспользуемся таблицей. В этом случае решаем в прямом порядке. В первой строке таблицы записываем все целые числа от исходного до итогового. Во второй пишем число, к которому нужно прибавить 1 для получения цифры из первой строки. В третьей строке аналогично, но с умножением. Четвертая строка — количество разных команд, которые могут привести к получению числа. 

Задание 23 в ЕГЭ  – это одно из заданий, проверяющих умение анализировать результат исполнения алгоритма, содержащего ветвление и цикл. Как правило, это задание не очень сложное и поэтому на него рекомендуется, на наш взгляд, обращать внимание всем учащимся, сдающим ЕГЭ по предмету «Информатика».

Основные способы решения задания 23 ЕГЭ по информатике.

1. Аналитический (с помощью дерева вариантов или таблицы)

2. Программный (рекурсия или динамическое программирование)

Рассмотрим пример задания.

Исполнитель преобразует число на экране.

У него две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая из них увеличивает число на экране на 1, а вторая – в два раза.

Программа исполнителя – это последовательность команд.

Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 1221 при исходном числе 5 траектория будет состоять из чисел 6, 12, 24, 25.

Сколько существует программ, которые число 2 преобразуют в число 32, причём траектория вычислений содержит число 10?

По сути, необходимо ответить на два вопроса.

А) Сколько существует программ, которые преобразуют число 2 в число 10?

Б) Сколько существует программ, которые преобразуют число 10 в число 32?

Для ответа на вопрос исходной задачи необходимо перемножить ответы на эти два вопроса, так как каждому способу получить из числа 2 число 10 может соответствовать любой из способов получения числа 32 из числа 10.

Приведём примеры решения задания выше.

1. Аналитический.

А) С помощью дерева вариантов посчитаем количество способов получения из числа 2 числа 10. Таких способов 7 (по числу обведённых в кружочек конечных результатов).

Б) С помощью дерева вариантов посчитаем количество способов получения из числа 10 числа 32. Таких способов 8 (по числу обведённых в кружочек конечных результатов).

Итого 7 * 8 = 56 различных программ.

2. Программный способ (рекурсия). Пример решения дадим на языке Pascal (легко можно перенести решение на нужный вам язык). Число a – начальное, b – число после работы программы из условия задачи. На каждом шаге анализируем, какие числа можем получить за 1 ход из числа a.

function func(a, b : integer) : integer;

begin

if (b < a) then

result := 0

else if (b = a) then result := 1

else result := func(a+1, b) + func(2*a, b)

end;

begin

writeln ( func(2,10) * func(10,32) );

end.

Замечание. Рассмотрим другой возможный вопрос в задаче.

Сколько существует программ, которые число 2 преобразует в число 32, причём траектория не содержит число 10?

Необходимо найти общее число программ, преобразующих число 2 в число 32, и вычесть количество программ, содержащих число 10, то есть вычислить результат по формуле func(2,32) — func(2,10)*func(10,32).

3*. Программный способ решения (с помощью динамического программирования). Последовательно вычисляем элементы в массиве элементы с индексами от a до b. В i-м элементе массива будет храниться число способов получить из начального числа a число i. Для каждого числа (индекса массива) смотрим, какие числа можно из него получить описанными операциями. Пример на языке Pascal (легко можно перенести решение на нужный вам язык).

var dp : array[ 1..32 ] of integer;

function func2 ( const a, b : integer) : integer;

var i: integer;

begin

dp [ a ] := 1;

for i := (a+1) to b do

dp[ i ] := 0;

for i:= a to b do

begin

if ( 2 * i <= b) then

dp [2 * i ] := dp [2 * i] + dp [ i ];

if (i + 1 <= b) then

dp [i + 1] := dp [i + 1] + dp [ i ];

end;

func2 := dp [b];

end;

begin

writeln ( func2(2,10) * func2(10,32) );

end.

Надеемся, что приведенные примеры помогут вам решить задание 23 в ЕГЭ по информатике и овладеть такими понятиями, как рекурсия, динамическое программирование, дерево вариантов.

Автор материалов — Лада Борисовна Есакова.

Решение систем логических уравнений методом замены переменных

Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной.

Пример 1.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно за­пи­сать си­сте­му в виде од­но­го урав­не­ния:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1  → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0  достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

Сло­жим ко­ли­че­ство наборов: 1 + 3 + 9 + 27 + 81 = 121.

Ответ: 121

Пример 2.

Сколько существует различных наборов значений логических переменных x1, x2, … x9, y1, y2, … y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

…

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x9, y1, y2, … y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение:

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 — два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 2⁹ наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2⁹ +2⁹ = 1024 наборов.

Ответ:1024

Решение систем логических уравнений методом визуального определения рекурсии.

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

Пример 3.

Сколь­ко раз­лич­ных ре­ше­ний имеет си­сте­ма урав­не­ний

¬x1 ∨ x2 = 1

¬x2 ∨ x3 = 1

…

¬x9 ∨ x10 = 1,

где x1, x2, … x10 — ло­ги­че­ские пе­ре­мен­ные?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний x1, x2, … x10, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 ( 0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 ( 0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

N_i+1 = N_i + 1. Тогда для десяти переменных получим 11 наборов.

Ответ: 11

Решение систем логических уравнений различного типа

Пример 4.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x₁, …, x₄, y₁,…, y₄, z₁,…, z₄, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x₁ → x₂) ∧ (x₂ → x₃) ∧ (x₃ → x₄) = 1

(y₁ → y₂) ∧ (y₂ → y₃) ∧ (y₃ → y₄) = 1

(z₁ → z₂) ∧ (z₂→ z₃) ∧ (z₃ → z₄) = 1

x₄ ∧ y₄ ∧ z₄ = 0

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x₁, …, x₄, y₁, …, y₄, z₁, …, z₄, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что три уравнения системы одинаковы на различных независимых наборах переменных.

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):

Аналогично, решениями второго и третьего уравнений будут абсолютно такие же наборы y1,…,y4 и z1,…, z4.

Теперь проанализируем четвертое уравнение системы: x₄ ∧ y₄ ∧ z₄ = 0. Решением будут все наборы x4, y4, z4, в которых хотя бы одна из переменных равна 0.

Т.е. для x4 = 0 подойдут все возможные наборы (y4, z4), а для x4 = 1 подойдут наборы (y4, z4), в которых присутствует хотя бы один ноль : (0, 0), (0,1) , (1,0).

Общее количество наборов 25 + 4*9 = 25 + 36 = 61.

Ответ: 61

Решение систем логических уравнений методом построения рекуррентных формул

Метод построения рекуррентных формул применяется при решении сложных систем, в которых порядок увеличения количества наборов неочевиден, а построение дерева невозможно из-за объемов.

Пример 5.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, … x7, y1, y2, … y7, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

…

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

(x7 ∨ y7) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, …, x7, y1, y2, …, y7, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что первые шесть уравнений системы одинаковы и отличаются только набором переменных. Рассмотрим первое уравнение. Его решением будут следующие наборы переменных:

Обозначим:

число наборов (0,0) на переменных (x1,y1) через A₁,

число наборов (0,1) на переменных (x1,y1) через B₁,

число наборов (1,0) на переменных (x1,y1) через C₁,

число наборов (1,1) на переменных (x1,y1) через D₁.

число наборов (0,0) на переменных (x2,y2) через A₂,

число наборов (0,1) на переменных (x2,y2) через B₂,

число наборов (1,0) на переменных (x2,y2) через C₂,

число наборов (1,1) на переменных (x2,y2) через D₂.

Из дерева решений видим, что

A₁=0, B₁=1, C₁=1, D₁=1.

Заметим, что набор (0,0) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. A₂=B₁+C₁+D₁.

Набор (0,1) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. B₂=B₁+C₁+D₁.

Аналогично рассуждая, заметим, что С₂=B₁+C₁+D₁. D₂= D₁.

Таким образом, получаем рекуррентные формулы:

A_i+1 = B_i + C_i + D_i

B_i+1 = B_i + C_i + D_i

C_i+1 = B_i + C_i + D_i

D_i+1 = A_i +B_i + C_i + D_i

Составим таблицу

Последнему уравнению (x7 ∨ y7) = 1 удовлетворяют все наборы, кроме тех, в которых x7=0 и y7=0. В нашей таблице число таких наборов A₇.

Тогда общее количество наборов равно B₇ + C₇ + D₇ = 127+127+1 = 255

Ответ: 255