Алгебра логики как решать уравнения

Как решать уравнения алгебры логики

Это символы не жёстко привязаны к соотв. операциям, можно использовать другие.

Примеры логических выражений

С применением отрицания

Со знаком «эквивалентно»

Со знаком «следствие»

С применением конъюкции и дизъюнкции

С применением Не-и и Не-или

В калькуляторе вы сможете упростить выражения, содержащие следующие операции: NOT, XOR, AND, OR, NAND, NOR, NOT

© Контрольная работа РУ — калькуляторы онлайн

Где учитесь?

Для правильного составления решения, укажите:

Как решать уравнения алгебры логики

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

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

Рассмотрим метод сведения к одному уравнению. Данный метод предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 1). Для этого применяют операцию логического отрицания. Затем, если в уравнениях есть сложные логические операции, заменяем их базовыми: «И», «ИЛИ», «НЕ». Следующим шагом объединяем уравнения в одно, равносильное системе, с помощью логической операции «И». После этого, следует сделать преобразования полученного уравнения на основе законов алгебры логики и получить конкретное решение системы.

Решение 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 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.

Урок №6 Решение логических уравнений (10 класс)

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Выберите документ из архива для просмотра:

Выбранный для просмотра документ Урок 6 Решение логических уравнений.doc

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

Определим значения этих выражений при указанных значениях аргументов:

Ознакомление с темой урока, изложение нового материала (30 минут)

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

1. Решить логическое уравнение

Ответ запишите в виде строки из четырех символов: значений переменных 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, а .

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

Решение: преобразуем выражение

A + B =1 и C + D =1

2 способ: составление таблицы истинности

3 способ: построение СДНФ – совершенной дизъюнктивной нормальной формы для функции – дизъюнкции полных правильных элементарных конъюнкций.

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

Дополним конъюнкции до полных конъюнкций (произведение всех аргументов), раскроем скобки:

Учтем одинаковые конъюнкции:

В итоге получаем СДНФ, содержащую 9 конъюнкций. Следовательно, таблица истинности для данной функции имеет значение 1 на 9 строках из 2 4 =16 наборов значений переменных.

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

,

3 способ: построение СДНФ

Учтем одинаковые конъюнкции:

1

В итоге получаем СДНФ, содержащую 5 конъюнкций. Следовательно таблица истинности для данной функции имеет значение 1 на 5 строках из 2 4 =16 наборов значений переменных.

Построение логического выражения по таблице истинности:

для каждой строки таблицы истинности, содержащей 1 составляем произведение аргументов, причем, переменные, равные 0, входят в произведение с отрицанием, а переменные, равные 1 – без отрицания. Искомое выражение F будет составляется из суммы полученных произведений. Затем, если возможно, это выражение необходимо упростить.

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

3. Задание на дом (5 минут)

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

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

Выбранный для просмотра документ Урок 6 Решение логических уравнений.ppt

Описание презентации по отдельным слайдам:

Проверка домашнего задания: Какое из приведенных слов удовлетворяет логическому условию: (первая буква согласная→вторая буква согласная) ٨ (последняя буква гласная → предпоследняя буква гласная)? Если таких слов несколько, укажите наименьшее. 1) АННА 2) МАРИЯ 3) ОЛЕГ 4) СТЕПАН 2. Укажите, какое логическое выражение равносильно выражению 3. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? xyzF 0001 0111 1100

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

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

3. Сколько решений имеет уравнение (в ответе укажите только число)? 1 способ: рассуждения Ответ: 9 2 способ: составление таблицы истинности ABCD АВСDA+BC+DF

3 способ: построение СДНФ – совершенной дизъюнктивной нормальной формы для функции – дизъюнкции полных конъюнкций. Преобразуем исходное выражение, раскроем скобки для того, чтобы получить дизъюнкцию конъюнкций: (A+B)*(C+D)=A*C+B*C+A*D+B*D= Дополним конъюнкции до полных конъюнкций (произведение всех аргументов), раскроем скобки:

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

Построение логического выражения по таблице истинности: для каждой строки таблицы истинности, содержащей 1 составляем произведение аргументов, причем, переменные, равные 0, входят в произведение с отрицанием, а переменные, равные 1 – без отрицания. Искомое выражение F будет составляется из суммы полученных произведений. Затем, если возможно, это выражение необходимо упростить. Пример: дана таблица истинности выражения. Построить логическое выражение. аbcF 0000 0010 0100 0110 1001 1011 1101 1110

Задание на дом: По заданной таблице истинности составить логическое выражение и упростить его. 2. Решить уравнение: 3. Сколько решений имеет уравнение? аbcF 0000 0010 0100 0111 1001 1011 1100 1111

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

  • Сейчас обучается 945 человек из 80 регионов

