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

Сколько различных решений имеет уравнение J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, где J, K, L, M, N — логические переменные?

В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Выражение (N ∨ ¬N) истинно при любом N, поэтому

Применим отрицание к обеим частям логического уравнения и используем закон де Моргана ¬ (А ∧ В) = ¬ А ∨ ¬ В . Получим

Логическая сумма равна 1, если хотя бы одно из составляющих ее высказываний равно 1. Поэтому полученному уравнению удовлетворяют любые комбинации логических переменных кроме случая, когда все входящие в уравнение величины равны 0. Каждая из 4 переменных может быть равна либо 1, либо 0, поэтому всевозможных комбинаций 2·2·2·2 = 16. Следовательно, уравнение имеет 16 −1 = 15 решений.

Осталось заметить, что найденные 15 решений соответствуют любому из двух возможных значений логической переменной N, поэтому исходное уравнение имеет 30 решений.

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

Сложим количество вариантов: 1 + 3 + 9 + 27 + 81 + 243 = 364.

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

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

Запишем переменные в строчку: x₁x₂x₃x₄x₅x₆x₇x₈. Импликация ложна только в том случае, когда из истины следует ложь. Условие не выполняется, если в ряде после одинаковых цифр присутствует другая цифра. Например, «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, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Запишем переменные в строчку: x₁x₂x₃x₄x₅x₆x₇. Импликация ложна только в том случае, когда из истины следует ложь. Условие не выполняется, если в ряду после одинаковых цифр присутствует другая цифра. Например, «11101. » что означает невыполнение второго условия.

Рассмотрим комбинации переменных, удовлетворяющие всем условиям. Выпишем варианты, при которых все цифры чередуются, таких два: 1010101 и 0101010. Теперь для первого варианта, начиная с конца, будем увеличивать количество повторяющихся подряд цифр(настолько, насколько это возможно). Выпишем полученные комбинации: «1010111; 1011111. » таких комбинаций восемь. Аналогично для второго варианта: «0101011; 0101111. «. Учтём, что при подсчёте комбинация для второго варианта комбинации 0000000 и 1111111 были учтены дважды. Таким образом, получаем 8 + 8 − 2 = 14 решений.

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

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

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

Заметим, что выражение (x₃ ≡ x₄) в двух случаях равно 1 и в двух случаях равно 0. Таким образом, одно уравнение имеет восемь решений.

Второе уравнение связано с первым только через выражение (x₃ ≡ x₄). Построим древо решений второго уравнения:

Для каждого из значений 0 и 1 выражения (x₃ ≡ x₄) существует четыре набора переменных x₁, x₂. x₄, удовлетворяющих первому уравнению (см. первый рисунок). Таким образом, система из двух уравнений имеет 4 · 4 = 16 решений.

Третье уравнение связано со вторым только через выражение (x₅ ≡ x₆). Построим древо решений третьего уравнения:

Для каждого из значений 0 и 1 выражения (x₅ ≡ x₆) существует 2 · 4 = 8 наборов переменных x₁, x₂. x₆, удовлетворяющих первому уравнению (см. первый и второй рисунок). Таким образом, система из трёх уравнений имеет 8 · 4 = 32 решения.

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

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

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

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

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

Аналогично система из четырёх уравнений будет иметь 64 решения.

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

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

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

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

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

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

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

Система из трёх уравнений будет иметь 10 решений, из четырёх — 12. Отрицание в последнем уравнении действует только на комбинацию переменных, не связанных с с предыдущими уравнениями. Поэтому, количество решений данной в условии системы совпадает с количеством решений системы из шести однотипных уравнений (системы, в которой в последнем уравнении нет знака отрицания после конъюнкции), и равно 16.

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

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

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

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

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

Аналогично система из четырёх уравнений будет иметь 64 решения, система из пяти уравнений — 128.

Задание 1. Сколько различных решений имеет уравнение J ∧ ¬ K ∧ L ∧ ¬ M ∧ (N ∨ ¬ N) = 0, где J, K, L, M, N — логические переменные?

Выражение (N ∨ ¬ N) ис тин но при любом N, по это му

J ∧ ¬ K ∧ L ∧ ¬ M = 0.

Осталось заметить, что найденные 15 решений соответствуют любому из двух возможных значений значений логической переменной N, поэтому исходное уравнение имеет 30 решений.

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

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬ K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

где 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) → (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 = 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) ∨ ( ¬ 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.

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

1) Из последнего уравнения следует, что глобально мы имеем три варианта — x1=1, y1=1; x1=0, y1=1; x1=0, y1=0.

3) Уравнение (1) описывает ряд переменных . Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x (или y) в порядке возрастания их номеров, справа будут единицы, а слева — нули.

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.

3) Уравнение (1) описывает ряд переменных . Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x (или y) в порядке возрастания их номеров, справа будут нули, а слева — единицы.

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

1) Из последнего уравнения следует, что глобально мы имеем три варианта — x1=1, y1=1; x1=0, y1=1; x1=1, y1=0.

3) Уравнение (1) описывает ряд переменных . Так как из переменной с более низким номером всегда следует переменная с более высоким, если любую переменную из этого ряда приравнять 1, то все следующие должны также быть равны 1. Для уравнения (2) существует то же самое правило. Иначе говоря, если записать переменные x (или y) в порядке возрастания их номеров, справа будут нули, а слева — единицы.

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

1) Из последнего уравнения следует, что глобально мы имеем три варианта: x5=1, y5=1; x5=0, y5=0; x5=0, y5=1.

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 единиц, что определяется по формуле:

источники:

http://www.sites.google.com/site/reseniezadanijinformatikipoege/home/zadanie-23

http://nuancesprog.ru/p/8926/