МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

для студентов факультета повышения квалификации

 

 

Москва 2016

План УМД 2015/2016 уч. г.

Методические указания

и контрольные задания

по курсу

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Составители: В.О. Мелихов, доцент

А.Н Кироев, аспирант.

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

Издание утверждено на заседании кафедры.

Отв.редактор В.Н.Шакин, доцент

Рецензент д.т.н. И.П Кузнецов.

Содержание

Введение.................................................................................................................................... 4

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

1.1. Понятие двоичной функции и способа ее задания.................................................... 6

1.2. Одноместные и двухместные двоичные функции..................................................... 7

1.3. Алгебра двоичных функций......................................................................................... 9

1.4. Совершенная дизъюнктивная нормальная форма.................................................... 11

1.5. Совершенная конъюнктивная нормальная форма.................................................... 12

1.6. Базисы функций алгебры логики............................................................................... 12

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

1.8. Существенные и несущественные переменные....................................................... 14

1.9. Минимизация функций алгебры логики................................................................... 15

1.9.1. Структурный метод карт Карно........................................................................... 15

1.9.2. Метод Блейка......................................................................................................... 18

2. Основы теории алгоритмов.............................................................................................. 22

2.1. Понятие алгоритма и связанных с ним категорий................................................... 22

2.2. Машина Тьюринга....................................................................................................... 22

2.3. Тезис Тьюринга............................................................................................................ 25

2.3.1. Композиция МТ..................................................................................................... 25

2.3.2. Разветвление МТ.................................................................................................... 25

2.4. Вычислительная сложность алгоритмических проблем.......................................... 26

Список рекомендуемой литературы.................................................................................... 28

Правило выбора варианта Контрольных работ и пример выполнения........................... 29

Контрольная работа................................................................................................................ 31

Введение

Целью данного курса является освоение теоретических основ таких разделов дискретной математики как Математическая логика и Теория алгоритмов. Курс " Математическая логика и Теория алгоритмов" посвящен изуче­нию элементов математического аппарата, предназначенного для описания дискретно изменяющихся величин, объектов, систем и процессов таких, например, как вычислительные системы и процессы. Изучение курса включает освоение фундаментальных понятий алгебры логики, теории формальных алгоритмов и вычислительной сложности.

В соответствии с содержанием курса данный сборник включает две части, посвященные соответственно изучению функций алгебры логики и теоретических основ формальных алгоритмов. Организация учебного материала, представленного в сборнике, полностью соответствует стандарту изложения математических дисциплин для инженерно-технических и вычислительных спе­циальностей и направлений подготовки. Объем учебных задач и требования к их выполнению позволяют получить необходимые практические навыки в работе с функциями алгебры логики, а также изучить свойства формальных алгоритмов.

Постановке контрольных заданий предшествует краткое изложение теоретического материала. По каждому из разделов приводятся ссылки на рекомендуемые для изучения литературные источники.

Изучение Математической логики в рамках дисциплины включает определение функций алгебры логики (ФАЛ) и способов их задания. Устанавливается связь ФАЛ с импульсными схемами. Учащиеся осваивают алгоритмы построения ФАЛ в виде совершенных формы и полинома Жегалкина. Определяется понятие базисного набора ФАЛ, доказывается эквивалентность базисов. Исследуется существенность двоичных переменных. Подробно рассматриваются вопросы структурной и аналитической минимизации ФАЛ.

На основе полученных представлений фундаментальное понятие алгоритма характеризуется с позиций теории формальных алгоритмических моделей и вычислительной сложности.

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

В результате освоения материалов курса студенты обучаются основным приемам представления и исследования функций алгебры логики приобретают практические навыки построения формальных алгоритмических моделей. Учащиеся должны уметь выделять основные элементы описания алгоритмической проблемы, правильно ориентироваться в вопросах вычислительной сложности алгоритмов.

Изучаемый курс закладывает математические основы, необходимые при освоении теории кодирования, теории автоматов, методов структурного синтеза импульсных устройств, а также методов автоматизации проектирования вычислительных систем

 

