Сколько решений имеет логическое уравнение x1 x2
- Войти
- Регистрация
- Главная
- ЕГЭ
- Вопросы и ответы
- Перевод баллов
- Соответствие заданий
- Программирование
- Типы данных Pascal
- Математические функции
- Логические операции
- Приоритет операций
- Законы логики
- О системах счисления
- Перевод чисел
- Таблица триад и тетрад
- Досрочный-2016
- Демо-2016
- Досрочный-2015
- Алгебра логики
- Вариант 1
- Вариант 2
- Вариант 3
- Вариант 4
- Вариант 5
- Вариант 6
- Вариант 7
- Вариант 8
- Вариант 9
- Вариант 10
- Степени двойки
- IP, маска и адрес сети
- Решатор 5
- Решатор 13
Скобки независимы друг от друга. Заменим каждую отдельной переменной:
a → b = 1
b → c = 1В битовой цепочке не может быть единицы перед нулём, т.к. в этом случае уравнение будет ложным. Построим цепочки по этому правилу:
a 1 0 0 0
b 1 1 0 0
c 1 1 1 0Всего четыре цепочки.
Каждая из переменных a, b, c является импликацией иксов, значит на каждую истину приходится 3 варианта, а на каждую ложь — 1 вариант.
То есть для первой цепочки (1 1 1) приходится 3^3 = 27 наборов, для второй цепочки (0 1 1) — 3^2 = 9 наборов, для третьей цепочки (0 0 1) — три набора, и для четвёртой цепочки (0 0 0) — один набор.
27+9+3+1 = 40 решений.Задача. Сколько различных решений имеет логическое уравнение?
Задача.
Сколько различных решений имеет логическое уравнение?1) Для получения истинности необходимо, чтобы все части конъюнкции были равны единице.
Для правой части конъюнкции это выполняется только тогда, когда B=C=0 и D=1.
В левой части необходимо, чтобы хотя бы один из членов дизъюнкции был равен единице. Значит A=1.
Ответ: одно решение.2) Для получения нуля необходимо, чтобы обе части дизъюнкции были равны нулю.
Отсюда А=В=С=0.
Для соблюдения ложности конъюнкции D может принять любое значение.
Ответ: два решения.3) Для получения нуля необходимо, чтобы все части дизъюнкции были равны нулю.
Первая импликация равна нулю только при А=1 и С=0.
Во втором члене конъюнкция будет равна нулю только при условии, что В=0.
В третьем члене импликация равна нулю только при D=1.
Ответ: одно решение.4) Всего четыре переменных. 16 комбинаций.
Только в двух случаях эта импликация равна нулю. При этом в левой части должны быть А=В=С=1. Тогда в левой части D может иметь любое значение.
Итого, 16-2=14 решений.
Проверьте пожалуйста!)Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1
Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1
Сколько различных решений имеет логическое уравнение
((x1 ≡ x2) → (x3 ≡ x4)) ∧ ((x3 ≡ x4) → ( x5 ≡ x6)) ∧ (( x5 ≡ x6) → (x7 ≡ x8)) = 1
где x1,x2,…,x6,x7,x8 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов
Произведём замену: y1 = x1 ≡ x2; y2 = x3 ≡ x4; y3 = x5 ≡ x6; y4 = x7 ≡ x8. Получим уравнение:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1.
Логическое И истинно, только тогда, когда истины все утверждения, поэтому данное уравнение эквивалентно системе уравнений:
Импликация ложна только в случае, если из истинного следует ложное. Данная система уравнений описывает ряд переменных . Заметим, что если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. То есть решения системы уравнений: 0000; 0001; 0011; 0111; 1111.
Уравнения вида xN ≡ x = 0 имеют два решение, уравнения вида xN ≡ x = 1 также имеет два решения.
Найдём сколько наборов переменных x соответствуют каждому из решений y.
Каждому из решений 0000; 0001; 0011; 0111; 1111 соответствует 2 · 2 · 2 · 2 = 16 решений. Всего 16 · 5 = 80 решений.
Выясним сколько решений имеет логическое уравнение x1 x2 x3 x4 1
Сложим количество вариантов: 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) описывает ряд переменных . Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x (или y) в порядке возрастания их номеров, слева будут нули, а справа — единицы.
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) описывает ряд переменных . Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило, только наоборот: из переменной с более высоким номером всегда следует переменная с более низким. Иначе говоря, если записать переменные x в порядке возрастания их номеров, справа будут единицы, а слева — нули, в y — напротив, слева единицы, справа — нули.
4) Рассмотрим вариант x3=1, y3=1. Тогда все следующие: x4, x5, y2, y1 тоже равны 1. Остаются переменные x1, x2, y4, y5. Так как x2 следует из x1, для них мы имеем 3 варианта, аналогично для y4 и y5. 3 3=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) описывает ряд переменных . Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x (или y) в порядке возрастания их номеров, справа будут единицы, а слева — нули.
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) описывает ряд переменных . Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x (или y) в порядке возрастания их номеров, справа будут нули, а слева — единицы.
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) описывает ряд переменных . Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x (или y) в порядке возрастания их номеров, справа будут нули, а слева — единицы.
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) описывает ряд переменных . Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x в порядке возрастания их номеров, справа будут нули, а слева — единицы, в y — так же.
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.
Метод подсчёта количества решений
Линейные алгебраические уравнения — одни из самых простых уравнений, которые мы можем решить. Если в уравнении только одна переменная, решение тривиально, в то время как для системы линейных уравнений существует множество способов найти уникальные решения.
В этой статье нас интересует частный случай линейного уравнения с несколькими переменными. Хорошо известно, что подобное уравнение имеет бесконечное число решений. Мы наложим определённые ограничения и в значительной степени сократим количество решений.
Общая форма интересующего нас уравнения:
где n и m — положительные целые числа.
Наша задача — найти число решений этого уравнения, предполагая, что xᵢ являются целыми числами. Это предположение значительно снижает число решений заданного уравнения.
Нам нужен метод
Давайте начнём с частного случая общего уравнения:
Нетрудно найти все решения этого уравнения методом простого счёта. Решения заданы парами (x₁, x₂):
Мы видим, что уравнение имеет шесть решений. Также нетрудно предположить, что, если мы заменим правую часть определённым положительным целым числом m, решения будут выглядеть так:
и мы сможем подсчитать число решений — m+1.
Это было просто, верно?
Теперь возьмём немного более сложный вариант с тремя переменными, скажем:
С несколько большими усилиями, чем в предыдущем примере, находим решения в виде наборов из трёх чисел (x₁, x₂, x₃):
Число решений в этом случае равно 10.
Легко представить, что метод прямого счёта может стать очень утомительным для уравнения с большим количеством переменных. Он также становится утомительным, если целое число в правой части уравнения становится больше — например, если в правой части у нас будет 8, а не 3, решений будет уже 45. Разумеется, не хотелось бы искать все эти решения методом прямого счёта.
Значит, нужен эффективный метод.
Разрабатываем метод
Существует ещё один способ, которым можно решить предыдущие два уравнения. Давайте снова начнём с этого уравнения:
Одним из решений было (5, 0). Давайте преобразуем его в:
Мы разложили решение на нули и единицы, соответствующие каждому числу. Ненулевую часть (в данном случае 5) мы разложили на соответствующее число единиц, а ноль преобразовали в ноль. Таким же образом мы можем разложить и другое решение:
Мы поменяли прежнее расположение нуля, чтобы получить новое решение. Итак, два числа в парах (обозначенные красным и голубым) разделены нулём (чёрный) в разложенном виде. Таким же образом запишем оставшиеся решения:
Записав решения таким образом, видим закономерность. Кажется, все решения — это просто перестановки нулей и единиц. Вопрос о том, сколько существует решений, становится эквивалентным вопросу как много таких перестановок нулей и единиц может быть сделано, начиная с любой из конфигураций.
В данном случае у нас есть 6 местоположений в разложенной конфигурации для размещения нулей и единиц. Мы можем выбрать простейшее решение в качестве начальной конфигурации:
Теперь всё, что нам нужно найти, это общее число способов, которыми можно заполнить шесть местоположений пятью единицами и одним нулём.
Подобные задачи подсчёта мы можем решить различными способами, но наиболее эффективным будет способ, разработанный в такой области математики как комбинаторика, которая даёт нам формулу для числа способов перестановки r объектов в n местоположений:
где n! (читается как “n факториал”) определяется как произведение всех целых чисел от 1 до n, т.е. n! = 1 × 2 × 3 × ⋅ ⋅ ⋅ × n. Мы также определяем 0! = 1.
Эта формула обычно записывается в компактной форме как:
Теперь, возвращаясь к задаче, мы можем использовать эту формулу для нахождения числа способов перестановки пяти единиц в шести местоположениях:
Это то же самое число, что мы получили методом прямого счёта!
Выглядит многообещающе, поэтому давайте проверим, сможем ли мы найти таким способом число решений второго линейного уравнения:
Некоторые решения можно записать в разложенном виде:
В этот раз нам нужно заполнить тремя единицами и двумя нулями пять местоположений. Используя формулу мы можем найти число способов расположения чисел:
И опять то же число, что мы получили методом прямого счёта. Мы можем также найти число решений для нерешённого случая, где в правой части уравнения 8 вместо 3. Одним из решений будет:
а нам нужно найти число способов разместить 8 единиц в 10 местоположениях, и это будет:
как и утверждалось выше.
Если мы уверены в том, что этот метод работает для всех случаев, нам нужна общая формула. Напомним, что общее уравнение имеет вид:
Простейшее решение этого уравнения:
Поскольку существует n переменных, количество нулей в этом решении равно n-1. Таким образом, разложение выглядит так:
В разложенной конфигурации видим m и n-1 нулей (как утверждалось выше).
Следовательно, общее число местоположений, которые нужно заполнить, равно (m+n-1). Единственное, что остаётся — найти число способов, которыми можно заполнить m+n-1 местоположений m единиц, что определяется по формуле:
Ещё пример задания:
где x1, …, x3, y1, …, y3, z1, …, z3 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение (последовательное подключение уравнений):
перепишем уравнения с помощью более простых обозначений:
заметим, что последние 3 уравнения независимы друга от друга, и вся система связана только через первое уравнение
рассмотрим второе уравнение
оно имеет три решения, каждое из которых соответствует единичному значению одного из слагаемых:
аналогичные уравнения 3-4 тоже имеют по три решения
теперь рассмотрим множество решений системы уравнений 2-3
при ограничении, которое накладывается первым уравнением:
поскольку импликация дает ложное значение (0) только для случая 10, первое уравнение в исходной системе запрещает комбинацию
.рассмотрим решение уравнений 2 и 3:
Эти уравнения независимы, поэтому система уравнений 2-3 (без дополнительных ограничений) имеет 33=9 решений
При ограничении
:в случае
имеем только одно решение системы, когда
в уравнении 2, то есть
для двух решений уравнения 3, когда
, подходят все 3 отдельных решения уравнения 2поэтому количество решений системы уравнений 2-3 при ограничении
вычисляется как 1 + 3 + 3 = 7 решенийрассуждая аналогично, подключаем уравнение 4 и ограничение
, получаем, что количество решений системы уравнений 2-4 при ограничении
вычисляется как 1 + 7 + 7 = 15 решений