Логические уравнения и методы их решения

Методы решения систем логических уравнений
статья по информатике и икт (10 класс) по теме

Методы решения систем логических уравнений при подготовке к ЕГЭ (задание В15)

Скачать:

Предварительный просмотр:

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

Решить систему логических уравнений можно, например, с помощью таблицы истинности (если количество переменных не слишком велико) или с помощью дерева решений, предварительно упростив каждое уравнение.

1. Метод замены переменных.

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

Рассмотрим применение этого метода на конкретном примере.

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

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

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

Введем новые переменные: А=(X1 ≡ X2); В=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Внимание! Каждая их переменных x1, x2, …, x10 должна входить только в одну из новых переменных А,В,С,D,Е, т.е. новые переменные независимы друг от друга).

Тогда система уравнений будет выглядеть так:

Построим дерево решений полученной системы:

Рассмотрим уравнение А=0, т.е. (X1 ≡ X2)=0. Оно имеет 2 корня:

Из этой же таблицы видно, что уравнение А=1 тоже имеет 2 корня. Расставим кол-во корней на дереве решений:

Чтобы найти количество решений одной ветви, надо перемножить количества решений на каждом ее уровне. Левая ветвь имеет 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 решения; правая ветвь имеет тоже 32 решения. Т.е. вся система имеет 32+32=64 решения.

2. Метод рассуждений.

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

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

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5 ) = 1

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

Первое и второе уравнения содержат независимые переменные, которые связаны третьим условием. Построим дерево решений первого и второго уравнений.

Чтобы представить дерево решений системы из первого и второго уравнений, надо каждую ветвь первого дерева продолжить деревом для переменных у . Построенное таким образом дерево будет содержать 36 ветвей. Некоторые из этих ветвей не удовлетворяют третьему уравнению системы. Отметим на первом дереве количество ветвей дерева «у» , которые удовлетворяют третьему уравнению:

Поясним: для выполнения третьего условия при х1=0 должно быть у1=1, т.е все ветви дерева «х» , где х1=0 можно продолжить только одной ветвью из дерева «у» . И только для одной ветви дерева «х» (правой) подходят все ветви дерева «у». Таким образом, полное дерево всей системы содержит 11 ветвей. Каждая ветвь представляет собой одно решение исходной системы уравнений. Значит, вся система имеет 11 решений.

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

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

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

Решение : Упростим систему. Построим таблицу истинности части первого уравнения:

Логические уравнения

В ЕГЭ (но не в учебниках) встречается тип заданий, которые до 2011 года имели один из двух видов:

• при каких значениях переменных a,b,c. данное выражение становится истинным(ложным);
• сколько различных решений имеет уравнение f(a,b,c. ) = 1 (0)

Это могут быть короткие выражения:

(K ^ L ^ M ) v (⌝L ^ ⌝M ^ N) = 0

((J → K) → (M /\ N /\ L)) /\ ((J /\ ¬K) → ¬(M /\ N /\ L)) /\ (M → J) = 1

