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

Министерство образования Республики Беларусь

Министерство образования и науки Российской Федерации

ГУВПО «Белорусско-Российский университет»

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

Задание №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 - класс самодвойственных функций;

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

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

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

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

. Обозначим .

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

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

. Обозначим .

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

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

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

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

Вопрос 6

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

Решение.

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

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

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

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

Вопрос 7

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

Решение:

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

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

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

Вопрос 8

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

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

=λ(qt;xt), qt+1=δ(qt;xt), Tt=f(qt;xt).

=Q

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

Литература

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