Задачи изучения дисциплины Изучив дисциплину, студент должен: 1

Вид материала

Учебно-методический комплекс

Содержание 1. Цель и задачи дисциплины 2. Содержание дисциплины 3. Виды работ с распределением времени 4. Перечень тем лекционных занятий 5. Перечень тем практических занятий Методические указания для студентов Методические указания для преподавателей Материалы текущего, промежуточного, итогового контроля

Подобный материал:

• Рабочая программа дисциплины (модуля) История бухгалтерского учета, 332.58kb.
• Задачи изучения дисциплины Входе изучения дисциплины студент должен: усвоить категории, 166.12kb.
• Задачи изучения дисциплины Врезультате изучения дисциплины студент должен: сформировать, 190.25kb.
• Задачи изучения дисциплины Врезультате изучения дисциплины студент должен: сформировать, 148.27kb.
• Рабочая программа дисциплины современные компьютерные сети цели и задачи изучения дисциплины, 67.85kb.
• Задачи курса: Врезультате изучения дисциплины студент должен, 508.82kb.
• Аннотация примерной программы учебной дисциплины «Эксплуатационные материалы» Цели, 59.72kb.
• Требования к уровню освоения содержания дисциплины, 69.97kb.
• Учебная программа дисциплины "философия" Аннотация, 247.87kb.
• Рабочая программа Наименование дисциплины Теоретическая механика По специальности 220501., 218.91kb.

Автор-составитель:


Сперанский Д.В., доктор технических наук, профессор кафедры «Высшая и прикладная математика»


Учебно-методический комплекс по дисциплине «Математическая логика и теория алгоритмов» составлен в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования по специальности: 220100 «Вычислительные машины, комплексы, системы и сети (ЭВМ)».


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




1. ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ


1.1. Целью дисциплины «Математическая логика и теория алгоритмов» является изучение указанных в рабочей программе глав этой дисциплины, необходимых при изучении дисциплин, входящих в учебный план по специальности 220100 «Вычислительные машины, комплексы, системы и сети (ЭВМ)».


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


1.2. Задачи изучения дисциплины

Изучив дисциплину, студент должен:

1.2.1. Знать базовые понятия дискретной математики.

1.2.2. Владеть основами математической логики и теории алгоритмов.

1.2.4. Уметь решать типовые задачи.

1.2.4. Иметь представление об использовании полученных знаний при решении инженерных задач.


2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ


2.1. Элементы классической математической логики. Предмет классической математической логики. Предмет логики высказываний. Логические операции над высказываниями. Понятие формулы алгебры высказываний. Равносильность и классификация формул. Логические эквивалентности. Определение булевой алгебры.

Примеры. Законы булевой алгебры. Переключа­тельные функции (ПФ). Определение различных типов ПФ. Полностью и не полностью определенные ПФ. Способы зада­ния ПФ. Специальные разложения ПФ. Минимизация ПФ. Те­орема о функциональной полноте. Примеры функционально полных базисов. Моделирование алгебры высказываний релей-но-контактными схемами. Задача анализа и синтеза. Миними­зация булевых функций. Алгебра предикатов. Кванторы, При­менение нормальных форм в программировании. Примеры формальных (аксиоматических) систем. Исчисления. Исчисле­ние высказываний. Исчисление предикатов. Непротиворечи­вость. Полнота.

Литература: [1; 2; 3; 5; 6; 7; 8].

2.2. Элементы неклассических математических логик. Пред­мет неклассических логик. Нечетная логика. Нечеткие высказы­вания. Правила преобразования нечетких высказываний. Ха­рактеристическая функция нечеткого подмножества. Функции нечетких переменных. Таблица значений функции нечетких пе­ременных. Равносильность двух функций нечетких переменных. Полиномиальные формы. Логическая структура функций нечет­ких переменных. Синтез функций нечетких переменных. Сети нечетких элементов. Модальная логика. Логические операции в модальной логике высказываний. Понятие формулы модальной алгебры высказываний. Модальная логика предикатов. Термо-ральная логика. Алгоритмическая логика Хоара. Формальные (аксиоматические) системы. Языки и грамматики формальных неклассических систем.

Литература: [1; 2; 6; 7; 10; 12; 13].

2.3. Элементы теории алгоритмов. Интуитивное понятие ал­горитма и его спецификации. Понятие об (обычном) четком и нечетком алгоритме. Формализация понятия четкого алгорит­ма. Рекурсивные функции. Понятие о примитивно-рекурсивной функции. Функции, вычисляемые на машинах Тьюринга, нор­мальные алгоритмы Маркова. Тезисы Черат, Тьюринга и Мар­кова. Эффективные алгоритмы. Разрешимые и неразрешимые проблемы. Понятие сложности вычислений. Схемы алгоритмов. Схемы потоков данных.

Литература: [1; 3; 4; 8; 10; 14].


3. ВИДЫ РАБОТ С РАСПРЕДЕЛЕНИЕМ ВРЕМЕНИ


Курс — II, семестр — IV.

Всего часов — 100 ч.

Лекционные занятия — 4 ч.

Практические занятия — 8 ч.

Число контрольных работ — 1

Самостоятельная работа — 88 ч.

Экзамен — 1.


4. ПЕРЕЧЕНЬ ТЕМ ЛЕКЦИОННЫХ ЗАНЯТИЙ

(примерный объем в часах)

Тема	Часы
Элементы классической математической логики. Логика высказываний	2
Элементы теории алгоритмов	2

5. ПЕРЕЧЕНЬ ТЕМ ПРАКТИЧЕСКИХ ЗАНЯТИЙ

(примерный объем в часах)

Тема	Часы
Элементы классической математической логики. Логика	2
предикатов. Решение типовых задач по классической
математической логике
Понятие о формальных (аксиоматических) системах.	2
Понятие о неклассических математических логиках.
Элементы нечеткой логики
Решение типовых задач по нечеткой логике	2
Решение типовых задач по теории алгоритмов	2

Рекомендуемая литература

основная

1. Ершов Юрий Леонидович. Математическая логика [Текст] : Учебное пособие для вузов / Ю.Л. Ершов, Е.А. Палютин, 1987. - 336 с.Имеются экземпляры: всего 1 : ЧЗ (1)
   
2. Зайцев, Иван Антонович. Высшая математика [Текст] : Учеб. для неинж. спец. с.-х. вузов / И.А. Зайцев, 1991. - 400 с.Имеются экземпляры: всего 2 : АБ (1), ЧЗ (1
   

дополнительная

3. Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2002 г.
   
4. Шестаков А.А., Дружинина О.В. Дискретная математика. Элементы нечеткой логики: Учеб. пос. – М: РГОТУПС, 2002 г.
   
5. Мендельсон Э. Введение в математическую логику. – М.: Наука, 2001 г.
   

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ СТУДЕНТОВ


Зaдание № 1.

Задана логическая формула  От нее перейти к эквивалентной ей формуле  так, чтобы последняя не содержала знаков операции  и . Исходя из таблиц истинности булевых операций доказать, что формулы  и  логически эквивалентны. Для формулы  найти СКНФ и СДНФ.

Приведем некоторые логические законы исчисления высказываний, которые понадобятся нам:

1). Правила замены операции импликации

( A (  (1)
( A (  (2)

Правила замены операции эквивалентности

A B  (A B ) ( ); (3)

A B  (A )  (4)

ПРИМЕР. Пусть  = . Используя (1), получаем    Поскольку  = p, то окончательно имеем  = p . Теперь докажем эквивалентность формул  и  , используя таблицы истинности операций отрицания, дизъюнкции, конъюнкции и импликации.

p	q	
0	0	1	1	1	1
0	1	1	0	0	0
1	0	0	1	1	1
1	1	0	0	1	1

Для формулы  =  построим СДНФ. Поскольку значение  равно 1 на наборах переменных pq = 00, 10, и 11, то каждому из них соответствует следующие произведения этих переменных:

 ,  ,  q.

Для получения СДНФ построим дизъюнкцию этих произведений:

 = (  )  (  q).

Для получения CКНФ выпишем термы, на которых функция  принимает значения , равные 0 (или, что все равно, значения равны 1). В нашем случае это терм () т.е. , =  q Далее в каждом таком терме инвертируем переменные и образуем из них дизъюнкцию. Затем все эти дизъюнкции объединяем через знаки конъюнкции. В нашем случае терм (q) заменяем на p   терм только один, то это и есть СКНФ для функции 

Задание № 2.

Найти область истинности предиката P( …,

Напомним, что областью истинности этого предиката называются те упорядоченные наборы  …,, на которых предикат имеет значение, равное 1.

ПРИМЕР. Задан предикат P(  ), где (  и A = {1,2,3,4}.

Множество есть множество всех упорядоченных троек ( , где   А.

Для решения рассматриваемой задачи необходимо построить все возможные упомянутые тройки (общее их число равно = 64) и для каждой из них проверить справедливость неравенства  . Например, для тройки (1,1,1) оно не выполняется, т.к. 1+1 неверно. Следовательно,эта тройка не принадлежит области истинности предиката. Рассмотрим другую тройку –(1,2,3). Для нее 1+2  3 , т.е. неравенство справедливо и эта тройка принадлежит области истинности предиката. Осуществив перебор всех троек и проверив для каждой из них справедливость неравенства, получаем следующую область истинности предиката:

(1,1,2),( 1,1,3),(1,1,4),(1,2,3),(1,2.4,),(1,3.4),(2,1,3),(2,2,4),(3.1,4).

Место для формулы.


Задание №3.

Задана функция от нечетких переменных. Требуется упростить эту функцию.

Отметим, что для упрощения обычных логических функций используются все известные логические законы, включая закон тождества (А А) , непротиворечивости (А = 0), исключенного третьего (А  = 1), свойства констант ( = 1,  = 0, А  0 = А, А  1 = 1, А ), идемпотентности (А А =А, АА = А), ассоциативности (А  ( В С) = ( А В С , (А  В)  С = А  (В  С), закон поглощения ( А  (А В) = А, А ( А  В) = А), закон де Моргана (   =  ) и т.д.

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

ПРИМЕР. Задана функция (А В) ). Выполняем последовательно ее преобразования: (А В) ) = (А А)  ( В А) А  А = А 0 = А.

Задание № 4.

Вначале напомним следующее определение. Пусть задана некоторые числовые функции : n-арная функция g и (n+2)-арная функция h. Говорят, что (n+1)-арная функция f возникает из функций g и h примитивной рекурсией, если для всех

 …, имеем

f( …,= g( …,

f( …,= h ( …, ,y, f( ,

Теперь перейдем к постановке задачи. Пользуясь определением примитивно рекурсивной функции, показать, что числовая функция а примитивно рекурсивна.

ПРИМЕР 1.Пусть f(x,y) = x+y. Это двуместная функция удовлетворяет соотношениям

x +0 = x = (x),

x+( y+1) = (x+y) +1 = s( x+y).

Следовательно, рассматриваемая функция возникает из примитивной рекурсивных , h(x,y,z) = z+1операцией примитивной рекурсии и потому заданная функция примитивно рекурсивна.

ПРИМЕР 2. Пусть f(x,y) = xy. Это двуместная функция удовлетворяет схеме примитивной рекурсии

x 0= O(x) ,

x(y+1) = xy +x

с начальными примитивно рекурсивными функциями

g(x) = O(x), h(x,y,z) = z+x.

Поэтому рассматриваемая функция примитивно рекурсивна.


МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ПРЕПОДАВАТЕЛЕЙ


Действующая с 2002 года по настоящее время программа по дисциплине «Математическая логика и теория алгоритмов» содержит 7 разделов. Что касается раздела « 2.6. Элементы теории кодирования», то он дублирует знания, которые освоить студенты по дисциплине «Теория информации и кодирования». По этой причине этот раздел из программы по дискретной математике целесообразно исключить. Остальные разделы программы содержат вопросы, касающиеся как четких, так и нечетких объектов и связанных с ними понятий (множества, подмножества, отношения, графы). Для студентов специальности ЭВМ существенно востребованными являются знания по классическим (четким) объектам и понятиям. Именно эти понятия широко применяются при логическом проектировании дискретных устройств, их минимизации, анализе архитектуры устройств и т.п.

К сожалению, в российской инженерной практике в настоящее время почти не используются понятия, связанные с нечеткими объектами. В связи с этим при освещении вопросов дисциплины «Математическая логика и теория алгоритмов» основное внимание следует уделить «четким» объектам и понятиям. Сведения о «нечетких» объектах безусловно расширяют кругозор студентов и в этом отношении не яляются бесполезными, но не более того. Среди всех прочих разделов программы разделы 2.1. Элементы комбинаторики, 2.2. Обычные (четкие) множества и нечеткие подмножества, их спецификации, 2.3. Обычные (четкие) отношения , 2.5. Нечеткая арифметика следует рассматривать как вспомогательные. Центральными с точки зрения возможности практического приложения являются разделы 2.4. Теория обычных (четких) и нечетких графов и 2.7.

Элементы тории конечных автоматов. Так, методы теории графов имеют широкие приложения в задачах размещения компонентов на плате, трассировки путей, задачах оптимального размещения компонетов устройств по критерию минимальности числа каналов , связывающих эти компоненты, и т.п. Что касается теории автоматов, то она имеет широкие приложения при логическом проектировании дискретных устройств. Отметим прежде всего, что автоматы (как абстрактные, так и структурные) используются в качестве моделей реальных цифровых устройств. На основе использования таких моделей решаются задачи оптимизации структур дискретных устройств, их контролепригодного проектирования, и т.п. Особо следует отметить приложения теории автоматов к проблемам технической диагностики дискретных устройств, где эта теория служит базой для разработки методов диагностики и контроля современных устройств , изготовленных с использование БИС, СБИС и микропроцессоров. Изложенные обстоятельства дают основания рекомендовать акцентировать внимание преподавателей на изложении в рамках установочных лекций упомянутых двух разделов программы. Отмети также и еще одно обстоятельство.

В последнее десятилетие возникло и успешно развивается новое направление прикладного характера, именуемое автоматным программированием. В рамках этого нового перспективного направления разрабатываются методы эффективного создания современных программных систем. С момента введения в действие в 2002 году обсуждаемой учебной программы по дисциплине «Математическая логика и теория алгоритмов» прошло более 8 лет, поэтому список литературы (как основной, так и дополнительный) нуждается в обновлении. В методических указаниях для студентов по специальности ЭВМ по выполнению контрольных работ, изданных кафедрой в 2009 году, булла указана новая современная литература из пяти наименований.

Особо следует отметить полезность еще одной монографии для студентов именно этой специальности – Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств.-М.: ФИЗМАТЛИТ, 2007.- 592 с. В ней последовательно вводятся базовые понятия всех разделов существующей рабочей программы.


МАТЕРИАЛЫ ТЕКУЩЕГО, ПРОМЕЖУТОЧНОГО, ИТОГОВОГО КОНТРОЛЯ

Билет № 1

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

2. Используя свойства кванторов общности и существования, сформулируйте

отрицания следующих утверждений в утвердительной форме ( они не должны начинаться со слов «неверно, что…» или «не …»):

а) Из всякого положения есть выход,

б) В каждом учреждении найдутся двое служащих с одинаковыми датами рождения.


Билет №2


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

2.Записать следующие высказывания с использованием кванторов:

а) Уравнение ax =b имеет не более одного корня,

б)Множество М содержит по меньшей мере один элемент.


Билет №3


1.Специальные разложения логических функций: дизъюнктивная и конъюктивная нормальная формы (днф и кнф). Совершенные днф и кнф.

Преобразование днф в совершенную днф. Построение совершенных днф и

кнф по таблице истинности логической функции. Привести примеры.

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


Билет №4


1.Исчисление предикатов: понятие предиката (n-местного предиката ). Понятие кванторов общности и существования. Квантификация многоместных высказывательных форм. Формулы исчисления предикатов. Законы отрицания высказываний с кванторами.

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

x	y	z	F(x,y,z)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

Билет №5


1.Элементы теории алгоритмов: свойства интуитивно понимаемого алгоритма ( дискретность, детерминированность, массовость и т.д.).

Определения простейших функций O(x), s(x) и . Определение операции суперпозиции функций и операции примитивной рекурсии.

2.Записать с использованием кванторов следующие высказывания:

а) Функция y= положительна при любом значении аргумента.

б) Функция y= принимает любое положительное значение.


Билет №6


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

2.Функцию, заданную представленной ниже таблицей, записать в виде сднф и скнф.

x	y	z	F(x,y,z)
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

Билет №7

1. Элементы теории алгоритмов : Понятие примитивно рекурсивной функции. Операция минимизации частичной функции. Понятие частично рекурсивной функции. Вычислимые функции. Привести примеры. Строгое математическое понятие алгоритма с использованием рекурсивных функций.

2.Пусть множество А = {1,2,3,4} и пусть П = {{123}, {4}} – его разбиение. Выпишите отношение эквивалентности, соответствующее этому разбиению.


Билет №8

1.Элементы теории алгоритмов: машина Тьюринга. Тезис Черча. Алгоритмически разрешимые и алгоритмически неразрешимые задачи. Привести примеры.

2.Дайте определения симметричного, антисимметричного, транзитивного и рефлексивного бинарных отношений. Приведите примеры таких отношений.

Билет №9

1.Дайте определение булевой алгебры. Частные виды булевой алгебры применительно к понятиям «высказывание» и «множество».Понятие функциональной полноты. Примеры функционально полных базисов.

2.Упростите логические выражения:

а) (A  B)  (A  B  С),

б) A  B  (CD) .


Билет №10

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

2.Пусть  = {,}   . Является ли отношением эквивалентности? Если да, то выпишите класс эквивалентности [с], содержащий элемент с.