Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Закон'
В соответствии с Конституцией Российской Федерации и международными актами о правах человека каждый гражданин Российской Федерации имеет право на сво...полностью>>
'Документ'
По итогам последних двух недель января котировки российских акций заметно снизились. На фоне недостатка свободных рублей и неблагоприятных внешнеэконо...полностью>>
'Документ'
До настоящего времени применение диагноза биполярного аффективного расстройства (БАР) белорусскими психиатрами остается редкостью [21]. Анализ диагно...полностью>>
'Доклад'
Формирование эффективной системы местного управления и самоуправления – одна из важнейших задач развития государственности в Республике Беларусь. Мес...полностью>>

Решение (1)

Главная > Решение
Сохрани ссылку в одной из сетей:

Содержание

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

  1. Общая часть………………………………………………………………………………………………. 4

    1. Множества и операции над ними…………………………………………………………………… 4

    2. Булева функция………………………………………………………………………………………………………. 5

    3. Математическая логика…………………………………………………………………………………….. 6

    4. Логика высказываний…………………………………………………………………………………………… 7

    5. Графы……………………………………………………………………………………………………………………………. 8

  2. Задачи………………………………………………………………………………………………………………. 12

  3. Решение............................................................................................................. 14

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

Литература……………………………………………………………………………………………………………………………

Введение

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

В курсе изучаются фундаментальные понятия, лежащие в основе математической кибернетики и таких разделов математики как алгебра, теория графов, математическая логика. Хотя данные разделы и являются отдельными математическими теориями, они не только используют методы друг друга, но и тесно связаны между собой. Все их можно объединить условным названием ``дискретная математика''. Этот термин характеризует конструктивный характер теории, алгоритмические, комбинаторные методы. Задачи дискретной математики, как правило, тесно связаны с компьютерными проблемами, естественно выражаются в виде различных алгоритмов.

Историческая справка

Дискретная математика, по-существу, стала активно развиваться с начала XX века, когда стали изучаться возможности формализации математики и были получены фундаментальные результаты в области математической логики. Это результаты Поста, Клини и, особенно, Гёделя. Теорема неполноты Гёделя имеет мировоззренческое значение – она показывает ограниченность формальных методов построения математической теории.

В основе дискретной математики 4 раздела:

  1. Язык дискретной математики;

  2. Логические функции и автоматы;

  3. Теория алгоритмов;

  4. Графы и дискретные экстремальные задачи.

Одной из важнейших проблем в дискретной математики является проблема сложности вычислений.

Теория сложности вычислений помогает оценить расход времени и памяти при решении задач на ЭВМ. Теория сложности позволяет выделить объективно сложные задачи (задачи перебора) и неразрешимые задачи.

  1. Общая часть

    1. Множества и операции над ними

Одно из основных понятий математики – множество.

Определение:

Множеством называется совокупность, набор предметов, объектов или элементов.

Множество обозначают: M,N …..

m1, m2, mn – элементы множества.

Символика

A  M – принадлежность элемента к множеству;

А  М – непринадлежность элемента к множеству.

Примеры числовых множеств:

1,2,3,… множество натуральных чисел N;

…,-2,-1,0,1,2,… - множество целых чисел Z.

множество рациональных чисел а.

I – множество иррациональных чисел.

R – множество действительных чисел.

K – множество комплексных чисел.

Множество А называется подмножеством В, если всякий элемент А является элементом В.

А  В – А подмножество В (нестрогое включение)

Множества А и В равны, если их элементы совпадают.

A = B

Если А  В и А  В то А  В (строгое включение).

Множества бывают конечные и бесконечные.

|М| - мощность множества (число его элементов).

Конечное множество имеет конечное количество элементов.

Пустое множество не содержит элементов: M = .

Существует 5 операций над множествами:

  1. объединение (сумма) множеств А и В представляет собой множества состоящие из элементов, принадлежащих хотя бы одному из множеств А и В. Если какой-нибудь элемент входит в оба множества, то в объединении этих множеств он включается только 1 раз

  2. пересечение (умножение) множеств А и В – это множество, которое состоит из элементов принадлежащих каждому из множеств.

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

  4. симметрическая разность множеств А и В представляет собой множество, состоящее из элементов, принадлежащих в точности одному из множеств А и в.

  5. дополнения. Если А Е, то дополнения (); относительно Е определяется так: т.е. это множество трех элементов, которые не принадлежат множеству А, а принадлежат множеству С.

1.2 Булева функция

Понятие булевой функции

Определение (Булева функция). Булевой функцией от n аргументов называется функция f из n-ой степени множества { 0, 1 } в множество { 0, 1 }. Иначе говоря, булева функция – это функция, и аргументы и значение

которой принадлежит множеству { 0, 1 }. Множество { 0, 1 } мы будем в дальнейшем обозначать через B. Булеву функцию от n аргументов можно рассматривать как n-местную алгебраическую операцию на множестве B. При этом алгебра <B;>, где  – множество всевозможных булевых функций называется алгеброй логики.

Определение (Фиктивные и существенные переменные). Переменная xi называется фиктивной (несущественной) переменной функции f(x1,···,xn), если

f(x1,···,xi-1,0,xi+1,···,xn) = f(x1,···,xi-1,1,xi+1,···,xn)

для любых значений x1,···,xi-1,xi+1,···,xn. Иначе переменная xi называется существенной. Функций от двух аргументов шестнадцать. Наиболее употребимые из этих функций только те, которые существенно зависят от обеих переменных.Эти функции записываются как бинарные операции в инфиксной нотации. x1 & x2 называется конъюнкцией, x1  x2 – дизъюнкцией, x1  x2 – импликацией, x1  x2 – эквивалентностью, x1  x2 – суммой по модулю 2, x1 | x2 – штрихом Шеффера. Значения 0 и 1 часто интерпретируют как ``ложь'' и ``истину''. Тогда понятным становится название функции ``отрицание'' – она меняет ``ложь'' на ``истину'', а ``истину'' на ``ложь''. Отрицание читается как ``не''. Конъюнкция читается обычно как ``и'' – действительно, конъюнкция равна 1 тогда и только тогда, когда равны 1 и первая и вторая переменная.* Кроме x1& x2 часто используют обозначение x1  x2 или x1 · x2 или x1x2 или min(x1,x2). Дизъюнкция читается ``или'' – дизъюнкция равна 1 тогда и только тогда, когда равны 1 первая или вторая переменная.* Импликация выражает факт, что из x1 следует x2.* Импликацию часто также обозначают x1  x2.

Суперпозиция функций

Определение (Суперпозиция функций). Суперпозицией булевых функций f0 и f1,...,fn называется функция f(x1,...,xm) = f0(g1(x1,...,xm),...,gk(x1,...,xm)), где каждая из функций gi(x1, ...,xm) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f1,...,fn.

3 Двойственные функции

Симметрия элементов 0 и 1 в множестве B приводит к понятию двойственности.

Определение (Двойственная функция). Функция g(x1,...,xn) = ¬f(¬x1,...,¬xn) называется двойственной функцией к функции f и обозначается f*

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

Основная идея математической логики – формализация знаний и рассуждений. Известно, что наиболее легко формализуемые знания – математические. Таким образом, математическая логика, по-существу, – наука о математике, или метаматематика. Центральным понятием математической логики является ``математическое доказательство''. Действительно, ``доказательные'' (иначе говоря, дедуктивные) рассуждения

– единственный вид признаваемых в математике рассуждений. Рассуждения в математической логике изучаются с точки зрения формы, а не смысла. По-существу, рассуждения моделируются чисто ``механическим'' процессом переписывания текста ( формул). Такой процесс называют выводом. Говорят

еще, что математическая логика оперирует только синтаксическими понятиями. Однако обычно всё же важно, как соотносятся рассуждения с действительностью (или нашими представлениями). Поэтому, надо всё же иметь в виду некоторый смысл формул и вывода. При этом используют термин семантика (синоном слова ``смысл'') и чётко разделяют синтаксис и семантику. Когда же действительно интересуются только синтаксисом, часто используют термин ``формальная система''. Мы будем использовать синоним этого термина – ``исчисление'' (используются ещё термины ``формальная теория'' и ``аксиоматика''). Объектом формальных систем являются строки текста (последовательности символов), с помощью которых записываются формулы.

Формальная система определена, если:

  1. Задан алфавит (множество символов, используемых для построения формул).

  2. Определено, какие именно строки считать формулами (остальные строки считаются просто бессмысленными).

  3. Выделено множество формул, называемых аксиомами. Это – стартовые точки в выводах.

  4. Задано множество правил вывода, которые позволяют из некоторой формулы (или множества формул) получать новую формулу.

1.4 Логика высказываний

Для понятия ``высказывание'' иногда используют термин ``пропозиция'', что является калькой с английского. Мы этот термин не используем, но говорим ``пропозициональный'' в смысле относящийся к логике высказываний. Центральными понятиями данной части являются пропозициональные формулы и пропозициональный вывод.

Объектный язык и метаязык

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

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

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

Пропозициональные формулы

Пропозициональная сигнатура – это множество символов, называемых атомами. Символы ¬ (отрицание), & (конъюнкция),  (дизъюнкция) и  (импликация) называются пропозициональными связками; ¬ – унарная связка, а другие – бинарные.

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

Чтобы определить понятие пропозициональной формулы, нам требуется следующее вспомогательное определение.

Определение. Множество X строк замкнуто относительно правил построения (для логики высказываний), если

каждый атом принадлежит X,

для любой строки F, если F принадлежит X, то ¬F тоже принадлежит,

для любых строк F, G и любой бинарной связки , если F и G принадлежат X, то также принадлежит (F  G).

Определение. (Формула). Строка F называется пропозициональной формулой, если F принадлежит всем множествам, которые замкнуты относительно правил построения.

Нормальные формы

Определение. (Эквивалентность). Формула F эквивалентна формуле G, если FI = GI для любой интерпретации I.

Корректность и полнота логики высказываний

Теорема корректности. Если существует вывод F из , тогда  логически влечёт F.

Теорема полноты. Для любой формулы F и любого множества формул , если  влечёт F, тогда существует вывод F из подмножества .

Полнота логики высказываний (для другого множества правил вывода) была установлена Емилем Постом в 1921 году.

1.5 Графы

Графом (G) будем называть тройку объектов (V, X, )

V – множество n вершин.

X – конечное множество ребер.

- функция инцидентности, которая каждому элементу множества X ставит в соответствие пару элементов из множества V.

задана на множестве X.

Если в значении функции инцидентности допускается перестановка вершин, то граф называется неориентированным. В противном случае граф называется ориентированным (Орграф).

Vj – начало ребра

Vk – его конец

xi) = (Vj, Vk) – ребро инцидентно в вершине Vj и в вершине Vk.

Если одной и той же паре вершин инцидентно несколько ребер, то ребра называются кратными.

Если на ребре xi0

(x0) = (Vj0, Vj0),

то ребро называется петлей.

Способы задания графов

  1. Аналитический

Если вершине не инцидентно никакое ребро, то эта вершина называется изолированной.

Выписываются все ребра и пишутся напротив две пары вершин, которым они инцидентны.

В конце выписываются все изолированные вершины.

  1. Геометрический

Каждая вершина графа задается точкой. А ребра, инцидентные паре вершин – кривой.

Желательно рисовать кривые без пересечения. Если пересечения существуют, то их надо отличать от вершин.

  1. С помощью матрицы инцидентности

A(m*n)

m = [V] – число вершин

n = [X}- число ребер

а) Неориентированные графы

Aij = {0, если Vi не инцидентно xj, 1, если Vi инцидентно xj)

б) Орграфы

Aij = {0, если Vi не инцидентно xj, -1, если Vi - начало xj, 1, если Vi - конец xj)

Для петель нужны дополнительные предположения.

Матрица смежности (задается одинаково для всех графов)

B(m*m) m = [V]

Bij равно числу ребер, инцидентных паре вершин (oi, oj)

Если граф не ориентирован, то матрица симметрична.

Граф, в котором нет кратных ребер и петель, называется простым.

Простой граф называется полным, если любой паре его вершин инцидентно одно ребро.

Граф называется двудольным, если множество вершин разбивается на 2 непересекающихся подмножества, такие, что ребра соединяют вершины из разных подмножеств.

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

Маршруты, циклы, связности.

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

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

Маршрут, в котором нет повторяющихся ребер, называется цепью.

Маршрут, в котором нет повторяющихся вершин (кроме первой и последней), называется простой цепью.

Если в простой цепи первая и последняя вершины совпадают, то она называется циклом.

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

Эти части называются компонентами связности.

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

Утверждение.

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

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

Несвязный граф, компонентами связности которого являются деревья, лесом.

Свойства деревьев.

Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.

Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

Планарные графы.

Определение.

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

Сама же укладка графа без пересечения ребер называется плоским графом.

Любой граф можно изобразить в трехмерном пространстве без пересечения ребер.

Для любого графа xi, соединяющего 2 вершины проводим новую плоскость, содержащую эту прямую, а ребро рисуем на плоскости.

Граф будет планарным, если существует его укладка на сфере.

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

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

Парное сочетание (паросочетание) двудольных графов

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

