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

Муниципальное бюджетное общеобразовательное учреждение

«Средняя общеобразовательная школа № 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)

142. Найдите наибольшее однобайтное двоичное решение уравнения
.

143. Найдите X , если .

144. Последовательность высказываний определена следующим рекуррентным соотношением: . Высказывания заданы, причем и истинны, ложно. Истинно или ложно высказывание ? Как выражается через ?

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

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

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

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

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

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

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

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

153. Найдите все различные решения уравнения: .

Найти корни логического уравнения:

Найти корни систем логических уравнений:

Найдите количество решений следующих систем логических уравнений:

x 3

l 2

l 3

k

M

N

Электрическая цепь между точками M и N составлена по схеме, изображенной на рисунке. Рассмотрим следующие четыре высказывания:
A = {Элемент цепи k вышел из строя},
B i = {Элемент цепи l i вышел из строя}. Замкнута ли цепь, если:
а) высказывание истинно,
б) высказывание истинно?
Является ли одно из этих высказываний отрицанием другого?

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

184. (Аварийный станок) На участке цеха стоят три станка – два рабочих, третий аварийный. Требуется соединить станки автоматической линией так, чтобы третий станок включался тогда, и только тогда, когда останавливается хотя бы один из первых двух станков.

185. Пусть в некотором конкурсе решается вопрос о допуске того или иного участника к следующему туру тремя членами жюри: A, B, C. Решение положительно тогда и только тогда, когда хотя бы двое членов жюри высказываются за допуск, причем среди них обязательно должен быть председатель жюри С . Необходимо разработать устройство для голосования, в котором каждый член жюри нажимает на одну из двух кнопок – «За» или «Против», а результат голосования всех трех членов жюри определяется по тому, загорится (решение принято) или нет (решение не принято) сигнальная лампочка.

186. Три преподавателя отбирают задачи для олимпиады. На выбор предлагается несколько задач. По каждой из задач каждый из преподавателей высказывает свое мнение: легкая задача (0) или трудная задача (1). Задача включается в олимпиадное задание, если не менее двух преподавателей отметили ее как трудную, но если все три преподавателя считают ее трудной, то такая задача не включается в олимпиадное задание как слишком сложная. Составьте функциональную схему устройства, которое будет выдавать на выходе 1, если задача включается в олимпиадное задание, и 0, если не включается.

187. Запишите структурную формулу для следующей логической схемы:

&

a

b

c

f

191. Имеются только два конъюнктора и один инвертор. Можно ли из этих трех логических элементов (вентилей) составить логическую схему, эквивалентную схеме выражения . Какой вид имеет эта схема?

192. Имеется только 1 конъюнктор, 1 дизъюнктор и 1 инвертор. Можно ли составить из этих элементов логическую схему, эквивалентную схеме логического выражения ? Все три вентиля должны быть использованы. Какой вид имеет эта схема?

Назначение сервиса . Онлайн-калькулятор предназначен для построения таблицы истинности для логического выражения .
Таблица истинности – таблица содержащая все возможные комбинации входных переменных и соответствующее им значения на выходе.
Таблица истинности содержит 2 n строк, где n – число входных переменных, и n+m – столбцы, где m – выходные переменные.

Инструкция . При вводе с клавиатуры используйте следующие обозначения: Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис .

Правила ввода логической функции

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 различных комбинаций возможных значений аргументов.

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

Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:

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

Для операции отрицания НЕ приняты следующие условные обозначения:
не А, Ā, not A, ¬А, !A
Результат операции отрицания НЕ определяется следующей таблицей истинности:

A	не А
0	1
1	0

Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.

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

Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
Применяемые обозначения: А или В, А V В, A or B, A||B.
Результат операции ИЛИ определяется следующей таблицей истинности:
Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В - ложны.

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

Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
Применяемые обозначения: А и В, А Λ В, A & B, A and B.
Результат операции И определяется следующей таблицей истинности:

A	B	А и B
0	0	0
0	1	0
1	0	0
1	1	1

Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.

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

Эта операция связывает два простых логических выражения, из которых первое является условием, а второе - следствием из этого условия.
Применяемые обозначения:
если А, то В; А влечет В; if A then В; А→ В.
Таблица истинности:

A	B	А → B
0	0	1
0	1	1
1	0	0
1	1	1

Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.

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

Применяемое обозначение: А ↔ В, А ~ В.
Таблица истинности:

A	B	А↔B
0	0	1
0	1	0
1	0	0
1	1	1

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

Применяемое обозначение: А XOR В, А ⊕ В.
Таблица истинности:

A	B	А⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.

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

• Действия в скобках
• Инверсия
• Конъюнкция (&)
• Дизъюнкция (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:

Какое выражение соответствует 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.Построить заголовок таблицы истинности специального вида 3.Заполнить строки таблицы истинности для всех сочетаний А и В, подставляя вместо X - 0 или 1. 4.Сформировать таблицу истинности для X = F (А,B) 5.По таблице истинности определить вид функции X, при необходимости воспользовавшись методами построения СКНФ и СДНФ, которые будут рассмотрены ниже.

Построение таблицы истинности специального вида ¬((А+B)·(X A·B))=¬(B+¬(X A))

Таблица истинности X=F(A, B) ABX Соответствует отрицанию импликации В в А ОТВЕТ:

Комбинационные схемы логических устройств Базисные элементы (ГОСТ): 1 А В Дизъюнкция А В Эквивалентность & А В Конъюнкция M2 А В XOR

Комбинационные схемы логических устройств Базисные элементы (ГОСТ): 1 А В Импликация & А В Элемент Шеффера & А В Коимпликация 1 А В Элемент Вебба

Пример схемы F 1 & 1 & & 1M2 B A

Решение схем 1 Вариант – преобразование схемы в сложное логическое выражение и затем – упрощение его по законам логики. 2 Вариант – построение таблицы истинности а затем, при необходимости, построение через СКНФ или СДНФ (см. ниже). Рассмотрим второй вариант, как более простой и понятный.

Построение таблицы истинности AB A + B + · B B · A + A B A + · ·

Таблица истинности F(A, B) ABX Соответствует отрицанию импликации В в А ОТВЕТ:

СДНФ и СКНФ (определения) Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ) Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной нормальной формой (ДНФ)

СДНФ и СКНФ (определения) Совершенной дизъюнктивной нормальной формой (СДНФ), называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием). Совершенной конъюнктивной нормальной формой (СКНФ), называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием).

Алгоритм получения СДНФ по таблице истинности 1.Отметить строки таблицы истинности в последнем столбце которых стоят 1. 2.Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание. 3.Все полученные конъюнкции связать в дизъюнкцию. Алгоритм получения СКНФ по таблице истинности 1.Отметить строки таблицы истинности в последнем столбце которых стоят 0. 2.Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение переменной в данной строке равно 0, то в конъюнкцию включать саму эту переменную, если равно 1, то ее отрицание. 3.Все полученные дизъюнкции связать в конъюнкцию.

Пример построения СKНФ XY F(X,Y) Отметить нули 2. Дизъюнкции: X + Y 3. Конъюнкция: (X + Y) · (X + Y)