lec09_1
.pdfСледствие 1. теоремы 9.1 о ФПС.
Из любой полной системы в общем случае можно извлечь полную подсистему, состоящую не более чем из пяти функций. (| | ≥ 6).
Доказательство:
– ФПС она не лежит полностью ни в одном из классов из T , T , L, M, S.
? 0 1
Т.е. f0, f1, fL, fM, fS, соответственно: f0 T0. f1 T1, fL L, fM M, fS S. Но, как только что доказано, система этих функций порождает весь
класс булевых функций. Ч.т.д.
Следствие 2. теоремы 9.1 о ФПС.
Из любой полной системы в общем случае можно извлечь полную подсистему, состоящую не более чем из четырех функций. (| | ≥ 5).
Доказательство:
Если в доказательстве теоремы 9?.1 Поста на первом этапе получили две константы, то несамодвойственная функция fS не нужна. Если получили отрицание, то не нужна немонотонная функция fM. То есть для полноты системы из предложенных 5+ функций нам нужно взять только четыре.
Ч.т.д. |
21 |
|
Из любой полной системы в общем случае можно извлечь полную |
? |
подсистему, состоящую не более чем из трех функций? (| | ≥ 4). |
Нельзя. Пример.
Q = {xy, x y z,0,1}
Доказательство:
Полноту предложенной Q покажем таблично:
Непосредственно проверяя (вычеркивая строки таблицы) можно теперь доказать, что никакая из подсистем Q не будет полной.
|
T0 |
T1 |
L |
M |
S |
xy |
+ |
+ |
- |
+ |
- |
x y z |
+ |
+ |
+ |
- |
+ |
0 |
+ |
- |
+ |
+ |
- |
1 |
- |
+ |
+ |
+ |
- |
|
|
|
|
|
|
Итог: в общем случае из ФПС (| | ≥ 4), нельзя выделить полную подсистему, состоящую не более чем из трех функций.
22
Пример 9.4. Проверка ФПС { }, {|} по Посту. 1,2) принадлежность классам T0, T1.
, | – не сохраняют «0» и не сохраняют «1»:
(0,0)=1, |(0,0)=1; (1,1)=0, |(1,1)=0.
, | T0, , | T1.
3) принадлежность классу L.
x1 x2 = (x1 x2) = 1 x1x2
x1 x2 = (x1 x2) = 1 x1 x2 x1x2
, | – не линейны. , | L.
4) принадлежность классу M.
= (1;1), = (0;0); ; ( ) = 0 1 = ( ) |( ) = 0 1 = |( ) , | – не монотонны. , | M.
5) принадлежность классу S.
Число единичных вершин для , | не 2., | – не самодвойственны. , | S.
|
x1 x2 |
|
x1 x2 |
x1 x2 |
|||
|
|
|
|
|
|
|
|
|
0 |
0 |
|
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
0 |
1 |
|
|
1 |
|
0 |
|
1 |
0 |
|
|
1 |
|
0 |
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
0 |
|
0 |
|
|
|
|
|
|
|
|
x1 x2 |
|
|
|
x1x2 |
|
||
x1 x2 |
|
x1 x2 |
x1x2 |
||||
|
T0 |
T1 |
L |
M |
S |
||
|
|
- |
- |
- |
- |
- |
|
| |
- |
- |
- |
- |
- |
||
23
Пример 9.5. Проверка ФПС по Посту. |
x1 |
x2 |
x3 |
1 |
2 |
|
f1 = (1111 0001), f2 = (1111 0000). = {f1, f2} – ФПС? |
0 |
0 |
0 |
1 |
1 |
|
1,2) принадлежность классам T0, T1. |
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
||
f1, f2 – не сохраняют «0», f2 не сохраняет «1»: |
||||||
0 |
1 |
1 |
1 |
1 |
||
f1(0,0)=1, f2(0,0)=1; f2(1,1)=0. |
||||||
1 |
0 |
0 |
0 |
0 |
||
f1 сохраняет «1»: f1(1,1)=1. |
||||||
1 |
0 |
1 |
0 |
0 |
||
f1, f2 T0, f2 T1. (f1 T1). |
||||||
1 |
1 |
0 |
0 |
0 |
||
|
||||||
3) принадлежность классу L. |
1 |
1 |
1 |
1 |
0 |
1= ( x1 x2 x3) ( x1 x2 x3) ( x1 x2 x3) ( x1 x2 x3) (x1 x2 x3) =
=(x1 1)(x2 1)x3 (x1 1)(x2 1)x3 (x1 1)x2(x3 1) (x1 1)x2x3 x1x2x3 =
=x1x2x2 … , т.к. x1x2x2 встречается 5 раз (для конъюнктов 5 единичных вершин), то x1x2x2 МЖ(f1). f1 не линейна. f1 L. (МЖ(f1) найден в примере 9.3)
|Nf| – нечетно f L. |
|
|
T0 |
T1 |
L M |
S |
Не обязательно. Очевидно f2 = x1 = x1 |
1 – линейна. |
1 |
- |
+ |
- |
|
2 |
|
|
|
|
||
f2 L. |
|
- |
- |
(+) |
|
|
|
24 |
|
|
|
|
|
Пример 9.5 (продолжение). Проверка ФПС по Посту.
4) принадлежность классу M.
Для f2 = (111), = (000); ; f2( ) = 0 1 = f2( ) f2 – не монотонна. f2 M.
Не обязательно.
Для f1 = (110), = (000); ; f1( ) = 0 1 = f1( ) f1 – не монотонна. f1 M.
5) принадлежность классу S.
Число единичных вершин для f1 не 4. f1 – не самодвойственна. f1 S.
Не обязательно.
Т.к. f2 = x1 это грань в В3. f2 – самодвойственна. f2 S.
Ответ: = {f1, f2} – ФПС
x1 |
x2 |
x3 |
1 |
2 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
|
T0 |
T1 |
L |
M |
S |
1 |
- |
+ |
- |
(-) |
- |
2 |
- |
- |
(+) |
- |
(+) |
25