Дискретная математика
Введение
Общество 21в. – общество информационное. Центр тяжести в решении задач переместился от задач вычислительной математики к задачам на дискретных структурах. Математика нужна не как метод расчета, а как метод мышлению средство формирования и организации…
Такое владение математикой богатой культуры, понимание важности точных формулировок.
В дисциплине мало методов, но много определений и терминов. В основе дискретной математике 4 раздела:
Язык дискретной математики;
Логические функции и автоматы;
Теория алгоритмов;
Графы и дискретные экстремальные задачи.
Теория алгоритмов и формальных систем является центральной в дисциплине. В настоящие время от нее возникли ответвления, например, разработка алгоритмических языков программирования.
Одной из важнейших проблем в дискретной математики является проблема сложности вычислений.
Теория сложности вычислений помогает оценить расход времени и памяти при решении задач на ЭВМ. Теория сложности позволяет выделить объективно сложные задачи (задачи перебора) и неразрешимые задачи.
Мы будем заниматься решением задач реальной размерности с учетом ограниченности временных и емкостных ресурсов ЭВМ.
Множества и операции над ними
Одно из основных понятий математики – множество.
Определение:
Множеством называется совокупность, набор предметов, объектов или элементов.
Множество обозначают: M,N …..
m1, m2, mn – элементы множества.
Символика
A M – принадлежность элемента к множеству;
А М – непринадлежность элемента к множеству.
Примеры числовых множеств:
1,2,3,… множество натуральных чисел N;
…,-2,-1,0,1,2,… - множество целых чисел Z.
множество
рациональных
чисел а.
I – множество иррациональных чисел.
R – множество действительных чисел.
K – множество комплексных чисел.
Множество А называется подмножеством В, если всякий элемент А является элементом В.
А В – А подмножество В (нестрогое включение)
Множества А и В равны, если их элементы совпадают.
A = B
Если А В и А В то А В (строгое включение).
Множества бывают конечные и бесконечные.
|М| - мощность множества (число его элементов).
Конечное множество имеет конечное количество элементов.
Пустое множество не содержит элементов: M = .
Пример: пустое множество:
1) множество действительных корней уравнения x2+1=0 пустое: M = .
2) множество , сумма углов которого 1800 пустое: M = .
Если дано множество Е и множество и мы рассматриваем все его подмножества, то множество Е называется униварсельным.
Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики …
Если универсальное множество состоит из n элементов, то число подмножеств = 2n.
Если
,
состоящее из
элементов E,
не принадлежащих
А, называется
дополненным.
Множество можно задать:
Списком элементов {a,b,c,d,e};
Интервалом 1 отношение антирефлексивное
главная диагональ содержит нули
Пр. отношнний
рефлексивное
< антирефлексивное
2. Если из aRb следует bRa, ==> отношение R симметричное. В матрице отношения элементы
сумм Cij=Cji. Если из aRb и bRa следует a=b ==> отношение R – антисимметричное.
Пр. Если а b и b a ==> a=b
Если дано a,b,c из aRb и aRc следует aRC ==> отношение называемое транзитивным.
Отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Пр. отношение равенства E
5. Отношение называется отношением нестрогого порядка, если оно рефлексивно,
антисимметрично и транзитивно. Отношение называется отношением строгого порядка,
если оно антирефлексивно, антисимметрично и транзитивно.
Пр. а) отношение u для чисел отношение нестрогого
б) отношение < u > для чисел отношение строгого
Лекция: Элементы общей алгебры
Р. Операции на множествах
Множество М вместе с заданной на нем совокупностью операций = {1,…, m}, т.е. система А = {М1;1,…, m} называется алгеброй. - сигнатура.
Если M1M и если значения ( M1), т.е. замкнуто ==> A1={М1;1,…, m} подалгебра A.
Пр. 1. Алгебра (R;+;*) – называется полем действительных чисел обе операции бинарные и
поэтому тип этой алгебры (2;2)
B=(Б;;) – булева алгебра. тип операций (2;2;1)
Р. Свойства бинарных алгебраических операций
запись ab.
1. (ab)c=a(bc) – ассоциативная операция
Пр. +,x – сложение и умножения чисел ассоциативно
2. ab = ba – коммутативная операция
Пр. +,x – коммутат.
–; : – некоммут.
умножение мат AB BA – некоммутативно.
3. a(bc) = (ab) (ac) –дистрибутивность слева
(ab)c) = (aс) (bc) –дистрибутивность справа.
Пр. (ab)e=aebe – возведение в степень дистрибутивного отношения произведения справа
но не abc abac
Р. Гомоморфизм и изоморфизм
Алгебры с разными членами имеют различные строения. Алгебры с одинаковыми членами имеют сходство. Пусть даны две алгебры A=(K; I) и B=(M; I) – одинакового типа.
Пусть отображение Г:KM при условии Г(I)= I(Г), (1) т.е. результат не зависит от последовательности возможных операций: Или сначала вып. операции Ib А и затем отображении Г, или сначала отображение Г, или сначала отображение Г и затем отображение Iв В.
Тогда условие (1) называется Гомоморфизмом алгебры А в алгебру В.
Когда существует взаимооднозначный гомоморфизм его называют изоморфизмом. В этом случае существует обратное отображение Г-1.
Мощности изоморфных алгебр равны.
Пр. Алгебры (QN; +) и (Q2; +) – отображение типа и условие (1) запишется как 2(а+b)=2а+2b.
Отношение изоморфизма является отношением эквивалентности на множестве алгебр, т.е вычисление рефлексивное, симметричности и транзитивности. Изоморфизм важнейшее понятие в математике. Полученные соотношения в алгебре А автоматически …. на изоморфные ал
Похожие работы
... которой были разработаны в последней четверти 19 века Георгом Кантором. Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания. Задание 1 Представить с помощью кругов Эйлера множественное выражение . Используя законы и свойства алгебры множеств, упростить заданное ...
глядит следующим образом: ( ( A – F) ( B A ) ) Ç ( E A ÇB ) ) Минимизация проводится с использованием восемнадцати законов. (см. литературы 2) 1) (( A – F) ( B A )) = (( A F) &# ...
... чисел . Обратным ему будет отображение . Для таких отображений справедливо следующее тождество: 9. КОМПОЗИЦИЯ , то их композицией (произведением) называют , причем, если осуществляется композиция, то . В математике такое отображение называют сложной функцией, y – промежуточный аргумент. Для композиции справедливо следующие отображения: - коммутативное - - ассоциативное - ...
... -педагогическая или научно-техническая проблема, являющаяся новым научным вкладом в теорию определенной области знаний (педагогику, технику и другие). 4. ПРАКТИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ ВЫПОЛНЕНИЯ ВЫПУСКНОЙ КВАЛИФИКАЦИОННОЙ РАБОТЫ БАКАЛАВРА ФИЗИКО-МАТЕМАТИЧЕСКОГО ОБРАЗОВАНИЯ ПРОФИЛЬ ИНФОРМАТИКА 4.1. Положение о выпускной квалификационной работе бакалавра физико-математического образования: ...
0 комментариев