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

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

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
31
Ответ: 61
Задача 9.
Найти число решений системы уравнений:
)
(
2 1
x
x

· (x
1
·
3
x
+
1
x
· x
3
) = 0
)
(
3 2
x
x

· (x
2
·
4
x
+
2
x
· x
4
) = 0
…
)
(
9 8
x
x

· (x
8
·
10
x
+
8
x
· x
10
) = 0
Решение: С учетом формулы
)
(
b
a

= a ·
b
+
a
·b перепишем исходную систему:
)
(
2 1
x
x

·
)
(
3 1
x
x

= 0
)
(
3 2
x
x

·
)
(
4 2
x
x

= 0
…
)
(
9 8
x
x

·
)
(
10 8
x
x

= 0

Ограничения:

«очередной бит равен хотя бы одному из 2-х следующих»

«запрещены комбинации 100 и 011»

«после 01 или 10 биты чередуются»
Это значит, что может быть 2 варианта:
1)
сначала цепочка нулей, потом биты чередуются;
2)
сначала цепочка единиц, потом биты чередуются;
Для системы с 10-ю переменными таких цепочек будет 10 для каждого варианта.
Ответ: 20
Задача 10.
Найти число решений системы уравнений:
(x
1

x
2
) · (x
2

x
3
) · (x
3

x
4
) = 1
(
1
у
+ y
2
) · (
2
у
+ y
3
) · (
3
у
+ x
4
) = 1
(y
1

x
1
) · (y
2

x
2
) · (y
3

x
3
) · (y
4

x
4
) = 1
Решение: Так как
b
a
b
a



, то можно исходную систему записать в виде:
(x
1

x
2
) · (x
2

x
3
) · (x
3

x
4
) = 1
(y
1

y
2
) · (y
2

y
3
) · (y
3

y
4
) = 1
(y
1

x
1
) · (y
2

x
2
) · (y
3

x
3
) · (y
4

x
4
) = 1
Как следует из решения задачи 3 , первое уравнение имеет пять решений:
0000, 0001, 0011, 0111 и 1111.

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
32
Такие же решения имееи второе уравнение, не связанное с первым. Поэтому система из первых двух уравнений имеет всего 25 решений.
Третье уравнение связывает первое и второе. Импликация y
i

x
i
должна быть равна 1 для любого i , поэтому запрещена комбинация y
i
= 1, x
i
= 0.

Ограничения: для y
i
= 1

x
i
= 1. а для y
i
= 0

x
i
={ 0/1}
Рассмотрим цепочку решений Y = 0000 для второго уравнения, которая не содержит единиц. В этом случае никаких ограничений на цепочку X (решение первого уравнения) не накладывается., она дает пять решений.
Цепочка Y = 0001 накладывает ограничение на последний бит X, который обязательно должен быть равен 1.
Поэтому нужно отобрать только те цепочки X, где последний бит равен 1, их всего 4.
Аналогично, цепочка Y = 0011 дает три допустимых цепочки X, цепочка Y = 0111 – две, а цепочка Y = 1111
– всего одну. Получаем: 5 + 4 + 3 + 2 + 1 = 15 решений.
Ответ: 15
Задача 11.
Найти число решений системы уравнений:
Решение: Введем обозначения:
и перепишем исходную систему как:
Вспомним, что:
Сделаем еще одно преобразование:
Представим систему в виде одного уравнения:
Как следует из решения задачи 2, это уравнение имеет всего два решения для: Z =01010 и Z =10101.
Перейдем к исходным переменным:

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
33
Отсюда следует, что каждый бит в цепочке Z дает два решения в исходных переменных. Поскольку каждая из двух цепочек Z содержит 5 битов, всего получаем: 2 · 2 5
= 2 · 32 = 64.
Ответ: 64
Задача 12.
Найти число решений системы уравнений:
(x
1

x
2
) · (x
2

x
3
) · (x
3

x
4
) = 1 1
x
· y
1
· z
1
+ x
1
·
1
y
· z
1
+ x
1
· y
1
·
1
z
= 1 2
x
· y
2
· z
2
+ x
2
·
2
y
· z
2
+ x
2
· y
2
·
2
z
= 1 3
x
· y
3
· z
3
+ x
3
·
3
y
· z
3
+ x
3
· y
3
·
3
z
= 1 4
x
· y
4
· z
4
+ x
4
·
4
y
· z
4
+ x
4
· y
4
·
4
z
= 1
Решение: Рассмотрим первое уравнение. Как следует из задачи 3, оно ограничивает цепочку X = x
1
x
2
x
3
x
4
так, что в ней сначала идут все нули, а потом все единицы. Всего таких цепочек 5:
X
0
= 0000, X
1
= 0001, X
2
= 0011, X
3
= 0111, X
4
= 1111.
Будем по очереди подставлять эти решения в последние четыре уравнения.
Для цепочки X
0
( при x
1
= x
2
= x
3
= x
4
= 0) получаем:
y
1
· z
1
= 1
y
2
· z
2
= 1
y
3
· z
3
= 1
y
4
· z
4
= 1
Существуют единственные цепочки X = Y = 1111, которые удовлетворяют всей системе. Следовательно, цепочка X
0
дает одно решение всей системе.
Для цепочки X
1
последнее уравнение превращается в
4
y
· z
4
+ y
4
·
4
z
= 1. Это значит, что последние биты цепочек Y и Z должны быть различны. Всего два варианта (y
4
, z
4
) = ( 0, 1) и (y
4
, z
4
) = ( 1, 0).
Следовательно, цепочка X
1
дает два решения всей системе.
Для цепочки X
2
последние и предпоследние биты цепочек Y и Z должны быть попарно различны (y
3

z
3
и
y
4

z
4
). Следовательно, цепочка X
2
дает 2 2
= 4 решения всей системе.
Аналогично, цепочка X
3
дает 2 3
= 8 решений всей системе, а цепочка X
4
– 2 4
= 16 решений.
Общее количество решений системы равно: 1 + 2 + 4 + 8 + 16 = 31.
Ответ: 31
Задача 13.
Найти число решений системы уравнений:
(x
1

x
2
)

