Дискретная математика. Громов Ю.Ю - 43 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

43
Заметим, что любую булеву функцию можно представить в виде су-
перпозиции любого из полученных базисов.
Техническая реализация булевых функций, вошедших в базисы, мо-
жет быть основана на использовании различных физических явлений.
Так, например, магнитные явления используются для реализации импли-
кации и коимпликации, явления в полупроводниках – для реализации
функций Шеффера и Вебба.
Задачи и упражнения
1. Установить, сохраняет ли константы 0 и 1, является ли линейной,
самодвойственной и монотонной булева функция:
а) f(x
1
, x
2
) = x
1
∨
2
x
;
г) f(x
1
, x
2
) = x
1
∨
x
2
;
б) f(x
1
, x
2
, x
3
) = x
2
∨
x
1
x
3
;
д) f(x
1
) =
1
x
;
в) f(x
1
, x
2
) =
21
xx
; е) f(x
1
, x
2
, x
3
) = x
1
x
2
∨
3
2
3
1
xxxx ∨
.
2. Определить, является ли полной система S булевых функций, и
образует ли она базис в двузначной логике:
а) S = {x
1
, x
1
x
2
∨
3
x
, x
1
∨ x
2
}; г) S = { x
2
∨
3231
xxxx
∨
,
x
1
x
2
∨ x
2
x
3
};
б) S = {x
1
x
2
,
31
2
xxx
∨
,
3
x
∨
2
1
xx
};
д) S = {
2
1
xx
∨
, x
1
x
2
x
3
,
1
x
};
в) S = { x
1
x
2
∨
1
x
,
3
2
3
1
xxxx
∨
}; е) S = {
2
1
xx
,
1
x
}.
8. ВЗВЕШЕННЫЙ ГРАФ И ЕГО МАТРИЧНОЕ ЗАДАНИЕ
Ранее понятие графа G было определено как совокупность множест-
ва вершин V и множества дуг U ⊂ V
2
:
G = 〈V, U 〉.
Введём некоторые дополнительные понятия. Говорят, что дуга
u ∈ U, соединённая с вершиной v ∈ V, инцидентна вершине v, а верши-
на v при этом коинцидентна дуге u. В дуге (v
i
, v
j
) вершины v
i
и v
j
называ-
ются граничными вершинами, причём v
i
– её начало, а v
j
– конец.
При удалении дуг из графа G = 〈V, U〉 получают частичный граф G′
графа G:
G′ = 〈V, U′〉, U′ ⊂ U .
Исключая из графа G вершины и инцидентные им дуги, получают
подграф G′′ графа G:
G′′ = 〈V′′, U′′〉, V′′ ⊂ V, U′′ ⊂ U .

Страницы