|
|
Множествами объединение, пересечение, разность и симметрическая разность, дополнение. Свойства операций и принцип двойственности правила
                   
|
Наименование БФ
|
0
|
1
|
1
|
Нуль
|
0
|
0
|
2
|
Тождественная
|
0
|
1
|
3
|
Отрицание
|
1
|
0
|
4
|
Единица
|
1
|
1
|
Нахождение минимальных ДНФ через тупиковые ДНФ.
Способы построения тупиковых ДНФ.
Ответ: Минимальная ДНФ содержится среди тупиковых.
Тупиковые ДНФ получаются путем выбрасывания из сокращенной ДНФ некоторых простых импликант.
Существуют алгоритмы, при помощи которых получаются единственные для данной функции тупиковые ДНФ. К таким тупиковым ДНФ относится ДНФ Квайна.
|
Локальные алгоритмы упрощения произвольных ДНФ. Теорема и алгоритм Квайна.
Ответ: Локальные упрощения ДНФ сводятся к поиску и последовательному удалению таких элементарных конъюнкций и литералов до тех пор, пока данная ДНФ не станет безызбыточной.
Теорема Квайна: Чтобы получить сокращенную ДНФ булевой функции из ее совершенной ДНФ, надо выполнить всевозможные неполные склеивания соседних конъюнкций, а затем всевозможные поглощения конъюнкций.
Алгоритм Квайна.
Начало. Задана совершенная ДНФ булевой функции.
Шаг 1. Построим список всех точек функции (булевых векторов) и упорядочим их по неубыванию числа единиц – веса.
Шаг 2. Разобьем список на подмножества (классы) векторов одинакового веса. Обозначим через Ci класс векторов веса i.
Шаг 3. Выполним неполные склеивания всех соседних векторов классов Ci и Ci+1, i
= 0,1, …, n-1. Участвующие в склеивании векторы (α и β) отметим, а полученные векторы (γ) занесем в новый список и приведем в нем подобные.
Шаг 4. Если новый список векторов не пуст, возвратимся с ним на шаг 2 (заметим, что троичные векторы списка оказываются уже упорядоченными по числу единиц).
Конец. Выписав из всех списков неотмеченные векторы, получим множество всех максимальных интервалов, оно задает сокращенную ДНФ исходной функции.
|
Замкнутые классы. Некоторые замкнутые классы: самодвойственные, линейные, монотонные функции. Функции, сохраняющие 1. Функции, сохраняющие 0.
Ответ: Множество булевых функций K называется замкнутым классом, если суперпозиция любых функций из множества K принадлежит этому же множеству K.
Класс S самодвойственных функций:
� = �(��, …, ��) ≃ |� �¯1, …, �¯ ¯�
= ¯�¯(¯�¯1¯¯, ¯…¯¯, ¯�¯�¯)
Класс M монотонных функций:
� = � �1, …, �� |∀� �� ≤ ��
⇒ �(�1, …, ��)
≤ �(�1, …, ��)
Класс L линейных функций:
� = � �1, …, �� |� �1, …, ��
= �0 ⊕ �1�1 ⊕ …
⊕ ����, �� ∈ 0,1
Булева функция сохраняет константу 1 (принадлежит классу T1), если на наборе из всех единиц функция принимает значение единица.
Булева функция сохраняет константу 0 (принадлежит классу T0), если на наборе из всех нулей функция принимает значение ноль.
|
Полные системы булевых функций. Примеры полных систем и представление БФ полиномом Жегалкина в базисе {0, 1, &,+}. Теорема Поста.
Ответ: Система булевых функций (f1, f2, fn) называется полной, если любая переключательная функция может быть представлена суперпозицией функций данной системы.
Примеры полных систем: А↓В, функция Шеффера.
Полином Жегалкина — полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или. Полином Жегалкина имеет следующий вид:
� = �000…000 ⊕ �100..0�1 ⊕ �010..0�2…
⊕ �00..01��
⊕ �110..0�1�2 ⊕ …
⊕ �00..110��−1��
⊕ … ⊕ �11..1�1�2…��
Теорема Поста: Набор булевых функций K является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов S,M,L,T_0,T_1, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна не самодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
|
Карты Карно. Ответ:
Карты Карно - это наглядное представление логической
функции в виде карты, которая удобна для оптимизации.
С каждой из сторон записывается значения комбинаций переменных так
чтобы в этом значении менялся один бит при переходе к следующему.
|
Понятие факториала. Правила
«произведения» и «суммы» в комбинаторике. Диаграммы Эйлера-Венна.
Ответ: Факториал натурального числа n определяется как произведение всех натуральных чисел от 1 до n включительно.
Правило сложения (правило «или») — одно из основных правил комбинаторики, утверждающее, что, если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то выбрать A или B можно n + m способами.
Правило умножения (правило «и») — одно из основных правил комбинаторики. Согласно ему, если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать � ∗ � способами. Естественным образом обобщается на произвольное количество независимо выбираемых элементов.
Диаграмма Венна — схематичное изображение всех возможных отношений нескольких подмножеств универсального множества.
|
Перестановки без повторений и с повторениями. Размещения без повторения и с повторениями.
Ответ: Число перестановок без повторений (n различных элементов):
�� = � � − 1 ∗ … ∗ 1 = �!
Число перестановок c повторениями (k различных элементов, где элементы могут повторяться �1, �2, …, �� раз и
�1 + �2 + … + �� = n, где n - общее количество элементов):
� � , � …. � = �!
� 1 2 � �1! ∗ �2! …. ∗ ��!
Число размещений без повторений из n по m (n различных элементов):
�� = �!
� � − � !
Число размещений с повторениями:
�˜� = ��
�
|
Сочетания без повторений и с повторениями. Свойства сочетаний без повторений.
Ответ: Число сочетаний без повторений (n различных элементов, взятых по m:
�� = �!
� �! � − � !
Число сочетаний c повторениями (n элементов, взятых по m, где элементы в наборе могут повторяться):
�˜� = (� + � − 1)!
� �! � − 1 !
Свойства сочетаний без повторений:
�0 = �� = 1
� �
�1 = ��−1 = �
� �
�� = ��−�
� �
�� = ��−1 + ��
�+1 � �
�−1
Σ �� = ��+1
�+� �+�
�=0
| |
|
|
Скачать 134.15 Kb.