Задача 14. Можно ли нарисовать картинки, не отрывая карандаша от бумаги и проводя каждую линию ровно один раз? Какие из них являются эйлеровыми графами?

0) 1) 2)

3) 4) 5)

6) 7)

8) 9)

Задача 15. Приведите к предваренной нормальной форме следующие формулы логики предикатов:

0)

Ø"y "x U(y, x) & $x "y R(y, x) ;

"y $x T(y, x) É "y "x Q(y, x);

1)

"y ($x "y G(y, x) Ú "s $x N(y, x, s)) ;

$y "x $z H(x, y, z) É $y $x G(y, x) ;

2)

Ø"y $x K(y, x) Ú $z $y "x Q(y, x, z) ;

"x $y A(x, y) É $y Ø "x R(y, x) ;

3)

$y "m U(y, m) & "x "y Q(y, x);

"z $x T(z, x) É "y $x U(y, x) ;

4)

$x "y T(y, x) Ú "y "x H(y, x) ;

"x Ø"y A(x, y) É $y "z T(y, z) ;

5)

$n "y "x P(n, y, x) & "y Ø$n A(n, y) ;

$n "y "x P(n, y, x) É "y Ø$n A(n, y) ;

6)

"z $x T(z, x) Ú "y $x U(y, x) ;

$x "y T(y, x) É "y "x H(y, x) ;

7)

"x Ø"y A(x, y) Ú $y "z T(y, z) ;

"x (Ø($y A(x, y) É $y P(y, x))) ;

8)

"y "z U(y, z) & "x $y P(y, x);

"y "z A(y, z) É $y "z P(y, z) ;

9)

$y "x $z H(x, y, z) Ú $y "x G(y, x);

"y Ø$x H(y, x) É "x "y P(y, x);

Автоматы.

Задачи синтеза автоматов

Задача 16. Постройте конечный автомат, выдающий на выходе символ “!”, всякий раз, когда во входной двоичной последовательности встречается:

0)последовательность 0000;

1)последовательность 1111;

2)последовательность 0110;

3)последовательность 0111;

4)последовательность 1000;

5)последовательность 0011;

6)последовательность 0010;

7)последовательность 1110;

8)последовательность 0001;

9)последовательность 1100.

Задача 17. Постройте конечный автомат таблично, складывающий:

0)четные натуральные числа в D₅; 1)нечетные натуральные числа в D₈;

2)натуральные числа в D₄; 3)нечетные натуральные числа в D₆;

4)четные натуральные числа в D₆; 5)нечетные натуральные числа в D₅;

6)четные натуральные числа в D₇; 7)натуральные числа в D₃;

8)четные натуральные числа в D₈; 9)нечетные натуральные числа в D₇

Рекомендуемая литература

1. Акимов О.Е. Дискретная математика: логика, группы, графы.- М: Лаборатория Базовых Знаний, 2003 2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики - М.: Наука, 2003. 3. Горбатов В.А. Фундаментальные основы дискретной математики: информатика и математика.- М: Наука. Изд.фирма «Физ.-мат.лит», 2001 4. Гульден Я., Джексон Д. "Перечислительная комбинаторика", - М.: Наука, 2004. 5. Иванов Б.Н. Дискретная математика: алгоритмы и программы. Лаборатория Базовых Знаний, 2003 6. Карпов В.Г., Мощенский В.А. Математическая логика и дискретная математика. – Минск: Вышэйш. школа, 2001

7. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.:Энергоатомиздат, 2001 8. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 2001 9. Липский В. Комбинаторика для программистов. – М.: Мир, 2004.

10. Лорьер Ж.Л. Системы искусственного интеллекта. – М.: Мир, 2001. 11. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 2002. 12. Новиков Ф. Дискретная математика для программистов. - СПб: Питер, 2000 13. Оре О. Теория графов. – М.: Наука, 2001. 14. Риордан Дж. "Введение в комбинаторный анализ", - М.: ИЛ. 2003. 15. Романовский И.В. Дискретный анализ. – СПб: Невский диалект, 2003 16. Фляйшнер Г. Эйлеровы графы и смежные вопросы – М.: Мир, 2002

⇐ Назад
12