Специальные разделы математики. Элементы дискретной математики - Контрольная работа

Содержание

З а д а ч и 401 – 410. Даны формулы алгебры логики. Составить по ним таблицы истинности и совершенные дизъюнктивные нормальные формы (СДНФ).

403. .

З а д а ч и 411 – 420. Даны две формулы алгебры логики. Проверить их равносильность двумя способами: а) с помощью таблиц истинности; б) с помощью равносильностей.

413. .

З а д а ч и 421 – 430. Дан граф, вершины которого занумерованы. В таблице приведены номера ребер, соединяющих данные вершины, и длины этих ребер. Найти а) матрицу смежности графа; б) матрицу инцидентности графа; в) все маршруты длины 2, выходящие из вершины 1; г) все простые циклы, проходящие через вершину 1; д) выяснить, будет ли граф связным; е) найти степени всех вершин графа; е) выяснить, будет ли граф эйлеровым; ж) найти остов графа.

423.

Номера

смежных

вершин 12 13 14 15 16 18 23 56 67 68 78

Номер

ребра

Основная часть (выдержка)

Составим таблицу истинности:

x y

0 0 1 1 1 1

0 1 0 0 0 1

1 0 1 1 0 0

1 1 0 1 0 0

Составим СДНФ, равносильную исходной формуле. Выделим строки таблицы истинности формулы , в которых . По каждой из строк составляем конъюнкции следующим образом: если соответствующее значение аргумента в строке таблицы истинности равно 0, то соответствующий аргумент входит в конъюнкцию с отрицанием, если 1, то без отрицания. Собирая их через дизъюнкцию, получаем СДНФ, равносильную исходной формуле:

б)

Заключение (выдержка)

Найдем следующий цикл из списка, не содержащий ребро : 1561. Удалим из графа ребро , соединяющее вершины 5 и 6. Диаграмма графа будет выглядеть так:

Теперь найдем цикл, не содержащий ребер и . Это будет цикл 1681. Удалим из графа ребро l10, соединяющее вершины 6 и 8.

Следующий цикл 16781. Удалим из графа ребро l9, соединяющее вершины 6 и 7.

В полученном графе циклов нет, и он служит решением данной задачи.