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

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

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

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

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


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

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

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

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

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

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

. Обозначим .


yxf1(x,y)001011100111

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

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

. Обозначим .


yxf2(х,у)000011101110

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

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

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


T0T1SML?-+------++

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


Вопрос 6


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

Решение.

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

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

AB00001011111011111111

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

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


Вопрос 7


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

Решение:


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

x1x2x3x4abcdefg000001111110100010110000200101101101300111111001401000110011501011011011601101011111701111110000810001111111910011111011a10101111101b10110011111c11001001110d11010111101E11101001111F11111000111

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


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


Вопрос 8


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


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

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


xtqtYt(?)Tt(f)qt+1(?)JKQYTQt+1000000100011010000110011001101101101011110111110

=Q



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


Литература


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


Теги: Основы дискретной математики  Контрольная работа  Математика
Просмотров: 39827
Найти в Wikkipedia статьи с фразой: Основы дискретной математики
Назад