ЛР_3
.docxСоставим таблицу (Квайна), показывающую соответствие элементарных импликант и наборов значений переменных функции по значениям 1 данной функции:
Элементарные импликанты |
Сокращенные наборы |
Наборы значений переменных, определяющие 0 булевой функции |
||||
000 |
001 |
100 |
110 |
111 |
||
|
00_ |
1 |
1 |
|
|
|
|
_00 |
1 |
|
1 |
|
|
|
1_0 |
|
|
1 |
1 |
|
|
11_ |
|
|
|
1 |
1 |
В рассматриваемом примере ядром является формула:
Для «перекрытия» полного набора переменных достаточно выбрать одну из соответствующих элементарных импликант выделенном столбце. Поэтому получаем две различные минимальные дизъюнктивные нормальные формы:
Этот пример показывает, что минимальная ДНФ не всегда является наименьшей, которая по определению должна быть единственной.
Задача 2. Является ли данный набор булевых функций функционально
полным?
⇒,∧
¬
(Сначала дайте определение полноты системы функций.)
Функциональная полнота множества булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества.
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали
Хотя бы одна функция, не сохраняющая 0;
Хотя бы одна функция, не сохраняющая 1;
Хотя бы одна нелинейная функция;
Хотя бы одна несамодвойственная функция;
Хотя бы одна немонотонная функция.
-
Первый набор ⇒,∧:
Р0
P0
L
S
M
-
+
-
-
-
+
+
-
-
+
Второй набор ¬:
P0
P1
L
S
M
¬
-
-
+
+
-
1) P0 - класс функий, сохраняющих нуль (т.е если f(0,0,...,0)=0, то f принадлежит этому классу). Проверяем
-
не принадлежит классу P0
-
принадлежит классу P0
-
не принадлежит этому классу.
2) P1 - класс функций, сохраняющих единицу (т.е если f(1,1,...,1)=1, то f принадлежит этому классу).
-
принадлежит классу P1
-
принадлежит классу P1
-
не принадлежит классу P1
3)L-класс функций, представимы линейным многочленом Жегалкина.
нелинейный
многочлен
-
нелинейный многочлен, значит, функция
не принадлежит классу L.
-
линейный многочлен, значит, функция
принадлежит этому классу.
4) S -
класс самодвойственных функций. То есть
функций, для которых выполняется:
Самодвойственность проще всего определять по таблице значений функции.
x |
y |
F1 |
F2 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
x |
F3 |
0 |
1 |
1 |
0 |
Таблица самодвойственной функции, интересна тем, что столбец ее значений переходит сам в себя при инвертировании. То есть, например, первое значение функции должно равняться отрицанию последнего, второе - отрицании предпоследнего, и так далее. В нашем случает, самодвойственной функцией является только функция F3.
5) M -класс монотонных функций.
Функция f называется монотонной, если для любых наборов значений переменных (α1,α2,...,αn) и (β1,β2,...,βn), таких что (α1,α2,...,αn)≤(β1,β2,...,βn), выполняется f(α1,α2,...,αn)≤f(β1,β2,...,βn).
Бинарное отношение ≤ понимается так: (α1,α2,...,αn)≤(β1,β2,...,βn) ⇔ ∀i (αi≤βi).
Тогда, функции F1 и F3 не монотонны а, а функция F2 - монотонна. (Конкретизировать почему.)
Согласно критерию Поста, чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце таблицы Поста был хотя бы один минус.
Значит, наша система функций полна. (У Вас две системы функций, а не одна.) (Вы должны дать ответы по этим двум системам отдельно.)
⇒,∧ - набор булевых функций является функционально полным. (Но нет функции, не сохраняющей 1. В таблице Вы указали не верно его обозначение.)
¬ - булева функция является функционально полной. (Но это линейная функция! Внимательно разберите теорему Поста.)
-
Первый набор ⇒,∧:
Р0
P1
L
S
M
-
+
-
-
-
+
+
-
-
+
Второй набор ¬:
P0
P1
L
S
M
¬
-
-
+
+
-
Теорема Поста (о полноте): Набор булевых функций является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов S,M,L,Р0,Р1.
Первый набор булевых функций не является функционально полным, так как в случае P1 обе функции, сохраняют 1, для полноты нужно чтобы хотя бы одна принимала значение 0.
Второй набор булевых функций не является функционально полным, так как в случае L и S функция, является линейной и самодвойственной, для полноты нужно чтобы функция являлась нелинейной и несамодвойственной.
Тогда, функция F1 и F3 не монотонна, а функция F2 - монотонна.
Функция принадлежит классу монотонных функций M, если для любой пары наборов α и β таких, что α ≤ β, выполняется условие f(α) ≤ f(β). (Как определяется выделенный порядок?)
Перебор пар начнем с наборов α=00 и β=01: для них α≤β и выполнено условие монотонности f(00) = f(01). Набор α таков, что любой другой набор β является последователем α.
F1:
(0,0) = 1 и (0,1) = 1 - монотонность не нарушена.
(0,0) = 1 и (1,0) = 0 - монотонность нарушена. Значит функция не принадлежит классу монотонных функций M.
F2:
(0,0) = 0 и (0,1) = 0 - монотонность не нарушена.
(0,0) = 0 и (1,0) = 0 - монотонность не нарушена.
(0,1) = 0 и (1,0) = 0 - монотонность не нарушена.
(0,1) = 0 и (1,1) = 1 - монотонность не нарушена.
(1,0) = 0 и (1,1) = 1 - монотонность не нарушена.
F3:
= 1 и (1) = 0 - монотонность нарушена. Значит функция не принадлежит классу монотонных функций M.
Согласно критерию Поста, чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце таблицы Поста был хотя бы один минус.
Данный набор булевых функций является функционально полным.
Задача 3. Найти минимальную ДНФ для функции из задачи 5 лабораторной работы №2 с помощью карт Карно.
f(0,0,0)=f(1,1,0)=f(0,1,0)=f(0,1,1)=1
Карта Карно для логической функции 3 переменных.
x \ yz |
00 |
01 |
11 |
10 |
0 |
|
0 |
|
1 |
1 |
0 |
0 |
0 |
|
МДНФ:
(Дать пояснения к методу Карно и сделать проверку эквивалентности исходной функции.)
Карта Карно - графический способ минимизации булевых функций. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как построенная соответствующим образом таблица истинности функции.
В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.
Составим таблицы истинности для проверки эквивалентности формул:
x |
y |
z |
|
|
|
∧ ∧ |
∧y∧ |
∧y∧z |
x∧y∧ |
∧ ∧ ∨ ∧y∧ ∨ ∧y∧z ∨ x∧y∧ |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
x |
y |
z |
|
|
∧ |
∧y |
y∧ |
∧ ∨ ∧y ∨ y∧ |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
Формулы принимают значение 1 на одинаковых наборах значений переменных, поэтому они эквивалентны.
Задача 4. Составить контактную схему голосования по большинству голосов при 5 голосовавших.
|
X1 |
X2 |
X3 |
X4 |
X5 |
|
|
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
1 |
0 |
|
|
0 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
1 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
0 |
|
|
0 |
0 |
1 |
1 |
1 |
|
|
0 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
|
|
0 |
1 |
0 |
1 |
0 |
|
|
0 |
1 |
0 |
1 |
1 |
|
|
0 |
1 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
0 |
|
|
0 |
1 |
1 |
1 |
1 |
|
|
1 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
0 |
|
|
1 |
0 |
0 |
1 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
|
|
1 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
1 |
1 |
0 |
|
|
1 |
0 |
1 |
1 |
1 |
|
|
1 |
1 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
0 |
1 |
|
|
1 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
1 |
1 |
|
|
1 |
1 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
0 |
|
|
1 |
1 |
1 |
1 |
1 |