19842

Понятие компьютинга и дискретной математики

Лекция

Математика и математический анализ

Лекция 1 Понятие компьютинга и дискретной математики Компьютинг computing – это широкая область знаний которая не может быть сведена к рамкам какойлибо из составляющих ее дисциплин. Основы компьютинга включают в себя основы информатики и математики необходимые для п

Русский

2013-07-18

214.5 KB

3 чел.

Лекция 1

Понятие компьютинга и дискретной математики

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

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

Программная инженерия, как наука, обладает рядом особенностей:

Основанием программной инженерии является информатика, а не естественные науки.

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

управление производится абстрактными/логическими объектами вместо конкретных/физических установок.

Отсутствие «производственной» фазы в традиционном промышленном смысле.

«Сопровождение» программного обеспечения, в основном, связано с продолжающейся разработкой или эволюцией, а не с традиционным физическим износом.

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

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

Теория множеств

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

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

Такой подход называется аксиоматическим [1].

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

Основные понятия теории множеств

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

Элементы множества обозначаются маленькими латинскими буквами, сами множества- заглавными. Например, чтобы показать, что элемент a принадлежит множеству A, мы пишем , в противном случае .

Во множество можно объединять самые разные объекты. Например, множество натуральных чисел N, множество целых чисел Z, множество действительных чисел R, множество предметов в вашей комнате W, и т.д. Элементами множества могут выступать другие множества, например D= {{синий, красный, зеленый}, {шар, куб, цилиндр, пирамида}}. Такое множество D  называется классом или семейством [2] .

Количество элементов во множестве называется мощностью, или кардинальным числом. Например, мощность множества M={a,b,c} - M│=3. В зависимости от мощности, множества могут быть конечные и бесконечные. Множество, в состав которого не входит ни одного элемента, называется пустым и обозначается . Мощность пустого множества равна 0, . Но мощность множества С, элементом которого является пустое множество, равна единице, .

Множества равномощны, если их мощности равны. Например, множества D= {{синий, красный, зеленый}, {шар, куб, цилиндр, пирамида}} и  К={a,b} равномощны.

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

Если каждому элементу бесконечного множества можно поставить в соответствие натуральное число , причем, только одно , без пропусков и повторений, то это множество называется счетно-бесконечным и его мощность равна  (алеф-нуль), первому трансфинитному числу. Второе трансфинитное число 2 À0, алеф-один, равно мощности множества R действительных чисел. Известно и третье трансфинитное число 2^2 À0,, алеф-два, равное множеству точек в пространстве, заданных координатами (x, y, z). Трансфинитные числа обозначают буквами еврейского алфавита.

Свойства  трансфинитных чисел определяются следующим образом:

  1.  À0 00;
  2.  À000 ;

Кантор создал шкалу трансфинитных чисел: À0, 2 À0, 2^2 À0, ….

Считаем, что множество счетно, если оно состоит из конечного числа элементов, т.е. его кардинальное число совпадает с одним из натуральных чисел, или это множество счетно-бесконечное. Множество  несчетное, если оно  бесконечно и  неравномощно множеству натуральных чисел.

Множество A называется подмножеством B, если каждый элемент  из A, , принадлежит одновременно и множеству B, ,  .

Если во множестве B найдется хотя бы один элемент , который не принадлежит A , ,  то A собственное подмножество B,  . Пустое множество всегда является подмножеством любого множества B.

Множество B в приведенных выше определениях часто называют надмножеством (собственным надмножеством) множества A.

Множества A и B равны, если являются подмножествами  (надмножествами) друг друга.

Для каждого множества М можно построить новое множество, элементами которого являются все подмножества М и только они. Тогда множество М называют универсумом I, а множество всех его подмножеств – булеаном.

Например, возьмем в качестве универсума I множество натуральных чисел на отрезке [1, 3], I={1, 2, 3}, тогда булеан  B(I)={,{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. Если мощность универсума равна m, то мощность его булеана всегда .

Теорема (основная теорема о конечных множествах)

Любое конечное множество не может быть эквивалентно никакому своему собственному подмножеству

При определении множеств и подмножеств можно столкнуться с парадоксом Рассела, который заключается в следующем. Рассмотрим множество A всех множеств B, не содержащих себя в качестве элементов, . Если множество В существует, то содержит ли В в качестве элемента самого себя, т. е. ? При ответе на этот вопрос мы сталкиваемся с логическим противоречием: если , то по определению элементов множества . Если , то .

Способы задания множеств

Для задания множеств необходимо указать элементы, которые ему принадлежат. Это можно сделать следующим образом [3]:

  •  Перечислить элементы множества, M= {1, 2, 3, 4, 5}
  •  Использовать характеристический предикат M= {x / xN и x<6}
  •  С помощью производящей функции M= {x / for I:=1 to 5 do x:= i}

Операции над множествами определяются на некотором универсуме I. К ним относятся объединение, пересечение, дополнение, разность и симметрическая разность.

Объединением двух множеств А и B называется новое множество С, элементы которого удовлетворяют следующему условию:

.

Пересечением двух множеств A и B называется новое множество C, элементы которого удовлетворяют следующему условию:

.

Дополнением множества A называется новое множество C, элементы которого удовлетворяют следующему условию:

.

Разностью  двух множеств A и B  называется новое множество C, элементы которого удовлетворяют следующему условию:

.

Симметрической разностью  двух множеств A и B называется новое множество C, элементы которого удовлетворяют следующему условию:

.

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

 

А) Б) В)Г)  Д)

Рис.1.  Диаграммы Эйлера-Венна

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

Перечисленные операции получили название теоретико-множественных операций.

Задача 1

Даны множества  I={1, 2,  3, 4, 5, 6, 7, 8, 9},  A={1, 3, 5, 7, 9}, B={1, 2, 3, 8, 9},

C= {2, 3, 5, 6, 9}.

 Найти:

Решение

Учитывая старшинство операций, получаем:

 

Свойства операций над множествами

Идемпотентность

Коммутативность

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

Дистрибутивность

Поглощение

Действия с универсумом

Действия с пустым множеством

Свойства дополнения

Двойное дополнение

Законы де Моргана

Выражение для разности

Выражение для симметрической разности

Результаты всех этих операций над подмножествами универсума I дают также подмножества I. По этой причине мы вправе с помощью рассмотренных операций определить алгебры A на I.

Под алгеброй A=<M, S> понимается совокупность множества М с заданными на нем операциями S={O1, O2, . . . ,On}.

Алгебра A=< B(I);> называется алгеброй Кантора, на ней выполняются законы: идемпотентность, коммутативность, ассоциативность, дистрибутивность, поглощение, действия с универсумом, действия с пустым множеством, свойства дополнения, двойное дополнение, законы де Моргана.

Задача 2

С помощью законов алгебры Кантора упростить выражения:

Решение

_________________

Аксиоматика теории множеств

Современная теория множеств использует  систему аксиом (утверждений), принимаемых без доказательства, из которых выводятся все теоремы и утверждения теории множеств.

Система аксиом Цермело — Френкеля (ZF) является стандартной системой аксиом для теории множеств. К этой системе аксиом часто добавляют аксиому выбора, и называют системой Цермело- Френкеля с аксиомой выбора (ZFC).

1. Аксиома объёмности. Два множества A и B равны тогда и только тогда, когда они имеют одни и те же элементы.

2. Аксиома существования пустого множества. Существует множество без единого элемента. Это множество обычно обозначается {} или .

3. Аксиома объединения. Для произвольного множества A и произвольного множества B существует и причем единственное  множество С, называемое объединением множества A и B, состоящее из тех и только тех элементов, которые содержатся в множестве А или в множестве B.

4. Аксиома основания. Каждое непустое множество S содержит элемент a такой, что .

5. Аксиома множества подмножеств. Для любого множества  A существует множество B, состоящее из тех и только тех элементов, которые являются подмножествами множества A. Множество подмножеств множества  A обозначается B(A) (булеан).

6. Схема выделения. Любому множеству  A и свойству  отвечает множество B, элементами которого являются те и только те элементы a, которые обладают свойством . Схема выделения содержит счётное количество аксиом, так как каждая формула логики первого порядка порождает аксиому.

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

8. Аксиома выбора. Для любого семейства попарно непересекающихся непустых множеств существует множество c такое, что, каково бы ни было множество x данного семейства, множество состоит из одного элемента.

9. Аксиома бесконечности. Существует хотя бы одно бесконечное множество – множество натуральных чисел N.

Далее введём определение: множество называется индуктивным, если оно

а) содержит пустое множество

б) содержит последователь (то есть элемент ) каждого своего элемента. Аксиома бесконечности утверждает, что индуктивные множества существуют.

Непротиворечивость приведённой аксиоматики на настоящий момент не установлена.

Метод включения-исключения и его применения (оценки для числа элементов, ни обладающих, ни одним из свойств; формула для числа элементов, обладающего в точности p свойствами).

Литература

  1.  Лихтарникова Л.М., Сукачева Т.Г. Математическая логика/Курс лекций. - СПб.: Издательство «Лань», 1998.-288с.
  2.  Горбатов В.А. Фундаментальные основы дискретной математики. -  М.: Наука. Физматлит, 1999.-544с.
  3.  Новиков Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2001. – 304с.
  4.  Капитонова Ю.В., Кривой С.Л., Летичесвский А.А., Луцкий Г.М. Лекции по дискретной математике. – СПб.: БХВ-Петербург, 2004. – 624 с.

7


1

1

1

1

  1.  

 

А также другие работы, которые могут Вас заинтересовать

71573. Підстави набуття та припинення права власності 109.5 KB
  ЦК України право власності набувається на підставах що не заборонені законом зокрема із правочинів. Романович розрізняє поняття способів і підстав набуття права власності. Так способи набуття права власності –- це сукупність подій і обставин які чітко передбачені в законі...
71574. Речові права на чуже майно 84 KB
  Право користування чужим майном сервітути за новим законодавством України Вісник Львівського університету. 395 ЦК України речовими правами на чуже майно є: 1 право володіння; 2 право користування сервітут; 3 право користування земельною ділянкою для сільськогосподарських потреб емфітевзис...
71575. Право власності окремих суб’єктів права. Право приватної власності фізичних осіб 43 KB
  Підстави виникнення та припинення права власності фізичних осіб. Зміст і здійснення фізичними особами права приватної власності. Деякі аспекти застосування цивільного законодавства при здійсненні права власності подружжя Юридична Україна.
71576. Право спільної власності 58.5 KB
  Для спільної власності характерною є множинність суб’єктів права власності. Такі суб’єкти є учасниками спільної власності, співвласниками. Оскільки відносини між ними виникають щодо одного об’єкта, що є у спільній власності, тому існує необхідність їхнього правового регулювання.
71577. Цивільно-правові засоби захисту права власності 64.5 KB
  Цивільноправові засоби захисту права власності Основні засади захисту права власності. Система цивільноправових засобів захисту права власності. Позов про визнання права власності Позов про виключення майна з опису звільнення зпід арешту.
71578. Право власності на житло 121 KB
  З часу проголошення Україною незалежності пріоритетним напрямком її державної економічної політики став розвиток права приватної власності на житло. Становленню системи нормативноправових актів у сфері регулювання права власності на житло сприяло прийняття Цивільного та Земельною кодексів...
71579. Право комунальної власності 30.5 KB
  Право комунальної власності. Поняття суб’єкти та об’єкти права комунальної власності. Підстави виникнення права комунальної власності. Здійснення права комунальної власності.
71581. ВАКУМНОЕ НАПЫЛЕНИЕ (ВН) ПОКРЫТИЙ 207.5 KB
  ВН -– группа методов объединённых общим принципом создания при пониженном давлении поНД потока корпускулярных частиц атомы молекулы ионы и их осаждения на напыляемой поверхности Пв НП. При этом должно быть обеспечено отсутствие в потоке напыляемых частиц НЧ конденсированной фазы...