МИНИСТЕРСТВО ВНУТРЕННИХ ДЕЛ
РОССИЙСКОЙ ФЕДЕРАЦИИ
САНКТ-ПЕТЕРБУРГСКИЙ УНИВЕРСИТЕТ МВД РОССИИ
ИНФОРМАТИКА И МАТЕМАТИКА
КУРС ЛЕКЦИЙ
по дисциплине
ИНФОРМАТИКА И МАТЕМАТИКА
для курсантов и слушателей
САНКТ-ПЕТЕРБУРГ
2007
Содержание
ЧАСТЬ 1. ПРИКЛАДНАЯ МАТЕМАТИКА 4
Тема 1. Теория множеств и математическая логика 4
Лекция № 1/1. Элементы теории множеств и математической логики 4
Тема 2. Теория вероятностей 11
Лекция № 2/1. Основные понятия теории вероятностей 11
Тема 3. Математическая статистика 15
Лекция № 3/1. Основные понятия математической статистики 15
Тема 4. Теория графов и алгоритмов 20
Лекция № 4/1. Элементы теории графов 20
Тема 5. Моделирование социальных процессов 23
Лекция № 5/1. Основы моделирования социально-правовых процессов 23
Тема 6. ОСНОВНЫЕ ПОЛОЖЕНИЯ ОБЩЕЙ ТЕОРИИ СИСТЕМ 38
Лекция 6/1 “Основные положения общей теории систем” 38
Часть II Информатика 52
Тема 7. Аппаратное и программное обеспечения ПЭВМ 52
Лекция № 7/1. Аппаратное и программное обеспечение ПЭВМ 52
Тема 8. Электронные таблицы 65
Лекция № 8/1. Электронные таблицы 65
Тема 9. Информационные системы 77
Лекция № 9/1. Информационные системы 77
Тема 10. Экспертные системы 89
Лекция № 10/1. Экспертные системы 89
Тема 11. Информационно-вычислительные сети 100
Лекция № 11/1. Информационно-вычислительные сети 100
ЧАСТЬ 1. ПРИКЛАДНАЯ МАТЕМАТИКА Тема 1. Теория множеств и математическая логика Лекция № 1/1. Элементы теории множеств и математической логики
Основные вопросы, рассматриваемые на лекции:
1. Понятия множества и подмножества. Способы задания множеств.
2. Операции над множествами.
3. Понятия логического значения, высказывания и предиката.
4. Алгебра высказываний.
1. Понятия множества и подмножества. Способы задания множеств
В математике некоторые понятия являются первичными, неопределяемыми. К ним относятся понятия натурального числа, точки, прямой и т.д. Одним из таких неопределяемых понятий является понятие «множество». Этому понятию нельзя дать формального определения, которое не сводилось бы просто к замене слов «множество» его синонимами: «совокупность», «набор элементов», и т.п. В языках существуют различные обозначения множественности: птицы собираются в стаи, рыбы – в косяки; много людей – группа, марок – коллекция, фломастеров – набор и т.д. В математике аналог этого явления обозначается одним словом – множество, которое абстрагируется от содержания своих элементов. Можно говорить не только о множествах, элементами которых являются материальные объекты, но и о множествах, элементы которых – чисто абстрактные понятия (числа, геометрические фигуры, символы и т.п.).
Теория множеств – раздел математики, изучающий множества (это объект изучения), например, общие свойства множеств как абстрактных объектов (это – предмет).
Множество состоит из элементов (это единственно, что можно сказать о нем: не оговаривается количество и природа). Понятие «множество» не следует понимать буквально и толковать его как совокупность, содержащую «много» элементов. Оказывается удобным считать множеством даже пустое – содержащее ноль элементов.
Множества чаще всего обозначаются прописными буквами латинского алфавита A,B,... X, а их элементы – малыми буквами: а, b, ...x. Факт принадлежности элемента множеству записывается: а A. Пустое множество обозначается символом .
Множество считается заданным, если существует возможность для любого элемента выяснить принадлежность его к множеству. Имеется два существенно различных способа задания множеств. Можно либо указать правило для определения того, принадлежит или не принадлежит рассматриваемому множеству любой данный объект (описание), либо дать полный перечень элементов этого множества (перечисление). Например, одно и то же множество из четырех человек мы можем определить как участников музыкального квартета, или как людей по фамилиям Иванов, Петров, Сидоров и Романов.
Способы задания множеств
Перечислением A = {a1; a2; ... an} – указывается полный перечень элементов множества;
Описанием A={x : условие} – указывается правило для определения того, принадлежит или не принадлежит множеству объект. Например, множество попугаев в Антарктиде (сколько элементов?), {x : x < 1}.
Иногда кажется, что множество точно и четко определено некоторым описанием, хотя на самом деле это не так. Определим множество A следующим образом: оно состоит из всех натуральных чисел, каждое из которых удается описать при помощи не более двадцати слов русского языка («пять», «число, следующее после восьми», «наибольшее однозначное число, кратное четырем» и т.д.). Множество конечно, поскольку имеется лишь конечное число слов русского языка. Допустим, что n1, n2,... nk – элементы A. Возьмем m = n1 + n2 +...+ nk – «сумма всех натуральных чисел, которые можно определить с помощью не более двадцати русских слов». m A, поскольку также задается не более чем двадцатью словами, значит совпадает с одним из чисел n1, n2,... nk. С другой стороны, способ задания определяет, что m больше любого из элементов. Значит, множество A не задано корректно.
2. Операции над множествами
A
|
|
|
|
A
|
|
|
|
A
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B
|
|
|
|
B
|
|
|
|
B
|
|
|
|
|
|
Рис. 1
|
|
Рис. 2
|
|
Рис. 3
|
Рассмотрим пример: A – множество всех лиц, имеющих российское гражданство; B – множество лиц, имеющих белорусское гражданство.
Операция и ее свойства
|
Результат примера
|
A B – объединение множеств (Рис. 1) – множество, состоящее из всех элементов, которые входят ИЛИ в множество A, ИЛИ в множество B. AA=A, A=A.
|
Множество лиц, имеющих или российское или белорусское гражданство, граждане государства, получающегося при объединении двух.
|
A B – пересечение множеств (Рис. 2) – множество, состоящее из всех тех общих элементов, которые входят И в то И в другое множество. AA=A, A=.
|
Множество всех лиц, имеющих двойное гражданство, то есть и российское, и белорусское.
|
A \ B – разность множеств (Рис. 3) – множество всех тех элементов A, которые не входят в B. A\A=, A\=A, \A=, A\B=A\(AB).
|
Множество россиян, не имеющих белорусского гражданства.
|
Как видно из свойств операций, пустое множество играет роль аналогичную нулю в числовой алгебре, похожа на умножение, а - на сложение чисел.
Что является пересечение множества юношей и множества девушек учебной группы? Пустое множество, так как нет ни одного элемента, входящего в оба указанные множества. Если бы множества определялись, как множество интересов юношей и множество интересов девушек, то несомненно, что общие элементы нашлись бы.
Приведите пример множеств: A B = . В A – n элементов, в B – m, причем AB = . Сколько элементов в множествах A B и A B?
И
звестны площади (рис. 4) s(A), s(B), s(A B). Выразить через них s(A B).
s(A B) = s(A) + s(B) – s(A B).
Действительно, в сумму первых двух слагаемых площадь пересечения входит дважды. Справедлива ли эта формула для случая, когда s – мера, означающая количество элементов множества? Да, и справедлива вообще для любой меры, определенной на множествах – веса, длины, объема и т.д.
Множество решений системы уравнений или неравенств является пересечением множеств решений этих уравнений или неравенств. Решить графически систему неравенств:
y < x;
y > x2
AB – декартовое произведение множеств = {(a, b): a A, bB} – множество всех пар, первая компонента которых является элементом A, а вторая – B: AB BA.
Например, A = {номера вагонов в поезде}, B = {номера мест в вагоне}. AB = {(вагон, место) – места в поезде}. Другой пример: привычная запись времени – 10:40 является декартовым произведением множеств (каких?). Обобщая операцию, получим ABC – множество троек (a, b, c) и т.д. Важным случаем декартового произведения является произведение множества самого на себя: AA, AAA и т.д., которое обозначается в общем случае, как степень множества – An. Например, R3 – трехмерное декартовое пространство, каждый элемент которого – тройка вещественных чисел (x, y, z).
Задание. Множество A содержит n элементов, B – m элементов. Сколько элементов будет содержать множество AB?
Результат каждой операции является множеством, поэтому к нему также применимы множественные операции, например: (AB)C.
Как и в алгебре чисел, операции могут обладать некоторыми свойствами:
коммутативность: AB=BA; AB=BA;
ассоциативность: (AB)C=A(BC); (AB)C=A(BC);
дистрибутивность: (AB)C=(AC)(BC); (AB)C=(AC)(BC).
Пример некоммутативной операции в арифметике - «-», в теории множеств - «\».
Отношения между множествами
A = B – множества равны: A и B состоят из одних и тех же элементов.
B A – B подмножество A: все элементы множества B принадлежат множеству A. Похоже на отношение «<« для чисел.
B A – B подмножество A или они равны. Похоже на отношение «≤» для чисел.
Отметим, что отношение «<« определено только для числовых значений, например (рис. 7), нельзя писать, что C < B, но можно: s (C) < s (B) для различных мер.
В числовой алгебре две переменные (имеющие числовые значения) могут быть связаны некоторой функцией. Например, y = 2x-1. Иногда между двумя множествами также можно установить соответствие, т.е. ввести правило, по которому для каждого элемента одного множества указывается вполне определенный элемент или элементы другого множества. На основе понятия соответствия между множествами вводится понятие отображения множеств.
f: A B - отображение множества A в множество B – соответствие, при котором каждому элементу множества A отвечает единственный элемент множества B.
Например, для множества людей: каждому человеку можно поставить в соответствие число, соответствующее его росту. Любая мера на множествах – отображение множеств в множество чисел.
3. Понятия логического значения, высказывания и предиката
Математику от других областей знаний отличает наличие доказательств. Доказательства встречаются и в других сферах человеческой деятельности, например, в юриспруденции. Однако, в юриспруденции доказательства могут и оспариваются, в математике признаются эталоном бесспорности. Хотя, представления об убедительности доказательства меняются постоянно. Для средневековых судов доказательством невиновности служил факт, что человек мог удержать в руке раскаленное железо; если брошенная в воду связанная женщина не тонула, ее объявляли ведьмой.
Математическая логика исследует способы рассуждений и доказательств, применяемых в математике.
Предложения какого-либо языка могут являться описанием предметов, явлений или отношений, существующих, например, в реальном мире. При этом оказывается, что кроме своей структуры и смыслового содержания они различаются еще степенью соответствия их содержания описываемому объекту. В простейшем случае последняя характеристика сводится к тому, что они признаются либо истинными, либо ложными.
Объекты математической логики
1) логические значения - два абстрактных объекта: истина и ложь (могут иметь обозначения: да/нет, 1/0, белый/черный и т.д., в силу абстракции форма обозначения несущественна);
2) высказывание – языковое выражение (текст), которому можно приписать логическое значение;
3) предикат – высказывание, текст которого содержит предметные (обобщение числовых: значения – какие-либо объекты) переменные.
Фразам «Сколько времени?», «Иди ко мне!» приписать логические значения нельзя, они не могут рассматриваться как высказывания. Но определить логическое значение не всегда удается и для высказываний.
Определение логических значений высказываний
Эмпирически - на основе опыта: «Москва – столица России» (Истина);
Экспериментально – проверкой: «Кислород легче водорода» (Ложь);
Вычислениями - получаются по правилам математической логики;
Произвольно - «Через точку, лежащую вне прямой, можно провести только одну прямую, параллельную данной» (Истина). В этом случае ни эмпирически, ни экспериментально получить логическое значение нельзя. Не удается получить его и средствами математической логики, то есть доказательствами. Значение является допущением, которое привело к созданию евклидовой геометрии.
Для некоторых высказываний невозможно установить истинность: «ровно 1000 лет назад на территории города шел дождь». Естественный язык допускает грамматически правильные конструкции, которые выглядят как осмысленные утверждения, но о которых в принципе нельзя решить, истинны ли они.
Пример 1.
Утверждение в правой рамке – ложно
|
|
Утверждение в левой рамке – истинно
|
Пример 2. (Парадокс брадобрея). В деревне жил всего один брадобрей, который брил всех тех и только тех мужчин, которые не брились сами. Брил ли он самого себя? Кстати, это хороший пример абстрактности логики: здесь множество логических значений - {брил, не брил}, а приписываются они мужчинам.
4. Алгебра высказываний
Определены на высказываниях, результат также является высказыванием, таблицы определяют текст и логическое значение для результатов операций.
Операция
|
Текст предложения результата
(a – текст высказывания A, b – текст B)
|
AB Логическое умножение
|
a »И» b
|
AB Логическое сложение
|
a »ИЛИ» b
|
AB Импликация
|
«ЕСЛИ» a »ТО» b. Высказывание утверждает о следовании из одной ситуации другой и ложность его определена только для случая нарушения такого следования
|
A~B Эквивалентность
|
«ДЛЯ ТОГО, ЧТОБЫ» a «НЕОБХОДИМО И ДОСТАТОЧНО» b
|
A Отрицание
|
«НЕ» a
|
...
|
|
Сколько вообще может быть различных функций, определенных на двух значениях? Нетрудно подсчитать, что различных комбинаций четырех 0 и 1 в таблице может быть 16.
Результат каждой операции является высказыванием, поэтому к нему также применимы логические операции, при этом образуются выражения, например: (AB)C.
Отношения между высказываниями
AB - два высказывания называются равнозначными, если их логические значения равны, тексты не принимаются во внимание. Выберите для высказывания «Не уверен, что эта новость окажется для вас неприятной» равнозначное из следующих:
Уверен, что эта новость будет для вас приятной.
Уверен, что эта новость будет для вас неприятной.
Уверен, что эта новость не будет для вас приятной.
Похоже, эта новость будет для вас приятной.
Похоже, эта новость будет для вас неприятной.
Проверить, построив таблицу истинности для высказываний их равнозначность (тексты высказываний конечно не совпадают):
( A) A
A A A
A A A
A (B C) (A B) (A C)
A (B C) (A B) (A C)
|
A B (A B)
A B (A B)
A B A B
A B (A B) (B A)
|
Оказывается, некоторые операции (формулы 6-9) можно выразить в виде, содержащем только операции и ( и ). Это значит, что некоторое множество из N логических операций образует полную систему операций, которая позволяет построить остальные 16-N операций. Этим пользуются разработчики компьютеров, имеющие технические компоненты, реализующие 3-4 логические операции.
Предикат
P(x), P(x, y) и т.д. – предикаты, то есть высказывания, текст которых содержит переменные, определенные на множестве некоторых значений. Логическое значение предиката зависит от значений переменных. Например, «житель Санкт-Петербурга имеет высшее образование» при подстановке некоторых значений переменной «житель Санкт-Петербурга» будет высказыванием истинным, при остальных – ложным. «X < Y/2» при некоторых сочетаниях X и Y будет истинным, при некоторых – нет.
Над предикатом определены те же операции, что и над высказываниями. Если о некотором предикате известно, что он истинный, то мы можем дедуктивно порождать истинные высказывания, подставляя в него необходимые значения.
|
