Попов И.И., Матвеев А.А., Максимов Н.В. Архитектура электронно-вычислительных машин и систем (2004) (1186255), страница 12
Текст из файла (страница 12)
Прежде всего термы-произведения разбиваются на пары,отличающиеся единой переменной, которая в одном терме стоит сознаком ¬ (¬х), а во втором – без него (х). Затем в каждой паре общеепроизведение двух переменных выносится за скобки, а в скобкахостается терм ¬х + х, всегда равный 1. Вот что мы получим, применивэту процедуру к первому выражению для функции f1 (на рис.___ слева).ƒ1 = ¬х1 ¬х2 ¬х3 + ¬х1 ¬х2 х3 + ¬х1 х2 х3+ х1 х2 х3 == ¬х1 ¬х2 (¬х3+х3) + (¬х1+х1) х2 х3 == ¬х1 ¬х2 • 1 + 1 • х2 х3 ==¬х1 ¬х2 + х2 х3Это выражение минимально.
Соответствующая ему логическаясхема приведена на рис.___. справа.66Переключательные схемыВ компьютерах и других автоматических устройствах широкоприменяются электрические схемы, содержащие сотни и тысячипереключательных элементов: реле, выключателей и т.п. Разработкатаких схем весьма трудоёмкое дело и здесь с успехом может бытьиспользован аппарат алгебры логики.Переключательная схема — это схематическое изображениенекоторого устройства, состоящего из переключателей и соединяющихих проводников, а также из входов и выходов, на которые подаётся и скоторых снимается электрический сигнал.Каждый переключатель имеет только два состояния: замкнутое иразомкнутое.
Переключателю Х поставим в соответствие логическуюпеременную х, которая принимает значение 1 в том и только в томслучае, когда переключатель Х замкнут и схема проводит ток; если жепереключатель разомкнут, то х равен нулю.Два переключателя Х и связаны таким образом, что когда Хзамкнут, торазомкнут, и наоборот. Следовательно, еслипереключателю Х поставлена в соответствие логическая переменная х,то переключателю должна соответствовать переменная .Всей переключательной схеме также можно поставить всоответствие логическую переменную, равную единице, если схемапроводит ток, и равную нулю — если не проводит.
Эта переменнаяявляется функцией от переменных, соответствующих всемпереключателям схемы, и называется функцией проводимости F.Найдем функции проводимости F некоторых переключательныхсхем:Таблица 10Структура и функции проводимости некоторыхпереключательных схем№1234СхемаПояснениеФункция проводимостиСхема не содержитF=1переключателейипроводит ток всегдаСхема содержит одинF=0постоянноразомкнутый контактСхема проводит ток,F(x) = x;когда переключатель хзамкнут,инепроводит, когда хразомкнут,следовательно,Схема проводит ток,F(x) = ;67567когда переключатель хразомкнут,инепроводит, когда хзамкнутСхема проводит ток,когдаобапереключателязамкнутыСхема проводит ток,когда хотя бы один изпереключателейзамкнутF(x) = x & y;F(x)=x ∪ y;Схема состоит из двухпараллельных ветвейДве схемы называются равносильными, если через одну из нихпроходит ток тогда и только тогда, когда он проходит через другую (приодном и том же входном сигнале).Из двух равносильных схем более простой считается та схема,функция проводимости которой содержит меньшее число логическихопераций или переключателей.Задача нахождения среди равносильных схем наиболее простыхявляется очень важной.При рассмотрении переключательных схем возникают двеосновные задачи: синтез и анализ схемы.Синтез схемы по заданным условиям ее работы сводится к трёмэтапам:- составлению функции проводимости по таблице истинности,отражающей эти условия;- упрощению этой функции;- построению соответствующей схемы.Анализ схемы сводится к- определению значений её функции проводимости при всехвозможных наборах входящих в эту функцию переменных.- получению упрощённой формулы.В табл.
11 приводятся примеры синтеза (строки 1, 2), и анализа(строка 3) переключательных схем68Таблица 11Примеры анализа и синтеза переключательных схемОписаниесхемы1 Содержит4переключателя, x, y, z и t, ипроводит токтогда и толькотогда,когдазамкнутконтактпереключателяt и какойнибудьизостальныхтрёхконтактов.2 Содержит5переключателей и проводитток в том итолько в томслучае, когдазамкнутыровно четыреизэтихпереключателей.3 Имеетсячетыревозможныхпутипрохождениятокапризамкнутыхпереключателях a, b, c, d, e :черезпереключатели a, b; черезпереключатели a, e, d; черезпереключатели c, d и черезпереключатели c, e, b.Функция проводимостиF(x, y, z, t) = t .
(x v y v z)F(a, b, c, d, e) = (a ∧ b). ∨(a ∧ e ∧ d) ∨ (c ∧ d) ∨ (c ∧ e ∧ b69СхемаТаблица 12Примеры упрощения переключательных схемИсходная схемаРешениеОкончательнаясхема1.2Здесьпервоеслагаемоеотрицаниемлогическогологическоеявляетсявторогослагаемого,адизъюнкцияпеременной с ее инверсиейравна 1.345(по закону склеивания)Решение логических задач средствами алгебры логики————Обычно используется следующая схема решения:изучается условие задачи;вводится система обозначений для логических высказываний;конструируется логическая формула, описывающая логическиесвязи между всеми высказываниями условия задачи;определяются значения истинности этой логической формулы;70— из полученных значений истинности формулы определяютсязначения истинности введённых логических высказываний, наосновании которых делается заключение о решении.Пример.
Некий любитель приключений отправился в кругосветноепутешествие на яхте, оснащённой бортовым компьютером. Егопредупредили, что чаще всего выходят из строя три узла компьютера —a, b, c, и дали необходимые детали для замены. Выяснить, какой именноузел надо заменить, он может по сигнальным лампочкам на контрольнойпанели. Лампочек тоже ровно три: x, y и z.Инструкция по выявлению неисправных узлов такова:если неисправен хотя бы один из узлов компьютера, то горит покрайней мере одна из лампочек x, y, z;если неисправен узел a, но исправен узел с, то загорается лампочкаy;если неисправен узел с, но исправен узел b, загорается лампочка y,но не загорается лампочка x;если неисправен узел b, но исправен узел c, то загораютсялампочки x и y или не загорается лампочка x;если горит лампочка х и при этом либо неисправен узел а, либовсе три узла a, b, c исправны, то горит и лампочка y.В пути компьютер сломался.
На контрольной панели загореласьлампочка x. Изучив инструкцию, путешественник починил компьютер.Какие узлы заменил путешественник и какие изъяны он обнаружил винструкции?Решение. Введем обозначения для логических высказываний:a — неисправен узел а; x — горит лампочка х;b — неисправен узел b; y — горит лампочка y;с — неисправен узел с; z — горит лампочка z.Правила 1–5 выражаются следующими формулами:Формулы 1–5 истинны по условию, следовательно, их конъюнкциятоже истинна:Выражая импликацию через дизъюнкцию и отрицание (поскольку), получаем:71Подставляя в это тождество конкретные значения истинности x=1,y=0, z=0, получаем:Отсюда следует, что a=0, b=1, c=1.Ответ на первый вопрос задачи: нужно заменить блоки b и c; блока не требует замены. Ответ на второй вопрос задачи получитесамостоятельно.Узлы ЭВМУзлами ЭВМ являются стандартизованные наборы логическихэлементов, из которых, как из «кирпичиков» набираются схемы,входящие в состав микропроцессоров, блоков памяти, контроллероввнешних устройств и пр.Узлы ЭВМ разделяются на :1.
комбинационные - это узлы, выходные сигналы которыхопределяются только сигналом на входе, действующим в настоящиймомент времени (например, дешифратор).Выходной сигнал дешифратора зависит только от двоичного кода,поданного на вход в настоящий момент времени. Комбинационные узлыназывают также автоматами без памяти.Рис. 12. Фрагмент (3 разряда) схемы многоразрядного сумматора2. последовательностные (автоматы с памятью) - это узлы,выходной сигнал которых зависит не только от комбинации входныхсигналов, действующих в настоящий момент времени, но и отпредыдущего состояния узла (счетчик).3. программируемые узлы функционируют в зависимости от того,какая программа в них записана. Например, программируемаялогическая матрица (ПЛМ), которая в зависимости от прожженной в нейпрограммы может выполнять функции сумматора, дешифратора, ПЗУ.72Многоразрядный сумматор процессора состоит из полныходноразрядных сумматоров (рис.
12). На каждый разряд ставитсяодноразрядный сумматор, причем выход (перенос) сумматора младшегоразряда подключен к входу сумматора старшего разряда.Например, схема вычисления суммы S = (s3 s2 s1 s0) двухдвоичных трехразрядных чисел A = (a2 a1 a0) и B = (b2 b1 b0) можетиметь вид, приведенный на рис.13:Сумматор может быть построен как:- комбинационная схема (последовательный сумматор), или- последовательностная схема (накапливающий сумматор).Рис. 13 Последовательный сумматорПоследовательный сумматор осуществляет суммированиеслагаемых и цифр переноса поразрядно, начиная с младшего разряда.Основой его схемы является одноразрядный сумматор. Суммированиепроизводится в одноразрядном сумматоре SM.а)б)Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
