Информатика задание 23 метод отображения. Несколько уравнений: использование битовых масок

1. Общие сведения

Сложность : высокая.

Примерное время решения (для тех, кто будет выполнять часть 2): 5-10 минут

Тема: Основы логики

Подтема: Анализ логических выражений

Что проверяется: Умение анализировать логические выражения. Умение описать на естественном языке множество значений логических переменных, при которых заданный набор логических выражений истинен.

Как может выглядеть задание:

Например, так.

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

2. Пример задания

2.1. Условие задачи.

Задача 2012- B15-1.

Сколько существует различных наборов значений логических переменных x 1 , x 2 , ... x 9 , x 10 , которые удовлетворяют всем перечисленным ниже условиям?

((x 1 ≡ x 2 ) \/ (x 3 ≡ x 4 )) /\ (¬(x 1 ≡ x 2 ) \/ ¬(x 3 ≡ x 4 )) =1

((x 3 ≡ x 4 ) \/ (x 5 ≡ x 6 )) /\ (¬(x 3 ≡ x 4 ) \/ ¬(x 5 ≡ x 6 )) =1

((x 5 ≡ x 6 ) \/ (x 7 ≡ x 8 )) /\ (¬(x 5 ≡ x 6 ) \/ ¬(x 7 ≡ x 8 )) =1

((x 7 ≡ x 8 ) \/ (x 9 ≡ x 10 )) /\ (¬(x 7 ≡ x 8 ) \/ ¬(x 9 ≡ x 10 )) =1

В ответе не нужно перечислять все различные наборы значений x 1 , x 2 , ... x 9 , x 10 , при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

2.2. Набросок решения.

В системе фигурируют логические функции от следующих выражений:

(x 1 ≡ x 2 ), (x 3 ≡ x 4 ), (x 5 ≡ x 6 ), (x 7 ≡ x 8 ), (x 9 ≡ x 10 )

Подобно тому, как это делается при решении алгебраических уравнений, сделаем замену переменных:

t 1 = x 1 ≡ x 2

t 2 = x 3 ≡ x 4

t 3 = x 5 ≡ x 6

t 4 = x 7 ≡ x 8

t 5 = x 9 ≡ x 10

Общая формула замены (k=1, 2, 3, 4, 5 ):

t k = (x 2 k-1 ≡ x 2 k)

(t 1 \/ t 2 ) /\ (¬t 1 \/ ¬ t 2 ) =1

(t 2 \/ t 3 ) /\ (¬t 2 \/ ¬ t 3 ) =1

(t 3 \/ t 4 ) /\ (¬t 3 \/ ¬ t 4 ) =1

(t 4 \/ t 5 ) /\ (¬t 4 \/ ¬ t 5 ) =1

Уравнения полученной системы имеют вид (k=1, 2, 3, 4 ):

(t k \/ t k+1 ) /\ (¬t k \/ ¬ t k+1 ) =1

Это означает, что из каждых двух переменных t k и t k +1 ровно одна равна 1 и ровно одна равна нулю, т.е. эти переменные имеют разные значения. Таким образом, систему можно еще немного упростить и записать ее так:

¬(t 1 ≡ t 2 ) =1

¬(t 2 ≡ t 3 ) =1

¬(t 3 ≡ t 4 ) =1

¬(t 4 ≡ t 5 ) =1

Б. Анализ системы.

В любом решении последней системы значения переменных чередуются. Поэтому такая система имеет ровно два решения: 01010 и 10101 (первая цифра – значение переменной t 1 , вторая - значение t 2 и т.д.).

t k = x 2 k-1 ≡ x 2 k

(здесь k=1, 2, 3, 4, 5 ), то каждому значению t k соответствуют две пары значений переменных x 2 k-1 иx 2 k . Например, t k = 1 в двух случаях: { x 2 k-1 = x 2 k =1 } и { x 2 k-1 = x 2 k =0 }.

2.2.2. Подсчет числа решений

Каждому из двух решений системы для переменных t соответствует 2 5 = 32 решения исходной системы. Поэтому исходная система имеет 2∙32 = 64 решения.

Упражнение. Выпишите все решения. Это немного утомительно, но полезно.

3. Пример из открытого сегмента банка заданий ФИПИ

3.1. Условие задачи.

Задача 2012- B15-2 (открытый сегмент, зачёт 3:2011)

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

¬(x 8 ≡ x 9) /\ (x 8 \/ x 10) /\ (¬x 8 \/ ¬x 10) =0

В ответе не нужно перечислять все различные наборы значений x 1 , x 2 , ..., x 10 , при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

3.2. Набросок решения.

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

2.2.1. Как устроено множество решений

А. Предварительный этап – упрощаем уравнения.

Заметим, что выражение (a \/ b) /\ (¬a \/ ¬b) равносильно тому, что ровно одна из переменных a и b равна 1, то есть равносильно выражению ¬(a ≡ b). Поэтому каждое выражение вида (x k \/ x k+2) /\ (¬x k \/ ¬x k+2) , где k=1, …, 8, в наших уравнениях можно заменить выражением ¬(x k ≡ x k+2).

Таким образом, наша система эквивалентна системе

¬(x 1 ≡ x 2) /\ ¬(x 1 ≡ x 3) =0

¬(x 2 ≡ x 3) /\ ¬(x 2 ≡ x 4) =0

Поэтому систему можно записать в следующем виде

¬(x 1 ≡ x 2) → (x 1 ≡ x 3) =1

¬(x 2 ≡ x 3) → (x 2 ≡ x 4) =1

¬(x 8 ≡ x 9) → (x 8 ≡ x 10) =1

Б. Анализ системы.

Каждое из уравнений полученной системы имеет вид (k = 1, …, 8):

¬(x k ≡ x k+1) → (x k ≡ x k+2) =1

Иными словами, если два соседних элемента набора x k и x k+1 не равны между собой, то x k =x k+2 , то есть элементы x k+1 и x k+2 также не равны между собой. Таким образом, набор удовлетворяет системе, тогда и только тогда, когда он обладает следующими свойствами. В начале набора стоит несколько (может быть, одно) одинаковых значений (назовем это"головой" набора). Затем (после первого появления нового числа) значения в наборе чередуются ("хвост" набора).

Пример решения: 1111010101 (в этой последовательности первая цифра – значение переменной x 1 , вторая цифра – значение переменной x 2 , и т.д.)

Здесь голова набора состоит из четырех единиц, а хвост – это последовательность 01010101. в данном примере длина головы равна 4.

