Математическая логика и теория алгоритмов

1. Математическая логика и теория алгоритмов

Доцент каф. АОИ, к.т.н. Перемитина Татьяна Олеговна
[email protected]
Математическая логика
и теория алгоритмов
Теория алгоритмов

2. Булевы функции

1) Определение понятия «алгоритм».
2) Характерные черты алгоритма.
3) Основная задача теории алгоритмов .
4) Существующие подходы к
формализации определения алгоритма.
5) Машина Тьюринга.
6) Повторение пройденного материала.
2

3. Определение понятия «алгоритм»

Современное формальное определение
вычислительного алгоритма было дано в
30-50-е годы XX века в работах
Тьюринга, Поста, Чёрча, Маркова.
Само слово «алгоритм» происходит от
имени арабского учёного Абу Абдуллах
Мухаммеда ибн Муса аль-Хорезми.
Алгоритм – это общий, единообразный, точно
установленный способ решения любой задачи из данной
массовой проблемы.
3

4.

Характерные черты
алгоритма
• Дискретность.
• Детерминированность.
• Элементарность шагов.
• Массовость.
• Результативность.
Общая Теория алгоритмов занимается проблемой
эффективной вычислимости.
4

5. Уточнение понятия алгоритма

• Уточнение понятия эффективно
вычислимой функции (Черч, Гедель).
• Машинная арифметика (Тьюринг).
• Нормальные алгоритмы (Марков).
5

6. Алгоритмическая вычислимость

Под задачейбудем понимать:
f :{0,1}* {0,1}*
Какие задачи м ожно решит ьалгорит м ич
ески,
а какие нет ?
х f ( x)
алгоритм
6

7.

Постановка задачи
f(x)
Вычислимые
Эффективно
вычислимые
Невычислимые
Другие виды
вычислимых
функций
7

8. Рекурсивные функции

Функция y f ( x1 , x2 ,.., xn ) называется
эффективно вычислимой если существует
алгоритм, позволяющий вычислять ее
значения
O ( x) 0;
( x) x 1;
m
I n ( x1, x2 ,....,xn ) xm , 1 m n
8

9.

Тезис Черча
f (0, x) ( x),
f ( y 1, x) ( y, f ( y, x), x).
Класс алгоритмически вычислимых функций
совпадает с классом всех частично рекурсивных
функций.
9

10. Машинная арифметика

Машина Тьюринга
10

11. Машина Тьюринга

1. Внешний
алфавит
A a0 , a1 ,..., an
11

12. Машина Тьюринга

2. Внутренний
алфавит
,..., q ,
q , q (память)
Q
R
,
L
,
C
,
...
0
1
m
12

13. Машина Тьюринга

3. Бесконечная
лента
13

14. Машина Тьюринга

4. Считывающее
устройство
14

15. Функциональная схема

C
ai q j al L qs
R
15

16. Пример 1

a0a2a1a0
16

17. Решение

Ответ: слово а2а1 преобразовано в слово а2а1а1, следовательно
данная машина применима к исходной информации.
17

18. Задача 1

a0a1a1a0
18

19. Решение

Ответ: слово а1а1 преобразовано в слово а1а1а1, следовательно
данная машина применима к исходной информации.
19

20. Алгебра Жегалкина

Закон коммутативности:
x y y x
Закон дистрибутивности:
x y z xy xz
1
Законы ассоциативности:
x y z x y z
x y z x y z
x x 0; х 0 х; х 1 х.
20

21. Пример 2

f ( x, y) х у
Представьте данную булеву функцию в
виде полинома Жегалкина
f ( x, y) ( х y) (( x 1) ( y 1) 1)
(( х y x y 1) 1)
( х y x y) 1 1
х y x y.
Ответ: f ( x, y) х y x y.
21

22. Решение

Представьте данную булеву функцию в
виде полинома Жегалкина: f ( x, y) х у
22

23. Пример 3

Представьте данную булеву функцию в
виде полинома Жегалкина: f ( x, y) х у
Задача 2
Представьте данную булеву функцию в виде
полинома Жегалкина:
f ( x, y) х у 23

24. Решение

Представьте данную булеву функцию в
виде полинома Жегалкина: f ( x, y) х у
24

25. Пример 4

f ( x, y) х у
Для данной булевой функции
определить минимальную ДНФ.
¬x
f ( x, y) х у
y 0
1
0
1
1
1
0
1
x
y
25

26. Пример 5

f ( x, y) х у
Для булевой функции
определить минимальную ДНФ; СДНФ, СКНФ; построить
полином Жегалкина и логическую схему.
¬x &¬ у
y 0
1
0
1
0
1
0
1
x
x&y
26

27.

СДНФ и СКНФ
27

28. Полином Жегалкина

28

29.

Логическая схема
f ( x, y) х у ( x y) ( x y)
29

30. Спасибо за внимание!

30