ДИСКРЕТКА105 (555928), страница 3

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

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

Основные теории множеств Н. Бурбаки. Под множеством понимается множество элементов, обладающих некоторыми свойствами и находящимися в некотором отношении между собой или с элементами других множеств. Два множества тождественно равны между собой А---В только в том случае, если все элементы множества А принадлежат множеству В и наоборот. Множество может содержать, как множество элементов, так и содержать ни одного. Такое множество пустое 0. Его роль, как число ”0”. Множество А, все элементы которого принимают элементы множества В, называются подмножеством В. А<В Если А=В, то А<=В. Подмножество любого множества является пустое множество. АсА и 0сА=собственные подмножества, любые другие подмножества будут несобственные. Множества могут задаваться перечислениями (1) и описаниями (2). 1. А=(а,б,с,д,ф) перечислены все элементы 2. Описываются элементы, входящие в множество. Для (2) требуется задание некоторого …… свойства всем элементам, чтобы определить их отношение к множеству.

Операции над множествами: 1. Объединение А и В есть множество всех элементов, входящих в А или В 2. Пересечением А и В есть множество всех элементов, принадлежащих и А и В. Множества, не имеющие общих элементов называются не пересекающимися. 3. Разность множеств А/В есть множество состоящее из элементов А, не входящих в В. 4. Универсальное множество Е – все другие возможные множества будут подмножеством Е. 5. А II=Е/А дополнение множества А. Для наглядности представления операций над множествами используются круги Эйлера.

Свойства операций. Для этих операций справедливы законы дистрибутивный, коммутационный, ассоциативный.

Картели – есть последовательность элементов любой природы. Длина картели – количество элементов картели (вектор, очередь). 1,1…1 элементы могут быть одни. Картели с длиной=2 называются парами. Множество пар представляют собой плоский график. Картели с длиной 3-тройки ит.д. Если картели для Н, то он ЭНКА.

Прямая (декартово) произведение множеств. А*В – произведение есть множество всех пар, первая компонента которых берется из множества А, а другие из множества В. А=(а,б) В=(с,д) А*В=((а,с)(а,д)(б,с)(б,д)) Прямое произведение не ассоциативное и не коммутационное А*Вне=В*А, А*(В*С)не=(А*В)*С. Понятие степени множества АвстепениН=А*А*…*А (=Н раз). В этом случае ЭНКИ содержат элементы множества А, которые одинаковы А=(а1,а2), Авквадрате=((а1,а1),(а1,а2),(а2,а1),(а2,а2)). Произведение множеств отличаются от операций над множествами: в результате операций над множествами получаются множества, элементы которых принадлежат исходному множеству; элементы произведения множеств есть множества другой природы. Пусть, например, П, М ряд натуральных чисел. Тогда множество (П,М) – множество пар натуральных чисел, каждый из которых может иметь собственную природу.

Бинарные отношения. Р(с-под)МвстепениН называется местным отношением на множестве М. Если Н=1 – это само подмножество М, такие отношения называются признаками. Говорят М обладает признаком Р (асР), если (ас-посерединеР) принадлежит этому множеству, а множество Рс-посерединеМвстепени1 является подмножеством. Так как при Н=1, отношение Р есть признак, то отношение к ним не применяются. Примером 3-х местного или тетрарного отношения являются множества координат самолетов в пространстве. Говорят, что координата находится в некотором отношении с двумя другими координатами. Наиболее часто встречаются двух местные бинарные отношения. Эти отношения устанавливают соответствия одного множества А к элементам другого множества В. Такое отношение может быть задано совокупностью упорядоченных пар множеств. Если элементы А и В находятся в некотором отношении Р, то пишут аРб. В общем случае пары элементов переставлять нельзя.

Бинарные отношения устанавливаются для любых множеств, не только числовых. Например, для множества людей жить в одном городе и отношение.

Задание бинарных отношений. Используются любые способы задания множеств. Наиболее часто используется матричный способ задания. Матрица бинарного отношения М=(а1,а2,ан) есть квадратная матрица Г порядка Н, в которой элемент матрицы Сиж, стоящий на пересечении и строки и ж столбца определяется как: сиж=(1, если выполняется Аи Раж; 0, в противном случае.

Бинарное отношение можно задавать с помощью графов. Отношением Р называется рефлексивным, если для любого ас-посерединеМ выполняется аРа. Главная диагональ матрицы такого уравнения содержит только 1. Отношение Р называется антирефлексивным, если выполняется аРа. Отношение Р называется симметричным, если для пары (а,б)с-посерединеМ из того, что аРб => обратное соотношение бРа. Матрица симметричного отношения симметрична относительно главной диагонали, то есть Сиж=Сжи. Отношение Р называется транзитивным, если для любых (а,б,с)с-посерединеМ из аРб, бРс => аРс. Если Р отношение ”больше”, а>б, б>c, а>с. В булевой алгебре доказано, что нарушение одного из 3х свойств ведет к тому, что оптимальное решение получено не может быть.

Основные теории графов. Под графом Г понимается пара Г(Х,Г), где Х - непустое множество вершин, а Г - непустое множество ребер, соединяющее некоторые из вершин Х. Две дуги называются смежными, если они различны и для них существует граничная точка.

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

Макстермом или конституентой нуля называется элементарная сумма аргументов функций, в которую входят все аргументы этой функции один раз.

Булева функция называется монотонной, если при возрастании значений набора аргументов значения функций на этих наборах, по крайней мере не убывают.

Булева функция называется линейной, если она может быть представлена полиномом Жегалкина I степени.

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

Система булевых функций называется функционально полной, если любая булева функция, как бы сложна она не была, может быть представлена с помощью функций, входящих в эту систему.

К полным системам булевых функций относится система, состоящая всего лишь из одной системы: эта функция Пирса (ИЛИ-НЕ) и функция Шефера (И-НЕ).

Минимизировать булеву функцию это значит найти такую её запись, в которой вхождение аргументов в эту запись минимально.

Сокращенной ДНФ функции называется дизъюнкция всех её простых импликант.

Булева сумма элементарных произведений называется дизъюнктивной нормальной формой (ДНФ).

Булево произведение элементарных сумм называется конъюнктивной нормальной формой (КНФ).

Импликантой булевой функции называется такая булева функция, которая принимает значение 1 на тех же наборах, что и сама функция.

Под логическим многополюсником понимается логическая схема, где m – входов и n – выходов.

Конечным автоматом называется дискретный преобразователь информации с конечным входным алфавитом , с конечным выходным , с конечным числом состояний , работа которого описывается двумя характеристическими функциями (функция выходов), (функция переходов).

Чтобы определить конечный автомат нужно задать функцию входов и выходов и задать конечное состояние автомата.

Если функция входов и выходов задается вероятностью уравнений, то и автомат вероятностей, в противном случае автомат называется детермированным.

Работа автомата определяется в дискретные моменты времени, которые называются тактами, а сам конечный автомат синхронным.

Конечные автоматы можно задавать с помощью таблиц входов и выходов методом теории графов с помощью матриц.

Автомат Мили – J и S уравнения:

Автомат Мура:

Тупиковое состояние конечного автомата это такое состояние, которое не имеет ни одной исходящей дуги, а только заходящие.

Триггер – есть запоминающее устройство, способное хранить 1 бит информации.

Под графом понимается пара , где - непустое множество вершин, а – непустое множество ребер, соединяющие некоторые из вершин .

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

Список файлов лекций