АСЛС - сбит материал

1. Алгебра на логиката. Логически функции. Дефиниции.Свойства.
- логически константи - логическа 0 и логическа 1;
- логическа променлива - всяка величина , която може да приема само две стойности – „0” и „1”
- логическа функция - функция на краен брой логически променливи, която може да приема само две стойности – „ 0” и „1”.
- набор - всяка комбинация от стойности на аргументите на дадена функция.
Тъй като аргументите могат да приемат само две стойности, броят на различните набори от n аргумента е 2n.
Броят на различните функции от n аргумента е 2n. Например, при 4 аргумента броят на наборите е 4, а на различните функции е 22n=16.
Всяка логическа функция f(x1, x2, ..., xn) разделя множеството от 2n набора на две непресичащи се подмножества: подмножество на единичните набори(за които функцията е 1); подмножество на нулевите набори(за които функцията е 0). Функция от този тип се нарича напълно определена логическа функция.
Една логическа функция може да бъде и непълно определена, т.е. за определени набори функцията не получава определена стойност.
Две логически функции са еквивалентни (тъждествени), ако зависят от едни и същи променливи и приемат едни и същи стойности за всеки набор на аргументите си: f1(x1, x2, ..., xn)=f2(x1, x2, ..., xn).
Една логическа функция на n аргумента е съществено независима от i-тия аргумент, ако приема една и съща стойност за различни значения на този аргумент, при което той може да бъде изключен от записа на функцията:

2. Алгебра на логиката. Елементарни ЛФ(на една и две променливи).
ЕЛФ - функции, които зависят от един и от два аргумента(+ „0” и „1”).
Техническите средства, които реализират тези ЛФ се наричат логически елементи. С тяхна помощ се изграждат логическите схеми.
Функциите „0” и „1” се наричат тривиални - за тяхното техническо реализиране не са необходими елементи.
функцията „x” също е тривиална - за реализирането й също не са необходими елементи, тъй като нейната стойност съвпада със стойността на аргумента й.
Техническото средство, което реализира функцията инверсия е логически елемент, наречен инвертор. Той
Функцията конюнкция(и Лог.Произв.) приема „1”, когато всичките й аргумента едновременно са „1”(„И” - „.”).
Функцията дизюнкция(и Лог.Сума) приема „1”, когато поне един от аргументите й е „1”(„ИЛИ” - “+” или “V”).
Дефинициите за инверсните функции могат да се получат от горните, като вместо стойност 1 на функцията се запише стойност 0.
Функциите логическа равнозначност и логическа неравнозначност също могат да се дефинират за n аргумента.

3. Алгебра на логиката. Аксиоми, основни правила и закони. Примери.

Таблицата може да бъде допълнена с теоремата на Шенон, която се явява приложение на закона на де Морган върху n аргумента и гласи следното:

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

4. Алгебра на логиката. Методи за представяне на логически функции. Примери.
Поведението на коя да е логическа функция в зависимост от стойностите на аргументити й може да бъде описано по един от следните начини:
А) Описателно - поведението на функцията се описва словесно.
Примери: Логическо произведение (конюнкция) на два аргумента е такава логическа функция f(1), която приема стойност 1, само в случай че и двата аргумента приемат стойност 1.
Б) Таблично.
Функцията се представя чрез таблица, в която се записват всички набори от аргументите и стойностите на функцията за всеки набор. Таблицата се нарича таблица на истинност.
Примери:

В) Аналитично.
Функциите се представят с логически изрази. Логическите изрази - формули, състоящи се от лог. константи и променливи, свързани с операциите И, ИЛИ и НЕ.

Г) Графично.
Функцията се представя чрез карта на Карно (КК).

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

6. Методи за минимизация на ЛФ. Примери.
А) графичен – КК
Б) Метод на Куайн и Куайн МакКласки
В) Метод на Нелсон
Г) Харвардски метод

7 и 8. Минимизация на логически функции с карти на Карно. Примери.
КК се използват за получаване на М*Ф на ЛФ.
МДНФ е сумата от „1”,а МКНФ е сбор от „0”.
Минимизацията на непълно определени ЛФ е с *.

10. Функционално пълен набор от ЛФ и ЛЕ.
функционално пълен базис от логически функции - за представянето на коя да е логическа функция чрез използването на елементарните логически функции И, ИЛИ и НЕ.
Ако се изключои ИЛИ или И...
Функционално пълните системи от ЛФ И-ИЛИ-НЕ, И-НЕ и ИЛИ-НЕ и съответните логически елементи, с които се реализират тези функции, са най-разпространени и най-често използвани в практиката. Съществуват и други функционално пълни системи от ЛФ, но те почти не се използват в практиката, тъй като не са разработени логически елементи, които да ги реализират.

11-13. Синтез на КЛС.
Схемите, изградени от логически елементи, се наричат логически схеми.
Логическа схема, чиито изходни сигнали в определен момент от времето зависят само от входните сигнали в същия момент от времето, се нарича КЛС (фиг.2.5.).

