ДМ_Конспект
.pdfМножество
Совокупность объектов произвольной природы, которые удовлетворяют двум свойствам: все объекты этой совокупности попарно различимы; существует некий признак принадлежности объекта этой совокупности.
Множество-степень
То же, что и булеан множества.
Мощность множества
Мощность конечного счѐтного множества есть число его элементов.
Мультимножество
При многократной записи одного и того же элемента множество называют мультимножеством.
Нестрогое включение
Запись A B означает, что А подмножество множества В, возможно, совпадающее с ним.
Несущее множество (носитель)
Множество M в алгебре A (M ; 1 , ...,m , ..).
Нульарные операции
Фиксированные элементы множества M (называются также выделенными элементами, иногда нулями).
Объединение (теоретико-множественная операция)
Объединением множеств A и B называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств A или B .
(То же, что и сумма).
Отрицание (теоретико-множественная операция) (То же, что и дополнение).
Пересечение
Пересечением множеств A и B называется множество, состоящее из всех тех и только тех элементов, которые принадлежат и A , и B .
Подмножество
Множество A , все элементы которого принадлежат и множеству B , называется подмножеством множества B .
Порождающая процедура
Процедура, которая, будучи запущенной, порождает некоторые объекты, являющиеся элементами определенного множества.
Пустое множество
Множество, не содержащее ни одного элемента (обозначается специальным символом ).
Равенство множеств
Неупорядоченные множества равны, если они содержат одинаковый набор элементов.
Разбиение множества
Система множеств, в которой все попарные пересечения множеств пусты, называется разбиением множества D всех элементов этих множеств, а множества такой системы называются классами.
251
Разность (теоретико-множественная операция)
Разность A и B (обозначается A B или A \ B ) это множество, состоящее из тех и только тех элементов, которые принадлежат A и не принадлежат B .
Семейство
(То же, что и класс).
Сигнатура
Множество операций над элементами множества M , т.е. {1 ,2 ,...,m ,..}, где i операции.
Симметрическая разность
(То же, что и дизъюнктивная сумма).
Строгое включение
Подмножество А множества В, которое не совпадает с множеством В.
Сумма
(То же, что и объединение).
Счетное множество
Множество А называется счетным, если его объекты можно пересчитывать (каждому объекту множества присвоить натуральное число, которое было бы номером лишь одного элемента множества).
Теоретико-множественные операции
Операции объединения, пересечения, разности и дополнения.
Унарная операция
Операция, заданная на некотором множестве, называется унарной, если она действует на один элемент множества и еѐ результатом является элемент этого же множества.
Универсальное множество
Множество, содержащее все элементы, принимающие участие в решении определенного класса задач (обозначают символом U).
(Тоже, что и универсум)
Универсум
(Тоже, что и универсальное множество).
Упорядоченное множество
Множество, в котором важны не только его элементы, но и порядок их следования во множестве.
Элементы множества
Объекты, которые образуют множество, попарно различимы и имеют свойство принадлежности объекта этому множеству.
2. Отношения и их свойства
n -арное отношение
Подмножество декартова произведения n множеств X1 , X 2 , ..., X n , т.е.
R X1 X 2 ... X n . n -местное отношение
То же, что и n -арное отношение.
252
Антирефлексивность
Отношение R на множестве X называется антирефлексивным, если из x1 R x2 следует, что x1 x2 .
Антисимметричность
Отношение R на множестве X называется антисимметричным, если из x1 R x2
и x2 R x1 следует, что x1 |
x2 |
|
|
Антитранзитивность |
|
|
|
Отношение R на множестве X называется антитранзитивным, если для любых |
|||
xi , x j , xk из xi R x j и x j R xk следует, что не выполняется xi R xk . |
|
||
Асимметричность |
|
|
|
Отношение |
R X X |
называется асимметричным, если R R 1 |
, т.е. из |
двух соотношений xi Rx j и x j Rxi по меньшей мере одно не выполняется. |
|||
Атрибут |
|
|
|
Наименование столбца таблицы данных (реляционной таблицы). |
|
||
Биективное отображение |
|
||
Функция |
f : X Y |
называется биективным отображением, |
если она |
одновременно сюръективна и инъективна.
Биективная функция
То же, что и биективное отображение.
Бинарное отношение
Подмножество декартового произведения R X Y на паре множеств X и Y . То же, что и двухместное отношение.
Взаимно однозначное отображение
Такое отображение между элементами двух множеств, при котором каждому элементу первого множества соответствует только один элемент второго множества, и обратно каждому элементу второго множества соответствует только один элемент первого. Частный вид отображения.
Графом редукции
Граф транзитивного отношения, в котором изображается только путь из xi в xk ,
а обусловленные транзитивностью дуги опускаются.
Двухместное отношение
То же, что и бинарное отношение
Декартово произведение
Множество всех возможных упорядоченных наборов (x1 , x2 , ..., xn ) из n элементов, в которых первый элемент принадлежит множеству X1 , второй
множеству X 2 , n -й множеству X n .
Декартов квадрат
Декартово произведение, в котором одно и то же множество X умножается два раза само на себя.
Декартов куб
253
Декартово произведение, в котором одно и то же множество X умножается три раза само на себя.
Декартова степень
Декартово произведение X X ... X , в котором одно и то же множество X умножается n раз само на себя.
Диаграмма Хассе
Схема, которой наглядно можно представить любое частично упорядоченное множество.
Деление отношений
Операция реляционной алгебры. Результирующее отношение содержит те атрибуты делимого, которые не присутствуют в делителе. Значения этих атрибутов берутся из тех кортежей делимого, которые включают в себя кортежи делителя. Отношение-делитель должно иметь набор атрибутов, включенный в набор атрибутов делимого.
Домен
Множество или область данных, на которых определено отношение в реляционной алгебре.
Естественное соединение отношений
Операция реляционной алгебры. При естественном соединении двух отношений образуется результирующее отношение, кортежи которого являются соединением кортежей первого и второго отношений, если значение общих атрибутов совпадает.
Запись отношения
Элементы отношения, соответствующие строкам реляционной таблицы (упорядоченное множество).
То же, что и кортеж.
Инъективное отображение
Функция |
f : X Y , для любых элементов |
xi , x j DO f |
которой из xi x j |
следует |
f (xi ) f (x j ) . |
|
|
Инъективная функция
То же, что и инъективное отображение.
Классы эквивалентности
Непересекающиеся подмножества X i , на которые разбивается множество X .
Композиция отношений
Отношение C S R , состоящее из всех тех пар (x, z) X Z , для которых существует такое y Y , что (x, y) R и ( y, z) S .
Кортеж
Элементы отношения, соответствующие строкам реляционной таблицы (упорядоченное множество).
Линейный порядок
Частичный порядок, если любые два элемента x и y из множества X сравнимы, т.е. x y и y x .
254
Линейно упорядоченное множество
Множество X , на котором задано отношение частичного порядка R и для которого любые два элемента этого множества сравнимы.
Матричный способ задания отношений основан на представлении отношения соответствующей ему прямоугольной таблицей (матрицей).
Несравнимые элементы
Элементы отношения (пары (x, y) , для которых ни одно из соотношений xRy или yRx не имеет места.
Область значений отношения
Множество всех вторых координат упорядоченных пар из бинарного отношения
R .
Область значений отображения
Множество f ( X ) Y , где f ( X ) значения функции.
Область определения отношения
Множество первых координат упорядоченных пар из бинарного отношения R .
Образ
То же, что и область значений отображения.
Обратное отношение
Подмножество множества Y X , образованное теми парами ( y, x) Y X , для которых (x, y) R .
Объединение отношений
Теоретико-множественная операция на отношениях. При выполнении операции объединения двух отношений получаем отношение, включающее все кортежи, входящие хотя бы в одно из отношений-операндов.
Ограничение отношений
Операция реляционной алгебры. Результатом ограничения отношения по некоторому атрибуту или атрибутам является отношение, состоящее в точности из тех кортежей, которые удовлетворяют условию .
Одноместное отношение
Подмножество множества X (признак).
Отношение нестрогого порядка
Отношение R в множестве X такое, что для любых x, y, z из X выполняются
свойства рефлексивности, антисимметричности, транзитивности.
Отношением строгого порядка
Отношение R в множестве X такое, что выполняются свойства антирефлексивности, асимметричности, транзитивности.
Отношение толерантности
Отношение R в множестве X такое, что выполняются свойства рефлексивности и симметричности.
Отображение
255
специальные операции над отношениями: ограничение отношений (выбор), проекцию отношений, соединение отношений, деление отношений.
Реляционная модель данных
Модель данных, которая с математической точки зрения является табличным представлением данных (двумерная таблица).
Сечение отношения
Если xi X , то сечение отношения R по элементу xi , обозначаемое R(xi ) , есть множество R(xi ) Y , состоящее из элементов y Y таких, что (xi, y) R ,
т.е. R(xi ) {y Y | (xi , y) R}. |
|
|
|
|
||
Симметричное отношение |
|
|
|
|
||
То же, что и обратное отношение. |
|
|
|
|
||
Симметричность |
|
|
|
|
|
|
Отношение |
R X X |
называется симметричным, |
если R R 1 , |
т.е. |
при |
|
выполнении |
соотношения xi Rx j |
выполняется и |
соотношение x j Rxi |
( R |
||
выполняется либо в обе стороны, либо не выполняется вообще). |
|
|
||||
Система представителей отношения эквивалентности |
|
|
||||
Подмножество из множества X , |
содержащее по одному и только одному |
|||||
элементу из каждого класса некоторого разбиения множества. |
|
|
||||
Соответствие |
|
|
|
|
|
|
Если x X |
и y Y , то |
DO (R) X и DЗ (R) Y . В таких случаях |
R |
есть |
||
отношение от X к Y , называется соответствием и обозначается X Y .
Сравнимые элементы
Элементы x и y называются сравнимыми в отношении частичного порядка R , если выполняется хотя бы одно из соотношений xRy или yRx .
Схема отношения |
|
|
Список атрибутов реляционной таблицы. |
|
|
Сюръективное отображение |
|
|
Функция f : X Y называется сюръективным отображением, если DЗ f |
Y . |
|
Для сюръективной функции для любого y Y |
существует x X такой, |
что |
f (x) y . |
|
|
Сюръективная функция
То же, что и сюръективное отображение.
Тождественное отношение
Отношение, равносильное x x . |
|
Транзитивность |
|
Отношение R X X называется R |
транзитивным, если R R R , т.е. из |
xi Rxj и x j Rxk следует xi Rxk . |
|
Унарное отношение |
|
То же, что и одноместное отношение. |
|
Универсальное отношение |
|
То же, что и полное отношение. |
|
257
Упорядоченное множество
Множество, в котором определено отношение порядка.
Фактор-множество
Множество всех сечений отношения R называется фактор-множеством множества Y по отношению R и обозначают Y \ R .
Функциональное отношение
Отношение F X Y называется функциональным, если его элементы (упорядоченные пары (x, y) ) имеют различные первые координаты.
Функция
То же, что и отображение
Цепь
То же, что и линейно упорядоченное множество.
Частично упорядоченное множество
Если на множестве задано отношение частичного порядка, то это множество называется частично упорядоченным.
Частичная функция
Если вместо DO f X в функциональном отношении выполняется DO f X , то f называется частичной функцией.
3. Основы математической логики
3.1 Двоичная логика. Булевы функции и преобразования
n-мерный булевый куб
Множество всех двоичных слов (обозначаемое как Bn ), содержит 2n элементовслов, т.е. | Bn | 2n .
Алгебра Жегалкина |
|
|
|
|
|
|
||
Алгебра |
(B, , , 0, 1) , |
образованная множеством |
B {0, 1} |
вместе с |
||||
операциями конъюнкции ( ), суммы по модулю 2 ( ) и константами 0 и 1. |
||||||||
Алгебра логики |
|
|
|
|
|
|
||
Двухэлементная |
булева |
алгебра (B, , , |
|
, , ~), |
где |
носитель алгебры |
||
|
||||||||
B {0, 1}, |
и в |
которой |
множество операций дополнено |
двумя |
бинарными |
|||
операциями: импликацией ( f13(x1, x2 )) и эквивалентностью ~ ( f9 (x1, x2 )).
Булева алгебра (двухэлементная)
Алгебраическая |
структура (B, , , |
|
|
) , где B {0, 1} и операция |
|
есть |
||
|
|
|
|
|||||
конъюнкция f1 (x1, x2 ) , есть дизъюнкция f7 (x1, x2 ) , « |
» есть отрицание |
f2 (x) . |
||||||
Булева функция |
|
|
|
|
|
|
|
|
Функция вида |
y f (x1, x2 , ..., xn ) , |
аргументы xi и |
значения y |
которой |
||||
принадлежат множеству B {0,1}.
Булевы константы
Значения 0 и 1 из множества B {0,1}.
258
Булевы переменные
Переменные, которые могут принимать значения только из множества
B {0,1}.
Булевый базис
Базис, состоящий из отрицания, дизъюнкции и конъюнкции.
Булевый набор
Совокупность конкретных значений аргументов булевой функции.
Двоичное слово ( n -слово)
Совокупность конкретных значений аргументов булевой функции.
Двойственная функция
Функция f * (x1 , x2 , ..., xn ) называется двойственной к функции f (x1 , x2 , ..., xn ) ,
если f * (x1, x2 , ..., xn ) f (x1, x2 , ..., xn ) .
Дизъюнктивная нормальная форма (ДНФ)
Формула, представленная в виде дизъюнкции элементарных конъюнкций.
Дизъюнктивное поглощение
A Ax A , где A некоторая элементарная конъюнкция переменных; x булева переменная.
Дизъюнктивное ядро булевой функции
Такое множество еѐ простых импликант, которое образует покрытие f , но
после удаления импликанты теряет это свойство, то есть перестает быть полной системой импликант.
Длина полинома Жегалкина
Количество попарно различных элементарных конъюнкций в полиноме Жегалкина.
Единичный элемент (единица)
Элемент 1 из множества B {0,1}.
Закон ассоциативности (сочетательный закон)
x1 (x2 x3 ) (x1 x2 ) x3 ; x1 (x2 x3 ) (x1 x2 ) x3 .
Законы де Моргана
x1 x2 x1 x2 ; x1 x2 x1 x2 .
Закон дистрибутивности (распределительный закон)
x1 (x2 x3 ) (x1 x2 ) (x1 x3 ) ; x1 (x2 x3 ) (x1 x2 ) (x1 x3 ) .
Закон идемпотентности x1 x1 x1; x1 x1 x1 .
Закон инволюции (двойного отрицания)
x1 x1 .
Закон исключенного третьего
x1 x1 1.
Закон коммутативности (переместительный закон) x1 x2 x2 x1 ; x1 x2 x2 x1 .
Закон поглощения (элиминации)
259
x1 (x1 x2 ) x1 ; x1 (x1 x2 ) x1 .
Закон противоречия
x1 x1 0 .
Закон тождества (свойство констант) x1 0 x1; x1 1 1; x1 1 x1 ; x1 0 0 .
Замкнутый класс булевых функций
Класс (множество) называется замкнутым классом, если [ A] A (где A некоторое подмножество функций из P2 ).
Замыкание множества A булевых функций
Множество [ A], состоящее из функций, представимых в виде формул через функции множества A (где A некоторое подмножество функций из P2 ).
Импликанта
Импликантой некоторой функции f называется функция g , такая, что на всех интерпретациях, на которых g равна единице, f тоже равна единице.
Имплицента
Импликантой некоторой функции f называется функция g , такая, что на всех интерпретациях, на которых g равна нулю, f тоже равна нулю.
Инверсия
Функция f2 (x) x , равная 1, когда аргумент принимает значение 0, и равная 0
при аргументе 1.
Индекс (коэффициент) простоты
Коэффициент, характеризующий «сложность» ДНФ (КНФ).
Интерпретация булевой функции
Для булевой функции y f (x1, x2 , ..., xn ) конкретное (индивидуальное) значение булевого набора (x1 , x2 , ..., xn ) .
Инфисная запись формул
Запись формул, при которой знаки функций стоят между аргументами.
Классы Поста
T0 − класс функций, сохраняющих 0; T1 − класс функций, сохраняющих 1; S −
класс самодвойственных функций; M − класс монотонных функций; L − класс линейных функций.
Конституента единицы
Булева функция n аргументов, которая принимает значение, равное 1, только на одной интерпретации (наборе).
То же, что и минтерм n -го ранга
Конституента нуля
Булева функция n аргументов, которая принимает значение, равное 0, только на одной интерпретации (наборе).
То же, что и макстерм n -го ранга
Конъюнктивная нормальная форма (КНФ)
Формула, представленная в виде конъюнкции элементарных дизъюнкций.
260