Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Дискретни устройства без памет

Понятието за автомати, въведено в предишния раздел, е доста общо. Чрез налагане на ограничения върху компонентите X, Y, Q, Ψ, Θ можем да получим специални случаи на автомати. Един от тях са машини без памет, т.е. устройства, в които няма фиксиране на вътрешното състояние. Очевидно в този случай компонентите Q и Ψ трябва да бъдат изключени от общото описание; автоматична машина без памет се дефинира от тройка от компоненти < X, Y, .>. Съотношението (9.2) приема формата

т.е. символът на изхода на този цикъл се определя само от символа за въвеждане и не зависи от по-рано получени символи. Следователно, всеки автомат без памет реализира един конвертор (оператор), който изпълнява "литералния превод" на входните символни последователности в изхода.

Да предположим, че има дискретно устройство, което има n входа x 1 ..... x n и t изходи y 1 ..., y t . Ако устройството няма памет, преобразуването на входните сигнали в изхода се описва чрез система от уравнения:

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

Такива устройства могат да бъдат изградени чрез комбиниране на определен набор от елементарни компоненти (елементи). Тези елементи образуват крайно множество, наречено основа, а елементите, включени в нея - основни. Основата има значението на набор от елементарни (най-прости) действия, които бяха обсъдени в теорията на алгоритмите, а основният елемент може да се разглежда като устройство, което извършва елементарно действие. Ако говорим за двоични дискретни устройства, тогава базите се изграждат от елементи, които реализират най-простите логически функции. Припомнете си, че такива функции включват конюнкцията (логическо AND - ^), дизюнкция (логическо OR - v), импликация (→), по модул 2 (Å), еквивалентност ( ~ ) и отрицания (логически НЕ - Ø,). Въпреки това, между най-простите функции има отношения на еквивалентност (виж приложението), които позволяват да се изразят някои функции чрез други. В резултат се оказва, че няма нужда да се включват в базата всички елементи, които изпълняват най-простите логически функции - достатъчно е да се избере някаква минимална подмножество от тях. Това условие се изпълнява от основата, изградена върху елементите AND, OR и NOT - нарича се най -простата, а включените в нея елементи се наричат логически елементи или (логически порти). Диаграмите на елементите са показани на фиг. 9.1. Помислете за всеки от тях поотделно.

Елементът А (^) има два входа, към които могат да се подават сигнали х 1 и х 2 ; всеки от сигналите е двоичен, т.е. може да бъде една от двете стойности - 1 или 0; елементът формира единствения изходен сигнал y, чиито стойности се определят само от входните сигнали. Изходна функция Q (x 1 , x 2 ) според таб. Б.1 (вж. Приложение Б) приема следните стойности:

Функцията на изходите на елемента OR (V) приема следните стойности:

Логическият елемент NOT (Ø) осигурява единично преобразуване (с един входен сигнал) в съответствие с правилата:

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

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





Вижте също:

Пример А.3

Пример А.5

Тестови въпроси и задачи

Пример 7.2

Пример 9.4

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru