metod_15.03.04_atppp_moas_2016 (1016590), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Для приведения булевойфункции к виду содержащему лишь связки из базиса S1 могут быть полезны следующие эквивалентности:X→Y=¬XvYX↔Y=(Xv¬Y)(¬XvY)X⊕Y=¬XYvX¬YX|Y=¬Xv¬YX↓Y=¬X&¬Y2. Система S2={¬,&} образует базис. Произвольную функцию можно сначалапривести к виду, содержащему связки из S1, а затем использовать соотношениеXvY=¬(¬X•¬Y).3. Система S3={¬,v} образует базис. Произвольную функцию можно сначалапривести к виду, содержащему связки из S1, а затем использовать соотношениеX•Y=¬(¬Xv¬Y).4.

Система S4={1,&,⊕} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношения:¬X=1⊕XXvY=X⊕Y⊕X•Y5. Система S5={|} образует базис. Произвольную функцию можно сначалапривести к виду, содержащему связки из S2 а затем использовать соотношения:X•Y=¬(¬X|¬Y)¬X=X|X6. Система S6={↓} образует базис. Произвольную функцию можно сначалапривести к виду, содержащему связки из S3 а затем использовать соотношения:XvY=¬(¬X|¬Y)¬X=X↓X7.СистемаS7={→,0}образуетбазис.Пример: Записать функцию X↔(Y⊕Z) в базисе S1={¬,&,v}.X↔(Y⊕Z)=(Xv¬(Y⊕Z))•(¬Xv(Y⊕Z))=(Xv¬(¬Y•ZvY•¬Z))•(¬Xv¬Y•ZvY•Z)Совершенные формы. Полином Жегалкина.1)Задание 1: по заданным таблицам истинности построить СДНФ иСКНФ2)XYZ00010000011010010000001110001001110101111011010111111110Задание 2. Представить в виде полинома Жегалкина:f (x1, x2,, x3) = x1 v ( x2  x3)Основы теории множествМножества и операции над ними.Одно из основных понятий математики – множество.Определение:Множеством называется совокупность, набор предметов, объектов илиэлементов.Множество обозначают: M,N …..m1, m2, mn – элементы множества.СимволикаA  M – принадлежность элемента к множеству;А  М – непринадлежность элемента к множеству.Примеры числовых множеств:1,2,3,… множество натуральных чисел N;…,-2,-1,0,1,2,… - множество целых чисел Z.Nмножество рациональных чисел а.MI – множество иррациональных чисел.R – множество действительных чисел.K – множество комплексных чисел.Множество А называется подмножеством В, если всякий элемент А является элементом В.А  В – А подмножество В (нестрогое включение)Множества А и В равны, если их элементы совпадают.A=BЕсли А  В и А  В то А  В (строгое включение).Множества бывают конечные и бесконечные.|М| - мощность множества (число его элементов).Конечное множество имеет конечное количество элементов.Пустое множество не содержит элементов: M = .Пример: пустое множество:1) множество действительных корней уравнения x2+1=0 пустое: M = .2) множество , сумма углов которого  1800 пустое: M = .Если дано множество Е и мы рассматриваем все его подмножества, томножество Е называется универсальным.Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики …Если универсальное множество состоит из n элементов, то число подмножеств = 2n.Если A  E  A , состоящее из элементов E, не принадлежащих А, называется дополненным.Множество можно задать:1) Списком элементов {a,b,c,d,e};2) Интервалом 1<x<5;3) Порождающей процедурой: xk=k sinx=0;Операции над множествами1)Объединение множеств А и В (союз или).

Множество, состоящие изэлементов, которые принадлежат хотя бы одному из множеств А или В называется объединенным.АВОтношение множеств наглядно иллюстрируется с помощью диаграммВенна.Диаграмма Венна – это замкнутая линия, внутри которой расположеныэлементы множества.Объединение двух множествОбъединение системы множеств можноАзаписатьnU M i - объединение системы ni 1Вмножеств.Пример: объединение множеств, когда онизаданы списком.A = {a,b,d} B = {b,d,e,h} AUB = {a,b,c,d,e,h}Объединение трех множеств:AUBAUBABABC2) Пересечением множеств А и В называется множество, состоящие изэлементов принадлежащих одновременно множествам А и В.A BААСВВПересечение прямой и плоскости1)если прямые || пл., то множество пересечений – единственнаяточка;2)если прямые II пл., то M ;3)если прямые совпадают, то множество пересечений = множествопрямой.nMiПересечение системы множеств: i14)Разностью 2-х множеств А и В называется множество, состоящее извсех элементов А, не входящих в В.С=А\ВA\BА\ВАВАA\BAВBA = {a,b,d}; B = {b,c,d,h} C = A \ B={a}.В отличии от предыдущих операций разность:1) строго двухместна;2) не коммутативна, т.е.

A\B  B\A.4) дополнение A \ E  AE – универсальное множество.A -- дополнениеОперации объединения, пересечения и дополнения называются Булевыми.Основные законы операций над множествамиНекоторые свойства ,  похожи на алгебраические операции, однакомногие свойства операций над множествами все же отличаются.Свойства множеств.Основные свойства1)AUB=BUA; AB=BA – переместительный закон объединения ипересечения.2)(АUB)UC = AU(BUC); (AB)C=A(BC) – сочетательный за-3)АU=A, A=, A \ =A, A \ A=кон.1,2,3 – есть аналог в алгебре.3.а)  \ A =  - нет аналога.4)A  A; A  A  E; A  A  ; E \ A = A ; A \ E=; AUA=A; AA=A;AUE=E; AE=A;5.а) свойства 1-4 очевидны и не нуждаются в доказательствах.5)A(BUC)=(AB)(AC) – есть аналогичный распределительный за-кон  относительно U.Прямые произведения и функцииПрямым декартовым “х” множеств А и В называется множество всех пар(a;b), таких, что аА, bB.С=AхВ, если А=В то С=А2.Прямыми «х» n множеств A1x,…,xAn называется множество векторов(a1,…an) таких, что a1A1,…, AnAn.Через теорию множеств введем понятие функции.Подмножество FMx x My называется функцией, если для каждого элемента хMx найдется yМу не более одного.(x;y)F, y=F(x).Соответствие между аргументом и функцией можно изобразить с помощью диаграммы Венна:МхMyа) взаимнооднозначное соответствие (отображение)а) не взаимнооднозначное соответствие (отображение)Определение: Между множествами MX и MY установлено взаимноодназночное соответствие, если каждому хMX соответствует 1 элемент yMY и обратное справедливо.Пример: 1) (х,у) в кругеx=2  y=2y2y=2  x=2..4234X2) x = sinxR Rне взаимнооднозначное соответствие.   ;1;1 2 2 -/2/2Пусть даны две функции f: AB и g: BC, то функция y:AC называется композицией функций f и g.Y=f o go – композиция.Способы задания функций:1)таблицы, определены для конечных множеств;2)формула;3)графики;Способы 1-3 частные случаи выч.

процедуры.Пример процедуры, не относящейся к 3 способам задания функций n!Взаимнооднозначное соответствие и мощности множеств.Определение: Множества равномощны |A|=|B| если между ними взаимнооднозначное соответствие.Теорема: Если для конечного множества А мощность равна |A| то количество всех подмножеств 2|A|=2n.Множества равномощные N называются счетными, т.е. в них можно выполнить нумерацию элементов. N – множество натуральных чисел.Множество N2 – счетно.ДоказательствоРазобьем N2 на классыК 1-ому классу отнесем N1 (1; 1)1-ый элемент1-го множества1-ый элемент2-го множестваКо 2-му классу N2 {(1;2), (2;1)}К i-му классу Ni {(a;b)| (a+b=i+1}Каждый класс будет содержать i пар.Упорядоченный классы по возрастанию индекса i, а пары внутри классаупорядоченные по направлению первого элемента а.Занумеруем последовательность классов, что и доказывает счетностьмножества N2.Аналогично доказывается счетность множеств N3,…,Nk.Теорема Кантора:Множество всех действительных чисел на отрезке [0;1] не является счетным.ДоказательствоДопустим это множество счетно изобразим его числа десятичными дробями.1-я 0, a11, a12 ….}2-я 0, а21, a22 ….1………………….Возьмем произвольное число 0,b1,b2,b3b1  a11, b2  a22, …Эта дробь не может выйти в последовательность1т.к.

