close

Вход

Забыли?

вход по аккаунту

?

471.Учебное пособие опорный конспект лекций для студентов по изучению Раздела 2

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
МИНИСТЕРСТВО ОБРАЗОВАНИЯ САРАТОВСКОЙ ОБЛАСТИ
государственное автономное профессиональное образовательное учреждение
Саратовской области
«Саратовский архитектурно-строительный колледж»
«Утверждаю»
зам. директора по учебной работе
Муравьёва О.И.______________
______________________2014 г.
Учебное пособие
опорный конспект лекций для студентов по изучению
Раздела 2.Основы дискретной математики
дисциплины «Математика»
для специальности среднего профессионального образования
270802.52 «Строительство и эксплуатация зданий и сооружений»
на базе среднего общего образования
Саратов, 2014
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рассмотрено
на заседании комиссии
математических и естественнонаучных
дисциплин
Председатель ПК
______________ /Дерябина Н.И./
Одобрено
методическим советом
ГАПОУ СО «САСК»
протокол № _______
Председатель_______________
Разработал
преподаватель математики ГАПОУ СО «САСК» Дерябина Н.И.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Цель методического пособия
Последнее время вопросу совершенствования преподавания математики уделяется большое
внимание. Разрабатываются новые, более эффективные методы преподавания математики,
совершенствуются формы организации уроков. Современный поток научно-технической
информации настолько велик, что его всё труднее охватить учебными программами и довести до
сознания студента за достаточно короткий срок обучения. Основа современной организации
учебного процесса – самостоятельная работа студентов. Перенос центра тяжести на
самостоятельную работу обучающихся требует коренных изменений в методике преподавания.
С таких позиций подготовлено данное методическое пособие, представляющее собой
опорный конспект, который включает в себя теоретический материал, примеры решения задач,
вопросы для контроля.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание
1.Понятие множества.
2.Способы задания множеств.
3.Подмножества.
4.Операции над множествами.
5.Абстрактные законы операций над множествами.
6.Вопросы для контроля.
7.Элементы математической логики. Введение
8.Логические операции над высказываниями.
9. Вопросы для контроля
10. Основные формулы и определения
11.Рекомендуемая литература
4
4
4
5
6
7
8
9
12
13
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
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
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4. Операции над множествами
Чтобы нагляднее представить эти операции, изобразим их на диаграмме, называемой
диаграммой Эйлера – Венна. Здесь прямоугольник обозначает универсальное множество, а круги
внутри прямоугольника – подмножества.
Дополнением к множеству А называется множество элементов, которые не содержатся в А.
Обозначают его А и читают «дополнение множества А к U».
Пересечением множеств А и В называется множество элементов, принадлежащих и А и В,
Обозначают А ⋂ В и читают «пересечение А и В».
Если А и В непустые множества, пересечение которых пусто, т. е. А ⋂ В = Ø, то их называют
непересекающимися множествами.
Объединением множеств А и В называется множество элементов, принадлежащих либо А,
либо В (либо обоим). Обозначают А U В и читают «объединение А и В».
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Разностью множеств А и В называется множество элементов, принадлежащих А и не
принадлежащих В. Обозначают А \ В и читают «разность А и В».
Например,
если А= { 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.
2.
3.
4.
5.
6.
Законы для объединения и пересечения:
AA=A
7. A  (B  C) = (A  B)  (A  C)
AA=A
8. A  (B  C) = (A  B)  (A  C)
AB=BA
9. A  U = U
AB=BA
10. A   = 
A  (B  C) = (A  B)  C
11. A  U = A
A  (B  C) = (A  B)  C
12. A   = A
Законы для дополнений:
1.
2.
3.
==A
A
AA=U
AA=
4. (A  B)___
= A _ B _
5. (A  B)
=A
___
_B _
6. U = 
_
_
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.
2.
3.
4.
5.
A\B=AB _
U\A=A _
A\U=
A\=A
\A=
Законы для разностей множеств:
6. A \ A = 
7. ((A \ B) \ C) = A \ (B  C)
8. A \ (B \ C) = (A \ B)  (A  C)
9. A  (B \ C) = (A  B) \ (C  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
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7. Элементы математической логики
ВВЕДЕНИЕ
Математическая логика представляет собой область математики, изучающую различные
способы логических рассуждений с помощью математических методов.
Родоначальником науки о логике является греческий философ Аристотель (384-322г. до н.
э.). Он, используя законы человеческого мышления, формализовал известные до него правила
рассуждений. Лишь в конце XVII века немецкий математик Г. Лейбниц предложил
математизировать формальные рассуждения Аристотеля, вводя символьное обозначение для
основных понятий и используя особые правила, близкие к вычислениям. Лейбниц утверждал,
что “мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и
для того, чтобы облегчить сам процесс нашего мышления”.
Применение математики в логике определило новую науку - математическую логику.
Математическое описание рассуждений позволило получить точные утверждения и
эффективные процедуры в решении конкретных задач логики. Рассуждения в математической
логике изучаются с точки зрения формы описания процесса, явления или события и
формального преобразования этого описания. Такой процесс называют выводом заключения
Иногда математическое описание рассуждений называют логико - математическим
моделированием.
Основными объектами при изучении математической логики являются формальный язык
логики и правила вывода. Формальный язык необходим для символьного описания процессов,
явлений или событий и логических связей между ними. Правила вывода необходимы для
формирования процедуры рассуждения. Для обеспечения вывода вводится система аксиом,
формализующая весь механизм вывода заключения.
Математическое описание логики следует воспринимать, как некую формальную систему,
оперирующую с символами по определенным правилам, облегчающим интерпретацию в
реальном мире.
Выделяют несколько типов математических моделей формальной логики. Среди них можно
выделить Логику высказываний, Логику предикатов, Логику нечетных множеств и отношений,
Реляционную логику и др.
Логика высказываний (prepositional calculus) есть модель формальной системы, предметом
которой являются высказывания или повествовательные предложения, взятые целиком без
учета их внутренней структуры
Логика предикатов (predicate calculus) есть модель формальной системы, предметом которой
являются повествовательные предложения с учетом их внутренних состава и структура
Логика нечетных множеств и отношений (fuzzy calculus) есть модель формальной системы,
предметом которой являются повествовательные предложения с учетом их внутреннего состава
и структуры и при нечетком (размытом) задании характерных признаков отдельных элементов
или отношений между ними.
Логика реляционная (relation calculus) есть модель формальной системы, предметом которой
являются отношения в виде множества однородных повествовательных предложений,
существенно расширяющие логику предикатов.
Математическая логика является разделом дискретной математики, в котором, в частности,
формальными методами изучаются высказывания. Широкое применение кроме самой математики
этот её раздел получил при анализе и синтезе логических схем входа и выхода данных в
компьютерах и других цифровых устройствах, в частности: связи, видео- и фотоаппаратуры и др.
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Определение.
Любое предложение, о смысле которого можно сказать, истинно оно или ложно, называется
высказыванием.
Пример: Предложение « Я иду на занятия» является высказыванием, а предложения «Который
час?», « Куда ведёт эта дорога?» высказываниями не являются.
«Река Волга впадает в Каспийское море» - высказывание истинно
«Лондон – столица России» - высказывание ложно
«Число 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
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Дизъюнкция ( операция «или», логическая сумма) двух элементарных высказываний А и В –
новое высказывание, которое считается ложным, если оба высказывания ложны и истинным – во
всех других случаях. Обозначается А ٧ В и читается «А или В», при этом разделительный смысл
слова «или» исключается.
Логические значения дизъюнкции описываются таблицей истинности:
А
В
Аv В
1
1
1
1
0
1
0
1
1
Пример1) ВысказываниеA: «Москва – столица России»
B: «Минск - столица России»
А٧В истинно.
Пример 2) ВысказываниеA: «Для печати применяют матричный принтер»
B: «Для печати применяют струйный принтер»
C: «Для печати применяют лазерный принтер»
D: «Для печати применяют литерный принтер»
Тогда F= ( A٧B٧C٧D) отражают высказывание: «Для печати применяют матричный принтер,
струйный принтер, лазерный принтер или литерный принтер».
Неравнозначность (исключающее, разделительное «или») двух элементарных
высказываний А и В – новое высказывание, которое ложно, если оба высказывания либо
одновременно истинны, либо одновременно ложны и истинно - в противном случае.
Обозначается А ⊕ В и читается: «либо А, либо В», «или А, или В». Понимается в
разделительном смысле.
Логические значения неравнозначности описываются таблицей истинности:
А⊕ В
А
В
1
1
0
1
0
1
0
1
1
0
0
0
Пример: ВысказываниеA: Юноша – школьник
B: Юноша – студент
Тогда:
А⊕ В (или школьник или студент) ложно.
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Отрицание (инверсия) высказывания А - новое высказывание, которое считается истинным,
если высказывание А ложно, и ложным, если высказывание А истинно. Обозначается символом Ā
и читается « не А» или «неверно, что А».
Логические значения неравнозначности описываются таблицей истинности:
А
Ā
1
0
0
Пример:
!
1
А: «Волга впадает в каспийское море»
Ā: «Волга не впадает в каспийское море»
Ā : «Не верно , что Волга не впадает в каспийское море»
Ā : « 4 – простое число».
Импликация( логическое следование) ) двух высказываний А и В – новое высказывание,
которое считается ложным, если А истинно, а В – ложно и истинным – во всех остальных случаях.
Обозначается символом А → В и читается «если А, то В» или « изА следует В». При этом
высказывание А называют условием или посылкой, а высказывание В – следствием или
заключением.
Логические значения импликации описываются таблицей истинности
А
В
А→В
1
1
1
1
0
0
0
1
1
0
0
1
Пример: 1) A: «Москва – столица России»
B: «Москва – столица США»
Тогда А → В ложно, т. к. А истинно, а В – ложно.
Пример 2) Даны высказывания:
A: «По проводнику протекает электрический ток»
B: «Вокруг проводника есть магнитное поле»
Тогда формула F= (А → В) отражает высказывание «Если по проводнику протекает
электрический ток, то вокруг проводника есть магнитное поле».
Пример 3)
A:«На упругое тело оказывают влияние внешние силы»
B:«В упругом теле возникают внутренние силы, препятствующие изменению
формы»
тогда формула F= (А → В) отражает высказывание
«Если на упругое тело оказывают влияние внешние силы, то в нём возникают внутренние силы
,препятствующие изменению формы»
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Двойная импликация ( эквивалентность) двух высказываний А и В – новое высказывание,
которое считается истинным, когда оба высказывания А и В одновременно истинны. Либо
одновременно ложны, и ложным во всех остальных случаях. Обозначается символом А↔В ( А~В,
А ≡ В) и читается «А тогда и только тогда, когда В» или « А эквивалентно В» или «для того,
чтобы А необходимо и достаточно, чтобы В»
Логические значения двойной импликации описываются таблицей истинности:
А
В
А↔ В
1
1
1
1
0
0
0
1
0
0
0
1
Пример:1)A: «Четырёхугольный параллелограмм»
B: «Четырёхугольный параллелограмм, у которого противолежащие стороны попарно
параллельны»
А ↔В истинно.
Пример 2) Даны высказывания:
Тогда F= (А ↔В)
оно делилось на 2.
A: «Быть чётным числом»
B: «Число делится на 2»
отображает высказывание «для того чтобы число было чётным надо, чтобы
Пример 3) Даны высказывания:
A: «Выполнить загрузку операционной системы в компьютер»
B: «Вставить диск с записанной операционной системой»
Тогда F= (А ↔В) отображает высказывание «для того, чтобы выполнить загрузку операционной
системы в компьютер, надо вставить диск с установленной операционной системой».
9. Вопросы для контроля
1.Что называется высказыванием?
2. Приведите примеры высказываний.
3. Приведите примеры предложений, которые не являются высказываниями.
4. Какие значения может принимать высказывание?
5. Перечислите виды логических операций над высказываниями и сформулируйте их определение.
6. Что представляет собой таблица истинности высказывания, как она строится?
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
10. Основные формулы и определения
Под множеством понимают объединение в одно общее объектов, хорошо различаемых
нашей интуицией или нашей мыслью
Исходное множество будем называть универсальным множеством; подмножества,
содержащие один элемент – единичными множествами;
множество, не содержащее никаких элементов – пустым множеством и обозначать Ø .
Дополнением к множеству А называется множество элементов, которые не содержатся в
А. Обозначают его А и читают «дополнение множества А к U».
Пересечением множеств А и В называется множество элементов, принадлежащих и А и
В, Обозначают А ⋂ В и читают «пересечение А и В».
Объединением множеств А и В называется множество элементов, принадлежащих либо
А, либо В (либо обоим). Обозначают А U В и читают «объединение А и В».
Разностью множеств А и В называется множество элементов, принадлежащих А и не
принадлежащих В. Обозначают А \ В и читают «разность А и В».
Любое предложение, о смысле которого можно сказать, истинно оно или ложно,
называется высказыванием.
Высказывания, представляющие собой одно утверждение, называются простыми, или
элементарными. Из элементарных высказываний по определённым логическим правилам
составляют сложные высказывания.
Конъюнкция (операции «и», логическое произведение) двух элементарных высказываний
А и В – новое высказывание, которое считается истинным, если оба высказывания А и В истинны
и ложным – во всех других случаях. Обозначается А ٨ В и читается « АиВ»
Дизъюнкция ( операция «или», логическая сумма) двух элементарных высказываний А и В
– новое высказывание, которое считается ложным, если оба высказывания ложны и истинным – во
всех других случаях. Обозначается А ٧ В и читается «А или В», при этом разделительный смысл
слова «или» исключается.
Неравнозначность (исключающее, разделительное «или») двух элементарных
высказываний А и В – новое высказывание, которое ложно, если оба высказывания либо
одновременно истинны, либо одновременно ложны и истинно - в противном случае.
Обозначается А ⊕ В и читается: «либо А, либо В», «или А, или В». Понимается в
разделительном смысле
Отрицание (инверсия) высказывания А - новое высказывание, которое считается
истинным, если высказывание А ложно, и ложным, если высказывание А истинно. Обозначается
символом Ā и читается « не А» или «неверно, что А».
Импликация( логическое следование) ) двух высказываний А и В – новое высказывание,
которое считается ложным, если А истинно, а В – ложно и истинным – во всех остальных случаях.
Обозначается символом А → В и читается «если А, то В» или « изА следует В». При этом
высказывание А называют условием или посылкой, а высказывание В – следствием или
заключением.
Двойная импликация ( эквивалентность) двух высказываний А и В – новое высказывание,
которое считается истинным, когда оба высказывания А и В одновременно истинны. Либо
одновременно ложны, и ложным во всех остальных случаях. Обозначается символом А↔В ( А~В,
А ≡ В) и читается «А тогда и только тогда, когда В» или « А эквивалентно В» или «для того,
чтобы А необходимо и достаточно, чтобы В»
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
11. Рекомендуемая литература:
1.
2.
3.
4.
«Математика» С.Г. Григорьев, С.В. Задулина Москва2007.
«Дискретная математика» Ю.И. Галушкина Москва2008.
«Дискретная математика» С.А. Канцедал Москва2007.
«Математическая логика» В.Ф. Пономарёв Калининград2001.
14
1/--страниц
Пожаловаться на содержимое документа