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

Размещено на http://www.allbest.ru/

Содержание

Введение

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

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

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

2. Графы

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

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

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

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

Заключение

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



Введение

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



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 - рандомизирующая последовательность.

Размещено на http://www.allbest.ru/

Рисунок 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

Конъюнктивная и дизъюнктивная нормальные формы (КНФ и ДНФ)

Дизъюнктивной нормальной формой называется формула, имеющая вид дизъюнкции элементарных конъюнкций.

Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций./2/

f(e1,e2,…,en)= x1e1x2e2…xnen (2)

Для приведения функции от двух переменных f(x,y) к ДНФ следует воспользоваться формулой 2 и таблицей 1.

Каждая булева функция f(x1,x2,…,xn), которая не идентична нулю, может быть записана в виде всевозможных булевых выражений типа

f(x,y)=( (3)

Каждую булеву функцию f(x1,x2,…,xn), которая не равна тождественно единице, можно представить в виде произведения всевозможных булевых выражений вида:

f(e1,e2,…,e3) = x1e1 x2e2 … xnen (4)

Для приведения функции от двух переменных f(x,y) к КНФ следует воспользоваться теоремой 2 и таблицей 1.Следовательно ДНФ=x&y.

Построение полинома Жегалкина.

Полином Жегалкина определяется по формуле:

,

где ki () попарно различные монотонные элементарные конъюнкции./2/

Для функции , которая зависит от трех переменных, полином Жегалкина будет следующий:

P(x, y) = B0B1xB2yB3xy (3)

Метод неопределенных коэффициентов заключается в том, что последовательной подстановкой x, y и соответственно значений функций при них в данный полином, находим коэффициенты в0, в1, в2, в3, в4, в5, в6, в7. Значения переменных x, y и значение функции представлены в таблице 4:

Таблица 2 - значение функции

x	Y	f (x, y)
0	0	0
0	1	0
1	0	0
1	1	1

На основании таблицы 2 составляем систему уравнений и находим последовательно коэффициенты:

f(00)=B0=0

f(01)=B0B2=0; B2=0

f(10)=B0B1=0; B1=0

f(11)=B0B1B2B3=1; B3=1

следовательно, получили полином Жегалкина:

P(x,y)=x*y (5)



Нахождение производной от двух переменных. Находим две производных.

и ;

(5)

(6)

Используя формулу 6 можно построить таблицу истинности (таблица 6) для функции (6), а также таблицу (таблица7) значений производной (5)

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

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

Таблица 4 - Значение производной (5)

f(x,y)	f(	f(x,y)
0	0	0
0	1	1
0	0	0
1	0	1

Найдем производную по x,y

- (6)

- (7)

Для нахождения дифференциала функции (1) сначала построим таблицу истинности для функции (7) (таблица 8) и окончательным результатом будет таблица 9 для функции 6.

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

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

Таблица 6 - Значение производной

f(x,y)	f(	f(x,y) f(
0	1	1
0	0	0
0	0	0
1	0	1



2. Графы

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

Рассмотрим экономическую задачу: одна крупная компания решила поощрить своих работников и устроить всем работникам отдых в городе С. Для того чтобы приехать в город С необходимо проехать несколько промежуточных городов. Перед экспертами компании была поставлена задача найти оптимальный путь. Они определили расстояния между городами и построили неориентированный граф.

Если задачу перевести на язык математики, то получится, имеется n вершин и число ребер не меньше n-1. Если две вершины соединены, то они соединены только одним ребром.

Размещено на http://www.allbest.ru/

Рисунок 2 - Исходный граф

Вершине A присваиваем постоянный ярлык 0. Далее приписываем вершинам смежные к A (B и I) временные ярлыки. Bременный ярлык вершины B равен 5; временный ярлык вершины I равен 4. Выбираем наименьший - это будет I, и делаем его постоянным. На рисунке он выделяется жирным шрифтом.



Размещено на http://www.allbest.ru/

Рисунок 3 - Нахождения первого присоединенного ребра

L(w)=4 далее назначаем временные ярлыки H и F и они соответственно будут равны 11 и 10, выбираем минимальный - это будет F, выделяем его и делаем его постоянным и так далее, пока не дойдем до G .

Размещено на http://www.allbest.ru/

Рисунок 4-Резулитирующий граф

В результате получается, что кратчайший путь будет равен 13 и будет пролегать через A, I, F, G.

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

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

Решить - эту задачу можно с помощью Жадного алгоритма.

Решением задачи будет следующий алгоритм. /6/

a. находится ребро с максимальным весом, из него составляется подграф. Ясно, что таковым является ребро с весом равным 14, соединяющее вершины D и E.

б. дальнейшим шагом находится следующее ребро с максимальным весом. Это ребро, соединяющее E и F (с весом 13)

в. присоединяется ребро, связывающее E и C (с весом 12)

г. присоединяется ребро, связывающее E и G (с весом 11)

д. присоединяется ребро, связывающее I и H (с весом 8)

е. присоединяется ребро, связывающее I и F (с весом 8)

ж. присоединяется ребро, связывающее A и B (с весом 6)

В результате получаем граф, изображенный на рисунке 5, который и будет примером применения жадного алгоритма.

Размещено на http://www.allbest.ru/

Рисунок 5 - Максимальное дерево покрытия

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

Вес = 10+7+8+6+6+7=44

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

В одном большом городе имеется один большой супермаркет (F) и существует множество дорог к нему. Известны затраты на проезд . Требуется найти путь с минимальными затратами.

Для решение этой задачи можно применить алгоритм минимального остова./6/

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

Десять городов поставим в соответствие десяти вершинам графа a, b, c, d, e, f, g, h, i, j,. Цель обозначим F, а начало пути обозначим A.

Решением задачи будет следующая последовательность этапов:

1 этап (H-J), 2 этап: (I-g) , 3 этап: (h-i), 4 этап: (I-f), 5 этап: (g-d), 6 этап: (d-b), 7 этап:(b-a), 8 этап: (b-e). Выполнение алгоритма завешено, так как добавление ребер без образования петель невозможно. Осталось сложить веса ребер, составляющих подграф графа G, который образует минимальный остов. Эта сумма будет следующая: 2+7+4+6+5+7+6+6+4=47. В результате получаем, что существует один путь к F - это AIF и он равен = 10. Построив граф (рисунок 6), можно увидеть, что существует только единственный путь от начала нашего пути до указанной цели.



Размещено на http://www.allbest.ru/

Рисунок 6 -Результирующий граф

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

Предприятия(A) в целях увеличить свою прибыль решила открыть свои филиалы в 10 городах (B,C,D,E,F,G,I,H,J) и, чтобы минимизировать затраты и сэкономить время экономистам была поставлена задача найти минимальный путь и так чтобы все города были пройдены по одному разу.

Так как этот граф является Гальмитонов, то одним из способов решения будет решение при помощи Коммивояжера./6/

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



Подсчитываем Kпр=1+1+1+1+1+1=6.

б) Для каждого нулевого элемента определяются коэффициенты Кi,j по формуле 2.

(4)

К15=3; К26=3; К34=2; К43=2; К51=3; К62=3; К15=3

Выбираем наибольший из коэффициентов (К1,5=3). Следовательно, в наш гамильтонов граф будет включено ребро, соединяющее 1 и 5 вершины с весом 13. Далее вычеркиваем строку и столбец, соответствующие индексу

Повторяем шаг под буквой а и получаем:

Kпр=6+3 =9.

Далее повторяем шаг б:

К21=1; K26=2; K34=2; K43=1; K53=0; K54=0; K62=3.

Следующим ребром, которое будет включено в граф - это K62=3

Повторяем шага



Получаем Kпр=11

Повторяем шаг б:

K21=2; K34=0; K36=3; K43=3; K53=0; K54=0

Получаем, что будет включено ребро K36=3

Добавляем к графу ребро K21=2

В ходе решения задачи были выделены элементы матрицы:

К1,5 , К6,2, К3,6 , К2,1 , К5,4 ,К4,3, которым соответствуют ребра (1-5), (6-2), (3-6), (2-1), (5-4), (4-3) с весами 3, 3, 3, 2.

Длина маршрута равна 11, что совпадает с суммой всех коэффициентов приведения: 6 + 3 + 2 = 11. Построим граф (рисунок 8) и, если все вершины соединились, следовательно, задача было решена правильно.



Размещено на http://www.allbest.ru/

Рисунок 8- Результирующий граф



Заключение

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



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

1. Воротников А.П., Практикум по введению в математическую логику.- СПб., 1986 - 300с.

2. Новиков Ф.А., Дискретная математика для программистов. - СПб., 2002 - 302с.

3. Новиков Ф.А., Введение в крипторафию. - СПб, 1993 - 190 с.

4. Логинов Б.М., Лекции по дискретной математике. - Калуга, 1993 - 140с.

5. Яблонский С.В., Введение в дискретную математику .-M.: Наука, 1996 - 200с.

6. Методические указания по дискретной математике - 30с.

Размещено на Allbest.ru

...