Курс повышения квалификации

Инструменты онлайн-обучения на примере программ Zoom, Skype, Microsoft Teams, Bandicam

  • Курс добавлен 31.01.2022
  • Сейчас обучается 25 человек из 16 регионов

Курс повышения квалификации

Педагогическая деятельность в контексте профессионального стандарта педагога и ФГОС

  • Сейчас обучается 40 человек из 24 регионов

Ищем педагогов в команду «Инфоурок»

Дистанционные курсы для педагогов

«Взбодрись! Нейрогимнастика для успешной учёбы и комфортной жизни»

Свидетельство и скидка на обучение каждому участнику

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

5 590 380 материалов в базе

Материал подходит для УМК

«Информатика (углублённый уровень) (в 2 частях)», Семакин И.Г., Шеина Т.Ю., Шестакова Л.В.

1.6.2. Логические формулы и функции

Самые массовые международные дистанционные

Школьные Инфоконкурсы 2022

33 конкурса для учеников 1–11 классов и дошкольников от проекта «Инфоурок»

«Психологические методы развития навыков эффективного общения и чтения на английском языке у младших школьников»

Свидетельство и скидка на обучение каждому участнику

Другие материалы

  • 12.11.2017
  • 2001
  • 237
  • 12.11.2017
  • 707
  • 1
  • 12.11.2017
  • 274
  • 0
  • 12.11.2017
  • 980
  • 8
  • 12.11.2017
  • 972
  • 0
  • 12.11.2017
  • 377
  • 0
  • 12.11.2017
  • 705
  • 0
  • 12.11.2017
  • 796
  • 0

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Добавить в избранное

  • 12.11.2017 16174
  • RAR 112.9 кбайт
  • 273 скачивания
  • Рейтинг: 5 из 5
  • Оцените материал:

Настоящий материал опубликован пользователем Егорова Елена Александровна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Автор материала

  • На сайте: 4 года и 11 месяцев
  • Подписчики: 0
  • Всего просмотров: 96267
  • Всего материалов: 15

Московский институт профессиональной
переподготовки и повышения
квалификации педагогов

Дистанционные курсы
для педагогов

663 курса от 690 рублей

Выбрать курс со скидкой

Выдаём документы
установленного образца!

Учителя о ЕГЭ: секреты успешной подготовки

Время чтения: 11 минут

В ростовских школах рассматривают гибридный формат обучения с учетом эвакуированных

Время чтения: 1 минута

Инфоурок стал резидентом Сколково

Время чтения: 2 минуты

В Ростовской и Воронежской областях организуют обучение эвакуированных из Донбасса детей

Время чтения: 1 минута

Каждый второй ребенок в школе подвергался психической агрессии

Время чтения: 3 минуты

Ленобласть распределит в школы прибывающих из Донбасса детей

Время чтения: 1 минута

Минобрнауки создаст для вузов рекомендации по поддержке молодых семей

Время чтения: 1 минута

Подарочные сертификаты

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

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

[spoiler title=»источники:»]

http://www.sites.google.com/a/gkl-kemerovo.ru/informatics/logic/7-sistemy-logiceskih-uravnenij

http://infourok.ru/urok-reshenie-logicheskih-uravneniy-klass-2278711.html

[/spoiler]

Автор статьи

Юлия Валерьевна Шульгина

Эксперт по предмету «Логика»

преподавательский стаж — 10 лет

Задать вопрос автору статьи

Общая характеристика логических уравнений

Определение 1

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

Разнообразные уравнения часто встречаются в жизни. Их используют в финансовых расчетах, строительной сфере, даже в спорте. Уже в древних цивилизациях люди применяли уравнения, а по мере развития науки (в первую очередь математики) сфера их использования только расширялась.

В математической логике решается особый тип уравнений – логические уравнения. Их специфика состоит в том, что неизвестные, которые требуется отыскать, – это не числовые, а логические переменные (могут иметь значения «истина» или «ложь»). Соответственно, и связываются они не арифметическими, а логическими операциями.