Паросочетанием в двудольном графе называется любое множество попарно несмежных ребер (у них нет общих вершин).

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

Паросочетание называется совершенным (из множества v в множество w), если число ребер в нем совпадает с числом вершин в подмножестве c.

Для любого подмножества S через ф(S) обозначим те вершины из множества w, которые соединяются ребрами с вершинами подмножества S.

Теорема Холла (без доказательства)

Для того, чтобы в двудольном графе существовало совершенное паросочетание, необходимо и достаточно, чтобы для любого подмножества S из множества V выполнялось условие [S] <= [ф(S)].

Венгерский алгоритм нахождения максимального паросочетания.

Дан двудольный граф. Все определения для графа справедливы.

Полным паросочетанием называется паросочетание (ПС), к которому нельзя добавить ни одного ребра графа, не нарушив условие несмежности ребер.


2. Задачи

Задача 1

В штучном отделе магазина посетители обычно покупают или один торт, или одну коробку конфет, или один торт и одну коробку конфет. В один из дней было продано 57 тортов и 36 коробок конфет. Сколько было покупателей, если 12 человек купили и торт и коробку конфет?

Задача 2

Дано три множества:

А = {корпус, процессор, память, материнская плата}

В = {процессор, память, видео карта, дисковод}

С = {память, материнская плата, дисковод, винчестер}

Универсум представляет собой множество:

U = {корпус, процессор, память, материнская плата, видео карта, дисковод, винчестер, сетевая карта}.

Сделать над ними операции и эти операции изобразить с помощью диаграмм Эйлера-Венна:

а)

б)

Задача 3

Даны множества:

A = {a,b,c,d,e}

B = {a,c,e,g,i}

C = {a,c}

D = {e}

Сделать над ними операцию:

Задача 4

Для конечного множества А = {1,2,3,4,5,6,7,8,9,10} составить матрицу отношения, установить, какими свойствами обладает отношение, установить является ли это отношение отношением эквивалентности или порядка(какого порядка).

Отношение: неравенство.

Задача 5

Дано множество V векторов одинаковой длины. Записать проекции векторов с V на i-тую ось.

V = {(a,d,s,o),(b,d,s,o),(c,d,d,f)}

Задача 6

Даны три логических высказывания: А, В, и С. Построить таблицу истинности для логической операции:

Задача 7

Выяснить, является ли следующая формула тавтологией:

Задача 8

Выяснить любым способом, будут ли данные формулы равносильными: и

Задача 9

Построить совершенную дизъюнктивную и совершенную конъюнктивную нормальную форму для заданной логической формулы:

Задача 10

Минимизировать булеву функцию, заданную таблицей истинности, и формулу, которая образовалась после минимизации изобразить в виде переключательной схемы:

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

f

1

0

1

1

0

0

0

1




Скачать документ

Похожие документы:

  1. Решение вопросов безопасности гтс

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

    Решение
    В соответствии с планом работы ФГУП “РФЯЦ ВНИИЭФ”, в рамках двустороннего соглашения о сотрудничестве ФГУП “РФЯЦ ВНИИЭФ” и Научно исследовательского университета ННГУ имени Лобачевского на площадках Технопарка и города Сарова с 18
  3. Решение №1 единственного учредителя

    Решение
    4. Определить Уставный капитал ООО « » в размере 10  (десять тысяч) рублей, что составляет 100% Уставного капитала. Единственная доля Уставного капитала принадлежит единственному учредителю ООО « ».
  4. Решение ученого совета ниу итмо от 29 ноября 2011г

    Решение
    Заслушав и обсудив доклад директора ДМС университета Рыбина А.В. о развитии информационного Интернет-пространства университета в международном измерении Ученый совет отмечает в целом успешное развитие международного портала университета .
  5. Решения Комиссии Совета по железнодорожному транспорту полномочных специалистов вагонного хозяйства железнодорожных администраций государств-участников Соглашения о совместном использования грузовых вагонов в межгосударственном сообщении от 5-7 апреля 2005г

    Документ
    Решения Комиссии Совета по железнодорожному транспорту полномочных специалистов вагонного хозяйства железнодорожных администраций государств-участников Соглашения о совместном использования грузовых вагонов в межгосударственном сообщении»
  6. Решение заседания Консультативного совета по работе с участниками внешнеэкономических связей (далее Совет)

    Решение
    1. О ходе реализации Концепции таможенного оформления и таможенного контроля в местах, приближенных к Государственной границе Российской Федерации в регионе деятельности Горно-Алтайской таможни.

Другие похожие документы..