Помощь по Теле2, тарифы, вопросы

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, где J, K, L, M, N — логические переменные?

Пояснение.

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

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

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

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

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

Ответ: 30

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

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

где J, K, L, M, N – логические переменные?

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

Пояснение.

Используем формулы A → B = ¬A ∨ B и ¬(А ∨ В) = ¬А ∧ ¬В

Рассмотрим первую подформулу:

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

Рассмотрим вторую подформулу

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

Рассмотрим третью подформулу

1) M → J = 1 следовательно,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Объединим:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 следовательно, 4 решения.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Объединим:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L следовательно, 4 решения.

в) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Ответ: 4 + 4 = 8.

Ответ: 8

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

((K ∨ L) → (L ∧ M ∧ N)) = 0

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

Пояснение.

перепишем уравнение, используя более простые обозначения операций:

((K + L) → (L · M · N)) = 0

1) из таблицы истинности операции «импликация» (см. первую задачу) следует, что это равенство верно тогда и только тогда, когда одновременно

K + L = 1 и L · M · N = 0

2) из первого уравнения следует, что хотя бы одна из переменных, K или L, равна 1 (или обе вместе); поэтому рассмотрим три случая

3) если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения

4) если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

5) если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

6) всего получаем 4 + 3 + 3 = 10 решений.

Ответ: 10

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

(K ∧ L) ∨ (M ∧ N) = 1

Пояснение.

Выражение истинно в трех случаях, когда (K ∧ L) и (M ∧ N) равны соответственно 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N равны 1, а K и L любые, кроме как одновременно 1. Следовательно 3 решения.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 решение.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 решения.

Ответ: 7.

Ответ: 7

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

(X ∧ Y ∨ Z) → (Z ∨ P) = 0

где X, Y, Z, P – логические переменные? В ответе не нужно перечислять все различные наборы значений, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Пояснение.

(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Логическое ИЛИ ложно только в одном случае: когда оба выражения ложны.

Следовательно,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Следовательно, существует только одно решение уравнения.

Ответ: 1

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

(K ∨ L) ∧ (M ∨ N) = 1

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

Пояснение.

Логическое И истинно только в одном случае: когда все выражения истинны.

K ∨ L = 1, M ∨ N = 1.

Каждое из уравнений дает по 3 решения.

Рассмотрим уравнение А ∧ В = 1 если и А и В принимают истинные значения в трех случаях каждое, то в целом уравнение имеет 9 решений.

Следовательно ответ 9.

Ответ: 9

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

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

где A, B, C, D – логические переменные?

В ответе не нужно перечислять все различные наборы значений A, B, C, D, при которых выполнено данное равенство. В качестве ответа вам нужно указать количество таких наборов.

Пояснение.

Логическое "ИЛИ" истинно, когда истинно хотя бы одно из утверждений.

(D ∧ ¬D)= 0 при любых D.

Следовательно,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, что дает нам 3 варианта решений при каждом D.

(D ∧ ¬ D)= 0 при любых D, что дает нам два варианта решений (при D = 1, D = 0).

Следовательно: всего решений 2*3 = 6.

Итого 6 решений.

Ответ: 6

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

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

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

Пояснение.

Применим отрицание к обеим частям уравнения:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Логическое ИЛИ истинно в трех случаях.

Вариант 1.

K ∧ L ∧ M = 1, тогда K, L, M = 1, а ¬L ∧ M ∧ N = 0. N любое, то есть 2 решения.

Вариант 2.

¬L ∧ M ∧ N = 1, тогда N, M = 1; L = 0, K любое, то есть 2 решения.

Следовательно, ответ 4.

Ответ: 4

A, B и С — целые числа, для которых истинно высказывание

¬ (А = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(С > B)).

Чему равно В, если A = 45 и C = 43?

Пояснение.

1) ¬(А = B); (A > B)→(B > C); (B > A)→(С > B);

2) эти простые высказывания связаны операцией ∧ (И, конъюнкция), то есть, они должны выполняться одновременно;

