Тема 3.4 Представление булевой функции в виде минимальной днф.
Метод квайна, минимизация при помощи карт Вейча-Карно
Самостоятельная работа №6. Самостоятельная работа №7
Тема 3.5 Полнота множества функций.
Любую булеву функцию можно выразить в виде формулы через элементарные функции: отрицание, конъюнкцию, дизъюнкцию, двоичное сложение и константу 0 или 1.
Эти функции можно рассматривать как систему элементарных функций, через которые выражается любая булева функция.
Система булевых функций {f1, f2, …, fm} называется полной, если любая булева функция может быть выражена через функции этой системы с помощью составления из них сложных функций..
Составление сложных функций из элементарных функций системы называется суперпозицией.
Достаточное условие полноты системы.
Пусть система функций {f1, f2, …, fm} (I) полная и любая из функций этой системы может быть выражена через функции g1, g2, …, gl , тогда система { g1, g2, …, gl}(II) тоже полная.
Полноту системы можно доказать , опираясь на то, что любая булева функция представима в виде полинома, или доказав с помощью достаточного условия.
Тема 3.6 Важнейшие замкнутые классы.
Пусть MР2. Замыканием М называется множество всех функций из P2, которые можно выразить формулами над М. Замыкание М обозначается [M].
Множество функций М называется замкнутым классом, если [M]=M.
Пример:
1) P2 – замкнутый класс.
2) Множество {1,x1x2} не является замкнутым классом. Его замыканием будет класс линейных функций: [{1, x1 x2}] = {f(x1, ..., xn) = c0 c1x1 cnxn}. Действительно, по определению формулы над М, функция f(G1, x3), где f – есть сумма по модулю 2, G1 – функция х1 х2, будет формулой над М: f(G1, x3) = (x1 x2) x3.
В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному:
М – полная система, если [M] = P2.
3) A = {f(x1, ..., xn) f(1, 1, ..., 1) = 0} – незамкнутый класс. Возьмем формулу над этим множеством. Пусть f, g1, ..., gn A, т.е. f(1, 1, ..., 1) = 0, g1(1, 1, ..., 1) = 0, тогда f(g1, ..., gn) [A]. Посмотрим, принадлежит ли функция f(g1, ..., gn) множеству А. f(g1(1, ..., 1), g2(1, ..., 1), ..., gn(1, ..., 1) = f(0, ..., 0)), но f(0, ..., 0) не обязано быть равным 0. Действительно, пусть g1(x1, x2) = x1 x2, g2(x) = x A. Возьмем g2(g1(x1, x2)) = x1 x2 [A], g2(g1(1, 1)) = 1 1 = 0, следовательно, g2(g1(x1, x2)) A, отсюда [A] A и А – незамкнутый класс.
Важнейшие замкнутые классы в р2
1) Т0 - класс функций, сохраняющих константу 0.
Т0
= {
f(x1,
..., xn
f(0,
..., 0) = 0, n
= 1, 2, ...}. Покажем, что Т0
является собственным подмножеством
Р2,
т.е. Т0
и Т0
Р
(не совпадает с Р2).
Для этого достаточно привести примеры
функций, входящих в Т0,
и примеры функций из Р2,
не входящих в Т0:
x1&x2,
x1x2,
xТ0
и
x1|x2,
x1
x2,
Т0.
Покажем далее, что [Т0]
= Т0.
Вложение Т0
[
Т0]
очевидно, так как по определению формулы
любая функция из Т0
является формулой над Т0
и, следовательно, принадлежит [Т0].
Покажем, что [Т0]
Т0.
Для этого надо показать, что Ф
= f(f1,
..., fm)
[
Т0],
если все функции f,
f1,
f2,
f3,
..., fm
Т0.
Надо заметить, что в формуле в качестве
функции f1
могут быть взяты переменные, которые
мы договорились считать тождественными
функциями. Тождественная функция
принадлежит классу Т0,
поэтому достаточно показать, что Ф
= f
(f
1, ..., fm)
Т0.
Для этого рассмотрим следующую функцию:
Ф(0,
..., 0) = f
(f
1(0, ..., 0), f
2(0, ..., 0),
...) = f(0,
..., 0) = 0.
Число
функций, зависящих от n
переменных и принадлежащих Т0,
будет равно
2) T1 – класс функций, сохраняющих константу 1.
T1
= {f(x1,
...) f(1,
1, ...) = 1}; x1&x2,
x1x2,
xT1,
х1х2,
x1
x2T1,
следовательно Т1
– собственное
подмножество Р2.
Покажем, что [T1] T1, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т1, можно рассмотреть Ф = f(f1, ..., fn) [T1], где f, f1, ..., fn T1. Найдем Ф(1, ..., 1) = f(f1(1, ..., 1), ..., fn(1, ..., 1)) = f(1, ..., 1) = 1, следовательно, Ф = f(f1, ..., fn) T1, отсюда следует [T1] = T1.
3) S – класс самодвойственных функций.
S
= {f(x1,
...)f*
= f };
x,
,
x1x2x3S,
x1&x2,
x1x2,
x1x2S,
следовательно, S
– собственное подмножество Р2.
|S(n)|
=
.
Покажем, что [S]S.
Ф
= f(f1,
..., fn)
[S],
если f,
f1,
..., fn
S,
а также, что Ф
S.
По принципу двойственности, Ф*
= f*(f1*,
..., fn*)
= f(f1,
..., fn)
= Ф,
отсюда S
– замкнутый класс.
4) L – класс линейных функций.
L = {f(x1, ...) f = c0c1x1...cnxn}; очевидно, L , с другой стороны
L P2, так как x1&x2 L. Заметим, что тождественная функция принадлежит L и |L(n)| = 2n+1. Покажем, что [L] L. Рассмотрим Ф = f(f1, ..., fm), где f, f1, ..., fn L. Тогда Ф = а0 а1(с10 с11х1 ... c1nxn1) a2(c20 c21x1 c22x2...c2nxn2)...an(cm0 cm1x1 ... cmnxnm) = в0 в1х1 ... вnхn ФL.
5) М – класс монотонных функций.
Набор
=
(1,
..., n)
предшествует набору
=
(1,
..., n)
и обозначается
,
если для 1in
ii,
например:
=
(0010),
=
(0110), тогда
.
Не любые два набора находятся в отношении
предшествования, например, наборы (0110)
и (1010) в таком отношении не находятся.
Отношение предшествования (
)
является отношением порядка на множестве
наборов длины n,
множество таких наборов будет частично
упорядоченным множеством по отношению
к операции.
Функция f(x1, ..., xn) называется монотонной, если для двух наборов и , таких что , выполняется f( ) f( ). Функции 0, 1, x, x1&x2, x1x2 M, x1x2, x1 x2, x1 ~ x2 M.
Для
числа монотонных функций, зависящих от
n
переменных, существуют оценки сверху
и снизу, но точное число сосчитать не
удается. Покажем, что М
замкнутый класс. Рассмотрим функцию
Ф[M],
Ф
= f(f1,
..., fm),
где f,
f1,
..., fmM,
причем можем считать, что все они зависят
от n
переменных. Пусть набор
=
1,
..., n),
=
(1,
..., n).
Рассмотрим Ф1,
..., n)
= f(f11,
..., n),
…, fm1,
..., n))
и Ф(1,
..., n)
= f(f1(1,
..., n),
..., fm(1,
..., n)).
Здесь f1()
f1(),
..., fm()
fm(),
тогда набор (f1(),
..., fm())
(f1(),
..., fm()),
но тогда Ф()
Ф(),
так как fM,
отсюда Ф
= f(f1,
..., ) – монотонная функция.
Функция f есть суперпозиция над M, если f реализуется некоторой формулой над M.
Лемма о немонотонной функции. Отрицание можно получить суперпозицией констант 0 и 1, тождественной функции и немонотонной функции.
Доказательство.
Пусть f(x1,
..., xn)
– немонотонная функция. Тогда существуют
наборы
и
,
для которых
но
Пусть i1,
…, ik
есть все те номера аргументов, для
которых
,
p=1,
…, k.
На всех остальных аргументных местах
j
имеем j
= j.
В выражении
заменим нули на местах i1,
…, ik
на x.
В результате получим функцию g(x),
для которой g(0)
= f(
)
= 1 и g(1)
= f(
)
= 0. Функция g(x)
является отрицанием.
Классы T0, T1, L, S, M пересекаются, но не совпадают, что видно из следующей таблицы, где «+» означает, что функция принадлежит данному классу и «-» – не принадлежит.
|
T0 |
T1 |
L |
S |
M |
x |
+ |
+ |
+ |
+ |
+ |
|
- |
- |
+ |
+ |
- |
0 |
+ |
- |
+ |
- |
+ |
1 |
- |
+ |
+ |
- |
+ |
x1x2 |
+ |
+ |
- |
- |
+ |
A={x, , 0, 1, x1x2) не является полной системой функций так как всегда есть функции Р2 не входящие в эти классы.
Задачи
1. Доказать, что пересечение любых двух замкнутых классов замкнуто.
2. Доказать, что объединение двух замкнутых классов не всегда замкнуто