Файл: Matlog.doc

Начальное и конечное состояния ленты для случая a = 2, b = 3 представлено на рис. 5.6 a) и b)

a)

1

1



1

1

1

b)

1

1

1

1

1

Рис. 5.6

5.3. Вычислимые по Тьюрингу функции

Будем рассматривать функции f от одной или нескольких переменных, заданных на множестве N = {0, 1, 2, …, n, …} натуральных чисел или его подмножествах (частичные функции) и принимающие значения на множестве N.

Определение 5.8. Функция f(x₁, x₂, …, x_n) называется вычислимой, если существует алгоритм, позволяющий вычислять ее значения для тех переменных, для которых она определена, и работающий бесконечно, если функция для данного набора переменных не определена.

Определение 5.9. Функция f(x₁, x₂, …, x_n) называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая эту функцию.

Переменные можно располагать в виде слов с разделителями

11…1 11…1……11…1

Пример 5.9.

Запись 111 111 соответствует трем переменным x₁, x₂, x₃, равным, соответственно, 3, 2 и 1

Функция также записывается словом, состоящим из единиц.

Пример 5.8 представляет функцию двух переменных f(a, b) = a + b.

Тезис Тьюринга. Всякий алгоритм можно реализовать машиной Тьюринга.

Тезис Тьюринга доказать нельзя. Это утверждение означает, что математическое понятие вычислимой по Тьюрингу функции является идеальной моделью интуитивного понятия алгоритма. Этот тезис подтверждается опытом. По своему характеру тезис Тьюринга напоминает математические законы механики, которые точно так же не могут быть доказаны, но, открытые Ньютоном, многократно подтверждены опытом. В силу тезиса Тьюринга невозможность построения машины Тьюринга означает отсутствие алгоритма решения данной проблемы.

Изучение машин Тьюринга закладывает фундамент алгоритмического мышления, сущность которого состоит в том, что нужно уметь разделять процесс вычисления на простые составляющие шаги. В машине Тьюринга такое разделение доведено до предельной простоты. В современной ЭВМ алгоритмический процесс разделяется не на столь мелкие составляющие, как в машине Тьюринга. Наоборот, есть стремление укрупнить выполняемые машиной процедуры. Например, операция сложения в машине Тьюринга – целая программа, а в ЭВМ это простейшая функция.

Ответы на контрольные вопросы

Тема 1

1. а) конъюнкция; б) эквивалентность; в) дизъюнкция; г) импликация.

2. б).

3. а), г).

Тема 2.

1. б), в).

2. а) конъюнкция: б) дизъюнкция.

3. а), в), д), е).

4. б) – приведенная, в) – нормальная.

Указания к выполнению лабораторных работ

Лабораторные работы проводятся с помощью системы компьютерного тестирования «КОБРА» (лабораторные работы 1 – 3) и компьютерного интерпретатора машины Тьюринга «АЛГО» (лабораторная работа 4).

Лабораторная работа №1. Логика высказываний

Для выполнения этой работы требуется изучить следующие разделы логики высказываний:

1. Определение высказывания

2. Операции над высказываниями

3. Формулы логики высказываний

4. Равносильность формул

5. Запись сложного высказывания в виде формулы логики высказываний

6. Тождественно-истинные, тождественно-ложные и выполнимые формулы

7.Формализация рассуждений

8. Правильные рассуждения

Лабораторная работа №2. Логика предикатов

Для выполнения этой работы требуется изучить следующие разделы логики предикатов:

1. Определение предиката

2. Кванторы.

3. Формулы логики предикатов

4. Равносильность формул

5 Приведенные и нормальные формулы

6. Выражение суждения в виде формулы логики предикатов

7. Интерпретация формулы логики предикатов в виде суждения

8. Выполнимость. Общезначимость

Лабораторная работа №3. Формальные аксиоматические теории (исчисления). Нечеткая логика

Для выполнения этой работы требуется изучить следующие разделы исчисления высказываний, исчисления предикатов и нечеткой логики:

1. Принципы построения формальных теорий

2. Вывод в исчислении высказываний

3. Вывод в исчислении предикатов

4. Метод резолюций.

5. Нечеткие множества

6. Нечеткие высказывания

7. Нечеткие предикаты

Лабораторная работа №4. Машина Тьюринга

Эта лабораторная работа рассчитана на использование программной системы – интерпретатора машины Тьюринга. Порядок действий при этом следующий. Чтобы приступить к выполнению работы необходимо запустить систему с помощью кнопки «Алго»; выбрать в главном меню пункт "Интерпретатор"; затем выбрать пункт "Машина Тьюринга". Вся информация о работе с системой может быть получена нажатием кнопки «Помощь».

Контрольные задания по курсу "Математическая логика и теория алгоритмов"

1. Раздел «Логика высказываний»

Задание

1. Установить, является ли данная формула тождественно-истинной.

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

3. Установить, является ли данное рассуждение правильным, (проверить, следует ли заключение из конъюнкции посылок).

Варианты индивидуальных заданий

Вариант №1

1. (P  Q)  ((Q  R)  (P  R)).

2. Он и жнец, и швец, и на дуде игрец.

3. Если человек принял какое-то решение, и он правильно воспитан, то он преодолеет все конкурирующие желания. Человек принял решение, но не преодолел конкурирующих желаний. Следовательно, он неправильно воспитан.

Вариант №2

1. (P  Q)  ((P  (Q  R))  (P  R)).

2. Идет дождь, и идет снег.

3. Если данное явление психическое, то оно обусловлено внешним воздействием на организм. Если оно физиологическое, то оно тоже обусловлено внешним воздействием на организм. Данное явление не психическое и не физиологическое. Следовательно, оно не обусловлено внешним воздействием на организм.

Вариант №3

1. (P  R)  ((Q  R)  ((P  Q)  R)).

2. Он хороший студент или хороший спортсмен.

3. Если подозреваемый совершил кражу, то, либо она была тщательно подготовлена, либо он имел соучастников. Если бы кража была тщательно подготовлена, то, если бы были соучастники, украдено было бы много. Украдено мало. Значит, подозреваемый невиновен.

Вариант №4

1. (Q  R)  ((P  Q)  (P  R)).

2. Если стальное колесо нагреть, то его диаметр увеличится.

3. Если курс ценных бумаг растет, или процентная ставка снижается, то падает курс акций. Если процентная ставка снижается, то либо курс акций не падает, либо курс ценных бумаг не растет. Курс акций понижается. Следовательно, снижается процентная ставка.

Вариант № 5

1. ((Q  (R  P))  (R & (P  Q)))  R .

2. Если воду охлаждать, то объем ее будет уменьшаться.

3. Либо свидетель не был запуган, либо, если Генри покончил жизнь самоубийством, то записка была найдена. Если свидетель был запуган, то Генри не покончил жизнь самоубийством. Записка была найдена. Следовательно, Генри покончил жизнь самоубийством.