Студенты технических факультетов МТУСИ в течение третьего семестра выполняют одну контрольную работу, в которой должны быть выполнены задания 1-3 и сдают экзамен.

Бюджет времени (в часах)

Аудиторная работа	Самостоятельная работа
лекции	упражнения	итого	изучение курса	выполнение контрольных работ	итого

Рабочая программа

1. Функции алгебры логики (ФАЛ). Способы задания ФАЛ. Эквивалентность двух функций. Количество различных ФАЛ от n переменных.
2. Основные 2-местные и 1-местные функции алгебры логики. Связь ФАЛ с импульсными элементами.
3. Совершенная дизъюнктивная нормальная форма. Алгоритм построения.
4. Совершенная конъюнктивная нормальная форма. Алгоритм построения.
5. Полином Жегалкина. Алгоритм построения.
6. Базисные наборы функций алгебры логики. Эквивалентность басисов. Представление ФАЛ в различных базисах
7. Существенные и несущественные логические переменные. Процедура определения существенности.
8. Минимизация функций алгебры логики по Карно-Вейчу. Процедура минимизации.
9. Минимизация произвольной дизъюнктивной формы или произвольной конъюнктивной формы. Процедура минимизации.
10. Предикаты. Кванторы.
11. Понятие алгоритма и связанных с ним категорий
12. Машина Тьюринга (МТ). Операции над МТ.
13. Другие формальные системы описания алгоритма
14. Недетерминированная МТ
15. Размерность и трудоемкость задачи. Классы вычислительной сложности

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

1.1. Понятие двоичной функции и способа ее задания.

Математической логикой называется раздел математики занимающийся изучением общих законов построения и применения двоичных функций. Двоичной функцией от n - двоичных переменных называется функциональное всюду определенное и (как правило) всюду значимое соответствия вида

, где каждая из переменных , а также сама функция принимают значения издискретного множества В, состоящего всего из 2 элементов .

Совокупность переменных , получивших определенное значение, в математической логике принято называть набором. Учитывая, что каждая из переменных может принимать в наборе всего лишь одно значение (равное 0 либо 1) все возможные наборы , образующие область определения функции , легко могут быть перечислены. Такое перечисление обычно принято производить в естественном порядке. Например, в таблице 1, приведено в естественном порядке перечисление набров из 3-х переменных.

Ясно, что двоичная функция от n - переменных будет определена на наборах, т.к. каждому набору может быть однозначно сопоставлен его номер p в диапазоне от 0 до

Можно сказать, что набор переменных представляет свой номер в виде двоичного числа. А естественный порядок наборов соответствует расстановке наборов по возрастанию их номеров.

Таблица 1

р

 

Функциональность соответствия означает, что любому конкретному набору переменных будет соответствовать не более одного значения функции. Определение значений двоичной функции на наборах называется таблицей истинности функции.

Т.к. значениями могут быть опять таки 0 либо 1, то количество различных функций от n - переменных будет равно , где m – количество наборов, или, подставляя количество наборов -

Алгебра двоичных функций.

Название «логических» двоичные функции заслужили в связи с тем, что механизмы их преобразований отражают формальную логику человеческого мышления. Так, если предположить, что переменным двоичных функций (принимающим всего два значения) соответствуют утверждения, про которые можно оказать одно из двух: " это истина" или " это ложь", то на их основе с примением двоичных функций, выполняющим роль логических операций, можно построить более сложные утверждения.

Например,

- " утверждение Х" И " утверждение У" образуется операцией

- " утверждение Х" ИЛИ " утверждение У" образуется операцией

- " утверждение Х" ЭКВИВАЛЕНТНО " утверждению У" образуется операцией

- ИЗ " утверждения Х" СЛЕДУЕТ " утверждение У" образуется операцией

- " НЕ утверждение Х" образуется операцией ;

Двухместные и одноместные функции (операции) образуют Алгебру логических функций, что означает достаточность их совокупности для представления любой логической функции. Т.е. любая логическая функция от конечного числа логических переменных может быть представлена с помощью двухместных и одноместных функций в виде некоторого выражения и наоборот, любому правильно построенному из логических переменных и операций выражению будет отвечать некоторая логическая функция. При этом предполагается, что в правильно записанном выражении

1. операнды двухместных операций записываются слева и справа от знака операции,

2. операции выполняются таким образом, что

- первым производится – отрицание

- вторым – логическое произведение

- третьим – логическая сумма и все остальные операции в очередности их записи

3. очередность пункта 2 может быть изменена с помощью расстановки скобок причем количество открывающих скобок равно количеству закрывающих и скобки раскрываются в обычном порядке «от внутренних к наружным»

Пример 1. Построить таблицу истинности следующей двоичной функции.

р

 

Алгебру логических функций характеризуют законы

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

двойного отрицания

коммутатитвности

ассоциативности

дистрибутивности

де-Моргана (инверсии)

склеиванияи

поглощения

Совокупность приведенных законов легко может быть расширена новыми тождествами.

Две функции алгебры логики (ФАЛ) являются эквивалентными или тождественно равными, если равны их значения на соответствующих наборах. Например, нетрудно заметить, что

и т.д.

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

Пример 4

. Построить представление функции импликации во всевозможных базисах.

В избыточном базисе (А) в виде СДНФ, либо в виде СКНФ.

Для получения функции в базисе (Б) надо избавиться от операций дизъюнкции. Приэтом естественно исходить из представления, где употребление этой операции ниже, т.е. использовать СДНФ функции).

Для получения функции в базисе (В) надо избавиться от операций конъюнкции,. используяь СКНФ).

Исходя из вида функции в базисе (Б), получим ее вид в базисах (Г) и (Е)

А исходя из вида функции в базисе (В), получим ее вид в базисах (Д) и (Ж) |

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

Любую логическую функцию можно представить в виде полинома. Произведение, логических переменных называется монотонным, если оно содержит переменные без отрицаний. Сумма по модулю 2 попарно различных монотонных произведении называется полиномом Жегалкина (ПЖ):

Алгоритм построения полинома Жегалкина

Для произвольной логической функции от n - переменных:

1. записать в общем виде полином Жегалкина с неопределенными коэффициентами;

Например, для функции 2-х переменных общий вид полинома

2. решить систему.из линейных уравнений относительно неизвестных коэффициентов, образуемую путем подстановки значений функции на наборах таблицы истинности;

1. полученные значения коэффициентов подставить в полином.

Пример 5. Построить полином Жегалкина для функции из примера 1.

Общий вид полинома от 3-х переменных

 

Таким образом ПЖ

Заметим, что возможность представления любой функции в виде полинома Жегалкина указывает на базисность набора функций - «базис Жегалкина».

Метод Блейка

Метод Блейка аналитической минимизации функции, исходя из произвольной ДНФ. Минимизация осуществляется в 2 этапа

1) на первом этапа применяется ) закон обобщенного склеивания (до тех пор пока это возможно)

Здесь и далее - проиэвольные логические произведения;

2) на втором этапе применяется закон обобщенного поглощения (до тех пор пока это возможно)

Пример 7. Построить МДНФ для функции, заданной в виде произвольной ДНФ:

Метод Блейка аналитической минимизации функции, исходя из произвольной КНФ

1) на первом этапе раскрыть скобки, удаляя слагаемые вида и заменяя слагаемые ;

2) на втором этапе применяется закон обобщенного поглощения

Пример 8. Построить МДНФ для функции, заданной в виде произвольной КНФ

 

Основы теории алгоритмов

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

Одним из формальных методов представления алгоритмов является машина Тьюринга (МТ), которая включает следующие компоненты:

1. Устройство управления, имеющее одно из состояний множества

..Множество состояний всегда содержит состояние

