Сколько существует различных наборов значений логических переменных
Сколько существует различных наборов значений логических переменных x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
- Задать вопрос
- Регистрация
- Техподдержка
- Войти с логином и паролем
- Сбросить пароль
- Войти с телефоном
- Техподдержка
JS: 2.15.4
CSS: 4.9.14
jQuery: 3.6.0
DataForLocalStorage: 2022-06-10 01:16:03-standard
jQuery 
jQuery UI
Bootstrap
Font Awesome
Консультация онлайн # 191985
Составим таблицу функции (x1→x2)⊕(x3→x4):
Из неё видно, что первому условию удовлетворяют все наборы вида 0x10xxxxxx, 100xxxxxxx, 1011xxxxxx и 1110xxxxxx, где x — любое значение (всего 128+128+64+64=384 набора). Аналогично, второму условию удовлетворяют все наборы вида xx0x10xxxx, xx100xxxxx, xx1011xxxx и xx1110xxxx. Тогда одновременно первому и второму условию будут удовлетворять следующие наборы: 0x100xxxxx, 0x1011xxxx, 100x10xxxx, 101110xxxx, 11100xxxxx и 111011xxxx (всего 64+32+32+16+32+16=192 набора). Если учесть также наборы, удовлетворяющие третьему условию (xxxx0x10xx, xxxx100xxx, xxxx1011xx и xxxx1110xx), то первым трём условиям будут удовлетворять следующие наборы: 0x100x10xx, 0x101110xx, 100x100xxx, 100x1011xx, 1011100xxx, 10111011xx, 11100x10xx и 11101110xx (всего 16+8+16+8+8+4+8+4=72 набора). Наконец, с учётом наборов, удовлетворяющих четвёртому условию (xxxxxx0x10, xxxxxx100x, xxxxxx1011 и xxxxxx1110), решением будет 0x100x100x, 0x100x1011, 0x1011100x, 0x10111011, 100x100x10, 100×101110, 1011100×10, 1011101110, 11100x100x, 11100×1011, 111011100x, 1110111011 — 8+4+4+2+4+2+2+1+4+2+2+1=36 наборов.
Разбор 23 задания ЕГЭ 2016 по информатике из демоверсии
Разбор 23 задания ЕГЭ 2016 года по информатике из демоверсии. Это задание на умение строить и преобразовывать логические выражения (уметь вычислять логическое значение сложного высказывания по известным значениям элементарных высказываний). Это задание высокого уровня сложности. Примерное время выполнения задания 10 минут.
Задание 23:
Сколько существует различных наборов значений логических переменных x1, x2, … x9, y1, y2, … y9, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x9, y1, y2, … y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Разбор 23 задания ЕГЭ 2016:
1) Для начала, найдем количество решений для первого уравнения. Из уравнения видно, что если две соседних переменные не равны, то следующая пара переменных обязательно должна быть равной:
(xi ≠ yi)→(xi+1 = yi+1).
Если первая пара переменных одинаковая, то следующая должна иметь разные значения: (xi = yi)→(xi+1 ≠ yi+1).
Исходя из этого правила, построим таблицу истинности для первого уравнения с нужными нам строками (при которых функция истинна).
Пусть x1 и y1 имеют разные значения (0,1 или 1,0), тогда x2 и y2 будут одинаковы (0,0 или 1,1).
Пусть x1 и y1 имеют одинаковые значения (0,0 или 1,1), тогда x2 и y2 будут разные (0,1 или 1,0).
Вывод, по первому уравнению мы имеем 8 наборов переменных.
2) Теперь найдем количество решений для второго уравнения.
Варианты решений второго уравнения будут точно такими же, как и для первого.
3) Добавим для второй таблицы два столбца для общих переменных: x1 и y1
Не обращая внимания на столбцы значений x3 и y3 вставьте значения для x1 и y1, исходя из Таблицы 1.
Берем первую строку таблицы: x2=0, y2=1
Смотрим в Таблице 1, чему будут равны переменные x1 и y1 : при x2=0, а y2=1.
Значения переменных x1 и y1 могут быть либо x1=0, y1=0, либо x1=1, y1=1.
Заполним всю таблицу:
Из таблицы видно, что, после добавления второго уравнения, количество найденных решений увеличилось в два раза.
Все уравнения в нашей системе однотипны, значит каждое следующее уравнение также будет увеличивать количество решений в два раза.
Задача №23. Решение систем логических уравнений.
Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной.
Сколько существует различных наборов значений логических переменных 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.
Сколько существует различных наборов значений логических переменных x1, x2, . x9, y1, y2, . 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 наборов.
Решение систем логических уравнений методом визуального определения рекурсии.
Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.
Сколько различных решений имеет система уравнений
где 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) переменных:
Ni+1 = Ni + 1. Тогда для десяти переменных получим 11 наборов.
Решение систем логических уравнений различного типа
Сколько существует различных наборов значений логических переменных x1, . x4, y1. y4, z1. z4, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, . x4, y1, . y4, z1, . z4, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.
Заметим, что три уравнения системы одинаковы на различных независимых наборах переменных.
Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):
Сколько существует различных наборов значений логических переменных
Логические уравнения
Системы логических уравнений, содержащие однотипные уравнения
Задание 1 Сколько существует различных наборов значений логических переменных x1, х2, хЗ, х4, х5, хб, х7, х8, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, х2, хЗ, х4, х5, хб, х7, х8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Сделаем замену переменных:
(x1 —> х2) = y1; (хЗ—> х4) = y2; (х5 —> хб) = y3; (х7 —> х8) = y4.
Тогда можно записать систему в виде одного уравнения:
(y1 —> y2) ∧ (y2 — > y3) ∧ (y3 — > y4) = 1.
Для того, чтобы это равенство было выполнено, ни одна из импликаций не должна быть ложной
Вот все возможные варианты значений «y» (ключевым является тот факт, что переменные y независимы):
Импликация x1 —> х2 дает «0» при одном наборе переменных и «1» при трех наборах переменных.
Поскольку каждая из переменных «y» независима от другой, для каждой строки полученной таблицы перемножаем количество вариантов комбинаций исходных переменных:
Сложим количество вариантов: 1 + 3 + 9 + 27 + 81 = 121.
Задание 2. Сколько существует различных наборов значений логических переменных x1, х2, хЗ, х4, х5, хб, х7, х8, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, х2, хЗ, х4, х5, хб, х7, х8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Сделаем замену переменных:
(x1 —> х2) = y1; (хЗ—> х4) = y2; (х5 —> хб) = y3; (х7 —> х8) = y4; (х9 —> х10) = y5.
Тогда можно записать систему в виде одного уравнения.
(y1 —> y2) ∧ (y2 — > y3) ∧ (y3 — > y4) ∧ (y4 — > y5) = 1.
Для того, чтобы это равенство было выполнено, ни одна из импликаций не должна быть ложной
Вот все возможные варианты значений «y»(ключевым является тот факт, что переменные y независимы):
Импликация x1 —> х2 дает «0» при одном наборе переменных и «1» при трех наборах переменных.
Поскольку каждая из переменных «y» независима от другой, для каждой строки полученной таблицы перемножаем количество вариантов комбинаций исходных переменных:
Сложим количество вариантов: 1 + 3 + 9 + 27 + 81 + 243 = 364.
Задание 3. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, x8 которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, x6, x7, x8 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Запишем переменные в строчку: x1x2x3x4x5x6x7x8. Импликация ложна только в том случае, когда из истины следует ложь. Условие не выполняется, если в ряде после одинаковых цифр присутствует другая цифра. Например, «11101. » что означает невыполнение второго условия.
Рассмотрим комбинации переменных, удовлетворяющие всем условиям. Выпишем варианты, при которых все цифры чередуются, таких два: 10101010 и 01010101. Теперь для первого варианта, начиная с конца, будем увеличивать количество повторяющихся подряд цифр (настолько, насколько это возможно). Выпишем полученные комбинации: «10101011; 10101111. » таких комбинаций восемь. Аналогично для второго варианта: «01010101; 01010100. «. Таким образом, получаем 8 + 8 = 16 решений.
Задание 4. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, x6, x7, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Запишем переменные в строчку: x1x2x3x4x5x6x7. Импликация ложна только в том случае, когда из истины следует ложь. Условие не выполняется, если в ряду после одинаковых цифр присутствует другая цифра. Например, «11101. » что означает невыполнение второго условия.
Рассмотрим комбинации переменных, удовлетворяющие всем условиям. Выпишем варианты, при которых все цифры чередуются, таких два: 1010101 и 0101010. Теперь для первого варианта, начиная с конца, будем увеличивать количество повторяющихся подряд цифр(настолько, насколько это возможно). Выпишем полученные комбинации: «1010111; 1011111. » таких комбинаций восемь. Аналогично для второго варианта: «0101011; 0101111. «. Учтём, что при подсчёте комбинация для второго варианта комбинации 0000000 и 1111111 были учтены дважды. Таким образом, получаем 8 + 8 − 2 = 14 решений.
Задание 5. Сколько существует различных наборов значений логических переменных x1, x2, . x8, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x8 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Построим древо решений первого уравнения:
Заметим, что выражение (x3 ≡ x4) в двух случаях равно 1 и в двух случаях равно 0. Таким образом, одно уравнение имеет восемь решений.
Второе уравнение связано с первым только через выражение (x3 ≡ x4). Построим древо решений второго уравнения:
Для каждого из значений 0 и 1 выражения (x3 ≡ x4) существует четыре набора переменных x1, x2. x4, удовлетворяющих первому уравнению (см. первый рисунок). Таким образом, система из двух уравнений имеет 4 · 4 = 16 решений.
Третье уравнение связано со вторым только через выражение (x5 ≡ x6). Построим древо решений третьего уравнения:
Для каждого из значений 0 и 1 выражения (x5 ≡ x6) существует 2 · 4 = 8 наборов переменных x1, x2. x6, удовлетворяющих первому уравнению (см. первый и второй рисунок). Таким образом, система из трёх уравнений имеет 8 · 4 = 32 решения.
Задание 6. Сколько существует различных наборов значений логических переменных x1, x2, . x10, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x10 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Построим древо решений первого уравнения:
Заметим, что выражение (x3 ≡ x4) в двух случаях равно 1 и в двух случаях равно 0. Таким образом, одно уравнение имеет восемь решений.
Второе уравнение связано с первым только через выражение (x3 ≡ x4). Построим древо решений второго уравнения:
Для каждого из значений 0 и 1 выражения (x3 ≡ x4) существует четыре набора переменных x1, x2. x4, удовлетворяющих первому уравнению (см. первый рисунок). Таким образом, система из двух уравнений имеет 4 · 4 = 16 решений.
Третье уравнение связано со вторым только через выражение (x5 ≡ x6). Построим древо решений третьего уравнения:
Для каждого из значений 0 и 1 выражения (x5 ≡ x6) существует 2 · 4 = 8 наборов переменных x1, x2. x6, удовлетворяющих первому уравнению (см. первый и второй рисунок). Таким образом, система из трёх уравнений имеет 8 · 4 = 32 решения, система из четырёх — 64.
Задание 7. Сколько существует различных наборов значений логических переменных x1, x2, . x10, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x10 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Построим древо решений первого уравнения:
Заметим, что выражение (x3 ≡ x4) в двух случаях равно 1 и в двух случаях равно 0. Таким образом, одно уравнение имеет восемь решений.
Второе уравнение связано с первым только через выражение (x3 ≡ x4). Построим древо решений второго уравнения:
Для каждого из значений 0 и 1 выражения (x3 ≡ x4) существует четыре набора переменных x1, x2. x4, удовлетворяющих первому уравнению (см. первый рисунок). Таким образом, система из двух уравнений имеет 4 · 4 = 16 решений.
Третье уравнение связано со вторым только через выражение (x5 ≡ x6). Построим древо решений третьего уравнения:
Для каждого из значений 0 и 1 выражения (x5 ≡ x6) существует 2 · 4 = 8 наборов переменных x1, x2. x6, удовлетворяющих первому уравнению (см. первый и второй рисунок). Таким образом, система из трёх уравнений имеет 8 · 4 = 32 решения.
Аналогично система из четырёх уравнений будет иметь 64 решения.
Задание 8. Сколько существует различных наборов значений логических переменных x1, x2, . x8, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x8 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Рассмотрим первое уравнение.
При x1 = 1 возможны два случая: x2 = 0 и x2 = 1. В первом случае x3 = 1. Во втором — x3 либо 0, либо 1. При x1 = 0 также возможны два случая: x2 = 0 и x2 = 1. В первом случае x3 либо 0, либо 1. Во втором — x3 = 0. Таким образом, уравнение имеет 6 решений (см. рисунок).
Рассмотрим систему из двух уравнений.
Пусть x1 = 1. При x2 = 0 возможен лишь один случай: x3 = 1, переменная x4 = 0. При x2 = 1 возможно два случая: x3 = 0 и x3 = 1. В первом случае x4 = 1, во втором — x4 либо 0, либо 1. Всего имеем 4 варианта.
Пусть x1 = 0. При x2 = 1 возможен лишь один случай: x3 = 0, переменная x4 = 1. При x2 = 0 возможно два случая: x3 = 0 и x3 = 1. В первом случае x4 либо 1, либо 0, во втором — x4 = 0. Всего имеем 4 варианта.
Таким образом, система из двух уравнений имеет 4 + 4 = 8 вариантов (см. рисунок).
Система из трёх уравнений будет иметь 10 решений, из четырёх — 12. Отрицание в последнем уравнении действует только на комбинацию переменных, не связанных с с предыдущими уравнениями. Поэтому, количество решений данной в условии системы совпадает с количеством решений системы из шести однотипных уравнений (системы, в которой в последнем уравнении нет знака отрицания после конъюнкции), и равно 16.
Задание 9. Сколько существует различных наборов значений логических переменных x1, x2, . x8, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x8 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Построим древо решений первого уравнения:
Заметим, что выражение (x3 ≡ x4) в двух случаях равно 1 и в двух случаях равно 0. Таким образом, одно уравнение имеет восемь решений.
Второе уравнение связано с первым только через выражение (x3 ≡ x4). Построим древо решений второго уравнения:
Для каждого из значений 0 и 1 выражения (x3 ≡ x4) существует четыре набора переменных x1, x2. x4, удовлетворяющих первому уравнению (см. первый рисунок). Таким образом, система из двух уравнений имеет 4 · 4 = 16 решений.
Третье уравнение связано со вторым только через выражение (x5 ≡ x6). Построим древо решений третьего уравнения:
Для каждого из значений 0 и 1 выражения (x5 ≡ x6) существует 2 · 4 = 8 наборов переменных x1, x2. x6, удовлетворяющих первому уравнению (см. первый и второй рисунок). Таким образом, система из трёх уравнений имеет 8 · 4 = 32 решения.
Задание 10. Сколько существует различных наборов значений логических переменных x1, x2, . x12, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x12 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Построим древо решений первого уравнения:
Заметим, что выражение (x3 ≡ x4) в двух случаях равно 1 и в двух случаях равно 0. Таким образом, одно уравнение имеет восемь решений.
Второе уравнение связано с первым только через выражение (x3 ≡ x4). Построим древо решений второго уравнения:
Для каждого из значений 0 и 1 выражения (x3 ≡ x4) существует четыре набора переменных x1, x2. x4, удовлетворяющих первому уравнению (см. первый рисунок). Таким образом, система из двух уравнений имеет 4 · 4 = 16 решений.
Третье уравнение связано со вторым только через выражение (x5 ≡ x6). Построим древо решений третьего уравнения:
Для каждого из значений 0 и 1 выражения (x5 ≡ x6) существует 2 · 4 = 8 наборов переменных x1, x2. x6, удовлетворяющих первому уравнению (см. первый и второй рисунок). Таким образом, система из трёх уравнений имеет 8 · 4 = 32 решения.
Аналогично система из четырёх уравнений будет иметь 64 решения, система из пяти уравнений — 128.
Логические уравнения
Задание 1. Сколько различных решений имеет уравнение J ∧ ¬ K ∧ L ∧ ¬ M ∧ (N ∨ ¬ N) = 0, где J, K, L, M, N — логические переменные?
В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Выражение (N ∨ ¬ N) ис тин но при любом N, по это му
J ∧ ¬ K ∧ L ∧ ¬ M = 0.
Применим отрицание к обеим частям логического уравнения и используем закон де Моргана ¬ (А ∧ В ) = ¬ А ∨ ¬ В . По лу чим
Логическая сумма равна 1, если хотя бы одно из составляющих ее высказываний равно 1. Поэтому полученному уравнению удовлетворяют любые комбинации логических переменных кроме случая, когда все входящие в уравнение величины равны 0. Каждая из 4 переменных может быть равна либо 1, либо 0, поэтому всевозможных комбинаций 2·2·2·2 = 16. Следовательно, уравнение имеет 16 −1 = 15 решений.
Осталось заметить, что найденные 15 решений соответствуют любому из двух возможных значений значений логической переменной N, поэтому исходное уравнение имеет 30 решений.
Задание 2. Сколько различных решений имеет уравнение
((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 ре ше ния .
(J ∧ ¬ K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬ K) ∨ (0 ∧ N ∧ L) = 0.
(¬J ∨ K) ∨ ¬ M ∨ ¬ N ∨ ¬ L = (1 ∨ K) ∨ 1 ∨ ¬ N ∨ ¬ L.
Задание 3. Сколько различных решений имеет уравнение:
¬((J → K) → (L ∧ M ∧ N)) ∨ ¬ ((L ∧ M ∧ N) → ( ¬ J ∨ K)) ∨ (M ∧ J) = 0
Используем формулу A → B = ¬ A ∨ B
Рассмотрим первую подформулу:
¬((¬J ∨ K) → (M ∧ N ∧ L)) = ¬ ( ¬ ( ¬ J ∨ K) ∨ (M ∧ N ∧ L)) = ¬ ((J ∧ ¬ K) ∨ (M ∧ N ∧ L)) =
Учитывая, что ¬(А ∨ В ) = ¬А ∧ ¬В ,
= (¬J ∨ K) ∧ ( ¬ M ∨ ¬ N ∨ ¬ L)
Рассмотрим вторую подформулу
¬((L ∧ M ∧ N) → ( ¬ J ∨ K)) = ¬ ( ¬ (L ∧ M ∧ N) ∨ ( ¬ J ∨ K)) = L ∧ M ∧ N ∧ J ∧ ¬ K
Применим отрицание к левой и правой части уравнения, получится
[(J ∧ ¬ K) ∨ (M ∧ N ∧ L)] ∧ [ ¬ L ∨ ¬ M ∨ ¬ N ∨ ¬ J ∨ K] ∧ [ ¬ M ∨ ¬ J] = 1
1) (¬M ∨ ¬ J) = 1, сле до ва тель но ,
0 ∧ ¬ K ∧ ¬ L ∨ ¬ N ∨ K, сле до ва тель но , 0 ре ше ний .
[(0 ∧ ¬ K) ∨ (1 ∧ N ∧ L)] ∧ [ ¬ L ∨ 0 ∨ ¬ N ∨ 1 ∨ K] ∧ [ ¬ M ∨ 1] = N ∧ L ∧ ¬ L ∨ ¬ N ∨ 1 ∨ K = 1 => L=N=1, следовательно, 2 решения.
[(1 ∧ ¬ K) ∨ (0 ∧ N ∧ L)] ∧ [ ¬ L ∨ ¬ 0 ∨ ¬ N ∨ ¬ 1 ∨ K] ∧ [ ¬ 0 ∨ ¬ 1] = 1, сле до ва тель но , 4 ре ше ния .
Задание 4. Сколько различных решений имеет уравнение
((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 решений.
Задание 5. Сколько различных решений имеет уравнение
где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.
Выражение истинно в трех случаях, когда (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 ре ше ния .
Задание 6. Сколько различных решений имеет уравнение
(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.
Следовательно, существует только одно решение уравнения.
Задание 7. Сколько различных решений имеет уравнение
(X ∨ Y ∨ Z) → (X ∧ P) = 1
где X, Y, Z, P – логические переменные? В ответе не нужно перечислять все различные наборы значений, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.
Применим преобразование импликации:
(X ∨ Y ∨ Z) → (X ∧ P) = 1;
¬(X ∨ Y ∨ Z) ∨ (X ∧ P) = 1;
(¬X ∧ ¬ Y ∧ ¬ Z) ∨ (X ∧ P) = 1; (1)
Логическое «ИЛИ» ложно , когда ложны оба утверждения.
Логическое «И» истинно только тогда, когда истинны оба утверждения.
(¬X ∧ ¬ Y ∧ ¬ Z) = 1 тогда X = 0, Y = 0, Z = 0.
Тогда из (1) следует, что P может быть как 1, так и 0, то есть 2 набора решений.
(¬X ∧ ¬ Y ∧ ¬ Z) = 0, (X ∧ P) = 1.
Тогда P = 1, X = 1.
(0 ∧ ¬ Y ∧ ¬ Z) = 0 => есть 4 ре ше ния .
В итоге 6 решений.
Задание 8. Сколько различных решений имеет уравнение
где 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 решений.
Задание 10. Сколько различных решений имеет уравнение
(¬K ∨ ¬ L ∨ ¬ M) ∧ (L ∨ ¬ M ∨ ¬ N) = 0
где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.
Применим отрицание к обеим частям уравнения:
(K ∧ L ∧ M) ∨ ( ¬ L ∧ M ∧ N) = 1
Логическое ИЛИ истинно в трех случаях.
K ∧ L ∧ M = 1, тогда K, L, M = 1, а ¬ L ∧ M ∧ N = 0. N любое , то есть 2 ре ше ния .
¬L ∧ M ∧ N = 1, тогда N, M = 1; L = 0, K любое , то есть 2 ре ше ния .
Следовательно, ответ 4.
Системы логических уравнений, содержащие не однотипные уравнения
Задание 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, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
1) Из последнего уравнения следует, что глобально мы имеем три варианта — x1=1, y1=1; x1=0, y1=1; x1=1, y1=0.
2) Логическое И истинно, только тогда, когда истины все утверждения, а импликация ложна только в случае, если из истинного следует ложное.
3) Уравнение (1) описывает ряд переменных
4) Рассмотрим вариант x1=1, y1=1. Так как первые числа каждого ряда равны 1, то все следующие тоже равны 1. Существует только одна комбинация для этого варианта.
5) Рассмотрим вариант x1=0, y1=1. Для y-ряда все переменные равны 1, для x же существует 5 комбинаций, так как в ряде x может быть от 1 до 5 нолей включительно.
6) Последний вариант рассмотрим аналогично предыдущему. Там существует всего 5 комбинаций.
Правильный ответ: 5+5+1=11 комбинаций.
Задание 2. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5 ) = 1
(y5 → y4) ∧ (y4 → y3) ∧ (y3 → y2) ∧ (y2 → y1 ) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
1) Из последнего уравнения следует, что глобально мы имеем x3=1, y3=1.
2) Логическое И истинно, только тогда, когда истины все утверждения, а импликация ложна только в случае, если из истинного следует ложное.
3) Уравнение (1) описывает ряд переменных
4) Рассмотрим вариант x3=1, y3=1. Тогда все следующие: x4, x5, y2, y1 тоже равны 1. Остаются переменные x1, x2, y4, y5. Так как x2 следует из x1, для них мы имеем 3 варианта, аналогично для y4 и y5. 33=9.
Задание 3. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) = 1
(¬y1 ∨ y2) ∧ ( ¬ y2 ∨ y3) ∧ ( ¬ y3 ∨ y4) = 1
(y1 → x1) ∧ (y2 → x2) ∧ (y3 → x3) ∧ (y4 → x4) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Конъюнкция истина тогда и только тогда, когда каждое высказывание истинно.
Для первого выражения это означает, что, если х1 равен 1, то х2, х3 и х4 также равны 1, т. е. для х1. х4 решения существуют только в виде «1111», «0111», «0011», «0001» и «0000».
Применив преобразование импликации ко второму выражению, увидим, что оно аналогично первому.
В третьем выражении из «y» следует соответствующее ему «x», это означает, что если y = 1, то и x = 1.
Следовательно, первому набору для x «1111» соответствует 5 наборов y. Второму — 4, третьему — 3, и. т. д.
Следовательно, ответ: 5 + 4 + 3 + 2 + 1 = 15.
Задание 4. Сколько существует различных наборов значений логических переменных 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, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
1) Из последнего уравнения следует, что глобально мы имеем три варианта — x1=1, y1=1; x1=0, y1=1; x1=0, y1=0.
2) Логическое И истинно, только тогда, когда истины все утверждения, а импликация ложна только в случае, если из истинного следует ложное.
3) Уравнение (1) описывает ряд переменных
4) Рассмотрим вариант x1=1, y1=1. Так как первые числа каждого ряда равны 1, то все следующие тоже равны 1. Существует только одна комбинация для этого варианта.
5) Рассмотрим вариант x1=0, y1=1. Для y-ряда все переменные равны 1, для x же существует 5 комбинаций, так как в ряде x может быть от 1 до 5 нолей включительно.
6) Последний вариант рассмотрим аналогично предыдущему. Там существует всего 25 комбинаций.
Правильный ответ: 25+5+1=31 комбинация.
Задание 5. Сколько существует различных наборов значений логических переменных x1, х2, хЗ, х4, х5, хб, y1, у2, уЗ, у4, у5, у6 которые удовлетворяют всем перечисленным ниже условиям?
(x1 → х 2) ∧ ( х 2 → хЗ ) ∧ ( хЗ → х 4) ∧ ( х 4 → х 5) ∧ ( х 5 → х 6) = 1
(y1 → y2) ∧ ( у 2 → уЗ ) ∧ ( уЗ → у 4) ∧ ( у 4 → у 5) ∧ ( у 5 → у 6) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, х2, хЗ, х4, х5, y1, у2, уЗ, у4, у5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
1) Из последнего уравнения следует, что глобально мы имеем три варианта — x1=1, y1=1; x1=0, y1=1; x1=1, y1=0.
2) Логическое И истинно, только тогда, когда истины все утверждения, а импликация ложна только в случае, если из истинного следует ложное.
3) Уравнение (1) описывает ряд переменных
4) Рассмотрим вариант x1=1, y1=1. Так как первые числа каждого ряда равны 1, то все следующие тоже равны 1. Существует только одна комбинация для этого варианта.
5) Рассмотрим вариант x1=0, y1=1. Для y-ряда все переменные равны 1, для x же существует 6 комбинаций, так как в ряде x может быть от 1 до 6 нолей включительно.
6) Последний вариант рассмотрим аналогично предыдущему. Там существует всего 6 комбинаций.
Правильный ответ: 6+6+1=13 комбинаций.
Задание 6. Сколько существует различных наборов значений логических переменных x1, х2, хЗ, х4, х5, y1, у2, уЗ, у4, у5, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → х 2) ∧ ( х 2 → хЗ ) ∧ ( хЗ → х 4) ∧ ( х 4 → х 5 ) = 1
(y1 → y2) ∧ ( у 2 → уЗ ) ∧ ( уЗ → у 4) ∧ ( у 4 → у 5 ) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, х2, хЗ, х4, х5, y1, у2, уЗ, у4, у5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
1) Из последнего уравнения следует, что глобально мы имеем три варианта — x1=1, y1=1; x1=0, y1=1; x1=1, y1=0.
2) Логическое И истинно, только тогда, когда истины все утверждения, а импликация ложна только в случае, если из истинного следует ложное.
3) Уравнение (1) описывает ряд переменных
4) Рассмотрим вариант x1=1, y1=1. Так как первые числа каждого ряда равны 1, то все следующие тоже равны 1. Существует только одна комбинация для этого варианта.
5) Рассмотрим вариант x1=0, y1=1. Для y-ряда все переменные равны 1, для x же существует 5 комбинаций, так как в ряде x может быть от 1 до 5 нолей включительно.
6) Последний вариант рассмотрим аналогично предыдущему. Там существует всего 5 комбинаций.
Правильный ответ: 5+5+1=11 комбинаций.
Задание 7. Сколько существует различных наборов значений логических переменных 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, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
1) Из последнего уравнения следует, что глобально мы имеем три варианта: x5=1, y5=1; x5=0, y5=0; x5=0, y5=1.
2) Логическое И истинно, только тогда, когда истины все утверждения, а импликация ложна только в случае, если из истинного следует ложное.
3) Уравнение (1) описывает ряд переменных
4) Рассмотрим вариант x5=1, y5=1. Тогда остальные переменные могут принимать любые значения: всего таких комбинаций 25.
5) Рассмотрим вариант х5=0, у5=0. Тогда все переменные равны 0, следовательно, 1 комбинация.
6) Рассмотрим вариант х5=0, у5=1. Тогда все переменные х равны 0, а переменные у могут принимать любые значения. Всего таких комбинаций 5.
Задание 8. Сколько существует различных наборов значений логических переменных x1, х2, хЗ, х4, х5, у1, у2, уЗ, у4, у5, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, х2, хЗ, х4, х5, у1, у2, уЗ, у4, у5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Заметим, что первые два уравнения связаны друг с другом только через третье.
Найдем количество решений первого уравнения. Каждая из переменных x1, . , x5 может принимать только два значения. Импликация ложна только тогда, когда из истины следует ложь. Если записать значения переменных подряд, то можно увидеть, что для того, чтобы равенство выполнялось, необходимо, чтобы после «1» никогда не стоял «0». Следовательно, получаем такие решения: (x1,x2,x3,x4,x5) = 00000, 00001, 00011, 00111, 01111, 11111.
Во втором уравнении необходимо, чтобы после «0» никогда не стояла «1». Следовательно, получаем такие решения: (y1,y2,y3,y4,y5) = 00000, 10000, 11000, 11100, 11110, 11111. Таким образом, система из двух уравнений имеет 6·6 = 36 решений: для каждого набора переменных y существует 6 наборов переменных x.