Логические основы кодирования операций

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

Логические операции были разработаны выдающимся английским ученым первой половины 19-го века Джорджем Булем. Он создал математический аппарат алгебры логики, получивший в его честь второе название - булевой алгебры.

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

Высказывание – это любое утверждение, которое можно оценить как истинное - 1, или ложное - 0. При этом считается, что высказывание удовлетворяет закону исключённого третьего, т.е. каждое высказывание или истинно, или ложно и не может быть одновременно и истинным, и ложным. Например, высказывания: "Сейчас идёт снег" - это утверждение может быть истинным или ложным; "Москва – столица России" - истинное утверждение; "Частное от деления 10 на 2 равно 3" - ложное утверждение.

В булевой алгебре высказывания играют роль данных, их обозначают буквами. Например, a, b, c. Над высказываниями выполняются операции. Простейшими операциями являются логическое сложение, логическое умножение и операция отрицания. Их ещё называют соответственно: дизъюнкция, конъюнкция и инверсия. Для обозначения операции логического сложения используют символы + или Ú, логического умножения – символы *, & или Ù, инверсия – обозначается чертой над элементом или символом Ø перед элементом. Выбор для использования одного из нескольких знаков, обозначающих одну и ту же операцию, определяется только соображениями наглядности.

Результаты выполнения операций определены в следующей таблице:

А	В	А*ВА&ВАÙВ	АÚВ А+В	А ØА	В ØВ

Переменные в булевой алгебре могут принимать только два значения - 0 и 1. Функция в булевой алгебре – это алгебраическое выражение, содержащее переменные булевой алгебры, связанные между собой и с другими элементами выражения операциями булевой алгебры. Например,

f(x1,x2,x3) = (x1 & x2 Ú Ø(x2 Ú x3)) & x1 Ú Øx3.

Если положить x1=0, x2=1, x3=1, то f(0,1,1)= (0 Ù 1 Ú Ø(1 Ú 1)) Ù 1 Ú Ø1=0.

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

Особое практическое значение в информатике имеют высказывания в виде математических выражений, содержащих математические операции сравнения данных. Используются следующие знаки операций сравнения: < (меньше), <= (меньше или равно), = (равно), |= (не равно), > (больше), >= (больше или равно). Результатом выполнения операции сравнения являются 0 (ложь) или 1 (истина). Примером подобных высказываний может служить выражение вида (X>6), которое, например, при присвоении X значения 2, принимает значение 0 (ложь), а при присвоении X значения 8 - принимает значение 1 (истина).

Высказывания в виде логических функций применяются при составлении алгоритмов в структурах "Развилка" и "Повторение".

Доказано, что любые операции над двоичными данными могут быть представлены (синтезированы) как вычисление функций булевой алгебры. Не вдаваясь в подробности данной проблемы (она не тривиальна), рассмотрим в качестве примера представление операции сложения одноразрядных двоичных чисел b+d в виде вычисления двух логических функций - S(b,d)=bÙ(Ød)Ú(Øb)Ùd и P(b,d)=bÙd. Функция S(b,d) дает результат сложения одноразрядных двоичных чисел, а P(b,d) - значение цифры переноса в следующий разряд. Пусть b=1, d=0, тогда S(b,d)=1, а P(b,d)=0. Следовательно, 1+0=1 и переноса в соседний разряд нет. Легко проверить правильность полученного результата и при других сочетаниях значений b и d. Используя теперь N пар подобных функций, можно синтезировать операцию сложения N-разрядных двоичных чисел. Если учесть, что операции умножения и деления основаны на операции сложения положительных и отрицательных чисел, то подобным же способом можно синтезировать и эти операции. Таким образом, любые операции могут быть представлены (синтезированы, закодированы) как вычисление ограниченного набора логических функций, машинная реализация которых не вызывает принципиальных трудностей.

Контрольные вопросы

1. Чем обусловлена необходимость кодирования информации?

2. Что понимается под системой кодирования информации?

3. Почему позиционная система счисления рассматривается в информатике как универсальная система кодирования информации?

4. Принцип и алгоритм построения кода в позиционной системе счисления.

5. Почему в информатике применяются системы счисления с основаниями 2, 8 и 16?

6. Как преобразовать число из двоичной системы счисления в 8-ричную или 16-ричную?

7. Как преобразовать число из 8-ричной или 16-ричной систем счисления в двоичную?

8. Как преобразовать число из 8-ричной системы счисления в 16-ричную?

9. Как преобразовать число из произвольной системы счисления в десятичную?

10. Как преобразовать число из десятичной системы счисления в произвольно заданную систему счисления?

11. Как преобразовать число из одной произвольно заданной системы счисления в другую произвольно заданную систему счисления?

12. Принцип построения кода в двоично-десятичной системе кодирования.

13. Принцип кодирования информации, представленной в виде текста.

14. Принцип кодирования изображений и звука.

15. Какие действия называют логическими операциями? Перечислите и охарактеризуйте изученные логические операции.

16. Что представляет собой логическая функция в булевой алгебре?

17. Почему булева алгебра рассматривается как система кодирования любых действий (операций)?