(((J -> K) -> (M & N & L)) & ((J &

и системы однотипных или не совсем однотипных выражений.

в случае коротких выражений иногда проще всего построить таблицу истинности. Существуют онлайн-построители, например http://programming.dojo.net.nz/study/truth-table-generator/index

также можно писать несложные программы для построения таблиц истинности:

Проделывать многие операции над логическими выражениями умеет и WolframAlpha:

В целом дело сводится к анализу выражения, попыткам найти скрытую схему в нем.

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

Если это дизъюнкция, то могут быть рассуждения вида «если левая скобка 0, то правая обязана быть 1»

В демонстрационном варианте 2012 г., А ТАКЖЕ в реальных вариантах весны/лета 2011 года появилась новая формулировка:

Алгоритм решения системы с большим числом однотипных уравнений

1. преобразовать уравнения, найти что-то с известной таблицей истинности
2. проанализовать таблицу истинности. например, если получается XOR то либо первый аргумент 1 либо второй
3. метод гипотез: пусть х1 = 0, тогда при х2 = 0 получаем 00ххххххх, при х2 = 1 получаем 01ххххххх
4. первое уравнение дает N ветвей решений, нужно посмотреть что у них общего
5. так же разобрать второе уравнение, после чего должна проявиться закономерность построения решений
6. найти закономерность — определить, на сколько увеличилось число ветвей благодаря второму уравнению
7. подсчитать общее количество распространив эту схему до конца системы
8. может быть проще увидеть взаимосвязь всех уравнений вместе, как они определяют закономерность построения решения

2012 год

B15

Вот два способа рассуждения.

I.

Если обозначить A = x1 ≡ x2, B = x3 ≡ x4 и так далее

то получим: (A ∨ B) ∧ (¬A ∨ ¬B)

или, по закону Де Моргана, (A ∨ B) ∧ ¬(A ∧ B)

это достаточно известная альтернативная формула для исключающего ИЛИ, как и (A ∧ ¬B) ∧ (¬A ∧ B)

Тогда система принимает вид:

Из первого уравнения видно, что либо x1 и x2 одинаковы, либо x3 и x4 одинаковы.

то есть если x1 и x2 одинаковы, то x3 и x4 разные

и наоборот, если x1 и x2 различны, то x3 и x4 одинаковы

Иными словами, рассмотрим наборы при x1 = 0, тогда

если x2 = 0, то левая скобка 1, тогда правая скобка д.б. 0, т.е. либо x3,x4 = 0,1 либо 1,0,

если x2 = 1, то левая скобка 0, тогда правая скобка д.б. 1, т.е. либо x3=x4=0 либо x3=x4=1

получается четыре ветви

теперь рассмотрим наборы при x1 = 1, тогда

получается опять четыре ветви

то есть первое уравнение дает восемь «ветвей» решений

Что даст второе уравнение?

либо x3 и x4 одинаковы, либо либо x5 и x6 одинаковы

в каждой из 8 ветвей на некоторую пару x3,x4 приходится по две пары x5,x6

то есть второе уравнение даст 16 ветвей

Аналогично, третье уравнение даст 32 ветви,

а четвертое уравнение в каждой из них по два итоговых решения.

Итого — 64 решения.

II.

Если смотреть на систему как на целое, то можно получить общий вид цепочек

тогда не верно (x3 ≡x4), но верно (x5 ≡x6), не верно (x7 ≡x8) и верно (x9 ≡x10)

это наборы вида 00xx00xx00 00xx00xx11

в которых xx — это 01 или 10

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

8 групп комбинаций, в каждой из которых по 4 возможных значения на местах xx xx 8*4 = 32

И то же самое, если НЕ верно (x1 ≡x2)

Итого 64 решения.

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

Обозначим A0 = пара 00, A1 = пара 11, B0 = пара 01, B1 = пара 10

После любого A может идти только B и наоборот.

Рассмотрим комбинации по две:

A0B0 A0B1 A1B0 A1B1 B0A0 B0A1 B1A0 B1A1 — их получилось 8.

если их будет по три

то на каждую такую кобминацию будет по две трехбуквенных, то есть 16

если по четыре, то 32

Итого 64 решения.

2014 год

B15

Преобразуем уравнения к удобному виду:

(x1 ⊕ x2 ) ^ (x1 ⊕ x3) = 0

(x2 ⊕ x3 ) ^ (x2 ⊕ x4) = 0

(x8 ⊕ x9 ) ^ (x8 ⊕ x10) = 0

рассмотрим решения 0ххххххххх

(0 ⊕ x2 ) ^ (0 ⊕ x3) = 0

эти две скобки не должны быть одновременно 1, чтобы конъюнкция была 0

если левая скобка 1, то вторая д.б.0 и наоборот, и еще они могут быть равны 0 одновременно

итак если x2 = 1 то x3 = 0

если правая 1, то левая 0

а одновременно они нули — это 011ххххх

рассмотрим решения 1ххххххххх

(1 ⊕ x2 ) ^ (1 ⊕ x3) = 0

если х2 = 0, левая скобка 1, правая д.б. 0, т.е. х3 = 1

если х3 = 0, правая скобка 1, левая д.б.0, т.е. х2 = 1

и одновременно скобки нули при х2 = х3 = 1

итак, первое уравнение дает шесть ветвей решений

010xxxxxxx 001ххххххх 011ххххх

(1 ⊕ 0 ) ^ (1 ⊕ x4) = 0 (0 ⊕ 1 ) ^ (0 ⊕ x4) = 0 (1 ⊕ 1 ) ^ (1 ⊕ x4) = 0

0101хххххх 0010хххххх 0110хххххх

101ххххххх 110ххххххх 111ххххххх

(1 ⊕ 0 ) ^ (1 ⊕ x4) = 0 (0 ⊕ 1 ) ^ (0 ⊕ x4) = 0 (1 ⊕ 1 ) ^ (1 ⊕ x4) = 0

1010хххххх 1100хххххх 1110хххххх

итак второе уравнение дало 8 ветвей

третье должно дать 10

итак, ответ — 20 решений

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

2013 год

B15

преобразуем второе уравнение

все скобки здесь должны быть истинами

рассмотрим x1 = 1 и y1 = 1

т.е. комбинации 1xxx1xxx

(1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1

(1 → y2) /\ (y2 → y3) /\ (y3 → y4) = 1

(1 → 1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 →x4) = 1

это сразу определяет что x2 = 1, x3 = 1, x4 = 1 и то же для игреков

т.е. из этой ветви годится только решение 11111111

И (*) ВООБЩЕ если x_n = 1 то очевидно для всех i x_n+i = 1

и то же для всех y

т.е. если встречается 1, то далее все одноименные переменные тоже 1

01110111 например годится, 00110011 и 00010001

это следует из первых двух уравнений

а что дает третье уравнение?

то что если какой-то y=1 то однономерной x с ним тоже будет 1

т.е. ветви решений не симметричны:

годится 01110000 но не годится 00001111

подсчитаем комбинации исходя из этого

xx110011 (00, 01 и 11)

xxx10001 (000, 001, 011 и 111)

xxxx0000 (0000, 0001, 0011, 0111, 1111)

Ответ: 15

И еще примеры решения конкретных систем: Пример 1, Пример 2

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

Два варианта решения:

• таблица истинности (гарантия верного ответа)
• аналитический (упрощение, сведение к системе)

АЛГОРИТМ аналитического решения

1. возможно решать противоположную задачу, определив общее число наборов,
2. в зависимости от необходимости превратить в конъюнкцию = 1 или дизъюнкцию = 0
3. разбить на систему
4. согласно таблице истинности описать наборы решений для каждой части системы
5. по возможности выбрать ту, где меньше решений
6. посмотреть какие решения совпадают, т.е. протестировать решения одной части для другой части
7. выкинуть из второй части то, что не является решениями первой части.
8. для системы из двух легко воспользоваться формулой количества пересечений.
9. иногда довольно легко подсчитать комбинации по их «правилу образования», иногда нагляднее и проще выписать их себе списком (если это в пределах десятка).

Рассмотрим пример: (K V L) → (L ^ M ^ N) = 0

Импликация. Ложна когда первая часть истинна, а вторая ложна. Отсюда система:

Первый вариант рассуждений. Рассмотрим антирешения.

дизъюнкция ложна в 4 случаях: 0000 0001 0010 0011

конъюнкция истинна в 2 случаях: 0111 1111

при этом эти «антирешения» не пересекаются, т.е. получается, что все остальные 16-6 = 10 комбинаций должны подходить обоим уравнениям. Потому что эти 10 комбинаций не содержат ни антирешений первого, ни антирешений второго уравнения.

Второй вариант рассуждений. Выберем уравнение с наименьшим числом решений, это первое (16-4 = 12).

Подставим эти решения во второе. Как это сделать, если у нас нет их полного списка?

Очень просто. Среди этих 12 решений есть 2 антирешения второго, так как она оба НЕ входят в 4 антирешения первого.

Значит их нужно выкинуть. 12-2 = 10

Третий вариант. Объединение множеств решений первого и второго — 16. Решений первого 12, решений второго 14.

А найти надо пересечения. По формуле мощности пересечения множеств

|X ∩ Y| = |X| + |Y| — |X U Y| = 12 + 14 — 16 = 26 — 16 = 10

Ответ: 10 решений.

( K | L ) | ( L & M & N )

0 0 0 0 | 1 0 0 0 1 0 0 0 0 0

0 0 0 1 | 1 0 0 0 1 0 0 0 0 1

0 0 1 0 | 1 0 0 0 1 0 0 1 0 0

0 0 1 1 | 1 0 0 0 1 0 0 1 0 1

0 1 0 0 | 0 0 1 1 0 1 0 0 0 0

0 1 0 1 | 0 0 1 1 0 1 0 0 0 1

0 1 1 0 | 0 0 1 1 0 1 1 1 0 0

0 1 1 1 | 0 0 1 1 1 1 1 1 1 1

1 0 0 0 | 0 1 1 0 0 0 0 0 0 0

1 0 0 1 | 0 1 1 0 0 0 0 0 0 1

1 0 1 0 | 0 1 1 0 0 0 0 1 0 0

1 0 1 1 | 0 1 1 0 0 0 0 1 0 1

1 1 0 0 | 0 1 1 1 0 1 0 0 0 0

1 1 0 1 | 0 1 1 1 0 1 0 0 0 1

1 1 1 0 | 0 1 1 1 0 1 1 1 0 0

1 1 1 1 | 0 1 1 1 1 1 1 1 1 1

Рассмотрим другой пример: (K v L) & (M v N) = 1

Первому не подходят 0000, 0001, 0010, 0011, т.е. решений 12

Второму не подходят 0000, 0100, 1000, 1100, т.е. решений 12

Объединение множеств решений первого и второго — 15,а не 16, так как комбинация 0000 не подходит обоим уравнениям..

|X ∩ Y| = |X| + |Y| — |X U Y| = 12 + 12 — 15 = 24 — 15 = 9

Или можно просто сказать, что уникальных антирешений всей системы 7 — они складываются из антирешений первого, антирешений второго минус 1 (одно) повторение антирешения 0000, 16-7 = 9

Ответ: 9 решений

(K ^ L ^ M ) v (⌝L ^ ⌝M ^ N) = 0

Дизъюнкция равна 0, это система

16 комбинации всего возможны

антирешения первого: 111х, их два, следовательно 16-2 = 14 решений первого

антирешения второго: х001, их два, следовательно 16-2 = 14 решений второго

антирешения НЕ пересекаются

поэтому решений 14+14 — 16 = 12

(K v L v M ) ^ (⌝L ^ ⌝M ^ N) = 1

Здесь у второго вообще 2 решения (0001 и 1001), подставляем их в первое, 0001 является антирешением первого.

Ответ: 1 решение

(K ^ L ^ M ) → (⌝M ^ N) = 1

решим сначала (K ^ L ^ M ) → (⌝M ^ N) = 0

не противоречат ли они второй?

значит здесь 2 решения

значит у противоположной задачи 16 — 2 = 14 решений

Задания в 2010 году были в два раза длиннее. И переменных там больше.

Задача №23. Решение систем логических уравнений.

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

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

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных 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 перемножаются:

Кол-во наборов на x1…x8

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

Сколько существует различных наборов значений логических переменных x1, x2, . x9, y1, y2, . 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 9 наборов (x1,y1), (x2,y2),…, (x9,y9).

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

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

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

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

где 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 наборов.

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

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

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

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

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

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