русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Логические основы функционирования компьютеров


Дата добавления: 2013-12-23; просмотров: 1180; Нарушение авторских прав


 

В компьютерах принцип программного управления реализуется с помощью арифметико – логического устройства (процессора), в основе устройства которого лежат аппаратные средства преобразования двоичных кодов. Математической основой работы этих устройств является алгебра логики.

В основе алгебры логики лежат понятия зависимой и независимой переменных (функции и аргумента). Их отличия от соответствующих понятий обычной алгебры в том, чтопеременные могут принимать лишь одноиз двух значений: 0 или 1. Пусть x1, х2,..., хn- двоичные аргументы, тогда функция y= f(x1...xn)является двоичной функцией двоичных аргументов, которая также может принимать значение либо 0, либо 1. Данная функция задается или аналитически, либо таблично. При табличном представлении значение функции должно быть задано на всех возможных наборах значений аргумента. Общее число этих наборов равно 2n,где n - число аргументов, а общее число всех возможных двоичных функций n двоичных аргументов будет 22n.

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

X Y0 Y1 Y2 Y3

 

Функция Y1, значения которой совпадают со значениями аргу­мента, называется тавтологией, или повторением, и записывается ана­литически

Y1= X (Y1тождественна X).Функция, значения которой противоположны значениям аргумента, называется инверсией, или отри­цанием. В таблице такой функцией является Y2=(Y2тождествен­на не X).Черта над аргументом означает отрицание или инверсное значение. Значение Y3 не изменяется при изменениях аргумента и всегда тождественно единице Y3=1 Это функция константа единицы.



Рассмотрим двоичные функции двух (п=2) двоичных аргументов. Всего таких функций 16, каждая из которых определена на 22=4 на­борах значений аргумента.

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

X1 X2 Y1 Y7 Y12 Y10

 

 

Функция Y1=X1 Λ X2соответствует операции логического умно­жения и называется конъюнкцией. Знак Λ (или &) обозначает действие логического умножения. Иногда она обозначается как «·». Это действие выполняет устройство, которое называется автомат "И”. На схемах это устройство обозначается так:

&
X1
X2
Y1
«И»

 

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

Функция Y7 = X1 v X2похожа (за исключением последней строки на операцию арифметического сложения и соответствует операции логического сложения (v - знак логического сложения). Данная функция называется дизъюнкцией и обращается в нуль только тогда, когда аргументы равны нулю, и в единицу - во всех остальных случаях. Это действие выполняет автомат "ИЛИ", имеющий следующее обозначение

 

X1
X2
Y7
«ИЛИ»  

Функции Y12= 1 и Y10= 2 соответствуют операции инверсии ( или отрицания) и выполняются автоматом "НЕ", со следующим обозначением.

Xi
Yi
«не»

Но если операции "И" и "ИЛИ" могут выполняться над произвольным числом аргументов n > 2, то операция «НЕ» всегда выполняется над одним аргументом.

Среди множества двоичных функций есть такие, которые принимают значение 1 лишь на одном наборе двоичных аргументов. Такие функции называются конституентами единицы. Для n =2 данные функции приведены в следующей таблице.

 

X1 X2 Y1 Y2 Y4 Y8

 

Y8=

Y4=

Y2=

Y1=

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

Аналитическое выражение для любой заданной таблично двоичной функции можно записать с помощью совершенной дизъюнктивной нормальной формы (СДНФ). СДНФ - это дизъюнкция конституент единицы, записанных для тех наборов двоичных аргументов, на кото­рых функция принимает единичное значение. Пусть функция у= f(x1,x2,x3) задана в виде нижеприведённой таблицы.

X1 X2 X3 Y

 

Аналитическая запись данной функции в СДНФ будет представлять дизъюнкцию трех конституент еди­ницы, записанных для 3,5и 6строк таблицы, т.е.

Y=

 

Таким образом, с помощью трех функций и соответствующих им трех логических действий можно записать или формально выразить любую логическую функцию. Другими словами, в алгебре логики опре­делено только три логических действия, никаких других действий нет. Порядок выполнения действий: сначала выполняется инверсия, затем конъюнкция и последним - дизъюнкция. Если есть скобки, то сначала выполняются операции в скобках.

При выполнении логических действий необходимо знать следующие основные соотношения для логических сложения и умножения:

 

x v 0 = x x v 1 =1 x v x = x x v = 1

 

x Λ 0 = 0 x Λ 1 = x x Λ x = x x Λ = 0

 

= x x v x v … v x = x x Λ x Λ … Λ x = x

 

 

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

 

 

Основные законы алгебры логики:

1. Переместительный закон. От перестановки мест двоичных аргументов значение логического выражения не изменяется:

 

X1V X2=X2V X1

2. Сочетательный закон. Значение логического выражения не зависит от последовательности действий над логическими переменными.

X1 X2 X3 = X1 ( X2 X3) = (X1 X2) X3

X1 v X2 v X3 =(X1 v X2) V X3 = X1 v (X2 v X3)

 

3. Первый распределительный закон: X1 (X2 v X3) = X1X2 v X1X3

Из приведенных законов следует, что, как и в обычной алгебре, логические переменные можно менять местами и выносить за скобки. Однако в алгебре логики есть еще законы, которые не аналогов в обычной алгебре.

4. Второй распределительный закон: X1 v X2X3 = (X1 v X2)(X1 v X3)

5. Закон инверсии. Этот закон базируется на теореме де Моргана, которая формулируется следующим образом. При замене в исходной,
логической функции аргументов их отрицаниями, знаков логического
сложения знаками логического умножения, а знаков логического умножения знаками логического сложения получается функция, являющаяся
инверсной от исходной :

 

 

 

Указанные соотношения и законы позволяют проводить анализ и синтез логических схем, одним из этапов которых является построе­ние СДНФ. Рассмотрим способы образования СДНФ для заданных анали­тически логических выражений.

Первый способ заключается в том, что для заданной аналитичес­ки функции строится таблица истинности, из которой по рассмотрен­ному выше правилу записывается СДНФ.

Пример. Построить СДНФ для функции

Функция содержит три аргумента, для которых в таблице истин­ности заполняем 23=8 строк. Подставляя входные наборы аргументов в заданную функцию, определяем значения Y.

 

X1 Х2 X3 Y

 

Так, для первой строки Проводя ана­логичные действия для всех строк, заполняем столбец Y. Столбец для Y мог быть заполнен и исходя из анализа исходной функции. Так, функция Y будет принимать значение 1 в том случае, если X3= 1 либо . Последнее тождество возможно, когда либо X1 =0, либо X2=0. Т.е. Y=1 на тех наборах, когда либо X1=0,либо X2 =0,либо X3=1. Составив таблицу, СДНФ запишем как дизъюнкцию семи консти­туент единицы:

 

 

 

Второй способ образования СДНФ заключается в том, что:

· на основании теоремы де Моргана инверсии дизъюнкций и конъюнкций заменяются на конъюнкции и дизъюнкции инверсий аргу­ментов;

· раскрываются скобки во всех логических выражениях;

· образуются конституенты единицы домножением членов, не содержащих Xi , i= 1,2, … , n на с последующим раскрытием ско­бок;

· упорядочиваются соответствующие индексы во всех наборах аргументов.

Пример. Получить СДНФ для функции

Пользуясь теоремой де Моргана и проводя упрощения, получим

 

 

Домножим все члены на недостающее значение аргументов:

 

 

Раскрывая скобки и приводя подобные, СДНФ получим в виде

 

 

 



<== предыдущая лекция | следующая лекция ==>
Принцип программного управления | Анализ комбинационных схем


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.