9

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

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

Контрольная работа

Дискретная математика

Выполнил:

Коновалова Н.В.

Задание 1

Построить таблицу значений функции алгебры логики, найти все существенные переменные:

Решение:

(1)

- знак сложения по модулю два. Вектор значений сложения по модулю два: ₁=(0 1 1 0).

~ - эквивалентность, или равнозначность Вектор значений сложения по модулю два: ₂=(1 0 0 1).

- стрелка Пирса. Вектор значений стрелки Пирса:

₃=(1 0 0 0).

- знак отрицания. Вектор значений отрицания:

₄=(1 1 0 0).

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

Ответ: Вектор значений функции f(x, y, z) (0;1;1;0;1;0;0;1)

Задание 2

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

Решение

(2)

где ? - сложение по модулю 2, знак ? обозначает конъюнкцию.

Метод неопределенных коэффициентов заключается в том, что последовательной подстановкой x, y, z и соответственно значений функций при них в данный полином (2), строится система уравнений:

Полином Жегалкина

P(x, y, z)=₀1₁x₂y₃z₄xy₅xz₆yz₇xyz

Применим к заданной функции:

1=₀1₁0₂0₃0₄00₅00₆00₇000

1=₀1₁0₂0₃1₄00₅01₆01₇001

0=₀1₁0₂1₃0₄01₅00₆10₇010

0=₀1₁0₂1₃1₄01₅01₆11₇011

0=₀1₁1₂0₃0₄10₅10₆00₇100

0=₀1₁1₂0₃1₄10₅11₆01₇101

1=₀1₁1₂1₃0₄11₅10₆10₇110

1=₀1₁1₂1₃1₄11₅11₆11₇111

По свойству суммы по модулю два найдём :

₀=1, ₁=1, ₂=1, ₃=0 ₄=0, ₅=0, ₆=0, ₇=0

Полином Жегалкина будет иметь вид:

(x, y, z) =1 x y

Проверим таблицей истинности:

Таблица 2 - Таблица истинности для полинома Жегалкина

Ответ: Полином Жегалкина будет иметь вид

(x, y, z) =1 x y

Задание 3

Найти СКНФ и СДНФ функции:

Решение

Чтобы получить совершенную дизъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 1 и записать для каждого из них конъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 - то переменную надо взять с отрицанием, если 1 - без отрицания. Из получившихся конъюнкций надо построить дизъюнкцию.

Строится КНФ для заданной формулы. Рассматриваются члены, при которых функция f(x,y,z)=0.При условии, что переменная, входящая в этот член равна нулю, то она записывается без отрицания, а если равна единице, то она записывается с отрицанием. Искомая КНФ для функции (3) будет иметь следующий вид:

Ответ: КНФ функции

ДНФ функции

Задание 4

С помощью карт Карно найти минимальную КНФ и ДНФ функции:

Решение

На практике наиболее важной представляется нахождение минимальной ДНФ, но алгоритм ее нахождения по существу является вариантом перебора всех равносильных ДНФ. Если функция п переменных задана своей таблицей истинности, то правило Блейка имеет простой геометрический смысл. Все возможные наборы переменных представить себе как вершины п-мерного куба со стороной равной 1 (всего вершин будет 2^п) в декартовой системе координат, то надо отметить те вершины, на которых значение функции равно 1, и если какие-то из этих единиц лежат на “прямой”, “плоскости” или “гиперплоскости” в п-мерном пространстве, то в сокращенную ДНФ будут входить “уравнения” этих прямых или гиперплоскостей по известному правилу: если в это уравнение входило составной частью х = 0, то в сокращенную ДНФ входит , если х = 1, то просто х.

Построим карту Карно:

ДНФ:

КНФ:

Задание 5

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

Найдем пути и сечения между вершинами 1 и 4.

Составляем структурную матрицу S, затем вычеркиваем из нее 1-ю строчку и 4-й столбец (тем самым получаем минор М(1,4)):

