Задание 6. Тип заданий 23: системы логических уравнений.
  • Задание:

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

     

    (¬x1 ˅ y1) ≡ (x2 ˄ ¬y2)
    (¬x2 ˅ y2) ≡ (x3 ˄ ¬y3)
    (¬x3 ˅ y3) ≡ (x4 ˄ ¬y4)
    (¬x4 ˅ y4) ≡ (x5 ˄ ¬y5)

     

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

  • Решение:

    Обратите внимание на первое уравнение. Скобки в уравнении независимы, то есть в первой скобке свои переменные, во второй — свои. Значит каждую мы можем заменить отдельной переменной.

    Но скобки отличаются, нам нужно сделать их похожими.

    Обратите внимание на выражение (¬x1 ˅ y1). По закону де Моргана мы можем его преобразовать к виду ¬(x1 ˄ ¬y1), и в этом случае у нас скобки будут уже идентичны:

    ¬(x1 ˄ ¬y1) ≡ (x2 ˄ ¬y2)
    ¬(x2 ˄ ¬y2) ≡ (x3 ˄ ¬y3)
    ¬(x3 ˄ ¬y3) ≡ (x4 ˄ ¬y4)
    ¬(x4 ˄ ¬y4) ≡ (x5 ˄ ¬y5)

    Теперь мы можем заменить каждую скобку другой переменной:

    ¬a ≡ b
    ¬b ≡ c
    ¬c ≡ d
    ¬d ≡ e

    Рассмотрим битовые цепочки для этой системы. В цепочке значений a-e не может быть двух единиц или двух нулей, так как в этом случае система будет ложна. Таким образом, для данной системы существует всего две цепочки решений:

    a 0 1
    b 1 0
    c 0 1
    d 1 0
    e 0 1

    Каждая из переменных a-e представляет собой скобку, внутри которой две переменные, связанные конъюнкцией. Конъюнкция двух переменных истинна в одном случае, а ложна в трёх, значит на каждый нуль в цепочке приходится три варианта значений, а на каждую единицу — один. Таким образом, для первой цепочки существует 33 = 27 наборов значений, а для второй — 32 = 9. Общее количество наборов — 27+9 = 36.

    Ответ: 36

     

Поделиться:
 
Комментарии (0)

Нет комментариев. Ваш будет первым!

Перевести число из в Результат: 510 = 1012