Важное наблюдение. Для каждой непустой головы есть ровно один хвост, образующий вместе с ней решение. Действительно, первая цифра такого хвоста – это цифра, противоположная цифрам головы. А дальше цифры в хвосте чередуются.

3.2.2. Как устроено множество решений

В соответствии с важным наблюдением, количество решений совпадает с количеством возможных голов. Очевидно, существует 10 голов, состоящих из единиц (1, 11, 111, …, 1111111111) и столько же голов, состоящих из нулей.

Замечание. Как видим, сложность решения задачи не зависит от числа переменных и уравнений. Если понятно, как устроено множество решений, подсчитать количество решений для аналогичной системы, скажем, с 20-ю переменными, не сложнее, чем в уже рассмотренном случае.

4. Обсуждение

4.1. Какие знания/умения/навыки нужны ученику, чтобы решить эту задачу

Эта задача – одна из самых сложных в экзамене, если не самая сложная. Для ее решения ученик должен уметь

Преобразовывать логические выражения (включая выполнение замены переменных);

Переводить формальное описание, в виде системы логических условий, на нормальный, "человеческий" язык и

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

Наиболее трудным для усвоения, видимо, является второе из перечисленных требований – оно не формализуется, от ученика, как правило, требуется догадка.

Придумывайте свои подходы, применяйте их и сообщайте нам!

4.2.1. Разбирать эту задачу стоит только с учениками, которые достаточно свободно владеют преобразованиями логических выражений. Отметим несколько полезных преобразований (они встречались в разобранных примерах):

¬a \/ b равносильно a→ b

(a→ b) /\ (b→ a) равносильно a ≡ b

(¬a \/ b) /\ (a\/¬b) равносильно a ≡ b

(a \/ b) /\ (¬a \/ ¬b) равносильно ¬(a ≡ b).

Подробнее о преобразованиях логических выражений написано здесь [см. logic01. doc ]

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

4.2.2. Самое трудное – сообразить, что из себя представляет множество решений. В разделах 5 и 6 разобрано несколько примеров. Другие полезные примеры и рекомендации можно найти на сайте К.Ю.Полякова.

4.2.3. Подсчет количества решений – несложная комбинаторная задача. Сильные ученики могут сообразить, как провести подсчет, даже не обладая специальными знаниями. Стоит повторить формулы произведения возможностей и формулу суммы арифметической прогрессии.

4.2.4. Таким образом, план подготовки может быть примерно таким.

1) Повторить логические преобразования и элементы комбинаторики.

2) Порешать задачи и попрактиковаться в переводе формального описания, в виде системы логических условий, на нормальный, "человеческий" язык.

Точного алгоритма действий, гарантированно приводящего к успеху здесь нет. Первая цель – понять, что собой представляет множество решений системы. Для этого систему бывает полезно преобразовать (упростить) систему, используя тождественные преобразования и замены переменных. Затем – подсчитать количество элементов во множестве решений.

Во многих случаях система состоит из однотипных уравнений, каждое из которых связывает небольшое число переменных (две-три-четыре), при том, что в системе может быть 10 и более переменных. Обычно, количество переменных не является источником сложности, оно является параметром решения. Если не получается решить задачу в общем виде, можно попробовать перебрать все решения для системы с небольшим количеством переменных. Это может подсказать, как выглядит решение в общем виде.

5. Другие задачи

Задача 2012- B15-3

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

(x 1 → x 2) /\ (x 2 → x 3) /\ (x 3 → x 4) /\ (x 4 → x 5) = 1

В ответе не нужно перечислять все различные наборы значений x 1 , x 2 , ..., x 5 , при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Решение. Очевидно, выполнены следующие соотношения:

(x 1 → x 2) = 1

(x 2 → x 3) = 1

(x 3 → x 4) = 1

(x 4 → x 5) = 1

Допустим, что набор {a1, a2, a3. a4, a5} – решение нашего уравнения. Допустим, что a4 = 1. Тогда, из уравнения

(x 4 → x 5) = 1

следует, что a5 = 1 (напомним: 1 → 0 ложно!). Допустим теперь, что а3=1. Из условия

(x 3 → x 4) = 1

следует, что a4=1 и, значит, по доказанному, a5 = 1.

Аналогично можно показать (проверьте сами!), что если в решении встречается 1, то далее идут только единицы.

Таким образом, решения уравнения – это наборы, в которых сначала идут нули, а потом – единицы.

Важно не забыть про «особые» наборы – 00000 и 11111. Они тоже годятся.

Таким образом, вот все решения уравнения:

00000, 00001, 00011, 00111, 01111, 11111

Каждое решение полностью описывается количеством единиц в нем. Это количество может быть от 0 до 5. Количество решений – 6.

Задача 2012- B15-4

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

(x 1 → x 2) /\ (x 2 → x 3) /\ (x 3 → x 4) /\ (x 4 → x 5) = 1 (1)

(z 1 → z 2) /\ (z 2 → z 3) /\ (z 3 → z 4) = 1 (2)

В ответе не нужно перечислять все различные наборы значений x 1 , x 2 , ..., x 5 , z 1 , ..., z 4 , при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Решение. Про такие системы говорят, что переменные в них «разделенные»: x 1 , …, x 5 встречаются только в уравнении (1), а z 1 , …, z 4 - только в уравнении (2). Из решения задачи 3 следует, что уравнению (1) удовлетворяют 6 наборов значений переменных x 1 , x 2 , ..., x 5 , а уравнению (2) – 5 наборов значений переменных z 1 , …, z 4 Каждый из этих наборов для { x i } может образовать решение с любым из наборов для { z i }. Поэтому общее количество решений равно 6∙5 = 30.

6. Задачи для самостоятельного решения

Задача 2012- B15-Т1

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

(x 1 → x 2) /\ (x 2 → x 3) /\ … /\ (x 499 → x 500) = 1

В ответе не нужно

Задача 2012- B15- Т2

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

(x 2 → x 1) /\ (x 3 → x 2) /\ … /\ (x 1000 → x 999) = 1

В ответе не нужно перечислять все различные наборы значений x 1 , x 2 , ..., x 1000 , при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Задача 2012- B15- Т3

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

(x 1 → x 3) /\ (x 3 → x 5) /\ … /\ (x 9 → x 11) = 1

(x 2 → x 4) /\ (x 4 → x 6) /\ … /\ (x 8 → x 10) = 1

В ответе не нужно перечислять все различные наборы значений x 1 , x 2 , ..., x 11 , при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Задача 2012- B15- Т4

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

