Специальность 230100.62 Контрольная работа по дискретной математике (стр. 5 )

Найдем для нее полином Жегалкина. Это можно сделать методом неопределенных коэффициентов, а можно непосредственно переписывая отрицание и дизъюнкцию через операции алгебры Жегалкина:

ПФ не является линейной (есть ).

, а — это противоречит определению монотонности, следовательно, не является монотонной.

, т. е. не сохраняет 0.

, т. е. сохраняет 1.

, т. е. , значит, не является самодвойственной.

2. Функция .

линейная (нет конъюнкции).

монотонна, т. к. для всех .

, сохраняет 0.

, не сохраняет 1.

, не является самодвойственной.

По таблице видим, что для каждого из классов нашлась ПФ, ему не принадлежащая, значит ∑ – функционально полная система.

Определение. Функционально полная система называется базисом, если при удалении из нее любой ПФ, она перестает быть функционально полной.

Если из нашей системы убрать , то останется 0, который один не дает функционально полной системы (он принадлежит ); если же убрать 0, то останется , которая сохраняет 1. Поэтому система ∑ образует базис.

Ответ. Данная система является функционально полной и образует базис.

Замечание.

1. Ранее отмечалось, что из функций двух переменных только ⊕  и линейные, поэтому нелинейность можно было определить сразу.

2. Для проверки функциональной полноты после того, как таблица заполнена для первой функции, для второй достаточно было проверить лишь принадлежность или непринадлежность ее классу . Для проверки на базис таблица просматривается полностью.

Дополнительные указания по графам

Теория графов — удобный аппарат для формализации и решения задач из самых разных областей. К ним, в частности, относятся: проектирование и исследование сетей связи, анализ электрических сетей, анализ печатных схем, задачи проектирования электрических и монтажных схем, блок-схемы программ, исследование автоматов, задачи календарного планирования, планирование и обеспечение материально-технического снабжения, поиск информации, теория информации, размещение предприятий коммунального обслуживания, теория игр, биология, генеалогия, головоломки, определение химического состава и многое другое.

Говоря нестрого, граф — это множество точек (вершин) и соединяющих их отрезков линий (ребер). Основной пример — схемы коммуникаций: дороги, авиалинии, трубопроводы и т. п.

Мы должны изучить основные понятия теории графов и некоторые задачи, связанные с ними. Терминология этого раздела дискретной математики не является общеупотребительной, она своя у разных авторов. Мы будем придерживаться определений из [6]. Если вы пользуетесь другими пособиями, сравнивайте, какие понятия совпадают с [6], а какие отличаются. Рассмотрим эти понятия на примерах.

Пример. Дан граф G:

1. Определить степени всех вершин графа.

2. Записать матрицу смежности вершин .

3. Записать матрицу инцидентности .

4. Указать мосты и точки сочленения, если они есть.

5. Проверить, является ли граф эйлеровым.

6. Проверить, является ли граф гамильтоновым.

7. Проверить, является ли граф двудольным. Если да, указать подмножества V1 и V2.

8. Записать какой-нибудь маршрут от до .

9. Указать какой-нибудь простой цикл.

10. Построить дерево, покрывающее граф.

Решение. 1.Степенью вершины графа называется количество рёбер, инцидентных ей. Вершине инцидентно лишь  одно ребро e1, значит, , а вершине инцидентны ребра , , , значит, и т. д. Составим таблицу.

	1	3	2	2	4	3	3	3	1

2.Матрица смежности вершин.

, где — число вершин, равно количеству рёбер, соединяющих вершины и .

Если граф не содержит кратных рёбер и петель, то ,  если вершины и смежные, и в противном случае.

В нашем примере , так как нет петель, , так как вершина смежна , и т. д.

3.Матрица инцидентности имеет m строк (m-количество рёбер) и n столбцов, , если ребро инцидентно вершине , и в противном случае.