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