Чтобы решить логическое уравнение, требуются определенные знания:

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

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

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

  • применение к каждому уравнению (или входящим в него выражениям) определения функции. Хотя этот метод кажется очень простым, он позволяет решать и достаточно сложные системы логических уравнений;
  • построение таблиц истинности для частей уравнения. Этот метод хорош для уравнений, содержащих 2-3 логические переменные. Если количество переменных велико, приходится перебирать очень много комбинаций и вычисление становится громоздким. Так, для 4 переменных речь идет о 16 комбинациях, а для 5 переменных – уже о 32. Если при этом в правой или левой части уравнения содержится громоздкое выражение, то может потребоваться большое количество расчетов;
  • сведение к одному уравнению. Этот метод позволяет трансформировать систему со сравнительно небольшим количеством уравнений, если каждое из них достаточно простое. Логические уравнения преобразуют таким образом, чтобы в правой части каждого из них получилось одно и то же выражение. После этого уравнения объединяются с помощью конъюнкции. Далее к собранному выражению применяют законы алгебры логики и получают решение исходной системы;
  • замена переменной. Это универсальный метод решения сложных математических уравнений. На первом этапе каждое из входящих в систему уравнений максимально упрощают (в соответствии с законами алгебры логики), а затем повторяющиеся части заменяют новыми переменными. После этого определяют количество решений новой системы и возвращаются к замене, определяя окончательное количество решений;
  • отображение. Этот метод не только позволяет решить сложную систему логических уравнений, но и компактно оформить процесс решения. В основе метода отображений лежит предположение, что, зная количество пар ($x_{k}, x_{k+1}$ ) можно определить количество пар ( $x_{k+1}, x_{k+2}$ ) и тем самым получить общее количество решений для первого уравнения, входящего в систему. Далее полученное правило применяют к остальным парам переменных и получают итоговое решение системы.

«Логические уравнения» 👇

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

Логические операции в логических уравнениях

В логических уравнениях чаще всего встречаются следующие базовые логические операции:

  • отрицание (инверсия). Эта операция применяется к одному аргументу (переменной или целому выражению). Если аргумент истинный, в результате будет получена ложь; если аргумент ложный – истина;
  • дизъюнкция (логическое сложение, «или»). Эта операция объединяет два выражения (или переменные). В результате ее применения получается истина, если хотя бы один из исходных аргументов истинный. Единственный вариант, когда результатом дизъюнкции будет ложь – ложность всех входящих в нее аргументов;
  • конъюнкция (логическое умножение, «и»). Эта операция соответствует пересечению двух выражений (или переменных). Ее результат будет истинным в том и только том случае, когда истинны все входящие в нее аргументы. Если хотя бы один из аргументов ложен, ложной будет и вся конъюнкция;
  • импликация (логическое следование, «если-то»). Эта операция связывает два аргумента (выражения, переменных), первый из которых называется условием (посылкой), а второй следствием (заключением). Ложной импликация будет только в одном случае – если посылка истинна, а заключение ложно. Иными словами, из ложной посылки может следовать как ложь, так и истина, а из истинной – только истина;
  • эквивалентность (равнозначность, «тогда и только тогда, когда»). Эта операция связывает два аргумента и истинна, если они принимают одинаковые значения (оба ложны или оба истинны). Если аргументы разные по истинностной характеристике, то эквивалентность ложна;
  • строгая дизъюнкция (исключающее «или», сложение по модулю 2). Эта операция связывает два аргумента. Она истинна, если один из аргументов истинный, а второй ложный. В случае равенства истинностных характеристик аргументов (оба истинны или оба ложны) результатом применения строгой дизъюнкции будет ложь.

Как и в случае с арифметическими операциями, логические операции выполняются в установленном порядке, имея разные приоритеты:

  1. Действия в скобках.
  2. Инверсия.
  3. Конъюнкция.
  4. Дизъюнкция и строгая дизъюнкция.
  5. Импликация и эквивалентность.

Таким образом, для логического сложения и умножения действует тот же порядок, что и для одноименных арифметических операций.

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

Находи статьи и создавай свой список литературы по ГОСТу

Поиск по теме

В информатике существует раздел алгебры логики, ключевыми объектами которого являются высказывания. Высказывания всегда можно однозначно определить как истинное или ложное. Высказываниям присваиваются буквы (логические переменные) и значения, если высказывание истинное, то значение переменной равно 1, в противном случае 0.

С помощью логических операций строятся составные (сложные) высказывания. Существуют 3 основные логические операции: конъюнкция, дизъюнкция, инверсия.

Алгебра логики или способы решения логических задач

Для большей понятности и наглядности составим таблицу истинности

Алгебра логики или способы решения логических задач

Для примера разберем пару задач из учебника «Информатика 8 класс» автор Босова Л.Л.

Пример 1. Разбирается дело Джона, Брауна и Смита. Известно, что один из них нашел и утаил клад. На следствии каждый из подозреваемых сделал два заявления:

Смит: «Я не делал этого. Браун сделал это».

Джон: «Браун не виновен. Смит сделал это».

Браун: «Я не делал этого. Джон не делал этого».

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

Для решения задачи составим таблицу истинности

Алгебра логики или способы решения логических задач

Мы знаем, что один из них точно совершил преступление, поэтому рассмотрим 3 варианта виновности.

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

В нашем случае это первая строка, следовательно виновен Браун. Смита и Джона необходимо оправдать.

Рассмотрим еще один способ решения логических задач.

Пример 2. Алеша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:

Алеша: «Это сосуд греческий и изготовлен в V веке».

Боря: «Это сосуд финикийский и изготовлен в III веке».

Гриша: «Это сосуд не греческий и изготовлен в IV веке».

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

Для решения запишем каждое предположение отдельно:

Алгебра логики или способы решения логических задач

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

Иными словами, рассмотрим наборы при x1 = 0, тогда

если x2 = 0, то левая скобка 1, тогда правая скобка д.б. 0, т.е. либо x3,x4 = 0,1 либо 1,0,

если x2 = 1, то левая скобка 0, тогда правая скобка д.б. 1, т.е. либо x3=x4=0 либо x3=x4=1

получается четыре ветви

теперь рассмотрим наборы при x1 = 1, тогда

если x2 = 0, то …

если x2 = 1, то …

получается опять четыре ветви

то есть первое уравнение дает восемь «ветвей» решений

Что даст второе уравнение?

либо x3 и x4 одинаковы, либо либо x5 и x6 одинаковы

в каждой из 8 ветвей на некоторую пару x3,x4 приходится по две пары x5,x6

то есть второе уравнение даст 16 ветвей

Аналогично, третье уравнение даст 32 ветви,

а четвертое уравнение в каждой из них по два итоговых решения.

Итого — 64 решения.

II.

Если смотреть на систему как на целое, то можно получить общий вид цепочек

Пусть верно (x1 x2)

тогда не верно (x3 x4), но верно (x5 x6), не верно (x7 x8) и верно (x9 x10)

т.е. (x1 x2) / (x5 x6) / (x9 x10)

это наборы вида 00xx00xx00 00xx00xx11

11xx11xx11

в которых xx — это 01 или 10

Т.е. в каждом таком решении значения идут парами, если где-то пара одинаковая, то перед ней будет разная, и после будет разная.

8 групп комбинаций, в каждой из которых по 4 возможных значения на местах xx xx 8*4 = 32

И то же самое, если НЕ верно (x1 x2)

Итого 64 решения.

Или можно чуть более наглядно это описать для тех, кто любит переобозначения.

Обозначим A0 = пара 00, A1 = пара 11, B0 = пара 01, B1 = пара 10

После любого A может идти только B и наоборот.

Рассмотрим комбинации по две:

A0B0 A0B1 A1B0 A1B1 B0A0 B0A1 B1A0 B1A1 — их получилось 8.

если их будет по три

то на каждую такую кобминацию будет по две трехбуквенных, то есть 16

если по четыре, то 32

и по пять — 64.

Итого 64 решения.

2014 год

B15

¬(x1 ≡x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Преобразуем уравнения к удобному виду:

¬(x1 ≡x2) = x1 ⊕ x2

(x1 ∧ ¬x3) ∧ (¬x1 ∧ x3) = x1 ⊕ x3

Получается:

(x1 ⊕ x2 ) ^ (x1 ⊕ x3) = 0

(x2 ⊕ x3 ) ^ (x2 ⊕ x4) = 0

(x8 ⊕ x9 ) ^ (x8 ⊕ x10) = 0

рассмотрим решения 0ххххххххх

(0 ⊕ x2 ) ^ (0 ⊕ x3) = 0

эти две скобки не должны быть одновременно 1, чтобы конъюнкция была 0

если левая скобка 1, то вторая д.б.0 и наоборот, и еще они могут быть равны 0 одновременно

итак если x2 = 1 то x3 = 0

010xxxxxxx

если правая 1, то левая 0

001ххххххх

а одновременно они нули — это 011ххххх

рассмотрим решения 1ххххххххх

(1 ⊕ x2 ) ^ (1 ⊕ x3) = 0

если х2 = 0, левая скобка 1, правая д.б. 0, т.е. х3 = 1

101ххххххх

если х3 = 0, правая скобка 1, левая д.б.0, т.е. х2 = 1

110ххххххх

и одновременно скобки нули при х2 = х3 = 1

111ххххххх

итак, первое уравнение дает шесть ветвей решений

смотрим второе

010xxxxxxx 001ххххххх 011ххххх

(1 ⊕ 0 ) ^ (1 ⊕ x4) = 0 (0 ⊕ 1 ) ^ (0 ⊕ x4) = 0 (1 ⊕ 1 ) ^ (1 ⊕ x4) = 0

0101хххххх 0010хххххх 0110хххххх

0111хххххх

101ххххххх 110ххххххх 111ххххххх

(1 ⊕ 0 ) ^ (1 ⊕ x4) = 0 (0 ⊕ 1 ) ^ (0 ⊕ x4) = 0 (1 ⊕ 1 ) ^ (1 ⊕ x4) = 0

1010хххххх 1100хххххх 1110хххххх

1111хххххх

итак второе уравнение дало 8 ветвей

третье должно дать 10

4 12

5 14

6 16

7 18

8 20

итак, ответ — 20 решений

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

2013 год

B15

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) = 1

(¬y1 ∨ y2) ∧ (¬y2 ∨ y3) ∧ (¬y3 ∨ y4)=1

(y1 →x1) ∧ (y2 →x2) ∧ (y3 →x3) ∧ (y4 →x4)=1

преобразуем второе уравнение

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1

(y1 → x1) ∧ (y2 → x2) ∧ (y3 → x3) ∧ (y4 →x4) = 1

все скобки здесь должны быть истинами

рассмотрим x1 = 1 и y1 = 1

т.е. комбинации 1xxx1xxx

(1 → x2) / (x2 → x3) / (x3 → x4) = 1

(1 → y2) / (y2 → y3) / (y3 → y4) = 1

(1 → 1) / (y2 → x2) / (y3 → x3) / (y4 →x4) = 1

это сразу определяет что x2 = 1, x3 = 1, x4 = 1 и то же для игреков

т.е. из этой ветви годится только решение 11111111

И (*) ВООБЩЕ если xn = 1 то очевидно для всех i xn+i = 1

и то же для всех y

т.е. если встречается 1, то далее все одноименные переменные тоже 1

01110111 например годится, 00110011 и 00010001

это следует из первых двух уравнений

а что дает третье уравнение?

то что если какой-то y=1 то однономерной x с ним тоже будет 1

т.е. ветви решений не симметричны:

годится 01110000 но не годится 00001111

подсчитаем комбинации исходя из этого

11111111

x1110111 (0 и 1)

xx110011 (00, 01 и 11)

xxx10001 (000, 001, 011 и 111)

xxxx0000 (0000, 0001, 0011, 0111, 1111)

Ответ: 15

Вот рекомендации Константина Полякова.

И еще примеры решения конкретных систем: Пример 1, Пример 2

Рассмотрим решение коротких и длинных одиночных уравнений

Два варианта решения:

  • таблица истинности (гарантия верного ответа)
  • аналитический (упрощение, сведение к системе)

АЛГОРИТМ аналитического решения

    1. возможно решать противоположную задачу, определив общее число наборов,
    2. в зависимости от необходимости превратить в конъюнкцию = 1 или дизъюнкцию = 0
    3. разбить на систему
    4. согласно таблице истинности описать наборы решений для каждой части системы
    5. по возможности выбрать ту, где меньше решений
    6. посмотреть какие решения совпадают, т.е. протестировать решения одной части для другой части
    7. выкинуть из второй части то, что не является решениями первой части.
    8. для системы из двух легко воспользоваться формулой количества пересечений.
    9. иногда довольно легко подсчитать комбинации по их «правилу образования», иногда нагляднее и проще выписать их себе списком (если это в пределах десятка).

Рассмотрим пример: (K V L) → (L ^ M ^ N) = 0

Импликация. Ложна когда первая часть истинна, а вторая ложна. Отсюда система:

(1) (K V L) = 1

(2) (L Λ M Λ N) = 0

Первый вариант рассуждений. Рассмотрим антирешения.

дизъюнкция ложна в 4 случаях: 0000 0001 0010 0011

конъюнкция истинна в 2 случаях: 0111 1111

при этом эти «антирешения» не пересекаются, т.е. получается, что все остальные 16-6 = 10 комбинаций должны подходить обоим уравнениям. Потому что эти 10 комбинаций не содержат ни антирешений первого, ни антирешений второго уравнения.

Второй вариант рассуждений. Выберем уравнение с наименьшим числом решений, это первое (16-4 = 12).

Подставим эти решения во второе. Как это сделать, если у нас нет их полного списка?

Очень просто. Среди этих 12 решений есть 2 антирешения второго, так как она оба НЕ входят в 4 антирешения первого.

Значит их нужно выкинуть. 12-2 = 10

Третий вариант. Объединение множеств решений первого и второго — 16. Решений первого 12, решений второго 14.

