Элементы математической логики, ее символы

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

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

     4.1 Математическая логика в технике.

     Роль  логической обработки бинарных данных на современном этапе развития вычислительной техники существенно возросла. Это  связано, в первую очередь, с созданием  технически систем. реализующих в том или ином виде технологии  получения и  накопления знаний, моделированием отдельных  интеллектуальных функций человека. Ядром таких систем являются мощные ЭВМ и вычислительные комплексы.  Кроме того, существует  большой класс прикладных задач, которые можно свести к решению логических задач, например, обработка и синтез изображений, транспортные задачи. Требуемая производительность вычислительных средств достигается путем распараллеливания и конвейеризации вычислительных процессов. Это реализуется, как правило, на основе сверхбольших интегральных, схем (СБИС). Однако технология СБИС и их структура предъявляет ряд специфических  требований к алгоритмам, а именно: регулярность, параллельно - поточная организация вычислений, сверхлинейная операционная сложность (многократное использование каждого элемента входных данных), локальность связей вычислений, двумерность  пространства реализации вычислений. Эти требования обусловливают необходимость решения проблемы эффективного  “погружения” алгоритма в вычислительную среду, или, как еще принято говорить, - отображение алгоритма в архитектуру вычислительных средств. В настоящее время доказана ошибочность ранее широко распространенных взглядов, состоящих в том, что переход на параллельно -конвейерные  архитектуры ЭВМ потребуют лишь небольшой модификации  известных алгоритмов. Оказалось, что параллелилизм и конвейеризация вычислительных процессов требует разработки новых алгоритмов даже для тех задач, для которых существовали хорошо изученные и апробированные методы и алгоритмы решения, но ориентированные на последовательный принцип реализации. По прогнозам специалистов, в ближайшее десятилетие следует ожидать появления новых концепций построения вычислительных средств. Основанием для прогнозов являются результаты проводимых в настоящее время перспективных исследований, в частности, в области биочипов и органических  переключающих элементов. Некоторые направления ставят своей целью  создание схем в виде слоев органических молекул и пленок с высокоразвитой структурой.  Это позволит, по  мнению исследователей, “выращивать”   компьютеры на основе генной инженерии  и усилить аналогию между элементами  технических систем  и клетками мозга. Тем самым реальные очертания приобретают нейрокомпьютеры, которые имитируют  интеллектуальные функции биологических объектов, в том  числе человека. По-видимому,  молекулярная электроника станет основой для создания ЭВМ шестого поколения. Все это объективно обусловливает  интенсивные работы по  методам синтезов алгоритмов обработки логических данных и их эффективному  погружению в операционную  среду бинарных элементов. Очевидно, что бинарные элементы и бинарные данные наиболее полно соответствуют друг другу в плане представления  и обработки  последних на таких элементах, если рассматривать их по отдельности. Действительно, положим, алгебра логики над числами  (0,1) реализуется на бинарном  элементе полном использовании его операционного ресурса. Другими словами, ставится вопрос об эффективности, а иногда вообще возможности реализации данного алгоритма на такой сети (структуре). В этом состоит суть погружения алгоритма в структуру.

     4.2 Математическая логика в криптографии.

       Криптография  изучает методы пересылки сообщений  в замаскированном виде, при которых  только намеченные отправителем получатели могут удалить маскировку и прочитать сообщение. Общая схема защиты информации представлена на рисунке 2. Этап кодирования от ошибок основан на  внесении в передаваемое сообщение избытка информации, достаточного для преодоления помех на линии связи. Например, допустим, передается последовательность символов типа “0” и “1”. При этом в сети связи с некоторой вероятностью могут происходить ошибки приема сигнала “0 “ вместо сигнала “1” или наоборот, тогда кодер на каждый символ ai сообщения передает пятью импульсами  00000, если ai -0 и наоборот. На приемном конце принимаемая последовательность импульсов разбивается по пять импульсов, называемая блоками. Если в принятом блоке содержится 2 и менее импульса 0, то принимается решение о том, что передавался символ ai-1. Таким образом, исходная вероятность ошибки будет значительно снижена. Более элегантные методы кодирования, которые при достаточной надежности позволяют вносить не такой большой избыток информации. Для выражения в информации требуется ввести некоторый алфавит, из которого будет состоять сообщение (конечные упорядоченные множества из этих символов). Обозначим через A – мощность  выбранного алфавита. Будем также считать, что все множества информации или , что то же самое, множество всевозможных сообщений конечно. В качестве меры информации в сообщении данной длины можно взять Log2 от числа всевозможных сообщений конечно. Тогда объем информации, падающий на один символ алфавита X=log2a. Далее имеем дело со словами длинной S, тогда всего таких слов будет N=AS (декартова S- степень алфавита), а следовательно, количество информации в слове Y=Log2N=Log2As=SX.  
Львиную долю криптоанализа составляют методы, построенные на вероятностном анализе криптограммы и предлагаемого исходного языка. Поскольку всякий обычный язык имеет избыток информации, причем неравномерно размешенных в словах , то буквы алфавита этого языка могут иметь устойчивые частные характеристики. Например, в английском языке – это часто повторяющая буква “e”, кроме того, частотными  характеристиками могут быть буквосочетания и их комбинации.  
 Общая схема криптосистемы с секретным ключом изображена на рисунке 3. Здесь Х – открытый текст,  Y- шифр  текста, K – ключ шифра, R – рандомизирующая последовательность.

     4.3 Математическая логика в программировании.

     Функция одного аргумента - это правило, ставящее  соответствие любому значению, лежащему в области изменения этого аргумента (которая будет и областью определения этой функции), другую величину, лежащую в области значений функции. 

     Понятие функции было перенесено в языки  программирования. В языке программирования, как правило, предусмотрен ряд встроенных функций, например sin, cos, sqrt и т.д. Кроме  того, программист имеет возможность  определять свои собственные функции. Они могут работать не только с вещественными числами, но и с различными типами данных, включающими обычно integer (целое), real (вещественное), boolean (булевское), character (строковое). Они могут также работать со структурами. В языках Паскаль, Алгол=68 и ПЛ/1 имеются, например, типы records (записи), arrays (массивы), lists (списки), files of records (файлы,  состоящие из записей), а значениями функций могут быть указатели этих структур. Все это согласовано с понятием области определения, вне которой функция не определена. В языках программирования эта область задана обычно указанием типа данных, который является некоторым множеством величин. Так, в Паскале компилятор должен следить за тем, чтобы никакая функция не применялась к величине неподходящего типа, которая  могла  бы  выйти  за  пределы  области  определения функции.

       Функция многих аргументов. Теперь нужно обобщить определение, чтобы охватить функции  многих аргументов. Для этого соберем n аргументов в упорядоченный набор, который будем рассматривать как один аргумент. Возьмем функцию вычитания diff(x.y). Трактуется ее как отображение пар <х,у> в целые числа. В виде множества упорядоченных пар ее можно записать следующим образом: 
diff = {«5,3>, 2>. «6,3>, 3>, «4,5>, -1>...} 
              Если бы вместо этого у нас была функция четырех аргументов h(x,y,z,w), то использовали бы отображение, определенное на четверках <x,y,z,w>. Этот прием используется и в программировании. Если необходимо уменьшить количество аргументов процедуры или функции (причем все они имеют один и тот же тип), то в Фортране можно записать эти значения в массив и передать в качестве параметра этот массив, а не отдельные значения. В более общем случае (например, в Паскале), когда аргументам разрешается иметь различные типы, можно передать в качестве параметра запись и хранить значения в виде отдельных компонент этой записи. В действительности набор, состоящий из n элементов в математике соответствует записи в программировании. Каждая из ее компонент берется из своей отдельной области, как и в случае записи. Единственное отличие состоит в том, что компонента определяется своим расположением (позицией), а не именем. Реляционная модель данных работает с множествами упорядоченных наборов, которые соответствуют файлам записей, хранящимся в машине. Также математическая логика используется и в других областях информатики – это в разработке в области моделирования и автоматизации интеллектуальных процедур – направление так называемого искусственного интеллекта.

5. Список литературы

1. Дж. Кемени, Дж. Снелл, Дж. Томпсон. Введение в конечную математику: Пер. с англ. М.: Мир, 1963. 
2. Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. М.: Издательство Московского университета, 1982. 
3. Марков А. А.. Элементы математической логики. М.: Изд-во МГУ, 1984.

4. Создатель формальной логики // Информатика, № 41/2000. 
5. Соколов Е.А. Интегральные схемы логических операций // Новое в жизни, науке, технике. Сер. “Вычислительная техника и ее применение”. Аппаратный состав ЭВМ, № 5/88. 
6. Стяжкин Н. И. Формирование математической логики. М.: Наука, 1967. 508 с.

7. Шенфилд Дж. Математическая логика. М.: Наука, 1975.