Реферат: Математическая Логика

притом ,если f не определена, то и программа не должна ничего выдавать.

притом ,если f не определена, то и программа не должна ничего выдавать.

(, а числа представляются в виде ,например .)

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

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

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

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

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

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

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

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

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

МТ-П:

НАМ:

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

Команда МТП:

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

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

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

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

Пример :

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

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

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

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