Искомые пути, расположенные в порядке прохождения ребер:

П₄₁ = aeaсdfbcgbdeh

Сечения же получатся отрицанием этих путей. Применяя правила де Моргана (заменяя конъюнкцию на дизъюнкцию и наоборот), затем раскрывая скобки, получаем: (знаки отрицания опущены во всех равенствах, кроме 1-го):

S₄₁= aeaсdfbcgbdeh = (ae) (acdf) (bcg) (bde) h = abhabchabghabdh v abeh ebh ebch ebgh ebdh v abcdefh v abcdfgh v abcdegh v abcdefgh

Задание 6

Придумать связный взвешенный граф из восьми вершин и не менее чем 14 ребер (нумерация ребер - слева направо, веса от 1 до 20). Для этого графа построить минимально остовное дерево с помощью алгоритма Прима, и найти расстояние между вершинами 1 и 8 с помощью алгоритма Дейкстры. Реализовать алгоритм на любом языке программирования.

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

алгебра логика граф

Алгоритм Дейкстры (поиск пути с минимальным весом).

Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив S содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие рас- стояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний A[i,k] задает длины дуге A[i,k]; если такой дуги нет, то A[i,k] присваивается большое число Б, равное "машинной бесконечности".

1 (инициализация). В цикле от 1 до N заполнить нулями массив

S; заполнить числом i массив C; перенести i-ю строку матрицы

A в массив B,

S[i]:=1; C[i]:=0 (i - номер стартовой вершины)

2 (общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для

которых S[k]=0); пусть минимум достигается на индексе j, т. е. B[j]<=B[k]

Затем выполняются следующие операции:

S[j]:=1;

если B[k] > B[j]+A[j,k], то (B[k]:=B[j]+A[j,k]; C[k]:=j)

(Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk).

(Если все S[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь

надо) перечислить вершины, входящие в кратчайший путь).

3 (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке

следующей процедурой:)

3.1. z:=C[k];

3.2. Выдать z;

3.3. z:=C[z]. Если z = О, то конец,

иначе перейти к 3.2.

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

Рисунок 2 - Реализация алгоритма Дейкстры

Для построения остова графа воспользуемся алгоритмом Прима:

Начинаем с пустого U=0. Добавляем к U вершины, каждый раз находя ребро наименьшей стоимости между U и V-U.

Положить в U любую вершину; // изначально U - пусто.

while ( V-U не пусто )

{

Выбрать ребро (u, v) наименьшей стоимости,

u из U, v из V-U;

Добавить v к U (и убрать из V-U);

Применим алгоритм, начиная с U={V_{5-7}}. Шаги алгоритма следующие:

· W_min(u,v)= U={V_{5-7},V_{7-8}}

· W_min(u,v)= U={ V_{5-7},V_{5-6},V_{7-8}}

· W_min(u,v)= U={ V_{5-7},V_{5-6},V_{7-8},V_{4-7}}

· W_min(u,v)= U={ V_{5-7},V_{5-6},V_{7-8},V_{4-7},V_{3-5}}

· W_min(u,v)= U={ V_{5-7},V_{5-6},V_{7-8},V_{4-7},V_{3-5},V_{2-4}}

· W_min(u,v)= U={ V_{5-7},V_{5-6},V_{7-8},V_{4-7},V_{3-5},V_{2-4}},V_{1-2}}

Результатом является остовное дерево графа.

5-7 5-6 7-8 4-7 3-5 2-4 1-2

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

1. Гиндикин С.Г. Алгебра логики в задачах. М., 1972.

2. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

3. Лихтарникова Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. СПб, 1988.

4. Мамонтова Н.П. и др. Методические указания к практическим занятиям по теории сетей связи / ЛЭИС. Л., 1978.

5. Нефедов В.Н., Осипова В.А. Курс дискретной математики / МАИ. М., 1992.

6. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

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