(x 1 → x 3) /\ (x 3 → x 5) /\ … /\ (x 99 → x 101) = 1

(x 2 → x 4) /\ (x 4 → x 6) /\ … /\ (x 98 → x 100) = 1

В ответе не нужно перечислять все различные наборы значений x 1 , x 2 , ..., x 500 , при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Ответы: Т1. 501; Т2. 1001; Т3. 42; Т4. 2652.

Носкин Андрей Николаевич,
учитель информатики
высшей квалификационной категории,
кандидат военных наук, доцент
ГБОУ Лицей №1575 город Москва

Оптимизированный метод отображения для решения задачи 23 из КИМ ЕГЭ по информатике и ИКТ

Одной из самой трудной задачей в КИМ ЕГЭ является задача 23, в которой надо найти количество различных наборов значений логических переменных, которые удовлетворяют указанному условию.
Данная задача является едва ли не самым сложным заданием КИМ ЕГЭ по информатике и ИКТ. С ним, как правило, справляются не более 5% экзаменуемых {1}.
Такой маленький процент учеников, которые справились с данным заданием объясняется следующим:
- ученики могут путать (забыть) знаки логических операций;
- математические ошибки в процессе выполнения расчетов;
- ошибки в рассуждениях при поиске решения;
- ошибки в процессе упрощения логических выражений;
- учителя рекомендуют решать данную задачу, после выполнения всей работы, так как вероятность допущения
ошибок очень велика, а «вес» задачи составляет всего лишь один первичный балл.
Кроме того, некоторые учителя сами с трудом решают данный тип задач и поэтому стараются решать с детьми более простые задачи.
Также усложняет ситуацию, что в данном блоке существует большое количество разнообразных задач и невозможно подобрать какое-то шаблонное решение.
Для исправление данной ситуации педагогическим сообществом дорабатываются основные две методики решения задач данного типа: решение с помощью битовых цепочек {2} и метод отображений {3}.
Необходимость доработки (оптимизации) данных методик обусловлена тем, что задачи постоянно видоизменяются как по структуре, так и по количеству переменных (только один тип переменных Х, два типа переменных Х и Y, три типа: X, Y, Z).
Сложность освоения данными методиками решения задач подтверждается тем, что на сайте К.Ю. Полякова существует разборов данного типа задач в количестве 38 штук{4}. В некоторых разборах приведены более одного типа решения задачи.
Последнее время в КИМ ЕГЭ по информатике встречаются задачи с двумя типа переменных X и Y.
Я оптимизировал метод отображения и предлагаю своим ученикам пользоваться усовершенствованным методом.
Это дает результат. Процент моих учеников, которые справляются с данной задачей варьируется до 43% от сдающих. Как правило, ежегодно у меня сдает ЕГЭ по информатике от 25 до 33 человек из всех 11-х классов.
До появления задач с двумя типами переменными метод отображения ученики использовали очень успешно, но после появления в логическом выражении Y, я стал замечать, что у детей перестали совпадать ответы с тестами. Оказалось, они не совсем четко стали представлять, как составить таблицу отображений с новым типом переменной. Тогда мне пришла мысль, что для удобства надо все выражение привести к одному типу переменной, как удобно детям.
Приведу более подробно данную методику. Для удобства буду ее рассматривать на примере системы логических выражений, приведенных в {4}.
Сколько различных решений имеет система логических уравнений

(x 1 ^ y 1) = (¬x 2 V ¬ y 2 )
(x 2 ^ y 2) = (¬ x 3 V ¬ y 3 )
...
(x 5 ^ y 5 ) = (¬ x 6 V ¬ y 6 )

где x 1 , …, x 6 , y 1 , …, y 6 , - логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение:
1. Из анализа системы логических уравнений мы видим, что присутствует 6 переменных Х и 6 переменных У . Так как любая из этих переменных может принимать только два значения (0 и 1), то заменим эти переменные на 12 однотипных переменных, например Z.
2. Теперь перепишем систему с новыми однотипными переменными. Сложность задачи будет заключаться во внимательной записи при замене переменных.

(z 1 ^ z 2) = (¬z 3 V ¬ z 4 )
(z 3 ^ z 4) = (¬ z 5 V ¬ z 6 )
...
(z 9 ^ z 10 ) = (¬ z 11 V ¬ z 12)

3. Построим таблицу, в которой переберем все варианты z 1 , z 2 , z 3 , z 4 , поскольку в первом логическом уравнении четыре переменных, то таблица будет иметь 16 строк (16=2 4); уберем из таблицы такие значения z 4 , при которых первое уравнение не имеет решения (зачеркнутые цифры).

0	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1
1	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1

4. Анализируя таблицу, строим правило отображения пар переменных (например, паре Z 1 Z 2 =00 соответствует пара Z 3 Z 4 = 11) .

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

6. Складываем все результаты: 9 + 9 + 9 + 27 = 54
7. Ответ: 54.
Приведенная выше оптимизированная методика решения задачи 23 из КИМ ЕГЭ позволила ученикам вновь обрести уверенность и решать успешно этот тип задачи.

Литература:

1. ФИПИ. Методические рекомендации для учителей, подготовленные на основе анализа типичных ошибок участников ЕГЭ 2015 года по ИНФОРМАТИКЕ и ИКТ. Режим доступа: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

2. К.Ю. Поляков, М.А. Ройтберг. Системы логических уравнений: решение с помощью битовых цепочек. Журнал Информатика, № 12, 2014, с. 4-12. Издательский дом "Первое сентября", г.Москва.
3. Е.А. Мирончик, Метод отображения. Журнал Информатика, № 10, 2013, с. 18-26. Издательский дом "Первое сентября", г.Москва.

На уроке рассмотрено решение 23 задания ЕГЭ по информатике: дается подробное объяснение и разбор задания 2017 года

23-е задание — «Преобразование логических выражений» — характеризуется, как задание высокого уровня сложности, время выполнения – примерно 10 минут, максимальный балл — 1

Элементы алгебры логики: преобразования логических выражений

Для выполнения 23 задания ЕГЭ необходимо повторить следующие темы и понятия:

• Рассмотрите тему .
• Рассмотрите тему .

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

1. Одно уравнение с непересекающимися операндами внешней операции и одним вариантом решения:

2. Одно уравнение с непересекающимися операндами внешней операции и несколькими вариантами решения

3. Одно уравнение с пересекающимися операндами внешней операции

