БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976.

2. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. – М.: Наука, 1997.

3. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1997.

4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1998.

5. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории автоматов. – М.: Наука, 1975.

6. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986.

 

КОНТРОЛЬНАЯ РАБОТА

 

Во всех задачах через N обозначен номер варианта. Другие данные для каждого варианта приведены в таблицах 1, 2, 3 приложения.

Задача 1. В табл. 1 прил. даны две формулы алгебры логики . Определить, эквивалентны ли эти формулы. Для решения задачи необходимо по формулам построить таблицы значений функций, реализованных этими формулами, и сравнить их.

Задача 2. В табл. 1 прил. даны две функции алгебры логики . Определить полноту данной системы функций. Для решения этой задачи необходимо для каждой функции проверить принадлежность её
к классам . Построить таблицу определения полноты системы и заполнить её. Если функция принадлежит какому-либо из указанных
классов, то в соответствующей клетке таблице ставим 1, в противном случае ставим 0:

	0	1	1	0	0
	1	0	0	1	1

 

Задача 3. В табл. 1 прил. даны две функции алгебры логики . Для функции  построить СДНФ, а для функции  построить СКНФ.

Примечание. Пусть функция  задана таблицей, где .

x1	x2	x3	f
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

 

В задачах 2-3 эта функция записана в строку: .

Задача 4. Пусть универсальное множество W состоит из всех десятичных цифр: .

Будем считать, что порядок перечисления цифр зафиксирован, т.е. «0» ‑ первая цифра,…, «9» ‑ десятая цифра.

Даны числа u и v (см. табл. 2 прил.). Обозначим через U
(через V) множество цифр, встречающихся в записи числа u (числа v).

Задание:

а) выписать множества U и V;

б) выписать булевы векторы ;

в) вычислить и выписать булевы векторы , где  – дополнение множества U (множества V) в универсальном множестве W, т.е. , ;

г) выписать множества , используя полученные характеристические векторы .

Задача 5. Пусть квадратные булевы матрицы  и , , заданы условиями:

где  – остаток от деления числа N на 5.

Пусть M={1, 2, 3, 4, 5, 6}. Будем считать, что матрицы А и В являются характеристическими матрицами бинарных отношений  и , т.е.

, .

Задание:

а) выписать матрицы А и В;

б) выписать в явном виде отношения a и b и нарисовать графы G(a) и G(b);

в) вычислить и выписать в явном виде отношения:

, , , , , . Для каждого из этих отношений выписать характеристическую матрицу и нарисовать соответствующий граф;

г) вычислить произведения матриц АВ и ВА. Используя полученные матрицы, выписать в явном виде отношения  и  и нарисовать соответствующие им графы;

д) для каждого из отношений ,  указать, каким из следующих свойств они удовлетворяют: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, полнота.

Задача 6. Числа s, t, l заданы в табл. 2 прил.

Определим множество , где N={1, 2, 3,…} – множество натуральных чисел, и зададим на А отношение эквивалентности e, положив  тогда и только тогда, когда числа a и b дают одинаковые остатки при делении на l.

Задание:

а) выписать в явном виде множество А;

б) выписать остатки, которые могут получиться при делении натуральных чисел на число l;

в) вычислить разбиение П(e) множества А, отвечающее эквивалентности e. Для каждого блока разбиения П(e) указать соответствующий ему остаток.

Задача 7. Число p задано в табл. 2 прил.

Определим множество  и зададим на  отношение делимости (без остатка) |, положив a|b тогда и только тогда, когда b делится на a без остатка (запись «a|b» читается «a делит b»).

Задание:

а) выписать в явном виде ;

б) построить диаграмму упорядоченного множества ;

Задача 8. Запись  ( ) означает, что нужно положить число a равным остатку от деления числа b на число n.

Через  обозначается целая часть числа a, т.е. наибольшее целое число, не превосходящее a.

Число n задано в табл. 3 прил.

Рассмотрим автомат , где , , а функции  и  определяются так:

для всех  и

, где  ( )

, где  (mod 2).

Задание:

а) выписать множество ;

б) выписать таблицы для функций d и l;

в) изобразить диаграмму автомата A;

г) вычислить  и  для всех слов p, указанных в табл. 3 прил.;

д) минимизировать автомат A. Для полученного минимального автомата B:

– выписать множества состояний, входных и выходных сигналов;

– выписать таблицы, задающие функции переходов и выходов автомата B;

