Пусть – логическая функция от n переменных. Логическое уравнение имеет вид:
Константа С имеет значение 1 или 0.
Логическое уравнение может иметь от 0 до различных решений. Если С равно 1, то решениями являются все те наборы переменных из таблицы истинности, на которых функция F принимает значение истина (1). Оставшиеся наборы являются решениями уравнения при C, равном нулю. Можно всегда рассматривать только уравнения вида:
Действительно, пусть задано уравнение:
В этом случае можно перейти к эквивалентному уравнению:
Рассмотрим систему из k логических уравнений:
Решением системы является набор переменных, на котором выполняются все уравнения системы. В терминах логических функций для получения решения системы логических уравнений следует найти набор, на котором истинна логическая функция Ф, представляющая конъюнкцию исходных функций :
Если число переменных невелико, например, менее 5, то нетрудно построить таблицу истинности для функции , что позволяет сказать, сколько решений имеет система и каковы наборы, дающие решения.
В некоторых задачах ЕГЭ по нахождению решений системы логических уравнений число переменных доходит до значения 10. Тогда построить таблицу истинности становится практически неразрешимой задачей. Для решения задачи требуется другой подход. Для произвольной системы уравнений не существует общего способа, отличного от перебора, позволяющего решать такие задачи.
В предлагаемых на экзамене задачах решение обычно основано на учете специфики системы уравнений. Повторяю, кроме перебора всех вариантов набора переменных, общего способа решения задачи нет. Решение нужно строить исходя из специфики системы. Часто полезно провести предварительное упрощение системы уравнений, используя известные законы логики. Другой полезный прием решения этой задачи состоит в следующем. Нам интересны не все наборы, а только те, на которых функция имеет значение 1. Вместо построения полной таблицы истинности будем строить ее аналог - бинарное дерево решений. Каждая ветвь этого дерева соответствует одному решению и задает набор, на котором функция имеет значение 1. Число ветвей в дереве решений совпадает с числом решений системы уравнений.
Что такое бинарное дерево решений и как оно строится, поясню на примерах нескольких задач.
Задача 18
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют системе из двух уравнений?
Ответ: Система имеет 36 различных решений.
Решение: Система уравнений включает два уравнения. Найдем число решений для первого уравнения, зависящего от 5 переменных – . Первое уравнение можно в свою очередь рассматривать как систему из 5 уравнений. Как было показано, система уравнений фактически представляет конъюнкцию логических функций. Справедливо и обратное утверждение, - конъюнкцию условий можно рассматривать как систему уравнений.
Построим дерево решений для импликации () - первого члена конъюнкции, который можно рассматривать как первое уравнение. Вот как выглядит графическое изображение этого дерева
Дерево состоит из двух уровней по числу переменных уравнения. Первый уровень описывает первую переменную . Две ветви этого уровня отражают возможные значения этой переменной – 1 и 0. На втором уровне ветви дерева отражают только те возможные значения переменной , для которых уравнение принимает значение истина. Поскольку уравнение задает импликацию, то ветвь, на которой имеет значение 1, требует, чтобы на этой ветви имело значение 1. Ветвь, на которой имеет значение 0, порождает две ветви со значениями , равными 0 и 1. Построенное дерево задает три решения, на которых импликация принимает значение 1. На каждой ветви выписан соответствующий набор значений переменных, дающий решение уравнения.
Вот эти наборы: {(1, 1), (0, 1), (0, 0)}
Продолжим построение дерева решений, добавляя следующее уравнение, следующую импликацию . Специфика нашей системы уравнений в том, что каждое новое уравнение системы использует одну переменную из предыдущего уравнения, добавляя одну новую переменную. Поскольку переменная уже имеет значения на дереве, то на всех ветвях, где переменная имеет значение 1, переменная также будет иметь значение 1. Для таких ветвей построение дерева продолжается на следующий уровень, но новые ветви не появляются. Единственная ветвь, где переменная имеет значение 0, даст разветвление на две ветви, где переменная получит значения 0 и 1. Таким образом, каждое добавление нового уравнения, учитывая его специфику, добавляет одно решение. Исходное первое уравнение:
имеет 6 решений. Вот как выглядит полное дерево решений для этого уравнения:
Второе уравнение нашей системы аналогично первому:
Разница лишь в том, что в уравнении используются переменные Y. Это уравнение также имеет 6 решений. Поскольку каждое решение для переменных может быть скомбинировано с каждым решением для переменных , то общее число решений равно 36.
Заметьте, построенное дерево решений дает не только число решений (по числу ветвей), но и сами решения, выписанные на каждой ветви дерева.
Задача 19
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?
Эта задача является модификацией предыдущей задачи. Разница в том, что добавляется еще одно уравнение, связывающее переменные X и Y.
Из уравнения следует, что когда имеет значение 1(одно такое решение существует), то и имеет значение 1. Таким образом, существует один набор, на котором и имеют значения 1. При , равном 0, может иметь любое значение, как 0, так и 1. Поэтому каждому набору с , равном 0, а таких наборов 5, соответствует все 6 наборов с переменными Y. Следовательно, общее число решений равно 31.
Задача 20
Решение: Вспоминания основные эквивалентности, запишем наше уравнение в виде:
Циклическая цепочка импликаций означает тождественность переменных, так что наше уравнение эквивалентно уравнению:
Это уравнение имеет два решения, когда все равны либо 1, либо 0.
Задача 21
Сколько решений имеет уравнение:
Решение: Так же, как и в задаче 20, от циклических импликаций перейдем к тождествам, переписав уравнение в виде:
Построим дерево решений для этого уравнения:
Задача 22
Сколько решений имеет следующая система уравнений?
Можно выделить различные способы решения систем логических уравнений. Это сведение к одному уравнению, построение таблицы истинности и декомпозиция.
Задача: Решить систему логических уравнений:
Рассмотрим метод сведения к одному уравнению . Данный метод предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 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) |
В настоящее время возрастают требования к
повышению качества обучения школьников. Одной из
важнейших инноваций содержания математического
образования есть включение в школьные программы
элементов математической логики. Это
обусловлено ролью, которую играют логические
знания в общеобразовательной подготовке
современного человека.
Изучение элементов математической логики
целесообразно начать в 5–6-x классах, или в 7
классе – в зависимости от системы изложения в
учебнике, по которому ведется преподавание.
Необходимое время может быть найдено за счет
отказа от рассмотрения с учащимися вопросов,
которые не входят в обязательный минимум
содержания основной школы (корень степени п,
степень с дробным показателем, метод интервалов,
тригонометрический материал в курсе алгебры), но
сохраняются в ряде учебников и в практике работы
учителей.
Но чаще всего данные разделы изучаются только на
факультативных курсах.
Тема: “Системы логических уравнений” (10 кл.)
Цели урока:
- знакомство учащихся с понятием систем логических уравнений изучение различных методов их решения, повторение способов решения алгебраических систем и скалярного произведения векторов;
- развитие математического мышления и логической речи учащихся, воображения, умения анализировать, применять свои знания в незнакомой ситуации;
- воспитание интереса к предмету, прилежания, внимания.
Оборудование: школьная доска, мел, тетради, ручки, карандаши, сетки для решения систем с тремя и четырьмя неизвестными.
ХОД УРОКА
I. Организационный момент
II. Сообщение темы урока
Запись названия темы в тетрадь.
– На прошлом занятии мы изучали логические операции. Сегодня мы продолжаем изучать логические уравнения, научимся решать системы таких уравнений. Сразу нужно отметить, что системы логических уравнений решаются немного иначе, чем алгебраические. Вернее, другими способами.
III. Актуализация знаний
– Что значит, решить систему с двумя
переменными?
Решить систему с двумя переменными – это значит
найти все пары (х, у), которые удовлетворяют
каждому из заданных уравнений или доказать, что
решения нет.
Какие вы знаете способы решения систем?
- способ подстановки,
- способ сложения,
- способ введения новых переменных,
- графический способ.
1. Решить систему уравнений по рядам.
- Первый ряд – методом сложения;
- Второй – графическим способом;
- Третий – методом подстановки.
а) Сложив почленно уравнения, имеем: 2х + 10х = 15 + 9;
12х = 24; х = 2, подставив это значение во второе уравнение, получим: 10 . 2 – 11у = 9, откуда у = 1.
Ответ: (2;1).
б) Из первого уравнения , из второго уравнения ,
А (2;1) – точка пересечения графиков уравнений.
(2;1) – решение системы.
в) Из первого уравнения подставляем во второе
11у = 15 – 4, 11у = 11, у = 1.
Ответ: (2;1).
– Что называется скалярным произведением
векторов?
Скалярным произведением векторов называется
число, равное произведению длин этих векторов на
косинус угла между ними.
Как записать скалярное произведение в
координатной форме?
.
IV. Основной этап
Используя две операции “дизьюкнцию” и “конъюнкцию”, рассмотрим булевы системы двух уравнений с двумя неизвестными:
Нахождение переменной в одном уравнении с
одной логической операцией приводит к
нескольким решениям. Если бы решение системы
выражалось некоторой определенной формулой, то
при подстановке исходных данных (коэффициентов
уравнения) мы получили бы вполне определенное
решение. На простом примере мы видим
многозначность решения, поэтому либо решения
системы в общем виде должно выражаться
несколькими формулами, либо таких формул в явном
виде не существует. В настоящее время такие
формулы еще не найдены, поэтому системы
логических уравнений решают своеобразными
методами, с которыми мы сегодня и познакомимся на
уроке.
Система зависит от шести параметров a
, b
,
c
, d
, m
, n
, каждое из которых
принимает два значения 0 или 1. Следовательно,
всего получаем 2 6 = 64 случая.
Аналитический результат можно получить
логичными рассуждениями и перебрав все 64 случая.
Задание 1. (один учащийся работает у доски).
Решить систему, если a = 0, b = 0, c = 0, d = 0, m = 0, n = 0.
.
Ответ: система имеет 4 решения: (1;1), (0;1), (1;0),(0;0).
Задание 2. (самостоятельно в тетрадях с последующей проверкой).
Решить систему, если a = 1, b = 0, c = 0, d = 0, m = 0, n = 0.
,
Ответ: система имеет 2 решения: (0;0), (0;1).
Аналогично можно решить остальные 62 системы,
подставляя вместо параметров a
, b
, c
,
d
, m
, n
соответственно значения 0 и 1.
Даже можно объединить некоторые случаи в классы,
чтобы выделить условия для случаев, когда
система имеет единственное решение, несколько
решений или не имеет решения.
В школьном курсе математики можно выделить
весьма ограниченный круг задач, которые можно
решить при помощи систем логических уравнений.
Задание 3. Шесть прозрачных стаканов с водой расставлены в два параллельных ряда по три стакана в каждом. На рисунке представлен вид спереди и вид с правой стороны. Через прозрачные стенки стаканов видны уровни воды в каждом стакане и во всех стаканах, стоящих за ними. Определите, сколько воды налито в каждый стакан.
По рисунку видно, что стаканы либо полные, либо
пустые. Множество стаканов, которые могут
оказаться на указанных шести местах, образуют
алфавит, который состоит из двух элементов.
Обозначим пустой стакан – 0, а полный – 1. тогда
множество состоит из 0 и 1, т.е. = {0,1} .
Занумеруем проекции на рисунке числами от 1 до 5.
Занумеруем ряды стаканов следующим образом и
укажем элементы, которые могут оказаться в этих
рядах
Первая проекция показывает, что в первом столбце нет полных стаканов, т.е. х 11 = 0, х 21 = 0.
Из пятой проекции видно, что х 23 = 0, х 22 = 0. Остальные элементы легко определить: х 12 = 1, х 13 = 1.
Аналитически постановка задачи сводится к решению системы уравнений
Имеем систему уравнений, в которой операции
“+” – дизъюнкция, “ .
” –
конъюнкция.
Из второго уравнения системы и истинных таблиц
конъюнкции и дизъюнкции получаем х
21 + х
22
+ х
23 = 0 => х
21 = х
22 =
х
23 = 0.
Из третьего уравнения => х
11 = 0.
Подставим найденные значения неизвестных в
четвертое и пятое уравнения системы:
Все свободные и неизвестные члены принимают
значения 0 или 1, а уравнения удовлетворяют
логическим операциям, т.е. получаем систему
логических уравнений.
Таким образом, если в задаче даны два вида
стаканов, то она легко решается путем решения
системы логических уравнений. Это позволяет
сэкономить время, дает более короткий и простой
путь решения.
Рассмотрим метод прозрачных таблиц (метод сеток)
– аналог графического способа для решения
алгебраических систем, который позволяет быстро
решать систему уравнений, содержащую не более
четырех переменных.
Этот метод основан на скалярном произведении
векторов.
Тема урока: Решение логических уравнений
Образовательная – изучение способов решения логических уравнений, формирование умений и навыков решения логических уравнений и построения логического выражения по таблице истинности;Развивающая - создать условия для развития познавательного интереса учащихся, способствовать развитию памяти, внимания, логического мышления;
Воспитательная : способствовать воспитанию умения выслушивать мнение других, воспитание воли и настойчивости для достижения конечных результатов.
Тип урока: комбинированный урок
Оборудование: компьютер, мультимедийный проектор, презентация 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 минут)
Решить уравнение:
Сколько решений имеет уравнение (в ответе укажите только число)?
По заданной таблице истинности составить логическое выражение и
упростить его.
