33. Минимизация логических функций методом Квайна.

Теорема Квайна

Если исходя из СДНФ провести все возможные операции неполного склеивания, а затем все возможные операции элементарного поглощения, то в результате образуется сокращённая ДНФ, т.е. дезъюнкция всех простых имплекант.

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

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

34. Понятие функционально-полной системы логических функций

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

1) "И-ИЛИ-НЕ" (базис конъюнкции, дизъюнкции, инверсии)

2) "И-НЕ"           (базис Шеффера)

3) "ИЛИ-НЕ"     (базис Пирса или функция Вебба).

Элементы, реализующие операцию "И-НЕ", “ИЛИ-НЕ” и “Исключающее ИЛИ” на принципиальных  и  структурных схемах изображаются так:

Примеры реализации логических операций в базисах “И-НЕ” и “ИЛИ-НЕ”.

Реализация операции “НЕ”:

Реализация операции “И”:

Реализация операции “ИЛИ”:

 Пример реализации комбинационного устройства в базисе "И-НЕ". Пусть задана функция, реализуемая комбинационным устройством, в аналитической форме

 .

Используя закон де Моргана и с учетом закона двойного инвертирования, запишем эту функцию в виде

 .

Как следует из полученного аналитического выражения, логическое устройство должно содержать три двухвходовых   и один трехвходовой элемент И-НЕ. Функциональная схема комбинационного устройства, построенная в базисе И-НЕ, показана на рис. 1.10.

35. 36 Понятие замкнутого класса. Класс монотонных логических функций.Понятие замкнутого класса. Класс линейный логических функций..

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

Классы логических функций

Функция, "сохраняющая 0".

Это - такая логическая функция, значение которой равно 0, если все аргументы равны 0: f(0,0,...,0) = 0.

Примером функции, сохраняющей 0, является функция  .

Функция, "сохраняющая 1".

Это - такая логическая функция, значение которой равно 1, если все аргументы равны 1: f(1,1,...,1) = 1.

Примером функции, сохраняющей 1, является функция &.

"Монотонная" функция.

Это - такая логическая функция, которую можно выразить через & и  .

Монотонную функцию можно распознать по ее таблице истинности. Для этого нужно взять все пары строк в таблице, которые отличаются всего в одном столбце (не считая крайнего правого). Например: 0,0,0,0 и 0,0,0,1; 1,0,0,1 и 1,1,0,1. Пусть в одной строке в некотором столбце стоит "0", а в другой строке в этом же столбце стоит "1". Нельзя, чтобы в крайнем правом столбце, где записано значение функции было наоборот: "1", а потом "0". Если такая ситуация нигде не встречается, то функция монотонная, и ее можно выразить через   и &. Пример монотонной функции:  .

"Линейная" функция.

Это - такая логическая функция, которую можно выразить через  , 0 и 1.

Чтобы узнать, линейна ли функция, надо выразить ее через полином Жегалкина и посмотреть, не встречается ли там операция &. Если нет, то функция линейна. Для функций от 1 и 2 переменных мы уже приводили формулы, выражающие их через &,   и константы.

Двойственные функции.

Логические функции f и g называются двойственными, если

f(~x1, ~x2,...,~xN) = ~g(x1, x2,..., xN).

Кратко это будем обозначать так: "f" * "g". Двойственные функции легко обнаружить с помощью простого приема. Надо заменить в таблице истинности все "0" на "1", а все "1" на "0". Полученная таблица истинности и будет таблицей двойственной функции. Ниже приведен список двойственных функций для всех унарных и бинарных операций.  "0" * "1"  "x" * "x"  "~" * "~"  "&" * " "  " " * " "  "|" * " "  "<" * " "  ">" * " "

"Самодвойственная" функция.

Это - логическая функция, которая двойственна самой себе:

f(~x1, ~x2,...,~xN) = ~f(x1, x2,..., xN).