Представление логических функций (ЛФ) 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Представление логических функций (ЛФ)



СДНФ переключательной функции записывается по таблице истинности.

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

Используя это правило, запишем в СДНФ функции f1 и f2 трех переменных, заданных таблице 3.13.

Таблица 3.13

x1 x2 x3 f1 f2
           
           
           
           
           
           
           
           

В результате получим следующие выражения:

Для получения f1 используем 2, 4 и 6 строки

f1 = + х2 (3.1)

Для получения f2 используем 1, 7 и 8 строки.

f2 = + х2 + х1 х2 х3 (3.2)

 

 

Элементарные конъюнкции СДНФ называют конституантами (составляющими) единицы, так как они соответ­ствуют наборам, при которых ЛФ принимает значения 1.

После составления выражения для f1 можно по­строить из логических элементов И, ИЛИ, НЕ функцио­нальную схему, которая будет вычислять значение ЛФ f1.

Чтобы построить функциональную схему для ЛФ, записан­ной в СДНФ, надо взять k ЛЭ И на n входов каждая, где k — число конъюнкций СДНФ, и объединить выходы схем И с помощью элемента ИЛИ на k входов.

Для ЛФ f1 функциональная (или логическая) схема приведена на рис. 3. 6 (на схеме не показаны лишь элементы НЕ, с помощью которых получаются инверсные значения переменных х1 и x2).

Рисунок 3.6 Рисунок 3.7

Для каждой функциональной схемы можно сделать оценку ее сложности, которая выражается ценой схемы С (по Квайну).

Цена С определяется суммарным числом входов логических элементов.

Чем меньше вели­чина С, тем проще функциональная схема. Если ЛФ за­дана в СДНФ, ее цену можно выразить формулой:

С = kn + k.

Для ЛФ f1 - k = 3 -число конъюнкций, а n = 3 –число входов (х1 х2 х3).

Тогда С = 3 х 3 + 3 = 12

Используя правило склеивания (ПРАВИЛО 11), можно упростить ЛФ, заданную в СДНФ.

Для этого в СДНФ сначала склеи­ваются между собой конъюнкции ранга п, затем полу­ченные конъюнкции ранга (n — 1), (n — 2), и так до тех пор, пока в выражении для ПФ не останется ни одной пары склеиваемых между собой конъюнкций. Операция склеи­вания позволяет понизить ранг конъюнкций и сократить их число. В результате уменьшается цена функциональной схемы.

Например, в выражении f1 = + х2 выполним склеивание:

-конъюнкций и х2 по переменной х2, получим: ;

-и конъюнкций и по переменной х1 , получим: .

В результате функция f1 преобразуется к виду f1 = + (3.3)

Функциональная схема, реализующая ЛФ f1 по выра­жению (3.3), изображена на рис. 3.7.

Цена этой схемы С = 6, т. е. по сравнению с эквивалентной схемой на рис. 3.8 цена уменьшилась в 2 раза.

В результате попарного склеивания конъюнкций ранга п, а далее (п — 1), (п — 2) и т. д., в выражении для ЛФ остаются конъюнкции, которые между собой не склеивают­ся.

Конъюнкция, которая не склеивается ни с какой другой конъюнкцией ДНФ, называется простой импликантой.

В выражении (3.3) конъюнкции не склеивают­ся между собой, т. е. они являются простыми импликантами.

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

 

Понятие суперпозиции

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

С помощью суперпозиции можно получить более сложные функции любого числа переменных.

Пример:

Если F = X1 v X2 и X1 =Z1Z2; Х2 = Z3 v Z4, тогда Y = Z1 Z2 v Z3 v Z4.

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

Систему функций называют минимально полным базисом, если удаление из нее любой функции превращает эту систему в неполную.

В теории алгебры логики доказано, что функционально полные системы образуют следующие наборы функ­ций:

1. , Х1 v Х2, Х1 Х2 - НЕ, ИЛИ и И - булев базис, избыточный;

2. , Х1 v Х2 - НЕ и ИЛИ;

3. , Х1 Х2 - НЕ и И;

4. ; - И-НЕ;

5. - ИЛИ-НЕ и др.

 



Поделиться:


Последнее изменение этой страницы: 2017-01-19; просмотров: 326; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.152.77.92 (0.105 с.)