Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними.

Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2.

   Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным (обозначают значком бесконечности).
Так, расстояние между вершинами Б и Д графа, представленного на рисунке  бесконечно: S(БД) = ∞        

Ориентированные графы в экономике активно используются в сетевом планировании, в математике — в теории игр, теории множеств; при решении многих задач, в частности, комбинаторных.

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

Над возможностями применения логики в технике ученые и инженеры задумывались уже давно. Например, голландский физик Пауль Эренфест (1880 - 1933), еще в 1910 году писал: "...Пусть имеется проект схемы проводов автоматической телефонной станции. Надо определить:

1) будет ли она правильно функционировать при любой комбинации, могущей встретиться в ходе деятельности станции;
2) не содержит ли она излишних усложнений.

Почему необходимо уметь строить логические схемы?

Дело в том, что из вентилей составляют более сложные схемы, которые позволяют выполнять арифметические операции и хранить информацию. Причем схему, выполняющую определенные функции, можно построить из различных по сочетанию и количеству вентилей. Поэтому значение формального представления логической схемы чрезвычайно велико. Оно необходимо для того, чтобы разработчик имел возможность выбрать наиболее подходящий ему вариант построения схемы из вентилей. Процесс разработки общей логической схемы устройства (в том числе и компьютера в целом), становится иерархическим, причем на каждом следующем уровне в качестве "кирпичиков" используются логические схемы, созданные на предыдущем этапе.
Алгебра логики дала в руки конструкторам мощное средство разработки, анализа и совершенствования логических схем. В самом деле, гораздо проще, быстрее и дешевле изучать свойства и доказывать правильность работы схемы с помощью выражающей ее формулы, чем создавать реальное техническое устройство. Именно в этом состоит смысл любого математического моделирования.

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

Правило построения логических схем:

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

Примеры.

ТЕСТОВЫЕ ВОПРОСЫ К ТЕМЕ 4.

1.Электронная схема, применяемая в регистрах компьютера для запоминания одного разряда двоичного кода это …

A) вентиль

B) логическая схема

C) триггер

D) электронная схема

2.Часть электронной логической схемы, которая реализует элементарную логическую функцию – это …

A) логическая схема компьютера

B) логический элемент компьютера

C) электронный элемент компьютера

D) триггер

3. Такой структурной схемой обозначается    

       а) конъюнктор

       б) дизъюнктор

       в) вентиль не

     г) инвертор
4.Графическое изображение логичекого выражения называется

a) схема

b) чертеж

c) график

d) рисунок

5.Устройство, реализующее базовую логическую операцию называется:

a) регистр

b) ячейка

c) винтель

d) триггер

e) инвертор

7.

a) Конъюктор

b) Дизъюктор

c) Триггер

d) Инвертор

8. Определить сигнал на выходе из схемы

a) 1

b) 0

c) 10

d) 11

e) 2

9.

a) Да

b) нет