Упрощение логического выражения: Упрощение логических выражений — справочник для студентов и школьников

Упрощение логических выражений | Законы алгебры логики (курс pol 136 ч.)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углубленный курс, 4 часа в неделю)

Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 10 классы | Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углубленный курс, 4 часа в неделю) | Упрощение логических выражений

Содержание урока

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

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

Задачи

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

Закон двойного отрицания означает, что операция «НЕ» обратима: если применить ее два раза, логическое значение не изменится. Закон исключённого третьего основан на том, что в классической (двузначной) логике любое логическое выражение либо истинно, либо ложно («третьего не дано»). Поэтому если А = 1, то А = 0 (и наоборот), так что произведение этих величин всегда равно нулю, а сумма — единице.

Операции с константами и закон повторения легко проверяются по таблицам истинности операций «И» и «ИЛИ». Переместительный и сочетательный законы выглядят вполне привычно, так же, как и в арифметике. Почти везде «работает» аналогия с алгеброй чисел, нужно только помнить, что в логике 1 + 1 = 1, а не 2.

Распределительный закон для операции «ИЛИ» — это обычное раскрытие скобок. А вот для операции «И» мы видим незнакомое выражение, в алгебре чисел это равенство неверно. Доказательство можно начать с правой части, раскрыв скобки:

(А + В) • (А + С) = А • А + А • С + В • А + В • С.

Дальше используем закон повторения (А • А = А) и заметим, что

А + А • С = А • (1 + С) = А • 1 = А.

Аналогично доказываем, что А + В • А = А • (1 + В) = А, таким образом,

(А + В) • (А + С) = А + В • С.

Равенство доказано. Попутно мы доказали также и закон поглощения для операции «И» (для операции «ИЛИ» вы можете сделать это самостоятельно). Отметим, что из распределительного закона следует полезное тождество:

А + А • В = (А + А) • (А + В) = А + В.

Правила, позволяющие раскрывать отрицание сложных выражений, названы в честь шотландского математика и логика Огастеса (Августа) де Моргана. Обратите внимание, что при этом не просто «общее» отрицание переходит на отдельные выражения, но и операция «И» заменяется на «ИЛИ» (и наоборот). Доказать законы де Моргана можно с помощью таблиц истинности.

Теперь с помощью приведённых законов алгебры логики упростим полученное ранее логическое выражение для объединения областей 3 и 4 на диаграмме с тремя переменными (§ 20, рис. 3.15):

(А • В • C) + А • В • C = (А + А) • В • C = В • C.

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

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

1. Заменить все «небазовые» операции (исключающее ИЛИ, импликацию, эквивалентность и др.) на их выражения через базовые операции «НЕ», «И» и «ИЛИ».

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

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

Пример

