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

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

X
1
X
3
X
2

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
42 0
0 0
0 1
0 0
1 1
1 0
0 1
0 1
1 1
1 обратите внимание, что в каждой строчке в первых двух столбцах должно быть по крайней мере одно значение, равное значению в третьем столбце (который выделен желтым)
6)
добавим еще одно уравнение и еще одну переменную X
4
:
X
1
X
4
X
3
X
2
0
?
0 0
0
?
1 0
0
?
1 1
1
?
0 0
1
?
0 1
1
?
1 1
7)
чтобы «подключить» второе уравнение, нужно использовать то же самое правило: каждой строчке в первых двух столбцах должно быть, по крайней мере, одно значение, равное значению в третьем столбце (который выделен желтым); это значит, что в первой и последней строчках
(где X
1
= X
3
) значение X
4
может быть любое (0 или 1), а в остальных строчках – только строго определенное:
X
1
X
4
X
3
X
2
0 0
0 0
0 1
0 0
0 1
1 0
0 1
1 1
1 0
0 0
1 0
0 1
1 0
1 1
1 1
1 1
8)
таким образом, количество решений при подключении очередного уравнения к системе возрастает на 2!
9)
подключили X
5
– получили 10 решений,
X
6
– получили 12 решений,
X
7
– получили 14 решений,
X
8
– получили 16 решений,
X
9
– получили 18 решений,
X
10
– получили 20 решений.
10)
остается одно последнее уравнение (X
10

X
1
) = 0, из которого следует, что X
10
не равен X
1 11)
из таблицы следует, что только в первой и последней строчках значения первой и последней переменных совпадают, то есть из полученных 20 решений нужно отбросить 2 12)
таким образом, получается 20 – 2 = 18 решений
Ответ: 18
Пример 3:
Сколько различных решений имеет система уравнений
¬(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
– логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение (замена переменных):
1)
количество комбинаций 10 логических переменных равно 2 10
= 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
43 2)
заметим, что при обозначениях
)
(
2 1
1
X
X
Y


,
)
(
4 3
2
X
X
Y


,
)
(
6 5
3
X
X
Y


,
)
(
8 7
4
X
X
Y


и
)
(
10 9
5
X
X
Y


мы получаем систему из 4 уравнений и 5 независимыми переменными; эта система уравнений относится к типу, который рассмотрен в предыдущей разобранной задаче:
¬Y
1

Y
2
= 1
¬Y
2

Y
3
= 1
¬Y
3

Y
4
= 1
¬Y
4

Y
5
= 1
3)
как следует из разбора задачи в примере 1, такая система имеет 5+1 = 6 решений для переменных
Y
1
… Y
5 4)
теперь нужно получить количество решений в исходных переменных, X
1
… X
10
; для этого заметим, что переменные Y
1
… Y
5 независимы;
5)
предположим, что значение Y
1
известно (0 или 1); поскольку
)
(
2 1
1
X
X
Y


, по таблице истинности операции «эквивалентность» (истина, когда два значения одинаковы), есть две соответствующих пары (X
1
;X
2
) (как для случая Y
1
= 0, так и для случая Y
1
= 1)
6)
у нас есть 5 переменных Y
1
… Y
5, каждая их комбинация дает 2 пары (X
1
;X
2
), 2 пары (X
3
;X
4
),
2 пары (X
5
;X
6
), 2 пары (X
7
;X
8
) и 2 пары (X
9
;X
10
), то есть всего 2 5
= 32 комбинации исходных переменных
7)
таким образом, общее количество решений равно 6 ·32 = 192
Ответ: 192
Замечание: При решении каждой системы логических уравнений следует учитывать ее
особенности, на основе которых и выбирать метод решения.

Задачи для тренировки (часть 3.2)
1.
Укажите значения переменных К, L, M, N, при которых логическое выражение
(¬(М

L)

К) → (¬К

¬М

N)
ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.
2.
Сколько различных решений имеет уравнение:
((J→K) →( M

N

L) )

((J

¬K) → ¬( M

N

L))

(M→J)= 1
где K, L, M, N, J – логические переменные? В ответе не нужно перечислять все различные наборы значений
K, L, M, N и J, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.
3. Сколько различных решений имеет система уравнений
(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
7

¬X
8
)

(¬X
9

X
10
)

(X
9

¬X
10
) = 1
где x
1
, x
2
, …, x
10
– логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
4. Сколько существует различных наборов значений логических переменных x
1
, x
2
, ... x
10
, которые удовле- творяют всем перечисленным ниже условиям?
¬(x
1
≡ x
2
) ∧ ( (x
1
∧ ¬x
3
) ∨ (¬x
1
∧ x
3
) ) = 0
¬(x
2
≡ x
3
) ∧ ( (x
2
∧ ¬x
4
) ∨ (¬x
2
∧ x
4
) ) = 0

Конспект по теме: ‘Основы алгебры логики. Решение логических задач.’
Учитель информатики Батракова Л.В.
44
...
¬(x
7
≡ x
8
) ∧ ( (x
7
∧ ¬x
9
) ∨ (¬x
7
∧ x
9
) ) = 0
В ответе не нужно перечислять все различные наборы значений переменных x
1
, x
2
, … x
10
при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
5. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1
(¬y1 \/ y2) /\ (¬y2 \/ y3) /\ (¬y3 \/ y4) = 1
(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Используемая литература:
1. Богомолова О.Б Логические задачи на ЕГЭ: имена и логические выражения/ Учебно-методическая газета для учителей информатики: Информатика №8, 2011 г.
2. Поляков К.Ю., Шестаков А.П., Еремин Е.А. Логические основы компьютеров / Учебно-методическая газета для учителей информатики: Информатика №12, 2010 г.
3. Поляков К.Ю. Системы логических уравнений / Учебно-методическая газета для учителей информатики:
Информатика №14, 2011 г.
4. Крылов С.С., Ушаков Д.М. ЕГЭ. Информатика. Тематические тестовые задания ФИПИ/ М. Издательство
“Экзамен”, 2012.
5. Поляков К.Ю. ЕГЭ-А10: задачи с интервалами/ Учебно-методическая журнал для учителей информатики: Информатика №2, 2013 г.
6. Поляков К.Ю., Еремин Е.А. Информатика. Углубленный уровень. Учебник для 10 класса, часть 1/
Издательство БИНОМ 2013 г.
7. Поляков К.Ю. Что год грядущий нам готовит: ЕГЭ-2015 / Учебно-методическая газета для учителей информатики: Информатика №11, 2014 г.
8. Поляков К.Ю., Ройтенберг М.А. Системы логических уравнений: решение с помощью битовых цепочек.
/ Учебно-методическая газета для учителей информатики: Информатика №12, 2014 г.
9. Богомолова О.Б., Усенков Д.Ю. Решение задач ЕГЭ с множествами: быстрый метод./ Учебно- методическая газета для учителей информатики: Информатика № 5-6, 2015 г.
10. Поляков К.Ю. Множества и логика в задачах ЕГЭ / Учебно-методическая газета для учителей информатики: Информатика № 10, 2015 г.
Ссылки:
http://kpolyakov.narod.ru/
http://www.inf1.info http://info.150-4ex-lyubschool.edusite.ru/DswMedia/v9.pdf http://www.fipi.ru/
http://inf.reshuege.ru/?redir=1

Чтобы успешно справиться с задачами данной темы, надо знать:
1.
логические операции
2.
законы алгебры логики
3.
правила составления таблиц истинности
4.
методы решения логических задач
Желаю удачи 