Методы решения логических уравнений сообщение
Обновлено: 19.05.2024
Большое количество задач ЕГЭ посвящено логике высказываний. Для решения большинства из них достаточно знания основных законов логики высказываний, знания таблиц истинности логических функций одной и двух переменных. Приведу основные законы логики высказываний.
- Коммутативность дизъюнкции и конъюнкции:
a ˅ b ≡ b ˅ a
a ^ b ≡ b ^ a - Дистрибутивный закон относительно дизъюнкции и конъюнкции:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ с) ≡ (a ^ b) ˅ (a ^ с) - Отрицание отрицания:
¬(¬а) ≡ а - Непротиворечивость:
a ^ ¬а ≡ false - Исключающее третье:
a ˅ ¬а ≡ true - Законы де-Моргана:
¬(а ˅ b) ≡ ¬а ˄ ¬b
¬(а ˄ b) ≡ ¬а ˅ ¬b - Упрощение:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ true ≡ a
a ˄ false ≡ false - Поглощение:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a - Замена импликации
a → b ≡ ¬a ˅ b - Замена тождества
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)
Представление логических функций
Любую логическую функцию от n переменных – F(x1, x2, … xn) можно задать таблицей истинности. Такая таблица содержит 2 n наборов переменных, для каждого из которых задается значение функции на этом наборе. Такой способ хорош, когда число переменных относительно невелико. Уже при n > 5 представление становится плохо обозримым.
Другой способ состоит в том, чтобы задавать функцию некоторой формулой, используя известные достаточно простые функции. Система функций 1, f2, … fk> называется полной, если любую логическую функцию можно выразить формулой, содержащей только функции fi.
Полной является система функций . Законы 9 и 10 являются примерами, демонстрирующими, как импликация и тождество выражается через отрицание, конъюнкцию и дизъюнкцию.
Фактически полной является и система из двух функций – отрицания и конъюнкции или отрицания и дизъюнкции. Из законов де-Моргана следуют представления, позволяющие выразить конъюнкцию через отрицание и дизъюнкцию и соответственно выразить дизъюнкцию через отрицание и конъюнкцию:
(а ˅ b) ≡ ¬(¬а ˄ ¬b)
(а ˄ b) ≡ ¬(¬а ˅ ¬b)
Парадоксально, но полной является система, состоящая всего из одной функции. Существуют две бинарные функции – антиконънкция и антидизъюнкция, называемые стрелкой Пирса и штрих Шеффера, представляющие полую систему.
В состав базовых функций языков программирования включают обычно тождество, отрицание, конъюнкцию и дизъюнкцию. В задачах ЕГЭ наряду с этими функциями часто встречается импликация.
Рассмотрим несколько простых задач, связанных с логическими функциями.
Дан фрагмент таблицы истинности. Какая из трех приведенных функций соответствует этому фрагменту?
Функция под номером 3.
Для решения задачи нужно знать таблицы истинности базовых функций и помнить о приоритетах операций. Напомню, что конъюнкция (логическое умножение) имеет более высокий приоритет и выполняется раньше, чем дизъюнкция (логическое сложение). При вычислениях нетрудно заметить, что функции с номерами 1 и 2 на третьем наборе имеют значение 1 и уже по этой причине фрагменту не соответствуют.
Какое из приведенных чисел удовлетворяет условию:
(цифры, начиная со старшего разряда, идут в порядке убывания) → (число — четное) ˄ (младшая цифра – четная) ˄ (старшая цифра – нечетная)
Если таких чисел несколько, укажите наибольшее.
Условию удовлетворяет число под номером 4.
Первые два числа условию не удовлетворяют уже по той причине, что младшая цифра является нечетной. Конъюнкция условий ложна, если один из членов конъюнкции ложен. Для третьего числа не выполняется условие для старшей цифры. Для четвертого числа выполняются условия, накладываемые на младшую и старшую цифры числа. Первый член конъюнкции также истинен, поскольку импликация истинна, если ее посылка ложна, что имеет место в данном случае.
Задача 17: Два свидетеля дали следующие показания:
Первый свидетель: Если А виновен, то В и подавно виновен, а С – невиновен.
Второй свидетель: Виновны двое. А точно виновен и виновен один из оставшихся, но кто именно сказать не могу.
Какие заключения о виновности А, В и С можно сделать на основании свидетельских показаний?
Ответ: Из свидетельских показаний следует, что А и В виновны, а С – невиновен.
Решение: Конечно, ответ можно дать, основываясь на здравом смысле. Но давайте рассмотрим, как это можно сделать строго и формально.
Первое, что нужно сделать – это формализовать высказывания. Введем три логические переменные — А, В и С, каждая из которых имеет значение true (1), если соответствующий подозреваемый виновен. Тогда показания первого свидетеля задаются формулой:
Показания второго свидетеля задаются формулой:
Показания обоих свидетелей полагаются истинными и представляют конъюнкцию соответствующих формул.
Построим таблицу истинности для этих показаний:
| A | B | C | F1 | F2 | F1 ˄ F2 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
Суммарные свидетельские показания истинны только в одном случае, приводящие к однозначному ответу – А и В виновны, а С – невиновен.
Из анализа этой таблицы также следует, что показания второго свидетеля более информативны. Из истинности его показания следует только два возможных варианта — А и В виновны, а С – невиновен или А и С виновны, а В – невиновен. Показания первого свидетеля менее информативны – существует 5 различных вариантов, соответствующих его показаниям. Совместно показания обоих свидетелей дают однозначный ответ о виновности подозреваемых.
Логические уравнения и системы уравнений
Пусть F(x1, x2, …xn) – логическая функция от n переменных. Логическое уравнение имеет вид:
Константа С имеет значение 1 или 0.
Логическое уравнение может иметь от 0 до 2 n различных решений. Если С равно 1, то решениями являются все те наборы переменных из таблицы истинности, на которых функция F принимает значение истина (1). Оставшиеся наборы являются решениями уравнения при C, равном нулю. Можно всегда рассматривать только уравнения вида:
Действительно, пусть задано уравнение:
В этом случае можно перейти к эквивалентному уравнению:
Рассмотрим систему из k логических уравнений:
Решением системы является набор переменных, на котором выполняются все уравнения системы. В терминах логических функций для получения решения системы логических уравнений следует найти набор, на котором истинна логическая функция Ф, представляющая конъюнкцию исходных функций F:
Если число переменных невелико, например, менее 5, то нетрудно построить таблицу истинности для функции Ф, что позволяет сказать, сколько решений имеет система и каковы наборы, дающие решения.
В некоторых задачах ЕГЭ по нахождению решений системы логических уравнений число переменных доходит до значения 10. Тогда построить таблицу истинности становится практически неразрешимой задачей. Для решения задачи требуется другой подход. Для произвольной системы уравнений не существует общего способа, отличного от перебора, позволяющего решать такие задачи.
В предлагаемых на экзамене задачах решение обычно основано на учете специфики системы уравнений. Повторяю, кроме перебора всех вариантов набора переменных, общего способа решения задачи нет. Решение нужно строить исходя из специфики системы. Часто полезно провести предварительное упрощение системы уравнений, используя известные законы логики. Другой полезный прием решения этой задачи состоит в следующем. Нам интересны не все наборы, а только те, на которых функция Ф имеет значение 1. Вместо построения полной таблицы истинности будем строить ее аналог — бинарное дерево решений. Каждая ветвь этого дерева соответствует одному решению и задает набор, на котором функция Ф имеет значение 1. Число ветвей в дереве решений совпадает с числом решений системы уравнений.
Что такое бинарное дерево решений и как оно строится, поясню на примерах нескольких задач.
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют системе из двух уравнений?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5 ) = 1
Ответ: Система имеет 36 различных решений.
Решение: Система уравнений включает два уравнения. Найдем число решений для первого уравнения, зависящего от 5 переменных – x1, x2, …x5. Первое уравнение можно в свою очередь рассматривать как систему из 5 уравнений. Как было показано, система уравнений фактически представляет конъюнкцию логических функций. Справедливо и обратное утверждение, — конъюнкцию условий можно рассматривать как систему уравнений.
Построим дерево решений для импликации (x1→ x2) — первого члена конъюнкции, который можно рассматривать как первое уравнение. Вот как выглядит графическое изображение этого дерева:
Дерево состоит из двух уровней по числу переменных уравнения. Первый уровень описывает первую переменную X1. Две ветви этого уровня отражают возможные значения этой переменной – 1 и 0. На втором уровне ветви дерева отражают только те возможные значения переменной X2, для которых уравнение принимает значение истина. Поскольку уравнение задает импликацию, то ветвь, на которой X1 имеет значение 1, требует, чтобы на этой ветви X2 имело значение 1. Ветвь, на которой X1 имеет значение 0, порождает две ветви со значениями X2, равными 0 и 1. Построенное дерево задает три решения, на которых импликация X1 → X2 принимает значение 1. На каждой ветви выписан соответствующий набор значений переменных, дающий решение уравнения.
Продолжим построение дерева решений, добавляя следующее уравнение, следующую импликацию X2 → X3. Специфика нашей системы уравнений в том, что каждое новое уравнение системы использует одну переменную из предыдущего уравнения, добавляя одну новую переменную. Поскольку переменная X2 уже имеет значения на дереве, то на всех ветвях, где переменная X2 имеет значение 1, переменная X3 также будет иметь значение 1. Для таких ветвей построение дерева продолжается на следующий уровень, но новые ветви не появляются. Единственная ветвь, где переменная X2 имеет значение 0, даст разветвление на две ветви, где переменная X3 получит значения 0 и 1. Таким образом, каждое добавление нового уравнения, учитывая его специфику, добавляет одно решение. Исходное первое уравнение:
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1
имеет 6 решений. Вот как выглядит полное дерево решений для этого уравнения:
Второе уравнение нашей системы аналогично первому:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
Разница лишь в том, что в уравнении используются переменные Y. Это уравнение также имеет 6 решений. Поскольку каждое решение для переменных Xi может быть скомбинировано с каждым решением для переменных Yj, то общее число решений равно 36.
Заметьте, построенное дерево решений дает не только число решений (по числу ветвей), но и сами решения, выписанные на каждой ветви дерева.
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5 ) = 1
(x1→y1) = 1
Эта задача является модификацией предыдущей задачи. Разница в том, что добавляется еще одно уравнение, связывающее переменные X и Y.
Из уравнения X1 → Y1 следует, что когда X1 имеет значение 1(одно такое решение существует), то и Y1 имеет значение 1. Таким образом, существует один набор, на котором X1 и Y1 имеют значения 1. При X1, равном 0, Y1 может иметь любое значение, как 0, так и 1. Поэтому каждому набору с X1, равном 0, а таких наборов 5, соответствует все 6 наборов с переменными Y. Следовательно, общее число решений равно 31.
Сколько решений имеет уравнение:
Решение: Вспоминания основные эквивалентности, запишем наше уравнение в виде:
Циклическая цепочка импликаций означает тождественность переменных, так что наше уравнение эквивалентно уравнению:
Это уравнение имеет два решения, когда все Xi равны либо 1, либо 0.
Сколько решений имеет уравнение:
Решение: Так же, как и в задаче 20, от циклических импликаций перейдем к тождествам, переписав уравнение в виде:
Построим дерево решений для этого уравнения:
Сколько решений имеет следующая система уравнений?
Решение: Перейдем от 10 переменных к 5 переменным, введя следующую замену переменных:
Тогда первое уравнение примет вид:
Уравнение можно упростить, записав его в виде:
Переходя к традиционной форме, запишем систему после упрощений в виде:
Дерево решений для этой системы простое и состоит из двух ветвей с чередующимися значениями переменных:
Возвращаясь к исходным переменным X, заметим, что каждому значению переменной Y соответствует 2 значения переменных X, поэтому каждое решение в переменных Yпорождает 2 5 решений в переменных X. Две ветви порождают 2 * 2 5 решений, так что общее число решений равно 64.
Как видите, каждая задача на решение системы уравнений требует своего подхода. Общим приемом является выполнение эквивалентных преобразований для упрощения уравнений. Общим приемом является и построение деревьев решений. Применяемый подход частично напоминает построение таблицы истинности с той особенностью, что строятся не все наборы возможных значений переменных, а лишь те, на которых функция принимает значение 1 (истина). Часто в предлагаемых задачах нет необходимости в построении полного дерева решений, поскольку уже на начальном этапе удается установить закономерность появления новых ветвей на каждом следующем уровне, как это сделано, например, в задаче 18.
В целом задачи на нахождение решений системы логических уравнений являются хорошими математическими упражнениями.
Если задачу трудно решить вручную, то можно поручить решение задачи компьютеру, написав соответствующую программу решения уравнений и систем уравнений.
Написать такую программу несложно. Такая программа легко справится со всеми задачами, предлагаемыми в ЕГЭ.
Написать программу для решения логических уравнений полезно по многим причинам, хотя бы потому, что с ее помощью можно проверять правильность собственного решения тестовых задач ЕГЭ. Другая причина в том, что такая программа является прекрасным примером задачи на программирование, соответствующей требованиям, предъявляемым к задачам категории С в ЕГЭ.
В такой программе нужно построить цикл по числу наборов, в теле цикла по номеру набора сформировать сам набор, вычислить значение функции на этом наборе, и если это значение равно 1, то набор дает решение уравнения.
Единственная сложность, возникающая при реализации программы, связана с задачей формирования по номеру набора самого набора значений переменных. Красота этой задачи в том, что эта, казалось бы, трудная задача, фактически сводится к простой, уже неоднократно возникавшей задаче. Действительно, достаточно понять, что соответствующий числу i набор значений переменных, состоящий из нулей и единиц, представляет двоичную запись числа i. Так что сложная задача получения набора значений переменных по номеру набора сводится к хорошо знакомой задаче перевода числа в двоичную систему.
Можно выделить различные способы решения систем логических уравнений. Это сведение к одному уравнению, построение таблицы истинности и декомпозиция.
Задача: Решить систему логических уравнений:
Решение 1: Применяем инверсию к обеим частям первого уравнения:
Поскольку левые части уравнений равны 1, можно объединить их с помощью операции “И” в одно уравнение, равносильное исходной системе:
Раскрываем первую скобку по закону де Моргана и преобразовываем полученный результат:
Полученное уравнение, имеет одно решение: A =0, B=0 и C=1.
Следующий способ – построение таблиц истинности. Поскольку логические величины имеют только два значения, можно просто перебрать все варианты и найти среди них те, при которых выполняется данная система уравнений. То есть, мы строим одну общую таблицу истинности для всех уравнений системы и находим строку с нужными значениями.
Решение 2: Составим таблицу истинности для системы:
Полужирным выделена строчка, для которой выполняются условия задачи. Таким образом, A=0, B=0 и C=1.
Способ декомпозиции. Идея состоит в том, чтобы зафиксировать значение одной из переменных (положить ее равной 0 или 1) и за счет этого упростить уравнения. Затем можно зафиксировать значение второй переменной и т.д.
Решение 3: Пусть A = 0, тогда:
Из первого уравнения получаем B =0, а из второго – С=1. Решение системы: A = 0, B = 0 и C = 1.
В ЕГЭ по информатике очень часто требуется определить количество решений системы логических уравнений, без нахождения самих решений, для этого тоже существуют определенные методы. Основной способ нахождения количества решений системы логических уравнений – замена переменных . Сначала необходимо максимально упростить каждое из уравнений на основе законов алгебры логики, а затем заменить сложные части уравнений новыми переменными и определить количество решений новой системы. Далее вернуться к замене и определить для нее количество решений.
Задача: Сколько решений имеет уравнение ( A → B ) + ( C → D ) = 1? Где A, B, C, D – логические переменные.
Решение: Введем новые переменные: X = A → B и Y = C → D . С учетом новых переменных уравнение запишется в виде: X + Y = 1.
Дизъюнкция верна в трех случаях: (0;1), (1;0) и (1;1), при этом X и Y является импликацией, то есть является истинной в трех случаях и ложной – в одном. Поэтому случай (0;1) будет соответствовать трем возможным сочетаниям параметров. Случай (1;1) – будет соответствовать девяти возможным сочетаниям параметров исходного уравнения. Значит, всего возможных решений данного уравнения 3+9=15.
Следующий способ определения количества решений системы логических уравнений – бинарное дерево. Рассмотрим данный метод на примере.
Задача: Сколько различных решений имеет система логических уравнений:
Приведенная система уравнений равносильна уравнению:
( x 1 → x 2)*( x 2 → x 3)*…*( xm -1 → xm ) = 1.
Предположим, что x 1 – истинно, тогда из первого уравнения получаем, что x 2 также истинно, из второго - x 3=1, и так далее до xm = 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 значений переменных):
Такой подход хорошо иллюстрируется с помощью построения бинарного дерева. Количество возможных решений – количество различных ветвей построенного дерева. Легко заметить, что оно равно m +1.
Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной.
Сколько существует различных наборов значений логических переменных x1, х2, х3, х4, х5, х6, х7, х8, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → х2) → (х3→ х4) = 1
(х3 → х4) → (х5 → х6) = 1
(х5 → х6) → (х7 → х8) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, х2, х3, х4, х5, х6, х7, х8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Сделаем замену переменных:
(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = y4.
Тогда можно записать систему в виде одного уравнения:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конъюнкция равна 1 (истинна), когда каждый операнд принимает значение 1. Т.е. каждая из импликаций должна быть истинна, а это выполняется при всех значениях, кроме (1 → 0). Т.е. в таблице значений переменных y1, y2, y3, y4 единица не должна стоять левее нуля:
Т.е. условия выполняются для 5 наборов y1-y4.
Т.к. y1 = x1 → x2, то значение y1 = 0 достигается на единственном наборе x1, x2: (1, 0), а значение y1 = 1 – на трех наборах x1, x2: (0,0) , (0,1), (1,1). Аналогично для y2, y3, y4.
Поскольку каждый набор (x1,x2) для переменной y1 сочетается с каждым набором (x3,x4) для переменной y2 и т.д., то количества наборов переменных x перемножаются:
Кол-во наборов на x1…x8
Сложим количество наборов: 1 + 3 + 9 + 27 + 81 = 121.
Сколько существует различных наборов значений логических переменных x1, x2, . x9, y1, y2, . y9, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, . x9, y1, y2, . y9, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Сделаем замену переменных:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Систему можно записать в виде одного уравнения:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Т.к. zi = (xi ≡ yi), то значению zi = 0 соответствуют два набора (xi,yi): (0,1) и (1,0), а значению zi = 1 - два набора (xi,yi): (0,0) и (1,1).
Тогда первому набору z1, z2,…, z9 соответствует 2 9 наборов (x1,y1), (x2,y2),…, (x9,y9).
Столько же соответствует второму набору z1, z2,…, z9. Тогда всего 2 9 +2 9 = 1024 наборов.
Решение систем логических уравнений методом визуального определения рекурсии.
Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.
Сколько различных решений имеет система уравнений
где x1, x2, … x10 — логические переменные?
В ответе не нужно перечислять все различные наборы значений x1, x2, … x10, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Решим первое уравнение. Дизъюнкция равна 1, если хотя бы один из ее операндов равен 1. Т.е. решениями являются наборы:
Для x1=0 существуют два значения x2 ( 0 и 1), а для x1=1 только одно значение x2 (1), такие, что набор (x1,x2) является решением уравнения. Всего 3 набора.
Добавим переменную x3 и рассмотрим второе уравнение. Оно аналогично первому, значит для x2=0 существуют два значения x3 ( 0 и 1), а для x2=1 только одно значение x3 (1), такие, что набор (x2,x3) является решением уравнения. Всего 4 набора.
Несложно заметить, что при добавлении очередной переменной добавляется один набор. Т.е. рекурсивная формула количества наборов на (i+1) переменных:
Ni+1 = Ni + 1. Тогда для десяти переменных получим 11 наборов.
Решение систем логических уравнений различного типа
Сколько существует различных наборов значений логических переменных x1, . x4, y1. y4, z1. z4, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, . x4, y1, . y4, z1, . z4, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.
Заметим, что три уравнения системы одинаковы на различных независимых наборах переменных.
Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):
¬ (А = B) /\ ((A B)→(B C)) /\ ((B A)→(С B)). Чему равно В, если A = 45 и C = 43?
Обр вн, что это сложное выск состоит из трех простых
1) ¬(А = B); (A B)→(B C); (B A)→(С B)
2) эти простые выск связаны оп ∧ (И, конъюнкw), т е, они д вып одновременно
3) из ¬(А = B)=1 сразу следует, что А B
4) предп, что A B, тогда из 2 усл 1→(B C)=1; это выр м б истин только тогда, когда B C = 1
5) поэтому имеем A B C, этому условию соотв только число 44
6) на всякий сл пров и вар A C)=1;это выр истинно при любом B; теперь см 3 усл получ 1→(С B)=1;это выр м б истинно тогда и только тогда, когда C B, и тут мы получ противор, потому что нет такого числа B, для кот C B A.
B15 № 2210. Изв, что для X, Y и Z ист выск (Z Чему равно Z, если X=25 и Y=48?
3)A,B,C – целые , для кот истинно высказывание
Чему равно B, если A=45, C=18 отв B=18
Чему равно А, если B=16, C=7 отв A=15
Чему равно A, если C = 8 и B = 18?.
Чему равно C, если A=45 и B=18?
Каково наибольшее целое положите X, при кот высказывание
(X(X + 1) 55) → (X · X 50)
B15 № 2206. Сост табл ист для логич фу X = (А ↔ B) \/ ¬(A → (B \/ C)) в кот столбец зн арг А предст двоич запись числа 27, столбец зн арг В — числа 77, ст-ц зн арг С — числа 120. Число в столбце запис сверху вниз от ст разряда к младш. Перев получ двоич запись зн ф X в 10-чн систему счисления.
Решение 1 уравнения
Укажите зн перем, при кот логическое выр- ложно Ответ запиш в виде строки из 4 симв: зн перем К, L, М и N (в указ порядке). Так, н, строка 1101 соотв тому, что К=1, L=1, M=0, N=1.
А) (¬(М ∨ L) ∧ К) → (¬К ∧ ¬М ∨ N) б) (¬K ∨ M) → (¬L ∨ M ∨ N)
в) (¬(M ∨ L) ∧ K) →((¬K ∧ ¬M) ∨ N) г) (Р ∨ ¬Q) ∨ (Q → (S∨Т)) д) (K → M) ∨ (L ∧ K) ∨ ¬N
Укажите зн перем, при кот логическое выр-е истинно
А) (K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
А)
б)
б) ¬((J → K) → (L ∧ M ∧ N)) ∨ ¬((L ∧ M ∧ N) → (¬J ∨ K)) ∨ (M ∧ J) = 0
В) ((K ∨ L) → (L ∧M ∧ N))=0 г) (K ∧ L) ∨ (M ∧ N)=1 д) (X ∧ Y ∨ Z) → (Z ∨ P) = 0
и) (¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0 е) (X ∨ Y ∨ Z) → (X ∧ P) = 1
ж) (K ∨ L) ∧ (M ∨ N) = 1 з) ((A → B)∧ C) ∨ (D ∧ ¬D)= 1,
Системы логических уравнений
Способ 1. Сведение к одному уравнению
преобр ур так, чтоб пр ч = 1 (истинно). Для этого применим инверсию
предст импликацию и “исклИЛИ” через базовые оп (“И”, “ИЛИ”, “НЕ”)
и можно объед их с пом оп “И” в одно уравнение,
единств реш: A =1, B=0 и C=1.
Метод таблиц истинности
Недостаток метода — трудоемкость при большом кол перем ( 4)
0) 1)Кто из подозреваемых участвовал в преступлении, если известно:
1) если Иванов не участвовал или Петров участвовал, то Сидоров участвовал;
2) если Иванов не участвовал, то Сидоров не участвовал.
Реш. И - Иванов участв в преступл; П - Петров участв\ в преступл; С - Сидоров участв в преступ.
Соед оба утв в 1 выск:
Составим таблицу истинности на полученное высказывание:
видим, что только у Иванова в получ строках "ИСТИНА" совп с его участ в прес. Зн он и есть преступ.
Способ 3. Декомпозиция
Идея чтобы зафикс зн одной из перем (полож ее= 0 или 1) и за счет этого упростить уравн. Затем м зафикс зн 2 перем и т.д
А)при A =0 получаем импликац ложна только в 1
сл — когда посылка истинна, а следствие ложно система реш не имеет
б) A =1 Из 1 ура в силу свойств импликац следует,
из 2-го т к означ что т е реш
Метод Преобразования уравнений
пр1 Найти единств решение системы логических уравнений
Отв запиш в виде строки из 4 симв: зн пер A, B, C, D (в указ пор). Т, н, строка 1101 соотв тому, что А = 1, В = 1, С = 0, D = 1. Реш упрощ 1 ур с-мы л ч
Преобр 2 ур смы: итак
или откуда C=1 Тогда из 1 ур B=1
Пр2)Определить, кто из четырех студентов сдал экзамен, если известно, что:
а) если 1й сдал, то и 2й сдал;б) если 2й сдал, то 3й сдал или 1й не сдал;
в) если 4й не сдал, то 1й сдал, а 3й не сдал;г) если 4й сдал, то и 1й сдал
A — 1й студ сдал B — «2й с сдал C — 3й сдал E — 4й сдал
экз сдали все 4 студ
пр) какой корабль вышел в море если
А)Неверно, что если корабль A вышел в море, то корабль C — нет.
(б). В море вышел корабль B или корабль C, но не оба вместе.
. Реш. A — “корабль A вышел в море”,B — “корабль B вышел в море”,C — “корабл C вышел в море”.
Способ 1. Сведение к 1 уравнению.
преобр уравнения так, что правые части= 1 (истинн зн). Для этого
примен инверсию “НЕ”) к обеим частям 1 ур:
Теперь предст импликац и “искл ИЛИ” через баз оп (“И”, “ИЛИ “НЕ”):
объед уравн с пом оп “И” в 1 уравн
Раскр инверс в 1 скоб по зак Моргана и внос сомн A в скобку
Последнее ур, равносильн исх системе, имеет единств реш: A=1, B=0 и C=1.
Способ 4. Последовательное решение уравнений дерево решений
В нек сл м решать ур последоват, на каждом шаге доб по 1 перем в рассм набор.
1-е ур 2 пары (A=0,B=1) и (A=1,B=0)
Подкл 2ур из кот н опред доп знач C
При A =0 импликац не м б ложна, т е 1 строка предыд табл не дает ни 1 реш смы 2 уравн
При A =1 единственное реш, для кот C=1:
Задачи на решение с-мы уравнений
1)(x1 → х2) ∧ (х2 →хЗ) ∧ (хЗ → х4) ∧ (х4 → х5 )=1
(y1 → y2) ∧ (у2→уЗ) ∧ (уЗ →у4) ∧ (у4 → у5 )=1
Задачи на кол-во решений с-мы уравнений
возм решать противоп задачу, определив общее число наборов,
в з-ти от необх превр в конъюнк = 1 или дизъюнкцию = 0
разбить на систему согл табл истин описать наборы реш для каждой части системы
по возможности выбрать ту, где меньше решений
посмотреть какие реш совп, т.е. протестир решения одной части для др части
выкинуть из 2 части то, что не явл реш первой части.
для системы из 2 легко восп формулой колич пересечений.
иногда до легко подсч комб по их плу образ", иногда нагл и проще выпис их списком (если это в предел десятка)
Пр1)Ск разл реш имеет ур: (X\/Y\/Z)=(X/\P)=1, где X, Y, Z, P — логич переменные?
Это ур имеет последнюю оп импликацию, реш которой м б такие варианты:
1 ур вып при одновр вып усл: X=0, Y=0, Z=0
2 ур вып при любом зн P, т к X=0 из 1го уравн.
1 вар решения для перем XYZ (000) и нет вар реш для 2го уравн, т к при X=0X/\P не будет никогда равно 1.
нач решать со 2 ур, т к оно имеет всего 1 вар реш:X=1 и P=1.
При X=1 1е ур б всегда иметь реш. И ск таких вар ? Так там, кр перем X, исп еще 2 перем (Y и Z), кот дают 4 разных вар сочетан. То получ 1*4=4 вар реш
Итого, для всего исходного уравнения получаем 2+4=6 решений.
Пр2.Сколько разл реш имеет уравн ((J→K)→(M \N/\L)) /\ ((J/\¬K)→¬(M /\ N /\ L))/\(M→J)=1,
Реш. Сначала преобразуем: (JΛ¬K) → ¬(MΛNΛL).
(JΛ¬K) → ¬(M Λ N Λ L)=¬(¬JVK)→ ¬(M Λ N Λ L)-вынесли отрицание за скобки
замену: (J → K)=P (M Λ N Λ L)=Q Получ : (P→Q) Λ (¬P→¬Q) это лог оп эквиваленц:P↔Q.
Проведем обратную замену:P↔Q=(J → K)↔(M Λ N Λ L).
Выпишем ур с учетом преобр:((J → K)↔(M Λ N Λ L)) Λ (M → J) = 1.
Ур= 1,когда (J → K)↔(M Λ N Λ L)=1 и (M → J)=1-логич умн дает 1,когда оба лог операнда равны 1.
(J → K)↔(M Λ N Λ L) дает 2 решения:
и Получ 2 с-мы ур: и
1-я имеет 1 реш. 2-я 7 реш всего 8 реш
1.Ск разл реш имеет уравн где A,B,C,D,E или J K L M N –логич перем. В отв не перечисл все разл наборы зн А, В, С, D, Е, явл реш, а только указать кол таких наборов
В отв не н перечис все разл наборы зн перем x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при кот вып данная система равенств. В кач отв н указать количество таких наборов.
Проверим, явл ли найд зн решен 2 уравнения
В ответе не н перечисл все разл наборы знач x1, x2, . x9, x10, при кот вып данн система Ответ: 64
B15. Ск сущ разл наборов зн логич перем x1,x2,x3,x4,y1,y2,y3,y4, удовл всем перечисл ниже усло?
А) (x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1
(¬y1 \/ y2) /\ (¬y2 \/ y3) /\ (¬y3 \/ y4) = 1
(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1 отв 15
1. Сколько решений имеет система уравнений:
(A E) (B D) = B B C (E B C D), отв 5
В отв не н перечисл все разл наборы зн А, В, С, D, Е, явл реш, а только указ кол таких наборов.
2. Укаж зн пер А, В, С, D, при кот лв (А С) (А (В D)) ложно. Отв запиш в виде строки из 4 симв: зн перем A, B, C, D (в указ поряд). Т, н, строка 1101 соотв, А = 1, В = 1, С = 0, D = 1. Отв 0110
B15 № 2201. Ск разл реш имеет ур J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, где J, K, L, M, N — логиче перем? В отв не н перечис все разл наборы зн J, K, L, M и N, при кот вып данное рав В кач ответа н указать кол таких наборов.
Сколько различных решений имеет уравнение
Метод построения бинарного дерева решений
1а)Сколько разл реш имеет система логич ур:а) б)
1а)_Получив одну 1, все ост зн перем также стан 1, получив же 0, возм два вар: 0 и 1. Для одного ур дерево состоит из 2 уровней, для 2 ур доб одна перем и соотв один уровень дерева. Кол возм реш – кол разл ветвей постр дерева. Легко видеть, что оно равно m+1 На рис дерево на 5 уровней.
Реш. замена:(x1 ≡ x2)=y1 (x3 ≡ x4)=y2 (x5 ≡ x6)=y3 (x7 ≡ x8)=y4 (x9 ≡ x10)=y5
это инверсия эквиваленции: имеет 2 реш:y1=1,y2=0 или y1=0,y2=1.
Решим с-му из 2 уравн: и заменим одним
или по з-ну двойств вып, только когда и
пусть получаем пусть получаем т.е 2 реш
при доб 1 ур к самому 1му ур не меняется число реш=2. След, доб ост ур не изм общее кол реш=2
Теперь перейдем к поиску кол реш, исп обр подст для y. : y1 =(x1 ≡ x2) для каждого из зн y1 есть 2 реш. Анал и для ост:y3,y4,y5. Пары реш (x1,x2),(x3,x4),(x5,x6),(x7,x8),(x9,x10) - не зависят др от др, поэтому комб реш р 2 5 =32. не учли, что и y1,y2,y3,y4,y5 дают в 2 р больше реш. Общ кол реш: 32*2=64 реш.
1б) похожая з-ча при m=2 – 5 реш ,при m=3 – 8 решений пусть - кол решений при k уравн
-кол решений при x1=0, -кол реш при x1=1, тогда где
- число Фибоначчи. при n=7 при n=10
Прим1. Сколько различных реш имеет система уравн: где X1-X10 — логич перем?
В отв не н перечисл все разл наборы знач X1, X2, X3, …, X10, при кот вып данная с-ма ур. нужно указать количество таких наборов.
Реш.прив ур к б удобн виду. В частн, в 1й скобке кажд ур нах лв, равносильн эквивал. Во 2й скобке нах логич выр, равносиль искл или. Заменив выр в первых скобках на эквивал, а во 2х на искл или получим:
(X1≡ X2) +(X2 X3) = 1
(X2 ≡ X3) +(X3 X4) = 1
(X3 ≡ X4) _(X4 X5) = 1
(X8 ≡X9) +(X9 X10) = 1
X1 =0 X10= 0
Дальн реш построим на принципе рассужд и постр дерева решения. По условию X1= 0
Пусть X2 = 1.Тогда 1е усл 1го уравн не вып (Xl≡X2) и тогда д вып 2е усл 1го ур (X2 X3), т е, X3 = 0. Тогда получ, что X2 X3 (не вып 1е усл 2го уравн), значит, д вып 2е условие 2го уравн X3 X4, Зн, X4 = 1. Анал рассуждая, получ, что знач последую перем д чередоваться:
Х5 = 0, Х6 = 1, Х7 = 0, Х8 = 1, Х9 = 0, Х10 = 1. Эта ветка рассужд (X2 = 1) привела нас к единств реш, но оно нам не подходит, т к мы получ Х10 = 1, а по усл задачи Х10 = 0. (Правая ветка дерева).
Пусть X2 = 0. Тогда 1е усл 1го уравн вып (Xl≡X2). Это зн, что 2е усл 1го уравн (X2 X3), не обязат д выполняться. То есть, X3 может быть любым.
Пусть X3= 1. Тогда 1е усл 2го ур (X2 X3) не вып. Зн, д вып 2е усл 2го ур (X3 X4), т е, Х4 = 0. Ситуация анал уже рассм нами для X2 = 1 — зн послед перем д чередоваться:
Х5 = 1, Х6 = 0, Х7 = 1, Х8 = 0, Х9 = 1, Х10 = 0. Это одно их решений.
Пусть X3=0. Тогда 1е усл 2го ур вып (X2 ≡ X3), это з, что 2е усл 2го ур (X3 X4) не обязат д вып. То есть, X4 может быть любым. Мы пришли к. повторяющ ситуации. Для каждой послед перем если она будет = 1, это б давать единств реш, а если 0, то н будет рассм 2 вар зн след перем. Всего б иметь 10 реш, но 5 из них нам не подх, так какХ10 = 1.Представим дерево решений:
Прим2 Рассм следующ систему уравн. Она отличается от предыдущей последним уравнением.
Сколько различных решений имеет система уравнений:
где X1, X2, X3, …, X10 — логич перем?
Реш. Необх рассм две ситуации: X1 = 0 и X1 = 1.
При X1 = 0 реш будет такое же, как в предыдущей задаче. Дерево решений то же
При выборе реш н учесть, что X1 ≡ X10= 0 вып, когда X1 и X10 имеют разные зн. Поэтому при X1 =0 выбир X10= 1.Решений будет 5. Столько же решений будет при X1 =1.
Всего решений будет 10. Ответ: 10.
Задачи на дерево решений
B15 № 3822. Сколько сущ разл наборов зн логич перем x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовл всем перечис ниже условиям?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5 ) = 1
x1\/y1 =1
B15 № 3854. Сколько сущ разл наборов зн лог перем x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовл всем перечисл ниже условиям?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1
(y5→y4) /\ (y4→y3) /\ (y3→y2) /\ (y2→y1 ) = 1
x3/\y3 =1
В15-2012 Сколько существ разл наборов зн логич перем x1,x2, . x9, x10, кот удовл системе?
((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) =1
((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) =1
.
((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) =1
В ответе не н перечисл все разл наборы зн x1, x2, . x9, x10, при кот выполн данная система
РЕШЕНИЕ СИСТЕМ УРАВНЕНИЙ Метод Сеток
метод прозрачных таблиц (метод сеток) – аналог графич способа для реш алгебраич систем, кот позво быстро решать с-му уравн, содерж не более 4 перем.Этот метод осн на скал произвед векторов. Систему уравнений
м записать в векторном виде:
Отлож вдоль оси ох все знач перем , а вдоль оси оу все зн вектора . Постр сетку на плоскости, прямые кот прох через указ знач и в узлах сетки выч скал произв векторов, т.е. левую часть 1 ур смы.Заполн такой табл требует врем, но она заполн быстро, т.к. в ней много закономерн. Например:
Если 2 вектора имеют на одном и том же месте коорд,= 1, то скал произв вект=1. Как следствие этого факта в табл 1 правая верхняя четверть заполнена единицами.
Если коорд одного вектора явл инверсными знач для коорд др вектора, то = 0.
Если хотя один из векторов явл нулевым, то скалярное произвед=0.
После заполн табл реш любой системы ур легко найти. Рассм метод сеток на примере.
(1;0;1) – вектор своб членов.
По оси Оу нах вектор с коорд (1;1;0). Н налож 3 таб так, чтобы строки с вект (1;1;0), (1;0;1), (0;1;1), совмест. Нах узлы со з (1;0;1). Опуск перпенд на Ох из данных узлов и видим, что сма имеет единств решения: (0;1;0), т.е. х1 = 0, х2 = 1, х3 = 0.
Зад3 (один учащ работает у доски под рук-вом учителя). Постр сетку для реш систем с 4 неизвестны.
1)Решить систему логических уравнений методом сеток
Зад 3. 6 прозрач стаканов с водой расст в 2 паралл ряда по 3 стакана в каждом. На риспредст вид спереди и вид с правой стороны. Через прозр стенки стаканов видны уровни воды в каждом стакане и во всех стаканах, стоящих за ними. Опр, сколько воды налито в каждый стакан.
По рис видно, что стаканы либо полные, либо пустые. Мн-во стаканов, кот м оказ на указ 6 местах, обр алфа, кот сост из 2 элем.Обозн пустой стакан – 0, а полный – 1. тогда мн-во сост из 0 и 1, т.е. = .Занум проекции на рис числами от 1 до 5. Занум ряды стаканов след обраи укажем эл, кот м оказ в этих рядах
Читайте также: