Учебное пособие

Учебное пособие -> Глава 6

Глава 6. Логические основы алгоритмизации

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

При записи тех или иных логических выражений используется специальный язык, который принят в математической логике. Начало исследований в области формальной логики было положено Аристотелем в IV в. до н.э. Однако математические подходы к этим вопросам были впервые указаны немецким математиком Готфридом Вильгельмом Лейбницем (1646 - 1716 гг.). Он сделал попытку построить универсальный язык, с помощью которого споры между людьми можно было бы разрешать посредством вычислений. На заложенном Лейбницем фундаменте ирландский математик Джордж Буль построил здание новой науки – математической логики, - которая в отличие от обычной алгебры оперирует не числами, а высказываниями. В честь Д.Буля логические переменные в языке программирования Паскаль впоследствии назвали булевскими.

Высказывание – это любое утверждение, относительно которого можно сказать истинно оно или ложно, т.е. соответствует оно действительности или нет. Таким образом, по своей сути высказывания фактически являются двоичными объектами, и поэтому часто истинному значению высказывания ставят в соответствие 1, а ложному – 0. Например, запись А = 1 означает, что высказывание А истинно.

Рассмотрим элементарные логические операции.

Конъюнкция – соединение двух (или нескольких) высказываний в одно с помощью союза И (AND) называется конъюнкцией (или операцией логического умножения). Обозначаются Λ, &,х.

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

А	В	A&B
0	0	0
0	1	0
1	0	0
1	1	1

Дизъюнкция – соединение двух (или нескольких) высказываний в одно с помощью союза ИЛИ (OR) называется дизъюнкцией (или логического сложения). Обозначаются ||, V, +. Таблица истинности представлена далее.

A	B	A V B	A xor B
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	0

Xor-модифицированная операция «ИЛИ» исключающее или (хor), от обычного «ИЛИ» отличается последней строкой.

Отрицание (инверсия) – присоединение частицы НЕ (NOT) к данному высказыванию называется операцией отрицания (инверсии). Ā, ¬ А – «не А». Таблица истинности представлена далее.

Логическая операция НЕ является унарной. т.е. имеет всего один операнд. В отличие от нее, операции И (AND) и ИЛИ (OR) являются бинарными, так как представляют собой результаты действий над двумя логическими величинами.

Эквивалентность – служит для задания высказываний «тогда и только тогда, когда ... » или « если и только если» ... Обозначаются А ~ В (А ≡ В, А eqv В).

A	B	A~B
T	T	T
T	F	F
F	T	F
F	F	T

Импликация – служит для задания так называемых условных высказываний «если…, то …» «когда ..., тогда ». Обозначаются А→ В, (А imp В).

A	B	A → B
T	T	T
T	F	F
F	F	T
F	T	T

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

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

Пример: определим истинность сложного высказывания ¬A & ¬B.

A	B	¬A	¬B	¬A & ¬B
0	0	1	1	1
0	1	1	0	0
1	0	0	1	0
1	1	0	0	0

Высказывания, у которых таблицы истинности совпадают, называются равносильными. Для обозначения используют знак “=”. Пример: рассмотрим сложное высказывание (A & B) V (¬A & ¬B) и составим таблицу истинности. Если сравнить с таблицей истинности, для эквивалентности, то видно, что высказывания равносильны.

2. Конъюнкция (логическое И) – логическое умножение.

3. Дизъюнкция (логическое или) – логическое сложение.

Схемная реализация базовых логических элементов

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

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

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

В основе каждой из элементарных операций лежит некоторая последовательность логических действий, описанных в предыдущем параграфе. Проанализируем, например, операцию сложения двух чисел: 3+6. Имеем: 011 + 110 = 1011.

На каждом элементарнейшем шаге этой деятельности двум двоичным цифрам сопоставляется двоичное число (одно- или двузначное) по правилам: (0,0) => О, (0,1) => 1, (1.0) => 1, (1,1) => 10. Таким образом, сложение цифр можно описать логической бинарной функцией. Если дополнить это логическим правилом переноса единицы в старший разряд (оно будет сформулировано ниже при описании работы сумматора), то сложение полностью сведется к цепочке логических операций.

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

Логические элементы (ЛЭ) – это электронные схемы с одним или несколькими входами и одним выходом, через которые проходят электрические сигналы, представляющие 0,1.

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

Рисунок 18 - Обозначения базовых логических элементов

Существуют микросхемы, реализующие более сложные логические функции: И-НЕ, называемая операцией Шеффера (ĀВ), и ИЛИ- НЕ, называемая Стрелка Пирса (А+В).

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

Базовые логические элементы, изображенные на рис. 18, можно реализовать аппаратно. Это означает, что можно создать электронные устройства на транзисторах, резисторах и т.п., каждое из которых имеет один или два входа для подачи управляющих напряжений и один выход, напряжение на котором определяется соответствующей таблицей истинности. На практике логическому “да” (“истина”, или цифра 1 в таблицах истинности) соответствует наличие напряжения, логическому “нет” (“ложь”, или цифра 0) – его отсутствие.

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

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

Регистр – совокупность триггеров, предназначенных для хранения числа в двоичном коде.

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

В качестве примера одной из наиболее характерных схем выберем и сумматор. Его назначение состоит в нахождении суммы двух двоичных чисел. Этот узел интересен для тем, что он лежит в основе арифметического устройства ЭВМ и иллюстрирует некоторые принципы выполнения вычислительных операций в компьютере. Для простоты изучим онаиболее важное звено сумматора – полусумматор. Полусумматор реализует сложение 2-х одноразрядных двоичных чисел А и В. В результате получается 2-х разрядное двоичное число. Его младшую цифру обозначим S, а старшую, которая при сложении многорязрядных чисел будет перенесена в старший разряд, через С₀.

Используя таблицы истинности и перебирая все четыре (00 01 10 00) возможные случая значений А и В, обе цифры (S и С₀) можно получить по следующим логическим формулам S= (¬A& В) V (А&¬В), С₀ = (А& В).

A	B	S	C₀
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

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

Рисунок 19 - Логическая схема полусумматора

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

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

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

При этом два переключателя Х и ¬Х связаны таким образом, что когда Х замкнут, то ¬Х разомкнут, и наоборот, Следовательно, если переключателю Х поставлена в соответствие логическая переменная х, то переключателю ¬Х должна соответствовать переменная ¬х.

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

Функции проводимости F некоторых переключательных схем:

1. Схема не содержит переключателей и проводит ток всегда, следовательно, F= 1;

2. Схема содержит один постоянно разомкнутый контакт, следовательно, F=0;

3. Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, F(х) = х;

4. Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут, следовательно, F(х)= х;

5. Схема проводит ток, когда оба переключателя замкнуты, следовательно, F(х)= х • у;

6. Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, F(х) = х v у.

Задачи, возникающие при рассмотрении переключательных схем, подразделяются на задачи анализа и задачи синтеза схем.

1. Составление функции проводимости по заданным условиям.

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

Совершенной дизъюнктивной нормальной формой (СДНФ) называют наиболее полную форму записи логического выражения. Эта форма записи представляет собой сумму, каждое слагаемое которой является произведением всех входных аргументов или их инверсий, например:

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

Еще одной формой записи логического выражения является совершенная конъюнктивная нормальная форма (СКНФ). Это произведение сомножителей, каждый из которых является суммой всех входных аргументов или их отрицаний, например:

Этапы синтеза переключательных схем с использованием СДНФ:

1. Образование СДНФ (СКНФ) функции по заданной таблице истинности.

2. Упрощение этой функции (преобразованию СДНФ (СКНФ) в формулу с наименьшим числом вхождений переменных).

Образование СДНФ функции по заданной таблице истинности включает в себя:

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

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

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

Для образования конституэнты единицы С¹_i, принимающей единичное значение в i-ом наборе значений аргументов необходимо составить логическое произведение аргументов, в которое аргументы, принимающие в i-м наборе единичное значение, входят без знака отрицания, а аргументы, принимающие в i –м наборе новое значение, входят со знаком отрицания.

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

2. Для каждого выделенного набора образуется конституэнта поля, принимавшая нулевое значение при данном наборе значений аргументов;

3. Составляется логическое произведение образованных конституэнт ноля.

При преобразовании СДНФ (СКНФ) в формулу с наименьшим числом вхождений переменных (минимизация формулы) используют аксиомы и законы булевой алгебры:

- минимизация с использованием карт Карно или диаграмм Вейча.

При минимизации по методу Квайна предполагается, что исходная функция задана в СДНФ.

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

В качестве примера логического синтеза вычислительных схем рассмотрим построение одноразрядного двоичного сумматора, имеющего два входа (х₁ и х₂) и два выхода (S и P).

х1	0	1	1
х2	1	0	1
S=f1(x1,x2)	1	1	0
P=f2(x1,x2)	0	0	1

Представим выходные функции S и P в виде СДНФ:

Рисунок 21 – Логическая схема полусумматора

Для логических схем (И, ИЛИ, НЕ) существуют типовые технические схемы (логические элементы), реализующие их на полупроводниковых структурах, т.е. аппаратно.

Использование знаков 0 и 1 подчеркивает некоторое соответствие между значениями логических переменных и функций в математической логике и цифрами в двоичной системе счисления.

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

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

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

Рисунок 22 – Упрощенная логическая схема полусумматора

(A & B)

(¬A & ¬B)

(A & B) V (¬A & ¬B)