Законы алгебры логики примеры

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

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

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

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

Закон

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

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

Конспект урока

Информатика, 10 класс. Урок № 12.

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

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

Глоссарий по теме: основные законы алгебры логики, логические функции, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ)

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса

— М.: БИНОМ. Лаборатория знаний, 2017 (с.197—209)

Открытые электронные ресурсы по теме:

Теоретический материал для самостоятельного изучения.

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

Основные законы алгебры логики

Справедливость законов можно доказать построением таблиц истинности.

Пример 1. Упростим логическое выражение

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

В общем случае можно предложить следующую последовательность действий:

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

Пример 2. Упростим логическое выражение .

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

Аналогичные законы выполняются для операции объединения, пересечения и дополнения множеств. Например:

Пример 3. На числовой прямой даны отрезки B = [2;12] и C = [7;18]. Каким должен быть отрезок A, чтобы предикат становился истинным высказыванием при любых значениях x.

Преобразуем исходное выражение, избавившись от импликации:

A, B, C — множества. Для них можно записать (U — универсальное множество).

Будем считать, что.

Тогда , причем это минимально возможное множество А.

Так как множество B — это отрезок [2;12], а множество — это промежутки и, то пересечением этих множеств будет служить промежуток . В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий.

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

тождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.

Перепишем исходное выражение в наших обозначениях и преобразуем его:

Рассмотрим предикат . В числе 28₁₀=11100₂ 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание будет ложным.

Рассмотрим предикат . В числе 45₁₀=101101₂ 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание будет ложным.

Рассмотрим предикат . В числе 17₁₀=10001₂ 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна 0, если в числе х 4-й и 0-й биты будут содержать нули. Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах.

По условию задачи надо, чтобы .

Запишем это выражение для рассмотренных множеств истинности:

Так как , примем .

Объединением множеств M и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством K будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т.е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А.

Искомое число a должно быть таким, чтобы при любом неотрицательном целом значении переменной х: , и, кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 101100₂ = 44₁₀.

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

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

Для n=2 существует 16 различных логических функций. Рассмотрим их подробнее.

В алгебре логики имеется четыре основных закона:

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

2. Сочетательный, или закон ассоциативности для сложения и умножения, соответственно:

3. Распределительный, или закон дистрибутивности для сложения и умножения, соответственно:

4. Закон двойственности или инверсии (правило де Моргана) для логических операций сложения и умножения, соответственно:

сложение , , ,

умножение , , , .

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

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

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

Формы переключательной функции являются двойственными, если одна получается из другой путем замены всех символов операции И на символы операции ИЛИ и наоборот; всех нулей на единицы и наоборот. Например, для функции

двойственной функцией будетY_ДВ = = = .

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

Тождества и правила

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

Таблица 3.1– Набор логических тождеств

А Ú 0 = А	А Ú = 1	А·А = А
А Ú 1 = 1	А·0 = 0	А· = А
А Ú А = А	А·1 = 1	= А

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

склеивания: А·ВÚ А = А; (А·Ú В )(А +) = А.

Доказать справедливость этих соотношений можно путем следующих преобразований:

(А·Ú В )(А + ) = А – (А·Ú В )(А + ) = А А + А +В А +В =

= А (1 + + В + 0) = А.

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

F = = = = = .

Двойственная функция F_ДВ =

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

3.4 Элементарные логические функции.

Совокупность различных значений переменных называют набором. Булева функция n аргументов может иметь до N = 2 n наборов. Поскольку функция принимает только два значения, общее число булевых функций n аргументов равно 2 N = 2 2 n . Таким образом, функция одного аргумента может иметь четыре значения:

f₁ = А, f₂= , f₃ = 1 (константа 1), f₄ = 0 (константа 0).

Два аргумента дают 16 значений функции (таблица 3.3.).

Любая из этих функций обращается в единицу (конституента единицы) только на своем наборе, во всех остальных случаях (2 n – 1) она равна нулю. Функции взаимно инверсны, если на том же наборе функции обращается в нуль (конституента нуля), а в остальных случаях она равна единице.

В число шестнадцати функций входят и вырожденные функции:

Остальные десять булевых функций сведены в таблицу 3.4.

Кратко рассмотрим работу логических элементов, которые не были описаны выше.

Функции «дизьюнция с отрицанием» это логическое ИЛИ-НЕ (NOR gate) f₁ = (стрелка Пирса, функция Вебба). Судя по таблице (рис 3.6, а), низкий уровень напряжения устанавливается на выходе, если на любом из входов присутствует высокий уровень напряжения. Там же на рис.3.6, б приведено УГО логическое И-НЕ и эпюры напряжений входах и выходах схемы (рис 3.6в). Число входов можно расширять до любого количества.

Особенностью функции является то, что высокий уровень H на выходе устанавливается лишь при наличии низких уровней L на всех входах.

Следующая функциональная схема – логическое И-НЕ (штрих Шеффера, NAND gate) f₇ = . Если на любой из входов подан низкий уровень напряжения, то на выходе устанавливается высокий уровень напряжения (табл. на рис. 3.7, а). Там же приведены УГО логическое И-НЕ и эпюры напряжений входах и выходах схемы (рис. 3.7, а и3.7, б,соответственно).

Особенностью функции является то, что лог. 1 устанавливается на выходе при наличии хотя бы на одном из входов низкого уровня L.

Функция «запрет по b» логическая конъюнкция a и f₄ = . На рис.3.8, а представлена таблица истинности, условное графическое обозначение показано на рис. 3.8, б и на рис. 3.8, в – эпюры напряжений. В связи с тем, что сигнал b приходит на вход схемы логического умножения в инверсном виде, то сигналы а высокого уровня проходя на выход ЛЭ только при низком уровне управляющего сигнала b, что отражено наэпюрах (рис. 3.8,).

Импликация от В к А

Импликация от b к a это дизъюнкция a и f₁₁ = . На рис. 3.8 а, б, в приведена таблица истинности (а), условное графическое обозначение (б) и эпюры напряжений (в).

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

Равнозначность А и В

Равнозначность указывает на то, что оба аргумента имеют одинаковый (высокий H или низкий L) уровень. Таблица истинности, условное графическое обозначение и зпюры напряжений приведены на рис. 3.9 а, б, в, соотвтственно.

Функция «логическая равнозначность» широко применяется в разнообразных устройствах контроля.

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

Взаимно инверсные функции сведены в табл. 3.4.

Первая пара двойственных функций относится к дизъюнкциям.

Функция Пирса f₁ = инверсна по отношению к функции дизъюнкции f₁₄ = , .

Функция Шеффера f₇ = инверсна по отношению к конъюнкции f₈ = a Ù b:

Функции запрета и импликации также инверсны по отношению друг к другу:

Для функции «запрет по b» f₄ = b инверсной является «импликация от b к a» f₁₁ = :

В свою очередь «запрет по b» f₂ = своей инверсной функцией имеет «импликацию от a к b» f₁₃ = :

Взаимно инверсны функция неравнозначности (сложения по модулю два) f₆ = и функция равнозначности f₉ =

= .

Для доказательства этого равенства воспользуемся правилом де Моргана:

= = = = .

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Студент — человек, постоянно откладывающий неизбежность. 10623 — | 7341 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно