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

1) используя правила де Моргана, получить ДНФ и упростить её.

Решение:

2) даны две функции , Требуется:

а) для функции составить таблицу истинности и найти по ней полином Жегалкина, СДНФ и СКНФ. Упростить, если возможно, СДНФ.

б) для функции составить таблицу истинности и найти по ней полином Жегалкина, СДНФ и СКНФ. По карте Карно получить минимальную ДНФ, нарисовать эквивалентную РКС.

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

,

Решение:

а)

x	y

Найдем полином Жегалкина

СКНФ:

x	y

СКНФ=

СДНФ:

x	y

СДНФ=

б)

x	y	z

Функция является противоречием

Так как функция является противоречием, то полином Жегалкина равен 0, проверим это:

СКНФ:

x	y	z

СКНФ=

СДНФ:

Так как все значения функции равны нулю, функция не имеет СДНФ, соответственно невозможно получить минимальную ДНФ

в)

Рассмотрим заданные функции:

1. , – функции, сохраняющие ноль.

2. – функция, сохраняющая единицу. – – функция, не сохраняющая единицу.

3. – функция, не самодвойственная. – функция самодвойственная

4. – линейная – линейная

5. , – функции монотонные

	T0	T1	S	M	L
	+	+	-	+	+
	+	-	+	+	+

Система не является полной, так как она целиком содержится в классах T₀, М и L

3) дан граф. Составить для данного графа структурную матрицу. Найти: а) все простые пути из вершины i в вершину j; б) совокупность всех сечений между вершинами i и j.

i=3, j=5

Решение:

Составим структурную матрицу:

а) найдем все простые пути из вершины 3 в 5:

Вычислим минор , заменяя сложение и вычитание на дизъюнкцию, а умножение на конъюнкцию.˅

Получили все простые пути:

3→2→5

3→2→1→5

б) найдем совокупность сечений между 3 и 5 вершиной:

Получили совокупность сечений.

4)

заданы сеть и начальный поток f. Требуется построить максимальный поток, считая вершину с номером 1 источником и вершину с номером 4 стоком. Указать минимальное сечение, величина которого равна максимальному потоку.

Решение:

Путь из s=1 в t=4, по которому поток может быть увеличен, состоит из прямых дуг, соединяющих вершины s=1→3→t=4. Пометки указанных вершин

Добавка к потоку:

Построим новый поток ,

Путь из s=1 в t=4, по которому поток может быть увеличен, состоит из прямых и обратных дуг, соединяющих вершины s=1→2←3→t=4. Пометки указанных вершин

Построим новый поток ,

Путь из 1 в 4, на котором возможно увеличение потока построить не удалось, до стока t не дошли, поток максимален

Найдем минимальное сечение. Помеченные вершины М1={1,2}. Непомеченные вершины М2={3,4}. Прямые насыщенные дуги, идущие из М1 в М2, образуют минимальное сечение . Величина этого сечения равна 5+2+1+4=12 и совпадает с величиной максимального потока

5) на указанном множестве задано отношение. Для каждого отношения нужно: а) записать отношение R; б) построить матрицу смежности и граф отношения; в) проверить, является ли отношение рефлексивным, симметричным, транзитивным.

На множестве А={1,2,3,4,5,6} задано отношение R: xRy тогда и только тогда, когда x и y имеют общий делитель, отличный от 1

Решение:

а) Запишем отношение

Отношение R определяется множеством пар

(2,2) (2,4) (2,6)

(3,3) (3,6)

(4,2) (4,4) (4,6)

(5,5)

(6,2) (6,3) (6,4) (6,6)

б) построим матрицу смежности и граф отношения

Проверим свойства:

Рефлексивность. Отношение не рефлексивное, так как для x =1 отношение не выполняется, так как 1 имеет только один делитель, равный 1

Симметричность. Отношение симметрично, так как если x и y имеют общий делитель, отличный от единицы, то и y и x так же, имеют его

Транзитивность. Отношение не транзитивно, покажем на примере:

x и y имеют общий делитель 3, z и y имеют общий делитель 2, а x и z не имеют общего делителя, отличного от единицы

Дата добавления: 2015-07-11