(x
3

x
4
) = 1
(x
3

x
4
)

(x
5

x
6
) = 1
(x
5

x
6
)

(x
7

x
8
) = 1
Решение: Обозначим z
1
= x
1

x
2
, z
2
= x
3

x
4
, z
3
= x
5

x
6
, z
4
= x
7

x
8
.
Тогда система примет вид:
z
1

z
2
= 1
z
2

z
3
= 1
z
3

z
4
= 1
Перепишем эту систему в виде одного уравнения:
(z
1

z
2
) · (z
2

z
3
) · (z
3

z
4
) = 1.
Из решения задачи 3 это уравнение имеет пять решений:
Z
0
= 0000, Z
1
= 0001, Z
2
= 0011, Z
3
= 0111, Z
4
= 1111.
Перейдем к исходным переменным. Так как импликация a

b равна нулю для одной комбинации и равна
1 для трех комбинаций, то каждый ноль в цепочке Z дает одно решение в исходных переменных, а каждая 1
– три решения.
Общее количество решений: 3 0
+ 3 1
+ 3 2
+ 3 3
+ 3 4
= 121.
Здесь слагаемое 3 0
соответствует решению Z
0
= 0000, слагаемое 3 1
- решению Z
1
= 0001 и т.д.

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
34
Ответ: 121
Задача 14.
Найти число решений системы уравнений:
Решение: Обозначим:
Перепишем систему:
Отсюда следует, что цепочка Z имеет два решения (биты чередуются):
010101010 и 101010101.
Перейдем к исходным переменным.
Так как z
i
= (x
i

y
i
), то для z
i
= 0

(x
i
, y
i
) = (0, 1), (1, 0), а для z
i
= 1

(x
i
, y
i
) = (0, 0), (1, 1).
Следовательно, каждый бит цепочки Z дает два решения.
Общее количество решений: 2 9
+ 2 9
= 512 + 512 = 1024.
Ответ: 1024

Заключение: Основные шагипри решении аналогичных задач:
1)
упрощение выражений с помощью эквивалентных преобразований;
2)
замена переменных (если это возможно);
3)
исследование структуры всех решений («голова» + «хвост»);
4)
подсчет количества решений по формулам комбинаторики.

Задачи для тренировки (часть 3.1)
Задача 1. Сколько различных решений имеет система логических уравнений:
(x
1

y
1
)

((x
2

y
2
)

(x
1

y
1
)) = 1
(x
2

y
2
)

((x
3

y
3
)

(x
2

y
2
)) = 1
...
(x
5

y
5
)

((x
6

y
6
)

(x
5

y
5
)) = 1
x
6

y
6
= 1
где x
1
, …, x
6
, y
1
, …, y
6
, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Задача 2. Сколько различных решений имеет система логических уравнений:
(x
1

x
2
)

(x
2

x
3
)

(x
3

x
4
) = 1
(y
1

y
2
)

(y
2

y
3
)

(y
3

y
4
) = 1
(z
1

z
2
)

(z
2

z
3
)

(z
3

z
4
) = 1
x
1

y
2

z
3
= 0

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
35 где x
1
, …, x
4
, y
1
, …, y
4
, z
1
, …, z
4
, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Задача 3. Сколько различных решений имеет система логических уравнений:
(x
1

x
2
)

(x
2

x
3
) = 1

x
1

y
1

z
1

x
1


y
1

z
1

x
1

y
1


z
1
= 1

x
2

y
2

z
2

x
2


y
2

z
2

x
2

y
2


z
2
= 1

x
3

y
3

z
3

x
3


y
3

z
3

x
3

y
3


z
3
= 1
где x
1
, …, x
3
, y
1
, …, y
3
, z
1
, …, z
3
– логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Задача 4. Сколько различных решений имеет система логических уравнений:
(x
1

x
2
)

(x
3

x
4
) = 1
(x
3

x
4
)

(x
5

x
6
) = 1
где x
1
, x
2
, …, x
6
– логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Задача 5. Сколько различных решений имеет система уравнений:
¬(X
1

X
2
)

(X
3

X
4
) = 1
¬(X
3

X
4
)

(X
5

X
6
) = 1
¬(X
5

X
6
)

(X
7

X
8
) = 1
¬(X
7

X
8
)

(X
9

X
10
) = 1
где x
1
, x
2
, …, x
10
– логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Задача 6. Сколько различных решений имеет система уравнений:
(X
1

X
2
)

(¬X
1

¬X
2
)

(X
3

X
4
)

(¬X
3

¬X
4
) = 1
(X
3

X
4
)

(¬X
3

¬X
4
)

(X
5

X
6
)

(¬X
5

¬X
6
) = 1
(X
5

X
6
)

(¬X
5

¬X
6
)

(X
7

X
8
)

(¬X
7

¬X
8
) = 1
(X
7

X
8
)

(¬X