История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2017-12-12 | 211 |
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}.
|
|
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!