Э Алгебра логики Е Г Школа 58 Иванцова С.А., МОУ СОШ 58, г.Н.Новгород. - презентация

1 Э Алгебра логики Е Г Школа 58 Иванцова С.А., МОУ СОШ 58, г.Н.Новгород

2 В этой презентации приводятся тренировочные задания из нескольких источников: открытого сегмента федерального банка тестовых заданий, демонстрационных вариантов ЕГЭ прошлых лет, материалов К. Полякова (2009 г.), учебного пособия «ЕГЭ Информатика» (Крылов С.С., Лещинер В.Р., Якушкин П.А. - М.: Интеллект-Центр, 2007). Презентация содержит систематизированную информацию из различных источников, а также разработки автора в виде необходимых для исследования темы курса рекомендаций и решения ряда задач. Цель данной работы помочь вам «набить руку» в решении тестов ЕГЭ, разобраться с наиболее сложными заданиями и узнать объективный уровень своих знаний.

3 Что нужно прежде всего знать: 1. условные обозначения логических операций ¬А, не А, отрицание (инверсия) A B, A и B, A B логическое умножение (конъюнкция) A B, A или B, A + B логическое сложение (дизъюнкция) A B импликация (следование) А В, А В, А~В логическое равенство (эквивалентность) 2. таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквивалентность» А¬А АВА٨ВА٨В АВА۷ВА۷В АВАВ АВ

4 Что нужно прежде всего знать: 3. операцию «импликация» можно выразить через «ИЛИ» и «НЕ»: A B = ¬ A B или в других обозначениях A B = 4. операцию «эквиваленция» можно выразить через «ИЛИ» и «НЕ»: A B = ¬ A ¬ B A B или в других обозначениях A B = 5. приоритеты логических операций: 1. Скобки 2. Инверсия 3. Конъюнкция 4. Дизъюнкция 5. Импликация 6. Эквивалентность *теоретические выкладки частично предложены К.Ю. Поляковым

5 Законы алгебры логики

6 Пример 1: Для какого из указанных значений X истинно высказывание ¬((X > 2)(X > 3))? 1) 1 2) 2 3) 3 4) 4 *Решения примера 1 предложены К.Ю. Поляковым Решение (вариант 1, прямая подстановка): определим порядок действий: сначала вычисляются результаты отношений в скобках, затем выполняется импликация (поскольку есть «большие» скобки), затем – отрицание (операция «НЕ») для выражения в больших скобках выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 – ложное): XX > 2X > 2X > 3X > 3 (X > 2)(X > 3)¬((X > 2)(X >3)) таким образом, ответ – 3

7 Решение (вариант 2, упрощение выражения - позволяет получить общее решение – все множество X, для которых выражение истинно): 1. обозначим простые высказывания буквами: A = X > 2,B = X > 3 2. тогда можно записать все выражение в виде ¬(A B) или 3. выразим импликацию через «ИЛИ» и «НЕ»: ¬(A B) = ¬(¬A B) 4. раскрываем по формуле де Моргана операцию «НЕ» для всего выражения, получаем ¬(¬A B)= A ¬B 5. таким образом, данное выражение истинно только тогда, когда A истинно (X > 2), а B – ложно (X 3), то есть для всех X, таких что 2 < X 3 6. из приведенных чисел только 3 удовлетворяет этому условию, таким образом, ответ – 3. Пример 1: Для какого из указанных значений X истинно высказывание ¬((X > 2)(X > 3))? 1) 1 2) 2 3) 3 4) 4

8 Пример 2: Укажите, какое логическое выражение равносильно выражению A ¬(¬B C) 1) ¬A ¬B ¬C 2) A ¬B ¬C 3) A B ¬C4) A ¬B C *Решения примера 2 предложены К.Ю. Поляковым Способ 1 - с использованием законов де Моргана: перепишем заданное выражение и ответы в других обозначениях: заданное выражение и ответы: 1) 2) 3) 4) посмотрев на заданное выражение, видим инверсию (операцию «НЕ») для сложного выражения в скобках, которую раскрываем по формуле де Моргана, а затем используем закон двойного отрицания по которому : таким образом, правильный ответ – 3

9 Способ 2 - через таблицы истинности, если забыли формулы де Моргана): Перепишем заданное выражение и ответы в других обозначениях: заданное выражение и ответы: 1) 2) 3) 4) Для доказательства равносильности двух логических выражений достаточно показать, что они принимают равные значения при всех возможных комбинациях исходных данных; поэтому можно составить таблицы истинности для исходного выражения и всех ответов и сравнить их. Здесь 3 переменных, каждая из которых принимает два возможных значения 0 или 1 (всего 8 = 2 3 вариантов, которые в таблице истинности записывают по возрастанию двоичных кодов) Пример 2: Укажите, какое логическое выражение равносильно выражению A ¬(¬B C) 1) ¬A ¬B ¬C 2) A ¬B ¬C 3) A B ¬C4) A ¬B C

