Основы дискретной математики

Министерство образования Республики Беларусь Министерство образования и науки Российской Федерации ГУВПО «Белорусско-Российский университет».

Кафедра «Автоматизированные системы управления».

Задание № 21.

по курсу «Дискретная математика».

Выполнил:

студент группы АСОИ-091.

Людаговский В.В.

Проверил:

доцент каф. АСУ, к.т.н.

Якимов А.И.

Могилев 2010.

Вопрос 1.

Пусть U — множество точек плоскости, на которой задана декартова система координат. Найти пересечение множеств A? B, объединение AUB, разности множеств AB, BA, дополнения множеств A`, B`, изобразить их на плоскости:

A=, B=.

Решение:

По определению:

1.

2.

3.

4.

5.

6.

Вопрос 2.

[Доказать выполнимость следующего соотношения .

Доказательство:

Пусть, , .

а) Рассмотрим. Найдем множество. По определению.

.

Обозначим через x все элементы, которые удовлетворяют следующим условиям:, , а через у все элементы с, такие что .

Следовательно,, .

По определению декартового произведения множеств.

(1).

б) Рассмотрим выражение .

По определению декартового произведения множеств.

;

.

Тогда состоит из множества всех упорядоченных пар , таких, что a=b=x, c=y, т. е.

(2).

Из равенства правых частей соотношений (1) и (2) следует, что ..

Вопрос 3.

Построить композиции отображений и; проверить, являются ли они инъективными, сюръективными или биективными..

..

Решение:.

Композиция функций не является сюръекцией, так как нет ни одного элемента, для которого y=0 есть образ. Композиция функций не является инъекцией, так как различным может соответствовать одно значение. Композиция не является биекцией..

Композиция функций и является отображением Вопрос 4.

На множествах, А и В заданы отношения порядка и соответственно и задано отображение, где. Определить, является ли оно изотонным, изоморфизмом или автоморфизмом..

А={2,3,6,12,24}, B={1,2,3,5,6,10,15,30}; f (2)=1; f (3)=1; f (6)=5; f (12)=10; f (24)=30; =:{х делитель у}..

Решение:.

Нам известны образы функции f:. f (2)=1; f (3)=1; f (6)=5; f (12)=10; f (24)=30..

Множество, А — решетка, в которой можно выделить две цепи. Для цепи 261 224 отображение f сохраняет порядок, так как 151 030, т. е.

f (2) f (6) f (12) f (24). Для цепи 361 224 отображение f также сохраняет порядок, так как 151 030, т. е. f (3) f (6) f (12) f (24). Следовательно, отображение изотонно. Отображение также является изоморфизмом, так как обратное отображение f сохраняет порядок: для значений f (2) f (3) (1=1) прообразы 2 и 3 сравнимы..

Следовательно, отображение f изотонно и является изоморфизмом..

Вопрос 5..

Проверить полноту системы функций.

Решение:.

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

Т0 — класс функций, сохраняющих 0;.

T1 — класс функций, сохраняющих 1;.

S — класс самодвойственных функций;.

М — класс монотонных функций;.

L — класс линейных функций..

Для исследуемой системы составим таблицу Поста. Если функция входит в функционально замкнутый класс, то в таблице Поста в соответствующей ячейке ставится знак «+», иначе — знак «-»..

Для исследования системы на полноту построим таблицы.

истинности функций..

1. Обозначим ..

y.	x.	f1(x, y).

Функция f (x) не сохраняет 0 и 1, так как на нулевом наборе она принимает значение 1, а на единичном — 0. Очевидно, что данная функция немонотонна. Функция самодвойственна, так как на противоположных наборах функция принимает противоположные значения..

Для проверки линейности построим канонический полином Жегалкина:. Функция нелинейна, т.к. содержит элемент ху..

2. Обозначим ..

y.	x.	f2(х, у).

По таблице истинности видим, что f2(х, у) не сохраняет 0 и сохраняет 1. Эта функция монотонна, так как набор (0,0) предшествует набору (1,0), f2(0,0) >f2(1,0).На противоположных наборах (0,0) и (1,1) функция принимает одинаковые значения 0, следовательно, она несамодвойственна..

Функция линейна..

3. Построим таблицу Поста для заданной системы..

	T0.	T1.	S.	M.	L.
>	;		;	;	;
	;	;	;

Система функций будет полна, если в каждом столбце таблицы Поста стоит хотя бы один знак «-». Система функций полна..

Вопрос 6.

Определить, является ли формула тавтологией?.

Решение..

Построим таблицу истинности..

отображение функция триггер автомат.

A.	B.

Формула является тавтологией, так как не существует интерпретации, на которой она принимает ложное значение..

Формула является тавтологией..

Вопрос 7.

Дешифратор управляет семисегментным (сегменты a, b, c, d, e, f, g) индикатором, отображающим символы от 0 до 9, a, b, c, d, E, F. На вход дешифратора поступает четырехразрядный двоичный код. Необходимо составить таблицу истинности для логических функций управления сегментами индикатора. Для сегмента a синтезировать логическую схему управления..

Решение:.

Таблица истинности:.

x1.

x2.

x3.

x4.

a.

b.

c.

d.

e.

f.

g.

a.

b.

c.

d.

E.

F.

Для сегмента a: ..

Логическая схема управления для сегмента a..

Вопрос 8.

Используя канонический метод структурного синтеза конечных автоматов построить логическую схему однотактного JK триггера на заданном элементе памяти — T триггере..

Обобщённые схемы структурного автомата:.

Yt=л (qt;xt), qt+1=д (qt;xt), Tt=f (qt;xt)..

xt.	qt.	Yt (л).	Tt (f).	qt+1(д).
J.	K.	Q.	Y.	T.	Qt+1.

Y=Q.

Логическая схема:.

Литература

Таран Т. А., Мыценко Н. А., Темникова Е. Л. Сборник задач по дискретной математике. / 2-е изд., перераб. и доп. — К.: Инрес, 2005. — 64 с..

.