Задание. Таблица истинности функции двух переменных Y=f(X1, Х2) содержит 4 строки, а число функций двух переменных равно 16

Таблица истинности функции двух переменных Y=f(X1, Х2) содержит 4 строки, а число функций двух переменных равно 16. Рассмотрим только несколько основных функций двух переменных.

1. Логическое ИЛИ (логическое сложение, дизъюнкция): Y= X1 + X2 = X1 V X2 Техническая реализация этой функции - два параллельно соединенных ключа:

Логический элемент ИЛИ обозначается на схемах следующим образом:

2. Логическое И (логическое умножение, конъюнкция, схема совпадений): Y = X1X2 = X1&X2 Техническая реализация этой функции - два последовательно соединенных ключа:

Логический элемент И обозначается на схемах следующим образом:

3. Функция стрелка Пирса (ИЛИ-НЕ): Y = NOT(X1+X2). Логический элемент ИЛИ-НЕ обозначается на схемах следующим образом:

4. Функция штрих Шеффера (И-НЕ): Y = X1|X2 = NOT(X1X2). Логический элемент И-НЕ обозначается на схемах следующим образом:

Есть ещё три логические функции двух переменных, имеющие специальные названия: импликация, эквивалентность, неравнозначность (исключающее ИЛИ, сложение по модулю 2). Последние две функции являются взаимно обратными, также как, например, функция И и функция штрих Шеффера.

Тема: Основы теории алгоритмов

Цель работы:

· Изучить методы построения минимального остовного дерева.

· Изучить методы раскраски графа в минимальное число цветов.

Задание

Задан неориентированный взвешенный граф G. Построить минимальные остовные деревья Жадным алгоритмом и алгоритмом Прима.

Дан неориентированный граф G. Раскрасить граф последовательным алгоритмом в минимальное число цветов.