10 Исходное выражение истинно только тогда, когда и, то есть только при (в таблице истинности одна единица, остальные – нули). Выражение истинно, если хотя бы одна из переменных равна нулю, то есть, оно будет ложно только при (в таблице истинности один нуль, остальные – единицы) Аналогично выражение ложно только при, а в остальных случаях – истинно Выражение истинно только при, а в остальных случаях – ложно Объединяя все эти результаты в таблицу, получаем: Продолжение задачи: Укажите, какое логическое выражение равносильно выражению A ¬(¬B C) 1) ¬A ¬B ¬C 2) A ¬B ¬C 3) A B ¬C4) A ¬B C

11 ABC Видим, что таблицы истинности исходного выражения и 3 совпали во всех строчках, таким образом, правильный ответ – 3 Продолжение задачи: Укажите, какое логическое выражение равносильно выражению A ¬(¬B C) 1) ¬A ¬B ¬C 2) A ¬B ¬C 3) A B ¬C4) A ¬B C

12 Пример 3: Решение: воспользуемся тождествами: Используя эти тождества, получим высказывание в виде: где а = «Первая буква имени гласная» b = «Четвертая буква имени согласная», т.е. получим высказывание: или: Этому условию удовлетворяет только имя АНТОН. Ответ: 3 Для какого имени истинно высказывание: ¬(Первая буква имени гласная Четвёртая буква имени согласная) 1) ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР a b = (¬a) b (a b)= (¬a) (¬b) ¬(¬a)=a ¬(a b)= ¬(¬a b)=a (¬b) Первая буква имени гласная ¬ Четвёртая буква имени согласная Первая буква имени гласная Четвёртая буква имени гласная

13 Какое из приведенных имен удовлетворяет логическому условию (последняя буква согласная первая буква согласная) вторая буква согласная 1) ИРИНА 2) МАКСИМ 3) СТЕПАН 4) АРТЕМ Решение (метод логических рассуждений): Чтобы некое имя удовлетворяло логическому условию, необходимо, чтобы при выполнении операции логического умножения логическое выражение «вторая буква согласная» было истинно. Это условие уже исключает ответ 2). Чтобы первый множитель данной операции логического умножения был равен 1, надо, чтобы выражение под знаком отрицания: (последняя буква согласная первая буква согласная) было ложным, а это будет, если из истинной предпосылки «последняя буква согласная» не следует, что «первая буква согласная», (т.е. она гласная), а это соответствует только ответу 4) АРТЕМ Пример 4:

14 Пример 5: Решение: Воспользуемся тождествами: ( a b ) = ( a) ( b) ( b) = b Получим высказывание: ( A) ( B) = ( A) B Ответ: 4 Какое логическое выражение равносильно выражению ( A B)? 1) A B 2) A B 3) ( A) ( B) 4) ( A) B

15 Пример 6: Решение: Воспользуемся тождествами: ( a b ) = ( a) ( b) ( b) = b ( X Y)= ( X) ( Y)= X Y Получим высказывание: X Y Упростите выражение ( X Y)?

16 Пример 7: символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? 1) ¬X ¬Y ¬Z 2) X Y Z 3) X Y Z4) ¬X ¬Y ¬Z *Решения примера 7 предложены К.Ю. Поляковым Способ 1 - через таблицы истинности: XYZF нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данных 2. если для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F

17 4 перепишем ответы в других обозначениях: 1) 2) 3) 4) 1. первое выражение,, равно 1 только при, поэтому это неверный ответ (первая строка таблицы не подходит) 2. второе выражение,, равно 1 только при, поэтому это неверный ответ (первая и вторая строки таблицы не подходят) 3. третье выражение,, равно нулю при, поэтому это неверный ответ (вторая строка таблицы не подходит) 4.наконец, четвертое выражение, равно нулю только тогда, когда, а в остальных случаях равно 1, что совпадает с приведенной частью таблицы истинности 5. таким образом, правильный ответ – 4 ; частичная таблица истинности для всех выражений имеет следующий вид: XYZF × –– –––0 (красный крестик показывает, что значение функции не совпадает с F, а знак «–» означает, что вычислять оставшиеся значения не обязательно).

18 Замечание: метод применим не всегда, то есть, найденная в п. 4 функция может отсутствовать среди ответов Пример 7: символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? 1) ¬X ¬Y ¬Z 2) X Y Z 3) X Y Z4) ¬X ¬Y ¬Z Способ 2 – методом логических рассуждений: XYZF часто правильный ответ – это самая простая функция, удовлетворяющая частичной таблице истинности, то есть, имеющая единственный нуль или единственную единицу в полной таблице истинности 2. в этом случае можно найти такую функцию и проверить, есть ли она среди данных ответов 3. в приведенной задаче в столбце F есть единственный нуль для комбинации 4. выражение, которое имеет единственный нуль для этой комбинации, это, оно есть среди приведенных ответов (ответ 4) 5. таким образом, правильный ответ – 4

19 Пример 8: XYZF Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F? 1) ¬X ¬Y ¬Z 2) X Y Z 3) X ¬Y ¬Z4) X ¬Y ¬Z *Решения примера 8 предложены К.Ю. Поляковым Решение - методом логических рассуждений: перепишем ответы в других обозначениях: 1) 2) 3) 4) 1. в столбце F есть единственная единица для комбинации, простейшая функция, истинная (только) для этого случая, имеет вид, она есть среди приведенных ответов (ответ 3) 2. таким образом, правильный ответ – 3

20 Пример 9: Символом F обозначено одно из указанных ниже логических выражений из трёх аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? 1) ¬X ¬Y Z 2) ¬X ¬Y Z 3) X Y Z 4) X Y Z Решение: Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы: 1)¬X ¬Y Z =0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы; 2) ¬X ¬Y Z =1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы; 3) выражение X Y Z соответствует F, при всех предложенных комбинациях X,Y,Z; 4) X Y Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы. Ответ: 3

21 Пример 10: Каково наибольшее целое число X, при котором истинно высказывание (50 (X+1)·(X+1)) Решение (способ 1 – предложен К.Ю. Поляковым) – методом логических преобразований: 1. это операция импликации между двумя отношениями и 2. попробуем сначала решить неравенства Отсюда: A истинно, если X 50 Отсюда: B истинно, если X>-50-1 и X< обозначим эти области на оси X: на рисунке чёрные зоны обозначают область, где истинно выражение А, красная зона – это область, где истинно В

22 4. вспомним таблицу истинности операции «импликация»: Надо найти наибольшее Х, поэтому начинаем искать справа. На интервале X>50 видно, что А=1, В=0 (А В=0) На интервале 50-1<Х<50 видно, что А=0, В=0 (А В=1), т.е. этот вариант нам подходит. Т.о. 6,1 < Х< 7,1, т.е. Х=7 5. согласно таблице, заданное выражение истинно везде, кроме областей, где А=1 и В=0; область истинности выделена серым цветом 6. поэтому наибольшее целое число, удовлетворяющее условию – это первое целое число, меньшее, то есть, 7 7. таким образом, верный ответ – 7 ABA B

23 Решение (способ 2) – методом логических рассуждений: В данном выражении сопоставляются два алгебраических выражения: X 2 и (X+1) 2. Логическое выражение (50 (X+1)·(X+1))=1, если : 1) или одновременно логические выражения 50 (X+1) 2 =1. Это возможно, если 50 (X+1) 2 =1 для положительных значений X (отрицательные значения X не рассматриваем, т.к. по условию задачи требуется наибольшее целое число X). 2) или логическое выражение 50 (X+1) 2 =1 если: 50 (X+1) 2 =1 (кроме X=7). В этом случае наибольшее целое число X=6 3) или логическое выражение 50 (X+1) 2 =0 если: 50 (X+1) 2 =0 - при X 7 (отрицательные значения X не рассматриваем, т.к. по условию задачи требуется наибольшее целое число X). С учётом полученных выводов: |X|7 и X 7 получаем X=7. Таким образом, верный ответ – 7 Пример 10: Каково наибольшее целое число X, при котором истинно высказывание (50 (X+1)·(X+1))?

24 Пример 11: Сколько различных решений имеет уравнение ((K L) (L M N)) = 0 где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов. Решение - анализ исходного выражения (предложено К.Ю. Поляковым) : 1. перепишем уравнение, используя более простые обозначения операций: ((K + L) (L · M · N)) = 0 2. из таблицы истинности операции «импликация» следует, что это равенство верно тогда и только тогда, когда одновременно K + L = 1 и L · M · N = 0 3. из первого уравнения следует, что хотя бы одна из переменных, K или L равна 1 (или обе вместе); поэтому рассмотрим три случая 4. если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения 5. если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения 6. если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения 7. таким образом, всего получаем = 10 решений.

25 Сколько различных решений имеет уравнение J ¬K L ¬M (N ¬N) = 0, где J, K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов. Пример 12: Решение - анализ исходного выражения «от противного»: Исходное логическое выражение – это логическое произведение, которое включает в себя много переменных. Можно предположить, что оно равно 0 для многих переменных, и, наоборот, равно 1 в небольшом числе случаев, поэтому попытаемся найти количество решений «обратного» уравнения: J ¬K L ¬M (N ¬N) = 1 Для этого уравнения сразу определяются два решения: J=1, K=0, L=1, M=0, N=0, J=1, K=0, L=1, M=0, N=1 Поскольку для исходного уравнения возможно 2 5 = 32 решений (при пяти логических переменных), то исключая из них 2 вышеупомянутые, получаем ответ: 32-2=30

26 Пример 13: Укажите значения переменных К, L, M, N, при которых логическое выражение (¬(М L) К) (¬К ¬М) N) ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1. Способ 1(предложен К.Ю. Поляковым) – методом логических рассуждений: 1. запишем уравнение, используя более простые обозначения операций: 2. из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных 3. из таблицы истинности операции «импликация» следует, что это выражение ложно тогда и только тогда, когда одновременно и 4. первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда и ; отсюда следует (логическая сумма равна нулю), что может быть только при ; таким образом, три переменных мы уже определили 5. из второго условия,, при и получаем 6. таким образом, правильный ответ – 1000

27 Замечание: этот способ работает всегда и дает более общее решение; в частности, можно легко обнаружить, что уравнение имеет несколько решений (тогда оно не сведется к форме «сумма = 0» или «произведение = 1») Пример 13: Способ 2 (предложен К.Ю. Поляковым) - упрощение выражения: 1. запишем уравнение, используя более простые обозначения операций: 2. заменим импликацию по формуле : 3. раскроем инверсию по формуле де Моргана 4. упростим выражение : 5. мы получили уравнение вида «M+L+N = 0», в нем все слагаемые должны быть равны нулю 6. поэтому сразу находим 7. таким образом, правильный ответ – 1000 Укажите значения переменных К, L, M, N, при которых логическое выражение (¬(М L) К) (¬К ¬М) N) ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.

28 Пример 13: Укажите значения переменных К, L, M, N, при которых логическое выражение (¬(М L) К) (¬К ¬М) N) ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Способ 3 – построение таблицы истинности ( если по-другому не получается ): таким образом, правильный ответ – 1000 КLMN М L¬(М L)¬(М L) К ¬К¬М ¬К ¬М¬К ¬М) N

29 Сколько различных решений имеет уравнение (K/\L/\M)\/(¬L/\¬M/\N) = 1 где K, L, M, N - логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов. Решение (способ 1 – построение таблицы истинности): Ответ - 4 Пример 14: KLMN ¬L¬L ¬M¬M K/\L/\M ¬ L/\ ¬ M/\N(K/\L/\M)\/( ¬ L/\ ¬ M/\N)

30 Сколько различных решений имеет уравнение (K/\L/\M)\/(¬L/\¬M/\N) = 1 где K, L, M, N - логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов. Решение (способ 2 – методом логических рассуждений): Значение логического выражения (K/\L/\M)\/(¬L/\¬M/\N) истинно, если: 1)Первая скобка имеет значение 1. А это возможно лишь если K, L, M все равны 1, а значение N может быть любым, т.е. 0 или 1. Т.о. предполагаются 2 набора значений переменных, удовлетворяющих исходному уравнению: K=1, L=1, M=1, N=1 и K=1, L=1, M=1, N=0. 2)Вторая скобка имеет значение 1. А это возможно лишь если L=0, M=0, N=1, а значение K может быть любым, т.е. 0 или 1. Т.о. предполагаются ещё 2 набора значений переменных, удовлетворяющих исходному уравнению: L=0, M=0, N=1, K=1 и L=0, M=0, N=1, K=0. 2+2=4 различных решений Ответ - 4 Пример 14:

31 Решение: Этот способ решения подходит для конкретной задачи. Он основан на том, что импликация x->y ложна тогда и только тогда, когда x-истинно, y-ложно. X= K M, Y= L M N Отсюда по свойству дизъюнкции: x истинно при (K,M)=(0,0),(0,1),(1,1); y ложно лишь при (L,M,N)=(1,0,0)=> M=0=> K=0 Ответ: 0100 Пример 15: Укажите значения переменных К, L, M, N, при которых логическое выражение (¬K M) (¬L М N) ложно. Ответ запишите в виде строки из четырёх символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1

32 Решение (способ 1) – методом логических преобразований: Подставим значение Х и У: Воспользуемся распределительным законом Высказывание тождественно ложно, поэтому Существует единственное целое число меньше 20 и, при этом большее или равное 19. Это 19. Ответ: 19 Пример 16: X, Y, Z – целые числа, для которых истинно высказывание: ((Z

33 Решение (способ 2) – методом логических рассуждений: Подставляем в истинное высказывание исходные значения X и Y: ((Z<20) (Z<10)) ¬((Z+1)<20) ¬((Z+1)<10) = 1 Все три множителя в этом случае одновременно должны быть равны 1: ((Z<20) (Z<10)) =1 и ¬((Z+1)<20) =1 и ¬((Z+1)<10) = 1, тогда: ((Z+1)<20)=0 ((Z+1)<10) =0, тогда: Z<19=0 Z<9=0, тогда: Z 19=1 Z 9=1 Чтобы выражение ((Z<20) (Z<10)) =1, достаточно, чтобы Z<20 или Z<10. С учётом предыдущих выводов (Z 19=1 и Z 9=1) это возможно в двух случаях: при Z=19 или Z=9. Но при Z=9 не будет исполняться условие Z19=1, тогда ответ: Z=19 Пример 16: X, Y, Z – целые числа, для которых истинно высказывание: ((Z

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

35 Составьте таблицу истинности для логической функции X = (А B) ¬(A (B C)) в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В – числа 77, столбец значений аргумента С – числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функции X в десятичную систему счисления. *Решения примера 18 предложены К.Ю. Поляковым Пример 18: Решение (вариант 1): Запишем уравнение, используя более простые обозначения операций: Это выражение с тремя переменными, поэтому в таблице истинности будет 2 3 =8 строчек. Переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел: 27 = = = АВСX В таблице истинности строки переставлены в сравнении с традиционным порядком (А=27 10, В=77 10, С= ). Получаем Х = = =

36 Решение (вариант 2, преобразование логической функции): 1. запишем уравнение, используя более простые обозначения операций: 2. раскроем импликацию через операции И, ИЛИ и НЕ ( ): 3. раскроем инверсию для выражения по формуле де Моргана: 4. таким образом, выражение приобретает вид отсюда сразу видно, что Х = 1 только тогда, когда А = В или (А = 1 и В = С = 0): Х = = = Пример 18: Составьте таблицу истинности для логической функции X = (А B) ¬(A (B C)) в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В – числа 77, столбец значений аргумента С – числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функции X в десятичную систему счисления. АВСX Примечание 000 1А = В А = 1, В = С = А = В

37 Сколько различных решений имеет логическое уравнение (¬X 1 X 2 ) (¬X 2 X 3 ) (¬X 3 X 4 ) (¬X 4 X 5 ) (¬X 5 X 6 ) = 1 где x 1, x 2, …, x 6 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 19: Решение: Перепишем уравнение, заменив знаки логических операций: Учитывая, что, заменяем все выражения в скобках на импликацию: Решение уравнения можно записать в виде шести двоичных знаков, которые обозначают соответственно, переменные Далее вспомним, что импликация дает ложное значение, если её первая часть (посылка) истинна, а вторая (следствие) ложно, поэтому из сразу следует, что Это значит, что в исходном выражении появится нуль, если в цепочке битов, соответствующей значениям переменных, появится комбинация 10, то есть предыдущее значение истинно, а следующее за ним – ложно. Поэтому решениями этого уравнения будут все комбинации значений переменных, для которых в соответствующей битовой цепочке нет последовательности 10; таких цепочек всего 7: , , , , , , Таким образом, ответ: 7 решений.

38 Сколько различных решений имеет система уравнений ¬X 1 X 2 = 1 ¬X 2 X 3 = 1... ¬X 9 X 10 = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 20: Решение (последовательное решение, через нули): Рассмотрим первое уравнение ; согласно таблице истинности операции «ИЛИ» оно НЕ выполняется только в одном случае (точнее, с учетом других переменных, для одной группы комбинаций): (1,0,*) здесь звездочка означает, что остальные 8 переменных могут быть любыми Общее количество комбинаций X 1 и X 2 ­­ равно 2 2 = 4, поэтому число решений первого уравнения равно 4 – 1 = 3 Второе уравнение, рассматриваемое отдельно, тоже ложно только для одной комбинации имеет 3 группы решений: (x 1,1,0,*), где x 1, – некоторое логическое значение переменной X 1

39 Сколько различных решений имеет система уравнений ¬X 1 X 2 = 1 ¬X 2 X 3 = 1... ¬X 9 X 10 = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 20: Решение (продолжение): Теперь рассмотрим вместе первое и второе уравнения и определим, в скольких случаях хотя бы одно из них неверно Множества (1,0,x 3,*) и (x 1,1,0,*) не пересекаются, потому что в первом X 2 = 0, а во втором X 2 = 1, поэтому система из двух уравнений не выполнена для 4-х комбинаций: (1,0,0,*), (1,0,1,*), (0,1,0,*) и (1,1,0,*) Общее количество комбинаций трех логический переменных равно 2 3 = 8, поэтому количество решений системы из двух уравнений равно 8 – 4 = 4 Аналогично доказывается, что система из 3 уравнений имеет 5 решений, и т.д., то есть, система из 9 уравнений с 10 переменными имеет 11 решений Таким образом, ответ: 11 решений.

40 Сколько различных решений имеет система уравнений ¬X 1 X 2 = 1 ¬X 2 X 3 = 1... ¬X 9 X 10 = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 20: Решение (табличный метод): Рассмотрим все решения первого уравнения по таблице истинности: Строчка, выделенная красным фоном, не удовлетворяет условию, поэтому дальше ее рассматривать не будем. Теперь подключаем третью переменную и второе уравнение:

41 Сколько различных решений имеет система уравнений ¬X 1 X 2 = 1 ¬X 2 X 3 = 1... ¬X 9 X 10 = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 20: Решение (продолжение): При каких значениях переменной X 3 будет верно условие ? Очевидно, что на это уже не влияет X 1 (этот столбец выделен зеленым цветом). Если X 2 = 1, то сразу получаем, что X 3 = 1 (иначе ): Как видно из таблицы, верхняя строчка предыдущей таблицы (где были все нули) дает два решения при подключении очередного уравнения, а все остальные – по одному Понятно, что такая же ситуация будет продолжаться и дальше, то есть, при добавлении каждой новой переменной число решений увеличивается на 1 Рассуждая таким образом и дальше, получаем, что для 3-х уравнений с 4-мя переменными будет 5 решений, для 4 уравнений – 6 решений, …, а для 9 уравнений – 11 решений Обратите внимание на форму таблицы – единицы и нули образуют два треугольника. Таким образом, ответ: 11 решений

42 Сколько различных решений имеет система уравнений ¬(X 1 X 2 ) (X 3 X 4 ) = 1 ¬(X 3 X 4 ) (X 5 X 6 ) = 1 ¬(X 5 X 6 ) (X 7 X 8 ) = 1 ¬(X 7 X 8 ) (X 9 X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 21: Решение : Количество комбинаций 10 логических переменных равно 2 10 = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу Заметим, что при обозначениях: Мы получаем систему из 4 уравнений и 5 независимыми переменными; эта система уравнений относится к типу, который рассмотрен в предыдущей разобранной задаче: ¬Y 1 Y 2 = 1 ¬Y 2 Y 3 = 1 ¬Y 3 Y 4 = 1 ¬Y 4 Y 5 = 1

43 Сколько различных решений имеет система уравнений ¬(X 1 X 2 ) (X 3 X 4 ) = 1 ¬(X 3 X 4 ) (X 5 X 6 ) = 1 ¬(X 5 X 6 ) (X 7 X 8 ) = 1 ¬(X 7 X 8 ) (X 9 X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 21: Решение (продолжение): Как следует из разбора предыдущей задачи, такая система имеет 5+1 = 6 решений для переменных Y 1 … Y 5 Теперь нужно получить количество решений в исходных переменных, X 1 … X 10 ; для этого заметим, что переменные Y 1 … Y 5 независимы; Предположим, что значение Y 1 известно (0 или 1); поскольку, по таблице истинности операции «эквивалентность» (истина, когда два значения одинаковы), есть две соответствующих пары (X 1 ;X 2 ) (как для случая Y 1 = 0, так и для случая Y 1 = 1) У нас есть 5 переменных Y 1 … Y 5, каждая их комбинация дает 2 пары (X 1 ;X 2 ), 2 пары (X 3 ;X 4 ), 2 пары (X 5 ;X 6 ), 2 пары (X 7 ;X 8 ) и 2 пары (X 9 ;X 10 ), то есть всего 2 5 = 32 комбинации исходных переменных Таким образом, общее количество решений равно 6 ·32 = 192 Почему 6? Надо исключить те пары X 1… X 10, при которых, например, ложно: ¬Y 1 Y 2 = 1 и т.д. Ответ: 192 решения

44 Сколько различных решений имеет система уравнений (X 1 X 2 ) (¬X 1 ¬X 2 ) (¬X 3 X 4 ) (X 3 ¬X 4 ) = 1 (X 3 X 4 ) (¬X 3 ¬X 4 ) (¬X 5 X 6 ) (X 5 ¬X 6 ) = 1 (X 5 X 6 ) (¬X 5 ¬X 6 ) (¬X 7 X 8 ) (X 7 ¬X 8 ) = 1 (X 7 X 8 ) (¬X 7 ¬X 8 ) (¬X 9 X 10 ) (X 9 ¬X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 22: Решение : Количество комбинаций 10 логических переменных равно 2 10 = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу. Решать такую систему «в лоб» достаточно сложно, нужно попробовать ее упростить. Заметим, что (X 1 X 2 ) (¬X 1 ¬X 2 ) = (X 1 X 2 ), где символ означает операцию «эквивалентность» (значения равны); Кроме того, (¬X 3 X 4 ) (X 3 ¬X 4 ) = (X 3 X 4 ) = ¬(X 3 X 4 ), где символ означает операцию «исключающее ИЛИ» (значения НЕ равны); это операция, обратная эквивалентности. Используем замену переменных, выделив члены, объединя- ющие пары исходных переменных (X 1 и X 2, X 3 и X 4, X 5 и X 6, X 7 и X 8, X 9 и X 10 ) Y 1 = ¬(X 1 X 2 )Y 2 = ¬(X 3 X 4 )Y 3 = ¬(X 5 X 6 ) Y 4 = ¬(X 7 X 8 ) Y 5 = ¬(X 9 X 10 )

45 Сколько различных решений имеет система уравнений (X 1 X 2 ) (¬X 1 ¬X 2 ) (¬X 3 X 4 ) (X 3 ¬X 4 ) = 1 (X 3 X 4 ) (¬X 3 ¬X 4 ) (¬X 5 X 6 ) (X 5 ¬X 6 ) = 1 (X 5 X 6 ) (¬X 5 ¬X 6 ) (¬X 7 X 8 ) (X 7 ¬X 8 ) = 1 (X 7 X 8 ) (¬X 7 ¬X 8 ) (¬X 9 X 10 ) (X 9 ¬X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 22: Решение (продолжение): При этих обозначения система уравнений преобразуется к виду ¬Y 1 Y 2 = 1 ¬Y 2 Y 3 = 1 ¬Y 3 Y 4 = 1 ¬Y 4 Y 5 = 1 Как показано выше (при разборе предыдущей задачи), такая система имеет 5+1 = 6 решений для независимых переменных Y 1 … Y 5 Предположим, что значение Y 1 известно (0 или 1); поскольку, по таблице истинности операции «эквивалентность» есть две соответствующих пары (X 1 ;X 2 ) (как для случая Y 1 = 0, так и для случая Y 1 = 1) У нас есть 5 переменных Y 1 … Y 5, каждая их комбинация дает 2 пары (X 1 ;X 2 ), 2 пары (X 3 ;X 4 ), 2 пары (X 5 ;X 6 ), 2 пары (X 7 ;X 8 ) и 2 пары (X 9 ;X 10 ), то есть всего 2 5 = 32 комбинации исходных переменных Т. о., общее количество решений равно 6 ·32 = 192 Ответ: 192 решения

46 Сколько различных решений имеет система уравнений ((X 1 X 2 ) (X 3 X 4 )) (¬(X 1 X 2 ) ¬(X 3 X 4 )) = 1 ((X 3 X 4 ) (X 5 X 6 )) (¬(X 3 X 4 ) ¬(X 5 X 6 )) = 1 ((X 5 X 6 ) (X 7 X 8 )) (¬(X 5 X 6 ) ¬(X 7 X 8 )) = 1 ((X 7 X 8 ) (X 9 X 10 )) (¬(X 7 X 8 ) ¬(X 9 X 10 )) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 23: Решение (табличный метод): Рассмотрим первое уравнение, заменив обозначения логических операций на более простые:, где. Выражение в левой части последнего равенства – это операция эквивалентности между Y 1 и Y 2, то есть первое уравнение запишется в виде С помощью замены переменных сведем систему к виду: (Y 1 Y 2 ) = 1 (Y 2 Y 3 ) = 1 (Y 3 Y 4 ) = 1 (Y 4 Y 5 ) = 1 Рассмотрим все решения первого уравнения по таблице истинности: Строчки, выделенные красным фоном, не удовлетворяют условию, поэтому дальше их рассматривать не будем.

47 Сколько различных решений имеет система уравнений ((X 1 X 2 ) (X 3 X 4 )) (¬(X 1 X 2 ) ¬(X 3 X 4 )) = 1 ((X 3 X 4 ) (X 5 X 6 )) (¬(X 3 X 4 ) ¬(X 5 X 6 )) = 1 ((X 5 X 6 ) (X 7 X 8 )) (¬(X 5 X 6 ) ¬(X 7 X 8 )) = 1 ((X 7 X 8 ) (X 9 X 10 )) (¬(X 7 X 8 ) ¬(X 9 X 10 )) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 23: Решение (продолжение): Теперь подключаем третью переменную и второе уравнение: При каких значениях переменной X 3 будет верно условие ? Очевидно, что на это уже не влияет Y 1 (этот столбец выделен зеленым цветом). Cразу получаем два решения: Как видно из таблицы, каждая строчка предыдущей таблицы дает одно решение при подключении очередного уравнения, поэтому для любого количества переменных система имеет 2 решения – все нули и все единицы. Так же, как и в предыдущем способе, переходим к исходным переменным и находим общее количество решений: 2 ·32 = 64 Ответ: 64 решения

48 Сколько различных решений имеет система уравнений (X 2 X 1 ) (X 2 X 3 ) (¬X 2 ¬ X 3 )= 1 (X 3 X 1 ) (X 3 X 4 ) (¬X 3 ¬ X 4 )= 1... (X 9 X 1 ) (X 9 X 10 ) (¬X 9 ¬ X 10 )= 1 (X 10 X 1 ) = 0 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 24: Решение (табличный метод): Количество комбинаций 10 логических переменных равно 2 10 = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу перепишем уравнения, используя более простые обозначения операций:

49 Сколько различных решений имеет система уравнений (X 2 X 1 ) (X 2 X 3 ) (¬X 2 ¬ X 3 )= 1 (X 3 X 1 ) (X 3 X 4 ) (¬X 3 ¬ X 4 )= 1... (X 9 X 1 ) (X 9 X 10 ) (¬X 9 ¬ X 10 )= 1 (X 10 X 1 ) = 0 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 24: Решение (продолжение): Заметим, что по свойству операции эквивалентности, поэтому уравнения можно переписать в виде: Первое уравнение выполняется, когда есть X 2 равно X 1 или X 3

50 Сколько различных решений имеет система уравнений (X 2 X 1 ) (X 2 X 3 ) (¬X 2 ¬ X 3 )= 1 (X 3 X 1 ) (X 3 X 4 ) (¬X 3 ¬ X 4 )= 1... (X 9 X 1 ) (X 9 X 10 ) (¬X 9 ¬ X 10 )= 1 (X 10 X 1 ) = 0 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 24: Решение (продолжение): По таблице истинности находим 6 вариантов (для удобства мы будем записывать сначала столбец для X 1, а потом для всех остальных в обратном порядке): Обратите внимание, что в каждой строчке в первых двух столбцах должно быть по крайней мере одно значение, равное значению в третьем столбце (который выделен желтым)

51 Сколько различных решений имеет система уравнений (X 2 X 1 ) (X 2 X 3 ) (¬X 2 ¬ X 3 )= 1 (X 3 X 1 ) (X 3 X 4 ) (¬X 3 ¬ X 4 )= 1... (X 9 X 1 ) (X 9 X 10 ) (¬X 9 ¬ X 10 )= 1 (X 10 X 1 ) = 0 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 24: Решение (продолжение): Добавим еще одно уравнение и еще одну переменную X 4 :

52 Сколько различных решений имеет система уравнений (X 2 X 1 ) (X 2 X 3 ) (¬X 2 ¬ X 3 )= 1 (X 3 X 1 ) (X 3 X 4 ) (¬X 3 ¬ X 4 )= 1... (X 9 X 1 ) (X 9 X 10 ) (¬X 9 ¬ X 10 )= 1 (X 10 X 1 ) = 0 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 24: Решение (продолжение): Чтобы «подключить» второе уравнение, нужно использовать то же самое правило: каждой строчке в первых двух столбцах должно быть, по крайней мере, одно значение, равное значению в третьем столбце (который выделен желтым); это значит, что в первой и последней строчках (где X 1 = X 3 ) значение X 4 может быть любое (0 или 1), а в остальных строчках – только строго определенное:

53 Сколько различных решений имеет система уравнений (X 2 X 1 ) (X 2 X 3 ) (¬X 2 ¬ X 3 )= 1 (X 3 X 1 ) (X 3 X 4 ) (¬X 3 ¬ X 4 )= 1... (X 9 X 1 ) (X 9 X 10 ) (¬X 9 ¬ X 10 )= 1 (X 10 X 1 ) = 0 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 24: Решение (продолжение): Таким образом, количество решений при подключении очередного уравнения к системе возрастает на 2! Подключили X 5 – получили 10 решений, X 6 – получили 12 решений, X 7 – получили 14 решений, X 8 – получили 16 решений, X 9 – получили 18 решений, X 10 – получили 20 решений. Остается одно последнее уравнение (X 10 X 1 ) = 0, из которого следует, что X 10 не равен X 1 Из таблицы следует, что только в первой и последней строчках значения первой и последней переменных совпадают, то есть из полученных 20 решений нужно отбросить 2 Таким образом, получается 20 – 2 = 18 решений Ответ: 18 решений

54 Сколько различных решений имеет система уравнений (X 1 X 2 ) (¬X 1 ¬X 2 ) (X 1 X 3 ) = 1 (X 2 X 3 ) (¬X 2 ¬X 3 ) (X 2 X 4 ) = 1... (X 8 X 9 ) (¬X 8 ¬X 9 ) (X 8 X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 25: Решение (табличный метод): Количество комбинаций 10 логических переменных равно 2 10 = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу перепишем уравнения, используя более простые обозначения операций:

55 Сколько различных решений имеет система уравнений (X 1 X 2 ) (¬X 1 ¬X 2 ) (X 1 X 3 ) = 1 (X 2 X 3 ) (¬X 2 ¬X 3 ) (X 2 X 4 ) = 1... (X 8 X 9 ) (¬X 8 ¬X 9 ) (X 8 X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 25: Решение (продолжение): Заметим, что по свойству операции эквивалентности, поэтому уравнения можно переписать в виде: Сделать замену переменных так, чтобы новые переменные был независимы друг от друга, здесь довольно затруднительно, поэтому будем решать уравнения последовательно табличным методом.

56 Сколько различных решений имеет система уравнений (X 1 X 2 ) (¬X 1 ¬X 2 ) (X 1 X 3 ) = 1 (X 2 X 3 ) (¬X 2 ¬X 3 ) (X 2 X 4 ) = 1... (X 8 X 9 ) (¬X 8 ¬X 9 ) (X 8 X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 25: Решение (продолжение): Рассмотрим все возможные комбинации первых двух переменных ­X 1 и X 2, и сразу попытаемся для каждой из них подобрать значения третьей так, чтобы выполнялось первое уравнение :

57 Сколько различных решений имеет система уравнений (X 1 X 2 ) (¬X 1 ¬X 2 ) (X 1 X 3 ) = 1 (X 2 X 3 ) (¬X 2 ¬X 3 ) (X 2 X 4 ) = 1... (X 8 X 9 ) (¬X 8 ¬X 9 ) (X 8 X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 25: Решение (продолжение): Очевидно, что в первой и последней строчках таблицы, где, значения X 3 могут быть любыми, то есть каждая из этих строчек дает два решения; в то же время во второй и третьей строках, где, мы сразу получаем, что для выполнения первого равнения необходимо, то есть, эти две строчки дают по одному решению:

58 Сколько различных решений имеет система уравнений (X 1 X 2 ) (¬X 1 ¬X 2 ) (X 1 X 3 ) = 1 (X 2 X 3 ) (¬X 2 ¬X 3 ) (X 2 X 4 ) = 1... (X 8 X 9 ) (¬X 8 ¬X 9 ) (X 8 X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 25: Решение (продолжение): Заметим, что количество решений для каждой строчки исходной таблицы (с двумя переменными) определялось лишь тем, равны значения в двух последних столбцах (X 2 и X 1 ) или не равны; Также заметим, что в новой таблице в самой верхней и самой нижней строках значения X 3 и X 2 равны, а в остальных не равны (их 4 штуки); поэтому на следующем шаге (при подключении четвертой переменной и третьего уравнения) верхняя и нижняя строки дадут 2 варианта с равными X­ 4 и X 3, и = 6 вариантов, где X­ 4 и X 3 не равны В общем виде: если на шаге i в таблице решений есть n i строк, где значения в двух самых левых столбцах таблицы равны, и … m i строк, где значения в двух самых левых столбцах таблицы не равны, то на следующем шаге будет столько же (n i ) строк с равными значения в двух самых последних столбцах и n i +m i строк с неравными значениями

59 Сколько различных решений имеет система уравнений (X 1 X 2 ) (¬X 1 ¬X 2 ) (X 1 X 3 ) = 1 (X 2 X 3 ) (¬X 2 ¬X 3 ) (X 2 X 4 ) = 1... (X 8 X 9 ) (¬X 8 ¬X 9 ) (X 8 X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Пример 25: Решение (продолжение): Эту последовательность можно записать в виде таблицы (i – число задействованных переменных): Таким образом, для системы с 10 переменными общее количество решений равно = 20 Ответ: 20 решений

60 Спасибо за внимание!