Задание. Таблица истинности функции двух переменных 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. Раскрасить граф последовательным алгоритмом в минимальное число цветов.
|