– изобразить диаграмму автомата B.

 

 

ПРИЛОЖЕНИЕ

 

Таблица 1

 

N
1	(xÅ(y&z))	((x&y) Å(x&z))	0011 1111	1111 0000
2	(x®(y|z))	((x|y) ® (x|z))	0101 1111	1100 1100
3	(xÅ(y¯z))	((x¯y)Å(x¯z))	0111 0111	1010 1010
4	(xÚ(y|z))	((x|z) Ú (x|z))	0000 0011	1010 1010
5	(x& (y z))	((x y)&(x z))	0000 0101	1100 1100
6	(x« (y«z))	((xÅy)«(xÅz))	0001 0001	1111 0000
7	(x¯ (yÚz))	((xÚy) ¯ (xÚz))	1100 0000	1110 0001
8	(x¯ (y¯z))	((x|y) ¯ (x|z))	1010 0000	1011 1101
9	(x| (y®z))	(x® (y®z))	1000 1000	0111 0001
10	(x| (y¯z))	((xÅy) Ú (xÅz))	1111 1100	1100 0000
11	(xÅ (y&z))	((x®y) ® (x¯z))	1111 1010	1010 0000
12	(xÅ (yÚz))	(x| (yÚz))	1110 1000	1000 1000
13	(xÚ (y|z))	((x|y) Ú (x|z))	1101 1101	1010 1010
14	(x& (y®z))	((x& y)®z)	0001 0010	0011 0100
15	(x& (yÅz))	((x&y) Å (x&z))	0010 0011	0100 0101
16	(x (yÅz))	((xÅ y)z)	0011 0100	0101 0110
17	(xÚ (y¯z))	((xÚ y)¯z)	0100 0110	0011 0101
18	(x¯ (y&z))	((x¯ y)Úz)	0110 1000	0101 0111
19	(x| (y&z))	((x| y)&z)	1000 1001	0111 0011
20	(x| (y¯z))	((x&y) ® (xÚz))	1010 1100	1001 1011
21	(x® (y®z))	((x®y) ® (x®z))	1100 1110	1011 1111
22	(xÅ (y®z))	((xÅy) ® (xÅz))	0000 1111	1000 0111
23	(x® (y&z))	((x®y) & (x®z))	0001 1110	1001 0001
24	(x® (yÚz))	((x®y) Ú (x®z))	0010 1101	1010 0101
25	(x& (y«z))	((x&y) « (x&z))	0011 1100	1011 0100

 

Таблица 2

 

N	u, v	s	t	l	p
1	14586012	10	30	2	8
	23172800
2	12446211	15	42	4	12
	34282012
3	72411078	6	28	3	9
	15004871
4	52411247	12	35	11	13
	24007312
5	48164424	16	44	8	10
	34280012
6	5469289	11	50	10	14
	9271200
7	5400713	4	23	7	11
	2466732
8	24124832	13	52	15	15
	23147990
9	5112784	3	18	3	16
	2004241
10	4809092	7	20	5	23
	13132407
11	7428121	9	29	6	17
	2343972
12	488735	17	40	12	24
	645831
13	6242640	20	55	8	18
	7028951
14	6477287	42	70	5	25
	27913420
15	6121444	14	35	7	19
	3246002
16	3662813	18	41	13	26
	4856612
17	9025513	1	20	4	20
	4664231
18	4241239	9	49	7	27
	9132001
19	64422410	3	21	2	21
	2358553
20	542844	6	43	6	28
	9622405
21	5846462	8	19	3	22
	211115

 

Окончание табл. 2

N	u, v	s	t	l	p
22	9374647	14	44	4	29
	7111234
23	64124817	5	50	5	30
	75584113
24	1235600	19	65	16	32
	7200071
25	6959632	2	23	3	31
	78271218

Таблица 3

N	n	p
1	10	, , , ,
2	11	, , , ,
3	12	, , , ,
4	13	, , , ,
5	14	, , , ,
6	15	, , , ,
7	10	, , , ,
8	11	, , , ,
9	12	, , , ,
10	13	, , , ,
11	14	, , , ,
12	15	, , , ,
13	10	, , , ,
14	11	, , , ,
15	12	, , , ,
16	13	, , , ,
17	14	, , , ,
18	15	, , , ,
19	10	, , , ,
20	11	, , , ,
21	12	, , , ,
22	13	, , , ,
23	14	, , , ,
24	15	, , , ,
25	10	, , , ,