Информатика конспект лекций_2012

Пример 13. Точками сочленения графа, изображенного на рис. 12, являются вершины v3, v4, v6, v7.

10

Рис. 12. Точки сочленения графа

Следующее утверждение очевидно.

Утверждение 12. Если D/ – орграф, полученный в результате удаления нескольких вершин из орграфа D, то A(D/) получается из A(D) в результате удаления строк и столбцов, соответствующих удаленным вершинам.

Замечание 7. Аналогичное утверждение справедливо и для произвольных псевдографов (ориентированных и неориентированных).

Матрицы связности

Пусть D = (V, X) – орграф, где V={v1,.....,vn}. Матрицей дости-

жимости орграфа D называется квадратная матрица Т(D) = [tij] порядка n, у которой tij = 1, если вершина vj достижима из vi и tij = 0

– в противном случае. Матрицей сильной связности орграфа D называется квадратная матрица S(D) = [sij] порядка n, у которой sij = l, если вершина vj достижима из vj, и одновременно vj достижима из vi,

иsij = 0 – в противном случае (т. е. sij = 1 тогда и только тогда, когда вершины vj и vi принадлежат одной компоненте сильной связности орграфа D.

Пусть G = (V, X) – граф, где V = {v1,.....,vn}. Матрицей связности

графа G называется квадратная матрица S(G ) = [sij] порядка п, у которой sij = 1, если i = j или существует маршрут, соединяющий vj и vi,

иsij = 0 – в противном случае (т. е. sij = 1,тогда и только тогда, когда вершины vj и vi принадлежат одной компоненте связности графа G.

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

Утверждение 13. Пусть G = (V, X), где V = {v1,.....,vn} – граф с матрицей смежности А = А(G).

50

Тогда: S(G) = sign(E + A + A2 +... + An−1)= E A A2 ... An−1,

где Е – единичная матрица порядка n.

Утверждение 14. Пусть D = (V, X), где V = {v1,.....,vn} – орграф с матрицей смежности А = А(D). Тогда:

1) T (D) = sign(E + A + A2 +... + An−1)= E A A2 ... An−1 , где

Е – единичная матрица порядка n;

2) S(D) = T (D) & [T (D)]* , где * – обозначение операции транспо-

нирования матрицы.

Утверждения 13 и 14 дают простые, легко реализуемые на ЭВМ методы вычисления матриц S(G), T(D), S(D). Существуют и более экономичные методы вычисления этих матриц, например, метод Уоршелла.

Выделение компонент связности

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

Воспользуемся следующими утверждениями.

Утверждение 15. Пусть D – орграф с р ≥ 2 компонентами сильной связности: D1,...,Dp. Тогда, в результате удаления из D вершин, содержащихся в D1, получаем орграф с р-1 компонентами сильной связности: D2,...,Dp.

Воспользуемся тем очевидным фактом, что если D' – компонента сильной связности орграфа D, то D' является компонентой сильной связности и любого подграфа орграфа D, содержащего все вершины и дуги орграфа D'. Заключаем, что после удаления из D вершин, содержащихся в D1, имеем орграф D, подграфами которого являются D2,...,Dp, а следовательно, D2,...,Dp являются компонентами сильной связности орграфа D. Далее получаем, что объединение множеств вершин орграфов D2,...,Dp дает множество вершин орграфа D, а значит D2,...,Dp – все компоненты сильной связности орграфа D.

Утверждение 16. Пусть D' – компонента сильной связности орграфа D. Пусть также p(D) ≥ 2 и D" – орграф, получаемый в результате удаления из D вершин, содержащихся в D'. Тогда матрицами А(D"), S(D") являются подматрицы матриц A(D), S(D), получаемые в результате удаления из них строк и столбцов, соответствующих вершинам орграфа D'.

51

Утверждение 17. Единицы i-й строки или i-го столбца матрицы сильной связности орграфа D = (V, X), где V = {v1,.....,vn}, соответствуют вершинам компоненты сильной связности орграфа D, содержащей вершину vi.

Из утверждений 15 – 17 следует справедливость алгоритма определения числа компонент сильной связности орграфа D, а также матриц смежности этих компонент.

Алгоритм 1. Шаг 1. Полагаем р = 1, S1 = S(D).

Шаг 2. Включаем в множество вершин Vp очередной компонент сильной связности Dp орграфа D вершины, соответствующий единицам первой строки матрицы Sp. В качестве A(Dp) берем подматрицу матрицы A(D), находящуюся на пересечении строк и столбцов, соответствующих вершинам из Vp.

Шаг 3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если в результате такого вычеркивания не остается ни одной строки (и соответственно ни одного столбца), то р – количество компонент сильной связности и A(D1),...,A(Dp) – матрицы смежности компонент сильной связности D1,...,Dp орграфа D. В противном случае, обозначаем оставшуюся после вычеркивания из Sp соответствующих строк и столбцов матрицу через Sp+1, присваиваем р:= р+1 и переходим к шагу 2.

Замечание 8. После изменений в обозначениях и терминологии алгоритм 1 можно применить для определения числа компонент связности графа G, а также матриц смежности этих компонент. Для обоснования этого достаточно воспользоваться утверждениями, аналогичными утверждениям 15 – 17, но сформулированными для неориентированного графа G. Более того, алгоритм 1 остается справедливым и для произвольных псевдографов (ориентированных и не ориентированных). Доказательство аналогично.

52

ЛЕКЦИЯ 7. ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ

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

При записи тех или иных логических выражений используется специальный язык, который принят в математической логике. Ее основоположником является великий немецкий математик Готфрид Вильгельм Лейбниц. Ирландский математик Джордж Буль продолжил создание математической логики, которая оперирует не числами, а высказываниями. Высказывание – это любое утверждение, относительно которого можно сказать: истинно оно или ложно.

Так, например, предложение «7 – нечетное число» следует считать высказыванием, так как оно истинное. Предложение «Июль – зимний месяц» тоже высказывание, так как оно ложное.

Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения

«ученик десятого класса» и «информатика – интересный предмет».

Первое предложение ничего не утверждает об ученике, а второе использует слишком неопределённое понятие «интересный предмет». Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла.

Предложения типа «в городе A более миллиона жителей», «у него голубые глаза» не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно городе или человеке идет речь. Такие предложения называются высказывательными формами.

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

Употребляемые в обычной речи связки: «не», «и», «или», «если... , то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые. Такие слова и словосочетания называ-

ются логическими связками.

53

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

Элементарные высказывания соответствуют алгебраическим переменным, составные – функциям.

Так, например, из элементарных высказываний «Иванов – сыщик», «Иванов – скрипач» при помощи связки «и» можно получить составное высказывание «Иванов – сыщик и скрипач», понимаемое как «Иванов – сыщик, хорошо играющий на скрипке».

При помощи связки «ил» из этих же высказываний можно получить составное высказывание «Иванов – сыщик или скрипач», пони-

маемое в алгебре логики как «Иванов или сыщик, или скрипач, или и сыщик и скрипач одновременно».

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

К основным логическим операциям относят операцию НЕ (отрицание, инверсия – NOT), операцию И (логическое умножение, конъюнкция – AND), операцию ИЛИ (логическое сложение, дизъюнкция –

OR).

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

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

и1 («истина»). Логическая функция может также принимать два значения. Из этого следует, что логические переменные и функции определены на множестве двух значений – {0,1}.

Логические функции характеризуются (задаются) так называемыми таблицами истинности, или соответствия. Таблица истинности представляет собой таблицу, устанавливающую соответствие между возможными значениями наборов переменных и значениями функции. Сложные логические функции, как правило, выражаются через простые. Простые логические функции, зависящие от одной или двух

54

логических переменных, называются элементарными. Ниже, в табл. 9 и 10, приведены таблицы истинности базовых логических операций.

Таблица 9

Основные логические операции

X	Y	X and Y	X or Y
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

В вычислительной технике также часто используется операция «исключающее ИЛИ» (XOR), которая фактически сравнивает на совпадение два двоичных разряда. На практике, по технологическим причинам в качестве основного логического элемента используется элемент И-НЕ.

Таблица 10

Дополнительные логические операции

X	Y	X xor Y	Not(X and Y)
0	0	0	1
0	1	1	1
1	0	1	1
1	1	0	0

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

Математический аппарат алгебры логики очень удобен для описания функционирования аппаратных средств компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: «1» и «0».

55

Из этого следует два вывода:

1.Одни и те же устройства компьютера могут применяться для обработки и хранения как числовой информации, представленной

вдвоичной системе счисления, так и логических переменных.

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

Обработка информации в ЭВМ происходит путем последовательного выполнения элементарных операций. К ним относятся: установка, сдвиг, прием, преобразование, сложение и некоторые другие. Для выполнения каждой из этих операций сконструированы электронные узлы – регистры, счетчики, сумматоры, преобразователи кодов и т.д. Из этих узлов строятся интегральные микросхемы очень высокого уровня: микропроцессоры, модули ОЗУ, контроллеры внешних устройств и т.д. Сами указанные узлы собираются из основных базовых логических элементов – как простейших, реализующих логические функции И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и им подобных, так и более сложных, таких, как триггеры.

Логический элемент компьютера – это часть электронной логи-

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

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

Введем условные обозначения основных логических элементов

(рис. 13).

1

И	ИЛИ	НЕ	И-НЕ	исключающее
				ИЛИ

Рис. 13. Схемное обозначение основных логических элементов

56

Данные простейшие логические элементы можно реализовать аппаратно. Это означает, что можно создать электронные устройства на транзисторах, резисторах и т.д., каждое из которых имеет один или два входа для подачи управляющих напряжений и один выход, напряжение на котором определяется соответствующей таблицей истинности. На практике логическому «да» соответствует наличие напряжения, логическому «нет» – его отсутствие.

Вкачестве характерных устройств выберем два наиболее важных

иинтересных – триггер и сумматор. Триггер – это электронная схема, широко применяемая в регистрах компьютера для надёжного запоминания одного разряда двоичного кода. Сумматор – это электронная логическая схема, выполняющая суммирование двоичных чисел.

Простейший вариант триггера собирается из четырех логических элементов И-НЕ (рис. 14). Он имеет два входа R, S и два выхода –

прямой Q и инверсный Q . Термин триггер происходит от англий-

ского слова trigger – защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает «хлопанье» Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить («перебрасываться») из одного электрического состояния в другое, и наоборот.

Самый распространённый тип триггера – так называемый RSтриггер (S и R, соответственно, от английских set – установка и reset

– сброс).

D1

S

D3

&

&

&

&

R

D2

D4

Рис. 14. Логическая схема триггера

57

Проанализируем возможные комбинации значений входов R и S триггера, используя его схему и таблицу истинности схемы И-НЕ.

1.Пусть на входе R установлена 1, а на входе S – 0. Логические элементы D1 и D2 инвертируют эти сигналы. В результате, на вход элемента D3 поступает 1, а на D4 – 0. Поскольку на одном из выходов D4 уже есть 0, независимо от состояния другого входа на его выходе (он же – инверсный выход триггера) обязательно установится 1. Эта 1 передается на вход элемента D3 и в сочетании с 1 на другом входе порождает на выходе D3 логический 0. Итак, при R = 1 и S = 0 на прямом выходе триггера устанавливается 0, а а на инверсном – 1. Обозначение состояния триггера принято связывать с прямым выходом: говорят, что триггер «устанавливается в 0» или «сбрасывается». Отсюда и вход, появление сигнала на котором приводит к сбросу триггера, обозначают, R («reset»).

2.При аналогичных рассуждениях для симметричного случая

R = 0 и S = 1 можно убедиться, что триггер перейдет в единичное состояние – «установится» («set»).

3. Наиболее распространенная и интересная ситуация, когда

R = 0 и S = 0 – входные сигналы сняты. Состояние выхода будет полностью зависеть от состояния противоположных входов. Такое состояние будет устойчивым: 0 на одном из выходов будет поддерживать 1 на другом. Таким образом, при отсутствии входных сигналов триггер будет сохранять свое «предыдущее» состояние. Это свойство триггера и положено в основу хранения одного бита информации.

4. Последняя комбинация R = 1 и S = 1 приводит к тому, что на обоих выходах триггера установиться 1! Такое состояние логически недопустимо и крайне неустойчиво, поскольку снятие входных напряжений приведет к тому, что триггер случайным образом перейдет в одно из своих устойчивых состояний. Такая ситуация на практике является запрещенной. Ниже приведена таблица истинности триггера.

Поскольку один триггер может запомнить только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, для запоминания килобайта, соответственно, 8 · 210 = 8192 триггеров. Современные микросхемы памяти содержат миллионы триггеров. Пример таблицы истинности приведен в табл. 11.

Сумматор – это электронная логическая схема, выполняющая суммирование двоичных чисел.

58

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

Таблица 11

Таблица истинности RS-триггера

R	S	Q		Q
0	0	хранение
0	1	0		1
1	0	1		0
1	1	запрещено

Многоразрядный двоичный сумматор, предназначенный для сложения многоразрядных двоичных чисел, представляет собой комбинацию одноразрядных сумматоров. Начнем с изучения логической структуры простейшего возможного устройства, являющегося звеном сумматора – полусумматора, который реализует сложение двух одноразрядных двоичных чисел. В результате получается двухразрядное двоичное число. Его младшую цифру обозначим S, а старшую, которая при сложении многоразрядных чисел будет перенесена в старший разряд, через Co (от английских слов «сarry out» – «выходной перенос»).

Обе цифры можно получить по следующим логическим формулам:

S = (A & B) (A & B),Co = A & B

Составим для этих формул таблицу истинности (табл. 12).

Таблица 12

Таблица истинности для полусумматора

A	B	S	Co
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Таким образом, для реализации полусумматора достаточно соединить параллельно входы двух логических элементов, как это показано на рис. 15.

59