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

Пусть – логическая функция от 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. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
3. Максимальное количество переменных равно 10 .

Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики - алгебры логики. В алгебре логики можно выделить три основные логические функции: "НЕ" (отрицание), "И" (конъюнкция), "ИЛИ" (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:
По алгебраической форме можно построить схему логического устройства, используя логические элементы.


Рисунок1- Схема логического устройства

Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможны х логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.

Операция НЕ - логическое отрицание (инверсия)

• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.

Операция ИЛИ - логическое сложение (дизъюнкция, объединение)

Операция И - логическое умножение (конъюнкция)

Операция «ЕСЛИ-ТО» - логическое следование (импликация)

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

Приоритет логических операций

• Действия в скобках
• Инверсия
• Конъюнкция (&)
• Дизъюнкция (V), Исключающее ИЛИ (XOR), сумма по модулю 2
• Импликация (→)
• Эквивалентность (↔)

Совершенная дизъюнктивная нормальная форма

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все логические слагаемые формулы различны.
3. Ни одно логическое слагаемое не содержит переменную и её отрицание.
4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Совершенная конъюнктивная нормальная форма

1. Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все элементарные дизъюнкции различны.
3. Каждая элементарная дизъюнкция содержит переменную один раз.
4. Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.

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

Развивающая - создать условия для развития познавательного интереса учащихся, способствовать развитию памяти, внимания, логического мышления;

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

Тип урока: комбинированный урок

Оборудование: компьютер, мультимедийный проектор, презентация 6.

Ход урока

Повторение и актуализацию опорных знаний. Проверка домашнего задания (10 минут)

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

Выполним проверку домашнего задания по упрощению логических выражений:

1. Какое из приведенных слов удовлетворяет логическому условию:

(первая буква согласная→вторая буква согласная) ٨ (последняя буква гласная → предпоследняя буква гласная)? Если таких слов несколько, укажите наименьшее из них.

1) АННА 2) МАРИЯ 3) ОЛЕГ 4) СТЕПАН

Введем обозначения:

А – первая буква согласная

В – вторая буква согласная

С – последняя буква гласная

D – предпоследняя буква гласная

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

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

2. Укажите, какое логическое выражение равносильно выражению

Упростим запись исходного выражения и предложенных вариантов:

3. Дан фрагмент таблицы истинности выражения 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 способ: составление таблицы истинности

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

(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 минут)

Решить уравнение:

Сколько решений имеет уравнение (в ответе укажите только число)?

По заданной таблице истинности составить логическое выражение и

упростить его.

В настоящее время возрастают требования к повышению качества обучения школьников. Одной из важнейших инноваций содержания математического образования есть включение в школьные программы элементов математической логики. Это обусловлено ролью, которую играют логические знания в общеобразовательной подготовке современного человека.
Изучение элементов математической логики целесообразно начать в 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, а уравнения удовлетворяют логическим операциям, т.е. получаем систему логических уравнений.
Таким образом, если в задаче даны два вида стаканов, то она легко решается путем решения системы логических уравнений. Это позволяет сэкономить время, дает более короткий и простой путь решения.
Рассмотрим метод прозрачных таблиц (метод сеток) – аналог графического способа для решения алгебраических систем, который позволяет быстро решать систему уравнений, содержащую не более четырех переменных.
Этот метод основан на скалярном произведении векторов.