Решение логических уравнений по информатике. Системы логических уравнений в задачах егэ по информатике

Пусть – логическая функция от 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

Сколько решений имеет следующая система уравнений?

Способы решения систем логических уравнений

Киргизова Е.В., Немкова А.Е.

Лесосибирский педагогический институт –

филиал Сибирского федерального университета, Россия

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

Овладение азами этой науки невозможно без решения логических задач. Проверка сформированности умений применять свои знания в новой ситуации осуществляется за счет сдачи. В частности, это умение решать логические задачи. Задания В15 в ЕГЭ, являются заданиями повышенной сложности, так как они содержат системы логических уравнений. Можно выделить различные способы решения систем логических уравнений. Это сведение к одному уравнению, построение таблицы истинности, декомпозиция, последовательное решение уравнений и т.д.

Задача: Решить систему логических уравнений:

Рассмотрим метод сведения к одному уравнению . Данный метод предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 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 . Переменная А может принимать 2 значения 0 и 1:

Из первого уравнения следует, что , поэтому при A = 0 п олучаем B = 0 , а при A = 1 имеем B = 1 . Итак, первое уравнение имеет два решения относительно переменных A и B .

Изобразим второе уравнение, из которого определим значения C для каждого варианта. При A =1 импликация не может быть ложной, то есть вторая ветка дерева не имеет решения. При A =0 получаем единственное решение C = 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)*

Далее можно увидеть, что одно уравнение истинно в следующих трех случаях: (0; 0), (0; 1), (1; 1). Система двух уравнений истина в четырех случаях (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). При этом сразу видно, что существует решение, состоящее из одних нулей и еще m решений, в которых добавляется по одной единице, начиная с последней позиции до заполнения всех возможных мест. Можно предположить, что общее решение будет иметь такой же вид, но чтобы такой подход стал решением, требуется доказательство, что предположение верно.

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

Литература:

1. Логические задачи / О.Б. Богомолова – 2-е изд. – М.: БИНОМ. Лаборатория знаний, 2006. – 271 с.: ил.

2. Поляков К.Ю. Системы логических уравнений / Учебно-методическая газета для учителей информатики: Информатика №14, 2011 г.

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, где J, K, L, M, N — логические переменные?

Решение.

Выражение (N ∨ ¬N) истинно при любом N, поэтому

J ∧ ¬K ∧ L ∧ ¬M = 0.

Применим отрицание к обеим частям логического уравнения и используем закон де Моргана ¬ (А ∧ В) = ¬ А ∨ ¬ В. Получим ¬J ∨ K ∨ ¬L ∨ M = 1.

Логическая сумма равна 1, если хотя бы одно из составляющих ее высказываний равно 1. Поэтому полученному уравнению удовлетворяют любые комбинации логических переменных кроме случая, когда все входящие в уравнение величины равны 0. Каждая из 4 переменных может быть равна либо 1, либо 0, поэтому всевозможных комбинаций 2·2·2·2 = 16. Следовательно, уравнение имеет 16 −1 = 15 решений.

Осталось заметить, что найденные 15 решений соответствуют любому из двух возможных значений значений логической переменной N, поэтому исходное уравнение имеет 30 решений.

Ответ: 30

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

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

где J, K, L, M, N – логические переменные?

В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение.

Используем формулы A → B = ¬A ∨ B и ¬(А ∨ В) = ¬А ∧ ¬В

Рассмотрим первую подформулу:

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Рассмотрим вторую подформулу

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Рассмотрим третью подформулу

1) M → J = 1 следовательно,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Объединим:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 следовательно, 4 решения.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Объединим:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L следовательно, 4 решения.

в) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Ответ: 4 + 4 = 8.

Ответ: 8

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

((K ∨ L) → (L ∧ M ∧ N)) = 0

где K, L, M, N – логические переменные? В Ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве Ответа Вам нужно указать количество таких наборов.

Решение.

перепишем уравнение, используя более простые обозначения операций:

((K + L) → (L · M · N)) = 0

1) из таблицы истинности операции «импликация» (см. первую задачу) следует, что это равенство верно тогда и только тогда, когда одновременно

K + L = 1 и L · M · N = 0

2) из первого уравнения следует, что хотя бы одна из переменных, K или L, равна 1 (или обе вместе); поэтому рассмотрим три случая

3) если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения

4) если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

5) если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения

6) всего получаем 4 + 3 + 3 = 10 решений.

Ответ: 10

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

(K ∧ L) ∨ (M ∧ N) = 1

Решение.

Выражение истинно в трех случаях, когда (K ∧ L) и (M ∧ N) равны соответственно 01, 11, 10.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N равны 1, а K и L любые, кроме как одновременно 1. Следовательно 3 решения.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 решение.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 решения.

Ответ: 7.

Ответ: 7

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

(X ∧ Y ∨ Z) → (Z ∨ P) = 0

где X, Y, Z, P – логические переменные? В ответе не нужно перечислять все различные наборы значений, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение.

