19842

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

Лекция

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

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

Русский

2013-07-18

214.5 KB

4 чел.

Лекция 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.  

 

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

64296. МЕТОДИКА ВИРОБНИЧОГО НАВЧАННЯ МАЙБУТНІХ КРАВЦІВ У ПТНЗ ЗАСОБАМИ ІНТЕГРОВАНИХ МІКРОМОДУЛІВ 269.5 KB
  Основи створення методичних систем виробничого навчання та підвищення ефективності професійної підготовки кваліфікованих робітників розроблено в працях В. Перспективним напрямком інтеграції при створенні методичних систем навчання є використання модульного та мікромодульного...
64297. ВУГЛЕПЛАСТИКИ ТРИБОТЕХНІЧНОГО ПРИЗНАЧЕННЯ НА ОСНОВІ ФТОРОПЛАСТУ-4 ТА МОДИФІКОВАНОГО ВУГЛЕЦЕВОВОЛОКНИСТОГО НАПОВНЮВАЧА 197.5 KB
  Сучасна тенденція розвитку полімерного матеріалознавства полягає у пошуку раціональних шляхів використання відомих матеріалів шляхом модифікування їх властивостей.
64298. ОРГАНІЗАЦІЯ ДОСЛІДНИЦЬКОЇ ДІЯЛЬНОСТІ УЧНІВ З ДИЗАЙНУ У ПРОФЕСІЙНИХ НАВЧАЛЬНИХ ЗАКЛАДАХ ХУДОЖНЬОГО ПРОФІЛЮ 271.5 KB
  За нинішніх умов соціально-культурного розвитку суспільства дизайн як новий вид художньо-конструкторської професійної діяльності відіграє важливу роль у створенні цілісного естетичного середовища, підвищенні рівня конкурентоспроможності промислової продукції, предметів широкого вжитку.
64299. ВІДБІР БАСКЕТБОЛІСТІВ НА ЕТАПІ ПОЧАТКОВОЇ ПІДГОТОВКИ З УРАХУВАННЯМ ЇХ ОСОБИСТІСНИХ ОСОБЛИВОСТЕЙ 156 KB
  Матеріали стосовно особистісних особливостей баскетболістів що є значущими на етапі початкової підготовки В. Наявні критерії первинного відбору баскетболістів не повною мірою...
64300. ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ОПТИЧНИХ МУЛЬТИСЕРВІСНИХ МЕРЕЖ З ВИКОРИСТАННЯМ КОДОВОГО РОЗДІЛЕННЯ КАНАЛІВ 849 KB
  Інтенсивний розвиток телекомунікаційних послуг сьогодні вимагає якісних змін і підходів до побудови телекомунікаційних мереж. Нові підходи повинні враховувати велику пропускну здатність оптичних мереж та гнучкість топологічних рішень мультисервісних мереж...
64301. ПРОДУКТИВНІСТЬ ПШЕНИЦІ ЯРОЇ ТВЕРДОЇ ЗАЛЕЖНО ВІД ЕЛЕМЕНТІВ ТЕХНОЛОГІЇ ВИРОЩУВАННЯ В ПРАВОБЕРЕЖНОМУ ЛІСОСТЕПУ УКРАЇНИ 391.5 KB
  Створення та впровадження у виробництво сортів пшениці твердої з високим рівнем генетичного потенціалу продуктивності адаптованих до конкретних ґрунтовокліматичних умов розширює перспективи виробництва зерна пшениці твердої ярої особливо...
64302. ПІДВИЩЕННЯ ЕКСПЛУАТАЦІЙНОЇ НАДІЙНОСТІ ТРУБНИХ І ШТАНГОВИХ КОЛОН ДЛЯ БУРІННЯ ТА ВИДОБУВАННЯ НАФТИ І ГАЗУ 3.89 MB
  Проблема підвищення експлуатаційної надійності трубних і штангових колон для буріння та видобування нафти та газу нерозривно повязана з проблемою оцінки їх навантажування. Особливістю роботи елементів трубних і штангових колон є надзвичайно складний характер навантажування...
64303. ЕКОНОМІЧНА ВЛАДА ЯК ФАКТОР РОЗПОДІЛУ ДОХОДІВ 328.5 KB
  Процес розподілу доходів є складною соціальноекономічною проблемою оскільки зачіпає інтереси всіх економічних суб'єктів. Економічне та соціальне значення проблеми розподілу доходів зумовлено впливом на рівень стимулювання продуктивної економічної поведінки макроекономічну рівновагу соціальну напруженість.
64304. КОНЦЕПЦІЯ ІНФОРМАЦІЙНОГО РОЗВИТКУ ТРАНСПОРТНИХ СИСТЕМ 308 KB
  Транспортні системи, технології, машини, шляхи сполучення та багато інших підсистем та ланок, що забезпечують надання транспортних послуг населенню та організаціям, можна визначати як багаторівневу транспортну інфраструктуру.