Вариант 8: задания 1, 2, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15

  • ID: 06898 
  • 8 страниц

Фрагмент работы:

Вариант 8: задания 1, 2, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15

Вариант 8 (стр. 223)

№1

Доказать тожества, используя только определения операций над множествами.

а)...

РЕШЕНИЕ:

(=>) Пусть..., это выполняется тогда и только тогда, тогда.... А это значит, что x не лежит ни в A, ни в B, т.к. если бы он лежал хотя бы в одном множестве, то он лежал бы и в объединении этих множеств.

Получается, что... и..., или, по-другому... и.... По определению это....

( [0, 1) по следующему правилу:

f(x)=x, для всех x не равных (1/2)n

f(x)=x/2, для всех x равных (1/2)n

Тогда мы получаем взаимно-однозначное отображение, причём в образе этого отображения не будет единицы (1=(1/2)0).

Теперь сделаем отображение g:[0, 1] -> (0, 1] по правилу g(x)=1-f(x) - оно взаимно-однозначно.

№3

Доказать методом мат.индукции.

РЕШЕНИЕ:

10. База индукции.... =...

20. Шаг индукции: n=>n+1.

Пусть выполнено... для n. Проверим что выполняется следующее равенство:....

Заменим первые n слагаемых по предположению индукции:....

=...

Последнее утверждение истинно, значит истинно и то, что мы собирались доказать.

№4

Изобразить P1, P2 графически. Найти.... Проверить с помощью матрицы [P2] является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным.

=...

=...

РЕШЕНИЕ

Из вида матрицы [P2] можно заключить, что отношение P2 является рефлексивным (на диагонали матрицы стоят единицы), симметричным (матрица симметрична), транзитивным (т.к. [P2?P2]=[P2]), не является антисимметричным (есть элементы вне диагонали для симметричной матрицы). Таким образом, отношение P2 является отношением эквивалентности (рефлексивность, симметричность, транзитивность).

№5

Найти область определения, область значений отношения P. Является ли отношение рефлексивным, симметричным, транзитивным?

РЕШЕНИЕ:

Область определения, значений....

Рефлексивность: проверим.... Т.е...., это неверно, значит отношение не является рефлексивным.

Симметричность: пусть..., тогда.... Проверим, будет ли выполняться.... Очевидно, что нет, например при y=2, x=0. Следовательно, отношение не является симметричным.

Транзитивность: Пусть... и.... Тогда, по определению... и.... Отсюда следует, что..., и уж тем более.... То есть отношение является транзитивным.

№9

Даны графы G1 и G2. Найти............. Для графа... найти матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1.

G1:...G2:...

РЕШЕНИЕ:

:......:......:...

:...

Найдём для графа... матрицу смежности:

матрицу инцидентности (занумеруем дуги так e1=(1,1), e2=(1,2), e3=(1,3), e4=(1,4), e5=(2,2), e6=(2,3), e7=(3,2), e8=(3,4), e9=(4,1), e10=(4,3)):

Матрица сильных компонент S, находим через матрицу достижимости C:

=...

Матрица маршрутов длины 2:

Количество всех маршрутов длины 2, исходящих из вершины 1: 10.

№10

Найти матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли граф Эйлеровым? Является ли он планарным?

G:...

РЕШЕНИЕ:

Сразу заметим, что граф планарен. Т.к. его можно изобразить без пересечений:

Кроме того, он не является Эйлеровым, т.к. есть нечётные вершины.

Цикломатическое число:...=12-8+1=5.

Остов:...

u1..., u7 - ветви остова, v1..., v5 - хорды остова.

Матрица фундаментальных циклов:

Матрица фундаментальных разрезов (получаем транспонированием подматрицы в С):

Найдём эксцентриситеты вершин: e(1)=3, e(2)=2, e(3)=3, e(4)=3, e(5)=3, e(6)=3, e(7)=2, e(8)=3

Радиус=2, диаметр=3.

Найдём минимальное множество покрывающих цепей графа.

По теореме 4.7.2 минимальное число покрывающих цепей равно 2:

1-я цепь: u2, u3, u4, u5, v3, v2

2-я цепь: v1, u6, u7, v5, u1, v4.

№11

Составить таблицы истинности формул.

f=..., g=....

РЕШЕНИЕ:

x y......... f

0 0 1 1 0 0

0 1 0 0 1 1

1 0 1 0 0 1

1 1 0 1 0 0

x y............ xy... g

0 0 0 1 0 0 0 1 0

0 0 1 1 0 1 0 1 1

0 1 0 0 1 1 0 1 1

1 0 0 1 0 0 0 1 0

0 1 1 0 1 1 0 1 1

1 0 1 1 0 1 0 1 1

1 1 0 0 0 0 1 0 1

1 1 1 0 0 1 1 0 0

№12

Проверить эквивалентность формул:

а) таблицами истинности;

б) эквивалентными преобразованиями.

и...

РЕШЕНИЕ:

а)

x y z...............

0 0 0 1 1 0 0 1

0 0 1 1 1 0 1 1

0 1 0 0 0 1 0 0

0 1 1 1 1 1 1 1

1 0 0 1 1 1 1 1

1 0 1 1 1 1 1 1

1 1 0 0 1 1 1 1

1 1 1 1 1 1 1 1

б) эквивалентность:

№13

Эквивалентными преобразованиями привести формулу... к ДНФ, КНФ, СДНФ, СКНФ, полином Жегалкина.

РЕШЕНИЕ:

- ДНФ

СДНФ:...

КНФ:... - СКНФ

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

№14

Найти сокращённую, все тупиковые и минимальные ДНФ функции f(x, y, z)

=...

РЕШЕНИЕ:

а) методом Квайна.

СДНФ:....

000 001 011

100 110

00X 0X1

X00 1X0

Сокращённая ДНФ:...

000 001 011 100 110

00X v v

X00 v v

0X1 v v

1X0 v v

Тупиковые:.......

Минимальные:.......

б) карты Карно.

Обе минимальные.

Классы Поста: не сохраняет единицу ( f(1, 1, 1)=0), не сохраняет ноль (f(0, 0, 0)=1).

не самодвойственна ( f(0, 0, 1)=1?...(1, 1, 0)=0), нелинейна (...)

не монотонная (т.к. не сохраняет единицу и не тождественно ложна).

№15

Найти сокращённую, все тупиковые и минимальные ДНФ, КНФ функции

=...

x1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

x2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

x3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

x4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

f 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1

Нарисуем карты Карно:

здесь "максимальными" импликантами будут... и.... Остальные точки покроем разными способами:

Все тупиковые и минимальные ДНФ.

Для нахождения КНФ применим принцип двойственности:

Получаем две импликанты:... и....

Таким образом, сокращённая, тупиковая и минимальная КНФ:....