3) из ¬(А = B)=1 сразу следует, что А B;

4) предположим, что A > B, тогда из второго условия получаем 1→(B > C)=1; это выражение может быть истинно тогда и только тогда, когда B > C = 1;

5) поэтому имеем A > B > C, этому условию соответствует только число 44;

6) на всякий случай проверим и вариант A 0 →(B > C)=1;

это выражение истинно при любом B; теперь смотрим третье условие получаем

это выражение может быть истинно тогда и только тогда, когда C > B, и тут мы получили противоречие, потому что нет такого числа B, для которого C > B > A.

Ответ: 44.

Ответ: 44

Составьте таблицу истинности для логической функции

X = (А ↔ B) ∨ ¬(A → (B ∨ C))

в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В — числа 77, столбец значений аргумента С — числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему(включая нулевой набор). Переведите полученную двоичную запись значений функции X в десятичную систему счисления.

Пояснение.

Запишем уравнение, используя более простые обозначения операций:

1) это выражение с тремя переменными, поэтому в таблице истинности будет строчек; следовательно, двоичная запись чисел, по которым строятся столбцы таблицы А, В и С, должна состоять из 8 цифр

2) переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел

3) вряд ли вы сможете сразу написать значения функции Х для каждой комбинации, поэтому удобно добавить в таблицу дополнительные столбцы для расчета промежуточных результатов (см. таблицу ниже)

X 0

А	В	С
0	0
0	1	1
0	0	1
1	0	1
1	1	1
0	1	0
1	0	0
1	1	0

4) заполняем столбцы таблицы:

А	В	С					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

значение равно 1 только в тех строчках, где А = В

значение равно 1 в тех строчках, где либо В либо С = 1

значение равно 0 только в тех строчках, где А = 1 и В + С = 0

значение — это инверсия предыдущего столбца (0 заменяется на 1, а 1 – на 0)

результат Х (последний столбец) — это логическая сумма двух столбцов и

5) чтобы получить ответ, выписываем биты из столбца Х сверху вниз:

6) переводим это число в десятичную систему:

Ответ: 171

Каково наибольшее целое число X, при котором истинно высказывание (10 (X+1)·(X+2))?

Пояснение.

Уравнение является операцией импликации между двумя отношениями:

1) Конечно, здесь можно применить тот же способ, что и в примере 2208, однако при этом понадобится решать квадратные уравнения (не хочется…);

2) Заметим, что по условию нас интересуют только целые числа, поэтому можно попытаться как─то преобразовать исходное выражение, получив равносильное высказывание (точные значения корней нас совершенно не интересуют!);

3) Рассмотрим неравенство : очевидно, что может быть как положительным, так и отрицательным числом;

4) Легко проверить, что в области высказывание истинно при всех целых , а в области — при всех целых (чтобы не запутаться, удобнее использовать нестрогие неравенства, и , вместо и );

5) Поэтому для целых можно заменить на равносильное выражение

6) область истинности выражения — объединение двух бесконечных интервалов;

7) Теперь рассмотрим второе неравенство : очевидно, что так же может быть как положительным, так и отрицательным числом;

8) В области высказывание истинно при всех целых , а в области — при всех целых , поэтому для целых можно заменить на равносильное выражение

9) область истинности выражения — закрытый интервал;

10) Заданное выражение истинно везде, кроме областей, где и ;

11) Обратите внимание, что значение уже не подходит, потому что там и , то есть импликация дает 0;

12) При подставлении 2, (10 (2+1) · (2+2)), или 0 → 0 что удовлетворяет условию.

Таким образом, ответ 2.

Ответ: 2

Каково наибольшее целое число X, при котором истинно высказывание

(50 (X+1)·(X+1))?

Пояснение.

Применим преобразование импликации и преобразуем выражение:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Логическое ИЛИ истинно когда истинно хотя бы одно логическое высказывание. Решив оба неравенства и учитывая, что видим, что наибольшее целое число, при котором выполняется хотя бы одно из них - 7 (на рисунке жёлтым изображено положительное решение второго неравенства, синим - первого).

