Тема 8. Методи за минимизиране

Логически функции

За описание на функционирането на логическите схеми ще разгледаме някои базови понятия от алгебрата на логиката. Основите на този математически апарат са разработени от ирландския математик Бул (1815 – 1864), поради което често алгебрата на логиката се нарича Булева алгебра.

Основно понятие е т.нар. превключвателна или логическа функция. Логически функции са зависимости от вида:

(1)    Y = f ( X₁, X₂, X₃, …Xm ) ,

 в които както Y, така и аргументите (променливите) X₁, X₂, X₃, …X_m могат да приемат само две стойности: 0 и 1. От това следва, че областта на определение на логическата функция е крайна. При това съвкупността от стойности на тези аргументи се нарича набор. За всяка превключвателна функция от m променливи съществува число Z = 2^m различни набори (входни комбинации). Тъй като фукцията е определена чрез Z набора и може да приема само две стойности - 0 или 1 - то броят на различните логически функции от m променливи е равен на 2^Z = 2^2m.

Логическите функции се задават (дефинират) по няколко начина:

а) словесно (чрез текст);

б) таблично (чрез таблици на истинност);

в) аналитично (чрез формула Y = f ( X₁, X₂, X₃, …X_m ) );

г) графично (чрез m-мерен куб или карти на Вейч (Карно) ).

Един от начините за задаване на логически функции е чрез таблица на истинност. В нея е посочена стойността на функцията за всяко съчетание (набор) от стойности на аргументите.

Логическите функции от един аргумент имат условно обозначение и наименование дадени в таблица 1:

Таблица 1

Съществена е функцията Y = F₃ ( X ) =  , наречена логическо отрицание или инверсия. Означава се с чертичка над аргумента и се чете “не X”. Както се вижда от таблицата, стойността на функцията е винаги обратна на стойността на аргумента.

При n = 2, т.е. за логическа функция от два аргумента X₁ и X_2, съществуват 2⁴ = 16 различни логически функции. От всичките шестнадесет функции на две променливи интерес представляват функциите, показани в таблица 2:

Таблица 2

Както се вижда, функцията F₁ приема стойност единица, само когато стойностите и на двата аргумента са единици. За всички останали набори на аргументите F₁ е равна на нула.

Функцията F₆ приема стойност нула, когато стойностите на двата аргумента са еднакви. При различни стойности на двата аргумента функцията F₆ приема стойност единица.

Функцията F₇ е равна на нула, само когато стойностите и на двата аргумената са нула. Тя приема стойност единица за всички останали набори. В тях, или единият, или другият, или и двата аргумента имат стойност единица.

Функциите F₈, F₉ и F₁₄ представляват отрицание на функциите F₇, F₆ и F₁.

Аналогично на посочения по-горе начин се задават функции на повече от два аргумента.

Логическите функции дават връзката между входните променливи и изходните сигнали. Схемната реализация на функцията представлява логическа схема. В следващата таблица са показани всички общоупотребявани обозначения на логическите функции, които се използват в европейската и американската специализирана литература:

 Таблица 3

Теорема на Бул - Всяка булева функция може да се представи със съждителна формула (с помощта на конюнкция, дизюнкция и отрицание)

1. Булевата алгебра се използва за аналитично или таблично представяне на логическите функции, които извършват логическите елементи.

2. С помощта на Булевата алгебра се решават задачите за анализ и за синтез на логическите елементи.

3. Най-съществените причини за опростяване на една логическа функция са:

 - За реализирането на една функция трябва да се използват колкото е възможно по-малко елементи. Това намалява цената на схемата, повишава надеждността й и намалява габаритните й размери.

 - Повишаване на бързодействието на дадената схема. През всяка реална схема сигналът преминава за определено време. Когато сигналът преминава през много логически елементи, свързани последователно, времената на закъсненията им се сумират и се увеличава общото време за предаване на сигнала от входа към изхода.

Проектирането на логически схеми трябва да бъде оптимизирано в смисъл минимум елементи и минимално закъснение на изходния сигнал спрямо входния. Преобразуването на логически функции с цел минимизация може да се извърши:

а) графично с карти на Вейч или Карно;

б) аналитично (метод на Куайн – МакКласки).

През 1952 година Е. Вейч предлага диаграми удобни за опростяване на логически функции. Следващата година М. Карно предлага реорганизация на картите на Вейч, която обосновава математически.

Разликата между двата вида карти се състои само в различния начин на подреждане на променливите, определящи редовете и стълбовете на картата.Общото между двата вида карти се състои в използването на код на Грей (дву-, три-, m-разреден) в различните комбинации от стойности на променливите

Минимизиране на логическите функции по метода на Карно

 През 1953 год. Морис Карно публикува статия, в която описва своя метод за опростяване на булеви изрази с помощта на специални таблици, които по-нататьк са били наречени карти на Карно. Картата на Карно се състои от полета, които са толкова на брой, колкото са комбинациите на променливите за всяка отделна функция. Задължителното условие е две съседни полета трябва да отговарят на изискването да се отличават едно от друго само с по една променлива.

Например и се отличават само с една променлива Х_1, а

  и се отличават с две променливи Х₂ и Х₃.

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

Например за логическата функция от три променливи картата ще съдържа 8 полета, защото 2³ = 8. На фиг. 1 е показан принципът на разбиване на полетата за три променливи.

Ако въведем данните на таблицата на истинността в картата на Карно, то ще получим разпределение, показано в таблица 1.

По отношение на показаната карта, трябва да се отбележи, че полетата на крайния ляв ред се явяват като продължение на полетата в крайния десен ред. Това означава, че полетата с номера 0 и 1 се разполагат срещу полетата с номера 4 и 5 и те трябва да се разглеждат като съседни.

За да разберете принципа на минимизирането с помощта на картите на Карно, ще разгледаме следния пример.

Пример. Да се минимизира с помощта на картите на Карно логическата функция

* конюнкция

+ дизюнкция

Таблица 2

Единиците се записват в тези полета, където функцията е равна на единица.

Таблица 3

Ако две единици се намират в съседните полета, те се заграждат и това означава, че тези два члена могат да бъдат преобразувани (минимизирани) според изложеното по-горе правило.

В резултат на преобразуванията се получава окончателният запис на фун кцията:

На фиг. 2 е показано разбиване на карта на Карно за четири променливи.

 Фиг. 2

а) Разбиване на полета

б) връзка между полета и

комбинации от променливи

в) Номериране на полета

Разбиване на картата на Карно за четири променливи

Ако запишем минтермите на дадена Булева функция в съответните клетки, определени от единиците на функцията, то минтермите, лежащи в съседни клетки ще могат да се слепват. Това ценно свойство се използва за минимизация на Булеви функции.

Да обобщим:

1. Картата на Карно се състои от толкова на брой полета, колкото са комбинациите на променливите за всяка отделна функция. (за 3 променливи 2³=8 полета).

2. Задължително условие е: две съседни полета да се отличават едно от друго само с по една променлива.

Как се получава картата на Карно:

1. Функцията се записва в ДНФ.

2. Всеки член на функцията (минтерм), който се съдържа в тази форма, се записва на картата като “1” в съответното поле.

3. След това се групират единиците в съответстващите полета и се очертават със затворени линии (елипси).

4. Правило: от полетата може да бъде отстранена една променлива, а именно тази, за която в съседното поле се намира нейното допълване (отрицание).

предишна тема            следваща тема

изтегли PDF