- •Воронежский государственный технический университет
- •(Часть 1) Учебное пособие
- •Глава 1. Становление теории автоматов и ее основные задачи
- •Взаимосвязь теории автоматов и других научно-технических направлений
- •Подходы к определению конечного автомата.
- •Сущность метода "черного ящика".
- •Основные задачи теории автоматов
- •Глава 2. Формальная классификация абстрактных автоматов и их математические модели.
- •2.1 Словесные определения автоматов.
- •2.4.3 Модель совмещенного автомата (с-автомата)
- •2.4.4 Модель микропрограммного автомата
- •Глава 3 Структурные модели первого уровня абстрактных автоматов
- •3.1. Структурная модель автомата Мили
- •3.2. Структурная модель автомата Мура
- •3.3 Структурная модель с - автомата
- •3.4 Структурная модель микропрограммного автомата
- •Глава 4. Способы задания абстрактных и структурных автоматов.
- •Глава 5 Минимизация абстрактных автоматов
- •Глава 6. Математические основы алгебры логики
- •Теоремы алгебры логики
- •6.4.1 Словесная форма представления логических функций
- •6.4.3 Аналитическая форма представления логических функций
- •6.4.4 Геометрическая и кубическая формы представления
- •2.4.3 Модель совмещенного автомата………………25
- •Глава 5 Минимизация абстрактных автоматов……………..58
- •Глава 6. Математические основы алгебры логики……...…70
- •Учебное издание
- •394026 Воронеж, Московский просп.,14
6.4.3 Аналитическая форма представления логических функций
Табличные способы задания логических функций становятся весьма громоздкими с увеличением числа аргументов. Так, уже при восьми аргументах количество строк в таблице истинности или количество клеток карты Карно равно 256. Аналитические формы представления логических функций более компактны и наглядны, и позволяют очень просто синтезировать комбинационные автоматы из ограниченного количества логических элементов, реализующих логические операции умножения (конъюнкцию), сложения (дизъюнкцию) и отрицания (инверсию). В то же время, аналитические формы логических функций позволяют выполнять различные их математические преобразования с целью получения более простых соотношений или для каких - либо других целей.
Аналитический способ предусматривает запись логической функции в форме логического выражения, показывающего, какие логические операции над аргументами должны выполняться и в какой последовательности. Сложные функции от многих аргументов могут быть представлены в форме "функций от функций", т.е. выражаться через более простые функции - от меньшего числа аргументов. Так, если z = z(x,y); x = x (a,b); y = y (c,d), то z = z (a,b,c,d). Операция замены аргументов одной функции другими, более простыми функциями носит название суперпозиции функции. Многократное использование принципа суперпозиции дает возможность получить функции желаемого числа аргументов.
Для аналитического задания логических функций используются, так называемые, нормальные формы.
В алгебре логики существует две самые распространенные аналитические формы представления функции: совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ). Каждая логическая функция имеет одну СДНФ и одну СКНФ.
СДНФ логической функции может быть получена путем многократного применения теоремы разложения (6.25) к некоторой функции n аргументов для каждой ее переменной xi (i=1…n). Применяя теорему разложения, получим
F (x1, x2,… xn) = f(0,0,…0 )x1 x2…xn +
+
(6.31)
(6.32)
+
2n
-1 =
∑ fi
mi, i=0
………………………
+ f(1,1,…1 )x1 x2…xn
где fi - значение логической функции на i -ом входном наборе аргументов;
mi - i -ый минтерм или i -ая элементарная конъюнкция максимального ранга.
Из (6.31) следует, что СДНФ логической функции — это дизъюнкция конституент единицы (минтермов), соответствующих наборам входных переменных, для которых функция равна единице. Совершенная дизъюнктивная нормальная форма записывается для истинного значения логической функции. В то же время относительно логической функции можно сказать, что она истинна тогда, когда не ложна. Такое утверждение можно формализовать следующим образом.
Образуем логическую функцию по ее нулевым значениям на всех входных наборах. Тогда
2n
-1 =
∑ fi
mi. i=0
F(x1, x2,… xn)
Применяя к (6.32) правило де Моргана, получим
2n
-1 =
∏ (fi
+ Mi), i=0
(6.33)
F(x1, x2,… xn)
88
87
где fi - значение логической функции на i -ом входном наборе аргументов;
Mi - i -ый макстерм или i -ая элементарная дизъюнкция максимального ранга.
Представление логической функции в виде (6.33) называется совершенной конъюнктивной нормальной формой (СКНФ).
СКНФ логической функции — это конъюнкция конституент нуля (макстермов), соответствующих входным наборам, для которых функция равна нулю.
Рассмотрим алгоритмы перехода от табличного описания логической функции к ее аналитическому описанию (СДНФ, СКНФ).
Алгоритм перехода от таблицы истинности логической функции к ее записи в виде СДНФ:
1) выбрать в таблице истинности такие входные наборы, на которых функции обращается в единицу;
2) по каждому такому набору составить элементарные конъюнкции максимального ранга (минтермы);
3) в минтермы записать не инвертированными переменные, заданные единицей в таблице истинности, а инвертированными - те переменные, которые в таблице истинности заданы нулем;
4) полученные минтермы соединить между собой знаками дизъюнкции.
Алгоритм перехода от таблицы истинности логической функции к ее записи в виде СКНФ:
1) выбрать в таблице истинности такие входные наборы, на которых функция имеет нулевые значения;
2) по каждому такому набору составить элементарные дизъюнкции максимального ранга (макстермы);
3) в макстермы записать не инвертированными переменные, заданные нулем в таблице истинности, а инвертированными - те переменные, которые в таблице истинности заданы единицей;
4) полученные макстермы соединить между собой знаками конъюнкции.
Помимо двух основных (СДНФ и СКНФ) аналитических форм представления функций в алгебре логики существуют дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ), а также минимальные дизъюнктивные и конъюнктивные нормальные формы (МДНФ и МКНФ).
ДНФ/КНФ – это дизъюнкция/конъюнкция элементарных конъюнкций /дизъюнкций, ранг хотя бы одной из которых отличается от максимального ранга. ДНФ/КНФ называется минимальной, если она содержит наименьшее число букв по сравнению со всеми ДНФ/КНФ, существующими для данной функции. При помощи правил развертывания элементарных конъюнкций и дизъюнкций, ДНФ и КНФ могут быть преобразованы в СДНФ и СКНФ.
В общем виде СДНФ и СКНФ записываются выражениями (6.32) и (6.33), которые могут быть слишком громоздкими. Для их упрощения используется более компактная числовая форма записи, предусматривающая только перечисление десятичных эквивалентов двоичных наборов, на которых функция принимает значение единицы (для СДНФ) или нуля (для СКНФ), соединив их знаками дизъюнкции (для СДНФ) и конъюнкции (для СКНФ).
Пример 6.4. Пусть логическая функция P(x,y,z) задана следующей таблицей истинности (табл. 6.3). Требуется представить ее в виде СДНФ и СКНФ.
Р ешение. По таблице истинности находим, что функция P(x,y,z) принимает единичные значения на четырех входных наборах аргументов. Данным наборам аргументов соответствуют следующие четыре минтерма: x y z, x y z, x y z, x y z.
Т
90
89
P сднф(x,y,z) =
Таблица 6.3
По аналогии, представим данную логическую функцию в виде СКНФ. В итоге получим:
Pскнф(x,y,z) =