Ответ: 7

Укажите значения переменных К, L, M, N, при которых логическое выражение

(¬(М ∨ L) ∧ К) → (¬К ∧ ¬М ∨ N)

ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.

Пояснение.

Дублирует задание 3584.

Ответ: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Пояснение.

Применим преобразование импликации:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Применим отрицание к обоим частям уравнения:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Преобразуем:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Следовательно, M = 0, N = 0, рассмотрим теперь (¬K ∧ L ∨ M ∧ L):

из того, что M = 0, N = 0 следует, что M ∧ L = 0, тогда ¬K ∧ L = 1, то есть K = 0, L = 1.

Ответ: 0100

Укажите значения переменных K, L, M, N, при которых логическое выражение

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Пояснение.

Запишем уравнение, используя более простые обозначения операций (условие «выражение ложно» означает, что оно равно логическому нулю):

1) из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных

2) из таблицы истинности операции «импликация» следует, что это выражение ложно тогда и только тогда, когда одновременно

3) первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда и ; отсюда следует (логическая сумма равна нулю), что может быть только при ; таким образом, три переменных мы уже определили

4) из второго условия, , при и получаем .

Дублирует задание

Ответ: 1000

Укажите значения логических переменных Р, Q, S, Т, при которых логическое выражение

(Р ∨ ¬Q) ∨ (Q → (S ∨ Т)) ложно.

Ответ запишите в виде строки из четырех символов: значений переменных Р, Q, S, T (в указанном порядке).

Пояснение.

(1) (Р ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (Р ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Применим преобразование импликации:

¬Q ∨ S ∨ Т = 0 => S = 0, T = 0.

Ответ: 0100

Укажите значения переменных K, L, M, N, при которых логическое выражение

(K → M) ∨ (L ∧ K) ∨ ¬N

ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Пояснение.

Логическое "ИЛИ" ложно тогда и только тогда, когда ложны оба утверждения.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Применим преобразование импликации для первого выражения:

¬K ∨ M = 0 => K = 1, M = 0.

Рассмотрим второе выражение:

(L ∧ K) ∨ ¬N = 0 (см. результат первого выражения) => L ∨ ¬N = 0 => L = 0, N = 1.

Ответ: 1001.

Ответ: 1001

Укажите значения переменных K, L, M, N, при которых логическое выражение

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

истинно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Пояснение.

Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.

1) (K → M) = 1 Применим преобразование импликации: ¬K ∨ M = 1

2) (K → ¬M) = 1 Применим преобразование импликации: ¬K ∨ ¬M = 1

Отсюда следует, что K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Применим преобразование импликации: K ∨ (M ∧ ¬L ∧ N) = 1 из того что K = 0 получаем:

M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.

Ответ: 0011

Известно, что для целых чисел X, Y и Z истинно высказывание

(Z Чему равно Z, если X=25 и Y=48?

Пояснение.

Выполнив подстановку чисел получаем что Z = 47.

Обратим внимание, что это сложное высказывание состоит из трех простых

1) (Z 2) эти простые высказывания связаны операцией ∧ (И, конъюнкция), то есть, они должны выполняться одновременно.

3) из ¬(Z+1 24, а из ¬(Z+1 47.

4) из (Z Z Ответ: 47.

Ответ: 47

A, B и C – целые числа, для которых истинно высказывание:

(C Чему равно C, если A=45 и B=18?

Пояснение.

Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.

Подставим значения чисел в выражение:

1) (C (C 2) ¬(C+1 , C ≥ 44.

3) ¬(C+1 , C ≥ 17.

Из 2) и 1) следует, что C

Ответ: 44

¬(А = B) ∧ ((B A)) ∧ ((A 2C))

Чему равно A, если C = 8 и B = 18?.

Пояснение.

Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.

1) ¬(А = B) = 1, то есть А ≠ 18 = 1.

2) ((B A)) Применим преобразование импликации: (18 > A) ∨ (16 > A) = 1

3) (A 2C) Применим преобразование импликации: (A > 18) ∨ (A > 16) = 1

