Теория дискретных устройств автоматики и телемеханики

Конспект лекций по дисциплине Теория дискретных устройств автоматики и телемеханики Лекция 1 Понятие функции алгебры логики Функцию n переменных f x1 , x2 , ..., xn  называют функцией алгебры логики (ФАЛ), если она, также как и её переменные может принимать только два значения: 0 и 1. Переменные функции алгебры логики x1 , x2 , ..., xn сопоставляют сигналам на входах некоторого дискретного устройства (рис. 1), а значения функции y  f x1 , x2 , ..., xn  - значению сигнала на его выходе. Рисунок 1 В логических выражениях принято слева от знака равенства записывать условное обозначение функции, а справа – аналитическое выражение, описывающую логическую взаимосвязь между выходным сигналом дискретного устройства и входными переменными. Примерами записи логических выражений являются следующие: y  x1  x2  x3 , z  a  b   c и т.д. Способы задания функций алгебры логики Существует ряд способов задания (описания) ФАЛ. На рис. 2 приведены основные из них. Рисунок 2 Табличный способ задания ФАЛ При табличном способе задания ФАЛ, она представляется таблицей, в которой каждой совокупности значений переменных x1 , x2 , ..., xn приведено соответствующее единственное значение функции y . Совокупность значений переменных называется набором, а таблица при условии, что значения функции определены для всех возможных наборов из n переменных, носит название Таблица истинности. Поскольку каждая из входных переменных может принимать только два значения – 0 и 1, то максимальное количество уникальных наборов входных переменных, а, следовательно, и количество строк в таблице истинности, может быть определено по формуле вида: N  2n , (1) где 2 – основание системы счисления (все переменные могут принимать только одно из двух возможных значений); n – количество переменных, входящих в ФАЛ. Так, например, для ФАЛ трёх переменных y  f x3 , x2 , x1  , таблица истинности, не считая строки заголовка, должна содержать 2 3  8 строк, для ФАЛ пяти переменных y  f x1 , x2 , x3 , x4 , x5  – 2 5  32 и т.д. Таблица истинности 1 функции y трёх переменных может иметь, например, такой вид: Таблица 1 Так как на каждом наборе значений входных переменных функция может принимать одно из двух возможных значений, то, следовательно, при n входных переменных возможны R  2 N  2 2 различных ФАЛ. Иными словами для n переменных можно построить R различных таблиц истинности. Например, при одной переменной ( n  1) возможно задать четыре различных ФАЛ (см. табл. 2), для n  2 – 16, для n  3 – 256 и т.д. Таблица 2 n 2 Таблица истинности является конечным результатом абстрактного синтеза дискретного устройства и служит исходным документом для различного рода преобразований ФАЛ на последующих этапах синтеза. Графический способ задания ФАЛ При графическом способе каждому набору значений переменных ФАЛ соответствует определенная точка n -мерного пространства. Координатам вершин n -мерного куба соответствуют наборы значений переменных, а их обозначениям – приписаны значения функции на этих наборах. Поскольку каждая из переменных ФАЛ может принимать только два значения: 0 и 1, то каждое ребро, соединяющее две соседние вершины, наборы которых отличаются одной переменной, имеет единичную длину. Поэтому n -мерный куб называют единичным. Количество вершин n -мерного куба равно количеству строк в таблице истинности, а количество координатных осей равно количеству n переменных. При количестве переменных более 3-х графическое представление ФАЛ затруднительно. Единичный 3-x мерный куб, соответствующий ФАЛ, заданной ранее таблицей истинности (табл. 1), приведен на рис. 3. Для примера вершина куба на рис. 3 и ячейка табл. 1, содержимое которых описывает один и тот же набор переменных (№6), выделены пунктиром. Аналогичным образом можно сопоставить вершинам куба остальные ячейки таблицы истинности. Рис. 3. Пример графического представления ФАЛ Координатный способ задания ФАЛ При координатном способе ФАЛ задают в виде координатной карты состояний, называемой картой Карно. Карта Карно представляет собой прямоугольную или квадратную таблицу, разделенную горизонтальными и вертикальными линиями на клетки. Общее количество клеток в карте Карно соответствует количеству наборов ФАЛ, следовательно, оно может быть вычислено по формуле (1). Следует отметить, что общее количество клеток карты Карно совпадает с количеством вершин n -мерного куба, и количеством ячеек в столбце y 3 таблицы истинности. При построении карты Карно для ФАЛ, содержащей не более четырёх переменных, все переменные разбиваются на две группы. Одна из групп переменных определяет выбор строки в карте Карно, а другая – выбор столбца. На пересечении строки и столбца находится клетка, в которую записывается значение функции при соответствующем наборе переменных. Переменные разбиваются на группы таким образом, чтобы в соседних клетках наборы различались только значением одной переменной. В качестве примера на рис. 4 представлена карта Карно для ФАЛ, заданной в табл. 1. В ней ячейка, соответствующая набору переменных № 6 из табл. 1, выделена пунктиром. Содержимое остальных ячеек также однозначно соответствует содержимому ячеек столбца " y" из табл. 1. Принятые обозначения: xi  xi  1 xi   x i  0  В скобках внутри ячеек указаны номера соответствующих наборов из таблицы истинности (табл. 1) Рисунок 4 Общий вид карты Карно ФАЛ четырёх и двух переменных представлен на рис. 5. У карт Карно двух и четырёх переменных всегда число строк равно числу столбцов, у карт Карно трёх переменных число строк отличается в два раза от числа столбцов. Использование карт Карно вызывает определенные сложности, если количество переменных превышает четыре. Рисунок 5. Карты Карно для 4-х и 2-х переменных 4 Координатный способ задания ФАЛ используется, как правило, для минимизации ее аналитического выражения. Числовой способ задания ФАЛ При числовом способе задания ФАЛ каждому десятичному номеру набора значений переменных ставят в соответствие число в двоичной системе исчисления. Для этого переменным xn , xn1, ..., x1 приписывают соответственно веса 2n1, 2n2 , ..., 20 . Принято веса и индексы переменным присваивать в порядке возрастания показателя степени справа налево. Например, Тогда функцию можно задать простым перечислением десятичных номеров тех наборов значений переменных, на которых она принимает значение «1». При этом номера наборов находятся путем суммирования произведений значений переменных на их вес по формуле: n N   xi  2 i 1  x1  2 0  x 2  21  ..... (6) i 1 где i – индекс переменной. Например, ФАЛ, заданная ранее таблицей 1, в числовой форме может быть записана следующим образом: y  3, 4, 5, 6, 7x3 , x2 , x1 . (7) При записи ФАЛ в числовой форме приняты следующие обозначения. В фигурных скобках перечислены номера наборов, при которых ФАЛ принимает единичное значение ( y  1 ), разделённые между собой запятыми. За скобкой перечислены входящие в ФАЛ переменные. Существенное значение имеет количество перечисленных вне скобок переменных, а также порядок их перечисления. Например, если вне скобок перечислены три переменных в порядке, приведённом в (7), то это означает, что указанный в скобках десятичный набор № 3, получается так. Переменные имеют веса: x1 – 2 0 , x 2 – 21 , x3 – 2 2 . Из формулы (6) следует, что равенство имеет место только в одном случае: 3  x3  2 2  x2  21  x1  2 0  0  2 2  1  21  1  20 , т.е. при следующих значениях переменных: x3  0 , x2  x1  1 , и т.д. 5 Если же числовая форма ФАЛ имеет вид: y  3, 4, 5, 6, 7x , x , x , то переменные в соответствии со своим индексом имеют те же веса: x1 – 2 0 , x 2 – 21 , x3 – 2 2 . Поэтому, равенство в формуле (6) будет иметь место при тех же значениях переменных: 1 2 3 x1  x 2  1 , x3  0 . Аналогично, если ФАЛ записана в форме y  3, 4, 5, 6, 7x , x , x , x , то это означает, что во все наборы входит четыре переменных, причём веса распределены следующим образом: x1 – 2 0 , x 2 – 21 , x3 – 2 2 , x 4 – 2 3 . Тогда ФАЛ принимает единичное значение ( y  1 ) на наборе с номером 3, который получается при следующих значениях переменных: x4  x3  0 , x2  x1  1 . ФАЛ на наборе с номером 7, который получается при x 4  0 , x3  x2  x1  1, также истинна, т.е. принимает значение, равное логической «1». Числовой способ записи ФАЛ используется в тех же целях, что и таблица истинности, но более компактен и удобен при использовании. 4 3 2 1 Аналитический способ задания ФАЛ При аналитическом способе ФАЛ задают в виде алгебраического выражения (формулы), показывающего какие и в какой последовательности должны выполняться логические операции над аргументами (переменными и двоичными константами). Основные логические функции, используемые при записи логических выражений приведены в табл. 6. Вместе с тем, среди различных форм аналитической записи ФАЛ, существуют некоторые исходные формы, основным назначением которых является первоначальное аналитическое описание ФАЛ. Эти формы называются нормальными и составляются на основе данных таблицы истинности или числового представления ФАЛ, с использованием которых могут быть составлены канонические формы записи двух видов (см. рис. 6): Рисунок 6 1) если в аналитическом задании ФАЛ, участвуют только наборы значений аргументов, на которых она принимает значение 1, то записывается дизъюнктивная совершенная нормальная форма (ДСНФ); 2) если в аналитическом задании ФАЛ, участвуют только наборы аргументов, на которых она принимает значение 0, то записывается конъюнктивная совершенная нормальная форма (КСНФ). 6 В свою очередь, после ряда преобразований ФАЛ, заданных в канонических формах, можно получить более простую аналитическую запись функций в виде дизъюнктивных (ДНФ) или конъюнктивных (КНФ) нормальных форм. Если для одной и той же ФАЛ совершенных форм каждого вида может быть только одна, то простых дизъюнктивных и конъюнктивных нормальных форм может быть получено множество в зависимости от цели и методов проведения преобразования ФАЛ, заданных в одной из канонических форм. Прежде чем рассмотреть методы получения канонических нормальных форм ФАЛ следует сделать пояснения. 1) канонические формы ФАЛ обычно получают на основе таблицы истинности или ее числового выражения; 2) в основе методов получения канонических форм лежит один и тот же принцип – принцип суперпозиции функций. Его суть заключается в том, что в качестве аргументов ФАЛ могут выступать не только двоичные переменные, но и другие ФАЛ. Например, принципу суперпозиции удовлетворяет ФАЛ вида y  f 1  f 2 , если переменные f 1 и f 2 сами являются ФАЛ, имеющими аналитическое выражение f1  x1  x2 , f 2  x1 ; 3) при получении обеих канонических форм в качестве аргументов (переменных) используют некие вспомогательные функции, называемые конституентами; 4) конституенты, используемые при получении ДСНФ, отличаются от конституент, используемых при получении КСНФ: при получении ДСНФ используют конституенты единицы – минтермы, представляющие собой логическое произведение переменных ФАЛ, а при получении КСНФ – конституенты нуля – макстермы, представляющие собой логическое сложение переменных ФАЛ. ДСНФ ДСНФ представляет собой дизъюнкцию минтермов: F  f1  f 2  f 3  ...  f m . Минтерм – это вспомогательная подстановочная функция, имеющая аналитическое выражение, которая обладает следующими свойствами: 1. в неё входит то же количество переменных, что и в ФАЛ, заданную в виде таблицы истинности (карты Карно). 2. минтерм принимает единственное единичное значение только на одном из всех возможных наборов значений переменных, тогда как на всех остальных наборах его значение равно нулю (в таблице истинности минтерма в столбце значений функции имеется только одна ячейка с содержимым 1, в остальных ячейках нули). 3. набор значений аргументов, на котором минтерм принимает своё единственное единичное значение совпадает с набором значений аргументов, на котором ФАЛ, заданная таблицей истинности или числовым методом, принимает одно из своих единичных значений. 7 Задача получения ДСНФ может быть разделена на три этапа:  определение количества минтермов;  определение аналитического выражения для каждого минтерма;  составление выражения ДСНФ. Определение количества минтермов. Поскольку один минтерм позволяет получить только одно из единичных значений заданной ФАЛ, тогда как она может иметь и более одного единичного значения, то в ДСНФ в общем случае входит столько минтермов m , сколько единиц содержится в столбце значений функции таблицы истинности или сколько номеров наборов находится в числовом выражении ФАЛ. Например, для ФАЛ, заданной таблицей истинности (табл. 1), при записи ДСНФ необходимо использовать пять минтермов. F  f1  f 2  f 3  f 4  f 5 (20) Причём, минтерм f 1 будет задаваться таким образом, чтобы единственная единица f 1  1 получалась на наборе № 3, f 2 будет задаваться так, чтобы единственная единица f 2  1 получалась только на наборе № 4 и т.д. Определение аналитического выражения для каждого из минтермов Аналитическое выражение для каждого минтерма получают следующим образом. Сначала вводят аналитические выражения для значений переменных, входящих в набор. При этом, если в таблице истинности значение переменной xi равно единице xi  1, то записывают просто xi , если же значение переменной равно нулю xi  0 , то записывают x i . Аналитическое выражение минтерма представляет собой конъюнкцию (логическое умножение) аналитических выражений значений переменных, входящих в набор, на котором значение минтерма должно быть равно единице. Например, минтерм f 1 , единственная единица у которого будет получаться на наборе № 3 табл. 1, имеет вид: f1  x3  x 2  x1 (табл. 8), минтерм f 2 , единственная единица у которого будет формироваться на наборе № 4 – f 2  x3  x2  x1 и т.д. При вычислении значений минтерма в табл. 8 использовались основные законы алгебры логики. Они приведены в табл. 10. Примечание: В булевой алгебре конъюнкция при выполнении вычислений имеет приоритет перед дизъюнкцией, поэтому скобки могут быть опущены. Отличительной особенностью дизъюнктивной совершенной нормальной формы от остальных нормальных форм является то, что во всех её конъюнкциях присутствуют все переменные, входящие в ФАЛ. 8 КСНФ КСНФ представляет собой конъюнкцию макстермов: F  f1  f 2  f 3  ...  f l . Макстерм – это вспомогательная подстановочная функция, имеющая аналитическое выражение, которая обладает следующими свойствами: 1. в неё входит то же количество переменных, что и в ФАЛ, заданную в виде таблицы истинности или числовым методом. 2. макстерм принимает единственное нулевое значение только на одном из всех возможных наборов значений переменных, тогда как на всех остальных наборах его значение равно единице (в таблице истинности макстерма в столбце значений функции имеется только одна ячейка с содержимым 0, в остальных ячейках единицы). ДСНФ и КСНФ ФАЛ используются для первичного формального аналитического описания дискретного автомата без памяти с целью последующей минимизации логического выражения алгебраическими методами или с применением карт Карно. Составление выражения ДСНФ После подстановки в формулу (20) аналитических выражений минтермов получим ДСНФ ФАЛ. Для ФАЛ, заданной табл.1 ДСНФ имеет следующий вид: f 1  x3  x 2  x1  x3  x 2  x1  x3  x 2  x1  x3  x 2  x1  x3  x 2  x1 . 9 Таблица 9 Основные элементарные функции алгебры логики ФАЛ Переменные Дизъюнкция (логическое сложение, логическое ИЛИ) Конъюнкция (логическое умножение, логическое И) x1  x 2 , x1  x 2 Сумма по модулю 2 (функция неравнозначности) Эквивалентность (функция равнозначности) (зависит от одной переменной) x1  x2 Инверсия (логическое отрицание, логическое НЕ) x1 Штрих Шеффера (логическое ИНЕ) Функция Вебба (логическое ИЛИ-НЕ, стрелка Пирса) x1  x2 , x1  x2 x1  x2 , x1 x2 x1  x2 , x1  x2 1 Обозначение x2 x1 x1  x 2 , x1  x 2 Таблица истинности 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Как читается x 1 или x 2 x1 и x 2 не x 1 или x 1 или x 2 x 1 эквивалентно x 2 x1 и x 2 Комментарий Функция дизъюнкции ложна (y=0) только в случае, если ложны значения всех переменных одновременно, иначе функция истинна. Функция конъюнкции истинна (y=1) только в случае, если истинны значения всех переменных одновременно, иначе функция ложна Функция отрицания истинна, если ложно значение переменной и ложна при истинном значении переменной. x1 x2 Обозначение логического элемента 1 x1 y x2 x1 x & y Функция неравнозначности истинна, если х1≠x2 и ложна при х1=x2 & y 1 y x2  Функция эквиваленции истинна, если х1=x2 и ложна при х1≠x2 x1 y несовместны x2  Функция штрих Шеффера ложна (y=0) только в случае, если истинны значения всех переменных одновременно, иначе функция истинна. x1 y x2 & ни x 1 ни x 2 Функция Вебба истинна (y=1) только в случае, если ложны значения всех переменных одновременно, иначе функция ложна x1 y x2 1 y x1 x x 2 m2 y 10 x1 Эквивалентная контактная схема x2 x1 x2 x x1 x2 x1 x2 x1 x1 x2 x2 В схемах СЦБ принято обозначать контакты нейтрального якоря реле двузначными цифрами. Первый 12 символ означает номер тройника, а второй – тип контакта. Общий контакт нумеруют единицей, фронтовой – 11 13 двойкой, а тыловой – тройкой. На принципиальных схемах принято изображать контактный тройник таким образом, чтобы фронтовой контакт находился сверху, а тыловой – снизу при этом номера контактов могут опускаться. Фронтовой контакт тройника реле замыкается в случае, когда обмотка реле находится под током и размыкается, если она обесточена.Тыловой контакт тройника реле замыкается в случае, когда обмотка реле обесточена. x 11 Лекция 2 Основные законы алгебры логики Таблица 10 Законы для одной переменной, нуля и единицы 1. Логическое сложение переменной с нулём Общий вид аналитической записи x0 x Подставим вместо переменной x некоторую ФАЛ f , получим f  0  f . В качестве f может быть любая ФАЛ. Если, например, ФАЛ имеет вид: Аналитическая запись а) f  x1  x 2 , то справедлива запись x1  x2  0  x1  x2 ; при суперпозиции ФАЛ б) f  x1  x 2 , то справедлива запись x1  x2   0  x1  x2 и т.д. Примечание: лог. умножение имеет приоритет перед лог. сложением, поэтому скобки в выражении (а) не ставятся Формулу: P  f  0 , где f  x1  x 2 , реализует следующая релейно-контактная схема P 1 2 x1 x2 f Пояснительная релейно-контактная схема Получается она так. Как следует из табл. 5, дизъюнкция реализуется параллельным соединением линий, а конъюнкция – последовательным. Тогда, поскольку ФАЛ имеет вид P  f  0 , то аргументы f и 0 будут формироваться двумя параллельными линиями. Вместе с тем, аргумент f сам является ФАЛ – f  x1  x 2 , тогда его внутренняя схема реализации представляет собой последовательное соединение ключей (обведено синим пунктиром на рис). Проанализируем синтезированную схему. Так как ток через обрыв в линии 1 никогда протекать не будет, то её можно исключить, при этом логика работы не изменится, а она приобретает вид: x1 x2 P Для полученной схемы справедливо записать P  x1  x2 . Следовательно, закон x1  x2  0  x1  x2 выполняется лог. 1 yx x Логическая схема Комментарий Как следует из табл. 5, выход логического элемента дизъюнкции, на один из входов которого всегда поступает лог.0, а на другой – значение переменной x, повторяет значение входной переменной х. Следовательно,: – если на входе x  1, то на выходе y  1 , – если на входе x  0 , то на выходе y  0 Примечание: входы логических элементов всегда изображают слева, а выходы – справа. В результате логического сложения переменной (ФАЛ) с нулём, результат совпадает с исходной переменной (ФАЛ) 2. Логическое сложение с единицей Общий вид аналитической записи x 1  1 Подставим вместо переменной x некоторую ФАЛ f , получим f  1  1 . В качестве f может быть любая ФАЛ. Если ФАЛ Аналитическая запись имеет вид: при суперпозиции ФАЛ а) f  x1  x 2 , то справедлива запись x1  x2  1  1 ; б) f  x1  x 2 , то справедлива запись  x1  x2   1  1 Формулу: P  f  1  x1  x 2  1 реализует следующая релейноконтактная схема P 1 1 2 x2 x1 Пояснительная релейно-контактная схема Проанализируем работу схемы. Перемычка (аналог лог.1) в линии 1 обеспечивает постоянное протекание тока через обмотку реле Р, независимо от положения ключей в линии 2. Следовательно, линию 2 можно исключить из схемы при этом логика её работы не изменится. 1 P Для полученной схемы справедливо записать P  1. Следовательно, x1  x2  1  1 лог. 1 Логическая схема 1 y 1 x Как следует из таблицы истинности логического элемента дизъюнкции (табл.5) при наличии хотя бы на одном из входов 13 Комментарий данного элемента лог.1 независимо от состояния другого входа на выходе всегда будет лог.1 Следовательно,: – если на входе x  1, то на выходе y  1 , – если на входе x  0 , то на выходе всё равно y  1 В результате логического сложения любой переменной (ФАЛ) с единицей, результат равен единице 3. Логическое умножение на единицу Общий вид аналитической записи x 1  x Подставим вместо переменной x некоторую ФАЛ f , получим f 1  f . В качестве f может быть любая ФАЛ. Если, Аналитическая запись например, ФАЛ имеет вид: при суперпозиции ФАЛ а) f  x1  x 2 , то справедлива запись x1  x2  1  x1  x2 , б) f  x1  x 2 , то справедлива запись x1  x2   1  x1  x2  и т.д. Формулу: P  f 1   x1  x2  1 реализует следующая релейноконтактная схема P 1 1 x1 2 x2 Пояснительная релейно-контактная схема Очевидно, перемычку можно изменения логики работы 1 x1 исключить из схемы без P 2 x2 Для полученной схемы справедливо записать P  x1  x2 Следовательно, x1  x2  1  x1  x2 лог. 1 & yx x Логическая схема Комментарий Общий вид Как следует из таблицы истинности логического элемента конъюнкции (табл.5), при наличии на одном из входов данного элемента лог.1, выходной сигнал y повторяет сигнал x Следовательно,: – если на входе x  1, то на выходе y  1 , – если на входе x  0 , то на выходе y  0 Результат логического умножения переменной на единицу равен самой переменной. 4. Логическое умножение на ноль x0  0 14 аналитической записи Подставим вместо переменной x некоторую ФАЛ f , получим f  0  0 . В качестве f может быть любая ФАЛ. Если ФАЛ Аналитическая запись имеет вид: при суперпозиции ФАЛ а) f  x1  x 2 , то справедлива запись  x1  x 2   0  0 ; б) f  x1  x2  x1  x2 , то – x1  x2  x1  x2  0  0 и т.д. Формулу: P  x  0 реализует следующая релейно-контактная схема Пояснительная релейно-контактная схема P x Обмотка реле Р никогда не будет под током, поскольку независимо от положения контакта х в цепи питания всегда будет обрыв. Следовательно, контакт х может быть исключен из схемы. P Для полученной схемы справедливо записать: P  0 Следовательно, x  0  0 лог. & y0 x Логическая схема Комментарий Как следует из таблицы истинности логического элемента конъюнкции (табл.5), при наличии на одном из входов данного элемента лог.0, выходной сигнал y независимо от значения входного сигнала x равен нулю. Следовательно,: – если на входе x  1, то на выходе y  0 , – если на входе x  0 , то на выходе y  0 Результат логического умножения переменной на ноль равен нулю. 5. Закон логической тавтологии (для конъюнкции) Общий вид x  x  ...  x  x аналитической записи Многократная конъюнкция одной и той же ФАЛ, например: x1  x2   x1  x2   x1  x2   x1  x2   x1  x2 ; Аналитическая запись x1  x2  x1  x2  x3  x1  x2  x3 при суперпозиции ФАЛ ФАЛ может быть любой. Важно, что все повторные вхождения ФАЛ (переменной) вычёркиваются из конечного выражения и при этом результат не меняется. Формулу: P  x1  x2  x1  x2  x3 Пояснительная реализует следующая релейно-контактная схема релейно-контактная P схема x x x x x 1 2 15 1 2 3 Как видно из приведенной схемы, пара ключей x1 будет замыкаться одновременно, в случае, если обмотка реле x1 (обмотка реле в которое они входят), будет под током, также одновременно они будут размыкаться в момент обесточивания обмотки реле x1 . Поскольку оба ключа одного реле коммутируют одну и ту же цепь, то достаточно оставить один ключ x1 , заменив дубликат проводником. То же можно сказать и о паре ключей x 2 . Следовательно, схема может быть преобразована к следующему виду: x2 x1 x3 P Полученная схема описывается формулой: P  x1  x2  x3 , но работает также как исходная. Это легко увидеть: обмотка реле Р для обеих схем будет под током только в случае, если x1  x2  x3  1 , т.е. все перечисленные реле находятся под током. Следовательно, x1  x2  x1  x2  x3  x1  x2  x3 x1 & x2 y  x1  x2  x1  x2  x3 x3 Логическая схема Как следует из табл. 5, на выходе элемента конъюнкции формируется единица (y=1) только в случае, если на всех входах присутствуют логические единицы. Если хотя бы на один вход элемента будет поступать логический ноль, то на выходе элемента также будет логический ноль (y=0). В данной схеме сигнал х1 разветвляется на два входа элемента конъюнкции, сигнал х2 также разветвляется на два входа элемента конъюнкции. Значит, логические единицы будут поступать на все пять входов элемента конъюнкции в случае, если равны единице три переменных x1  x2  x3  1. В остальных случаях на выходе элемента будет формироваться логический ноль. Следовательно, пятивходовый логический элемент конъюнкции будет работать также, как и трёхвходовый. x1 x2 & y  x1  x2  x3 x3 Комментарий Многократное логическое умножение одной и той же переменной (ФАЛ) самой на себя в результате даёт ту же переменную (ФАЛ) 16 6. Закон логической тавтологии (для дизъюнкции) Общий вид x  x  ...  x  x аналитической записи Подставим вместо переменной x некоторую ФАЛ f , получим f  f  ...  f  f . В качестве f может быть любая ФАЛ. Если ФАЛ, например, имеет вид: а) f  x1  x 2 , то справедлива запись x1  x2   x1  x2   x1  x2   x1  x2 ; Аналитическая запись при суперпозиции ФАЛ б) f  x1  x2  x1  x2 , то справедлива запись x1  x2  x1  x2  x1  x2  x1  x2  x1  x2  x1  x2  x1  x2  x1  x2 ; в) 1  1  ...  1  1 г) f  x1  x 2 , то справедлива запись x1  x 2  ...  x1  x 2  x1  x 2 и т.д. Формулу: P  x1  x2  x1  x2 реализует следующая релейно-контактная схема P x x 1 1 2 x1 x2 2 Пояснительная релейно-контактная схема Проанализируем работу схемы. В линиях 1 и 2 по одинаковой схеме включены контакты реле x1 и x2. В результате линии дублируют друг друга. Следовательно, любая их них может быть исключена без изменения логики работы схемы P x x 1 2 Для полученной схемы можно записать P  x1  x2 . Таким образом, x1  x2   x1  x2    x1  x2   x1  x2 Реализуем ФАЛ вида y  f  f , где f  x1  x 2 . Функцию f реализуем на элементе конъюнкции так, как представлено на рисунке x2 & Логическая схема f  x1  x2 x1 Выходной сигнал элемента конъюнкции представляет собой f , которая будет подвергаться операции тавтологии y  f  f , следовательно, выход элемента надо подключить к входам двухвходового элемента дизъюнкции, так как показано на рисунке 17 x2 & 1 f y  x1  x 2  x1  x 2 x1 Комментарий Проанализируем работу элемента дизъюнкции. Из всех наборов, перечисленных в табл.5, данный элемент работает только на двух наборах: – при формировании на выходе элемента конъюнкции сигнала f  1 на его входы поступает (1,1), а на выходе формируется y  1; – при формировании на выходе элемента конъюнкции сигнала f  0 на его входы поступает (0,0), а на выходе формируется y  0. Таким образом, элемент дизъюнкции просто повторяет сигнал f , а, следовательно, его можно исключить, не меняя логики работы схемы. Значит, x1  x 2  ...  x1  x 2  x1  x 2 Многократное логическое сложение одной и той же переменной (ФАЛ) в результате даёт ту же переменную (ФАЛ) 7. ФАЛ от прямых и инверсных значений (дизъюнкция) Общий вид x x 1 аналитической записи Подставим вместо переменной x некоторую ФАЛ f , получим f  f  1 . В качестве f может быть любая ФАЛ. Если ФАЛ, Аналитическая запись например, имеет вид: при суперпозиции ФАЛ а) f  x1  x 2 , то справедлива запись x1  x2   x1  x2  1 Примечание: инверсия имеет приоритет, аналогичный скобкам б) f  x1  x 2 , то справедлива запись x1  x2  x1  x2  1 и т.д. Формулой P  x  x может быть описана следующая релейноконтактная схема P 1 x 2 x Пояснительная релейно-контактная схема Проанализируем схему. Обмотка реле Р будет находиться под током как в случае нахождения реле х под током (замкнут фронтовой контакт), так и при обесточенном реле х (замкнут тыловой контакт). Таким образом, независимо от состояния реле х реле Р всегда будет под током (процесс перелёта контактов не рассматривается). Следовательно, оба контакта реле можно исключить, заменив их проводником 1 P Для полученной схемы можно записать следующее выражение: 18 P  1 . Таким образом, x  x  1 ФАЛ вида y  x  x на логических элементах реализуется так x 1 yx x Проанализируем работу логического элемента. Как видно, из всех возможных наборов входных сигналов, в дизъюнкции Логическая схема участвуют только наборы (0,1) и (1,0), то есть на один из входов элемента всегда будет поступать логическая единица. Вместе с тем, из табл.5 следует, что при равенстве единице значения хотя бы одной из переменных результат дизъюнкции также будет равен единице. Следовательно, выходной сигнал логического элемента всегда будет y  1 . Таким образом, x  x  1 . Аналогичный результат будет, если вместо переменных использовать ФАЛ (суперпозиция ФАЛ). Результат логического сложения противоположных значений Комментарий переменных равен единице. 8. ФАЛ от прямых и инверсных значений (конъюнкция) Общий вид xx0 аналитической записи Подставим вместо переменной x некоторую ФАЛ f , получим f  f  0 . В качестве f может быть любая ФАЛ. Если ФАЛ, Аналитическая запись например, имеет вид: при суперпозиции ФАЛ а) f  x1  x 2 , то справедлива запись x1  x2   x1  x 2  0 ; б) f  x1  x2 , то справедлива запись x1  x2  x1  x2  0 и т.д. Формулу P  x  x реализует следующая релейно-контактная схема P x x Пояснительная релейно-контактная схема Проанализируем схему. Обмотка реле Р никогда не будет под током, поскольку при замыкании фронтового контакта реле х цепь питания обмотки реле P будет разрывать тыловой, а при замыкании тылового – фронтовой. Следовательно, данную линию можно удалить, заменив разрывом цепи, при этом логика работы схемы не изменится. Логическая схема P Для полученной схемы можно записать следующее выражение: P  0 . Таким образом, x  x  0 ФАЛ вида y  x  x на логических элементах реализуется так 19 x & Комментарий y  x x Проанализируем работу логического элемента. Как видно, из всех возможных наборов входных сигналов, в конъюнкции участвуют только наборы (0,1) и (1,0). Вместе с тем, из табл.5 следует, что единица на выходе логического элемента формируется только при наличии на всех входах логических единиц. Поскольку комбинация (1,1) на входы логического элемента никогда не поступит, то, его выходной сигнал всегда будет y  0 . Таким образом, x  x  0 . Аналогичный результат будет, если вместо переменных использовать ФАЛ (суперпозиция ФАЛ). Результат логического умножения противоположных значений переменной равен нулю. 9. Закон двойной инверсии Общий вид аналитической записи xx Подставим вместо переменной x некоторую ФАЛ f , получим f  f . В качестве f может быть любая ФАЛ. Например, если Аналитическая запись при суперпозиции ФАЛ ФАЛ имеет вид f  x1  x2   x3 , то справедливо x1  x2   x3  x1  x2   x3 и т.д. Для реализации формулы P  x в виде релейно-контактной схемы воспользуемся принципом суперпозиции, для чего введём некоторую ФАЛ P /  x , тогда P  x  P / . Инверсию x будет реализовывать вспомогательное реле P / , а реле P будет реализовывать инверсию сигнала реле P / . Схема имеет следующий вид. P/ x P/ Пояснительная релейно-контактная схема P Проанализируем работу схемы. Когда реле х под током, цепь питания обмотки реле Р/, будет разорвана, но своим тыловым контактом реле Р/ будет обеспечивать питание реле Р. Если реле х обесточено, то цепь питания обмотки реле Р/ замкнута и обмотка реле Р/ находится под током, в то же время тыловой контакт реле разрывает цепь питания обмотки реле Р. Таким образом, реле Р/ работает в противофазе и реализует инверсию х, а реле Р работает в противофазе по отношению к реле Р/ и, следовательно, в одной фазе по отношению к реле х. Поэтому, два тыловых контакта, участвующих в включении реле Р можно исключить, заменив их одним фронтовым. Для полученной схемы можно записать следующее выражение: 20 x P P  x . Таким образом, x  x . Для реализации ФАЛ вида y  x воспользуемся элементами ИНЕ. Когда оба входа элемента И-НЕ (ИЛИ-НЕ) объединены, он реализует инверсию входного сигнала, это несложно выяснить, воспользовавшись табл. 5. Так как один элемент реализует одну инверсию, то для реализации двойной инверсии последовательно с ним включим еще один такой же элемент. Логическая схема имеет вид. Логическая схема Комментарий Общий вид аналитической записи Аналитическая запись при суперпозиции ФАЛ x & y/  x & y  y/  x Проанализируем работу полученной схемы. Пусть на входе x  1 , тогда на выходе первого логического элемента будет формироваться сигнал y /  0 . Выходной сигнал первого элемента является входным сигналом второго, следовательно, на выходе второго элемента y  1 , то есть повторяет входной сигнал x . Таким образом, пары последовательно включённых инверторов можно исключать из схемы, заменяя их проводником. Результат двойной инверсии переменной равен самой переменной Законы для двух и более переменных 1. Переместительный закон x1  x2  x2  x1 ; x1  x2  x2  x1 В соответствии с принципом суперпозиции любую из переменных или все можно заменить ФАЛ. Например, заменим переменную x1 некоторой ФАЛ f , получим f  x 2  x 2  f . Пусть f  x1  x2 тогда тождество имеет вид x1  x2  x2  x2  x1  x2 и т.д. Пояснительная релейно-контактная схема Формулы P1  x1  x 2 и P2  x 2  x1 реализуют следующие схемы 21 1 P1 x2 2 P2 x1 1 2 x1 x2 Очевидно, что обе схемы работают одинаково вне зависимости от того, к какой из параллельных линий подключён каждый из ключей, следовательно P1  P2 . Входные сигналы к логическому элементу дизъюнкции могут быть подключены в любом порядке, поэтому обе приведённые ниже схемы работают одинаково Логическая схема x2 x2 1 Общий вид аналитической записи f  x1  x 2 x1 x1 Комментарий 1 f  x1  x 2 От перемены мест аргументов дизъюнкции (конъюнкции) результат не меняется. 2. Сочетательный закон Перечисленные операции могут выполняться в любой последовательности x1  x2  x3  x1  x2  x3   x1  x2   x3 ; x1  x2  x3  x1  x2  x3   x1  x2   x3 ; x1  x2  x3  x4  x1  x2  x3   x4  x1  x2   x3   x4   x1  x2   x3  x4   x1  x4   x2  x3   ... Если вместо переменных аргументами выражения являются ФАЛ: x1  f1  x1  x2 , x 2  f 2  x 2 , x3  f 3  x2  x1 , то сочетательный закон может быть представлен в следующем Аналитическая запись виде: при суперпозиции ФАЛ x1  x2  x 2  x2  x1   x2  x2  x1   x1  x 2     x2  x1  x2  x1  x2 В качестве аргументов в выражении могут быть любые ФАЛ. Реализуем формулу P  x1  x2  x3 . Операция x1  x 2 должна выполняться в первую очередь. Во вторую очередь следует осуществлять конъюнкцию между результатом операции / P  x1  x2 и переменной x3 . Следовательно, схема реализации Пояснительная релейно-контактная схема ФАЛ P  x1  x2  x3  P /  x3 будет иметь следующий вид 22 x1 x2 P/ x3 P/ P Формулу P  x1  x2  x3 реализуем аналогично, но P /  x1  x3 x1 x3 P/ x2 P/ P Аналогичным образом можно реализовать формулу P  x2  x3  x1 . Промежуточный результат будет представлять ФАЛ P /  x2  x3 . x2 x3 P/ x1 P/ P Формулу P  x1  x2  x3 , поскольку в ней отсутствует приоритет операций, реализуем последовательным включением фронтовых контактов реле. x1 x2 x3 P Проанализировав перечисленные схемы на всех возможных наборах переменных, можно увидеть, что обмотка реле P во всех схемах будет под током только в случае, если x1  x2  x3  1. Следовательно, x1  x2  x3  x1  x2  x3   x1  x2   x3 При построении логической схемы ФАЛ y  x1  x2   x3  x4 , сначала на логических элементах получают ФАЛ промежуточных результатов (от вычисления значений переменных в скобках): f1  x1  x2 и f 2  x3  x4 , а затем к их выходам присоединяют входы элемента выполняющего заключительную операцию: y  f1  f 2 Логическая схема x1  f1  x1  x2 x2 x3   y  f1  f 2 f 2  x3  x4 x4 y  x1  x2   x3  x4  Аналогично построим логическую схему, реализующую ФАЛ вида y  x1  x2  x3   x4 23 x1 x2   f2  f1 y x3 x4 f 1  x 2  x3 f 2  x1  f1  x1  x2  x3  y  f2  x4  x1  x2  x3   x4 Логическая схема, реализующая ФАЛ y  x1  x2  x3  x4 представляет собой многовходовый сумматор по модулю два x1  x2 y x3 x4 Комментарий Общий вид аналитической записи Воспользовавшись табл.5 и подставив значения аргументов из любого набора можно легко убедиться, что все синтезированные логические схемы дают одинаковый результат. Следовательно, благодаря сочетательному закону, логический элемент на любое число входов может быть получен с использованием двухвходовых. Порядок выполнения элементарных дизъюнкций, конъюнкций, операций суммирования по модулю 2 на результат не влияет. 3. Распределительный закон x1  x2  x3   x1  x2  x1  x3 ; x1  x2  x3  x1  x2   x1  x3  Произведём замену xi  f i , получим f1  f 2  f 3   f1  f 2    f1  f 3 . ФАЛ в выражении могут быть Аналитическая запись любыми, например, пусть f1  x1  x2  x3 , f 2  x2 , f 3  x3 , тогда при суперпозиции ФАЛ справедливо следующее равенство: x1  x2  x3  x2  x3  x1  x2  x3  x2  x1  x2  x3  x3 и т.д.  Пояснительная релейно-контактная схема   Если формула x1  x2  x3   x1  x2  x1  x3 совпадает с принятыми в обычной алгеброй правилами, то справедливость формулы x1  x2  x3  x1  x2   x1  x3  неочевидна. Чтобы доказать равенство, синтезируем релейно-контактные схемы для левой и правой частей равенства, а затем проанализируем их. 24 Формулу P  x1  x2  x3 , контактная схема: x2 реализует следующая релейно- P x3 x1 Формулу P  x1  x2   x1  x3   f1  f2 схема вида: f1 x2 f2 x1 реализует контактная P x3 x1 Легко увидеть, что в обеих схемах обмотка реле Р окажется под током только в случаях, если x2  x3  1 независимо от состояния x1 или, если x1  1 , независимо от состояний x 2 и x3 . Следовательно, выражение x1  x2  x3  x1  x2   x1  x3  справедливо, а контактные схемы эквивалентны. Построим логическую схему, реализующую ФАЛ y  x1  x2  x3 . Поскольку при выполнении логических операций конъюнкция имеет приоритет перед дизъюнкцией, то сначала следует реализовать на логическом элементе конъюнкции некоторую промежуточную ФАЛ f1  x2  x3 , а затем на втором логическом элементе реализовать дизъюнкцию сигнала первого элемента f 1 и сигнала x1 : y  x1  f1 x1 Логическая схема x2 1 & y f1 x3 Построим логическую схему, реализующую ФАЛ y  x1  x2  x1  x3  . При построении логической схемы сначала, на логических элементах следует реализовать ФАЛ промежуточных результатов f1  x1  x 2 и f 2  x1  x3 , а затем реализовать конъюнкцию выходных сигналов y  f1  f 2 25 x3 1 f2 & x1 1 y f1 x2 Комментарий Общий вид аналитической записи Обе синтезированные схемы эквивалентны, что легко проверить, воспользовавшись таблицами истинности (табл. 5) логических элементов. – 4. Закон поглощения x1  x1  x 2  x1 ; x1   x1  x 2   x1 Произведём замену xi  f i в выражении x1  x1  x 2  x1 , получим f1  f1  f 2  f1 . Поскольку ФАЛ в формуле могут быть Аналитическая запись f1  x1  x2 и f 2  x1  x 2 при суперпозиции ФАЛ любыми, то, например, при справедливым будет и выражение вида: x1  x2  x2  x1  x2   x1  x1  x2 и т.д. а) Выясним справедливость равенства x1  x1  x 2  x1 . Для этого P  x1  x1  x2 . построим схему, реализующую ФАЛ Конъюнкция в релейно-контактных схемах осуществляется последовательным соединением ключей, а дизъюнкция – параллельным. Кроме того, конъюнкция имеет приоритет перед дизъюнкцией, следовательно, дизъюнкция в выражении будет осуществляться с результатом выполнения конъюнкции, т.е. P  x1  f1 , где f1  x1  x2 . Таким образом, релейно-контактная схема приобретает вид: 1 Пояснительная релейно-контактная схема x2 x1 P 2 x1 Легко заметить, что, если фронтовой контакт x1 разомкнут, то обмотка реле никогда не будет под, током, если же он замкнут, то реле оказывается под током независимо от положения контакта x 2 . Следовательно, линию 1 можно изъять, не изменяя результата работы схемы. Окончательно схема приобретает вид: x1 P Она может быть описана выражением P  x1 . Таким образом, левая и правая части равенства действительно эквивалентны 26 x1  x1  x 2  x1 б) Для доказательства справедливости равенства x1   x1  x 2   x1 рассуждая аналогичным образом, построим релейноконтактную схему, реализующую ФАЛ P  x1  x1  x 2  x1 P 1 x1 2 x2 Анализируя данную схему, легко увидеть, что обмотка реле P будет под током только в случае, если замкнут ключ x1 , но если он замкнут, то ключ x 2 оказывается зашунтированным, и его положение на работу реле не влияет, если ключ x1 разомкнут, то ключ x 2 тоже обесточен и его положение также не влияет на питание обмотки реле Р. Рассуждения при построении логической схемы аналогичны рассуждениям при построении релейно-контактной схемы. а) Реализуем функцию y  x1  x1  x2 . Поскольку в выражении присутствуют две операции, конъюнкция и дизъюнкция, и конъюнкция имеет приоритет, то сначала на логическом элементе конъюнкции реализуется логическое умножение входных сигналов f  x1  x 2 , а затем на элементе дизъюнкции реализуется логическая сумма входного сигнала x1 и выходного сигнала f 1 x2 & Логическая схема f1 1 x1 y Как следует из закона x1  x1  x 2  x1 (это можно проверить на основе анализа работы схемы с использованием таблицы истинности (табл. 5)), полученная схема может быть полностью исключена, поскольку её работа сводится к повторению на выходе y значения входного сигнала x1 . При этом входной сигнал x1 и выходной y следует соединить между собой проводником. x1 y б) Аналогично построим логическую схему y  x1   x1  x 2  . 27 для ФАЛ x2 1 f1 & x1 Комментарий y Работа данной схемы также сводится к повторению на выходе y значения входного сигнала x1 и также может быть заменена проводником. – 5. Закон склеивания   а) x1  x2  x2  x1  x2 ; б) x1  x2  x2  x1  x2 ; Общий вид аналитической записи в) x1  x2  x1  x2  x1 ;   г) x1  x2   x1  x2  x1 Примечание: формулы склеивания (в) и (г) наиболее часто используют при минимизации ФАЛ в дизъюнктивной и конъюнктивной нормальных формах соответственно. Произведём замену xi  f i в выражении x1  x2  x2  x1  x2 , получим f1  f 2  f 2  f1  f 2 . Поскольку ФАЛ в формуле могут быть любыми, то, например, при f1  x1  x2 и f 2  x1  x 2 Аналитическая запись справедливым будет выражение вида: при суперпозиции ФАЛ x1  x2  x1  x2  x1  x2  x1  x2  x1  x2 и т.д. Примечание: Поскольку инверсия имеет приоритет перед другими операциями, то выражение x1  x2 заключать в скобки не требуется. Выясним справедливость равенства x1  x2  x2  x1  x2 . Для Пояснительная релейно-контактная схема этого синтезируем схему, реализующую ФАЛ P  x1  x2  x2 . При построении учтём следующее. Формула содержит три операции: инверсию, дизъюнкцию и конъюнкцию. Приоритеты операций распределяются в порядке убывания так: инверсия, конъюнкция и дизъюнкция. Операция инверсии входного сигнала x 2 осуществляется подключением вместо фронтового – тылового контакта. Схема имеет вид: 1 x2 x1 P 2 x2 Если проанализировать схему, то можно выяснить, что единственная ситуация при которой обмотка реле Р будет обесточена, когда x1  x2  0 . В остальных случаях она будет под током. Следовательно, таблица истинности данной схемы полностью совпадает с таблицей истинности двухвходового 28 элемента ИЛИ, равенство справедливо x1  x2  x2  x1  x2 , а данная схема эквивалентна приведенной ниже: P x1 x2 Аналогично можно доказать справедливость остальных формул склеивания. Например, формулу P  x1  x2   x1  x2 реализует следующая релейно-контактная схема:  1 x1 x2 x1 x2  P 2 Легко заметить, что при замыкании фронтового контакта реле x1 ( x1  1 ), и любом состоянии реле x 2 ток будет поступать в обмотку реле Р либо по линии 1, либо по линии 2. Следовательно, состояние обмотки реле не зависит от состояния реле x 2 и его контакты можно исключить, заменив проводником. P x1 x1 Воспользовавшись законом тавталогии можно удалить дублирующие контакты реле x1 . В результате схема приобретает вид: P x1 Полученная схема  описывается  Следовательно, x1  x2   x1  x2  x1 и т.д. Логическая схема формулой:   P  x1 Построим логическую схему для ФАЛ y  x1  x2  x2 . Данная формула содержит три операции, которые необходимо выполнять в следующем приоритете: инверсия переменной, дизъюнкция, конъюнкция. Обозначим ФАЛ промежуточных результатов как: f1  x2 , f 2  x1  f1 , тогда логическая схема имеет вид: 29 x1 1 x2 1 f2 f1 & y В соответствии с законом слеивания (можно проверить независимо, построив таблицу истинности для данной схемы), полученная схема эквивалентна одному элементу конъюнкции y  x1  x 2 x1 & y x2 Комментарий – 6. Закон инверсии (закон де Моргана) Общий вид аналитической записи а) x1  x2  x3  ...  xn  x1  x2  x3  ... xn б) x1  x2  x3  ... xn  x1  x2  x3  ...  xn В выражении x1  x2  x1  x2 произведём замену переменной на ФАЛ xi  f i , получим f1  f 2  f1  f 2 . Поскольку ФАЛ в формуле могут быть любыми, то, например, при f1  x1  x2 и Аналитическая запись при суперпозиции ФАЛ f 2  x1 можно записать: x1  x2  x1  f1  f 2  x1  x2  x1 Воспользовавшись законом двойной инверсии (пара инверсий, изображённых чертой одной длины и расположенных друг под другом взаимно уничтожаются) упростим выражение и окончательно получим равенство в следующем виде: x1  x2  x1  x1  x2  x1 и т.д. Выясним справедливость равенства x1  x2  x1  x2 . Для этого синтезируем схемы, реализующие ФАЛ из левой и правой частей равенства: P1  x1  x2 и P2  x1  x2 . Пояснительная релейно-контактная схема Формула P1  x1  x2 содержит две операции: конъюнкцию и инверсию. Поскольку инверсия охватывает знак операции конъюнкции и переменные, участвующие в конъюнкции (края черты аналогичны паре скобок), то она осуществляется с результатом выполнения конъюнкции P /  x1  x2 , то есть во вторую очередь P1  P / . Реализующая формулу релейноконтактная схема имеет вид: 30 x1 P/ x2 P/ P1 Формула P2  x1  x2 содержит три операции, две инверсии и одну дизъюнкцию. Инверсии не охватывают знак дизъюнкции, значит, они должны быть выполнены ранее, чем операция дизъюнкции. Таким образом, сначала следует получить инверсные значения отдельных переменных x1 и x2 , а затем осуществить их логическое сложение. Чтобы изменить значение простой переменной (не ФАЛ !!!!, а одного входного сигнала) достаточно вместо фронтового использовать тыловой контакт, а чтобы логически сложить, достаточно соединить их параллельно (см. табл.5), тогда релейно-контактная схема имеет вид: x1 P2 x2 Если проанализировать работу обеих схем, то легко заметить, что обмотки реле Ð1 и Ð2 будут обесточены, только в случае, когда x1  x2  1 , а в остальных случаях будут под током. Следовательно, обе схемы эквивалентны, а равенство x1  x2  x1  x2 справедливо. Аналогично можно показать справедливость равенства x1  x2  x3  ...  xn  x1  x2  x3  ... xn Логическая схема Построим логическую схему для ФАЛ y1  x1  x2 . Рассуждения при построении логической схемы аналогичны рассуждениям, использовавшимся нами при построении релейно-контактной схемы. Таким образом, сначала на логическом элементе следует реализовать конъюнкцию сигналов x1 и x 2 , а результат выполнения операции инвертировать. Данная последовательность операций реализуется одним логическим элементом – И-НЕ (ФАЛ «штрих Шеффера») (см. обозначения, принятые при изображении логических элементов). x1 & y1 x2 Построим логическую формула также может элементом. Поскольку следует инвертировать 31 схему для ФАЛ y2  x1  x2 . Данная быть реализована одним логическим до выполнения операции дизъюнкции значения переменных, то логический элемент имеет вид (см. обозначения, принятые при изображении логических элементов): x1 1 y2 x2 Если построить таблицы истинности для обоих логических элементов, то можно увидеть, что они идентичны, то есть оба логических элемента реализуют одну и ту же ФАЛ. Следовательно, дизъюнкция инверсных значений входных сигналов, аналогична инверсии выходного сигнала после конъюнкции входных сигналов. Поскольку, инверсия входного сигнала любого логического элемента может быть заменена инверсией выходного сигнала предыдущего логического элемента (того, выход которого подключён к входу данного), а двойная инверсия эквивалентна неинверсному значению переменной, то логическая схема для ФАЛ y 2 может быть представлена на элементах одного вида следующим образом: x1 1 x1 1 x2 Комментарий 1 y2 1 y2 x2 Данная схема полностью собрана на элемента ИЛИ-НЕ. Она может быть заменена одним элементом И-НЕ. Оба перечисленных элемента относят к базисным (образующим минимальный базис), т.е. тем элементам, соединив которые определённым образом можно реализовать любую ФАЛ. Конъюнкция инверсных значений переменных эквивалентна инверсии дизъюнкции тех же переменных. Дизъюнкция инверсных значений переменных эквивалентна инверсии конъюнкции тех же переменных. Использование закона де Моргана позволяет преобразовывать любые ФАЛ к определённому базису: И, ИЛИ, НЕ; И-НЕ; ИЛИНЕ. Обозначения, принятые при изображении логических элементов Пусть логический элемент имеет вид, представленный на рис. 7. 32 Рисунок 7 Входы у любого логического элемента всегда располагают слева, а выход (ды) – справа. Окружностью у основания вывода « » обозначается инверсия соответствующего сигнала. Инверсия может осуществляться с входными и (или) выходными сигналами. Например, у логического элемента, изображённого на рис. Есть инверсия входного сигнала x 2 и выходного сигнала, который преобразуется в сигнал y . Последовательность преобразования логических сигналов элементом всегда обозначается одинаково. Она следующая: 1) Сначала логические сигналы поступают на входы логического элемента (см. рис. 7). Если на входах имеется инверсия, то соответствующие сигналы преобразуются в инверсные (см. рис. пунктирная область №1). Например, изображённый на рис. 7 элемент имеет инверсию сигнала x 2 , поэтому в последующих операциях вместо x 2 , будет участвовать промежуточный сигнал x2/  x2 . Для удобства можно в таблицу истинности логического элемента ввести ещё один столбик в котором записать соответствующие значения сигнала x 2/ : Таблица 11 x1 x2 x2/  x2 1 1 1 1 1 1 Сигнал x1 остаётся неизменным, поскольку инверсии на его входе нет. 2) Далее с преобразованными сигналами выполняется операция, которая обозначена внутри прямоугольника (см. рис. пунктирная область №2). Например, представленный на рисунке логический элемент реализует операцию «дизъюнкция» (см. табл. 11), причём аргументами для данной операции будут сигналы x1 и x 2/ . Обозначим результат операции символом r , причём r  x1  x2/ . Заполним ещё один столбик таблицы истинности элемента: Таблица 12 x2 x1 x2/  x2 33 r 1 1 1 1 1 1 1 1 1 При заполнении таблицы используем таблицу истинности элемента «дизъюнкция» (см. табл. 12). Поскольку переменная x 2 не участвует в операции, соответствующий столбец обозначен пунктиром. 3) Если имеется инверсия на выходе, то результат выполнения предыдущей операции следует инвертировать y  r . Если на выходе нет инверсии, то y  r , то есть дополнительных преобразований не требуется. Поскольку в нашем примере имеется инверсия на выходе логического элемента (см. рис. пунктирную область №3), то y  r . Запишем в таблице истинности ещё один столбец y . Значения этого столбика заполним по таблице истинности элемента отрицания (см. табл. 13), где в качестве аргументов будут использованы значения столбика r . Таблица 13 x2 x1 x2/  x2 r y 1 1 1 1 1 1 1 1 1 1 4) Так как входными сигналами для изображённого на рисунке логического элемента являются x1 и x 2 , а выходным – y , в то время как сигналы x 2/ и r символизируют промежуточные преобразования внутри логического элемента, то, вычеркнув столбики промежуточных преобразований, получим таблицу истинности 14 элемента в окончательном виде: Таблица 14 x2 x1 y 1 1 1 1 1 Она описывает взаимосвязь между входными сигналами элемента и выходным сигналом. Теперь, воспользовавшись принципом суперпозиции, выведем аналитическое выражение, задающее ФАЛ элемента, изображённого на рисунке. 34 В результате преобразования (1) была получена ФАЛ, после преобразования (2) была получена ФАЛ r  x1  x2/ , а после преобразования (3) – y  r . Произведем последовательные подстановки. Подставив x2/  x2 в r  x1  x2/ , получим r  x1  x2 , затем, подставив r  x1  x2 в y  r получим аналитическое выражение ФАЛ описывающее взаимосвязь выходного сигнала изображённого на рисунке логического элемента y с входными сигналами x1 и x 2 : y  x1  x2 . Проанализируем полученную формулу. Формула содержит несколько элементарных преобразований: две инверсии и одну дизъюнкцию. В ней же указан порядок выполнения логических операций, который может быть определен на основе следующих правил: 1. инверсия имеет приоритет перед другими операциями, аналогичный скобкам; 2. инверсия, обозначенная более короткой чертой, имеет приоритет перед инверсией, обозначенной более длинной чертой; 3. инверсия, охватывающая чертой другие логические операции, выполняется после выполнения этих операций. Для удобства восприятия последовательности операций мысленно выделим части выражения, охваченные чертой соответствующей инверсии парами скобок, это позволит наглядно увидеть в какой последовательности должны выполняться действия в приведенной формуле: y  x1  x 2  . Итак, сначала требуется инвертировать значение переменной x 2 . Перед выполнением следующей инверсии необходимо выполнить дизъюнкцию, поскольку инверсия охватывает чертой операцию дизъюнкции и участвующие в ней аргументы. В последнюю очередь результат нужно инвертировать. Если сопоставить последовательность аналитических и табличных преобразований, то можно заметить, что она одинакова, а, следовательно, формула y  x1  x2 полностью соответствует полученной для логического элемента таблице истинности (табл. 14). Это легко проверить подстановкой значений переменных. Например, возьмём следующий набор переменных x2  1 , а x1  0 .   Подставим значения в формулу: y  0  1 . Выполним инверсию, обозначенную более короткой чертой, получим: y  0  0 . Выполним дизъюнкцию y  0 . Выполним оставшуюся инверсию y  1 . Полученный результат совпадает, со значением функции y , записанным в таблице истинности (табл. 14) для данного набора переменных. Аналогично можно проверить соответствие аналитически заданной ФАЛ с табл. 14 на остальных наборах. Набор аргументов, на котором макстерм принимает своё единственное нулевое значение совпадает с набором аргументов, на котором ФАЛ, заданная таблицей истинности (картой Карно), принимает одно из своих нулевых значений. 35 Задача получения КСНФ может быть разделена на три этапа, аналогичных этапам получения ДСНФ: 1. – определение количества макстермов; 2. – определение аналитического выражения для каждого макстерма; 3. – составление выражения КСНФ. Определение количества макстермов. В общем случае КСНФ содержит столько макстермов l , сколько нулей содержится в столбце значений функции таблицы истинности (в ячейках карты Карно). Например, для ФАЛ заданной таблицей истинности (табл.1) при записи КСНФ необходимо использовать три макстерма, т.е.: f 0   1   2   3 (21) Как видно из сравнения соотношений (20) и (21) количество минтермов и количество макстермов при описании одной и той же ФАЛ в общем случае различно. Определение аналитического выражения для каждого из макстермов. Аналитическое выражение для каждого макстерма получают так. Сначала вводят аналитические выражения для значений переменных, входящих в набор. При этом, если в таблице истинности значение переменной xi равно единице xi  1 , то записывают x i , если же значение переменной равно нулю xi  0 , то записывают xi . Важно отметить, что аналитические выражения для переменных, входящих в макстерм инверсны по отношению к аналитическим выражениям переменных, входящих в минтерм. Аналитическое выражение макстерма представляет собой дизъюнкцию (логическое сложение) аналитических выражений значений переменных, входящих в набор, на котором значение макстерма должно быть равно нулю. Например, макстерм  1 единственный ноль у которого будет получаться на наборе № 0 табл. 1, имеет вид: f1  x3  x2  x1 (табл. 15), макстерм f 2 , единственная единица у которого будет формироваться на наборе № 4 – f 2  x3  x2  x1 и т.д. 36 Пример построения таблицы истинности: Рассмотрим последовательность построения таблицы истинности, описывающей функционирование некоторого дискретного устройства, например, схемы, содержащей три ключа и обмотку реле. Схема их соединения приведена на рисунке 8. Рисунок 8 а) При построении таблицы истинности в первую очередь необходимо определить количество столбцов в ней. Для этого можно воспользоваться следующей формулой: x nm где n – количество входных переменных; m – количество выходных ФАЛ; Можно в таблицу истинности добавить ещё один столбец, в который будет служить для нумерации двоичных наборов переменных в десятичной системе, хотя это и не обязательно. Проанализируем схему (рис. 8). Нетрудно заметить, что состояние обмотки реле y в схеме определяется совокупностью состояний ключей x1 , x2 , x3 , каждый из которых может иметь два положения: замкнут – пропускает ток или разомкнут – ток не пропускает. Если учесть также, что для обмотки реле y в данном примере возможны только два состояния: «под током» и «без тока», то, как следует из приведённого выше определения, реле 37 вместе со схемой реализует некоторую ФАЛ. Поскольку в схеме только одно реле, включаемое или отключаемое от источника тока при различных комбинациях положений ключей, то реализуется всего одна ФАЛ, значит m  1 . Количество входных переменных для ФАЛ y определяется количеством ключей, включенных в цепь питания обмотки реле, то есть n  3 . Итак, таблица истинности должна содержать x  5 столбцов, при условии наличия столбца номеров наборов переменных и x  4 при его отсутствии. № набора x1 x2 x3 y б) После того, как определено количество столбцов в таблице истинности ФАЛ, необходимо определить количество строк. Количество строк в таблице равно количеству уникальных (неповторяющихся) наборов переменных, которое можно определить по формуле (1). При этом строка заголовка не учитывается. Поскольку у данной ФАЛ n  3 , то количество строк равно N  2 3  8 . Номера наборов в таблице истинности заполним от нуля до N. № набора 1 2 3 4 5 6 7 x1 x2 x3 y в) Теперь необходимо перечислить все уникальные наборы входных переменных ФАЛ. Последовательность заполнения такая. Обычно, сначала заполняется самый правый столбец входных переменных ФАЛ. При этом в соседних двух ячейках столбца чередуют ноль и единицу. Начинают заполнение от нуля, который проставляется в ячейке столбца, расположенной в строке с набором № 0. г) Остальные столбцы таблицы истинности заполняются таким образом, чтобы в каждом последующем столбце группы ячеек с нулями и единицами были в два раза больше чем в предыдущем. Причем ячейки всех столбцов, относящиеся к строке набора № 0, обязательно заполняют нулями. При правильном заполнении всех столбцов самая верхняя ячейка каждого столбца должна содержать «0», а самая нижняя – «1», причём, в 38 последнем заполненном столбце верхняя половина наборов должна содержать нули, а нижняя – единицы. д) Далее условимся, что под состоянием любого ключа схемы «0» будем понимать его разомкнутое состояние, то есть состояние, когда он не пропускает ток, а под состоянием «1» – его замкнутое состояние. Аналогично будем считать, что в состоянии «1» обмотка реле y находится под током, а в состоянии «0» – обесточена. Тогда, непосредственно анализируя схему, можно заполнить столбец y таблицы истинности. Рассуждения при этом можно строить следующим образом. Если x1  0 , значит ключ x1 разомкнут; x2  1 , значит ключ x 2 замкнут; x3  1 , значит ключ x 3 замкнут, то y  1 , то есть цепь питания обмотки реле находится под током. Следовательно, в ячейке, соответствующей набору № 3 следует записать «1». № набора 1 2 3 4 5 6 7 x1 x2 x3 1 1 1 1 1 1 1 1 1 1 1 1 y 1 Рассуждая аналогичным образом, можно заполнить все остальные ячейки столбца f . Окончательно, таблица истинности для схемы, приведенной на рис. 3, имеет вид: № набора x1 x2 39 x3 y 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Примечание: Если в схеме используются контактные тройники реле, то принято считать, что при включении тройника в схему с использованием фронтового контакта (замыкается, если обмотка реле под током), соответствующая переменная имеет прямое значение xi , если же тройник включён тыловым контактом (замыкается, если обмотка реле обесточена), то соответствующая переменная имеет инверсное значение. Обозначается инверсия чертой над переменной x i . Полученная ФАЛ описывает функционирование только схемы, приведённой на рис. 8. Очевидно, что при иной схеме соединения ключей реле y будет реализовывать другую ФАЛ. Количество которых может быть достаточно велико. Лекция 3 Минимизация функций алгебры логики Пусть функционирование некоторой комбинационной схемы описано таблицей истинности. Одной и той же таблице истинности, как правило, могут соответствовать несколько различных аналитических выражений. Так, например, таблице истинности (см. табл. 10), соответствуют следующие выражения: Таблица 16   f 2  x1  x2  x2  x2  x1 ; f 3  x1  x 2  x1 ; f 4  x2  x1  x2 ; f 5  x 2  x1 . f1  x1  x2  x1  x2  x1  x2 ; № набора x2 x1 y 1 2 3 1 1 1 1 1 1 1 Это легко проверить непосредственной подстановкой в формулы значений переменных из всех наборов и вычислением значений функций. Для примера произведём подстановки в функции f1 , f 3 , f 5  – набор №0 ( x1  x 2  0 ): 40 f1  x1  x2  x1  x2  x1  x2  0  0  0  0  0  0  1  1  0  1  1  0  1  0  0  1 ; f 3  x1  x 2  x1  0  0  0  1  1  0  1  0  1 ; f 5  x 2  x1  0  0  1  1  1 ;  – набор №1 ( x 2  0 , x1  1 ): f1  x1  x2  x1  x2  x1  x2  1  0  1  0  1  0  0  1  1  1  0  0  0  1  0  1; f 3  x1  x 2  x1  1  0  1  0  1  1  0  1  1 ; f 5  x 2  x1  0  1  1  0  1 ;  – набор №2 ( x 2  1 , x1  0 ): f1  x1  x2  x1  x2  x1  x2  0  1  0  1  0  1  1  0  0  0  1  1  0  0  1  1; f 3  x1  x 2  x1  0  1  0  1  0  0  1  0  1 ; f 5  x 2  x1  1  0  0  1  1 ;  – набор №3 ( x 2  1 , x1  1 ): f1  x1  x2  x1  x2  x1  x2  1  1  1  1  1  1  0  0  1  0  0  1  0  0  0  0 ; f 3  x1  x 2  x1  1  1  1  0  0  1  0  0  0 ; f 5  x 2  x1  1  1  0  0  0 . Для каждого из аналитических выражений может быть синтезирована реализующая его комбинационная схема. Следовательно, может быть синтезировано множество различных комбинационных схем, которые описываются одной и той же таблицей истинности, но отличаются друг от друга входящими в них логическими элементами, их количеством и сложностью взаимосвязей между ними. Так как каждому символу аналитического выражения ФАЛ в контактной схеме, как правило, соответствует один контакт, а каждому оператору в логической схеме – один логический элемент, то очевидно, что сложность комбинационной схемы реализующей ту или иную ФАЛ, помимо прочего зависит от сложности её аналитического выражения (количества символов и операторов, входящих в выражение). Если учесть, что чем схема проще, тем экономичнее (дешевле изготовить, меньше расходы на эксплуатацию), то насущной становится задача максимального упрощения реализующих ФАЛ схем. Упрощению логических (контактных) схем способствует, в частности, минимизация ФАЛ. Под минимизацией ФАЛ понимают преобразование исходной функции алгебры логики, приводящее к уменьшению числа символов, в том числе, и числа операторов, входящих в ее аналитическое выражение. Каноническая задача минимизации ФАЛ заключается в нахождении аналитической формы записи ФАЛ, содержащей минимальное число вхождений переменных – так называемой минимальной формы. Исходными 41 формами при решении канонической задачи минимизации канонические формы записи ФАЛ, к которым относятся: 1. дизъюнктивная совершенная нормальная форма (ДСНФ); 2. конъюнктивная совершенная нормальная форма (КСНФ). являются Канонические формы входят в группу нормальных форм. Всего выделяют пять дизъюнктивных нормальных форм, одна из которых каноническая, и пять конъюнктивных нормальных форм, включая одну каноническую. Все они отличаются друг от друга в первую очередь степенью минимизации. При дизъюнктивной записи ФАЛ используют следующие формы: 1. дизъюнктивная нормальная форма (ДНФ), 2. дизъюнктивная совершенная нормальная форма (ДСНФ), 3. сокращённая дизъюнктивная нормальная форма (СДНФ), 4. тупиковая дизъюнктивная нормальная форма (ТДНФ), 5. минимальная дизъюнктивная нормальная форма (МДНФ). 6. Для конъюнктивной записи ФАЛ используют такие формы: 7. конъюнктивная нормальная форма (КНФ), 8. конъюнктивная совершенная нормальная форма (КСНФ), 9. сокращённая конъюнктивная нормальная форма (СКНФ), 10.тупиковая конъюнктивная нормальная форма (ТКНФ), 11.минимальная конъюнктивная нормальная форма (МКНФ). На рисунке 9 применительно к дизъюнктивной записи ФАЛ представлено соотношение между различными формами. Соотношение между дизъюнктивными нормальными формами ФАЛ Дизъюнктивная совершенная нормальная форма (ДСНФ) представляет собой дизъюнкцию минтермов. Каждый входящий в ДСНФ минтерм содержит все переменные, входящие в ФАЛ, соединенные между собой элементарными конъюнкциями. Количество минтермов равно количеству наборов переменных, на которых ФАЛ принимает единичные значения. Для каждой ФАЛ, заданной таблицей истинности, существует только одна ДСНФ. Например, таблице истинности (табл. 17) соответствует единственная ДСНФ следующего вида: f  f1  f 2  f 3  f 4  f 5  x3  x2  x1  x3  x2  x1  x3  x2  x1  x3  x2  x1  x3  x2  x1 42 Рисунок 9 Таблица 17 № набора x3 x2 x1 y 1 1 2 1 3 1 1 1 4 1 1 5 1 1 1 6 1 1 1 7 1 1 1 1 Дизъюнктивная нормальная форма (ДНФ) – представляет собой дизъюнкцию конечного числа элементарных конъюнкций, полученных в результате склеивания, так называемых, соседних импликант. ДНФ короче ДСНФ, поскольку может содержать меньшее число дизъюнкций, а участвующие в дизъюнкциях члены выражения могут содержать не все переменные ФАЛ. Следует отметить, что импликанты бывают соседними, несоседними и несоизмеримыми. Соседние импликанты должны удовлетворять двум следующим условиям:  обе содержат одинаковое число переменных;  отличаются друг от друга представлением только одной переменной. Например, соседними являются импликанты x1  x2  x3  x4 и x1  x2  x3  x4 , поскольку удовлетворяют обоим перечисленным условиям, а именно, 43 содержат одинаковое число переменных и отличаются друг от друга представлением только одной переменной – x 2 (в одной импликанте переменная x 2 представлена в прямом виде, а в другой - в инверсном x 2 , остальные переменные в обеих импликантах имеют одинаковый вид). Примерами соседних импликант являются также пары: x и x ; x1  x 2 и x1  x2 ; x1  x 2 и x1  x2 ; x1  x2 и x1  x2 ; x1  x2  x3 и x1  x 2  x3 и т.д. (каждая инверсия в импликантах охватывает только одну переменную и не охватывает знака конъюнкции). Несоседними являются импликанты, которые отличаются друг от друга значением нескольких переменных. Например, несоседними являются следующие импликанты x1  x 2 и x1  x2 , поскольку они отличаются друг от друга значениями двух переменных: в одной обе переменные имеют прямое значение, а в другой – инверсное. Примерами несоседних импликант являются также следующие: x1  x2  x3 и x1  x2  x3 (отличаются значениями двух переменных); x1  x2  x3 и x1  x2  x3 (отличаются значением трёх переменных); x1  x2  x3  x4 и x1  x2  x3  x4 и т.д. Среди несоседних импликант есть так называемые несоизмеримые. Несоизмеримые импликанты содержат различные переменные или их различное количество. Примером несоизмеримых импликант является пара x1  x2  x3 и x2  x3 , поскольку одна из них содержит переменную x1 , которой нет у другой. Также несоизмеримые импликанты представляет пара x1  x2  x3 и x1  x2  x4 , так как в одну из них входит переменная x 3 , которой нет в другой, а в другой есть переменная x 4 , которой нет в первой. ДНФ может быть получено путем склеивания только соседних импликант. В ДСНФ импликантами являются минтермы – конституенты единицы. Операция склеивания соседних импликант осуществляется с использованием формулы склеивания: x1  x2  x1  x2  x1  ( x2  x2 )  x1 1  x1 . В результате склеивания различающаяся переменная исчезает, при этом образуется новая импликанта, число переменных в которой уже на одну меньше, а число логических операций сокращается на три. Например, x1  x2  x3  x4  x1  x2  x3  x4  x1  x3  x4 и т.д. Считается, что импликанта, полученная в результате склеивания некоторого множества конституент покрывает эти конституенты (формирует те же значения функции на всех наборах значений переменных, что и склеенные конституенты 1). Поскольку ДСНФ может содержать более одной пары соседних импликант, а склейка любой из них приводит к появлению ДНФ, то одной 44 ДСНФ может соответствовать несколько ДНФ. Например, ДСНФ, заданной формулой (15), после первого склеивания могут соответствовать следующие ДНФ: f a  x3  x2  x1  x3  x2  x1  x3  x2  x1  x3  x2 ; f b  x2  x1  x3  x2  x1  x3  x2  x1  x3  x2  x1 ; f ñ  x2  x1  x3  x2  x3  x2  x1 ; f d  x2  x1  x3  x1  x3  x2  x1 ; f e  x3  x2  x1  x3  x2  x3  x2 и т.д. Если в результате склейки снова получаются соседние импликанты, то они тоже могут быть склеены. Например, ДНФ f e содержит соседние импликанты x3  x2 и x3  x2 , которые можно подвергнуть склеиванию. Процесс многоступенчатого склеивания приводит к получению импликант, которые не склеиваются с другими. Такие импликанты называются простыми. Логическую сумму всех простых импликант называют сокращённой ДНФ (СДНФ). Для ДСНФ (15) сокращенной ДНФ является, например, следующая ФАЛ: f x  x1  x2  x3 . Эквивалентность ФАЛ в виде ДСНФ и СДНФ легко проверить, вычислив значения обеих ФАЛ на всех возможных наборах переменных, и построив таблицу истинности. Обеим формулам будет соответствовать одна и та же таблица истинности. Поскольку ДСНФ содержит исходные импликанты (конституенты 1), а СДНФ – простые (несклеиваемые) импликанты, то по степени минимизации ДНФ находятся между ДСНФ и СДНФ. СДНФ часто является избыточной, так как одна и та же конституента может покрываться несколькими импликантами (участвовала в склейке при получении нескольких простых импликант). После исключения из СДНФ лишних импликант получают тупиковую ДНФ (ТДНФ). При удалении из ТДНФ любой импликанты получается ДНФ, которой соответствует ФАЛ, не эквивалентная минимизируемой (с отличающейся таблицей истинности). Следует заметить, что у минимизируемой ФАЛ может быть несколько ТДНФ. Путём сравнения ТДНФ между собой, выявляют минимальную ДНФ (МДНФ), которая содержит наименьшее число переменных. Соотношение между конъюнктивными нормальными формами ФАЛ Соотношение между конъюнктивными нормальными формами аналогично соотношению между дизъюнктивными нормальными формами. Конъюнктивная совершенная нормальная форма (КСНФ) представляет собой конъюнкцию макстермов (специально вводимых 45 конституент 0). Каждый входящий в КСНФ макстерм содержит все переменные, входящие в ФАЛ, соединенные между собой элементарными дизъюнкциями (без скобок и повторяющихся переменных). Количество макстермов равно количеству наборов переменных, на которых ФАЛ принимает нулевые значения (см. нормальные формы ФАЛ). Для одной ФАЛ существует только одна КСНФ. Например, таблице истинности (табл. 11) соответствует единственная КСНФ следующего вида:   f  f1  f 2  f 3  x3  x2  x1   x3  x2  x1  x3  x2  x1  Конъюнктивная нормальная форма (КНФ) – представляет собой конъюнкцию уменьшенного числа элементарных дизъюнкций по сравнению с КСНФ. По степени минимизации КНФ находится между КСНФ и СКНФ, поскольку может содержать меньшее число переменных и логических операций, а участвующие в конъюнкциях члены выражения (импликанты), могут содержать не все переменные ФАЛ. КНФ получается из КСНФ, тем же способом, что и ДНФ из ДСНФ, т.е. склеиванием соседних импликант. Определение соседних импликант дано ранее. При склеивании используется закон склеивания, а в первую очередь формула: x1  x2  x1  x2   x1  x2  x2  x1  0  x1 Примерами соседних импликант в КНФ являются следующие пары:  x и x (в результате склеивания получается импликанта x  x  0 );  x1  x2  и x1  x2  (в результате склеивания получается импликанта x1 );  x1  x2  x3  и x1  x2  x3  (в результате склеивания получается импликанта x1  x2  и т.д. Во всех перечисленных парах обе импликанты содержат одинаковые переменные и отличаются друг от друга значением только одной переменной, то есть удовлетворяют требованиям к соседним импликантам. Поскольку минимизация ФАЛ осуществляется только с использованием соседних импликант, то важно отличать их от несоизмеримых и несоседних. В связи с этим приведём по нескольку примеров импликант последних двух видов. Несоседними импликантами являются те пары, в которых каждая импликанта содержит одинаковые переменные, но при этом обе импликанты отличаются друг от друга значением более, чем одной переменной: 1. импликанты, отличающиеся значением двух переменных одновременно: x  x 1 2       x3 и x1  x2  x3 ,  x1  x 2  и x1  x2 ; 46 2. импликанты, отличающиеся значением трёх переменных одновременно: x  x 1 2         x3 и x1  x2  x3 , x1  x2  x3  x4 и x1  x2  x3  x4 и т.д. Несоизмеримыми импликантами являются те пары, в которых содержатся разные переменные или количество переменных различно:  импликанты, содержащие различные переменные: x  x 1 2     x3 и x1  x2  x4 , x2  x3  и  x 2  x1  ;  импликанты, содержащие различное количество переменных: x  x 1 2         x3 и x1  x2 , x1  x2  x3  x4 и x1  x2 и т.д. Логическая сумма всех простых (несклеиваемых) импликант называется сокращённой КНФ (СКНФ). Тупиковая КНФ (ТКНФ) получается из сокращённой, вычеркиванием лишних простых импликант. Минимальная КНФ (МКНФ) – это ТКНФ, содержащая наименьшее число букв (символов). Методы минимизации ФАЛ Фактически все методы минимизации основаны на законе склеивания. Вместе с тем, если рассмотреть ДСНФ, то легко заметить, что уже при первом склеивании возможны несколько ДНФ, которые, в свою очередь, могут содержать соседние импликанты, а могут и не содержать. Следовательно, в одном случае минимизация может завершиться тупиковой ДНФ уже после первого склеивания (сокращением одной импликанты и удалением одной переменной), а может включать в себя несколько последовательных склеиваний (см. рис. 10). Таким образом, результаты минимизации зависят от порядка склеивания импликант. Для примера на рис. 10 красным кружком обозначена некоторая ДНФ. Как видно, при её минимизации может быть получена ТДНФ, но МДНФ склеиванием данной ДНФ получена быть не может, хотя из ДСНФ её можно получить. Поэтому, перед применением любого из рассматриваемых далее методов минимизации, следует обязательно преобразовать ФАЛ к одной из канонических форм: ДНСФ или КСНФ. В большинстве методов минимизации лежит алгоритм перебора равносильных ДНФ. Классификация наиболее известных методов минимизации представлена ниже на рисунке. 47 Рис. 10. Метод минимизации ФАЛ при помощи алгебраических преобразований Рассмотрим метод минимизации ФАЛ при помощи алгебраических преобразований. Данный метод основан на применении основных законов алгебры логики (булевой алгебры), которые были рассмотрены ранее. Наиболее эффективными и часто используемыми при минимизации с помощью алгебраических преобразований являются закон склеивания и закон поглощения. Различают полное и неполное склеивание. После выполнения полного склеивания остаётся только импликанта-результат, а исходные соседние импликанты, подвергшиеся склейке удаляются. После полного склеивания в выражение ФАЛ входят как исходные импликанты, так и импликантарезультат. Например, при полном склеивании импликант некоторой ДНФ, получим: x1  x2  x3  x1  x2  x3  x1  x2 , для тех же импликант при выполнении неполного склеивания, результат будет такой: x1  x2  x3  x1  x2  x3  x1  x2  x3  x1  x2  x3  x1  x2 . Более эффективно применение неполного склеивания импликант. В этом случае минимизация осуществляется в следующем порядке. На первом этапе минимизации используют операции неполного склеивания импликант. При необходимости они повторяются вплоть до образования простых импликант. После того, как все операции склеивания выполнены, используют операции поглощения. Иногда, на последней стадии, применяют закон логической тавтологии (повторения), с целью удаления избыточных импликант. Рассмотрим применение данного метода минимизации к ДСНФ и КСНФ. 48 Минимизация ДСНФ методом алгебраических преобразований Пусть имеется некоторая ДСНФ: f  x1  x2  x3  x1  x2  x3  x1  x2  x3  x1  x2  x3  x1  x2  x3 Легко заметить, что она содержит пять минтермов (конституент единицы): f  f1  f2  f3  f4  f5 . каждый из которых имеет следующий вид: f1  x1  x2  x3 , f 2  x1  x2  x3 , f3  x1  x2  x3 , f 4  x1  x2  x3 , f5  x1  x2  x3 1. В начале минимизации ДСНФ произведём неполное склеивание импликант. Для этого выделим все пары соседних импликант: f1 и f 2 , f1 и f 3 , f1 и f 5 , f 2 и f 4 , f 3 и f 4 . В результате склеивания пар соседних покрывающие их импликанты следующего вида: импликант получим    x  x  x  x  x  x  x  x  x  x   x  x ;  x  x  x  x  x  x  x  x  x  x   x  x ;  x  x  x  x  x  x  x  x  x  x   x  x ;  x  x  x  x  x  x  x  x  x  x   x  x . f12  f1  f 2  x1  x2  x3  x1  x2  x3  x1  x2  x3  x3  x1  x2 ; f13  f1  f 3 f15  f1  f 5 f 24  f 2  f 4 f 34  f 3  f 4 1 2 3 1 2 3 1 3 2 2 1 3 1 2 3 1 2 3 2 3 1 1 2 3 1 2 3 1 2 3 1 3 2 2 1 3 1 2 3 1 2 3 1 2 3 3 1 2 Выражение ФАЛ после первого неполного склеивания содержит как исходные импликанты, так и покрывающие импликанты, и, следовательно, имеет вид: f  f1  f 2  f 3  f 4  f 5  f12  f13  f15  f 24  f 34   x1  x 2  x3  x1  x2  x3  x1  x 2  x3  x1  x2  x3  x1  x 2  x3  x1  x2  x1  x3  x2  x3   x1  x3  x1  x 2 Легко заметить, что в полученном выражении среди покрывающих импликант также имеются соседние, что позволяет осуществить повторное склеивание: 49   x  x   x  x ; f12 34  f12  f 34  x1  x2  x1  x2  x1  x2  x2  x1 ; f13 24  f13  f 24  x1  x3  x1  x3 1 3 3 1 После повторного склеивания больше не осталось соседних импликант. Результат имеет вид: f  f1  f 2  f 3  f 4  f 5  f12  f13  f15  f 24  f 34  f12 34  f13 24   x1  x 2  x3  x1  x2  x3  x1  x 2  x3  x1  x2  x3  x1  x 2  x3  x1  x2  x1  x3  x2  x3   x1  x3  x1  x 2  x1  x1 Воспользовавшись законом логической тавтологии (см. законы) можно удалить повторяющиеся импликанты. Очевидно, такими являются импликанты f12 34 и f13 24 . В окончательном выражении можно оставить любую из них: f  f1  f 2  f 3  f 4  f 5  f12  f13  f15  f 24  f 34  f12 34   x1  x 2  x3  x1  x2  x3  x1  x 2  x3  x1  x2  x3  x1  x 2  x3  x1  x2  x1  x3  x2  x3   x1  x3  x1  x 2  x1 2. К полученному выражению следует применить законы поглощения. Один из них имеет следующий вид: x1  x1  x2  x1 . Данное тождество легко доказывается. Для этого сначала используют распределительный закон и x1  x1  x 2  x1  1  x 2  . После чего осуществляют выносят x1 за скобки: преобразования в скобках с учетом закона логического сложения с единицей (см. ранее) x1  1  x 2   x1  1 и, в последнюю очередь используя закон логического умножения на единицу, получают окончательный результат: x1  1  x1 Из приведённого тождества можно сделать следующий вывод: при дизъюнктивной записи ФАЛ импликанта, содержащая некоторую переменную x1 поглощает все импликанты, содержащие эту же переменную в том же значении, но имеющие при этом большее число переменных. Наиболее эффективно минимизирует ФАЛ поглощение с использованием простых импликант, имеющих наименьшее число переменных, поэтому в выражении, полученном после неполного склеивания импликант ФАЛ, в качестве поглощающей попытаемся использовать импликанту, содержащую одну переменную – x1 . Легко заметить, что данная импликанта в полученном выражении может поглощать другие, поскольку переменная x1 входит также в импликанты содержащие большее число переменных. f1 , f 2 , f 3 , f 4 , f12 , f13 , f 24 , f 34 , 50 Следовательно, осуществим операцию поглощения. Для использованием распределительного закона вынесем x1 за скобки: этого с f  x1  x2  x3  x1  x2  x3  x1  x2  x3  x1  x2  x3  x1  x2  x3  x1  x2  x1  x3  x2  x3     x1  x3  x1  x2  x1  x1  x2  x3  x2  x3  x2  x3  x2  x3  x2  x3  x3  x2  1  x1  x2  x3   x 2  x3 Из закона логического сложения с единицей следует, что всё выражение, находящееся в скобках равно единице, тогда можно записать: f  x1  x1  x2  x3  x2  x3 Поскольку других импликант, содержащих одну переменную не осталось, то попробуем осуществить операцию поглощения для импликанты, содержащей две переменных. Как следует из выражения, после первого поглощения осталась только одна импликанта, содержащая две переменных – f15  x2  x3 . Данная импликанта может поглощать импликанту f 5 . Поглощение осуществим аналогичным образом:   f  x1  x1  x2  x3  x2  x3  x1  x2  x3  x1  1  x1  x2  x3 (47) Поскольку в полученном выражении больше нет импликант, которые можно поглотить, то полученная форма f  x1  x2  x3 является МДНФ. Проверка: Как известно, правильно выполненная минимизация ФАЛ не приводит к искажению таблицы истинности комбинационного автомата, но, как правило, упрощает его схему.  Формула (47) содержит меньше букв, чем формула (45), следовательно, ей соответствует более простая комбинационная схема.  Легко доказать, что формула (47) эквивалентна исходной ДСНФ (45), для этого достаточно подставить в обе формулы все возможные наборы переменных x1 , x2 , x3 . Обе формулы дают одинаковый результат, т.е. таблицы истинности обеих ФАЛ одинаковы.  Формула (47) содержит простые импликанты, следовательно, это тупиковая ДНФ (ТДНФ).  Скорее всего формула (47) действительно является МДНФ (можно узнать только сравнением с другими тупиковыми ДНФ полученными из ДСНФ). 51