(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Логическое ИЛИ ложно только в одном случае: когда оба выражения ложны.

Следовательно,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Следовательно, существует только одно решение уравнения.

Ответ: 1

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

(K ∨ L) ∧ (M ∨ N) = 1

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение.

Логическое И истинно только в одном случае: когда все выражения истинны.

K ∨ L = 1, M ∨ N = 1.

Каждое из уравнений дает по 3 решения.

Рассмотрим уравнение А ∧ В = 1 если и А и В принимают истинные значения в трех случаях каждое, то в целом уравнение имеет 9 решений.

Следовательно ответ 9.

Ответ: 9

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

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

где A, B, C, D – логические переменные?

В ответе не нужно перечислять все различные наборы значений A, B, C, D, при которых выполнено данное равенство. В качестве ответа вам нужно указать количество таких наборов.

Решение.

Логическое "ИЛИ" истинно, когда истинно хотя бы одно из утверждений.

(D ∧ ¬D)= 0 при любых D.

Следовательно,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, что дает нам 3 варианта решений при каждом D.

(D ∧ ¬ D)= 0 при любых D, что дает нам два варианта решений (при D = 1, D = 0).

Следовательно: всего решений 2*3 = 6.

Итого 6 решений.

Ответ: 6

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

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

Решение.

Применим отрицание к обеим частям уравнения:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Логическое ИЛИ истинно в трех случаях.

Вариант 1.

K ∧ L ∧ M = 1, тогда K, L, M = 1, а ¬L ∧ M ∧ N = 0. N любое, то есть 2 решения.

Вариант 2.

¬L ∧ M ∧ N = 1, тогда N, M = 1; L = 0, K любое, то есть 2 решения.

Следовательно, ответ 4.

Ответ: 4

A, B и С — целые числа, для которых истинно высказывание

¬ (А = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(С > B)).

Чему равно В, если A = 45 и C = 43?

Решение.

Обратим внимание, что это сложное высказывание состоит из трех простых

1) ¬(А = B); (A > B)→(B > C); (B > A)→(С > B);

2) эти простые высказывания связаны операцией ∧ (И, конъюнкция), то есть, они должны выполняться одновременно;

3) из ¬(А = B)=1 сразу следует, что А B;

4) предположим, что A > B, тогда из второго условия получаем 1→(B > C)=1; это выражение может быть истинно тогда и только тогда, когда B > C = 1;

5) поэтому имеем A > B > C, этому условию соответствует только число 44;

6) на всякий случай проверим и вариант A 0 →(B > C)=1;

это выражение истинно при любом B; теперь смотрим третье условие получаем

это выражение может быть истинно тогда и только тогда, когда C > B, и тут мы получили противоречие, потому что нет такого числа B, для которого C > B > A.

Ответ: 44.

Ответ: 44

Составьте таблицу истинности для логической функции

X = (А ↔ B) ∨ ¬(A → (B ∨ C))

в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В — числа 77, столбец значений аргумента С — числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему(включая нулевой набор). Переведите полученную двоичную запись значений функции X в десятичную систему счисления.

Решение.

Запишем уравнение, используя более простые обозначения операций:

1) это выражение с тремя переменными, поэтому в таблице истинности будет строчек; следовательно, двоичная запись чисел, по которым строятся столбцы таблицы А, В и С, должна состоять из 8 цифр

2) переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел

3) вряд ли вы сможете сразу написать значения функции Х для каждой комбинации, поэтому удобно добавить в таблицу дополнительные столбцы для расчета промежуточных результатов (см. таблицу ниже)

X 0

А	В	С
0	0
0	1	1
0	0	1
1	0	1
1	1	1
0	1	0
1	0	0
1	1	0

4) заполняем столбцы таблицы:

А	В	С					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

значение равно 1 только в тех строчках, где А = В

значение равно 1 в тех строчках, где либо В либо С = 1

значение равно 0 только в тех строчках, где А = 1 и В + С = 0

значение — это инверсия предыдущего столбца (0 заменяется на 1, а 1 – на 0)

результат Х (последний столбец) — это логическая сумма двух столбцов и

5) чтобы получить ответ, выписываем биты из столбца Х сверху вниз:

6) переводим это число в десятичную систему:

Ответ: 171

Каково наибольшее целое число X, при котором истинно высказывание (10 (X+1)·(X+2))?

Решение.

Уравнение является операцией импликации между двумя отношениями:

1) Конечно, здесь можно применить тот же способ, что и в примере 2208, однако при этом понадобится решать квадратные уравнения (не хочется…);

2) Заметим, что по условию нас интересуют только целые числа, поэтому можно попытаться как─то преобразовать исходное выражение, получив равносильное высказывание (точные значения корней нас совершенно не интересуют!);

3) Рассмотрим неравенство : очевидно, что может быть как положительным, так и отрицательным числом;

4) Легко проверить, что в области высказывание истинно при всех целых , а в области — при всех целых (чтобы не запутаться, удобнее использовать нестрогие неравенства, и , вместо и );

5) Поэтому для целых можно заменить на равносильное выражение

6) область истинности выражения — объединение двух бесконечных интервалов;

7) Теперь рассмотрим второе неравенство : очевидно, что так же может быть как положительным, так и отрицательным числом;

8) В области высказывание истинно при всех целых , а в области — при всех целых , поэтому для целых можно заменить на равносильное выражение

9) область истинности выражения — закрытый интервал;

10) Заданное выражение истинно везде, кроме областей, где и ;

11) Обратите внимание, что значение уже не подходит, потому что там и , то есть импликация дает 0;

12) При подставлении 2, (10 (2+1) · (2+2)), или 0 → 0 что удовлетворяет условию.

Таким образом, ответ 2.

Ответ: 2

Каково наибольшее целое число X, при котором истинно высказывание

(50 (X+1)·(X+1))?

Решение.

Применим преобразование импликации и преобразуем выражение:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Логическое ИЛИ истинно когда истинно хотя бы одно логическое высказывание. Решив оба неравенства и учитывая, что видим, что наибольшее целое число, при котором выполняется хотя бы одно из них - 7 (на рисунке жёлтым изображено положительное решение второго неравенства, синим - первого).

Ответ: 7

Укажите значения переменных К, L, M, N, при которых логическое выражение

(¬(М ∨ L) ∧ К) → (¬К ∧ ¬М ∨ N)

ложно. Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.

Решение.

Дублирует задание 3584.

Ответ: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Решение.

Применим преобразование импликации:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Применим отрицание к обоим частям уравнения:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Преобразуем:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Следовательно, M = 0, N = 0, рассмотрим теперь (¬K ∧ L ∨ M ∧ L):

из того, что M = 0, N = 0 следует, что M ∧ L = 0, тогда ¬K ∧ L = 1, то есть K = 0, L = 1.

Ответ: 0100

Укажите значения переменных K, L, M, N, при которых логическое выражение

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Решение.

Запишем уравнение, используя более простые обозначения операций (условие «выражение ложно» означает, что оно равно логическому нулю):

1) из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных

2) из таблицы истинности операции «импликация» следует, что это выражение ложно тогда и только тогда, когда одновременно

3) первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда и ; отсюда следует (логическая сумма равна нулю), что может быть только при ; таким образом, три переменных мы уже определили

4) из второго условия, , при и получаем .

Дублирует задание

Ответ: 1000

Укажите значения логических переменных Р, Q, S, Т, при которых логическое выражение

(Р ∨ ¬Q) ∨ (Q → (S ∨ Т)) ложно.

Ответ запишите в виде строки из четырех символов: значений переменных Р, Q, S, T (в указанном порядке).

Решение.

(1) (Р ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (Р ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Применим преобразование импликации:

¬Q ∨ S ∨ Т = 0 => S = 0, T = 0.

Ответ: 0100

Укажите значения переменных K, L, M, N, при которых логическое выражение

(K → M) ∨ (L ∧ K) ∨ ¬N

Решение.

Логическое "ИЛИ" ложно тогда и только тогда, когда ложны оба утверждения.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Применим преобразование импликации для первого выражения:

¬K ∨ M = 0 => K = 1, M = 0.

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

(L ∧ K) ∨ ¬N = 0 (см. результат первого выражения) => L ∨ ¬N = 0 => L = 0, N = 1.

Ответ: 1001.

Ответ: 1001

Укажите значения переменных K, L, M, N, при которых логическое выражение

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

истинно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Решение.

Логическое "И" истинно тогда и только тогда, когда истинны оба утверждения.

1) (K → M) = 1 Применим преобразование импликации: ¬K ∨ M = 1

2) (K → ¬M) = 1 Применим преобразование импликации: ¬K ∨ ¬M = 1

Отсюда следует, что K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Применим преобразование импликации: K ∨ (M ∧ ¬L ∧ N) = 1 из того что K = 0 получаем.

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

Задача: Решить систему логических уравнений:

Решение 1: Применяем инверсию к обеим частям первого уравнения:

Представим импликацию через базовые операции «ИЛИ», «НЕ»:

Раскрываем первую скобку по закону де Моргана и преобразовываем полученный результат:

Полученное уравнение, имеет одно решение: A =0, B=0 и C=1.

Решение 2: Составим таблицу истинности для системы:








0	0	1	1	0	1

Полужирным выделена строчка, для которой выполняются условия задачи. Таким образом, A=0, B=0 и C=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.

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

Приведенная система уравнений равносильна уравнению:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m ) = 1.

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

	Дерево	Количество решений
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)*

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

Образовательная – изучение способов решения логических уравнений, формирование умений и навыков решения логических уравнений и построения логического выражения по таблице истинности;

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

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

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

Оборудование: компьютер, мультимедийный проектор, презентация 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 минут)

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

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

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

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

А	В	С					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

А	В	С					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

А	В	С					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1