|
|
Множествами объединение, пересечение, разность и симметрическая разность, дополнение. Свойства операций и принцип двойственности правила
Отношения эквивалентности: классы эквивалентности и фактормножества. Ядро функции.
Ответ: Рефлективное, транзитивное, симметричное, бинарное отношение называется отношением эквивалентности.(≡) Подмножество элементов
� ∋ � будем называть классом эквивалентности элементов � ∋ � , если все
� ≡ �
Если R определено на множестве M, т.е. � ⊂ �2 , тогда множество классов эквивалентности называется фактормножеством множества M по эквивалентности R.
Ядро функции ƒ обозначаемое ���ƒ= ƒ°ƒ−1 . Ядро функции является отношением эквивалентности на области определения этой функции.
|
Отношения порядка: минимальные элементы, частичный и линейный порядок.
Антисимметричное транзитивное отношение наз-ся отношением порядка.
Если оно рефлексивно, тогда оно отношение нестрогого порядка. А если антирефлексивно, тогда оно отношение строгого порядка.
(x1, x2)=(x,y)
Если x1, x2 – точки числовой оси, тогда отношение порядка подразумевает, что одно из этих чисел меньше либо равно второго элемента пары. В частном случае может быть строго меньше.
Замечание. Если мн-во состоит из несовпадающих элементов, тогда будет выполняться строгое неравенство. Тогда мы имеем дело с антирефлексивным.
Если (x,y)∈R, то для числовых мн-в очевидно, что перестановочная пара (y,x)∉R, т.к. x
Одна из двух перестановочных пар всегда существует. Т.е. для числовых мн-в всегда выполняется свойство полноты, линейности.
∀a,b∈A (a,b)∈R∨(b,a)∈R
Утверждение 1. Отношение порядка на числовом мн-ве обладает свойством полноты (линейности) и такое мн-во наз- ся вполне упорядоченным. Если в качестве мн-ва будем рассматривать булеан какого-либо мн-ва (мн-во всевозможных подмн-в), тогда св-во полноты (линейности) не выполняется (выполняется частично), т.е. булеан какого-либо мн-ва наз-ся частично упорядоченным мн-вом.
На булеане выполняется частичный порядок. A={1,2}
2A={ ∅,{1},{2},{1,2}}
Берем пару эл-тов (подмн-в):
{1},{2} ({1},{2}) ({2},{1}), т.к.
{1}⊈{2} и {2}⊈{1}
Булеан – частично упорядоченное мн-во.
Общее обозначение отношения порядка для произведения мн- ва, на котором оно определено: ⊰
Эл-т x∈M будет называться минимальным эл-том мн-ва, на котором задано отношение порядка, если не существует других меньших его элементов, т.е.
¯∃¯y¯¯∈¯¯M¯¯¯¯y¯¯⊰¯¯x¯¯&¯¯(¯x¯¯≠¯¯y¯¯)
Пример: ∅ - минимальный элемент булеана Теорема. В любом конечном непустом частично упорядоченном мн-ве ∃ элемент.
Теорема 2. На всяком частично упорядоченном множестве может быть дополнен до линейного.
|
Замыкание отношений: замыкание отношения относительно свойства, транзитивное и рефлексивное транзитивное замыкания. Алгоритм Уоршалла.
Ответ: Пусть имеются R и R’ для которых выполняются С(R) и C(R’), заданы на множестве M, отношение R’ будет называться замыканием относительно свойства C, если выполняются три условия:
C(R’) справедливо для R’
R’ является надмножеством R, т.е. R⊂R’
R’ является наименьшим надмножеством R, т.е. не существует другого R’’, обладающим свойством C(R) и R⊂R’’⊂R’
�+ = †∞ �� – это �� = �°�°…°�
�=0
транзитивное замыкание отношения R.
�∗ = †∞ �� = �0 ∪ �1 ∪ �2 ∪ … ∪ �° ∪
�=0
�+ = � ∪ �+ , I – тождественное отношение (a,a) – рефлективное. R* -
рефлективное, транзитивное замыкание. Алгоритм Уоршалла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования.
|
Элементарные булевы функции: существенные и несущественные переменные и переключательные функции (ПФ). ПФ одной переменной (нуль, тождественная, отрицание, единица). ПФ двух переменных (нуль, конъюнкция, сложение по модулю 2, дизъюнкция, стрелка Пирса, эквивалентность, импликация, штрих Шеффера и единица). Их таблицы истинности.
Ответ: Множества элементов X с заданными на нем двуместными функциями (операциями): ∨, ∧ и одноместной функцией ‾ называется булевой алгеброй.
Если � �1, …, ��−1, 0, ��+1, …, �� = �(�1, …, ��−1, 1, ��+1, …, ��) , то xi- называется несущественной, иначе xi – существенная.
Если логическое значение 1 интерпретировать как включено, а 0
как отключено, тогда БФ � = �(�1, …, ��) называют переключательной функцией (ПФ), а устройство имеющее n входов и один выход и принцип работы которого описывается этой БФ (ПФ) называется переключательным элементом (ПЭ).
ПФ одной переменной:
ПФ двух переменных
|
|
|
Наименование
|
X
|
0
|
0
|
1
|
1
|
|
Y
|
0
|
1
|
0
|
1
|
1
|
Конъюнкция
|
0
|
0
|
0
|
1
|
2
|
Отрицание импликации
|
0
|
0
|
1
|
0
|
3
|
Тождественная первой переменной
|
0
|
0
|
1
|
1
|
4
|
Отрицание импликации
|
0
|
1
|
0
|
0
|
5
|
Тождественная второй переменной
|
0
|
1
|
0
|
1
|
6
|
Сложение по модулю 2
|
0
|
1
|
1
|
0
|
7
|
Дизъюнкция
|
0
|
1
|
1
|
1
|
8
|
Стрелка Пирса
|
1
|
0
|
0
|
0
|
9
|
Эквивалентность
|
1
|
0
|
0
|
1
|
1
0
|
Инверсия второй переменной
|
1
|
0
|
1
|
0
|
1
1
|
Импликация
|
1
|
0
|
1
|
1
|
1
2
|
Инверсия первой переменной
|
1
|
1
|
0
|
0
|
1
3
|
Импликация
|
1
|
1
|
0
|
1
|
1
4
|
Штрих Шеффера
|
1
|
1
|
1
|
0
|
|
|
|
|
|
|
Реализация функций
формулами. Равносильные формулы. Закон (теорема) поглощения и принцип двойственности (теорема Моргана).
Ответ:
Всякой формуле однозначно соответствует некоторая функция, при этом говорят, что формула реализует функцию.
Формулы называются равносильными, если реализуют одну и ту же функцию.
Закон (теорема) поглощения: �⋀ �⋁� = � ;
� ∨ � ∧ � = �.
Принцип двойственности (теорема Моргана): ¯�¯¯∨¯�¯ =
�¯ ∧ �¯; ¯�¯¯∧¯�¯ = �¯ ∨ �¯.
|
Нормальные формы: теоремы «о разложении
булевой функции по переменным» и «о единственности существования совершенной дизъюнктивной нормальной формы (СДНФ) для любой кроме нуля, булевой функции». Конъюнктивные нормальные формы (КНФ) и теорема «о единственности существования совершенной конъюнктивной нормальной формы (СКНФ) для любой, кроме единицы, булевой функции».
Ответ: Теорема «о разложении булевой функции по переменным»:
� �1, �2, …, �� =
⋁(� ,…,� ) ��1 ��2 …���(�1, �2, …, ��, ��+1, ��+2, …, ��) ,
1 � 1 2 �
где
σ – укороченное обозначение σ набора. Логическое суммирование V ведется по σ наборам число которых равно 2n штук.
Теорема «о единственности существования совершенной дизъюнктивной нормальной формы (СДНФ) для любой кроме нуля, булевой функции»: Любая БФ, кроме БФ≡0, имеет единственную СДНФ.
Любая БФ, кроме БФ≡1, имеет единственную СКНФ, т.е. любая БФ может быть представлена в виде КНФ � �1, �2, …, �� =
⋀�∗ � ,� =1 ��1 , ��2 , …, ���
1 2 1 2 �
|
Эквивалентные преобразования в
СДНФ: элиминация операций (замена на операции &, V, not), протаскивание отрицаний, раскрытие скобок, правило склеивания/расщепления, сортировка. Ответ: Элиминация операций: �1→ �2 =
�¯1⋁�2
Протаскивание отрицаний: Если имеются поlформулы в виде отрицания дизъюнктивного выражения или конъюнктивного, тогда общее отрицание перейдет на отрицание переменных.
Раскрытие скобок: правило дистрибутивности.
Правило склеивание:
� ∧ � ∨ �¯ ∧ � = �; � ∨ � ∧ �¯ ∨ � = �
Правило расщепления: � ∨ � ∧ � = � ;
� ∧ � ∨ � = �
|
Нахождение совершенных,
сокращенных и минимальных ДНФ: геометрическая интерпретация ДНФ, методы построения сокращенных ДНФ, метод Блейка.
Ответ: Совершенная дизъюнктивная нормальная форма, СДНФ — ДНФ, удовлетворяющая условиям: в ней нет одинаковых простых конъюнкций; каждая простая конъюнкция полная.
Сокращенная ДНФ — форма записи функции, обладающая следующими свойствами: любые два слагаемых различаются как минимум в двух позициях; ни один из конъюнктов не содержится в другом.
Минимальная ДНФ — такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.
ДНФ для БФ f(x1,…,xn) содержит конъюнкты с n переменными и по теоремам разложения БФ в виде ДНФ нас интересуют те наборы � � =
⋁� � ,…,� =1 ��1 , ��2 , …, ��� можно
1 � 1 2 �
отобразить в виде n – мерного гиперкуба с единичными по длине ребрами, координаты вершин которого будут определяться двоичными n – разрядными наборами, соответствующие σ - наборам. Метод Блейка: Чтобы получить сокращенную ДНФ булевой функции из произвольной ДНФ, надо выполнить всевозможные обобщенные склеивания смежных конъюнкций, а затем всевозможные поглощения конъюнкций.
| |
|
|
Скачать 134.15 Kb.