Из 2) и 3) следует, что (18 > A) и (A > 16), так как в противном случае возникает противоречие А = 17.

Ответ: 17

A, B и С – целые числа, для которых истинно высказывание

¬(А = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))

Чему равно B, если A = 45 и C = 18?

Пояснение.

Логическое "И" истинно только тогда, когда истинны все высказывания.

Применение уравнений широко распространено в нашей жизни. Они используются во многих расчетах, строительстве сооружений и даже спорте. Уравнения человек использовал еще в древности и с тех пор их применение только возрастает. В математике существуют определенные задачи, которые посвящены логике высказываний. Чтобы решить данного рода уравнения необходимо обладать неким багажом знаний: знания законов логики высказываний, знания таблиц истинности логических функций 1 или 2 переменных, методы преобразования логических выражений. Кроме того, необходимо знать следующие свойства логических операций: конъюнкции, дизъюнкции, инверсии, импликации и эквивалентности.

Любую логическую функцию от \ переменных - \можно задать таблицей истинности.

Решим несколько логически уравнений:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Начнем решение с \[Х1\] и определим какие значения данная переменная может принимать: 0 и 1. Далее рассмотрим каждое их вышеприведенных значений и посмотрим, какое может быть при этом \[Х2.\]

Как видно из таблицы наше логическое уравнение имеет 11 решений.

Где можно решить логическое уравнение онлайн?

Решить уравнение вы можете на нашем сайте https://сайт. Бесплатный онлайн решатель позволит решить уравнение онлайн любой сложности за считанные секунды. Все, что вам необходимо сделать - это просто ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как решить уравнение на нашем сайте. А если у вас остались вопросы, то вы можете задать их в нашей групе Вконтакте http://vk.com/pocketteacher. Вступайте в нашу группу, мы всегда рады помочь вам.

Решение систем логических уравнений методом замены переменных

Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной.

Пример 1.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 → х2) → (х3→ х4) = 1

(х3 → х4) → (х5 → х6) = 1

(х5 → х6) → (х7 → х8) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, х2, х3, х4, х5, х6, х7, х8, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.

Тогда можно за­пи­сать си­сте­му в виде од­но­го урав­не­ния:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:

Т.е. условия выполняются для 5 наборов y1-y4.

Т.к. y1 = x1 → x2, то значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.

Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:

				Кол-во наборов на x1…x8

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

Ответ: 121

Пример 2.

Сколько существует различных наборов значений логических переменных x1, x2, ... x9, y1, y2, ... y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ... x9, y1, y2, ... y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение:

Сде­ла­ем за­ме­ну пе­ре­мен­ных:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Систему можно записать в виде одного уравнения:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 - два набора (xi,yi): (0,0) и (1,1).

Тогда первому набору z1, z2,…, z9 соответствует 2 9 наборов (x1,y1), (x2,y2),…, (x9,y9).

Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2 9 +2 9 = 1024 наборов.

Ответ: 1024

Решение систем логических уравнений методом визуального определения рекурсии.

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

Пример 3.

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

¬x9 ∨ x10 = 1,

где x1, x2, … x10 - ло­ги­че­ские пе­ре­мен­ные?

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

Решение:

Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:

Для x1=0 существуют два значения x2 (0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.

Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 (0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.

Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:

N i +1 = N i + 1. Тогда для десяти переменных получим 11 наборов.

Ответ: 11

Решение систем логических уравнений различного типа

Пример 4.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 , ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что три уравнения системы одинаковы на различных независимых наборах переменных.

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):

Аналогично, решениями второго и третьего уравнений будут абсолютно такие же наборы y1,…,y4 и z1,…, z4.

Теперь проанализируем четвертое уравнение системы: x 4 ∧ y 4 ∧ z 4 = 0. Решением будут все наборы x4, y4, z4, в которых хотя бы одна из переменных равна 0.

Т.е. для x4 = 0 подойдут все возможные наборы (y4, z4), а для x4 = 1 подойдут наборы (y4, z4), в которых присутствует хотя бы один ноль: (0, 0), (0,1) , (1,0).

				Кол-во наборов

Общее количество наборов 25 + 4*9 = 25 + 36 = 61.

Ответ: 61

Решение систем логических уравнений методом построения рекуррентных формул

Метод построения рекуррентных формул применяется при решении сложных систем, в которых порядок увеличения количества наборов неочевиден, а построение дерева невозможно из-за объемов.

Пример 5.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x1, x2, … x7, y1, y2, … y7, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x1, x2, ..., x7, y1, y2, ..., y7, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств. В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

Решение:

Заметим, что первые шесть уравнений системы одинаковы и отличаются только набором переменных. Рассмотрим первое уравнение. Его решением будут следующие наборы переменных:

Обозначим:

число наборов (0,0) на переменных (x1,y1) через A 1 ,

число наборов (0,1) на переменных (x1,y1) через B 1 ,

число наборов (1,0) на переменных (x1,y1) через C 1 ,

число наборов (1,1) на переменных (x1,y1) через D 1 .

число наборов (0,0) на переменных (x2,y2) через A 2 ,

число наборов (0,1) на переменных (x2,y2) через B 2 ,

число наборов (1,0) на переменных (x2,y2) через C 2 ,

число наборов (1,1) на переменных (x2,y2) через D 2 .

Из дерева решений видим, что

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

Заметим, что набор (0,0) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. A 2 =B 1 +C 1 +D 1 .

Набор (0,1) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. B 2 =B 1 +C 1 +D 1 .

Аналогично рассуждая, заметим, что С 2 =B 1 +C 1 +D 1 . D 2 = D 1 .

Таким образом, получаем рекуррентные формулы:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

Составим таблицу

Наборы	Обозн .	Формула	Количество наборов
			i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	A i	A i+1 =B i +C i +D i	0	3	7	15	31	63	127
(0,1)	B i	B i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

Последнему уравнению (x7 ∨ y7) = 1 удовлетворяют все наборы, кроме тех, в которых x7=0 и y7=0. В нашей таблице число таких наборов A 7 .

Тогда общее количество наборов равно B 7 + C 7 + D 7 = 127+127+1 = 255

Ответ: 255

Носкин Андрей Николаевич,
учитель информатики
высшей квалификационной категории,
кандидат военных наук, доцент
ГБОУ Лицей №1575 город Москва

Оптимизированный метод отображения для решения задачи 23 из КИМ ЕГЭ по информатике и ИКТ

Одной из самой трудной задачей в КИМ ЕГЭ является задача 23, в которой надо найти количество различных наборов значений логических переменных, которые удовлетворяют указанному условию.
Данная задача является едва ли не самым сложным заданием КИМ ЕГЭ по информатике и ИКТ. С ним, как правило, справляются не более 5% экзаменуемых {1}.
Такой маленький процент учеников, которые справились с данным заданием объясняется следующим:
- ученики могут путать (забыть) знаки логических операций;
- математические ошибки в процессе выполнения расчетов;
- ошибки в рассуждениях при поиске решения;
- ошибки в процессе упрощения логических выражений;
- учителя рекомендуют решать данную задачу, после выполнения всей работы, так как вероятность допущения
ошибок очень велика, а «вес» задачи составляет всего лишь один первичный балл.
Кроме того, некоторые учителя сами с трудом решают данный тип задач и поэтому стараются решать с детьми более простые задачи.
Также усложняет ситуацию, что в данном блоке существует большое количество разнообразных задач и невозможно подобрать какое-то шаблонное решение.
Для исправление данной ситуации педагогическим сообществом дорабатываются основные две методики решения задач данного типа: решение с помощью битовых цепочек {2} и метод отображений {3}.
Необходимость доработки (оптимизации) данных методик обусловлена тем, что задачи постоянно видоизменяются как по структуре, так и по количеству переменных (только один тип переменных Х, два типа переменных Х и Y, три типа: X, Y, Z).
Сложность освоения данными методиками решения задач подтверждается тем, что на сайте К.Ю. Полякова существует разборов данного типа задач в количестве 38 штук{4}. В некоторых разборах приведены более одного типа решения задачи.
Последнее время в КИМ ЕГЭ по информатике встречаются задачи с двумя типа переменных X и Y.
Я оптимизировал метод отображения и предлагаю своим ученикам пользоваться усовершенствованным методом.
Это дает результат. Процент моих учеников, которые справляются с данной задачей варьируется до 43% от сдающих. Как правило, ежегодно у меня сдает ЕГЭ по информатике от 25 до 33 человек из всех 11-х классов.
До появления задач с двумя типами переменными метод отображения ученики использовали очень успешно, но после появления в логическом выражении Y, я стал замечать, что у детей перестали совпадать ответы с тестами. Оказалось, они не совсем четко стали представлять, как составить таблицу отображений с новым типом переменной. Тогда мне пришла мысль, что для удобства надо все выражение привести к одному типу переменной, как удобно детям.
Приведу более подробно данную методику. Для удобства буду ее рассматривать на примере системы логических выражений, приведенных в {4}.
Сколько различных решений имеет система логических уравнений

(x 1 ^ y 1) = (¬x 2 V ¬ y 2 )
(x 2 ^ y 2) = (¬ x 3 V ¬ y 3 )
...
(x 5 ^ y 5 ) = (¬ x 6 V ¬ y 6 )

где x 1 , …, x 6 , y 1 , …, y 6 , - логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение:
1. Из анализа системы логических уравнений мы видим, что присутствует 6 переменных Х и 6 переменных У . Так как любая из этих переменных может принимать только два значения (0 и 1), то заменим эти переменные на 12 однотипных переменных, например Z.
2. Теперь перепишем систему с новыми однотипными переменными. Сложность задачи будет заключаться во внимательной записи при замене переменных.

(z 1 ^ z 2) = (¬z 3 V ¬ z 4 )
(z 3 ^ z 4) = (¬ z 5 V ¬ z 6 )
...
(z 9 ^ z 10 ) = (¬ z 11 V ¬ z 12)

3. Построим таблицу, в которой переберем все варианты z 1 , z 2 , z 3 , z 4 , поскольку в первом логическом уравнении четыре переменных, то таблица будет иметь 16 строк (16=2 4); уберем из таблицы такие значения z 4 , при которых первое уравнение не имеет решения (зачеркнутые цифры).

0	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1
1	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1

4. Анализируя таблицу, строим правило отображения пар переменных (например, паре Z 1 Z 2 =00 соответствует пара Z 3 Z 4 = 11) .

5. Заполняем таблицу, вычисляя количество пар переменных, при котором система имеет решение.

6. Складываем все результаты: 9 + 9 + 9 + 27 = 54
7. Ответ: 54.
Приведенная выше оптимизированная методика решения задачи 23 из КИМ ЕГЭ позволила ученикам вновь обрести уверенность и решать успешно этот тип задачи.

Литература:

1. ФИПИ. Методические рекомендации для учителей, подготовленные на основе анализа типичных ошибок участников ЕГЭ 2015 года по ИНФОРМАТИКЕ и ИКТ. Режим доступа: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

2. К.Ю. Поляков, М.А. Ройтберг. Системы логических уравнений: решение с помощью битовых цепочек. Журнал Информатика, № 12, 2014, с. 4-12. Издательский дом "Первое сентября", г.Москва.
3. Е.А. Мирончик, Метод отображения. Журнал Информатика, № 10, 2013, с. 18-26. Издательский дом "Первое сентября", г.Москва.

Можно выделить различные способы решения систем логических уравнений. Это сведение к одному уравнению, построение таблицы истинности и декомпозиция.

Задача: Решить систему логических уравнений:

Рассмотрим метод сведения к одному уравнению . Данный метод предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 1). Для этого применяют операцию логического отрицания. Затем, если в уравнениях есть сложные логические операции, заменяем их базовыми: «И», «ИЛИ», «НЕ». Следующим шагом объединяем уравнения в одно, равносильное системе, с помощью логической операции «И». После этого, следует сделать преобразования полученного уравнения на основе законов алгебры логики и получить конкретное решение системы.

Решение 1: Применяем инверсию к обеим частям первого уравнения:

Представим импликацию через базовые операции «ИЛИ», «НЕ»:

Поскольку левые части уравнений равны 1, можно объединить их с помощью операции “И” в одно уравнение, равносильное исходной системе:

Раскрываем первую скобку по закону де Моргана и преобразовываем полученный результат:

Полученное уравнение, имеет одно решение: A =0, B=0 и C=1.

Следующий способ – построение таблиц истинности . Поскольку логические величины имеют только два значения, можно просто перебрать все варианты и найти среди них те, при которых выполняется данная система уравнений. То есть, мы строим одну общую таблицу истинности для всех уравнений системы и находим строку с нужными значениями.

Решение 2: Составим таблицу истинности для системы:

0	0	1	1	0	1

Полужирным выделена строчка, для которой выполняются условия задачи. Таким образом, A=0, B=0 и C=1.

Способ декомпозиции . Идея состоит в том, чтобы зафиксировать значение одной из переменных (положить ее равной 0 или 1) и за счет этого упростить уравнения. Затем можно зафиксировать значение второй переменной и т.д.

Решение 3: Пусть A = 0, тогда:

Из первого уравнения получаем B =0, а из второго – С=1. Решение системы: A = 0, B = 0 и C = 1.

В ЕГЭ по информатике очень часто требуется определить количество решений системы логических уравнений, без нахождения самих решений, для этого тоже существуют определенные методы. Основной способ нахождения количества решений системы логических уравнений – замена переменных . Сначала необходимо максимально упростить каждое из уравнений на основе законов алгебры логики, а затем заменить сложные части уравнений новыми переменными и определить количество решений новой системы. Далее вернуться к замене и определить для нее количество решений.

Задача: Сколько решений имеет уравнение (A →B ) + (C →D ) = 1? Где A, B, C, D – логические переменные.

Решение: Введем новые переменные: X = A →B и Y = C →D . С учетом новых переменных уравнение запишется в виде: X + Y = 1.

Дизъюнкция верна в трех случаях: (0;1), (1;0) и (1;1), при этом X и Y является импликацией, то есть является истинной в трех случаях и ложной – в одном. Поэтому случай (0;1) будет соответствовать трем возможным сочетаниям параметров. Случай (1;1) – будет соответствовать девяти возможным сочетаниям параметров исходного уравнения. Значит, всего возможных решений данного уравнения 3+9=15.

Следующий способ определения количества решений системы логических уравнений – бинарное дерево . Рассмотрим данный метод на примере.

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

Приведенная система уравнений равносильна уравнению:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m ) = 1.

Предположим, что x 1 – истинно, тогда из первого уравнения получаем, что x 2 также истинно, из второго - x 3 =1, и так далее до x m = 1. Значит набор (1; 1; …; 1) из m единиц является решением системы. Пусть теперь x 1 =0, тогда из первого уравнения имеем x 2 =0 или x 2 =1.

Когда x 2 истинно получаем, что остальные переменные также истинны, то есть набор (0; 1; …; 1) является решением системы. При x 2 =0 получаем, что x 3 =0 или x 3 =, и так далее. Продолжая до последней переменной, получаем, что решениями уравнения являются следующие наборы переменных (m +1 решение, в каждом решении по m значений переменных):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Такой подход хорошо иллюстрируется с помощью построения бинарного дерева. Количество возможных решений – количество различных ветвей построенного дерева. Легко заметить, что оно равно m +1.

	Дерево	Количество решений
x 1
x 2
x 3
		…

В случае трудностей в рассужд ниях и построении де рева решений можно искать решение с использованием таблиц истинности , для одного – двух уравнений.

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

И составим таблицу истинности отдельно для одного уравнения:

x 1	x 2	(x 1 → x 2)

Составим таблицу истинности для двух уравнений:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) * (x 2 → x 3)