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.  

 

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

28843. Культурно-историческая теория Л.С. Выготского 48 KB
  Филосовская основа – Марксизм: Считалось что Человек – природное существо но его природа социальна и поэтому человека его психику новообразования нужно рассматривались как продукт общественноисторического развития. Только в процессе общественной жизни человека возникли сложились и развились его новые потребности а самые природные потребности человека в процессе его исторической развития изменились. С точки зрения динамики развития он разделил детство на критические и литические периоды дав качественную характеристику кризисов....
28844. Психологическая теория деятельности. Виды деятельности 44 KB
  Психологическая теория деятельности. Виды деятельности. Именно он первым из психологов поставил вопрос о необходимости психологического изучения деятельности и человека как деятеля как субъекта деятельности ввёл в психологических обиход сам термин деятельность. Анализируя психологическое содержание поведенческого акта деятельности; действия он предпочитает рассматривать его с позиций известной бихевиористической схемы S – R.
28845. Развитие детской и дифференциальной психологии в советской России 66 KB
  привели к необходимости развития отечественной науки. Басов заложил основы нового понимания механизмов психического развития которые были развиты в концепции Выготского. Выготский впервые перешел от утверждения о важности среды для развития к выявлению конкретного механизма этого влияния среды который собственно и изменяет психику ребенка приводя к появлению специфических для человека высших психических функций ВПФ. При этом знаки будучи продуктом общественного развития несут на себе отпечаток культуры того социума в котором растет...
28846. История психологии как наука 52 KB
  История психологии как наука Предмет История психологии – это особая отрасль знания имеющая собственный предмет. Его нельзя смешивать с предметом самой психологии как науки. В истории психологии изучается не сама психическая реальность а представления о ней какими они были на разных этапах развития науки. История психологии описывает и объясняет как эти факты и законы открывались.
28847. Психологические учения античности 66 KB
  Психологические учения античности Понимание души в донаучных представлениях о переселении душ орфической и тотемной религии их влияние на античную психологию: понятия анимизма гилозоизма. Деятельность животного или человека объясняется присутствием этой души а его успокоение во сне или в смерть ее отсутствием; сон или транс временное а смерть постоянное отсутствие души. анима душа дух одухотворение окружающего мира утверждение что за всеми явлениями реальности живыми и неживыми стоят духи души. Начало понимания связи...
28848. Характеристика психологических учений средневековья 67 KB
  Главное качество души – единство ввёл принцип холизма душа и разум едины. Бог – поставляет в мировой разум идеи – душа получает идеи и передает человеку в материю – материя чувственный мир. Душа – производит все живые существа вдохнув в них жизнь. Душа человека находится в связи с Душой божественной и чувственным миром.
28849. Особенности психологических воззрений в новое время 55 KB
  встаёт проблема соотношения физического и психического опыт – становится основным методом изучения природы в том числе и человека. Задача науки – это покорение природы и усовершенствование человека. Он отверг душу как силу организующую поведение и управляющую им открыв путь к объективному изучению явлений органической природы. интуитивное знание – истинное объективное содержаться в разуме и открываются интуитивно Спиноза утверждал существование единой неделимой и вечной субстанции преодоление дуализма Декарт – Бога или Природы.
28850. Развитие эмпирической психологии в новое время 64.5 KB
  Особенности развития психологии: предмет и метод исследования Основными чертами психологии в 17 19 веке становятся: представление о живом теле в том числе о человеке как о механистической системе которая не нуждается в душе Вспомним принцип бритвы оккама который стал ведущим в психологии нового времени – ничего лишнего уточнение предмета психологии которая становилась наукой о сознании основные проблемы которые изучала психология: проблема познания содержание и функции сознания а также страстях и аффектах – как одних из...
28851. Психологические идеи Г. Лейбница 40.5 KB
  Таким образом он не признавал учение Спинозы о единой субстанции душа и тело едины и говорил о существовании множества субстанций – монад замкнутые нематериальные целостности – духовная субстанция обладающая психической активностью то из чего состоит весь мир человек душа Основные свойства монады: восприятие перцепция и стремление Виды монад: 1. Лейбниц считал что душа и тело совершенно не зависят друг от друга и функционируют по разным законам хотя и действуют так что создается впечатление их взаимосвязи. Душа и тело...