А найти надо пересечения. По формуле мощности пересечения множеств

|X ∩ Y| = |X| + |Y| — |X U Y| = 12 + 14 — 16 = 26 — 16 = 10

Ответ: 10 решений.

Таблица истинности: http://programming.dojo.net.nz/study/truth-table-generator/index

~(K | L ) | (L & M & N)

K L M N | ~ ( K | L ) | ( L & M & N )

——————————————————-

0 0 0 0 | 1 0 0 0 1 0 0 0 0 0

0 0 0 1 | 1 0 0 0 1 0 0 0 0 1

0 0 1 0 | 1 0 0 0 1 0 0 1 0 0

0 0 1 1 | 1 0 0 0 1 0 0 1 0 1

0 1 0 0 | 0 0 1 1 0 1 0 0 0 0

0 1 0 1 | 0 0 1 1 0 1 0 0 0 1

0 1 1 0 | 0 0 1 1 0 1 1 1 0 0

0 1 1 1 | 0 0 1 1 1 1 1 1 1 1

1 0 0 0 | 0 1 1 0 0 0 0 0 0 0

1 0 0 1 | 0 1 1 0 0 0 0 0 0 1

1 0 1 0 | 0 1 1 0 0 0 0 1 0 0

1 0 1 1 | 0 1 1 0 0 0 0 1 0 1

1 1 0 0 | 0 1 1 1 0 1 0 0 0 0

1 1 0 1 | 0 1 1 1 0 1 0 0 0 1

1 1 1 0 | 0 1 1 1 0 1 1 1 0 0

1 1 1 1 | 0 1 1 1 1 1 1 1 1 1

Рассмотрим другой пример: (K v L) & (M v N) = 1

(1) K v L = 1

(2) M v N = 1

Первому не подходят 0000, 0001, 0010, 0011, т.е. решений 12

Второму не подходят 0000, 0100, 1000, 1100, т.е. решений 12

Объединение множеств решений первого и второго — 15,а не 16, так как комбинация 0000 не подходит обоим уравнениям..

|X ∩ Y| = |X| + |Y| — |X U Y| = 12 + 12 — 15 = 24 — 15 = 9

Или можно просто сказать, что уникальных антирешений всей системы 7 — они складываются из антирешений первого, антирешений второго минус 1 (одно) повторение антирешения 0000, 16-7 = 9

Ответ: 9 решений

(K ^ L ^ M ) v (⌝L ^ ⌝M ^ N) = 0

Дизъюнкция равна 0, это система

(1) K ^ L ^ M = 0

(2) ⌝L ^ ⌝M ^ N = 0

16 комбинации всего возможны

антирешения первого: 111х, их два, следовательно 16-2 = 14 решений первого

антирешения второго: х001, их два, следовательно 16-2 = 14 решений второго

антирешения НЕ пересекаются

поэтому решений 14+14 — 16 = 12

(K v L v M ) ^ (⌝L ^ ⌝M ^ N) = 1

(K | L | M ) & (~L & ~M & N)

    1. K v L v M = 1
    2. ⌝L ^ ⌝M ^ N = 1

Здесь у второго вообще 2 решения (0001 и 1001), подставляем их в первое, 0001 является антирешением первого.

Ответ: 1 решение

(K ^ L ^ M ) → (⌝M ^ N) = 1

решим сначала (K ^ L ^ M ) → (⌝M ^ N) = 0

    1. K ^ L ^ M = 1
    2. ⌝M ^ N = 0

первая

1110

1111

не противоречат ли они второй?

нет.

значит здесь 2 решения

значит у противоположной задачи 16 — 2 = 14 решений

https://docs.google.com/spreadsheet/ccc?key=0ArSeMvw1RqGVdC00XzNPR1BDWVJULVE2S0RySDFkUmc&usp=drive_web#gid=2

Задания в 2010 году были в два раза длиннее. И переменных там больше.

А вот как объясняются эти задачи в пособиях

На этой странице вы узнаете

  • Что такое алгебра логики и зачем здесь котики?
  • Как вычислить истинность логического выражения?
  • Для чего нужны законы логики?

Как часто поведение котов вам кажется странным? А если кот в галстуке или вооружен? Сейчас будем разбираться в логике с помощью этих пушистых созданий.

Понятие алгебры логики

Обратите внимание на этого персонажа:

Я скажу про него две вещи:

  1. Этот кот в галстуке.
  2. Этот кот белого цвета.

Очевидно, что с первым высказыванием и поспорить нельзя, а вот второе — наглая ложь. А если я захочу вас запутать: «Этот кот в галстуке или он белого цвета, из чего следует, что он белого цвета и в галстуке или не белый». Что это в итоге — правда или ложь?

Чтобы это определить, в математике есть отдельный раздел.

Алгебра логики — это раздел математики, который занимается логическими операциями над высказываниями.

Любое высказывание может быть либо истинным, либо ложным. Цель алгебры логики — определять истинность логических выражений на основании отдельных высказываний. Алгебра логики действительно может, например, складывать и умножать высказывания друг с другом, и чтобы в записи это выглядело адекватно, истину принято обозначать как 1, а ложь — как 0.

Что такое алгебра логики и зачем здесь котики?

В примере с котиком высказывание А было истинно, а высказывание В — ложно.
На языке алгебры логики это было бы записано как А = 1, В = 0.

Логические выражения и операторы 

Как вычислить истинность логического выражения?

Термин высказывание, мы теперь знаем. Но что такое логическое выражение? Выражение — это уравнение из высказываний, как математическое уравнение из чисел. 

«Этот кот вооружен и его глаза зеленого цвета», — в одном выражении мы использовали два высказывания. 

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

Например, я скажу про того же самого кота: «Этот кот вооружен и его глаза голубые». Это будет наглая ложь, так как я употребил союз И, то есть подразумеваю, что оба высказывания истинны — что неправда. Но если бы я сказал: «Этот кот вооружен или его глаза голубые», союз ИЛИ защитил бы меня от клейма лжеца. Я делаю акцент на истинности только одного высказывания из двух. 

Так и работают логические операторы — в зависимости от них все выражение и принимает значение истины или лжи.

Основные логические операторы алгебры логики:

  • Конъюнкция: логическое умножение или логическое И. В записи обозначается как ∧. А ∧ В дает истину только в том случае, если оба высказывания А и В истинны.

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

    В примере про кота выше выражение «Этот кот вооружен ∧ его глаза голубые» будет ложным. Он вооружен, но глаза у него не голубые. Одно из высказываний не выполнилось, так что конъюнкция равна 0.

  • Дизъюнкция: логическое сложение или логическое ИЛИ. В записи обозначается как ∨. А ∨ В дает истину в том случае, если хотя бы одно из высказываний истинно.

    Называется логическим сложением за схожесть: если складывать только 0 и 1, чем мы и занимаемся, то достаточно одному слагаемому быть 1, чтобы все выражение не было равно 0.

    Важно сразу понять — если применить логическое сложение к двум единицам (1 ∨ 1), мы получим не 2, а все еще 1. Все-таки единица здесь означает не число, а истину, и сложив две, мы не получим одну сверх-истину.

    Тогда выражение «Этот кот вооружен ∨ его глаза голубые» будет уже истинным: глаза его не голубые, но он все-таки вооружен. Дизъюнкция вернет нам 1.

  • Инверсия: логическое отрицание или логическое НЕ. Превращает истину в ложь и наоборот.

    Ложное высказывание «Его глаза голубые» можно легко превратить в истину, если сказать «Его глаза НЕ голубые». В записи обозначается чертой над выражением или знаком ¬, например, ¬А.

  • Эквиваленция, если проще — равенство. Если оба высказывания равны (оба 0 или оба 1), то получим истину, иначе — ложь. Обозначается как ≡.

    Истинным будет выражение «У кота нет оружия так же, как его глаза голубые». И то, и другое — ложь, но мы их сравнили, сказав, что они одинаковы по истинности, что уже правда.

  • Импликация, иначе говоря, следование. Обозначается стрелочкой, например А ⇒ В. Если из истины следует ложь, то это автоматически ложь, все остальное — истина. 

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

Приоритет этих операторов:

  1. инверсия;
  2. конъюнкция;
  3. дизъюнкция;
  4. импликация;
  5. эквиваленция.

Как и везде в математике, приоритет можно менять с помощью скобок — что в них, то выполняется в первую очередь.

Таблицы истинности

В логических уравнениях высказывания используются в виде переменных, а главная проблема, которую рассматривает алгебра логики — когда точно неизвестна истинность каждого высказывания. Назовем эту ситуацию “кот в мешке”. Сказать про кота можно что угодно, но будет ли это правдой —  мы не узнаем, пока не заглянем в мешок. В таких ситуациях нам может помочь таблица истинности.

Таблица истинности — это таблица, которая показывает истинность всего логического уравнения в зависимости от истинности отдельных переменных.

В этой таблице содержатся все возможные наборы переменных. Количество наборов N зависит от количества различных переменных i как N = 2i.

Чтобы удобно записать наборы, нумеруем их по порядку начиная с 0, переводим их номер в двоичную систему счисления (2сс) и записываем набор цифр.

