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

Теоремы для двух переменных и более

; (переместительный закон),

(сочетательный закон)

(распределительный закон)

; (теорема де-Моргана)

;

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

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

Реализация логических элементов с помощью элементов И-НЕ «штрих Шеффера» показана на рис.2.2.

НЕ И И-ИЛИ-НЕ

Рис.2.2 - Реализация различных логических функций с помощью элементов

И-НЕ:

Можно показать, что функционально полной является система, состоящая из булевой функции «стрелка Пирса».

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

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

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

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

Если же каждый член дизъюнктивной нормальной функции от п аргументов содержит все эти п аргументов, часть из которых входит в него с инверсией, а часть — без нее, то такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ);^;

Например, функция задана в табличной форме:

Х₁	Х₂	Х₃	У

Тогда СДНФ будет:

Для реализации полученной функции необходимо иметь четыре трехвходовых элемента «И» и один четырехвходовый элемент «ИЛИ» (см. рис.2.3).

Рис.2.3 - Функциональная схема для выполнения заданной функции алгебры логики

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

Возможность записи функций в дизъюнктивных формах и конъюнктивных формах определяется исходя из следующего. Рассмотрим произвольную логическую функцию от п аргументов типа конституенты единицы, которая полностью определяется заданием набора, обращающего ее в единицу. В этом наборе некоторые аргументы могут быть равными «1», а остальные равны «0». Составим конъюнкцию от всех п аргументов, причем те аргументы, которые в указанном наборе равны «0», возьмем с инверсией, а аргументы равные «1» - без инверсии. Если все аргументы будут соответствовать заданному набору, то функция обратится в конъюнкцию п единиц и будет равна «1». Для всех остальных наборов хотя бы один аргумент отличается от заданного набора, а значит, и вся конъюнкция обратится в «0». Таким образом, произвольная функция от п аргументов типа конституенты «1» может быть выражена через конъюнкцию и инверсию. Например, функция четырех аргументов, которая обращается в «1» при x₁=0, x₂=1, x₃=1, x₄=0 и в «0» на всех остальных наборах, может быть записана в виде:

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

x₁=1, x₂=0, x₃=1, x₄=1

обращается в «0», а на всех остальных наборах равна «1», то она будет иметь вид:

Произвольная функция может быть выражена через функции дизъюнкции, конъюнкции и инверсии как в виде СДНФ, так и в виде СКНФ.

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

Х₁
Х₂
Х₃
F(x₁,x₂,x₃)

можно записать функцию в СДНФ в виде:

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

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

Пример решения:

Х₁
Х₂
Х₃
F(х₁,х₂,х₃)

В СНДФ функция будет выражена в следующем виде:

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

Схема соединений ЛЭ с применением 2-, 3-входовых элементов указана на рис.2.4.

Рис.2.4 - Функциональная схема для заданной функции после минимизации функции.

2.5 Минимизация функций алгебры логики с применением карты Карно.

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

В результате минимизации логические функции могут быть представлены в ДНФ или в КНФ с минимальным числом членов и с минимальным числом аргументов в каждом члене. Для упрощения выражений функций алгебры логики разработаны как графические, так и алгебраические методы.

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

Х₂ Х₂

Х₁

а)

Х₁

в) Х₄

Х₂

Х₁

б) Х₃

Х₃

Рис.2.5 Таблица карты Карно: а) для двух аргументов; б) для трех аргументов; в) для четырех аргументов

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

Число клеток карты равно числу возможных наборов значений аргументов и при числе аргументов n равно 2ⁿ. В каждую клетку карты записывается значение функции для соответствующего этой клетке набора значений аргументов. Например, если функция задана таблицей истинности (см. таблицу 2.2), то в форме карты Карно эта функция будет представлена так, как показано на

рис. 2.6, а.

Таблица 2.2 - Таблица истинности функции F(x₁x₂x₃)

Х₁
Х₂
Х₃
F(x₁x₂x₃)

При этом клетки верхней строки соответствуют следующим наборам (см. рис.2.6.а):

первая клетка: х₁=1; х₂=1;

вторая клетка: х₁=1; х₂=1; х₃=1,

третья клетка: ; х₂=1; х₃=1,

четвертая клетка: , , х₃=1.

При записи функции в минимальной форме по картам Карно используются следующие правила.

Все клетки, содержащие 1, объединяются в замкнутые области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2^k, где k=0, 1, 2, 3, 4, ... . Области могут пересекаться, и одни и те же клетки могут входить в разные области. Затем производится запись минимального выражения в дизъюнктивной нормальной форме ДНФ. Каждая область в такой записи представляется членом, число аргументов в котором на k меньше общего числа аргументов функции п, (равно п—k). Каждый член МДНФ составляется лишь из тех аргументов, которые для соответствующей области имеют значения либо без инверсий, либо только с инверсией.

Х₂ Х₂

1 1

а) I

1 1

Х₁ Х₁

Х₄

II

Х₃ IV

Б) III

Х₃

Рис.2.6 - Карта Карно: а) для функции F(x₁x₂x₃) - для трех аргументов;

б) для функции F(x₁x₂x₃) - для четырех аргументов

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

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

членах будет минимальным. Так, для функции трех аргументов, представленной на рис. 2.6, а, клетки, содержащие 1, охватываются двумя областями. В каждой области две клетки, и так как 2^k = 2, то, следовательно,

k = 1. Поэтому для этих областей n-k=3-1=2. В результате в ДНФ будет два члена и в каждом из них по два аргумента. Первой области соответствует импликанта х₁х₂, а второй области — импликанта . Следовательно, минимальная ДНФ для этой функции будет:

Примером задания функции четырех аргументов с помощью карты Карно может служить карта, приведенная на рис.2.6.б, где выделены четыре области. Первая и четвертая области имеют по две клетки; для них n—k=3 и соответствующие им члены будут и .Области II и III содержат по четыре клетки, и в ДНФ они будут выражены членами, содержащими по два аргумента и .Таким образом, минимальная форма функции будет

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

Представление функции и минимизация ее с помощью карт Карно усложняется, если число аргументов больше четырех. Так, для представления функции пяти аргументов необходимо использовать две карты, каждая из которых представляет собой карту четырех переменных; одна для х₅=1, а другая для х₅=0.Эти карты располагаются одна над другой, и области охвата клеток могут быть трехмерными, т. е. в одну область могут входить клетки двух карт. Для минимизации функций с числом аргументов более 7—8 карты Карно практически не используются, и в этих случаях используются алгебраические методы, такие как метод Квайна, метод неопределенных коэффициентов и др.

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