Основы дискретной математики
Министерство образования Республики
Беларусь
Министерство образования и науки
Российской Федерации
ГУВПО «Белорусско-Российский
университет»
Кафедра «Автоматизированные системы
управления»
Задание №21
по курсу «Дискретная математика»
Выполнил:
студент
группы АСОИ-091
Людаговский
В.В.
Проверил:
доцент каф.
АСУ, к.т.н.
Якимов А.И.
Могилев 2010
Вопрос 1
Пусть U - множество точек плоскости, на
которой задана декартова система координат. Найти пересечение множеств A∩B, объединение AUB,
разности множеств A\B, B\A, дополнения
множеств A`, B`, изобразить их на плоскости:
={<x,y>|y≥x2}, B={<x,y>|-3≤y≤5, -7≤x≤1}.
Решение:
По определению:
1.
.
.
.
.
.
Вопрос
2
[Доказать
выполнимость следующего соотношения .
Доказательство:
Пусть
, , .
а)
Рассмотрим . Найдем множество . По
определению
.
Обозначим
через x все элементы, которые удовлетворяют следующим
условиям: , , а через
у все элементы с, такие что .
Следовательно,
, .
По
определению декартового произведения множеств
(1)
б)
Рассмотрим выражение .
По
определению декартового произведения множеств
;
.
Тогда
состоит из множества всех упорядоченных пар <a, c>,
<b, c> таких, что 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.
Множество
А - решетка, в которой можно выделить две цепи. Для цепи 261224
отображение f сохраняет порядок, так как 151030, т.е
f(2) f(6) f(12)
f(24). Для цепи 361224
отображение f также сохраняет порядок, так как 151030, т.е. f(3) f(6) f(12)
f(24). Следовательно, отображение изотонно. Отображение
также является изоморфизмом, так как обратное отображение f сохраняет порядок:
для значений f(2) f(3)
(1=1) прообразы 2 и 3 сравнимы.
Следовательно,
отображение f изотонно и является изоморфизмом.
Вопрос
5.
Проверить
полноту системы функций
Решение:
Согласно теореме Поста, для полноты системы функций
необходимо и достаточно, чтобы в нее входили хотя бы одна немонотонная, хотя бы
одна нелинейная, хотя бы одна несамодвойственная, хотя бы одна не сохраняющая нуль
и хотя бы одна не сохраняющая единицу функции. Обозначим:
Т0 - класс функций, сохраняющих 0;
T1 - класс функций, сохраняющих 1;
S - класс самодвойственных функций;
М - класс монотонных функций;
Для исследуемой системы составим таблицу Поста. Если
функция входит в функционально замкнутый класс, то в таблице Поста в
соответствующей ячейке ставится знак «+», иначе - знак «-».
Для
исследования системы на полноту построим таблицы
истинности
функций.
.
Обозначим .
y
|
x
|
f1(x,y)
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
Функция f(x) не сохраняет 0 и 1, так как на
нулевом наборе она принимает значение 1, а на единичном - 0. Очевидно, что
данная функция немонотонна. Функция самодвойственна, так как на противоположных
наборах функция принимает противоположные значения.
Для
проверки линейности построим канонический полином Жегалкина: . Функция нелинейна, т.к. содержит элемент ху.
.
Обозначим .
y
|
x
|
f2(х,у)
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
По таблице истинности видим, что f2(х,у) не сохраняет 0 и сохраняет 1.
Эта функция монотонна, так как набор (0,0) предшествует набору (1,0), f2(0,0) >f2(1,0).На противоположных наборах (0,0) и (1,1) функция
принимает одинаковые значения 0, следовательно, она несамодвойственна.
Функция линейна.
. Построим таблицу Поста для заданной системы.
|
T0
|
T1
|
S
|
M
|
L
|
→
|
-
|
+
|
-
|
-
|
-
|
---++
|
|
|
|
|
|
Система
функций будет полна, если в каждом столбце таблицы Поста стоит хотя бы один
знак «-». Система функций полна.
Вопрос 6
Определить,
является ли формула тавтологией?
Решение.
Построим
таблицу истинности.
отображение функция триггер автомат
A
|
B
|
|
|
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
Формула является тавтологией, так как не существует интерпретации, на
которой она принимает ложное значение.
Формула является тавтологией.
Вопрос 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
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
2
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
3
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
4
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
5
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
6
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
7
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
8
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
9
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
a
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
b
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
c
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
d
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
E
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
F
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
Для
сегмента a: .
Логическая
схема управления для сегмента a.
Вопрос
8
Используя
канонический метод структурного синтеза конечных автоматов построить логическую
схему однотактного JK триггера на заданном элементе памяти - T
триггере.
Обобщённые
схемы структурного автомата:
=λ(qt;xt), qt+1=δ(qt;xt), Tt=f(qt;xt).
xt
|
qt
|
Yt(λ)
|
Tt(f)
|
qt+1(δ)
|
J
|
K
|
Q
|
Y
|
T
|
Qt+1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
=Q
Логическая схема:
Литература
Таран Т.А.,
Мыценко Н.А., Темникова Е.Л. Сборник задач по дискретной математике. / 2-е
изд., перераб. и доп. - К.: Инрес, 2005. - 64 с.