Эквивалентность трех подходов к понятию алгоритм

1.2 Эквивалентность трех подходов к понятию алгоритм.

1.2.1 Теорема об эквивалентности понятия вычислимой функции.

вычислима: ()

1)    Если существует программа МНР, которая вычисляет эту функцию.

2)    Если существует программа МТ-П, которая вычисляет эту функцию.

3)    Если существует программа НАМ, которая вычисляет эту функцию.

Использование НАМ:  

Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.

 Пусть  которая вычисляется на МТ-П, вычислим её на НАМ.

НАМ:

Команда МТП:  преобразуется по правилам:

Команда МТП:  

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

2.1 Основные определения

2.1.1 Декартово произведение

 - мн-во всевозможных упорядоченных пар элементов из А и В.

Пример:

2.1.2 Декартова степень произвольного множества.

Опр:  - множество всевозможных упорядоченных наборов длины n , элементов множества А.

2.1.3 Определение булевой функции от n переменных.

Любое отображение  - называется булевой функцией от n переменных, притом множество

2.1.4 Примеры булевой функции.

1)      логическая сумма (дизъюнкция).

2)     логическое умножение (конъюнкция).

3)     сложение по модулю два.

4)     логическое следствие (импликация).

5)     отрицание.

2.1.5 Основные булевы тождества.

1)    (ассоциативность)

2)    (коммутативность)

3)    (свойство нуля)

4)    (закон поглощения для 1)

5)    (ассоциативность)

6)    (коммутативность)

7)    (свойство нуля по умножению)

8)    (свойство нейтральности 1 по умножению)

9)    (дистрибутивность)

10)  (дистрибутивность 2)

11)  (закон поглощения)

12)  ( Законы

13)   де Моргана)

14)  (закон снятия двойного отрицания)

15)  (tertium non datur – третьего не дано)

16)  (ассоциативность)

17) 

18) 

19) 

20) 

21)   (Свойства

22)  идемпотентности)

2.2 Дизъюнктивные нормальные формы.

2.2.1 Основные определения.

 - конечный алфавит из переменных.

Рассмотрим слово:

Экспоненциальные обозначения:

 - элемент конъюнкции.

S – длина элемента конъюнкции.

ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.

Любая булева функция может быть представлена как ДНФ