Анализ и синтез на логически схеми
Функционално пълна система (базис) от логически функции и логически елементи
Изтегляне 1.14 Mb.
|
Свързани:
an-architectural-reassessment-of-a-villa-rustica-near-serdica, New Microsoft PowerPoint Presentation, кр цсх
| 2. Функционално пълна система (базис) от логически функции и логически елементи.
Вече беше показано, че всяка логическа функция може да бъде представена в СДНФ или СКНФ. В тези форми на запис участват логическите операции конюнкция, дизюнкция и отрицание. Следователно, за представянето на коя да е логическа функция е достатъчно да бъдат използвани елементарните логически функции И, ИЛИ и НЕ. Те образуват т.нар. функционално пълен базис от логически функции. Техническите средства, които реализират тези ЛФ, се наричат логически елементи и образуват функционално пълен базис от логически елементи (фиг.2.4.). фиг.2.4. Ако от този базис бъде изключена функцията ИЛИ, с останалите функции - И и НЕ също може да бъде представена коя да е логическа функция, тъй като чрез тях може да бъде представена липсващата ЛФ. Твърдението може да бъде доказано чрез закона на де Морган: Разполагаме с функциите и ; От закона на де Морган следва, че функцията f3(x1, x2)=x1+x2 може да се получи като . Следователно функциите И и НЕ притежават функционална пълнота, а оттам и логическите елементи, реализиращи тези функции. Аналогично може да бъде доказано, че функционално пълен базис представляват и функциите ИЛИ и НЕ. Базисът, съставен от функцията И-НЕ, (функция на Шефер), също е функционално пълен. Следователно базисът, съставен от логическия елемент (NAND, И-НЕ), реализиращ тази функция, също притежава функционална пълнота. Доказателство: Разполага се с функцията . Чрез нея трябва да бъдат изразени функциите , , и реализирани чрез логически елемент И-НЕ. Прилагаме някои от законите, теоремите и аксиомите на алгебрата на логиката и получаваме: Функцията може да бъде получена и по друг начин: . По аналогичен начин може да бъде доказано, че базисът ИЛИ-НЕ също е функционално пълен (респективно - функционално пълен е базисът, съставен само от логическия елемент ИЛИ-НЕ ). Функционално пълните системи от ЛФ И-ИЛИ-НЕ, И-НЕ и ИЛИ-НЕ и съответните логически елементи, с които се реализират тези функции, са най-разпространени и най-често използвани в практиката. Съществуват и други функционално пълни системи от ЛФ, като например: импликация, константа “0”; импликация, инверсия; забрана, инверсия; забрана, равнозначност; импликация, неравнозначност; конюнкция, равнозначност, константа “0”; дизюнкция, равнозначност, константа “0”; конюнкция, неравнозначност, константа “1”; дизюнкция, неравнозначност, константа “1”; конюнкция, равнозначност, неравнозначност; дизюнкция, равнозначност, неравнозначност и др., но те почти не се използват в практиката, тъй като не са разработени логически елементи, които да ги реализират. Изтегляне 1.14 Mb. Сподели с приятели:
|