Формулы для упрощения логических выражений

Формулы для упрощения логических выражений

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

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

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

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

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

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

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

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

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

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

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

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул.

В этом примере применены законы противоречия (11) и исключения констант (7).

В этом примере применён закон противоречия (11) и определение операции «Логического сложения».

В примере 3 применены законы противоречия (11) и исключения констант (7).

В примере (4) применён закон противоречия (11) и определение операции «Логического умножения».

Законы алгебры логики в этом примере применяются в следующей последовательности: правило де Моргана (14), сочетательный закон (6), закон противоречия (11) и правило операций с константами (7).

Законы алгебры логики в этом примере применяется в таком порядке: правило де Моргана (14), выносится за скобки общий множитель (закон дистрибутивности (8)), закон противоречия (11).

Читайте также:  Как возвести число в квадрат на калькуляторе

В этом примере к отрицаниям неэлементарных формул применяется правило де Моргана ((14) и (15)); сочетательный закон (6), используются законы двойного отрицания (13) и определение операции «Логического сложения».

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

Использование этих формул означает, что любое выражение можно умножить на единицу или к любому выражению добавить нуль. Пример:

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

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

Логические функции часто формируют на основе математических выражений. Математическое выражение, как известно, содержит переменные, константы и функции, соединённые знаками математических операций. Но для создания логической функции обязательно использование операций отношения: , ≤, ≥, =, ≠. Результат любой из этих операций является «истина» или «ложь», которые мы условились обозначать 1 или 0. Таким образом, каждая операция отношения создаёт одно простое высказывание.

Например, выражение X >Y принимает значение 0 или 1 в зависимости от конкретных значений X и Y. Таким образом, можно сформировать логическую функцию f от действительных переменных X и Y, которая будет истинной, если выполняется указанное выше условие. Записывается это так:

Другой пример. Сформировать логическую функцию, которая будет истинной, если переменные x и y кратны трём; x, y переменные целого типа.

Решение. Заметим, что целое число а будет кратно целому числу b, если остаток от целочисленного деления а на b будет равен нулю:

Здесь запись mod означает операцию вычисления остатка при целочисленном делении а на b.

В условии задачи легко выделить два простых высказывания: x кратно трём и y кратно трём. Между этими высказываниями стоит союз «и». Следовательно, это сложное высказывание содержит операцию логического умножения, а математически это высказывание можно записать так:

Читайте также:  Lg flatron l1718s не включается

f(x, y) = (x mod 3 = 0)∙(y mod 3 = 0).

Рассмотрим ещё один пример. Сформировать логическую функцию, которая будет истинной, если сумма a и b положительна, а величины a или b отрицательны. a и b переменные действительного типа.

Решение. В этом примере также можно выделить несколько простых высказываний:

Первое высказывание с двумя другими связывается союзом «а», что означает между ними операцию логического умножения. Далее, второе и третье простые высказывания соединены союзом «или», что означает между ними операцию логического сложения. Таким образом, мы получаем следующую функцию:

где X и Y – координаты точки, принадлежащей окружности. Точка будет внутри этой окружности, если её координаты удовлетворяют условию:

Чтобы точка была в верхней полуплоскости необходимо выполнение условия Y ≥ 0. Оба эти условия должны выполняться одновременно, что возможно только для операции логического умножения. Таким образом, искомая функция имеет вид:

Законы алгебры логики и правила преобразования логических выражений

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

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

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

Закон

Формулировка

1. Закон тождества

Всякое высказывание тождественно самому себе.

2. Закон исключенного третьего

Читайте также:  Почему не могу войти в почту майл

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

3. Закон непротиворечия

Высказывание не может быть одновременно истинным и ложным. Если высказывание Х истинно, то его отрицание НЕ Х должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно.

4. Закон двойного отрицания

Если дважды отрицать некоторое высказывание, то в результате получим исходное высказывание.

5. Переместительный (коммутативный) закон

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

6. Сочетательный (ассоциативный) закон

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

5. Распределительный (дистрибутивный) закон

(X / Y) / Z= (X / Z) / (Y / Z)

(X / Y) / Z = (X / Z) / (Y / Z)

Определяет правило выноса общего высказывания за скобку.

7. Закон общей инверсии Закон де Моргана

Закон общей инверсии.

8. Закон равносильности (идемпотентности)

от латинских слов idem — тот же самый и potens —сильный

9. Законы исключения констант:

10. Закон поглощения:

11. Закон исключения (склеивания):

12. Закон контрапозиции

14. А В = (А / В) / (¬A / ¬B);

15. А В = (¬A / В) / (А /¬B).

Применим законы алгебры логики. Покажем на примере как можно упростить логическое выражение:

1) (A/B) / (A/¬B) = A / (B / B)= A / 1 = A

Законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами.

¬ (X / Y) / (X / ¬Y) = ¬ X / ¬Y / (X / ¬Y) = ¬ X / X/¬Y /¬Y= 0 ¬Y /¬Y

3) применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией

4) ¬ X / Y / ¬ (X / Y) / X = ¬ X / Y / ¬ X / ¬Y / X= ¬ X / (Y / ¬Y) / X= ¬ X / X= 1

Ссылка на основную публикацию
Adblock detector