(А + B) • (А + B) • (А + С)=(А + B) • А • B • (А + C = (А • А + B • А) • B • (А + С) = B • А • B • (А + С) = А • B • B • (А + С) = B • А • (А + С) = B • (А.

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

Следующая страница Логические уравнения

Cкачать материалы урока

Упрощение логических выражений

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



1. X=X

2. XY=YX – переместительный закон умножения

3. X+Y=Y+X — переместительный закон сложения

4. X(YZ)=(XY)Z – сочетательный закон умножения

5. X+(Y+Z)=(X+Y)+Z — сочетательный закон сложения

6. X(Y+Z)=XY+XZ – первый распределительный закон

7. X+(YZ)=(X+Y)(X+Z) — второй распределительный закон

  

8. (X+Y)=XY – отрицание суммы равно произведению отрицаний слагаемых (для любого числа слагаемых)

  

9. (XY)=X+Y – отрицание произведения равно сумме отрицаний сомножителей (для любого числа сомножителей)

10. X+X=X



11. X+X=И – здесь И означает «истина»

12. XX=X



13. X*X=Л – здесь Л означает «ложь»

14. X*И=X

15. X+Л=X



16. XY=X+Y

 

17. XY=XY+XY

18. X+XY=X



19. X+XY=X+Y

 

20. X+XY=X+Y

 

21. XY=AB+AB

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

Упрощение логического выражения заключается в приведении его к виду, содержащему минимальное количество логических операций. В упрощенном выражении должны, как правило, содержатся только простые логические операции: И, ИЛИ, НЕ. Если в результате упрощения логическое выражение становится равным «Л» (ложь), то такое логическое выражение является тождественно-ложным. Если в результате упрощения логическое выражение становится равным «И» (истина), то такое логическое выражение является тождественно-истинным. А если полученное в результате упрощения логическое выражение может быть равным «Л» или «И» в зависимости от значений входящих в него переменных, то такое выражение называется нейтральным.

Пример 1

 

Дано логическое выражение: (AB)(A(B+C). Упростить данное логическое выражение и определить тип полученного в результате упрощения выражения (тождественно-истинное, тождественно-ложное, нейтральное).

Решение

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



1. (AB)=A+B (использовалось соотношение 16)

   

2. (A(B+C)=A+(B+C)=A+B+C

 

       

3. (AB)(A(B+C)=(A+B)(A+B+C)=(A+B)(A+B+C)+(A+B)(A+B+C)=

      

=(A+B)(A+B+C) +ABABC = (A+B)(A+B+C) (использовались соотношения 17,8,13,15)

Рассмотрим полученное логическое выражение:

 

(A+B)(A+B+C)

При A=1, B=0 и любом значении С, значением полученного выражения будет 0 (ложь), а при A=0, C=1 и любом значении В, значением полученного выражения будет 1 (истина).

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

Пример 2

Дано логическое выражение:

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

Решение:

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

1. (использовалось соотношение 16)

2. (использовалось соотношение 16)

3. (использовались соотношения 16,8,1)

4. (использовалось соотношение 20)

5. (использовалось соотношение 17)

(использовалось соотношение 8)

(использовались соотношения 12,10,1)

(использовались соотношения 13,15,18)

Ответ:

Упрощение логических функций, часть I

	Введение Упрощение логических функций в основном используется для уменьшения количества вентилей в проекте. Меньшее количество вентилей означает меньшее энергопотребление, иногда схема работает быстрее, а когда количество вентилей уменьшается, стоимость также снижается.     Существует много способов упростить логическую схему, некоторые из них приведены ниже. Мы подробно рассмотрим каждый из них на следующих нескольких страницах. Алгебраическое упрощение. Символическое упрощение с использованием теорем/постулатов. Требуются хорошие навыки Карты Карно. Схематическая техника с использованием «диаграммы Венна». Ограничено не более чем 6 переменными. Мы уже видели, как работает алгебраическое упрощение, поэтому давайте сосредоточимся на картах Карно или просто k-картах.           Карты Карно Карты Карно обеспечивают систематический метод получения упрощенных логических выражений суммы произведений (SOP). Это компактный способ представления таблицы истинности, используемый для упрощения логических выражений. Он идеально подходит для четырех или менее переменных и становится громоздким для пяти или более переменных. Каждый квадрат представляет собой minterm или maxterm. K-карта n переменных будет иметь 2 квадратов. Для логического выражения члены произведения обозначаются единицами, а члены суммы обозначаются нулями, но 0 часто остаются пустыми.     K-карта состоит из сетки квадратов, каждый квадрат представляет собой одну каноническую минитермную комбинацию переменных или их инверсию. Карта устроена так, что квадраты, представляющие минтермы, отличающиеся только одной переменной, являются смежными как по вертикали, так и по горизонтали. Следовательно, XY’Z’ будет примыкать к X’Y’Z’, а также будет примыкать к XY’Z и XYZ’.       Техника минимизации На основании Объединяющей теоремы: X + X’ = 1 Минимизируемое выражение обычно должно иметь форму суммы произведений (при необходимости применяется процесс преобразования для создания формы суммы произведений). Функция отображается на K-карте путем отметки 1 в тех квадратах, которые соответствуют терминам в упрощаемом выражении (другие квадраты могут быть заполнены нулями). Соседние пары единиц на карте объединяются по теореме Y(X+X’) = Y, где Y — любое логическое выражение (если две пары также являются смежными, их также можно объединить по той же теореме). Процедура минимизации состоит из распознавания этих пар и нескольких пар. Они обведены кружком, что означает сокращенные сроки. Обведены группы, содержащие две (2 1 ) единицы, четыре (2 2 ) единиц, восемь (2 3 ) единиц и так далее. Обратите внимание: поскольку квадраты на одном краю карты считаются соседними с квадратами на противоположном краю, из этих квадратов можно составить группу. Группы могут перекрываться. Цель состоит в том, чтобы покрыть все единицы на карте наименьшим количеством групп и создать для этого самые большие группы. После того, как все возможные группы сформированы, определяются соответствующие термины. Группа из двух единиц удаляет одну переменную из исходного minterm. Группа из четырех единиц удаляет две переменные из исходного minterm. Группа из восьми единиц удаляет три переменные из исходного minterm и т. д. Удалены переменные, отличающиеся от исходных минтермов группы.
	Copyright 1998-2014 Дипак Кумар Тала — Все права защищены У вас есть комментарий? напишите мне по адресу: deepak@asic-world. com

Минимизация булевых функций — GeeksforGeeks

Как обсуждалось в разделе «Представление булевых функций», каждая логическая функция может быть выражена как сумма minterms или произведение maxterms. Поскольку число литералов в таком выражении обычно велико, а сложность цифровых логических элементов, реализующих булевую функцию, напрямую связана со сложностью алгебраического выражения, из которого реализуется функция, предпочтительно иметь максимально упрощенная форма алгебраического выражения.
Процесс упрощения алгебраического выражения булевой функции называется минимизацией . Минимизация важна, поскольку она снижает стоимость и сложность соответствующей схемы.
Например, функцию можно минимизировать до . Схемы, связанные с приведенными выше выражениями, —

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

Минимизация с использованием алгебраических манипуляций —

Этот метод является самым простым из всех методов минимизации. Он подходит для выражений среднего размера, включающих 4 или 5 переменных. Алгебраические манипуляции — это ручной метод, поэтому он подвержен человеческим ошибкам.
Общие законы, используемые в алгебраических манипуляциях:

• Пример 1 – Минимизация следующей логической функции с помощью алгебраических операций-
  
• Решение – Свойства относятся к трем общим законам, упомянутым выше.

     

Минимизация с помощью K-Map –

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

• Пример 2 – Рассмотрим то же выражение из примера 1 и минимизируем его с помощью K-Map.
• Решение – Ниже приведена К-карта с 4 переменными данного выражения.
  
  На приведенном выше рисунке основные импликанты выделены зеленым, красным и синим цветом.
  Зеленый занимает всю третью строку, что дает нам –
  Красный занимает 4 квадрата, что дает нам –
  Синий занимает 4 квадрата, что дает нам –
  Итак, минимизированное логическое выражение равно-

Угловые вопросы GATE CS

Ответив на следующие вопросы, вы сможете проверить свои знания. Все вопросы были заданы в GATE в предыдущие годы или в пробных тестах GATE. Настоятельно рекомендуется их практиковать.

1. СУ ВОРОТА 2012, Вопрос 30
2. СУ ВОРОТА 2007, Вопрос 32
3.