Тема урока: Решение логических уравнений
Образовательная – изучение способов решения логических уравнений, формирование умений и навыков решения логических уравнений и построения логического выражения по таблице истинности;Развивающая - создать условия для развития познавательного интереса учащихся, способствовать развитию памяти, внимания, логического мышления;
Воспитательная : способствовать воспитанию умения выслушивать мнение других, воспитание воли и настойчивости для достижения конечных результатов.
Тип урока: комбинированный урок
Оборудование: компьютер, мультимедийный проектор, презентация 6.
Ход урока
Повторение и актуализацию опорных знаний. Проверка домашнего задания (10 минут)
На предыдущих уроках мы познакомились с основными законами алгебры логики, научились использовать эти законы для упрощения логических выражений.
Выполним проверку домашнего задания по упрощению логических выражений:
1. Какое из приведенных слов удовлетворяет логическому условию:
(первая буква согласная→вторая буква согласная) ٨ (последняя буква гласная → предпоследняя буква гласная)? Если таких слов несколько, укажите наименьшее из них.
1) АННА 2) МАРИЯ 3) ОЛЕГ 4) СТЕПАН
Введем обозначения:
А – первая буква согласная
В – вторая буква согласная
С – последняя буква гласная
D – предпоследняя буква гласная
Составим выражение:
Составим таблицу:
2. Укажите, какое логическое выражение равносильно выражению
Упростим запись исходного выражения и предложенных вариантов:
3. Дан фрагмент таблицы истинности выражения F:
Какое выражение соответствует F?
Определим значения этих выражений при указанных значениях аргументов:
Ознакомление с темой урока, изложение нового материала (30 минут)
Мы продолжаем изучать основы логики и тема нашего сегодняшнего урока «Решение логических уравнений». Изучив данную тему, вы узнаете основные способы решения логических уравнений, получите навыки решения этих уравнений путем использования языка алгебры логики и умения составления логического выражения по таблице истинности.
1. Решить логическое уравнение
(¬K M) → (¬L M N) =0
Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.
Решение:
Преобразуем выражение (¬K M) → (¬L M N)
Выражение ложно, когда оба слагаемые ложны. Второе слагаемое равно 0, если M
=0, N
=0, L
=1. В первом слагаемом K
=0, так как М=0, а 
.
Ответ: 0100
2. Сколько решений имеет уравнение (в ответе укажите только число)?
Решение: преобразуем выражение
(A +B )*(C +D )=1
A +B =1 и C +D =1
2 способ: составление таблицы истинности
3 способ : построение СДНФ – совершенной дизъюнктивной нормальной формы для функции – дизъюнкции полных правильных элементарных конъюнкций.Преобразуем исходное выражение, раскроем скобки для того, чтобы получить дизъюнкцию конъюнкций:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Дополним конъюнкции до полных конъюнкций (произведение всех аргументов), раскроем скобки:
Учтем одинаковые конъюнкции:
В итоге получаем СДНФ, содержащую 9 конъюнкций. Следовательно, таблица истинности для данной функции имеет значение 1 на 9 строках из 2 4 =16 наборов значений переменных.
3. Сколько решений имеет уравнение (в ответе укажите только число)?
Упростим выражение:
,
3 способ : построение СДНФ
Учтем одинаковые конъюнкции:
В итоге получаем СДНФ, содержащую 5 конъюнкций. Следовательно таблица истинности для данной функции имеет значение 1 на 5 строках из 2 4 =16 наборов значений переменных.
Построение логического выражения по таблице истинности:
для каждой строки таблицы истинности, содержащей 1 составляем произведение аргументов, причем, переменные, равные 0, входят в произведение с отрицанием, а переменные, равные 1 – без отрицания. Искомое выражение F будет составляется из суммы полученных произведений. Затем, если возможно, это выражение необходимо упростить.
Пример: дана таблица истинности выражения. Построить логическое выражение.
Решение:3. Задание на дом (5 минут)
Решить уравнение:
Сколько решений имеет уравнение (в ответе укажите только число)?
По заданной таблице истинности составить логическое выражение и
упростить его.
Применение уравнений широко распространено в нашей жизни. Они используются во многих расчетах, строительстве сооружений и даже спорте. Уравнения человек использовал еще в древности и с тех пор их применение только возрастает. В математике существуют определенные задачи, которые посвящены логике высказываний. Чтобы решить данного рода уравнения необходимо обладать неким багажом знаний: знания законов логики высказываний, знания таблиц истинности логических функций 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 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0
((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0
((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0
((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0
Решение:
Введем новые переменные: А=(X1 ≡ X2); В=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).
(Внимание! Каждая их переменных x1, x2, …, x10 должна входить только в одну из новых переменных А,В,С,D,Е, т.е. новые переменные независимы друг от друга).
Тогда система уравнений будет выглядеть так:
(А ∧ В) ∨ (¬А ∧ ¬В)=0
(В ∧ C) ∨ (¬B ∧ ¬C)=0
(С ∧ D) ∨ (¬C ∧ ¬D)=0
(D ∧ E) ∨ (¬D ∧ ¬E)=0
Построим дерево решений полученной системы:
Рассмотрим уравнение А=0, т.е. (X1 ≡ X2)=0. Оно имеет 2 корня:
X1 ≡ X2 |
||
Из этой же таблицы видно, что уравнение А=1 тоже имеет 2 корня. Расставим кол-во корней на дереве решений:
Чтобы найти количество решений одной ветви, надо перемножить количества решений на каждом ее уровне. Левая ветвь имеет 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 решения; правая ветвь имеет тоже 32 решения. Т.е. вся система имеет 32+32=64 решения.
Ответ: 64.
2. Метод рассуждений.
Сложность решения систем логических уравнений состоит в громоздкости полного дерева решений. Метод рассуждений позволяет не строить все дерево полностью, но понять при этом, сколько оно будет иметь ветвей. Рассмотрим этот метод на конкретных примерах.
Пример 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\/y1 =1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Решение :
Первое и второе уравнения содержат независимые переменные, которые связаны третьим условием. Построим дерево решений первого и второго уравнений.
Чтобы представить дерево решений системы из первого и второго уравнений, надо каждую ветвь первого дерева продолжить деревом для переменных у . Построенное таким образом дерево будет содержать 36 ветвей. Некоторые из этих ветвей не удовлетворяют третьему уравнению системы. Отметим на первом дереве количество ветвей дерева «у» , которые удовлетворяют третьему уравнению:
Поясним: для выполнения третьего условия при х1=0 должно быть у1=1, т.е все ветви дерева «х» , где х1=0 можно продолжить только одной ветвью из дерева «у» . И только для одной ветви дерева «х» (правой) подходят все ветви дерева «у». Таким образом, полное дерево всей системы содержит 11 ветвей. Каждая ветвь представляет собой одно решение исходной системы уравнений. Значит, вся система имеет 11 решений.
Ответ: 11.
Пример 2. Сколько различных решений имеет система уравнений
(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1
(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.
………………
(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1
(X1 ≡ X10) = 0
где x1, x2, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение : Упростим систему. Построим таблицу истинности части первого уравнения:
X1 ∧ X10 | ¬X1 ∧ ¬ X10 | (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10) |
||
Обратите внимание на последний столбец, он совпадает с результатом действия X1 ≡ X10.
X1 ≡ X10 |
После упрощения получим:
(X1 ≡ X2) ∨ (X1 ≡ X10)=1
(X2 ≡ X3) ∨ (X2 ≡ X10)=1
(X3 ≡ X4) ∨ (X3 ≡ X10)=1
……
(X9 ≡ X10) ∨ (X9 ≡ X10)=1
(X1 ≡ X10) = 0
Рассмотрим последнее уравнение: (X1 ≡ X10) = 0 , т.е. х1 не должно совпадать с х10. Чтобы первое уравнение было равно 1, должно выполняться равенство (X1 ≡ X2)=1, т.е. х1 должно совпадать с х2.
Построим дерево решений первого уравнения:
Рассмотрим второе уравнение: при х10=1 и при х2=0 скобка должна быть равна 1 (т.е. х2 совпадает с х3); при х10=0 и при х2=1 скобка (X2 ≡ X10)=0 , значит, скобка (X2 ≡ X3) должна быть равна 1 (т.е. х2 совпадает с х3):
Рассуждая таким образом, построим дерево решений для всех уравнений:
Таким образом, система уравнений имеет всего 2 решения.
Ответ: 2.
Пример 3.
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, которые удовлетворяют всем перечисленным ниже условиям?
(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1
(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1
(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1
(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1
(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1
Решение:
Построим дерево решений 1-го уравнения:
Рассмотрим второе уравнение:
- При х1=0 : вторая и третья скобки будут равны 0; чтобы первая скобка была равна 1, должны у1=1 , z1=1 (т.е. в этом случае - 1 решение)
- При х1=1 : первая скобка будет равна 0; вторая или третья скобка должна быть равна 1; вторая скобка будет равна 1 при у1=0 и z1=1; третья скобка будет равна 1 при у1=1 и z1=0 (т.е. в этом случае - 2 решения).
Аналогично для остальных уравнений. Отметим полученное кол-во решений у каждого узла дерева:
Чтобы узнать кол-во решений для каждой ветви, перемножим полученные числа по отдельности для каждой ветви (слева напрво).
1 ветвь: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 решение
2 ветвь: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 решения
3 ветвь: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 решения
4 ветвь: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 решения
5 ветвь: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 решения
Сложим полученные числа: всего 31 решение.
Ответ: 31.
3. Закономерное увеличение количества корней
В некоторых системах количество корней очередного уравнения зависит от количества корней предыдущего уравнения.
Пример 1. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, которые удовлетворяют всем перечисленным ниже условиям?
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
Упростим первое уравнение: (x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Тогда система примет вид:
¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0
¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0
¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0
И т.д.
Каждое следующее уравнение имеет на 2 корня больше, чем предыдущее.
4 уравнение имеет 12 корней;
5 уравнение имеет 14 корней
8 уравнение имеет 20 корней.
Ответ: 20 корней.
Иногда количество корней растет по закону чисел Фибоначчи.
Решение системы логических уравнений требует творческого подхода.
Муниципальное бюджетное общеобразовательное учреждение
«Средняя общеобразовательная школа № 18»
городского округа город Салават Республики Башкортостан
Системы логических уравнений
в задачах ЕГЭ по информатике
Раздел «Основы алгебры логики» в заданиях ЕГЭ считается одним из самых сложных и плохо решаемых. Средний процент выполнения заданий по данной теме самый низкий и составляет 43,2.
| Раздел курса | Средний процент выполнения по группам заданий |
| Кодирование информации и измерение ее количества | |
| Информационное моделирование | |
| Системы счисления | |
| Основы алгебры логики | |
| Алгоритмизация и программирование | |
| Основы информационно- коммуникационных технологий |
Исходя из спецификации КИМа 2018 года этот блок включает четыре задания разного уровня сложности.
| № задания | Проверяемые элементы содержания | Уровень сложности задания |
| Умение строить таблицы истинности и логические схемы | ||
| Умение осуществлять поиск информации в сети Интернет | ||
| Знание основных понятий и законов математической логики | ||
| Умение строить и преобразовывать логические выражения |
Задание 23 является высоким по уровню сложности, поэтому имеет самый низкий процент выполнения. Среди подготовленных выпускников (81-100 баллов) 49,8% выполнивших, средне подготовленные (61-80 баллов) справляются на 13,7%, оставшаяся группа учеников данное задание не выполняет.
Успешность решения системы логических уравнений зависит от знания законов логики и от четкого применения методов решения системы.
Рассмотрим решение системы логических уравнений методом отображения.
(23.154 Поляков К.Ю.) Сколько различных решений имеет система уравнений?
((x 1 y 1 ) (x 2 y 2 )) (x 1 x 2 ) (y 1 y 2 ) =1
((x 2 y 2 ) (x 3 y 3 )) (x 2 x 3 ) (y 2 y 3 ) =1
((x 7 y 7 ) (x 8 y 8 )) (x 7 x 8 ) (y 7 y 8 ) =1
где x 1 , x 2 ,…, x 8, у 1 ,у 2 ,…,у 8 - логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение . Все уравнения, включенные в систему, однотипны, и в каждое уравнение включено четыре переменных. Зная x1 и y1, можем найти все возможные значения x2 и y2, удовлетворяющие первому уравнению. Рассуждая аналогичным образом, из известных x2 и y2можем найти x3, y3, удовлетворяющее второму уравнению. То есть, зная пару (x1 , y1) и определив значение пары (x2 , y2) , мы найдем пару (x3 , y3 ), которая, в свою очередь, приведет к паре (x4 , y4 ) и так далее.
Найдем все решения первого уравнения. Это можно сделать двумя способами: построить таблицу истинности, через рассуждения и применение законов логики.
Таблица истинности:
| x 1 y 1 | x 2 y 2 | (x 1 y 1 ) (x 2 y 2 ) | (x 1 x 2 ) | (y 1 y 2 ) | (x 1 x 2 ) (y 1 y 2 ) | |||||
Построение таблицы истинности трудоемко и неэффективно по времени, поэтому применяем второй способ - логические рассуждения. Произведение равно 1 тогда и только тогда, когда каждый множитель равен 1.
(x 1 y 1 ) (x 2 y 2 ))=1
(x 1 x 2 ) =1
(y 1 y 2 ) =1
Рассмотрим первое уравнение. Следование равно 1, когда 0 0, 0 1, 1 1, значит (x1 y1)=0 при (01), (10), то пара (x 2 y 2 ) может быть любой (00), (01), (10), (11), а при (x1 y1)=1, то есть (00) и (11) пара (x2 y2)=1 принимает такие же значения (00) и (11). Исключим из этого решения те пары, для которых ложны второе и третье уравнения, то есть x1=1, x2=0, y1=1, y2=0.
| (x 1 , y 1 ) | (x 2 , y 2 ) |
Общее количество пар 1+1+1+22=25
2) (23.160 Поляков К.Ю.) Сколько различных решений имеет система логических уравнений
(x 1 (x 2 y 2 )) (y 1 y 2 ) = 1
(x 2 (x 3 y 3 )) (y 2 y 3 ) = 1
...
( x 6 ( x 7 y 7 )) ( y 6 y 7 ) = 1
x 7 y 7 = 1
Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,y1), (x2,y2) первого уравнения.
(x 1 (x 2 y 2 ))=1
(y 1 y 2 ) = 1
Решением второго уравнения являются пары (00), (01), (11).
Найдем решения первого уравнения. Если x1=0, то x2 , y2 - любые, если x1=1, то x2 , y2 принимает значение (11).
Составим связи между парами (x1 , y1) и (x2 , y2).
| (x 1 , y 1 ) | (x 2 , y 2 ) |
Составим таблицу для вычисления количества пар на каждом этапе.
| 0 |
|||||||
Учитывая решения последнего уравнения x 7 y 7 = 1, исключим пару (10). Находим общее число решений 1+7+0+34=42
3)(23.180) Сколько различных решений имеет система логических уравнений
(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 3 x 5 x 7 x 9 = 1
Решение. 1) Уравнения однотипные, поэтому методом рассуждения найдем всевозможные пары (x1,x2), (x3,x4) первого уравнения.
(x 1 x 2 ) (x 3 x 4 ) = 1
Исключим из решения пары, которые в следовании дают 0 (1 0), это пары (01, 00, 11) и (10).
Составим связи между парами (x1,x2), (x3,x4)
Данной материал содержит презентацию, в которой представлены методы решения логических уравнений и систем логических уравнений в задании В15 (№ 23, 2015) ЕГЭ по информатике. Известно, что это задание является одним из самых сложных среди заданий ЕГЭ. Презентация может быть полезна при проведении уроков по теме "Логика" в профильных классах, а также при подготовке к сдаче ЕГЭ.
Скачать:
Предварительный просмотр:
Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com
Подписи к слайдам:
Решение задания В15 (системы логических уравнений) Вишневская М.П., МАОУ «Гимназия №3» 18 ноября 2013 г., г. Саратов
Задание В15 - одно из самых сложных в ЕГЭ по информатике!!! Проверяются умения: преобразовывать выражения, содержащие логические переменные; описывать на естественном языке множество значений логических переменных, при которых заданный набор логических переменных истинен; подсчитывать число двоичных наборов, удовлетворяющих заданным условиям. Самое сложное, т.к. нет формальных правил, как это сделать, требуется догадка.
Без чего не обойтись!
Без чего не обойтись!
Условные обозначения конъюнкция: A /\ B , A B , AB , А &B, A and B дизъюнкция: A \ / B , A + B , A | B , А or B отрицание: A , А, not A эквиваленция: A В, A B, A B исключающее «или»: A B , A xor B
Метод замены переменных Сколько существует различных наборов значений логических переменных х1, х2, …, х9, х10, которые удовлетворяют всем перечисленным ниже условиям: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 В ответе не нужно перечислять все различные наборы х1, х2, …, х9, х10, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов (демо-версия 2012 г.)
Решение Шаг 1. Упрощаем, выполнив замену переменных t1 = x1 x2 t2 = x3 x4 t3 = x5 x6 t4 = x7 x8 t5 = x9 x10 После упрощения: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ (¬t4 \/ ¬ t5) =1 Рассмотрим одно из уравнений: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Очевидно, оно =1 только если одна из переменных равна 0, а другая – 1. Воспользуемся формулой для выражения операции XOR через конъюнкцию и дизъюнкцию: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1 t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1
Шаг2. Анализ системы ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т.к. tk = x2k-1 ≡ x2k (t1 = x1 x2 ,….), то каждому значению tk соответствует две пары значений x2k-1 и x2k , например: tk =0 соответствуют две пары - (0,1) и (1,0) , а tk =1 – пары (0,0) и (1,1).
Шаг3. Подсчет числа решений. Каждое t имеет 2 решения, количество t – 5. Т.о. для переменных t существует 2 5 = 32 решения. Но каждому t соответствует пара решений х, т.е. исходная система имеет 2*32 = 64 решения. Ответ: 64
Метод исключения части решений Сколько существует различных наборов значений логических переменных х1, х2, …, х5, y1,y2,… , y5 , которые удовлетворяют всем перечисленным ниже условиям: (x1→ x2)∧(x2→ x3)∧(x3→ x4)∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. В ответе не нужно перечислять все различные наборы х1, х2, …, х5, y 1 ,y2,… , y5, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов.
Решение. Шаг1. Последовательное решение уравнений х1 1 0 х2 1 0 1 х3 1 0 1 1 х4 1 0 1 1 1 х5 1 0 1 1 1 1 Первое уравнение – конъюнкция нескольких операций импликации, равна 1, т.е. каждая из импликаций истинна. Импликация ложна только в одном случае, когда 1 0, во всех других случаях (0 0, 0 1, 1 1) операция возвращает 1. Запишем это в виде таблицы:
Шаг1. Последовательное решение уравнений Т.о. получено 6 наборов решений для х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Рассуждая аналогично, приходим к выводу, что для y1, y2, y3, y4, y5 существует такой же набор решений. Т.к. уравнения эти независимы, т.е. в них нет общих переменных, то решением этой системы уравнений (без учета третьего уравнения) будет 6*6= 36 пар «иксов» и «игреков». Рассмотрим третье уравнение: y5→ x5 =1 Решением являются пары: 0 0 0 1 1 1 Не является решением пара: 1 0
Сопоставим полученные решения Там, где y5 =1, не подходят x5=0. таких пар 5. Количество решений системы: 36-5= 31 . Ответ: 31 Понадобилась комбинаторика!!!
Метод динамического программирования Сколько различных решений имеет логическое уравнение x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, где x 1, x 2, …, x 6 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количеств о таких наборов.
Решение Шаг1. Анализ условия Слева в уравнении последовательно записаны операции импликации, приоритет одинаков. Перепишем: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Каждая следующая переменная зависит не от предыдущей, а от результата предыдущей импликации!
Шаг2. Выявление закономерности Рассмотрим первую импликацию, X 1 → X 2. Таблица истинности: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Из одного 0 получили 2 единицы, а из 1 получили один 0 и одну 1. Всего один 0 и три 1, это результат первой операции.
Шаг2. Выявление закономерности Подключив к результату первой операции x 3 , получим: F(x 1 ,x 2) x 3 F(x 1 ,x 2) x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Из двух 0 – две 1, из каждой 1 (их 3) по одному 0 и 1 (3+3)
Шаг 3. Вывод формулы Т.о. можно составить формулы для вычисления количества нулей N i и количества единиц E i для уравнения с i переменными: ,
Шаг 4. Заполнение таблицы Заполним слева направо таблицу для i = 6, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец по предыдущему: : число переменных 1 2 3 4 5 6 Число нулей N i 1 1 3 5 11 21 Число единиц E i 1 2*1+1= 3 2*1+3= 5 11 21 43 Ответ: 43
Метод с использованием упрощений логических выражений Сколько различных решений имеет уравнение ((J → K) → (M N L)) ((M N L) → (¬ J K)) (M → J) = 1 где J , K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J , K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.
Решение Заметим, что J → K = ¬ J K Введем замену переменных: J → K=А, M N L =В Перепишем уравнение с учетом замены: (A → B) (B → A) (M → J)=1 4. (A B) (M → J)= 1 5. Очевидно, что A B при одинаковых значениях А и В 6. Рассмотрим последнюю импликацию M → J =1 Это возможно, если: M=J=0 M=0, J=1 M=J=1
Решение Т.к. A B , то При M=J=0 получаем 1 + К=0. Нет решений. При M=0, J=1 получаем 0 + К=0, К=0, а N и L - любые, 4 решения: ¬ J K = M N L K N L 0 0 0 0 0 1 0 1 0 0 1 1
Решение 10. При M=J=1 получаем 0+К=1 *N * L , или K=N*L, 4 решения: 11. Итого имеет 4+4=8 решений Ответ: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1
Источники информации: О.Б. Богомолова, Д.Ю. Усенков. В15: новые задачи и новое решение // Информатика, № 6, 2012, с. 35 – 39. К.Ю. Поляков. Логические уравнения // Информатика, № 14, 2011, с. 30-35. http://ege-go.ru/zadania/grb/b15/ , [ Электронный ресурс ] . http://kpolyakov.narod.ru/school/ege.htm , [ Электронный ресурс ] .