, с которого МТ начинает работать, а также состояние , с наступлением которого работа МТ заканчивается;

1. Бесконечную ленту, разбитую на ячейки, в каждой из которых содержится один из символов адфавита .Любой алфавит МТ всегда содержит пустой символ _ - " пробел";
2. Считывающую/записывающую головку, которая в зависимости от текущего состояния устройства управления и от текущего символа на ленте под головкой может передвинуться на одну ячейку вдоль ленты направо ( R )., налево ( L ) или остаться на месте ( Е ), а также может записатьв соответствии с заданием в ячейку под собой любой символ из алфавита А.

Задание МТ образует совокупность продукций (команд) , означающих, что, если устройство управления МТ находится в состоянии , головка " обозревает" на ленте символ , то устройство управления переходит в состояние , головка МТ записывает в ячейку символ (возможно тот же, что и был ранее) и передвигается либо влево на один символ, либо вправо на один символ, либо остается на месте (рис. 4).

Рис: 4. Машина Тьюринга

 

Конфигурацией или полным состоянием МТ называется ,

где - состояние устройства управления; - слово над алфавитом слева от головки; - слово справа от головки.первый символ которого -" обозревается" головкой. Выполнение продукции задания приводит к переходу от конфигурации к конфигурации .

Считают, что начальная и заключительная конфигурации МТ таковы, что считывающая/записывающая головка расположена слева от слова исходных данных данных или результата, над первым символом.

Машина Тьюринга правильно реализует некоторую функцию (или предикат), если от начальной конфигурации за конечное число шагов машина переходит к заключительной конфигурации , причем если значение - неопределено, то МТ никогда не останавливается.

Любые две МТ считаются одинаковыми, если они реализуют одну и ту же функцию.

Пример 9. Построить копирующую машину MT_С, выполняющую копирование произвольного унарного числа. Для представления чисел на ленте МТ часто используется унарная система. В унарном счислении натуральное число кодируется последовательностью символов «1» количество которых равно величине числа, например число 3 представляется в единичном коде как

Для распознавания позиции конца слова будем считать, что в конце исходных данных стоит специальный символ .

1. Система продукций копирующей MT_С

1.1. - запоминание копируемого символа;

1.2. -перенос копируемого символа вправо;

1.3. -копирование;

1.4. - возврат к последней скопированной позиции на ленте

1.5. - восстановление скопированного символа и продолжение копирования;

1.6. - завершение процесса копирования;

1.7. - вывод головки в исходное положение;

1.8. - остановка.

Замечание. Продукции 1.2 и 1.4 представляют групповую запись, означающую сходное функционирование МТ при разных данных.

2. Алфавит

3. Состояния устройства управления

4. Проверочная последовательность конфигураций для контрольного примера исходных данных

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

Тезис Тьюринга

Тезис Тьюринга: «всякий алгоритм может быть реализован в виде МТ» - определяет критерий, позволяющий отделить алгоритмически разрешимую проблему от проблем, не относящихся к таковым.

Понятие алгоритмически разрешимых проблем конкретизируют следующие две операции, определенные над множеством МТ.

Композиция МТ

Если МТ₁ и МТ₂ реализуют соответственно функции f1(X) и f2(У) - причем область значений f1 совпадает с областью определения f2, то может быть построена композиция MT=MT₂°MT₁, реализующая функцию. f2(f1(X)). Композиция МТ представляет собой последовательное подключение машин МТ₁ и МТ₂ (последовательный вычислительный процесс), при котором результат первой машины поступает на обработку второй (см. рис.5а).

Для построения МТ композиции ее начальное состояние полагают равным начальному состоянию МТ₁, конечное состояние МТ₁ полагают равным начальному состоянию МТ₂, а конечное состояние композиции полагают равным конечному состоянию MT₂.

а) б)

Рис. 5. Операции над МТ: а - композиция б - разветвление

 

Разветвление МТ

Если МТ₁ и МТ₂ реализуют соответственно функции f1(X) и f2(Х) с одинаковыми областями определения, существует МТ_Р, реализующая некоторый предикат Р(х), то может быть построена MT - разветвления , реализующая функцию

МТ – разветвления представляет параллельное подключение МТ₁ и МТ₂ (разветвление вычислительного процесса ), при котором результат формируется первой машиной, если значение предиката истинно, а иначе - формируется второй. МТ - разветвления начинает свою работу с копирования исходных данных, по одному из экземпляров которых машина предиката вырабатывает признак, указывающий на то, какая из функциональных машин формирует результат.

На­чальное состояние МТ- разветвления полагают равным начальному состоянию МТ композиции, состоящей из последовательного подключения копирующей MT_С, и МТ_Р, реализующей предикат Р. Вводятся две новые продукции:

услови­ям конечного состояния MT_С°МТ_Р и символу 1 (истинности предиката Р), сопоставля­ется начальное состояние MT1,

условиям конечного состояния MT_С°МТ_Р и символу 0 (ложности предиката Р) сопоставляется начальное состояние МТ2.

Конечные состояния МТ₁ и МТ₂ отождествляются с конечным состоянием
МТ - разветвления (рис. 5)

Т.к. интуитивно ясно, что любой алгоритм может быть запрограммирован с помощью последовательных действий и условных разветвлений, то введенные операции позволяют рассматривать МТ как модель алгоритма, анализируя на ней его свойства.

Список рекомендуемой литературы

 

Кузнецов О.П., Адельсон – Вельский Г.М. Дискретная математика для инженера.- М. Энергоатомиздат, 1988

 

Горбатов В.А. Основы дискретной математики. Учебное пособие для студентов вузов.-М.Высшая школа, 1986

 

Мендельсон Э. Введение в математическую логику. Пер. с англ.-М.наука 1976

 

Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М. Мир, 1981

 

Машины Тьюринга и рекурсивные функции /Под общ. ред. Г.Д.Эбинхауза: Пер с нем. – М.Мир 1972

1) Выбрать Вариант Контрольной работы (в конце методички) по числу из двух последних цифр Зачетки (или Студенческого билета).

Если Две последние цифры Вашей зачетки от 01 до 25 то

Ваш № Вариант = Две последние цифры зачетки

Иначе Если Две последние цифры Вашей зачетки от 26 до 49 то

Ваш № Вариант = 50 -Две последние цифры зачетки

Иначе Если Две последние цифры Вашей зачетки от 50 до 74 то

Ваш № Вариант = 75 -Две последние цифры зачетки

Иначе Если Две последние цифры Вашей зачетки от 75 до 99 то

Ваш № Вариант = 100 -Две последние цифры зачетки

Иначе Ваш № Вариант =13

 

2) Выполнить задания Контрольной работы

МАКЕТ представления Контрольной работы.

Группа№ _________ Студент Фамилия И.О. № зачетки_______ №Варианта_______

 

2.1) Тест – аттестация ранее полученных знаний.

Построить таблицу истинности двоичной функции из пункта б Варианта.

р

 

 

2.2) Для результирующей функции, полученной на этапе Тест – аттестации, выполнить построения, указанные в пункте б) Варианта: СДНФ, СКНФ, ПЖ, определение существенности, построение в базисах.

Например ПЖ.

Общий вид полинома от 3-х переменных

 

Таким образом ПЖ

 

2.3) минимизировать с помощью карт Карно (Вейча) двоичную функцию от 4-х переменных, заданную аналитически, либо своими значениями на наборах

Для функций заданных аналитически ( в виде произвольных ДНФ, КНФ) по желанию минимизацию можно выполнить либо методом Блейка, либо на картах (предварительно получив значения на наборах).

Например, для функции, заданной своими значениями на наборах

а

F(a)

Контрольная работа

Bариант l

а) минимизировать с помощью карт Карно двоичную функцию от 4-х переменных, заданную своими значениями на наборах

123456Следующая ⇒

Поделиться: