МАТЕМАТИЧЕСКАЯ ЛОГИКА

Построить таблицу истинности для формулы, СДНФ, СКНФ, затем упростить формулу

Задание 1. Построить таблицу истинности для формулы, СДНФ, СКНФ, затем упростить формулу.

Решение:

Таблица истинности заданной функции имеет вид: x'y'z'f(x,y,z) 0'0'0'1 0'0'1'0 0'1'0'1 0'1'1'0 1'0'0'1 1'0'1'1 1'1'0'1 1'1'1'1

Представим заданную логическую функцию в виде СДНФ (записав дизъюнкцию всех единиц функции):

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

В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.

Представим заданную логическую функцию в виде СКНФ:

.

Упростим СКНФ (поскольку в ней меньше элементов, чем в СДНФ):

Задание 3. Провести анализ РКС (по возможности упростить)

Решение:

Заданной РКС соответствует функция проводимости:

Упростим функцию проводимости.

Используем закон Блека-Порецкого, в результате получаем:

Используем закон Блека-Порецкого, получаем:

Используем свойство идемпотентности, в результате имеем:

Упрощенная РКС будет иметь вид:

Задание 4. Синтезировать РКС по заданным условиям ее работы

f(010)=f(100)=f(101)=f(011)=0.

Решение:

Запишем СКНФ функции проводимости:

Используем свойство склеивания, получаем:

Синтезированная РКС имеет вид:

Задание 5. Построить дерево кратчайших расстояний:

расстояния между узлами – произвольно от 1до 4, нумерация узлов на ваше усмотрение, начало тёмный кружок (1)

Решение:

Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 5.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0+1=1. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 1. Аналогичную операцию проделываем с двумя другими соседями 1-й вершины —3 и 5.

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

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 1. Ее соседи – вершины 3, 4 и 5.

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

Третий шаг. Шаг алгоритма повторяется, находим «ближайшую» из непосещенных вершин. Это вершина 5 с меткой 1. Ее соседи – вершины 3, 7, 8 и 9.

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

Четвертый шаг. Снова находим «ближайшую» из непосещенных вершин. Это вершина 3 с меткой 2. Ее соседи – вершины 4, 6 и 8.

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

Пятый шаг. Очередная «ближайшая» из непосещенных вершин - вершина 7 с меткой 2. Ее соседи – вершины 4, 6, 8 и 9.

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

Шестой шаг. Снова находим «ближайшую» из непосещенных вершин. Это вершина 8 с меткой 2. Ее соседи – вершины 4, 6, и 9.

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

Седьмой шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 4 с меткой 3. Ее соседом является вершина 6.

Все соседи вершины 4 проверены. Текущее минимальное расстояние до вершины 4 считается окончательным и пересмотру не подлежит. Вычеркнем её из графа, чтобы отметить, что эта вершина посещена. Поскольку у оставшихся вершин (6 и 9) нет непосещенных соседей, поиск завершаем.

Построим дерево кратчайших расстояний. Оно имеет вид:


Способ заказа и контакты