Рассмотрим каждый случай отдельно и учтем его результаты для второго уравнения системы:

Поскольку для двух уравнений решения в трех случаях не могут «работать» одновременно, то результат — это сложение трех решений:

4. Несколько уравнений: метод отображения решений уравнения

Метод отображения можно использовать:

5. Несколько уравнений: использование битовых масок

Побитовая маска (битовая маска) - метод, который можно использовать:

Решение 23 заданий ЕГЭ по информатике

Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 1 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1 , x2 , … x6 , y1 , y2 , … y6

(¬(x1 ∨ y1)) ≡ (x2 ∨ y2)
(¬(x2 ∨ y2)) ≡ (x3 ∨ y3)
…
(¬(x5 ∨ y5)) ≡ (x6 ∨ y6)

* Аналогичное задание находится в сборнике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е. 2019 года, вариант 7.

¬a ≡ b ¬b ≡ c ¬c ≡ d ¬d ≡ e ¬e ≡ f a ≠ b b ≠ c c ≠ d d ≠ e e ≠ f

Вспомним, как выглядит таблица истинности для эквивалентности:

x1	x2	F
0	0	1
0	1	0
1	0	0
1	1	1

Рассмотрим, в каких случаях выражения будут возвращать ложь. Каждое из пяти выражений будет ложно, когда: либо оба операнда истинны, либо оба операнда ложны (операция равносильность = истине: при 00 или 11).

Составим битовую маску для наших уравнений. В цепочке значений от a до f не может быть двух единиц или двух нулей, идущих подряд, так как в этом случае система будет ложна (к примеру, a ≠ b , если 0 ≠ 0 — это ложь). Таким образом, для данных уравнений существует всего две цепочки решений:

цеп.1 цеп.2 a 0 1 b 1 0 c 0 1 d 1 0 e 0 1 f 1 0

Теперь вспомним о заменах: каждая из переменных от a до f представляет собой скобку, внутри которой две переменные, связанные дизъюнкцией . Дизъюнкция двух переменных истинна в трех случаях (01, 10, 11), а ложна — в одном (00). Т.е., к примеру:

x1 ∨ y1 = 1 тогда, когда: либо 0 ∨ 1 , либо 1 ∨ 0 , либо 1 ∨ 1 x1 ∨ y1 = 0 тогда и только тогда, когда 0 ∨ 0

Это говорит о том, что на каждую единицу в цепочке приходится три варианта значений, а на каждый ноль - один . Т.о. получаем:

для первой цепочки: 3 3 * 1 3 = 27 наборов значений ,

и для второй: 3 3 * 1 3 = 27 наборов значений

Итого наборов:

27 * 2 = 54

Результат: 54

Подробное объяснение данного задания смотрите на видео:

23_2: Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 3 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1 , x2 , … x9 , y1 , y2 , … y9 , которые удовлетворяют всем перечисленным ниже условиям?

(¬(x1 ∧ y1)) ≡ (x2 ∧ y2)
(¬(x2 ∧ y2)) ≡ (x3 ∧ y3)
…
(¬(x8 ∧ y8)) ≡ (x9 ∧ y9)

* Аналогичное задание находится в сборнике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е. 2019 года, вариант 9.

✍ Решение (использование метода побитовая маска):

• Поскольку в скобках одинаковые действия, и переменные повторяются, то введем обозначения:

¬a ≡ b ¬b ≡ c ¬c ≡ d ¬d ≡ e ¬e ≡ f ¬f ≡ g ¬g ≡ h ¬h ≡ i

Вместо отрицания первого операнда просто будем использовать «не эквивалентно»:

a ≠ b b ≠ c c ≠ d d ≠ e e ≠ f f ≠ g g ≠ h h ≠ i

Вспомним таблицу истинности для эквивалентности:

x1	x2	F
0	0	1
0	1	0
1	0	0
1	1	1

Теперь рассмотрим, в каких случаях полученные условия будут возвращать ложь. Каждое из условий будет ложно, если либо оба операнда истинны, либо оба операнда ложны: например a ≠ b = 0 , если: a=0 и b=0 или a=1 и b=1

Это означает, что для одного условия не может быть такого случая, что a=0 и b=0 или a=1 и b=1 .

Составим битовую маску для условий. В цепочке значений от a до i не может быть двух единиц или двух нулей, идущих подряд, так как в этом случае система будет ложна. Таким образом, для данных условий существует всего две цепочки решений:

цеп.1 цеп.2 цеп. цеп. a 0 1 0 1 b 1 0 0 1 не может быть! c 0 1 ... ... d 1 0 e 0 1 f 1 0 g 0 1 h 1 0 i 0 1

a до i истинна в одном случае, а ложна — в трех . Т.е., к примеру:

x1 ∧ y1 = 0 тогда, когда: либо 0 ∧ 1 , либо 1 ∧ 0 , либо 0 ∧ 0 x1 ∧ y1 = 1 тогда и только тогда, когда 1 ∧ 1

0 в цепочке приходится три 1 - один . Т.о. получаем:

для первой цепочки: 3 5 * 1 4 = 243 набора значений ,

и для второй: 3 4 * 1 5 = 81 набор значений

Итого наборов:

243 + 81 = 324

Результат: 324

Предлагаем посмотреть видео с решением данного 23 задания:

23_3: Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1 , x2 , … x8 , y1 , y2 , … y8 , которые удовлетворяют всем перечисленным ниже условиям?

¬(((x1 ∧ y1) ≡ (x3 ∧ y3)) → (x2 ∧ y2))
¬(((x2 ∧ y2) ≡ (x4 ∧ y4)) → ¬(x3 ∧ y3))
¬(((x3 ∧ y3) ≡ (x5 ∧ y5)) → (x4 ∧ y4))
¬(((x4 ∧ y4) ≡ (x6 ∧ y6)) → ¬(x5 ∧ y5))
¬(((x5 ∧ y5) ≡ (x7 ∧ y7)) → (x6 ∧ y6))
¬(((x6 ∧ y6) ≡ (x8 ∧ y8)) → ¬(x7 ∧ y7))

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

* Аналогичное задание находится в сборнике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е., 2019 года, вариант 11.

✍ Решение с использованием метода побитовая маска:

• Поскольку в скобках одинаковые действия, и скобки повторяются в разных уравнениях, то введем обозначения. Обозначим латинскими буквами в алфавитном порядке скобки с переменными согласно их номерам:

1-a 2-b 3-c 4-d 5-e 6-f 7-g 8-h

После замены получим следующие выражения:

¬((a ≡ c) → b) ¬((b ≡ d) → ¬c) ¬((c ≡ e) → d) ¬((d ≡ f) → ¬e) ¬((e ≡ g) → f) ¬((f ≡ h) → ¬g)

Используя законы алгебры логики, преобразуем одно из условий (первое). Потом по аналогии выполним преобразования для остальных условий:

1. Избавимся от импликации:
было: ¬((a ≡ c) → b) стало: ¬(¬(a ≡ c) ∨ b)
2. По закону Де Моргана избавимся от отрицания над общей внешней скобкой:
было: ¬(¬(a ≡ c) ∨ b) стало: (a ≡ c) ∧ ¬b

По аналогии преобразуем остальные условия, учитывая, что двойное отрицание просто аннулирует отрицание:

(a ≡ c) ∧ ¬b (b ≡ d) ∧ c (c ≡ e) ∧ ¬d (d ≡ f) ∧ e (e ≡ g) ∧ ¬f (f ≡ h) ∧ g

Рассмотрим, в каких случаях условия будут возвращать истину. Внешняя операция конъюнкция: каждое из условий будет истинно только в том случае, если оба операнда истинны : например: (a ≡ c) ∧ ¬b возвратит истину , если: (a ≡ c) = 1 и ¬b = 1

Это означает, что все операнды, стоящие после знака конъюнкции, должны быть истинны.

Составим битовую маску для наших уравнений с учетом указанного требования:

цеп.1 a ? b 0 c 1 d 0 e 1 f 0 g 1 h ?

Значение для переменной a найдем из условия (a ≡ c) ∧ b . В битовой маске с=1 , значит, чтобы условие a ≡ c было истинным, а должно тоже равняться 1

Значение для переменной h найдем из условия (f ≡ h) ∧ ¬g . В битовой маске f=0 , значит, чтобы условие f ≡ h было истинным, h должно тоже равняться 0 (таблица истинности эквивалентности).

Получим итоговую битовую маску:

цеп.1 a 1 b 0 c 1 d 0 e 1 f 0 g 1 h 0

Теперь вспомним, что каждая из переменных от a до h представляет собой скобку, внутри которой две переменные, связанные конъюнкцией. Конъюнкция двух переменных истинна в одном случае, а ложна — в трех . Т.е., к примеру:

x1 ∧ y1 = 0 тогда, когда: либо 0 ∧ 1 , либо 1 ∧ 0 , либо 0 ∧ 0 x1 ∧ y1 = 1 тогда и только тогда, когда 1 ∧ 1

Это говорит о том, что на каждый 0 в цепочке приходится три варианта значений, а на каждую 1 - один . Т.о., получаем:

3 4 * 1 4 = 81 набор значений

Результат: 81

23_4: Разбор 23 задания ЕГЭ по информатике демоверсия 2018 года ФИПИ:

Сколько существует различных наборов значений логических переменных x1 , x2 , … x7 , y1 , y2 , … y7 , которые удовлетворяют всем перечисленным ниже условиям?

(¬x1 ∨ y1) → (¬x2 ∧ y2) = 1
(¬x2 ∨ y2) → (¬x3 ∧ y3) = 1
…
(¬x6 ∨ y6) → (¬x7 ∧ y7) = 1

✍ Решение, используется метод отображения:

• Внешняя операция в отдельно взятом уравнении — это импликация, результат которой должна быть истина. Импликация истинна если:

0 -> 0 0 -> 1 1 -> 1

т.е. ложна только, когда 1 -> 0

Если скобка (¬x1 ∨ y1) = 0 , то для скобки (¬x2 ∧ y2) возможны варианты 0 или 1 .

Если скобка (¬x1 ∨ y1) = 1 , то для скобки (¬x2 ∧ y2) возможен один вариант — 1 .

В скобках дизъюнкция (∨) истинна, когда: 0 ∨ 1, 1 ∨ 0, 1 ∨ 1; ложна, когда: 0 ∨ 0.

В скобках конъюнкция истинна, когда 1 ∧ 1 и ложна во всех остальных случаях.

Построим таблицу истинности для первого уравнения, учтем все возможные варианты. Выделим в ней те строки, которые возвращают ложь: т.е. где первая скобка (¬x1 ∨ y1) возвратит 1 , а вторая (¬x2 ∧ y2) — 0 :

Поскольку уравнения однотипные и отличаются только сдвигом номеров переменных на единицу, то будем использовать метод отображения. Для первого уравнения x1 и y1 будут обозначаться x i и y i , а x2 и y2 будут обозначаться x i+1 и y i+1 .

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

В итоге получаем:

1 + 19 + 1 + 1 = 22

Результат: 22

Видеоразбор демоверсии 2018 23 задания смотрите здесь:

23_5: Решение 23 задания ЕГЭ по информатике 2018 (диагностический вариант, С.С. Крылов, Д.М. Ушаков, Тренажер ЕГЭ 2018 года):

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

