Рекомендации методические рассмотрены и одобрены кафедрой вм и по 13 февраля 2008 г., протокол №5 Рецензент Кацуба В. С., канд физ мат наук, доцент кафедры высшей математики и программного обеспечения ЭВМ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО РЫБОЛОВСТВУ фгоувпо «МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» Кафедра высшей математики и программного обеспечения ЭВМ Математика Часть 7 Задания контрольной работы по теме «Специальные разделы высшей математики» и методические указания к ее выполнению для студентов 2 курса вечерне-заочного факультета всех специальностей Мурманск 2008 г. УДК 51 (076.5) ББК 22.1 я 73 3 15 Составители: Хохлова Людмила Ивановна, к.ф.н., доцент кафедры высшей математики и программного обеспечения ЭВМ МГТУ, Мостовская Любовь Григорьевна, доцент кафедры высшей математики и программного обеспечения ЭВМ МГТУ Методические рекомендации рассмотрены и одобрены кафедрой ВМ и ПО 13 февраля 2008 г., протокол № 5 Рецензент – Кацуба В.С ., канд. физ.-мат. наук, доцент кафедры высшей математики и программного обеспечения ЭВМ ÓМурманский государственный технический университет, 2008 Оглавление Стр. Введение. 4 Задания на контрольную работу по теме «Специальные разделы высшей математики». 5 Содержание теоретического материала и ссылки на литературу.. 9 Справочный материал к выполнению контрольной работы 10 1. Алгебра логики. 10 1.1. Высказывания и операции над ними . 10 1.2. Формулы алгебры логики . 13 1.3. Приложение алгебры логики. Релейно-контактые схемы .. 15 2. Булевы функции. 17 3. Графы.. 19 3.1. Основные определения . 19 3.2. Матрицы графов . 20 4. Элементы вариационного исчисления. 22 4.1. Функционалы в линейном нормированном пространстве . 22 4.2. Экстремумы функционала . 24 5. Оптимальное управление. 27 5.1. Математическая модель системы управления . 27 5.2. Оптимальное управление динамической системой . 28 5.3. Принцип максимума Понтрягина . 29 Решение примерного варианта контрольной работы.. 31 Рекомендуемая литература.. 39 Введение Настоящее пособие предназначено для студентов 2 курса вечерне-заочного факультета, обучающихся по техническим специальностям. В пособии содержатся ссылки на теоретический материал по теме «Специальные разделы высшей математики», список рекомендуемой литературы и задания к выполнению контрольной работы. К специальным разделам высшей математики в данном пособии отнесены «Математическая логика», «Графы», «Элементы функционального анализа», «Вариационное исчисление и оптимальное управление». В результате изучения этих разделов студенты должны: • знать, что такое высказывание, и уметь записывать формулы сложных высказываний при помощи логических операций; • уметь упрощать логические формулы при помощи равносильных преобразований; • иметь представление о булевых функциях одной и двух переменных; • знать основные термины теории графов, иметь представление о способах задания ориентированных и неориентированных графов; • знать, что такое функционал, вариация функционала, вариационная задача; • уметь находить экстремали некоторых функционалов; • иметь преставление о математических моделях систем управления; • знать принцип максимума Понтрягина и уметь находить оптимальное управление для динамической системы. Данные методические рекомендации включают справочный материал, необходимый для выполнения контрольной работы по теме «Специальные разделы высшей математики», и решение примерного варианта работы, в котором имеются ссылки на используемый справочный материал. Задания на контрольную работу по теме «Специальные разделы высшей математики» Контрольная работа состоит из пяти задач. Задание для каждой задачи включает в себя ее формулировку и десять вариантов исходных данных. Перед выполнением контрольной работы необходимо изучить теоретический материал по данной теме и закрепить его решением рекомендованных задач в соответствии со ссылками на литературу, затем ознакомиться со справочным материалом и образцом выполнения примерного варианта контрольной работы. Задача 1. Дана формула алгебры логики. Требуется: 1) при помощи равносильных преобразований упростить формулу; 2) построить релейно-контактные схемы для исходной и упрощенной формул. Номер варианта Формула 1 2 3 4 5 6 7 8 9 10 Задача 2. Дана булева функция f (x , y ). Составить таблицу значений функции и указать значение f (1, 0). Номер варианта Функция f (x , y ) 1 2 3 4 5 6 7 8 9 10 Задача 3. Составить список дуг ориентированного графа, изображенного на рисунке. Сформировать матрицу инцидентности и матрицу смежности этого орграфа. Номер варианта Орграф Номер варианта Орграф 1 6 2 7 3 8 4 9 5 10 Задача 4. Даны функционал I [y (x )] = и граничные условия для функции y (х ): y (a ) = A , y (b ) = B . Требуется найти экстремали функционала, удовлетворяющие граничным условиям. Номер варианта Функционал I [y (x )] Граничные условия 1 y (0) = 3 y (ln2) = 2 2 y (0) = 0 y (3) = 2 3 y (0) = 1 y (ln2) = – 1 4 y (0) = – 0,5 y (π ) = 0,5 5 y (0) = 0 y (2) = e 6 y (0) = 1 y (2) = 5 7 y (0) = 2 y (π ) = 0 8 y (0) = 0 y (1) = – 2 9 y (0) = 0 = 1 10 y (0) = 2 y (ln3) = 10 Задача 5. Дана модель объекта управления, описываемая системой дифференциальных уравнений и граничными условиями , , где N – номер варианта, t – время (t [0; b ]), – фазовый вектор (траектория объекта), u (t ) – функция управления объектом. Требуется найти оптимальное управление объектом u *(t ) и соответствующую ему оптимальную траекторию , если задан критерий качества управления: I [u (t )] = Номер варианта [0; b ] x 1 (0), x 2 (0) x 1 (b ), x 2 (b ) 1 [0; 3] x 1 (0) = 0, x 2 (0) = 1 x 1 (3) = – 1, x 2 (3) = 0 2 [0; 4] x 1 (0) = 2, x 2 (0) = 0 x 1 (4) = 0, x 2 (4) = 1 3 [0; 2] x 1 (0) = 1, x 2 (0) = 0 x 1 (2) = – 1, x 2 (2) = 3 4 [0; 3] x 1 (0) = 0, x 2 (0) = – 1 x 1 (3) = 1, x 2 (3) = 0 5 [0; 4] x 1 (0) = 0, x 2 (0) = – 2 x 1 (4) = 0, x 2 (4) = 1 6 [0; 2] x 1 (0) = 0, x 2 (0) = 1 x 1 (2) = – 2, x 2 (2) = 0 7 [0; 1] x 1 (0) = – 7, x 2 (0) = 0 x 1 (1) = 0, x 2 (1) = 3 8 [0; 2] x 1 (0) = 0, x 2 (0) = 2 x 1 (2) = 0, x 2 (2) = 1 9 [0; 1] x 1 (0) = – 3, x 2 (0) = 0 x 1 (1) = 6, x 2 (1) = 0 10 [0; 2] x 1 (0) = 0, x 2 (0) = 1 x 1 (2) = – 10, x 2 (2) = 0 Содержание теоретического материала и ссылки на литературу № задачи Содержание (темы) Литература 1 Высказывания, их значения истинности. Операции над высказываниями: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Таблицы истинности. Свойства логических операций, порядок их выполнения. Равносильные логические формулы. Алгебра Буля [1], часть 1, гл. 1, §1-6; часть 2, гл. 1, §1,2, №1.1-1.22, 1.45, 1.46(1,2), 1.48(1-7), 1.50, 1.51; [2], гл. 1, п.1.1.1-1.1.3, задачи 1-6; [3], гл. 16.3 2 Функции алгебры логики (булевы функции) и их преставление при помощи логических формул. Приложение алгебры логики: упрощение релейно-контактных схем [1], гл. 1, §7, 8, 13; часть 2, гл. 1, §3,4, №1.49; [2], гл. 1, п.1.2.1, 1.2.4, зад. 17; [3], гл. 16.4 3 Графы. Основные определения: вершины, ребра, кратные ребра. Ориентированные и неориентированные графы. Задание графов. Матрица инцидентности и матрица смежности графа [2], гл. 4, п.4.1.1, 4.1.4; [6], гл.III, §1-5 4 Функционал. Приращение функционала. Вариация функционала. Экстремумы функционала, необходимое условие экстремума. Экстремали функционала. Уравнение Эйлера для функционала вида [4], гл. 7, §1-2; [5], гл. II, §3.1, 3.3, 3.6, 4; №71, 72, 75-78; [7], гл.X, № 1281-1285, 1289-1298; [8], гл. 16, №3.1-3.8 5 Система управления и ее математическая модель. Оптимальное управление. Гамильтониан. Принцип максимума Понтрягина. Каноническая система уравнений задачи оптимального управления [9], часть III, гл. 9.1.1-9.1.2, №9.1, 9.3, 9.4 Примечание. Ссылки на литературу в таблице даны в соответствии с номерами в списке рекомендуемой литературы. Справочный материал к выполнению контрольной работы 1. Алгебра логики 1.1. Высказывания и операции над ними Математическая логика – разновидность формальной логики, т.е. науки, которая изучает умозаключения с точки зрения их формального строения. Высказыванием называется предложение, к которому можно применить понятия «истинно» или «ложно». Обозначаются высказывания малыми прописными буквами: a , b , х ,…. В математической логике не рассматривается смысл высказываний, определяется только их логическое значение – «истина» или «ложь», что принято обозначать соответственно «1» или «0». Примеры. 1. «Волга впадает в Каспийское море» – высказывание (истинное). 2. «Число 16 кратно 3» – высказывание (ложное). 3. «Может быть, сегодня пойдет снег» – не высказывание. 4. «3х – 5 = 0» – не высказывание. Истинные и ложные высказывания образуют соответствующие множества. С помощью простых высказываний можно составлять более сложные, соединяя простые высказывания союзами «и», «или», связками «не», «следует» и др. Таким образом, операции над высказываниями можно описывать при помощи некоторого математического аппарата. Основные логические операции над высказываниями. Отрицанием высказывания х называется высказывание, которое истинно тогда и только тогда, когда высказывание х ложно. Отрицание обозначается или Øх (читается: «не х »). Логические операции можно задавать при помощи таблиц истинности , показывающих соответствие значений истинности высказываний. Для высказываний x и эта таблица имеет вид: х 1 0 0 1 Конъюнкцией двух высказываний х и y называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания х и y . Конъюнкция обозначается: х Ù y , или х & y (читается: «х и y »). Таблица истинности для х Ù y имеет вид: х y х Ù y 1 1 1 1 0 0 0 1 0 0 0 0 Дизъюнкцией двух высказываний х и y называется высказывание, ложное тогда и только тогда, когда оба высказывания х и y ложны. Дизъюнкция обозначается х Ú y (читается: «х или y »). Таблица истинности для х Ú y имеет вид: х y х Ú y 1 1 1 1 0 1 0 1 1 0 0 0 Импликацией двух высказываний х и y называется высказывание, ложное тогда и только тогда, когда высказывание х истинно, а y – ложно. Импликация обозначается: х ® y (читается: «х влечет y » или «из х следует y »). Высказывание х называется посылкой импликации , а высказывание y – следствием . Таблица истинности для х ® y имеет вид: х y х ® y 1 1 1 1 0 0 0 1 1 0 0 1 Эквиваленцией (эквивалентностью) двух высказываний х и y называется высказывание, истинное тогда и только тогда, когда истинности высказываний х и y совпадают. Эквиваленция обозначается: х « y , или х ~ y (читается: «х эквивалентно y » или «х тогда и только тогда, когда y »). Таблица истинности для х « y имеет вид: х y х « y 1 1 1 1 0 0 0 1 0 0 0 1 1.2. Формулы алгебры логики Формулами алгебры логики называются выражения, полученные из переменных x , y ,… посредством применения логических операций: отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции, а также сами переменные, принимающие значения истинности высказываний x , y ,…. Формулы алгебры логики будем обозначать большими буквами латинского алфавита: А , В ,….. Если в формулу алгебры логики вместо переменных x , y ,… подставить конкретные высказывания, то получится высказывание, имеющее логическое значение «1» или «0». Пример. Высказывание x : «Волга впадает в Каспийское море» – истинное (x = 1), высказывание y : «Число 16 кратно 3» – ложное (y = 0), тогда формула А = x Ú y будет иметь логическое значение «1»: А = 1 (см. таблицу истинности для х Ú y ). На основе таблиц истинности основных логических операций можно составлять таблицы истинности для различных формул алгебры логики. Две формулы алгебры логики называются равносильными или эквивалентными , если они принимают одинаковые логические значения на любом наборе значений входящих в формулы переменных (элементарных высказываний). Равносильность формул А и В будем обозначать знаком «º»: А º В . Равносильность логических формул можно установить при помощи их таблиц истинности. Пример. С помощью таблиц истинности проверить, являются ли равносильными формулы А = и В = . Решение. Составим таблицы истинности для каждой из формул А и В . x y Ù А = 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1 1 x y x Ú y В = 1 1 0 1 0 0 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 Ответ: данные формулы являются равносильными. Другой способ доказательства равносильности логических формул – их упрощение с использованием основных равносильностей . Основные равносильности. Для любых элементарных высказываний x , y , z справедливы следующие равносильности, которые можно разбить на 3 группы. 1. Основные законы: 1) x Ù x º x ; 2) x Ú x º x ; 3) º x ; 4) x Ù 0 º 0; 5) x Ú 0 º x ; 6) Ù x º 0; 7) x Ù 1 º x ; 8) x Ú 1 º 1; 9) Ú x º 1; законы поглощения: 10) x Ù (y Ú x ) º x ; 11) x Ú (y Ù x ) º x . 2. Выражения одних логических операций через другие: 12) x ® y º Ú y ; 13) ; 14) x « y º (x ® y ) Ù (y ® x ); 15) . 3. Свойства логических операций: 16) x Ù y º y Ù x ; 17) x Ú y º y Ú x ; 18) x Ù (y Ù z ) º (x Ù y ) Ù z ; 19) x Ú (y Ú z ) º (x Ú y ) Ú z ; 20) x Ù (y Ú z ) º (x Ù y ) Ú (x Ù z ); 21) x Ú (y Ù z ) º (x Ú y ) Ù (x Ú z ). Множество высказываний с введенными для них логическими операциями и основными равносильностями называется алгеброй Буля . Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий: конъюнкция выполняется раньше, чем все остальные операции, дизъюнкция выполняется раньше, чем импликация и эквиваленция. Если над формулой стоит знак отрицания, то скобки тоже опускаются. Пример. Упростить логическую формулу: . Решение . Используем основные равносильности. . Ответ: А º x Ú y . 1.3. Приложение алгебры логики. Релейно-контактые схемы Релейно-контактной схемой (РКС ) или переключательной схемой называется схематическое изображение устройства, состоящего из следующих элементов: 1) переключателей (контактов, реле, ламп и др.); 2) соединительных проводников; 3) входов-выходов (полюсов РКС). Рассмотрим простейшую РКС, содержащую один переключатель Р . Если переключателю Р поставить в соответствие высказывание х : «Переключатель Р замкнут», то истинному значению х (х = 1) будет соответствовать замкнутое состояние переключателя, при котором РКС проводит ток, т.е. импульс, поступающий на вход, может быть снят на выходе. Значению х = 0 будет соответствовать разомкнутое состояние РКС (ток не проводится). Каждой РКС, состоящей из нескольких переключателей, можно поставить в соответствие высказывание, выраженное некоторой формулой А , таким образом, что истинному значению формулы (А = 1) будет соответствовать замкнутое состояние РКС, а значению А = 0 – разомкнутое состояние. Примеры таких соответствий приведены в таблице. Простейшие РКС и соответствующие им формулы логики. РКС Формула Значения Переключатель х : Простейшее высказывание: х х = 1, если переключатель замкнут; х = 0, если переключатель разомкнут Переключатель Отрицание простейшего высказывания: = 0, если переключатель замкнут; = 1, если переключатель разомкнут Последовательное соединение: (схема замкнута, когда оба переключателя замкнуты) Конъюнкция высказываний: x Ù y Параллельное соединение: (схема разомкнута, когда оба переключателя разомкнуты) Дизъюнкция высказываний: x Ú y Схема, которая всегда разомкнута x Ù x Ù º 0 Схема, которая всегда замкнута x Ú x Ú º 1 Из простейших РКС путем их последовательного и параллельного соединения могут быть построены более сложные переключательные схемы. Доказано, что любая формула алгебры логики может быть преобразована к виду, содержащему только операции отрицания, конъюнкции и дизъюнкции. Это позволяет изображать логические формулы при помощи РКС, а РКС задавать формулами. Например, согласно формулам основных равносильностей x ® y º Ú y и x « y º (x ® y ) Ù (y ® x ), следовательно, логическим операциям импликации и эквиваленции соответствуют РКС, изображенные рис. 1. Используя равносильные преобразования логической формулы, соответствующей некоторой РКС, можно упростить РКС , т.е. привести ее к виду, содержащему меньшее число переключателей. Пример . Упростить РКС, изображенную на рис. 2. Решение. Запишем соответствующую РКС формулу, используя таблицу простейших РКС и соответствующих им формул логики: . Упростим формулу, используя основные равносильности: . Таким образом, . Построим РКС, соответствующую упрощенной формуле (рис. 3). 2. Булевы функции Будем рассматривать логические переменные x 1 , x 2 , …, xn , принимающие только два значения: «1» или «0». Булевой функцией f (x 1 , x 2 , …, xn ) называется произвольная функция, аргументами которой являются логические переменные и принимающая только одно из двух значений: «1» или «0». Количество булевых функций одного аргумента равно 22 = 4, это функции: f 1 (x ) = 0, f 2 (x ) =1, f 3 (x ) = x и f 4 (x ) = . Булевых функций двух аргументов всего 24 = 16, а количество булевых функций n аргументов равно . Всякой формуле алгебры логики, составленной из элементарных высказываний x 1 , x 2 , …, xn соответствует булева функция f (x 1 , x 2 , …, xn ), аргументы которой принимают значения истинности соответствующих элементарных высказываний: «1» или «0». Две равносильные формулы алгебры логики определяют одну и ту же булеву функцию, т.к. значения истинности этих формул совпадают для одинаковых значений входящих в них переменных. Для булевых функций можно составлять таблицы значений – всякую булеву функцию n аргументов можно задать таблицей из 2n строк. Например, таблица значений некоторых функций 2-х аргументов, соответствующих основным логическим операциям (отрицание одного аргумента, конъюнкция, дизъюнкция, импликация и эквиваленция) выглядит так: x 1 x 2 x 1 Ù x 2 x 1 Ú x 2 x 1 ® x 2 x 1 « x 2 1 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 Значение булевой функции f (x 1 , x 2 ) при известных значениях аргументов устанавливается по строке таблицы, соответствующей заданным значениям x 1 и x 2 . Например, для функции f (x 1 , x 2 ) = x 1 ® x 2 значение f (1, 0) = 0, а значение f (1, 1) = 1. Каждой релейно-контактной схеме (РКС), составленной из переключателей x 1 , x 2 , …, xn , можно поставить в соответствие булеву функцию, называемую ее функцией проводимости: Функция проводимости РКС задается при помощи формулы логики, соответствующей этой РКС. Например, РКС, изображенная на рис. 2, имеет функцию проводимости , таблица значений которой имеет вид: х y f (x, y ) 1 1 1 1 0 0 0 1 0 0 0 0 3. Графы 3.1. Основные определения Рассмотрим некоторое конечное множество точек V = {v 1 , v 2 ,…,vn } и конечное множество линий Х , соединяющих некоторые пары из точек множества V . Полученная совокупность точек и линий называется графом и обозначается G = {V , X }. Элементы множества V называются вершинами графа, а элементы множества Х – ребрами . Граф можно изобразить при помощи геометрической конфигурации. Вершины обозначаются точками (кружочками), а ребра – линиями, соединяющими соответствующие вершины (рис. 4). При этом несущественным является расположение вершин, форма и длина ребер графа, важно лишь, соединены две данные точки ребром, или нет. Ребра, соединяющие одну и ту же пару вершин, называются кратными (или параллельными ) ребрами (ребра х 4 , х 5 графа G 1 на рис. 4). Если х – ребро графа, соединяющее вершины vi , vj , то вершины vi и vj называются концами ребра х . Множество ребер графа Х можно задать, как множество пар вершин из множества V . Если пары в этом множестве Х являются упорядоченными, то граф называется ориентированным или орграфом . Ребра орграфа называют дугами и на рисунках помечают стрелками (рис. 4).