Графическое изображение элементов для комбинационной схемы.

Зв'язок логічних функцій і функціональних схем

Побудова комп'ютерних обчислювальних систем безпосередньо пов'язана з використанням різноманітних логічних функцій. З усіх перерахованих логічних функцій апаратно реалізовані в різноманітних серіях мікросхем логічні операції "І", "АБО", "НЕ", а також "І - НЕ" і "АБО - НЕ".

Практична реалізація логічних функцій на апаратному рівні провадиться у відповідності з такою послідовністю:

<логічна функція> <функціональна схема> <принципова схема>.

Функціональні блоки логічних схем будуть надалі використані при розробці схем кінцевих автоматів. Розглянемо представлення основних логічних функцій за допомогою функціональних блоків (табл.4).

Інші логічні функції, подані в табл. 3, можуть бути виражені через наведений набір найпростіших функцій.

 

Таблиця 4.

Представлення логічних функцій

№ п/п	Функція	Функціональний блок	Приклад
	І	& Х 1 ... У Х n	У = Х1ÙХ2Ù... ÙХn
	АБО	Х 1 У ... Х n	У = Х1ÚХ2Ú... ÚХn
	НЕ	Х У
g bGyVpi0q9fpoB6FNbxNLY4/SRbV61VdQ7Uk5hH5w6aOR0QB+5ayjoS25/7IRqDgzby2pPx2Ox3HK kzOeXIzIwfPI6jwirCSokgfOenMR+p+xcajXDb00TOVauKaO1TqJGbvZszqSpcFMGh8/UZz8cz9l /frq858AAAD//wMAUEsDBBQABgAIAAAAIQBSDc/F3wAAAAkBAAAPAAAAZHJzL2Rvd25yZXYueG1s TI/LTsMwEEX3SPyDNUjsqPNoAoRMqooKCRZdEGDvxtMkajyOYjcNf49ZwXJ0j+49U24WM4iZJtdb RohXEQjixuqeW4TPj5e7BxDOK9ZqsEwI3+RgU11flarQ9sLvNNe+FaGEXaEQOu/HQkrXdGSUW9mR OGRHOxnlwzm1Uk/qEsrNIJMoyqVRPYeFTo303FFzqs8GYddu63yWqc/S4+7VZ6ev/VsaI97eLNsn EJ4W/wfDr35Qhyo4HeyZtRMDQhbH64AirO8fQQQgS7IcxAEhTyKQVSn/f1D9AAAA//8DAFBLAQIt ABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10u eG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5y ZWxzUEsBAi0AFAAGAAgAAAAhAIOOf4AmAgAAMgQAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9E b2MueG1sUEsBAi0AFAAGAAgAAAAhAFINz8XfAAAACQEAAA8AAAAAAAAAAAAAAAAAgAQAAGRycy9k b3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAACMBQAAAAA= " o:allowincell="f"/>	І - НЕ	Х 1 ... У   Х n
	АБО - НЕ	Х 1 ... У Х n	&

"Спроектувати пристрій з елементів І, АБО, НЕ з трьома входами Х1, Х2, Х3, на виході якого з'являється сигнал У = 1 у випадку, якщо на вхід пристрою подається не парне двійкове число або число, кратне числу три (Х3 відповідає двійковому розряду з меншою вагою)".

&

&

&

парне двійкове число або число, кратне числу три (Х3 відповідає двійковому розряду з меншою вагою)". 1

 

y

 

 

х₁ х₂ х₃ х₃

Рис. 1. Приклад комбінаційної схеми

Деревья. Бинарные деревья.

Дерево — это связный ациклический граф.^[1] Связность означает наличие путей между любой парой вершин (связаны между собой отношениями типа «родительская вершина – дочерняя вершина), ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.

Определить дерево с вершинами типа T можно следующим образом: это либо пустое дерево, не содержащее ни одной вершины; Либо некоторая вершина типа Т, соединенная ветвями с конечным числом отдельных деревьев с другими вершинами типа Т (эти деревья называются поддеревьями).

Чаще всего дерево изображается в виде графа, вершинами которого являются вершины дерева, а ребрами — его ветви. Начальная вершина дерева, называемая корнем, изображается в верхней части графа, и считается, что она находится на нулевом уровне. Вершина Y, расположенная ниже вершины X и соединенная с ней ветвью, называется непосредственным потомком вершины X, или ее дочерней вершиной (а вершина X, соответственно, — непосредственным предком вершины Y, или ее родительской вершиной).

Термин двоичное дерево (оно же бинарное дерево) имеет несколько значений:

· Неориентированное дерево, в котором число рёбер не превосходят 3.

· Ориентированное дерево, в котором число исходящих рёбер не превосходят 2.

 

Особым видом деревьев являются бинарные деревья. Бинарное дерево с вершинами типа T можно определить следующим образом:

· это либо пустое дерево, не содержащее ни одной вершины;

· либо некоторая вершина типа T, соединенная ветвями с двумя бинарными деревьями с вершинами типа T (эти деревья называются левым и правым поддеревом).

 

Пример бинарного дерева приведен на рис. 2; в нем вершина со значением 0 является корнем, все вершины со значением 1 являются левыми дочерними вершинами, а все вершины со значением 2 — правыми

.