Для эффективной подготовки по информатике для каждого задания дан краткий теоретический материал для выполнения задачи. Подобрано свыше 10 тренировочных заданий с разбором и ответами, разработанные на основе демоверсии прошлых лет.
Изменений в КИМ ЕГЭ 2020 г. по информатике и ИКТ нет.
Направления, по которым будет проведена проверка знаний:
- Программирование;
- Алгоритмизация;
- Средства ИКТ;
- Информационная деятельность;
- Информационные процессы.
Необходимые действия при подготовке :
- Повторение теоретического курса;
- Решение тестов по информатике онлайн ;
- Знание языков программирования;
- Подтянуть математику и математическую логику;
- Использовать более широкий спектр литературы – школьной программы для успеха на ЕГЭ недостаточно.
Структура экзамена
Длительность экзамена – 3 часа 55 минут (255 минут), полтора часа из которых рекомендовано уделить выполнению заданий первой части КИМов.
Задания в билетах разделены на блоки:
- Часть 1 - 23 задания с кратким ответом.
- Часть 2 - 4 задачи с развернутым ответом.
Из предложенных 23 заданий первой части экзаменационной работы 12 относятся к базовому уровню проверки знаний, 10 – повышенной сложности, 1 – высокому уровню сложности. Три задачи второй части высокого уровня сложности, одна – повышенного.
При решении обязательна запись развернутого ответа (произвольная форма).
В некоторых заданиях текст условия подан сразу на пяти языках программирования – для удобства учеников.
Баллы за задания по информатике
1 балл - за 1-23 задания
2 балла - 25.
З балла - 24, 26.
4 балла - 27.
Всего: 35 баллов.
Для поступления в технический вуз среднего уровня, необходимо набрать не менее 62 баллов. Чтобы поступить в столичный университет, количество баллов должно соответствовать 85-95.
Для успешного написания экзаменационной работы необходимо четкое владение теорией и постоянная практика в решении задач.
Твоя формула успеха
Труд + работа над ошибками + внимательно читать вопрос от начала и до конца, чтобы избежать ошибок = максимальный балл на ЕГЭ по информатике.
На уроке рассмотрено решение 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 |
Результат: 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.
✍ Решение (использование метода побитовая маска):
- Поскольку в скобках одинаковые действия, и переменные повторяются, то введем обозначения:
x1 | x2 | F |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Это означает, что для одного условия не может быть такого случая, что a=0 и b=0 или a=1 и b=1 .
Результат: 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.
✍ Решение с использованием метода побитовая маска:
- Поскольку в скобках одинаковые действия, и скобки повторяются в разных уравнениях, то введем обозначения. Обозначим латинскими буквами в алфавитном порядке скобки с переменными согласно их номерам:
- Избавимся от импликации: было: ¬((a ≡ c) → b) стало: ¬(¬(a ≡ c) ∨ b)
- По закону Де Моргана избавимся от отрицания над общей внешней скобкой: было: ¬(¬(a ≡ c) ∨ b) стало: (a ≡ c) ∧ ¬b
Это означает, что все операнды, стоящие после знака конъюнкции, должны быть истинны.
Результат: 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
Результат: 22
Видеоразбор демоверсии 2018 23 задания смотрите здесь:
23_5: Решение 23 задания ЕГЭ по информатике 2018 (диагностический вариант, С.С. Крылов, Д.М. Ушаков, Тренажер ЕГЭ 2018 года):
Сколько различных решений имеет уравнение:
(a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 1
где a, b, c, d, e — логические переменные?
В качестве ответа указать количество таких наборов.
✍ Решение:
- Внешняя логическая операция — ∨ — дизъюнкция. Таблица истинности:
Результат: 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, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.
✍ Решение:
- Поскольку все равенства однотипны (кроме последнего), отличаются только сдвигом номеров переменных на единицу, то для решения будем использовать метод отображения: когда, найдя результат для первого равенства, необходимо применить тот же принцип с последующими равенствами, учитывая полученные результаты для каждого из них.
- Рассмотрим первое равенство. В нем внешняя операция — это конъюнкция, результат которой должна быть истина. Конъюнкция истинна если:
Результат: 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))
В качестве ответа Вам нужно указать количество таких наборов.
✍ Решение:
- Поскольку в малых скобках везде одна и та же операция (∧ ), и переменные в скобках не пересекаются, то можно выполнить замену:
Ответ: 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
Решение систем логических уравнений методом замены переменных
Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной.
Пример 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
Каталог заданий.
Системы логических уравнений, содержащие однотипные уравнения
Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в 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.