История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Дисциплины:
2017-12-12 | 212 |
5.00
из
|
Заказать работу |
|
|
Пусть множество Х состоит из двух элементов 0 и 1, Х={0,1}; множество Y=Xn = {(x1, …,xn) | "i = , xi Î X}.
Логическая переменная – это переменная, которая может принимать только два значения: истина или ложь (true/false, 1/0).
Функция алгебры логики (булева функция) – f(x1,x2, …,xn) – это функция, у которой все аргументы есть логические переменные, и сама функция принимает только логические значения.
Количество всевозможных, различных двоичных наборов длиной n равно 2n.
способы описания ФАЛ:
Табличный (Любую булеву функцию можно представить таблицей, имеющей 2n строк. Такая таблица называется таблицей истинности.)
Графический (ФАЛ можно представить в виде n-мерного единичного куба: если наборам значений аргументов сопоставить точки n-мерного пространства, то множество 2n наборов определяет множество вершин n-мерного куба.)
- аналитический
- словесный
Законы булевой алгебры
Коммутативность
Ассоциативность
Дистрибутивность
Законы де Моргана
Законы поглощения
Законы склеивания
7)
Теория неориентированных графов. Подграф и изоморфизм.
Пусть V – некоторое непустое множество (V ¹ Æ).
V(2) – множество всех его двухэлементных подмножеств (V(2)={(u,v)|u,vÎV, неупорядоченная пара }).
Неориентированный граф G – пара множеств (V,E), E Í V(2) ,
где V – множество вершин графа G,
E – множество рёбер графа G.
Если |V|=p, а |E|=q, то обозначают граф G – (p, q)- граф или p-граф.
Изоморфные графы – существует взаимноодназначное соответствие, т. е. биекция, между множествами их вершин, сохраняющая отношение смежности.
Изоморфизм графов G и H: G @ H.
Изоморфизм есть отношение эквивалентности, т. к. он:
|
- симметричен;
- рефлексивен;
- транзитивен.
Подграф G1 = (V1, E1) графа G = (V, E) – граф, у которого все вершины и ребра удовлетворяют следующим соотношениям V1 Í V, E1 Í E.
Остовный подграф графа G -подграф, содержащийвсе вершины графа G, множество ребер есть подмножество ребер графа G.
Порожденный подграф (порожденный подмножеством вершин V1) – подграф, множество вершин которого V1 Í V, а множество ребер Е1 содержит все ребра графа G, инцидентные выбранным вершинам V1.
Связность в неорграфах.
Связный неориентированный граф G – любая пара вершин соединена маршрутом (простой цепью) в G.
Компонента связности или компонента графа G – максимальный связный подграф графа G.
Любой несвязный граф содержит, по крайней мере, две компоненты связности.
Теорема 1: Любой граф G является объединением своих компонент связности.
Теорема 2: Либо граф, либо его дополнение связны.
Число вершинной связности χ(G) – наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу.
Число реберной связности l(G) – наименьшее число рёбер, удаление которых приводит к несвязному или одновершинному графу.
Например:
Граф G: Граф R:
Граф G – связен.
Граф R – несвязен, в графе R три компоненты связности, R1 = {1,2,3}, R2 ={4}, R3={5,6,7}.
|
|
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!