Контрольная работа - файл n1.doc

Контрольная работа
скачать (93.5 kb.)
Доступные файлы (1):

543kb.

25.05.2007 13:51

n1.doc

Федеральное агентство по образованию

Пермский государственный технический университет

Кафедра информационных технологий и автоматизированных систем

Контрольная работа

по дисциплине

ДИСКРЕТНАЯ МАТЕМАТИКА

Вариант №3

Выполнил:студентгр.АСУз-05-1уск

Мартемьянов С.Н.

Проверил: Файзрахманов Р.А.

Пермь 2007

1. Множества

8.2 Доказать равенство множеств, преобразуя множества к одинаковому виду с помощью основных законов алгебры множеств.

Применим дистрибутивный закон

По закону исключения третьего

По закону идемпотентности пересечение множества с общим множеством дает это же множество

8.3

9.1

9.2

Применим ассоциативный закон

2.Графики, соответствия, отношения

21.а Какими свойствами обладает отношение «Быть братом» на множестве людей?

Отношение обладает свойством рефлективности.

21.б Быть подмножеством на семействе множеств?

Отношение обладает свойством антирефлективности.

23. Придумать содержательный пример соответствия, которое обладает указанными свойствами и объяснить (табл.2).

Таблица 2

Вариан- ты	Функциональное	Нефункцинальное	Инъективное	Неинъективное	Всюду определенное	Не всюду опреде ленное	Сюръективное	Несюръективное
а	+							+
н	+			+

И П

К1 К2

Рис.1 Рис.2

А) Есть три вида шоколада. Покупатель1 купил первый, покупатель2 купил второй. Третий остался. (рис.1)
н) Иванову и Петрову пришли приглашения из двух кадровых агенств. Оба обратились в первое. (рис.2)

Найти максимальные, минимальные, наибольшие и наименьшие элементы, а также Sup В и Inf В для множеств, представленных на рис.25.

а б в

а) Максимальные элементы {2,4,6}, минимальные {1,3,5,7}, SupB = 4.

б) Максимальные элементы {1,2}, минимальные {5,6}

в) Наибольший элемент {3}, максимальный {3}, минимальные {10,8,9,1,5}, SupB = 3

32. Доказать:

32.2. В решетке любой максимальный элемент является наибольшим, а любой минимальный – наименьшим.

Пусть х1

A наибольший элемент, а х2

A максимальный. Тогда а

А <x1 и а

А<=x2. Т.к . не может быть а = х1, то х2=х1.

34. Являются ли множества, представленные диаграммами Хассе (рис.26):

а) решетками;

А) б) в)
4. Логика высказываний.

1. Записать в символической форме следующие сложные высказывания:

ж) Этот человек студент или предприниматель

А – Человек

В – Студент

С – Предприниматель

АВvАС

з) Петров женат на Марье Ивановне или Лукерии Ильиничне

А – Петров

В – Марья Ивановна

С – Лукерия Ильиничга

АВvАС

и) Если при выполнении программы отклонение контролируемых параметров превышает предусмотренные нормы (стандарты), то требуется оперативная корректировка программы или уточнение стандартов

А – Отклонение

В – Норма

С – корректровка программы

Д – уточнение стандартов

(А>В)  (СvД)

к) Если Иванов Гражданин России, и все граждане Росси имеют право на образование, то Иванов имеет право на образование. Найти отрицание полученного высказывания.

А – Иванов

В – Гражданин России

С – Право на образование

 (АВ С)

Построить таблицы истинности для формул:

А	В
0	0	1	1	0
0	1	1	1	0
1	0	0	0	1
1	1	0	0	1

Получить ДНФ для формул:

к)

Получить СДНФ для формул:

Получить СДНФ, а затем перейти к СКНФ

≡

.

СКНФ - ≡ ≡ ≡ ≡ ≡

≡

.
5. Предикаты

25. Записать на языке предикатов:

а) все студенты учатся;

x R(x)

б) некоторые студенты отличники;

x ( C(x) & O(x) )

27. Записать на языке предикатов:

а) детям до 16 лет (D(x)) и роботам (R(x)) входить (B(x)) запрещено;

(D(x)→ B(x))( R(x)→ B(x))

б) всем детям до 16 лет (D(x)) и роботом (R(x)) надлежит получить справки (C(x)).

(xD(x)→ C(x))( xR(x)→ C(x))

28. Записать на языке предикатов:

а) всякое N , делящееся на 12, делится на 2, 4 и 6;

L(x,y) N делится на 12

P(x,y) N делится на 2,4,6

xL(x,y) →P(x,y)

6. Автоматы

1.Построить (синтезировать) автомат по содержательному описанию.

1.10. Автомат выдает сигнал 1, если на вход поступит слово МАМА, сигнал 2, если поступит слово МАМАЛЫГА, и 0 во всех остальных случаях. Слова отделяются друг от друга пробелами.

	Q0	Q1	Q2
мама	0	0	0
лыга	0	0	0
« «	0	1	2
Х	0	0	0

«х«/0

	Q0	Q1	Q2
мама	Q1	Q0	Q0
лыга	Q0	Q2	Q0
« «	Q0	Q0	Q0
Х	Q0	Q0	Q0

Преобразовать автомат Мили в автомат Мура:

	b₁	b₂	b₃
1	A	A	Б
2	Б	Б	А

	b₁	b₂	b₃
1	b₁	b₂	b₂
2	b₃	b₃	b₃

6. Преобразовать автомат Мили в автомат Мура, затем перейти от автомата Мура к автомату Мили и, используя минимизацию, получить исходный автомат Мили.
Таблица 28 Таблица 29

	q₁	q₂
x₁	y₂	y₂
x₂	y₁	y₁

	q₁	q₂
x₁	q₁	q₂
x₂	q₂	q₁

Минимизировать автомат Мура.

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

y₁

y₂

y₁

y₂

x₁

x₂

	1		2
	2		3
	4		7
1		2
2		3
4		7

	y₁	y₂	y₂	y₂	y₁	y₂	y₂
	1	2	3	4	5	6	7
x₁	2	3	7	3	4	7	3
x₂	4	7	7	3	6	7	3

Контрольная работа - файл n1.doc

n1.doc

Таблица 2

Вариан- ты