D40516 — Логические выражения и уравнения: ответ и решение

Впишите правильный ответ.

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

(x_i $\land$ y_j → x_i $\land$ y_j_{+ 1}) $\land$ (x_i $\land$ y_j → x_i_{+ 1} $\land$ y_j) = 1

для всех натуральных i и j, таких, что i < 7 и j < 5.

Ниже для Вашего удобства приведены некоторые из равенств, соответствующих этим условиям.

(x₁ $\land$ y₁ → x₁ $\land$ y₂) $\land$ (x₁ $\land$ y₁ → x₂ $\land$ y₁) = 1

(x₁ $\land$ y₂ → x₁ $\land$ y₃) $\land$ (x₁ $\land$ y₂ → x₂ $\land$ y₂) = 1

…

(x₆ $\land$ y₃ → x₆ $\land$ y₄) $\land$ (x₆ $\land$ y₃ → x₇ $\land$ y₃) = 1

(x₆ $\land$ y₄ → x₆ $\land$ y₅) $\land$ (x₆ $\land$ y₄ → x₇ $\land$ y₄) = 1

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, … x₇, y₁, y₂, … y₅, удовлетворяющих условию задачи.
В качестве ответа Вам нужно указать количество таких наборов.

СВОЙСТВА ЗАДАНИЯ

КЭС:

2.7 Алгебра логики. Понятие высказывания. Высказывательные формы (предикаты). Кванторы существования и всеобщности. Логические операции. Таблицы истинности. Логические выражения. Логические тождества. Логические операции и операции над множествами. Законы алгебры логики. Эквивалентные преобразования логических выражений. Логические уравнения и системы уравнений. Логические функции. Зависимость количества возможных логических функций от количества аргументов. Канонические формы логических выражений

2.8 Совершенные дизъюнктивные конъюнктивные нормальные формы, алгоритмы их построения по таблице истинности

2.9 Логические элементы в составе компьютера. Триггер. Сумматор. Многоразрядный сумматор. Построение схем на логических элементах по заданному логическому выражению. Запись логического выражения по логической схеме

Тип ответа:

Краткий ответ

Номер: D40516

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINFD40516

Ответ: 340

Даны 7 переменных x и 5 переменных y. Каждая принимает только значения 0 и 1.
Импликация ложна только при истинном основании и ложном следствии. Поэтому два условия для каждой пары индексов означают: если xᵢ = yⱼ = 1, то xᵢ₊₁ = yⱼ₊₁ = 1.
Это правило действует при 1 ≤ i < 7 и 1 ≤ j < 5. Разобьём все наборы на два непересекающихся случая.

1. Хотя бы в одной из двух последовательностей все переменные до последней равны нулю.
Если x₁ = … = x₆ = 0, все основания импликаций ложны. Последняя переменная x₇ и все 5 переменных y свободны. Получаем 2 · 2⁵ = 64 наборов.
Если y₁ = … = y₄ = 0, аналогично свободны последняя переменная y и все 7 переменных x: 2 · 2⁷ = 256 наборов.
При сложении дважды учтены наборы, в которых оба указанных начала состоят из нулей. В них свободны только две последние переменные, поэтому пересечение содержит 2 · 2 = 4 набора.
Всего в первом случае: 64 + 256 − 4 = 316.

2. В обеих последовательностях есть единица до последней позиции.
Пусть первые единицы находятся на позициях p и q. Подставим i = p, j = q: следующие элементы обеих последовательностей также равны 1. Затем, сохраняя j = q, последовательно получаем все оставшиеся единицы в x; сохраняя i = p — все оставшиеся единицы в y.
Значит, каждая последовательность имеет вид: несколько нулей, затем только единицы. Обратно, любая такая пара последовательностей удовлетворяет обеим импликациям: после единицы уже не может встретиться нуль.
Первая единица x может стоять на любой из 6 позиций до последней, первая единица y — на любой из 4 таких позиций. Выборы независимы: 6 · 4 = 24.

Складываем непересекающиеся случаи: 316 + 24 = 340.
Проверка полноты: либо хотя бы одно начало не содержит единиц, либо оба содержат. В первом случае все основания ложны, во втором необходимые продолжения однозначны. Ни один набор не пропущен и не посчитан дважды.
Ответ: 340.

Задание EGEINFD40516: Логические выражения и уравнения

Решение задания EGEINFD40516

Помочь улучшить сайт

Комментарии к решению