Материал: Основы дискретной математики
Основы дискретной математики
Министерство образования Республики Беларусь
Министерство образования и науки Российской Федерации
ГУВПО «Белорусско-Российский университет»
Кафедра «Автоматизированные системы
управления»
Задание №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.
Множество
А - решетка, в которой можно выделить две цепи. Для цепи 2
61224
отображение 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 |