новая папка 1 / 270324
.pdfМИНИСТЕРСТВО ОБРАЗОВАНИЯ САРАТОВСКОЙ ОБЛАСТИ
государственное автономное профессиональное образовательное учреждение Саратовской области
«Саратовский архитектурно-строительный колледж»
«Утверждаю» зам. директора по учебной работе
Муравьёва О.И.______________
______________________2014 г.
Учебное пособие опорный конспект лекций для студентов по изучению
Раздела 2.Основы дискретной математики
дисциплины «Математика» для специальности среднего профессионального образования
270802.52 «Строительство и эксплуатация зданий и сооружений» на базе среднего общего образования
Саратов, 2014
Рассмотрено |
Одобрено |
на заседании комиссии |
методическим советом |
математических и естественнонаучных |
ГАПОУ СО «САСК» |
дисциплин |
протокол № _______ |
Председатель ПК |
Председатель_______________ |
______________ /Дерябина Н.И./ |
|
Разработал преподаватель математики ГАПОУ СО «САСК» Дерябина Н.И.
Цель методического пособия
Последнее время вопросу совершенствования преподавания математики уделяется большое внимание. Разрабатываются новые, более эффективные методы преподавания математики, совершенствуются формы организации уроков. Современный поток научно-технической информации настолько велик, что его всё труднее охватить учебными программами и довести до сознания студента за достаточно короткий срок обучения. Основа современной организации учебного процесса – самостоятельная работа студентов. Перенос центра тяжести на самостоятельную работу обучающихся требует коренных изменений в методике преподавания.
С таких позиций подготовлено данное методическое пособие, представляющее собой опорный конспект, который включает в себя теоретический материал, примеры решения задач, вопросы для контроля.
Содержание |
|
1.Понятие множества. |
4 |
2.Способы задания множеств. |
4 |
3.Подмножества. |
4 |
4.Операции над множествами. |
5 |
5.Абстрактные законы операций над множествами. |
6 |
6.Вопросы для контроля. |
7 |
7.Элементы математической логики. Введение |
8 |
8.Логические операции над высказываниями. |
9 |
9. Вопросы для контроля |
12 |
10. Основные формулы и определения |
13 |
11.Рекомендуемая литература |
14 |
1. Понятие множества
Понятие множества является базисом современной математики, теория множеств – её фундамент.
Под множеством понимают объединение в одно общее объектов, хорошо различаемых нашей интуицией или нашей мыслью. Таково интуитивное определение понятия множества, данное основателем теории множеств Георгом Кантором. Это понятие в математике является первичным и, следовательно, не имеет строгого определения. Например: множество студентов колледжа, множество аудиторий, N - множество натуральных чисел, R - множество действительных чисел, Z - множество целых чисел. Объекты, составляющие множества, будем называть его элементами. Множества обозначаются прописными буквами латинского алфавита: А, В, С,…, а элементы множеств – строчными буквами: а, в, с,… . а А (а принадлежит А).
Если а не является элементом множества А, то пишут а А (а не принадлежит А).
2. Способы задания множеств
Множества можно задавать двумя способами: указать правило для определения того, принадлежит или не принадлежит рассматриваемому множеству данный объект, либо дать полный перечень элементов этого множества.
Первый способ назовём описанием множеств, а второй перечислением множеств. Примеры записи вторым способом: { 1,2,3,… } - множество натуральных чисел (под многоточием подразумеваются все последующие натуральные числа;
{ 0,1 } - значения корней уравнения х2 - х =0.
3. Подмножества
Множество, состоящее из некоторых элементов другого множества, называется подмножеством этого последнего множества.
Введём терминологию. Исходное множество будем называть универсальным множеством; подмножества, содержащие один элемент – единичными множествами; множество, не содержащее никаких элементов – пустым множеством и обозначать Ø .
Пример. Возьмём универсальное множество U, состоящее из трёх элементов { a,b,c} . Собственные подмножества U – это множества, которые содержат некоторые, но не все элементы U. Этими подмножествами являются три множества из двух элементов {a,b },
{a,c} , {b,c } и три единичных множества { a , b , c}. Подмножеством U является и пустое множество Ø , не содержащее элементов U.
Другими словами, множество А называется подмножеством множества В (обозначаем А В), если все элементы множества А принадлежат В. Тогда справедливо утверждение: для
любого элемента а, если а А, то а В при условии А В. Говорят, что множество А содержится в В или имеется включение множества А в В. Множества А и В называют равными или совпадающими (А = В), если они состоят из одних и тех же элементов, т. е. А В и В А. Таким образом, чтобы доказать равенство множеств, требуется установить два включения.
4
4. Операции над множествами
Чтобы нагляднее представить эти операции, изобразим их на диаграмме, называемой диаграммой Эйлера – Венна. Здесь прямоугольник обозначает универсальное множество, а круги внутри прямоугольника – подмножества.
Дополнением к множеству А называется множество элементов, которые не содержатся в А. Обозначают его А и читают «дополнение множества А к U».
Пересечением множеств А и В называется множество элементов, принадлежащих и А и В, Обозначают А В и читают «пересечение А и В».
Если А и В непустые множества, пересечение которых пусто, т. е. А В = Ø, то их называют непересекающимися множествами.
Объединением множеств А и В называется множество элементов, принадлежащих либо А, либо В (либо обоим). Обозначают А U В и читают «объединение А и В».
5
Разностью множеств А и В называется множество элементов, принадлежащих А и не принадлежащих В. Обозначают А \ В и читают «разность А и В».
Например,
если А= { 1,2,3,4 }, В= {1,2 }, то А \ В={ 3,4 }; если А= { 1,2,3 }, В={ 3,4,5,6 }, то А \ В={ 1,2 }; если А= { 1,2,5 }, В={ 3,4 }, то А \ В={ 1,2,5 }; если А= { 1,2}, В={ 1,2,3 }, то А \ В= Ø .
5. Абстрактные законы операций над множествами
Введённые операции над множествами подчинены некоторым очень простым абстрактным законам.
Эти законы очень напоминают элементарные законы алгебры высказываний.
По этой причине множество, его подмножества и законы сочетания подмножеств образуют алгебраическую систему, называемую булевой алгеброй. Система составных высказываний, подчиняющаяся таким законам, тоже называется булевой алгеброй. Таким образом любую из этих систем можно изучать или с алгебраической, или с логической точки зрения. Ниже перечислены основные законы, действующие в булевых алгебрах.
|
|
Законы для объединения и пересечения: |
||||||
1. |
A A = A |
|
|
|
|
|
7. A (B C) = (A B) (A C) |
|
2. |
A A = A |
|
|
8. A (B C) = (A B) (A C) |
||||
3. |
A B = B A |
|
|
9. A U = U |
||||
4. |
A B = B A |
|
|
10. A = |
||||
5. |
A (B C) = (A B) C |
|
11. A U = A |
|||||
6. |
A (B C) = (A B) C |
|
12. A = A |
|||||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
||
|
|
Законы для дополнений: |
||||||
1. |
= |
|
___ |
_ |
|
_ |
|
_ |
|
|
|
||||||
A = A |
4. (A B) = A B |
|
|
|
||||
2. |
A A = U |
5. (A |
B) = A |
|
B |
_ |
|
_ |
|
||||||||
3. |
A A = |
6. U = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6
|
|
|
|
|
_ |
Законы для разностей множеств: |
|
|
|
|
|
|
|
||
1. |
A \ B = A B |
6. A \ A = |
|||||
|
|||||||
2. |
U \ A = |
A |
_ |
|
7. ((A \ B) \ C) = A \ (B C) |
||
3. |
A \ U = |
|
8. A \ (B \ C) = (A \ B) (A C) |
||||
4. |
A \ = A |
|
9. A (B \ C) = (A B) \ (C A) |
||||
5. |
\ A = |
|
10. A (B \ C) = (A B) \ (A C) |
||||
|
|
|
|
|
|
|
|
Докажем один из законов для дополнений: А U В = А В
Пусть х А U В, по определению операции дополнения это означает, что х А U В, х U.Следовательно, х А и одновременно х В. Таким образом, х А и х В. Из определения операции пересечения получаем, что х А В. Поэтому, учитывая произвольность элемента х А U В, имеем А U В А В.
Пусть теперь х А В. Это означает, что х А и одновременно х В. Таким образом, х А и х В. Поэтому х А U В. Следовательно, х U \ (А U В) = (А В).
Поскольку х- произвольный элемент из А В, тл окончательно получаем А U В А В. Приходим к выводу, что А U В = А В
6.Вопросы для контроля
1.Какими способами можно задать множество?
2.Какие множества называются равными?
3.Что называется подмножеством данного множества?
4.Какое множество называется пустым?
5.Что называется пересечением множеств?
6.Какие множества называются непересекающимися?
7.Что называется объединением множеств?
8.Что называется разностью множеств?
9.Что называется дополнением множеств?
10.В каком случае разность А\В есть дополнение множества В до множества А ?
7
7. Элементы математической логики
ВВЕДЕНИЕ
Математическая логика представляет собой область математики, изучающую различные способы логических рассуждений с помощью математических методов.
Родоначальником науки о логике является греческий философ Аристотель (384-322г. до н. э.). Он, используя законы человеческого мышления, формализовал известные до него правила рассуждений. Лишь в конце XVII века немецкий математик Г. Лейбниц предложил математизировать формальные рассуждения Аристотеля, вводя символьное обозначение для основных понятий и используя особые правила, близкие к вычислениям. Лейбниц утверждал, что “мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, чтобы облегчить сам процесс нашего мышления”.
Применение математики в логике определило новую науку - математическую логику. Математическое описание рассуждений позволило получить точные утверждения и эффективные процедуры в решении конкретных задач логики. Рассуждения в математической логике изучаются с точки зрения формы описания процесса, явления или события и формального преобразования этого описания. Такой процесс называют выводом заключения Иногда математическое описание рассуждений называют логико - математическим моделированием.
Основными объектами при изучении математической логики являются формальный язык логики и правила вывода. Формальный язык необходим для символьного описания процессов, явлений или событий и логических связей между ними. Правила вывода необходимы для формирования процедуры рассуждения. Для обеспечения вывода вводится система аксиом, формализующая весь механизм вывода заключения.
Математическое описание логики следует воспринимать, как некую формальную систему, оперирующую с символами по определенным правилам, облегчающим интерпретацию в реальном мире.
Выделяют несколько типов математических моделей формальной логики. Среди них можно выделить Логику высказываний, Логику предикатов, Логику нечетных множеств и отношений, Реляционную логику и др.
Логика высказываний (prepositional calculus) есть модель формальной системы, предметом которой являются высказывания или повествовательные предложения, взятые целиком без учета их внутренней структуры
Логика предикатов (predicate calculus) есть модель формальной системы, предметом которой являются повествовательные предложения с учетом их внутренних состава и структура
Логика нечетных множеств и отношений (fuzzy calculus) есть модель формальной системы, предметом которой являются повествовательные предложения с учетом их внутреннего состава и структуры и при нечетком (размытом) задании характерных признаков отдельных элементов или отношений между ними.
Логика реляционная (relation calculus) есть модель формальной системы, предметом которой являются отношения в виде множества однородных повествовательных предложений, существенно расширяющие логику предикатов.
Математическая логика является разделом дискретной математики, в котором, в частности, формальными методами изучаются высказывания. Широкое применение кроме самой математики этот её раздел получил при анализе и синтезе логических схем входа и выхода данных в компьютерах и других цифровых устройствах, в частности: связи, видео- и фотоаппаратуры и др.
8
Определение.
Любое предложение, о смысле которого можно сказать, истинно оно или ложно, называется
высказыванием.
Пример: Предложение « Я иду на занятия» является высказыванием, а предложения «Который час?», « Куда ведёт эта дорога?» высказываниями не являются.
«Река Волга впадает в Каспийское море» - высказывание истинно «Лондон – столица России» - высказывание ложно «Число 9 делится на 3» - высказывание истинно.
Высказывания, представляющие собой одно утверждение, называются простыми, или элементарными. Из элементарных высказываний по определённым логическим правилам
составляют сложные высказывания. |
|
Элементарные высказывания обозначают латинскими буквами A, B, C, |
X, Y, Z,… |
Истинные значения высказываний обозначаются буквой И или цифрой 1, а ложные - буквой Л или цифрой 0.
Рассмотрим простейшие логические операции (связки), позволяющие строить сложные высказывания из элементарных.
8. Логические операции над высказываниями
Конъюнкция (операции «и», логическое произведение) двух элементарных высказываний А и В – новое высказывание, которое считается истинным, если оба высказывания А и В истинны и ложным – во всех других случаях. Обозначается А ٨ В и читается « АиВ»
Логические значения конъюнкции описываются таблицей истинности:
А |
В |
А ٨ В |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
. Пример Даны высказывания: A: «Компьютер содержит основной микропроцессор»
B: «Компьютер содержит оперативную память»
С: «Компьютер содержит контроллеры»
D: «Компьютер содержит порты ввода-вывода»
Тогда формула F= (A٨B٨C٨D) отражает высказывание «Компьютер содержит основной микропроцессор», «оперативную память», «контроллеры» и «порты ввода-вывода»
9