Математическая логика

 

Содержание

Введение……………………………………………………………..…..3

1 Математическая логика………………………………………….……4

1.1 Применение математической логики  в информатике…………….4

1.2  Применение математической  логики…………………………….10

2 Графы…………………………………………………………….……15

2.1 Алгоритм Дейкстра………………………………………………...15

2.2 Жадный алгоритм………………………………………………….16

2.3 Построение минимального остова………………………………..17

2.4 Задача Коммивояжера……………………………………………..19

Заключение …………………………………………………………….22

Список использованных источников ………………………………...23

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Математическая логика

1.1 Применение математической логики в информатике

Информатика – это наука, которая изучает компьютер, а также взаимодействие компьютера с человеком.

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

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

Идея логических машин появилась в 13 веке у испанского схоластика Раймунда Луллия, рассматривалась затем Лейбницем и получило новое развитие в 19 веке, после возникновения математической логики. В 1870 году английский философ и экономист Вильям Стэнли Джевонс построил в Манчестере “логическое пианино”, которое извлекало из алгебраически записанных посылок следствия, выделяя допустимые комбинации терминов. Это называют также разложением высказываний на конституанты. Важно отметить возможность практического применения логической машины для решения сложных логических задач.

Современные универсальные вычислительные машины являются вместе с тем логическими машинами. Именно введение логических операций сделало их такими гибкими; оно же позволяет им моделировать рассуждения. Таким образом, арифметическая ветвь “разумных автоматов” соединились с логической. В 20-е годы, однако, формальная логика представлялась слишком абстрактной о метафизической для приложения к жизни. Между тем уже тогда можно было предвидеть внедрение логических исчислений в технику.

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

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

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

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

 

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

Криптография изучает методы пересылки сообщений в замаскированном виде, при которых только намеченные отправителем получатели могут удалить маскировку и прочитать сообщение. Общая схема защиты информации представлена на рисунке 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 – рандомизирующая последовательность.

 

 

 

 

 

 

 

 

 

Рисунок 1 – Общая схема криптосистемы

 Теперь рассмотрим несколько наиболее популярных методов шифрования криптосистем с секретным ключом.

Метод перестановки. В общем, виде это метод описывается так: текст разбивается на равные группы по d – символов, и в группах осуществляется одна и та же перестановка символов. Очевидно, что всевозможных ключей будет d!. Перестановку осуществляемую таким образом, иногда называют транспозицией с периодом d.

Пример 1. Пусть исходный текст имеет следующий набор символов x=x1,x2 ..  Пусть d=5 и k=(23154), тогда x=x1x2x3x4x5| x6x7x8x9x10; y=x2x3x3x5x4|x7x6x8x10x9…

Примером такой же простой перестановки является шифр получивший название маршрут Гальмитона.  

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

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

Понятие функции было перенесено в языки программирования. В языке программирования, как правило, предусмотрен ряд встроенных функций, например 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 элементов в математике соответствует записи в программировании. Каждая из ее компонент берется из своей отдельной области, как и в случае записи. Единственное отличие состоит в том, что компонента определяется своим расположением (позицией), а не именем. Реляционная модель данных работает с множествами упорядоченных наборов, которые соответствуют файлам записей, хранящимся в машине. Также математическая логика используется и в других областях информатики – это в разработке в области моделирования и автоматизации интеллектуальных процедур – направление так называемого искусственного интеллекта.

1.2  Применение математической логики

Рассмотрим применение математической логики на примере данной функции:

(1)

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

Построение таблицы истинности.

Всякая логическая функция n переменных может быть задана таблицей, в левой части которой перечислены все 2n наборов значений переменных (то есть всевозможных наборов двоичных векторов длины n), а в правой части приведены значения функции на этих наборах. Функцию (1) можно представлять  через таблицу  истинности, причем все операции над переменными x и y , а именно – это конъюнкция, дизъюнкция, прямая сумма, импликация  можно заменить готовыми значениями булевой функции./2/ Пример преобразования функции к числам 0 и 1 представлен в таблице 1.

  Таблица 1- Таблица истинности  для функции (1)

x	y
0	0	1	1	1	0	1	0	0
0	1	0	0	0	1	1	0	0
1	0	1	0	0	1	1	0	0
1	1	0	0	1	1	0	1	1