Носкин Андрей Николаевич,
учитель информатики
высшей квалификационной категории,
кандидат военных наук, доцент
ГБОУ Лицей №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
)
Решение:
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. Издательский дом "Первое сентября", г.Москва.
Решение систем логических уравнений методом замены переменных
Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной.
Пример 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
Муниципальное бюджетное общеобразовательное учреждение
«Средняя общеобразовательная школа № 18»
городского округа город Салават Республики Башкортостан
Системы логических уравнений
в задачах ЕГЭ по информатике
Раздел «Основы алгебры логики» в заданиях ЕГЭ считается одним из самых сложных и плохо решаемых. Средний процент выполнения заданий по данной теме самый низкий и составляет 43,2.
| Раздел курса | Средний процент выполнения по группам заданий |
| Кодирование информации и измерение ее количества | |
| Информационное моделирование | |
| Системы счисления | |
| Основы алгебры логики | |
| Алгоритмизация и программирование | |
| Основы информационно- коммуникационных технологий |
Исходя из спецификации КИМа 2018 года этот блок включает четыре задания разного уровня сложности.
| № задания | Проверяемые элементы содержания | Уровень сложности задания |
| Умение строить таблицы истинности и логические схемы | ||
| Умение осуществлять поиск информации в сети Интернет | ||
| Знание основных понятий и законов математической логики | ||
| Умение строить и преобразовывать логические выражения |
Задание 23 является высоким по уровню сложности, поэтому имеет самый низкий процент выполнения. Среди подготовленных выпускников (81-100 баллов) 49,8% выполнивших, средне подготовленные (61-80 баллов) справляются на 13,7%, оставшаяся группа учеников данное задание не выполняет.
Успешность решения системы логических уравнений зависит от знания законов логики и от четкого применения методов решения системы.
Рассмотрим решение системы логических уравнений методом отображения.
(23.154 Поляков К.Ю.) Сколько различных решений имеет система уравнений?
((x 1 y 1 ) (x 2 y 2 )) (x 1 x 2 ) (y 1 y 2 ) =1
((x 2 y 2 ) (x 3 y 3 )) (x 2 x 3 ) (y 2 y 3 ) =1
((x 7 y 7 ) (x 8 y 8 )) (x 7 x 8 ) (y 7 y 8 ) =1
где x 1 , x 2 ,…, x 8, у 1 ,у 2 ,…,у 8 - логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение . Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено четыре переменных. Зная x1 и y1, можем найти все возможные значения x2 и y2, удовлетворяющие первому уравнению. Рассуждая аналогичным образом, из известных x2 и y2можем найти x3, y3, удовлетворяющее второму уравнению. То есть, зная пару (x1 , y1) и определив значение пары (x2 , y2) , мы найдем пару (x3 , y3 ), которая, в свою очередь, приведет к паре (x4 , y4 ) и так далее.
Найдем все решения первого уравнения. Это можно сделать двумя способами: построить таблицу истинности, через рассуждения и применение законов логики.
Таблица истинности:
| x 1 y 1 | x 2 y 2 | (x 1 y 1 ) (x 2 y 2 ) | (x 1 x 2 ) | (y 1 y 2 ) | (x 1 x 2 ) (y 1 y 2 ) | |||||
Построение таблицы истинности трудоемко и неэффективно по времени, поэтому применяем второй способ - логические рассуждения. Произведение равно 1 тогда и только тогда, когда каждый множитель равен 1.
(x 1 y 1 ) (x 2 y 2 ))=1
(x 1 x 2 ) =1
(y 1 y 2 ) =1
Рассмотрим первое уравнение. Следование равно 1, когда 0 0, 0 1, 1 1, значит (x1 y1)=0 при (01), (10), то пара (x 2 y 2 ) может быть любой (00), (01), (10), (11), а при (x1 y1)=1, то есть (00) и (11) пара (x2 y2)=1 принимает такие же значения (00) и (11). Исключим из этого решения те пары, для которых ложны второе и третье уравнения, то есть x1=1, x2=0, y1=1, y2=0.
| (x 1 , y 1 ) | (x 2 , y 2 ) |
Общее количество пар 1+1+1+22=25
2) (23.160 Поляков К.Ю.) Сколько различных решений имеет система логических уравнений
(x 1 (x 2 y 2 )) (y 1 y 2 ) = 1
(x 2 (x 3 y 3 )) (y 2 y 3 ) = 1
...
( x 6 ( x 7 y 7 )) ( y 6 y 7 ) = 1
x 7 y 7 = 1
Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,y1), (x2,y2) первого уравнения.
(x 1 (x 2 y 2 ))=1
(y 1 y 2 ) = 1
Решением второго уравнения являются пары (00), (01), (11).
Найдем решения первого уравнения. Если x1=0, то x2 , y2 - любые, если x1=1, то x2 , y2 принимает значение (11).
Составим связи между парами (x1 , y1) и (x2 , y2).
| (x 1 , y 1 ) | (x 2 , y 2 ) |
Составим таблицу для вычисления количества пар на каждом этапе.
| 0 |
|||||||
Учитывая решения последнего уравнения x 7 y 7 = 1, исключим пару (10). Находим общее число решений 1+7+0+34=42
3)(23.180) Сколько различных решений имеет система логических уравнений
(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 3 x 5 x 7 x 9 = 1
Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,x2), (x3,x4) первого уравнения.
(x 1 x 2 ) (x 3 x 4 ) = 1
Исключим из решения пары, которые в следовании дают 0 (1 0), это пары (01, 00, 11) и (10).
Составим связи между парами (x1,x2), (x3,x4)
Методы решения систем логических уравнений
Решить систему логических уравнений можно, например, с помощью таблицы истинности (если количество переменных не слишком велико) или с помощью дерева решений, предварительно упростив каждое уравнение.
1. Метод замены переменных.
Ввод новых переменных позволяет упростить систему уравнений, сократив количество неизвестных. Новые переменные должны быть независимыми друг от друга . После решения упрощенной системы надо снова вернуться к первоначальным переменным.
Рассмотрим применение этого метода на конкретном примере.
Пример.
((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0
((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0
((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0
((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0
Решение:
Введем новые переменные: А=(X1 ≡ X2); В=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).
(Внимание! Каждая их переменных x1, x2, …, x10 должна входить только в одну из новых переменных А,В,С,D,Е, т.е. новые переменные независимы друг от друга).
Тогда система уравнений будет выглядеть так:
(А ∧ В) ∨ (¬А ∧ ¬В)=0
(В ∧ C) ∨ (¬B ∧ ¬C)=0
(С ∧ D) ∨ (¬C ∧ ¬D)=0
(D ∧ E) ∨ (¬D ∧ ¬E)=0
Построим дерево решений полученной системы:
Рассмотрим уравнение А=0, т.е. (X1 ≡ X2)=0. Оно имеет 2 корня:
X1 ≡ X2 |
||
Из этой же таблицы видно, что уравнение А=1 тоже имеет 2 корня. Расставим кол-во корней на дереве решений:
Чтобы найти количество решений одной ветви, надо перемножить количества решений на каждом ее уровне. Левая ветвь имеет 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 решения; правая ветвь имеет тоже 32 решения. Т.е. вся система имеет 32+32=64 решения.
Ответ: 64.
2. Метод рассуждений.
Сложность решения систем логических уравнений состоит в громоздкости полного дерева решений. Метод рассуждений позволяет не строить все дерево полностью, но понять при этом, сколько оно будет иметь ветвей. Рассмотрим этот метод на конкретных примерах.
Пример 1. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
x1\/y1 =1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Решение :
Первое и второе уравнения содержат независимые переменные, которые связаны третьим условием. Построим дерево решений первого и второго уравнений.
Чтобы представить дерево решений системы из первого и второго уравнений, надо каждую ветвь первого дерева продолжить деревом для переменных у . Построенное таким образом дерево будет содержать 36 ветвей. Некоторые из этих ветвей не удовлетворяют третьему уравнению системы. Отметим на первом дереве количество ветвей дерева «у» , которые удовлетворяют третьему уравнению:
Поясним: для выполнения третьего условия при х1=0 должно быть у1=1, т.е все ветви дерева «х» , где х1=0 можно продолжить только одной ветвью из дерева «у» . И только для одной ветви дерева «х» (правой) подходят все ветви дерева «у». Таким образом, полное дерево всей системы содержит 11 ветвей. Каждая ветвь представляет собой одно решение исходной системы уравнений. Значит, вся система имеет 11 решений.
Ответ: 11.
Пример 2. Сколько различных решений имеет система уравнений
(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1
(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.
………………
(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1
(X1 ≡ X10) = 0
где x1, x2, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение : Упростим систему. Построим таблицу истинности части первого уравнения:
X1 ∧ X10 | ¬X1 ∧ ¬ X10 | (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10) |
||
Обратите внимание на последний столбец, он совпадает с результатом действия X1 ≡ X10.
X1 ≡ X10 |
После упрощения получим:
(X1 ≡ X2) ∨ (X1 ≡ X10)=1
(X2 ≡ X3) ∨ (X2 ≡ X10)=1
(X3 ≡ X4) ∨ (X3 ≡ X10)=1
……
(X9 ≡ X10) ∨ (X9 ≡ X10)=1
(X1 ≡ X10) = 0
Рассмотрим последнее уравнение: (X1 ≡ X10) = 0 , т.е. х1 не должно совпадать с х10. Чтобы первое уравнение было равно 1, должно выполняться равенство (X1 ≡ X2)=1, т.е. х1 должно совпадать с х2.
Построим дерево решений первого уравнения:
Рассмотрим второе уравнение: при х10=1 и при х2=0 скобка должна быть равна 1 (т.е. х2 совпадает с х3); при х10=0 и при х2=1 скобка (X2 ≡ X10)=0 , значит, скобка (X2 ≡ X3) должна быть равна 1 (т.е. х2 совпадает с х3):
Рассуждая таким образом, построим дерево решений для всех уравнений:
Таким образом, система уравнений имеет всего 2 решения.
Ответ: 2.
Пример 3.
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, которые удовлетворяют всем перечисленным ниже условиям?
(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1
(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1
(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1
(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1
(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1
Решение:
Построим дерево решений 1-го уравнения:
Рассмотрим второе уравнение:
- При х1=0 : вторая и третья скобки будут равны 0; чтобы первая скобка была равна 1, должны у1=1 , z1=1 (т.е. в этом случае - 1 решение)
- При х1=1 : первая скобка будет равна 0; вторая или третья скобка должна быть равна 1; вторая скобка будет равна 1 при у1=0 и z1=1; третья скобка будет равна 1 при у1=1 и z1=0 (т.е. в этом случае - 2 решения).
Аналогично для остальных уравнений. Отметим полученное кол-во решений у каждого узла дерева:
Чтобы узнать кол-во решений для каждой ветви, перемножим полученные числа по отдельности для каждой ветви (слева напрво).
1 ветвь: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 решение
2 ветвь: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 решения
3 ветвь: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 решения
4 ветвь: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 решения
5 ветвь: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 решения
Сложим полученные числа: всего 31 решение.
Ответ: 31.
3. Закономерное увеличение количества корней
В некоторых системах количество корней очередного уравнения зависит от количества корней предыдущего уравнения.
Пример 1. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, которые удовлетворяют всем перечисленным ниже условиям?
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
Упростим первое уравнение: (x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Тогда система примет вид:
¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0
¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0
¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0
И т.д.
Каждое следующее уравнение имеет на 2 корня больше, чем предыдущее.
4 уравнение имеет 12 корней;
5 уравнение имеет 14 корней
8 уравнение имеет 20 корней.
Ответ: 20 корней.
Иногда количество корней растет по закону чисел Фибоначчи.
Решение системы логических уравнений требует творческого подхода.
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, где J, K, L, M, N — логические переменные?
Пояснение.
Выражение (N ∨ ¬N) истинно при любом N, поэтому
J ∧ ¬K ∧ L ∧ ¬M = 0.
Применим отрицание к обеим частям логического уравнения и используем закон де Моргана ¬ (А ∧ В) = ¬ А ∨ ¬ В. Получим ¬J ∨ K ∨ ¬L ∨ M = 1.
Логическая сумма равна 1, если хотя бы одно из составляющих ее высказываний равно 1. Поэтому полученному уравнению удовлетворяют любые комбинации логических переменных кроме случая, когда все входящие в уравнение величины равны 0. Каждая из 4 переменных может быть равна либо 1, либо 0, поэтому всевозможных комбинаций 2·2·2·2 = 16. Следовательно, уравнение имеет 16 −1 = 15 решений.
Осталось заметить, что найденные 15 решений соответствуют любому из двух возможных значений значений логической переменной N, поэтому исходное уравнение имеет 30 решений.
Ответ: 30
Сколько различных решений имеет уравнение
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1
где J, K, L, M, N – логические переменные?
В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Пояснение.
Используем формулы A → B = ¬A ∨ B и ¬(А ∨ В) = ¬А ∧ ¬В
Рассмотрим первую подформулу:
(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Рассмотрим вторую подформулу
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L
Рассмотрим третью подформулу
1) M → J = 1 следовательно,
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Объединим:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 следовательно, 4 решения.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L
Объединим:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L следовательно, 4 решения.
в) M = 0 J = 0.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.
Ответ: 4 + 4 = 8.
Ответ: 8
Сколько различных решений имеет уравнение
((K ∨ L) → (L ∧ M ∧ N)) = 0
где K, L, M, N – логические переменные? В Ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве Ответа Вам нужно указать количество таких наборов.
Пояснение.
перепишем уравнение, используя более простые обозначения операций:
((K + L) → (L · M · N)) = 0
1) из таблицы истинности операции «импликация» (см. первую задачу) следует, что это равенство верно тогда и только тогда, когда одновременно
K + L = 1 и L · M · N = 0
2) из первого уравнения следует, что хотя бы одна из переменных, K или L, равна 1 (или обе вместе); поэтому рассмотрим три случая
3) если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения
4) если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения
5) если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения
6) всего получаем 4 + 3 + 3 = 10 решений.
Ответ: 10
Сколько различных решений имеет уравнение
(K ∧ L) ∨ (M ∧ N) = 1
Пояснение.
Выражение истинно в трех случаях, когда (K ∧ L) и (M ∧ N) равны соответственно 01, 11, 10.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N равны 1, а K и L любые, кроме как одновременно 1. Следовательно 3 решения.
2) "11" K ∧ L = 1; M ∧ N = 1. => 1 решение.
3) "10" K ∧ L = 1; M ∧ N = 0. => 3 решения.
Ответ: 7.
Ответ: 7
Сколько различных решений имеет уравнение
(X ∧ Y ∨ Z) → (Z ∨ P) = 0
где X, Y, Z, P – логические переменные? В ответе не нужно перечислять все различные наборы значений, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.
Пояснение.
(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>
¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;
(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;
Логическое ИЛИ ложно только в одном случае: когда оба выражения ложны.
Следовательно,
(Z ∨ P) = 0 => Z = 0, P = 0.
¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>
¬X ∨ ¬Y = 0 => X = 1; Y = 1.
Следовательно, существует только одно решение уравнения.
Ответ: 1
Сколько различных решений имеет уравнение
(K ∨ L) ∧ (M ∨ N) = 1
где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.
Пояснение.
Логическое И истинно только в одном случае: когда все выражения истинны.
K ∨ L = 1, M ∨ N = 1.
Каждое из уравнений дает по 3 решения.
Рассмотрим уравнение А ∧ В = 1 если и А и В принимают истинные значения в трех случаях каждое, то в целом уравнение имеет 9 решений.
Следовательно ответ 9.
Ответ: 9
Сколько различных решений имеет уравнение
((A → B)∧ C) ∨ (D ∧ ¬D)= 1,
где A, B, C, D – логические переменные?
В ответе не нужно перечислять все различные наборы значений A, B, C, D, при которых выполнено данное равенство. В качестве ответа вам нужно указать количество таких наборов.
Пояснение.
Логическое "ИЛИ" истинно, когда истинно хотя бы одно из утверждений.
(D ∧ ¬D)= 0 при любых D.
Следовательно,
(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, что дает нам 3 варианта решений при каждом D.
(D ∧ ¬ D)= 0 при любых D, что дает нам два варианта решений (при D = 1, D = 0).
Следовательно: всего решений 2*3 = 6.
Итого 6 решений.
Ответ: 6
Сколько различных решений имеет уравнение
(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0
где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.
Пояснение.
Применим отрицание к обеим частям уравнения:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
Логическое ИЛИ истинно в трех случаях.
Вариант 1.
K ∧ L ∧ M = 1, тогда K, L, M = 1, а ¬L ∧ M ∧ N = 0. N любое, то есть 2 решения.
Вариант 2.
¬L ∧ M ∧ N = 1, тогда N, M = 1; L = 0, K любое, то есть 2 решения.
Следовательно, ответ 4.
Ответ: 4
A, B и С — целые числа, для которых истинно высказывание
¬ (А = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(С > B)).
Чему равно В, если A = 45 и C = 43?
Пояснение.
1) ¬(А = B); (A > B)→(B > C); (B > A)→(С > B);
2) эти простые высказывания связаны операцией ∧ (И, конъюнкция), то есть, они должны выполняться одновременно;
3) из ¬(А = B)=1 сразу следует, что А B;
4) предположим, что A > B, тогда из второго условия получаем 1→(B > C)=1; это выражение может быть истинно тогда и только тогда, когда B > C = 1;
5) поэтому имеем A > B > C, этому условию соответствует только число 44;
6) на всякий случай проверим и вариант A 0 →(B > C)=1;
это выражение истинно при любом B; теперь смотрим третье условие получаем
это выражение может быть истинно тогда и только тогда, когда C > B, и тут мы получили противоречие, потому что нет такого числа B, для которого C > B > A.
Ответ: 44.
Ответ: 44
Составьте таблицу истинности для логической функции
X = (А ↔ B) ∨ ¬(A → (B ∨ C))
в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В — числа 77, столбец значений аргумента С — числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему(включая нулевой набор). Переведите полученную двоичную запись значений функции X в десятичную систему счисления.
Пояснение.
Запишем уравнение, используя более простые обозначения операций:
1) это выражение с тремя переменными, поэтому в таблице истинности будет строчек; следовательно, двоичная запись чисел, по которым строятся столбцы таблицы А, В и С, должна состоять из 8 цифр
2) переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел
3) вряд ли вы сможете сразу написать значения функции Х для каждой комбинации, поэтому удобно добавить в таблицу дополнительные столбцы для расчета промежуточных результатов (см. таблицу ниже)
| А | В | С | X|
| 0 | 0 | ||
| 0 | 1 | 1 | |
| 0 | 0 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
4) заполняем столбцы таблицы:
| А | В | С | X | ||||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
значение равно 1 только в тех строчках, где А = В
значение равно 1 в тех строчках, где либо В либо С = 1
значение равно 0 только в тех строчках, где А = 1 и В + С = 0
значение — это инверсия предыдущего столбца (0 заменяется на 1, а 1 – на 0)
результат Х (последний столбец) — это логическая сумма двух столбцов и
5) чтобы получить ответ, выписываем биты из столбца Х сверху вниз:
6) переводим это число в десятичную систему:
Ответ: 171
Каково наибольшее целое число X, при котором истинно высказывание (10 (X+1)·(X+2))?
Пояснение.
Уравнение является операцией импликации между двумя отношениями:
1) Конечно, здесь можно применить тот же способ, что и в примере 2208, однако при этом понадобится решать квадратные уравнения (не хочется…);
2) Заметим, что по условию нас интересуют только целые числа, поэтому можно попытаться как─то преобразовать исходное выражение, получив равносильное высказывание (точные значения корней нас совершенно не интересуют!);
3) Рассмотрим неравенство : очевидно, что может быть как положительным, так и отрицательным числом;
4) Легко проверить, что в области высказывание истинно при всех целых , а в области — при всех целых (чтобы не запутаться, удобнее использовать нестрогие неравенства, и , вместо и );
5) Поэтому для целых можно заменить на равносильное выражение
6) область истинности выражения — объединение двух бесконечных интервалов;
7) Теперь рассмотрим второе неравенство : очевидно, что так же может быть как положительным, так и отрицательным числом;
8) В области высказывание истинно при всех целых , а в области — при всех целых , поэтому для целых можно заменить на равносильное выражение
9) область истинности выражения — закрытый интервал;
10) Заданное выражение истинно везде, кроме областей, где и ;
11) Обратите внимание, что значение уже не подходит, потому что там и , то есть импликация дает 0;
12) При подставлении 2, (10 (2+1) · (2+2)), или 0 → 0 что удовлетворяет условию.
Таким образом, ответ 2.
Ответ: 2
Каково наибольшее целое число X, при котором истинно высказывание
(50 (X+1)·(X+1))?
Пояснение.
Применим преобразование импликации и преобразуем выражение:
(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).
Логическое ИЛИ истинно когда истинно хотя бы одно логическое высказывание. Решив оба неравенства и учитывая, что видим, что наибольшее целое число, при котором выполняется хотя бы одно из них - 7 (на рисунке жёлтым изображено положительное решение второго неравенства, синим - первого).
Ответ: 7
Укажите значения переменных К, L, M, N, при которых логическое выражение
(¬(М ∨ L) ∧ К) → (¬К ∧ ¬М ∨ N)
ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.
Пояснение.
Дублирует задание 3584.
Ответ: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Пояснение.
Применим преобразование импликации:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Применим отрицание к обоим частям уравнения:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
Преобразуем:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Следовательно, M = 0, N = 0, рассмотрим теперь (¬K ∧ L ∨ M ∧ L):
из того, что M = 0, N = 0 следует, что M ∧ L = 0, тогда ¬K ∧ L = 1, то есть K = 0, L = 1.
Ответ: 0100
Укажите значения переменных K, L, M, N, при которых логическое выражение
(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)
ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.
Пояснение.
Запишем уравнение, используя более простые обозначения операций (условие «выражение ложно» означает, что оно равно логическому нулю):
1) из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных
2) из таблицы истинности операции «импликация» следует, что это выражение ложно тогда и только тогда, когда одновременно
3) первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда и ; отсюда следует (логическая сумма равна нулю), что может быть только при ; таким образом, три переменных мы уже определили
4) из второго условия, , при и получаем .
Дублирует задание
Ответ: 1000
Укажите значения логических переменных Р, Q, S, Т, при которых логическое выражение
(Р ∨ ¬Q) ∨ (Q → (S ∨ Т)) ложно.
Ответ запишите в виде строки из четырех символов: значений переменных Р, Q, S, T (в указанном порядке).
Пояснение.
(1) (Р ∨ ¬Q) = 0
(2) (Q → (S ∨ Т)) = 0
(1) (Р ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ Т)) = 0 Применим преобразование импликации:
¬Q ∨ S ∨ Т = 0 => S = 0, T = 0.
Ответ: 0100
Укажите значения переменных K, L, M, N, при которых логическое выражение
(K → M) ∨ (L ∧ K) ∨ ¬N
ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.
Пояснение.
Логическое "ИЛИ" ложно тогда и только тогда, когда ложны оба утверждения.
(K → M) = 0, (L ∧ K) ∨ ¬N = 0.
Применим преобразование импликации для первого выражения:
¬K ∨ M = 0 => K = 1, M = 0.
Рассмотрим второе выражение:
(L ∧ K) ∨ ¬N = 0 (см. результат первого выражения) => L ∨ ¬N = 0 => L = 0, N = 1.
Ответ: 1001.
Ответ: 1001
Укажите значения переменных K, L, M, N, при которых логическое выражение
(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
истинно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.
Пояснение.
Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.
1) (K → M) = 1 Применим преобразование импликации: ¬K ∨ M = 1
2) (K → ¬M) = 1 Применим преобразование импликации: ¬K ∨ ¬M = 1
Отсюда следует, что K = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1 Применим преобразование импликации: K ∨ (M ∧ ¬L ∧ N) = 1 из того что K = 0 получаем:
M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.
Ответ: 0011
Известно, что для целых чисел X, Y и Z истинно высказывание
(Z Чему равно Z, если X=25 и Y=48?
Пояснение.
Выполнив подстановку чисел получаем что Z = 47.
Обратим внимание, что это сложное высказывание состоит из трех простых
1) (Z 2) эти простые высказывания связаны операцией ∧ (И, конъюнкция), то есть, они должны выполняться одновременно.
3) из ¬(Z+1 24, а из ¬(Z+1 47.
4) из (Z Z Ответ: 47.
Ответ: 47
A, B и C – целые числа, для которых истинно высказывание:
(C Чему равно C, если A=45 и B=18?
Пояснение.
Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.
Подставим значения чисел в выражение:
1) (C (C 2) ¬(C+1 , C ≥ 44.
3) ¬(C+1 , C ≥ 17.
Из 2) и 1) следует, что C
Ответ: 44
¬(А = B) ∧ ((B A)) ∧ ((A 2C))
Чему равно A, если C = 8 и B = 18?.
Пояснение.
Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.
1) ¬(А = B) = 1, то есть А ≠ 18 = 1.
2) ((B A)) Применим преобразование импликации: (18 > A) ∨ (16 > A) = 1
3) (A 2C) Применим преобразование импликации: (A > 18) ∨ (A > 16) = 1
Из 2) и 3) следует, что (18 > A) и (A > 16), так как в противном случае возникает противоречие А = 17.
Ответ: 17
A, B и С – целые числа, для которых истинно высказывание
¬(А = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))
Чему равно B, если A = 45 и C = 18?
Пояснение.
Логическое "И" истинно только тогда, когда истинны все высказывания.