Давайте запишем таблицы истинности для известных нам логических операторов:

  • инверсия берет только 1 переменную и сразу меняет ее значение:
  • конъюнкция берет две переменные и возвращает 1 только в том случае, если обе равны 1:
  • дизъюнкция вернет 1, если хотя бы одна из переменных равна 1:
  • эквиваленция вернет 1, если переменные равны, и 0 в противном случае:
  • импликация вернет 0, если из истины будет следовать ложь, и 1 во всех остальных случаях:

Импликацию можно выразить через дизъюнкцию:
А ⇒ В = ¬А ∨ В

Зная таблицы истинности отдельных операторов, давайте попробуем составить таблицу истинности для полного выражения.

Например, для выражения: А ∧ (В ∨ С) ≡ В ⇒ ¬А.

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

Здесь порядок операций будет следующим:

Создадим таблицу, в которой сразу пропишем все наборы 0 и 1 для переменных А и В и добавим столбцы для каждого шага вычисления. 

Чтобы удобно записать наборы, пронумеруем их по порядку начиная с 0. Переведем их номер в 2сс и запишем набор цифр. У нас 3 различные переменные, поэтому должно быть 8 наборов.

  1. Первое действие — сложение В и С. Для каждого набора запишем результат сложения в соответствующий столбец.
  1. Второе действие — инверсия переменной А.
  1. Третье действие — умножение значения А на результат первого действия:
  1. Четвертое — импликация значения В и результата второго действия:
  1. И последнее действие — эквиваленция результатов 3 и 4 действий:

Последний столбец — и есть результат таблицы истинности. По нему можно сказать, что при А = 1, В = 0 и С = 1 все исходное выражение равно 1, а во всех остальных случаях — 0.

Законы логики

Для чего нужны законы логики?

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

Их не так уж и мало: от самых простых и очевидных до достаточно хитрых; от тех, которые встречаются очень часто до довольно редких.

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

Попробуем упростить исходное выражение ¬(¬А ∧ ¬В) ∨ В ∧ С:

  1. Первым можно увидеть закон де Моргана, где у нас идет отрицание целой скобки:

¬(¬А ∧ ¬В) ∨ В ∧ С = ¬(¬А) ∨ ¬(¬В) ∨ В ∧ С

  1. Здесь же появляются переменные А и В, к которым можно применить закон двойного отрицания:

¬(¬А) ∨ ¬(¬В) ∨ В ∧ С = А ∨ В ∨ В ∧ С

  1. Можно заметить закон поглощения — В складывается с умножением В на С:

А ∨ В ∨ В ∧ С = А ∨ В

Итого, уравнение с 3 переменными и множеством отрицаний мы смогли превратить в максимально простую запись, где осталось всего 2 переменные:

¬(¬А ∧ ¬В) ∨ В ∧ С = А ∨ В

Фактчек

  • Алгебра логики — это математика, которая пользуется не числами, а высказываниями, являющимися истинными или ложными. Истина обозначается как 1, а ложь — как 0.
  • Основными логическими операторами являются инверсия, конъюнкция, дизъюнкция, импликация и эквиваленция.
  • Для расчета истинности логического уравнения используется таблица истинности.
  • Законы логики помогают сокращать логические уравнения.

Проверь себя

Задание 1.
Выберите правильный порядок приоритета логических операторов:

  1. Импликация, эквиваленция, конъюнкция, дизъюнкция, инверсия.
  2. Инверсия, конъюнкция, дизъюнкция, импликация, эквиваленция.
  3. Инверсия, конъюнкция, дизъюнкция, эквиваленция, импликация.
  4. Инверсия, дизъюнкция, конъюнкция, эквиваленция, импликация.

Задание 2.
Сопоставьте название логического оператора с упрощенным:

Инверсия А. Умножение
Эквиваленция Б. Отрицание
Импликация В. Следование
Дизъюнкция Г. Равенство
Конъюнкция Д. Сложение

Задание 3.
Чему будет равен последний столбец таблицы истинности для уравнения: А ∨ В ⇒ ¬С?

  1. 11101010
  2. 11101111
  3. 11111110
  4. 11000100

Задание 4.
Сократите логическое выражение: ¬(А ∨ В) ∧ (¬А ∨ С)

  1. ¬(А ∧ В)
  2. ¬А ∨ ¬В ∨ С
  3. ¬А ∧ ¬В ∧ С
  4. ¬А ∧ ¬В

Ответы: 1. — 2; 2. — 1Б, 2Г, 3В, 4Д, 5А; 3. — 1; 4. — 4.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *