Доказательство

Табличный способ задания логической функции

Таблица 2.1 – Таблица истинности функции 4 – х переменных

Наборы могут обозначаться десятичными или шестнадцатеричными числами. Для нашей таблицы: 2, 4, 7, 8, 9, 10, 12, 13,15 или 2, 4, 7, 8, 9, A, C, D, F.

Таблица 2.1 называется таблицей истинности.

Число двоичных наборов от количества переменных находится в следующей зависимости:

2 ⁿ,

где n – число переменных.

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

Это - частный способ табличного представления логических функций. В частности – карты Карно.

Таблица 2.2 – Матричный способ представления

3.

Булеан

Множество всех подмножеств множества М называется булеаном и обозначается 2 ^М:

2 ^М: = { А | А Ì М }.

ТЕОРЕМА

Для конечного множества М | 2 ^М | = 2^{| М |}.

Доказательство

Индукция по | М |. База: если | М | = 0, то М = Æ и 2^Æ = {Æ}. Следовательно, |2^Æ| = |{Æ}| =1 = 2⁰ = 2^|Æ|.

Индукционный переход: пусть " М | М | < k Þ |2 ^М | = 2^{| М |}. Рассмотрим М = { а ₁,…, а_k }, | М | = k. Положим

М₁: = { Х Ì 2 ^М | а_k Î Х } и М₂: = { Х Ì 2 ^М | а_k Ï Х }.

|

Имеем 2 ^М = М₁ U М₂ и М₁ ∩ М₂ = Æ. По индукционному предположению |М₁| = 2 ^{k –1}, |М₂| = 2 ^{k –1}. Следовательно, |2 ^М | = |М₁| + |М₂| = 2 ^{k -1} + 2 ^{k –1} = 2 ∙ 2 ^{k –1} = 2 ^k = 2^{| М |}.

Пересечение, объединение и разность подмножеств множества U (универсума) являются подмножествами множества U. Множество всех подмножеств множества U с операциями пересечения, объединения, разности и дополнения образует алгебру подмножеств множества U.

4.

1. Коммутативность объединения	1’. Коммутативность пересечения
2. Ассоциативность объединения	2’. Ассоциативность пересечения
3. Дистрибутивность объединения относительно пересечения	3’. Дистрибутивность пересечения относительно объединения
4. Законы действия с пустым и универсальным множествами	4’. Законы действия с пустым и универсальным множествами
5. Закон идемпотентности объединения	5’. Закон идемпотентности пересечения
6. Закон де Моргана	6’. Закон де Моргана
7. Закон поглощения	7’. Закон поглощения
8. Закон склеивания	8’. Закон склеивания
9. Закон Порецкого	9’. Закон Порецкого
10. Закон двойного дополнения

5.

Декартово произведение двух множеств — это множество, элементами которого являются всевозможные упорядоченные пары элементов исходных множеств.

Отношения

6.

а) Отношение - один из способов задания взаимодействия между элементами множества.

б)Бинарные отношения используются для определения взаимосвязей, которыми характеризуются пары элементов множества А и В.

в) Инфиксная нотация — это форма записи математических и логических формул, в которой операторы записаны в инфиксном стиле между операндами на которые они воздействуют.

7.

Обратное отношение: R¯¹={(a,b)|(b,a) принадлежит R};

Дополнение отношения: ͞R={(a,b)|(b,a) не принадлежит R};

Универсальное отношение: U={(a,b)|a принадлежит A, b принадлежит B}.

8.

· Рефлексивность:

· Антирефлексивность (иррефлексивность):

· Корефлексивность:

· Симметричность:

· Антисимметричность:

· Асимметричность: . Асимметричность Транзитивность:

· Связность:

9.

1)Отношение R на множество М называется отношением нестрогого порядка, если оно может быть представлено в виде: , где R₁- строгий порядок на М, а Е– диагональное отношение.

2)Отношение R на множестве М называется отношением строгого порядка, если оно антирефлексивно и транзитивно.

3)Отношение порядка , являющееся полным, то есть таким, что

называется полным порядком.

4) Бинарное отношение на множестве называется отношением частичного порядка ¹⁾, если оно удовлетворяет свойствам

1.рефлексивности: для всех ;

2.антисимметричности: для всех ;

3.транзитивности: для всех .

§ 5)Бинарное отношение на называется предпорядком (или квазипорядком), если оно транзитивно и рефлексивно, то есть

1.

2.

6)Замыканием отношения относительно свойства называется такое множество , что:

1. .

2. обладает свойством .

3. является подмножеством любого другого отношения, содержащего и обладающего свойством .

Другими словами, — минимальное надмножество , выдерживающее .

10.

1)Линейный порядок можно определить как слабый порядок, для которого классы безразличия содержат ровно по одному элементу.

2)

а) минимальный элемент — это такой элемент , что для любого элементы и не сравнимы или .

б) Элемент называют максимальным элементом множества , если для всякого имеет место одно из двух: или , или и не сравнимы.

3)

Диаграмма Хассе — вид диаграмм, используемый для представления конечного частично упорядоченного множества в виде рисунка его транзитивного сокращения. Конкретно, для частично упорядоченного множества диаграмма представляет каждый элемент как вершины на плоскости и отрезки или кривые, идущие вверх от элемента к элементу , если и не существует элемента , для которого . Эти кривые могут пересекаться, но не должны проходить через вершины, если только они не являются концами линии. Такая диаграмма с помеченными вершинами однозначно определяют частичный порядок.

11. Соответствие между множествами. Свойства соответствий: область определения, область значений, сечения.

Пусть есть два множества А={1,2,3} и B={a,b}. Обычное умножение этого кала даст нам шесть элементов в сумме:
А х В = {(1.а)(1.b)(2.a)(2.b)(3.a)(3.b)} и эта загогулина будет иметь 2^6 различных подмножеств. И любое из этих подмножеств называется СООТВЕТСВИЕМ (обозн. буквой G). Вот так просто

Область определения соотвествия (или первая проекция):

Dom G = np₁G={x|(x,y) ∈ G}

(символ Dom означает – Domain – область)

Область значений соответствия (или вторая проекция):

Im G =np₂G={y|(x,y) ∈G}

(Im – Image – образ)

Сечение соответствия G по элементу X₀:

G|_x0={y|(x₀,y) ∈G}

Если нужно но Y₀ то меняем y из формулы выше на х

12. Способы задания соответствий: граф соответствия, булевы матрицы.

Соответствие – это тоже множество, и его можно задавать как и все множества перечислением элементов. Но еще есть способы: матрица и граф соответствия.

Пускай есть X={x,y,z} и Y={a,b} и возьмем рандомное (а согл. 11 Соотвествие – это любое множество из образованного после умножения двух множеств) соответствие которое равно G={(x,a),(x,b),(z,a)}

И вся суть графического отображения состоит в НАНЕСЕНИИ точек Соотв. Элементам множеств (а б х у z) и создание направл. графов в том случае, если они образуют пару

А еще можно в виде матрицы задать – где 0 это не пересекается, 1 – пересекается

Такие матрицы зовутся БУЛЕВЫМИ (1 или 0). Сами матрицы можно перемножать и складывать как завещал нурлан (по законам алгебры), однако элементы уже нужно через различные логические операции херачить – типо Конъюнкции или Дизъюнкции. И тут надо различать ЛОГИЧЕСКАЯ операция над матрицами или АЛГЕБРАИЧЕСКАЯ

13. Отображения. Образы и прообразы элементов.

Соответствие G ⊂ X x Y называется отображением, если область определения соотвествия совпадает с множеством X (Dom G=X или np₁ G=X). Отображение зовется функциональным, если любое сечение содержит только 1 элемент.

Если G – функциональное соответствие, то сечение G|_x0 называют образом элемента Х₀∈Х, а сечение G|_y0 называют прообразом элемента y₀=Y

Определение (по мне так попроще) с инета:

Пусть даны два множества X и Y. Такое соответствие, при котором каждому элементу соответствует (единственный) элемент , называется отображением множества X в множество Y; в частности, если каждый элемент соответствует по крайней мере одному элементу , то такое соответствие называется отображением X на Y.

Если элементу x соответствует y, то y называется образом элемента x, а x - прообразом элемента y. Пишут: или y = f(x). Множество A всех элементов , имеющих один и тот же образ , называется полным прообразом элемента y.

14 Сюръективные, инъективные и биективные отображения.

Слова страшные, но по сути своей являются свойствами отображений.

Инъективным отображением называется отображение, для которого из неравенства x1 и x2 следует неравенство f(x1) и f(x2). Аналогично можно сказать, что из x1=x2 следует, f(x1)=f(x2). -> различные элементы множества Х должны иметь различные образы