Конспект_ОСНОВЫ ЛОГИКИ(3)(2). Решение логических задач. Учитель информатики Батракова Л. В

• Название: Решение логических задач. Учитель информатики Батракова Л. В
• Дата: 18.01.2019
• Размер: 1.45 Mb.
• Имя файла: Конспект_ОСНОВЫ ЛОГИКИ(3)(2).pdf
• Тип: Решение; #64191
• страница: 4 из 7

Часть 3. Логические уравнения и системы
3.1 Решение с помощью битовых цепочек
Основные идеи этого метода:
1)
Решение системы уравнений – это битовая цепочка (битовый вектор).
2)
Битовый вектор рассматривается как единый объект.
3)
Уравнения – это ограничения на битовый вектор (ограничения на комбинации битов).
4)
Нужно выделить элементарные уравнения и записать ограничения «на русском языке».
5)
Количество решений находится по правилам комбинаторики.
Пусть задана некоторая система логических уравнений от переменных x
1
, x
2
,…,x
N
вида:
F
1
(x
1
, x
2
,…,x
N
) = 1
…
F
M
(x
1
, x
2
,…,x
N
) = 1, где x
1
, x
2
,…,x
N
– логические переменные, которые принимают значения 0 или 1 ивыражения F
1
, …, F
M
,
зависящие от этих переменных, тоже логические. Множество их возможных значений - {0, 1}.

Решением этой системы называется такой вектор значений X = x
1
, x
2
,…,x
N
, при котором все
уравнения обращаются в тождество.
Поскольку все переменные , входящие в решение X , логические (0 или 1), то всё решение можно рассматривать как цепочку нулей и единиц длиной N. Такие цепочки называют битовыми цепочками или
битовыми векторами.
)
}
1
,
0
{
(
2 1


i
N
x
x
x
x
X

для любого
i
)
}
1
,
0
{
(
2 1


i
N
x
x
x
x
X

для любого
i

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
27
При анализе систем логических уравнений надо рассматривать битовый вектор-решение как целое, как единый объект. Результатом такого анализа будет описание множества векторов-решений, которое позволит подсчитать количество решений.

До того, как исследовать возможные решения, систему полезно упростить или использовать замену
переменных.
Простейшие ограничения, накладываемые уравнениями при решении задач, рассмотрим на простых задачах.
3.1.1. Решение логических уравнений
Задача 1. Найти число решений уравнения :
(x
1

x
2
) · (x
2

x
3
) · … · (x
4

x
5
) = 1.
Решение: Все сомножители имеют вид x
i

x
i+1
, они должны быть равны 1.

Ограничение: «любые два соседних бита должны быть равны».
Существует всего две таких цепочки: 00000, 11111, т.е. два решения.
Ответ: 2
Задача 2. Найти число решений уравнения :
(
2 1
x
x

) · (
3 2
x
x

) … (
5 4
x
x

) = 1.
Решение: Все сомножители имеют вид
1


i
i
x
x
, они должны быть равны 1.

Ограничение: «каждые два соседних бита должны быть различны».
Таким образом, нули и единицы в битовой цепочке чередуются. Существует всего две таких цепочки:
01010, 10101, т.е. два решения.
Ответ: 2
Задача 3. Найти число решений уравнения :
(x
1

x
2
) · (x
2

x
3
) · … ·(x
5

x
6
) = 1.
Решение: Все импликации (x
1

x
2
) · (x
2

x
3
) · … ·(x
5

x
6
) должны быть истинны. Импликация a

b ложна только при a=1 и b= 0, т.е. если a=1, то и b=1. Поэтому, если битовый вектор X = x
1
, x
2
,…,x
6
– решение данного уравнения, и в нем встретилась 1, то правее нее будут только единицы (сочетание «10» запрещено!). Каждое решение определяется тем, в какой позиции первый раз встретилась 1.

Ограничения:

запрещена комбинация 10;

после первой 1 все следующие биты – 1;

сначала все 0, потом все 1.
Таким образом, уравнение имеет 7 решений:
000000, 000001, 000011, 000111, 001111, 011111, 1111111.
Ответ: 7
Задача 4. Найти число решений уравнения :
((x
1
+ x
2
)

x
3
) · ((x
2
+ x
3
)

x
4
) · … · ((x
4
+ x
5
)

x
6
) = 1.
Решение: Все сомножители имеют вид ((x
i
+ x
i+1
)

x
i+2
), они должны быть равны 1, т.е. не допустима импликация 1

0. Поскольку левая часть импликации – это сумма двух соседних битов, а правая – следующий за ним бит, то можно сделать вывод, что слева от каждого нулевого бита (начиная с третьего) должны обязательно стоять два нуля. Этому условию удовлетворяют цепочки вида - «все нули, потом – все единицы»:
111111, 011111, 001111, 000111, 000011, 000001, 000000.
Кроме этого есть еще одна цепочка: 101111 (т.к. можно рассматривать пары x
1,
x
2
: {0,0} {0.1} {1,0} {1,1}).
Таким образом, уравнение имеет 8 решений. Для уравнений с N переменными N + 2 решения.

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
28

Ограничение: «слева от каждого нулевого бита (начиная с третьего) должны обязательно
стоять два нуля»
Ответ: 8
Задача 5. Найти число решений уравнения:
(x
1
+ x
2
) · (x
2
+ x
3
) · … · (x
5
+ x
6
) = 1.
Решение: Все сомножители имеют вид (x
i
+ x
i+1
), они должны быть равны 1. Так как в скобках содержится дизъюнкция, то в решении X = x
1
, x
2
,…,x
6
соседние биты не могут одновременнобыть равны 0.

Ограничение: «в битовой цепочке X нет двух подряд идущих нулей».
Здесь и далее битовые цепочки, удовлетворяющие условию задачи, будем называть правильными.
Обозначим через K
N
число правильных цепочек длины N, тогда K
1
= 2 - это цепочки длиной в единицу (0 и
1). K
2
= 3 - это цепочки длины 2 (01, 10, 11). K
3
= 5 – это цепочки длины 3 (010, 011, 101, 110, 111) и т. д.
Если на конце битовой цепочки длиной N стоит 0, то предыдущий символ обязательно должен быть равен
1, а вся начальная часть слева от него должна быть правильной цепочкой (без соседних нулей) длины N – 2.
Это даст нам K
N-2 решений с нулем на конце.
Если на конце битовой цепочки длиной N стоит 1, то начальная часть слева от него должна быть правильной цепочкой (без соседних нулей) длины N – 1. Это даст нам K
N-1 решений с единицей на конце.
Таким образом, получаем рекуррентную формулу для N > 2:
K
N
= K
N-1
+ K
N-2
Вспомним, что ряд Фибоначчи задается рекуррентной формулой: F
N
= F
N-1
+ F
N-2
, для N

3, с начальными условиями F
1
= F
2
= 1.
Можно заметить, что K
3
= K
1
+ K
2
= 5 (мы это уже вычисляли). Тогда,
K
4
= K
3
+ K
2
=8, K
5
= K
4
+ K
3
=13, K
6
= K
5
+ K
4
=21.
Ответ: 21
Задача 6. Найти число решений уравнения:
(x
1
· x
2

x
3
) · (x
2
· x
3

x
4
) · … · (x
4
· x
5

x
6
) = 1.
Решение: Все сомножители имеют вид (x
i
· x
i+1

x
i+2
), они должны быть равны 1, т.е. не допустима импликация 1

0. Левая часть импликации – это конъюнкция двух соседних битов.

Ограничение: «после того, как в битовой цепочке X = x
1
, x
2
,…,x
6
появляются две единицы подряд (
и таким образом x
i
· x
i+1
=1) , все следующие биты должны быть также равны 1».

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
29
Таким образом, любое решение состоит из двух частей:
1)
«голова», которая заканчивается на 0 и в которой нет двух единиц подряд;
2)
«хвост», состоящий из одних единиц.
Предположим, что «голова» состоит из m битов (0 ≤ m ≤ 6), а «хвост», соответственно , из 6 – m единичных битов. Такой «хвост» – единственный, так что число решений этого класса определяется количеством возможных «голов».
«Голова», в свою очередь , имеет свою структуру: последний бит – 0, а остальные представляют собой битовую цепочку, в которой нет двух соседних единиц.
При m = 0 «голова» - пустая.
При m = 1 только одна «голова» – «0».
При m = 2 две «головы» - «00» и «10».
При m > 2 число «голов» определяется последовательностью чисел Фибоначчи (см. задачу 5) – 3, 5, 8, 13.
Таким образом, у исходного уравнения есть:
1)
одно решение 111111 2)
одно решение 011111 3)
два решения 001111 и 101111 (с нулем во второй позиции) и т.д. (3, 5, 8, 13).
Всего получается 1+ 1 + 2 + 3 + 5 + 8 + 13 = 33 решения.
Ответ: 33
Задача 7. Найти число решений уравнения:
x
1

x
2

x
3

x
4

x
5

x
6
= 1.
Решение: Операции импликации выполняются слева направо. Исходное уравнение равносильно следующему:
((((x
1

x
2
)

x
3
)

x
4
)

x
5
)

x
6
= 1.
Для уравнения с N неизвестными общее количество комбинаций логических переменных равно 2
N
Обозначим число решений такого уравнения через K
N
, а число уравнений с нулем в правой части - Z
N
Тогда:
K
N
= 2
N
- Z
N
.

Ограничение: «запрещена комбинация 1

0 на последнем шаге».
Рассмотрим уравнение с нулем в правой части:
((((x
1

x
2
)

x
3
)

x
4
)

x
5
)

x
6
= 0.
Так как импликация равна нулю только для случая 1

0, то число решений этого уравнения совпадает с количеством решений уравнения:
((((x
1

x
2
)

x
3
)

x
4
)

x
5
= 1.
Так как x
6
= 0, то решение Z
N
в общем случаеможно записать:
Z
N
= K
N-1
= 2
N-1
- Z
N-1.
Используя равенство K
N
= 2
N
- Z
N
, получаем рекурретную формулу:
K
N
= 2
N
- K
N-1
.
Начальное значение для вычисления определим из уравнения с двумя неизвестными. Для x
1

x
2
= 1 получим три решения (0, 0), (0, 1) и (1, 1), то есть K
2
= 3.
Тогда:

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
30
K
3
= 2
3
– K
2
= 8 – 3 = 5
K
4
= 2
4
– K
3
= 16 – 5 = 11
K
5
= 2
5
– K
4
= 32 – 11 = 21
K
6
= 2
6
– K
5
= 64 – 21 = 43
Ответ: 43
3.1.2. Решение систем логических уравнений
Задача 8. Найти число решений системы уравнений:
1 1
)
(
)
(
1
)
(
)
(
)
(
1
)
(
)
(
)
(
1
)
(
)
(
)
(
8 8
7 7
8 7
6 6
8 7
6 7
6 2
2 4
3 2
3 2
1 1
3 2
1 2
1



























y
x
y
x
x
x
y
x
x
x
x
x
x
y
x
x
x
x
x
x
y
x
x
x
x
x
x

Решение: Первые 6 уравнений однотипны, отличаются только сдвигом номеров переменных. Будем рассматривать каждое решение как пару битовых цепочек (цепочек нулей и единиц):
8 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
X

и
8 7
6 5
4 3
2 1
y
y
y
y
y
y
y
y
Y


Ограничения:

первые сомножители в первых уравнениях,
1


i
i
x
x
, означают, что в цепочке
X
не может быть двух
нулей подряд (иначе эта скобка в первых 6 уравнениях и всё произведение равны нулю);

вторые скобки,
2 1




i
i
i
x
x
x
, означают, что если в цепочке
X
встретились две единицы подряд, то
потом будут только единицы, поскольку в противном случае
0 0
1


и все произведение равно 0.
Следовательно, любая битовая цепочка X, которая является решением, состоит из двух частей: «головы», в которой чередуются 0 и 1, и «хвоста», который состоит из одних 1. Такая цепочка полностью определяется позицией последнего нуля, т.е. есть всего 9 таких цепочек (позиция последнего нуля от 0 до 8, 0 значит, что нулей нет):
X
0
= 11111111
X
1
= 01111111
X
2
= 10111111
X
3
= 01011111
X
4
= 10101111
X
5
= 01010111
X
6
= 10101011
X
7
= 01010101
X
8
= 10101010
Третий сомножитель вида (
i
i
y
x

) связывает битовые цепочки
X
и Y, составляющие решение и является
Импликацией:
i
i
i
i
y
x
y
x



. Это означает, что:

если
1

i
x
, то
1

i
y
;

если же
0

i
x
, то для
i
y
есть два возможных значения – 0 и 1.
Поэтому для каждого из указанных выше девяти векторов
X
количество возможных цепочек
Y
авно
)
(
2
X
z
, где
)
( X
z
–количество нулей в соответствующем векторе
X
Поэтому для
0
X
(нет нулей) получаем 2 0
= 1 решение, для
1
X
и
2
X
(один нуль) – 2 1
= 2 решения; для
3
X
и
4
X
(два нуля) – 2 2
= 4 решения; для
5
X
и
6
X
(три нуля) – 2 3
= 8 решений; для
7
X
и
8
X
(четыре нуля) –
2 4
= 16 решений.
Общее количество решений системы: 1 + 2*(2 1
+ 2 2
+2 3
+ 2 4
) = 1 +2*30 = 61.