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

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

Первый способ: самый простой - «табличный».

Он подходит для тех систем, где все уравнения однотипны, т.е. второе уравнение подобно первому, третье - второму и т.д. Каждое новое уравнение в системе должно содержать переменные, которые есть в предыдущем уравнении. Количество общих переменных не должно быть больше 2. Желательно, чтобы общие переменные имели одинаковые значения, т.е. были «парой». В противном случае, этот метод становится не эффективным и нужно решать СЛУ по-другому.

Пример 1. (демонстрационный вариант 2016 года)

(¬ (x₁ ≡ y₁)) ≡ (x₂ ≡ y₂)

(¬ (x₂ ≡ y₂)) ≡ (x₃ ≡ y₃)

…

(¬ (x₈ ≡ y₈)) ≡ (x₉ ≡ y₉)

Шаг 1. Найдём количество решений для первого уравнения. Из уравнения видно, что если две соседних переменные не равны, то следующая пара переменных обязательно должна быть равной: (x_i ≠ y_i)→(x_i+1 = y_i+1).

И наоборот, если первая пара переменных одинаковая, то следующая должна иметь разные значения: (x_i = y_i)→(x_i+1 ≠ y_i+1).

Исходя из этого правила, построим таблицу истинности для первого уравнения, в которую войдут только нужные нам строки (те, при которых функция истинна).Пусть x₁ и y₁ имеют разные значения (0,1 или 1,0), тогда x₂ и y₂ будут одинаковы (0,0 или 1,1).

Пусть x₁ и y₁ имеют одинаковые значения (0,0 или 1,1), тогда x₂ и y₂ будут разные (0,1 или 1,0).

Итого, по первому уравнению мы имеем 8 наборов переменных.

Шаг 2. Найдём количество решений для второго уравнения. Варианты решений второго уравнения будут точно такими же, как и для первого.

Шаг 3. Добавьте во вторую таблицу два столбца для общих переменных: x₁ и y₁. Не обращая внимания на столбцы значений x₃ и y₃ вставьте значения для x₁ и y₁ , исходя из таблицы 1.

Берем первую строку таблицы: x₂=0, y₂=1

Смотрим в таблице 1 чему будут равны переменные x₁ и y₁ : при x₂=0, а y₂=1, значения переменных x₁ и y₁ могут быть либо x₁=0, y₁=0, либо x₁=1, y₁=1.

Если x₂=1, а y₂=0, то x₁ и y₁ также могут быть либо x₁=0, y₁=0, либо x₁=1, y₁=1.

И так далее заполняем всю таблицу:Видно, что, после добавления второго уравнения, количество найденных решений увеличилось в два раза.

Так как все уравнения в нашей системе однотипны, то каждое следующее уравнение также будет увеличивать количество решений в два раза.

Всего в данной системе 8 уравнений.

Итого: 8*2*2*2*2*2*2*2=1024 решения.

Ответ: 1024

Но такое простое решение подходит не для всех систем. Бывает, что даже для одного уравнения СЛУ трудно (невозможно) построить таблицу истинности, не говоря уже о том, чтобы объединить в таблице два уравнения.

Второй способ: замена выражений простыми переменными.

Этот способ особенно эффективен, когда вы видите, что после замены можно получить логическую операцию - импликацию.

Пример 2.

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

(x₃→x₄)→(x₅→x₆) = 1

(x₅→x₆)→(x₇→x₈) = 1

(x₇→x₈)→(x₉→x₁₀) = 1

Шаг 1. Введем замены:

Z₁=(x₁→x₂)

Z₂=(x₃→x₄)

Z₃=(x₅→x₆)

Z₄=(x₇→x₈)

Z₅=(x₉→x₁₀)

Тогда система уравнений примет более простой вид:

Z₁→Z₂= 1

Z₂→Z₃ = 1

Z₃→Z₄ = 1

Z₄→Z₅ = 1

Можно переписать СЛУ в виде одного уравнения:

(Z₁→Z₂)*(Z₂→Z₃)*(Z₃→Z₄)*(Z₄→Z₅) = 1

Как и СЛУ, это уравнение будет истинно только в том случае, когда каждый из множителей будет принимать значение ИСТИНА.

Шаг 2. Построим таблицу истинности для нашего уравнения, в которую войдут только те строки, при которых уравнение истинно. Внутри скобок - операция импликация между двумя соседними переменными: Z_i→Z_i+1

Импликация принимает значение истина, если первая переменная будет меньше или равна второй переменной.

Это значит, что для того, чтобы всё уравнение (вся система) была истинна, необходимо и достаточно, чтобы Z_i ≤ Z_i+1

Шаг 3. Для каждого из набора решений Z₁-Z₅ найдем количество решений x.

Возьмём первую строчку таблицы истинности: Z₁ = 0, Z₂ = 0, Z₃ = 0, Z₄ = 0, Z₅ = 0

Z₁=(x₁→x₂), Z₂=(x₃→x₄), Z₃=(x₅→x₆), Z₄=(x₇→x₈), Z₅=(x₉→x₁₀)

Следовательно, (x₁→x₂)=0 И (x₃→x₄)=0 И (x₅→x₆)=0 И (x₇→x₈)=0 И (x₉→x₁₀)=0

</ Импликация принимает значение ЛОЖЬ в одном единственном случае (1→0)

Значит, x₁=1, x₂=0, x₃=1, x₄=0, x₅=1, x₆=0, x₇=1, x₈=0, x₉=1, x₁₀=0. Итого 1 набор.

Общее количество решений: 1+3+9+27+81+243=364

Ответ: 364

Метод с заменой выражений очень хорош, но также не универсален. Есть такие СЛУ, где не подходит ни один из способов. Такие системы можно попытаться решить «целиком», не дробя на отдельные уравнения.

Третий способ: Анализ всей системы уравнений.

Пример 3.

((x₁*x₂)→x₃)*((x₄*x₅)→x₆)=1

((x₄*x₅)→x₆)*((x₇*x₈)→x₉)=1

((x₇*x₈)→x₉)*((x₁₀*x₁₁)→x₁₂)=1

Решение: табличный способ не эффективен, т.к. слишком много общих переменных (x1,x2,x3). Метод замены не эффективен, т.к. корневая операция - конъюнкция.

Перепишем систему в следующем виде:

((x₁*x₂)→x₃)*((x₄*x₅)→x₆)*((x₇*x₈)→x₉)*((x₁₀*x₁₁)→x₁₂)=1

Для того, чтобы все уравнение было истинно, необходимо и достаточно, чтобы каждый из множителей принимал значение ИСТИНА.

Найдём количество решений для первого множителя.Если в результате операции x₁*x₂ была получена ЛОЖЬ, то x₃ может принимать любое значение (0 или 1)

Если в результате операции x₁*x₂ была получена ИСТИНА, то x₃ может принимать только одно значение (1)

Следовательно, всего мы получаем 7 вариантов решений (для первого множителя).

Всего таких множителей 4, каждый из которых даст 7 решений. Итого: 7*7*7*7=2401 набор.

Ответ: 2401