фиг.2.5.
Y(t)=f(X(t)), където Y={y0, y1, ..., yk-1}; X={x0, x1, ..., xn-1}
Процедурата за синтез на КЛС се състои в изпълнението на следните стъпки:
1).Описване на логическата функция(и), която реализира схемата, чрез карта на Карно или чрез таблица на истинност.
2).Намиране на минималната форма на функцията(ите).
3).Преобразуване на минималната форма в съответствие с функционално пълния базис за реализация.

14. Метод на Куайн МакКласки
А)Съставя се таблица на истинност с „1” или „*” на всички функции и се групира по редове с брои „1” на X.
Б)Ако стойността само на една променлива X в два съседни класа се различава то може да се образува нова точка(-), покриваща ги. Ако има поне една „1” на изхода на функцията, то новата функция е „1”.
В)Точки, които нямат „V”, а функцията им е „1” се наричат прости импликанти. Те се включват в функцията като множество от малки функции.
Г)Построява се импликантна матрица(колоните са минтерми[mi], а редовете – простите импликанти). С „V” се отбелязват минтермите, които тя покрива.
Д)Отделят се съществените(колоните само със един „V”) просто импликанти, заедно с който отпада и съответният минтерм. След което се оформя нова импликантна матрица.
Е)Определя се минималният брой просто импликанти и се записват всички МДНФ на функцията, в които участват съществените прости импликанти.

15. Първи подход.
Получава се МДНФ за всяка функция, схемата се реализира в даден базис.

16. Втори подход.
Функциите(fn) се реализират в КК, след което всички съвпадащи единички от всички КК се извеждат в нова функция(Ф), която участва накрая във всички функции(fn) и се реализира в даден базис.
Предимства - необходимите за реализация логически елементи са по-малко на брой.
Този подход е подходящ, когато функциите се припокриват в значителна степен.
Тъй като при разгледаните два подхода за минимизация се използват картите на Карно, то е валидно ограничението, което те налагат за броя на аргументите на логическите функции - този брой не може да надвишава пет.

19. Декомпозиция на ЛФ при синтез на КЛС.
Представянето на една логическа функция чрез други логически функции се нарича декомпозиция.
От различните видове декомпозиции интерес представляват тези, които дават възможност сложна логическа функция да се представи чрез логически функции на по-малък брой променливи, например:

където с y1, y2, ..., yq са означени онези аргументи xi, от които зависи функцията Ф1, а със z1, z2, ..., zp - аргумeнтите xj, от които зависи функцията Ф2. Първите се наричат свързани, а вторите - свободни аргументи.
а) Множествата Y и Z нямат общи елементи (сечението им е празното множество), т.е. не съществуват аргументи xk, които едновременно да попадат и сред свободните, и сред свързаните. Съответната декомпозиция се нарича проста разделителна декомпозиция.
б) Множествата Y и Z имат общи елементи, съществуват аргументи xk, които едновременно попадат и сред свободните, и сред свързаните. Съответната декомпозиция се нарича проста неразделителна декомпозиция.

20. Преобразуватели на кодове
Преобразувателите на кодове са с няколко изхода, който се синтезират всеки поотделно, като N сегмента. Прави се таблица на истинност в която участват всички входове и изходи след което чрез КК се минимизират функциите на изходите и се реализира схемата в даденият базис.

21. Шифратори.
Шифраторите представляват преобразуватели от унитарен код в двоичен код и в общия случай имат 2n входа и n изхода. На изходите на схемата се получава двоичният код на номера на входа, към който е подадено активно ниво (0 или 1). В случай че на няколко входа има подадено активно ниво, то като резултат, на изходите се получава двоичният код на най-високоприоритетния активиран вход. Шифраторите от този тип се наричат приоритетни шифратори.

22. Дешифратори.
Дешифраторите представляват КЛС, които преобразуват n-разряден двоичен код в унитарен код и в общия случай имат n входа и 2n изхода. Казано с други думи, те служат за дешифриране на n-разрядни двоични комбинации, като за всяка комбинация на входните сигнали сигнал 1 се пoлучава само на един от изходите - на този, чийто индекс представлява десетичният еквивалент на подадената на входа двоична комбинация.
Действието на дешифратора се описва от следните логически изрази:

Дешифраторите, които имат всичките 2n изходи, се наричат пълни.

23.Мултиплексори.
Функцията за избор на данни от един от няколко източника се изпълнява от устройства, наречени мултиплексори. Мултиплексорите представляват КЛС, които имат n адресни (управляващи) входове, 2n информационни входове и един изход.
Към изхода на схемата се превключва този от информационните входове, чийто индекс представлява десетичният еквивалент на двоичната комбинация, подадена на адресните входове.
Мултиплексорът работи при нулево ниво на разрешаващия вход. Ако на този вход е подадено ниво логическа 1, на изхода на мултиплексора се получава 0 независимо от информацията, подадена на останалите входове.
Таблицата на истинност, описваща работата на мултиплексора, има следния вид:
Оттук може да бъде изведен и логическият израз, по който ще бъде ре