(a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 1

где a, b, c, d, e — логические переменные?

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

✍ Решение:

• Внешняя логическая операция — ∨ — дизъюнкция. Таблица истинности:

0 ∨ 0 = 0 0 ∨ 1 = 1 1 ∨ 0 = 1 1 ∨ 1 = 1

Поскольку дизъюнкция равна единице аж в трех случаях, то искать количество вариантов будет достаточно сложно. Значительно проще найти варианты, когда ∨ = 0 и вычесть их из общего количества вариантов .

Найдем общее количество строк в таблице истинности. Всего 5 переменных, поэтому:

количество строк в ТаблИстин = 2 5 = 32

Посчитаем, сколько вариантов имеют решение при значении уравнения = 0. Чтобы потом вычесть это значение из общего количества. Для операции дизъюнкция (∨) каждая скобка должна быть равна нулю:

(a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 0 0 0 0

Теперь рассмотрим каждую скобку отдельно:

1. (a → b) = 0, импликация ложна в одном случае (1 → 0) = 0 т.е. имеем a = 1 , b = 0 2. (c → ¬d) = 0, импликация ложна в одном случае (1 → 0) = 0 т.е. имеем c = 1 , d = 1 3. ¬(e ∨ a ∨ c) = 0

т.к. перед скобкой стоит отрицание, то для большей понятности раскроем скобки по закону Де Моргана:

¬e ∧ ¬a ∧ ¬c = 0 Конъюнкция равна 0, когда хоть один операнд = 0.

из п.1 и п.2 имеем a = 1 и c = 1 . Тогда для e имеем два варианта: e = 0 , e = 1 , т.е.:

¬0 ∧ ¬1 ∧ ¬1 = 0 ¬1 ∧ ¬1 ∧ ¬1 = 0

То есть всего имеем 2 цепочки «исключаемых» решений:

1. a = 1, b = 0, c = 1, d = 1, e = 0 2. a = 1, b = 0, c = 1, d = 1, e = 1

Эти два варианта исключаем (вычитаем) из общего количества:

32 - 2 = 30

Результат: 30

23_6: Разбор 23 задания демоверсии егэ по информатике 2019:

Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7 , которые удовлетворяют всем перечисленным ниже условиям?

(y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 1 (y2 → (y3 ∧ x2)) ∧ (x2 → x3) = 1 … (y6 → (y7 ∧ x6)) ∧ (x6 → x7) = 1 y7 → x7 = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x7, y1, y2, … y7, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.

✍ Решение:

• Поскольку все равенства однотипны (кроме последнего), отличаются только сдвигом номеров переменных на единицу, то для решения будем использовать метод отображения: когда, найдя результат для первого равенства, необходимо применить тот же принцип с последующими равенствами, учитывая полученные результаты для каждого из них.
• Рассмотрим первое равенство. В нем внешняя операция — это конъюнкция, результат которой должна быть истина. Конъюнкция истинна если:

1 -> 1 т.е.: (y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 1 1 1

Найдем случаи, когда равенство будет ложным (чтобы в дальнейшем исключить эти случаи):

(y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 0

Внутри первой «большой» скобки находится операция импликации. Которая ложна:

1 -> 0 = 0 т.е. случаи: y1=1 → (y2=0 ∧ x1=1) y1=1 → (y2=1 ∧ x1=0) y1=1 → (y2=0 ∧ x1=0)

Таким же образом проанализируем вторую скобку. В ней импликация вернет ложь:

(x1=1 → x2=0)

Построим таблицу истинности для первого уравнения, учтем все возможные варианты. Поскольку переменных 4, то строк будет 2 4 = 16 . Выделим те строки, которые возвращают ложь:

Теперь переходим к методу отображения. Для первого уравнения x1 и y1 обозначим x i и y i , а x2 и y2 обозначим x i+1 и y i+1 . Стрелками обозначим значения только тех строк таблицы истинности, которые возвращают 1 .

Найдем общее количество решений, подставляя в таблицу из отображения соответствующие значения x и y , и, учитывая предыдущие значения:

Теперь вернемся к последнему равенству. По условию оно должно быть истинным. Равенство вернет ложь только в одном случае:

y7=1 → x7=0 = 0

Найдем соответствующие переменные в нашей таблице:

Рассчитаем сумму по последнему столбцу, не учитывая строку, возвращающую ложь:

1 + 7 + 28 = 36

Результат: 36

Видео решения 23 задания демоверсии егэ 2019:

23_7: Разбор 23 задания ЕГЭ по информатике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е., 2019, вариант 16 (ФИПИ):

Сколько существует различных наборов значений логических переменных x1 , x2 , … x6 , y1 , y2 , … y6 , которые удовлетворяют всем перечисленным ниже условиям?

¬(((x1 ∧ y1)) ≡ (x2 ∧ y2)) → (x3 ∧ y3))
¬(((x2 ∧ y2)) ∨ ¬(x3 ∧ y3)) → (x4 ∧ y4))
¬(((x3 ∧ y3)) ≡ (x4 ∧ y4)) → (x5 ∧ y5))
¬(((x4 ∧ y4)) ∨ ¬(x5 ∧ y5)) → (x6 ∧ y6))

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

✍ Решение:

• Поскольку в малых скобках везде одна и та же операция (∧ ), и переменные в скобках не пересекаются, то можно выполнить замену:

¬((a ≡ b) → c) = 1 ¬((b ∨ ¬c) → d) = 1 ...

Избавимся от отрицания, указав, что каждое выражение при этом становится ложным:

(a ≡ b) → c = 0 (b ∨ ¬c) → d = 0 (c ≡ d) → e = 0 (d ∨ ¬e) → f = 0

Внешняя операция во всех выражениях — импликация (→ ). Вспомним таблицу истинности для операции импликация:

0 → 0 = 1 0 → 1 = 1 1 → 0 = 0 1 → 1 = 1

Импликация ложна только в одном случае: 1 → 0 = 0 . Все выражения в задании ложны. Учтем это.

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

цеп1 цеп2 a 0 1 b 0 1 c 0 0 d 0 0 e 0 0 f 0 0

Так как каждая переменная изначально заменяет скобку, в которой находится операция конъюнкция (∧), то, вспомнив таблицу истинности для этой операции, сопоставим для каждого нуля 3 решения (конъюнкция ложна в трех случаях), а для каждой единицы — 1 решение (конъюнкция истинна в одном случае).

Посчитаем значение для каждой побитовой цепочки:

цеп1 = 3*3*3*3*3*3 = 729 решений цеп2 = 1*1*3*3*3*3 = 81 решение

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

729 + 81 = 810 решений

Ответ: 810

Доступен видеоразбор задания 23:

23_8: Разбор 23 задания ЕГЭ по информатике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е., 2019, вариант 2 (ФИПИ):

Сколько существует различных наборов значений логических переменных x1 , x2 , … x12 , которые удовлетворяют всем перечисленным ниже условиям?

¬(x1 ≡ x2) → (x3 ∧ x4) = 0
¬(x3 ≡ x4) → (x5 ∧ x6) = 0
¬(x5 ≡ x6) → (x7 ∧ x8) = 0
¬(x7 ≡ x8) → (x9 ∧ x10) = 0
¬(x9 ≡ x10) → (x11 ∧ x12) = 0
(x1 ≡ x4) ∨ (x5 ≡ x8) ∨ (x2 ≡ x12) = 1

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

✍ Решение:

x1 x2 x4 x5 x8 x12 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0

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

x1 x2 x4 x5 x8 x12 0 1 1 0 1 0 y1 0 1 1 1 0 0 y2 1 0 0 0 1 1 y3 1 0 0 1 0 1 y4

Построим таблицу отображений отдельно для каждой получившейся строки, учитывая значения операндов (x n):

Посчитаем число решений для всех полученных строк: 4 + 4 + 2 + 2 = 12

Эти решения необходимо исключить, т.к. мы рассмотрели ложный случай уравнения 6 :

96 - 12 = 84

Каталог заданий.
Системы логических уравнений, содержащие однотипные уравнения

Сортировка Основная Сначала простые Сначала сложные По популярности Сначала новые Сначала старые
Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word

Сколь-ко су-ще-ству-ет раз-лич-ных на-бо-ров зна-че-ний ло-ги-че-ских пе-ре-мен-ных x1, x2, x3, x4, x5, x6, x7, x8 ко-то-рые удо-вле-тво-ря-ют всем пе-ре-чис-лен-ным ниже усло-ви-ям?

(x1≡x2)->(x2≡x3) = 1

(x2≡x3)->(x3≡x4) = 1

(x6≡x7)->(x7≡x8) = 1

В от-ве-те не нужно пе-ре-чис-лять все раз-лич-ные на-бо-ры зна-че-ний пе-ре-мен-ных x1, x2, x3, x4, x5, x6, x7, x8 при ко-то-рых вы-пол-не-на дан-ная си-сте-ма ра-венств. В ка-че-стве от-ве-та Вам нужно ука-зать ко-ли-че-ство таких на-бо-ров.

Решение.

Запишем переменные в строчку: x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 . Импликация ложна только в том случае, когда из истины следует ложь. Условие не выполняется, если в ряду после пары одинаковых цифр присутствует другая цифра. Например, «11101...», что означает невыполнение второго условия.

Рассмотрим комбинации переменных, удовлетворяющие всем условиям. Выпишем варианты, при которых все цифры чередуются, таких два: 10101010 и 01010101. Теперь для первого варианта, начиная с конца, будем увеличивать количество повторяющихся подряд цифр (настолько, насколько это возможно). Выпишем полученные комбинации: «1010 1011; 1010 1111; 1011 1111; 1111 1111; 1010 1000; 1010 0000; 1000 0000; 0000 0000» таких комбинаций девять, включая исходную. Аналогично для второго варианта: «0101 0101; 0101 0100; 0101 0000; 0100 0000; 0000 0000; 0101 0111; 0101 1111; 0111 1111; 1111 1111» - таких комбинаций также девять. Заметим, что комбинации 0000 0000 и 1111 1111 учтены дважды. Таким образом, получаем 9 + 9 − 2 = 16 решений.

Ответ: 16.

Ответ: 16

¬(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

¬(x 8 ≡ x 9) ∧ (x 8 ∨ x 10) ∧ (¬x 8 ∨ ¬x 10) = 0

В ответе не нужно

Решение.

Рассмотрим первое уравнение.

При x 1 = 1 возможны два случая: x 2 = 0 и x 2 = 1. В первом случае x 3 = 1. Во втором - x 3 либо 0, либо 1. При x 1 = 0 также возможны два случая: x 2 = 0 и x 2 = 1. В первом случае x 3 либо 0, либо 1. Во втором - x 3 = 0. Таким образом, уравнение имеет 6 решений (см. рисунок).

Рассмотрим систему из двух уравнений.

Пусть x 1 = 1. При x 2 = 0 возможен лишь один случай: x 3 = 1, переменная x 4 = 0. При x 2 = 1 возможно два случая: x 3 = 0 и x 3 = 1. В первом случае x 4 = 1, во втором - x 4 либо 0, либо 1. Всего имеем 4 варианта.

Пусть x 1 = 0. При x 2 = 1 возможен лишь один случай: x 3 = 0, переменная x 4 = 1. При x 2 = 0 возможно два случая: x 3 = 0 и x 3 = 1. В первом случае x 4 либо 1, либо 0, во втором - x 4 = 0. Всего имеем 4 варианта.

Таким образом, система из двух уравнений имеет 4 + 4 = 8 вариантов (см. рисунок).

Система из трёх уравнений будет иметь 10 решений, из четырёх - 12. Система из восьми уравнений будет иметь 20 решений.

Ответ: 20

Источник: ЕГЭ по ин­фор­ма­ти­ке 30.05.2013. Ос­нов­ная волна. Центр. Ва­ри­ант 1.

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

(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 7 ∧ ¬x 8) ∨ (¬x 7 ∧ x 8) ∨ (x 9 ∧ x 10) ∨ (¬x 9 ∧ ¬x 10) = 1

В ответе не нужно перечислять все различные наборы значений переменных x 1 , x 2 , … x 10 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение.

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

Количество пар значений	x 3	x 4
×4	1	1
×4	0	0
×2	1	0
×2	0	1

Поскольку уравнения идентичны с точностью до индексов переменных, древо решений второго уравнения аналогично первому. Следовательно, пара значений x 3 = 1 и x 4 = 1 порождает два набора переменных x 3 , ..., x 6 , удовлетворяющих второму уравнению. Поскольку среди наборов решений первого уравнения данных пар четыре, всего получаем 4 · 2 = 8 наборов переменных x 1 , ..., x 6 , удовлетворяющих системе из двух уравнений. Рассуждая аналогично для пары значений x 3 = 0 и x 4 = 0, получаем 8 наборов переменных x 1 , ..., x 6 . Пара x 3 = 1 и x 4 = 0 порождает четыре решения второго уравнения. Поскольку среди наборов решений первого уравнения данных пар две, получаем 2 · 4 = 8 наборов переменных x 1 , ..., x 6 , удовлетворяющих системе из двух уравнений. Аналогично для x 3 = 0 и x 4 = 1 - 8 наборов решений. Всего система из двух уравнений имеет 8 + 8 + 8 + 8 = 32 решения.

Проведя аналогичные рассуждения для системы из трёх уравнений, получаем 80 наборов переменных x 1 , ..., x 8 , удовлетворяющих системе. для системы из четырёх уравнений существует 192 набора переменных x 1 , ..., x 10 , удовлетворяющих системе.

Ответ: 192.

Ответ: 192

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 501.

Гость 17.12.2013 18:50

Пересчитывали 3 раза, получается, что после 2 уравнения 34 решения, а у вас 32, у нас 8+12+8+6, а у вас 8+8+8+8

Петр Мурзин

Приведите ваше решение полностью. Напишите, каким образом вы получаете 12 и 6.

Иван Гребенщиков 12.06.2016 20:51

Вообще, можно решить эту задачу намного проще. Если заметить (x1 ∧ ¬x2) ∨ (¬x1 ∧ x2) тождественно ¬(x1 == x2) и (x3 ∧ x4) ∨ (¬x3 ∧ ¬x4) тождественно (x3 == x4), то,подставив в изначальное уравнение, получаем: ¬(x1 == x2) ∨ (x3 == x4) = 1. Однако и это выражение можно преобразовать и получить (x1 == x2) → (x3 == x4) = 1.

Преобразовав аналогичным образом все выражения получаем:

(x1 == x2) → (x3 == x4) = 1

(x3 == x4) → (x5 == x6) = 1

(x7 == x8) → (x9 == x10) = 1

Заменив (x1 == x2) на А1, (x3 == x4) на А3, ... , (x9 == x10) на А9 получаем наборы решений для А-итых:

А1 А3 А5 А7 А9

Каждому A-итому соответствует(вне зависимости от значения) пара пар значений i-того и i + 1 - ого x-сов => (2 * 2 * 2 * 2 * 2) * 6(так как шесть наборов решений для А-итых) = 192

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

(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 7 ∧ x 8) ∨ (¬x 7 ∧ ¬x 8) ∨ (¬x 9 ∧ x 10) ∨ (x 9 ∧ ¬x 10) = 1

В ответе не нужно перечислять все различные наборы значений переменных x 1 , x 2 , … x 10 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение.

Построим древо решений для первого уравнения.

Таким образом, первое уравнение имеет 12 решений.

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

Количество пар значений	x 3	x 4
×2	1	1
×2	0	0
×4	1	0
×4	0	1

Поскольку уравнения идентичны с точностью до индексов переменных, древо решений второго уравнения аналогично первому (см. рис.). Следовательно, пара значений x 3 = 1 и x 4 = 1 порождает четыре набора переменных x 3 , ..., x 6 , удовлетворяющих второму уравнению. Поскольку среди наборов решений первого уравнения данных пар две, всего получаем 4 · 2 = 8 наборов переменных x 1 , ..., x 6 , удовлетворяющих системе из двух уравнений. Рассуждая аналогично для пары значений x 3 = 0 и x 4 = 0, получаем 8 наборов переменных x 1 , ..., x 6 . Пара x 3 = 1 и x 4 = 0 порождает два решения второго уравнения. Поскольку среди наборов решений первого уравнения данных пар четыре, получаем 2 · 4 = 8 наборов переменных x 1 , ..., x 6 , удовлетворяющих системе из двух уравнений. Аналогично для x 3 = 0 и x 4 = 1 - 8 наборов решений. Всего система из двух уравнений имеет 8 + 8 + 8 + 8 = 32 решения.

Третье уравнение связано со вторым только через переменные x 5 и x 6 . Древо решений аналогичное. Тогда для системы из трёх уравнений каждая пара значений x 5 и x 6 будет порождать количество решений в соответствии с древом (см. рис.): пара (1, 0) породит 2 решения, пара (1, 1) породит 4 решения, и т. д.

Из решения первого уравнения мы знаем, что пара значений x 3 , x 4 (1, 1) встречается в решениях два раза. Следовательно, для системы из трёх уравнений количество решений для пары x 3 , x 4 (1, 1) равно 2 · (2 + 4 + 4 + 2) = 24 (см. рис.). Воспользовавшись таблицей выше, вычислим количество решений для оставшихся пар x 3 , x 4:

4 · (2 + 2) = 16

2 · (2 + 4 + 4 + 2) = 24

4 · (2 + 2) = 16

Таким образом, для системы из трёх уравнений имеем 24 + 16 + 24 + 16 = 80 наборов переменных x 1 , ..., x 8 , удовлетворяющих системе.

Для системы из четырёх уравнений существует 192 набора переменных x 1 , ..., x 10 , удовлетворяющих системе.

Ответ: 192.

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

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

Пример 1.

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

Ответ: 121

Пример 2.

Сколько существует различных наборов значений логических переменных x1, x2, ... x9, y1, y2, ... y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ... x9, y1, y2, ... y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение:

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

Т.к. 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 наборов.

Ответ: 1024

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

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

Пример 3.

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

¬x9 ∨ x10 = 1,

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

Ответ: 11

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

Пример 4.

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

(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 4 ∧ y 4 ∧ z 4 = 0

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

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

Решение:

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

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

Аналогично, решениями второго и третьего уравнений будут абсолютно такие же наборы y1,…,y4 и z1,…, z4.

Теперь проанализируем четвертое уравнение системы: x 4 ∧ y 4 ∧ z 4 = 0. Решением будут все наборы x4, y4, z4, в которых хотя бы одна из переменных равна 0.

Т.е. для x4 = 0 подойдут все возможные наборы (y4, z4), а для x4 = 1 подойдут наборы (y4, z4), в которых присутствует хотя бы один ноль: (0, 0), (0,1) , (1,0).

				Кол-во наборов

Общее количество наборов 25 + 4*9 = 25 + 36 = 61.

Ответ: 61

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

Метод построения рекуррентных формул применяется при решении сложных систем, в которых порядок увеличения количества наборов неочевиден, а построение дерева невозможно из-за объемов.

Пример 5.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, … x7, y1, y2, … y7, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, ..., x7, y1, y2, ..., y7, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что первые шесть уравнений системы одинаковы и отличаются только набором переменных. Рассмотрим первое уравнение. Его решением будут следующие наборы переменных:

Обозначим:

число наборов (0,0) на переменных (x1,y1) через A 1 ,

число наборов (0,1) на переменных (x1,y1) через B 1 ,

число наборов (1,0) на переменных (x1,y1) через C 1 ,

число наборов (1,1) на переменных (x1,y1) через D 1 .

число наборов (0,0) на переменных (x2,y2) через A 2 ,

число наборов (0,1) на переменных (x2,y2) через B 2 ,

число наборов (1,0) на переменных (x2,y2) через C 2 ,

число наборов (1,1) на переменных (x2,y2) через D 2 .

Из дерева решений видим, что

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

Заметим, что набор (0,0) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. A 2 =B 1 +C 1 +D 1 .

Набор (0,1) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. B 2 =B 1 +C 1 +D 1 .

Аналогично рассуждая, заметим, что С 2 =B 1 +C 1 +D 1 . D 2 = D 1 .

Таким образом, получаем рекуррентные формулы:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

Составим таблицу

Наборы	Обозн .	Формула	Количество наборов
			i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	A i	A i+1 =B i +C i +D i	0	3	7	15	31	63	127
(0,1)	B i	B i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

Последнему уравнению (x7 ∨ y7) = 1 удовлетворяют все наборы, кроме тех, в которых x7=0 и y7=0. В нашей таблице число таких наборов A 7 .

Тогда общее количество наборов равно B 7 + C 7 + D 7 = 127+127+1 = 255

Ответ: 255