отличается отвсех чисел, значит нельзя пронумеровать числа на отрезке [0;1].Множество несчетно и называется континуальным, а его мощность континуум.Метод, используемый при доказательстве, называется диагональным методом Кантора.ОтношениеПусть дано RMn – n местное отношение на множество М.Будем изучать двухместные или бинарные отношения. Если а и b находятся в отношении R, то записывается а R b.Проведем отношение на множество N:А) отношение  выполняется для пар (7,9) (7,7)Б) (9,7) не выполняется.Пример отношения на множество RА) отношение находится на одинаковом расстоянии от начала координатвыполняется для пар (3; 4) и (2; 21)Б) (3; 4) и (1; 6) не выполняется.Для задания бинарных отношений можно использовать любые способы задания множеств.Для конечных множеств используют матричный способ задания множеств.Матрица бинарного отношения на множество M={1;2;3;4}, тогда матрицаотношения С равнаС=123411111201113001140001Отношение Е заданные единичной матрицейется отношением равенства.С=101010001называ-Отношением назовется обратным к отношением R, если ajRai тогда итолько тогда, когда ajRai обозначают R-1.Свойства отношенийЕсли aRa ==> очн.

рефлексивное и матрица содержит на главной диа-1.гонали единицу, если ни для какого а не … ==> отношение антирефлексивноеглавная диагональ содержит нулиПр. отношнний рефлексивное< антирефлексивное2. Если из aRb следует bRa, ==> отношение R симметричное. В матрицеотношения элементысумм Cij=Cji. Если из aRb и bRa следует a=b ==> отношение R – антисимметричное.Пр. Если а  b и b  a ==> a=bЕсли дано  a,b,c из aRb и aRc следует aRC ==> отношение называе-3.мое транзитивным.Отношение называется отношением эквивалентности, если оно ре-4.флексивно, симметрично и транзитивно.Пр.

отношение равенства E5. Отношение называется отношением нестрогого порядка, если оно рефлексивно,антисимметрично и транзитивно. Отношение называется отношениемстрогого порядка,если оно антирефлексивно, антисимметрично и транзитивно.Пр.а) отношение  u  для чисел отношение нестрогогоб) отношение < u > для чисел отношение строгогоОперации на множествахМножество М вместе с заданной на нем совокупностью операций  ={1,…, m}, т.е. система А = {М1;1,…, m} называется алгеброй.  - сигнатура.Если M1M и если значения ( M1), т.е.

замкнуто ==> A1={М1;1,…, m}подалгебра A.Пр. 1. Алгебра (R;+;*) – называется полем действительных чисел обе операции бинарные ипоэтому тип этой алгебры (2;2)2.B=(Б;;) – булева алгебра. тип операций (2;2;1)Р. Свойства бинарных алгебраических операцийзапись ab.1. (ab)c=a(bc) – ассоциативная операцияПр. +,x – сложение и умножения чисел ассоциативно2. ab = ba – коммутативная операцияПр. +,x – коммутат.–; : – некоммут.умножение мат AB  BA – некоммутативно.3. a(bc) = (ab) (ac) –дистрибутивность слева(ab)c) = (aс) (bc) –дистрибутивность справа.Пр.

(ab)e=aebe – возведение в степень дистрибутивного отношения произведения справано не abc  abacГомоморфизм и изоморфизмАлгебры с разными членами имеют различные строения. Алгебры с одинаковыми членами имеют сходство. Пусть даны две алгебры A=(K; I) и B=(M;I) – одинакового типа.Пусть отображение Г:KM при условии Г(I)= I(Г), (1) т.е. результат независит от последовательности возможных операций: Или сначала вып. операции I b А и затем отображении Г, или сначала отображение Г, или сначала отображение Г и затем отображение I в В.Тогда условие (1) называется Гомоморфизмом алгебры А в алгебру В.Когда существует взаимооднозначный гомоморфизм его называют изоморфизмом. В этом случае существует обратное отображение Г-1.Мощности изоморфных алгебр равны.Пр. Алгебры (QN; +) и (Q2; +) – отображение типа и условие (1) запишется как 2(а+b)=2а+2b.Отношение изоморфизма является отношением эквивалентности на множестве алгебр, т.е вычисление рефлексивное, симметричности и транзитивности.Изоморфизм важнейшее понятие в математике.Операции над множествамиМножество – одно из основных понятий математики.

Характеристики

Список файлов учебной работы