ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9328
Скачиваний: 24
41
⎩
⎨
⎧
−
≤
≤
≤
−
−
≤
<
≤
=
÷
.
1
k
x
y
0
если
,
y
x
,
1
k
y
x
0
если
,
0
y
x
Импликация
⎩
⎨
⎧
−
≤
≤
≤
+
−
−
−
≤
<
≤
−
=
⊃
.
1
k
x
y
0
если
,
y
x
)
1
k
(
,
1
k
y
x
0
если
,
1
k
y
x
Функция Вебба: v
k
(x
1
, x
2
)=max (x
1
, x
2
) + 1 (mod k).
Разность по модулю k
:
⎩
⎨
⎧
−
≤
<
≤
−
−
−
≤
≤
≤
−
=
−
.
1
k
y
x
0
если
),
x
y
(
k
;
1
k
x
y
0
если
,
y
x
y
x
Опираясь на понятие эквивалентности, можно описать неко-
торые основные свойства элементарных функций. Пусть
(x
1
°
x
2
)
обозначает любую из функций
min(x
1
,x
2
), x
1
⋅
x
2
(mod k), max (x
1
,
x
2
), x
1
+x
2
(mod k).
1. Функция (
x
1
°
x
2
) обладает свойством
ассоциативности
:
((x
1
°
x
2
)
°
x
3
)=(x
1
°
(x
2
°
x
3
)).
2. Функция (
x
1
°
x
2
) обладает свойством
коммутативности
:
(x
1
°
x
2
)= (x
2
°
x
1
).
Кроме того, справедливы следующие соотношения:
1.
Дистрибутивность
умножения относительно с
ложения
:
(x
1
+x
2
)
⋅
x
3
=(x
1
⋅
x
3
)+(x
2
⋅
x
3
).
2. Д
истрибутивность
операции
max
относительно опера-
ции
min
:
max(min(x
1
,x
2
), x
3
)=min(max(x
1
,x
3
),max(x
2
,x
3
)).
3.
Дистрибутивность
операции
min
относительно операции
max
:
min(max(x
1
,x
2
), x
3
)=max(min(x
1
,x
3
),min(x
2
,x
3
)).
4.
Идемпотентности
операций
max
и
min
:
max(x,x)=x; min(x,x)=x.
5. Аналоги правил
де Моргана
в
P
2
:
min(~x
1
, ~x
2
)= ~max(x
1
, x
2
), max(~x
1
, ~x
2
)= ~min(x
1
, x
2
).
Следующие равенства вводятся по определению:
max (x
1
, x
2
, …, x
n–1
, x
n
) = max (max (x
1
, x
2
, …, x
n–1
), x
n
)),
n
≥
3;
min (x
1
, x
2
, …, x
n–1
, x
n
) = min (min (x
1
, x
2
, …, x
n–1
), x
n
)), n
≥
3;
42
⎩
⎨
⎧
≠
=
−
=
−
.
0
x
если
,
0
x
если
,
x
k
,
0
x
Рассмотрение свойств элементарных функций показывает,
что не для всех обобщений булевых функций сохраняются соот-
ветствующие свойства. Например,
~(~x)=x
, но
x
x
≠
(при k
≥3).
4.2
Разложение
функций
k-
значных
логик
в
первую
и
вторую
формы
Любую функцию
f(x
1
, x
2
, …, x
n
)
из
P
k
(n
≥
1)
можно предста-
вить в
первой форме
, являющейся аналогом совершенной ДНФ
для функции алгебры логики:
{
}
,
)
x
(
J
),...,
x
(
J
),
x
(
J
),
,...
,
(
f
min(
max
)
x
,...,
x
,
x
(
f
n
2
2
1
n
2
1
~
n
2
1
n
1
σ
σ
σ
σ
σ
σ
σ
=
где максимум берется по всем наборам
)
,...,
,
(
~
n
2
1
σ
σ
σ
=
σ
значений
переменных
x
1
, x
2
, …, x
n
.
Справедливо еще одно представление для функции
k
-знач-
ной логики, называемой
второй формой
:
)
x
(
j
...
)
x
(
j
)
x
(
j
)
~
(
f
)
x
~
(
f
n
n
~
2
2
1
n
1
σ
σ
σ
σ
∑
⋅
⋅
⋅
⋅
σ
=
,
где суммирование ведется по всем наборам
)
,...,
,
(
~
n
2
1
σ
σ
σ
=
σ
значений переменных
x
1
, x
2
, …, x
n
(сумма и произведение берут-
ся по модулю
k
).
4.3
Замкнутые
классы
и
полнота
в
k-
значных
логиках
Система
S
функций
f
1
, f
2
, …, f
n
, из
P
k
называется (функцио-
нально)
полной
, если любая функция из
P
k
может быть записана
в виде формулы через функции этой системы.
Приведем некоторые системы
S
полных систем.
1.
Система
S=P
k
полна. Очевидно, что множество всех
функций из
P
k
представляет полную систему.
2.
Система
S={0, 1, …, k–1, J
0
(x), …, J
k–1
(x), min (x
1
, x
2
), max (x
1
, x
2
)}.
3.
Система
43
S = { x , max (x
1
, x
2
)}.
4.
Система
S = { v
k
(x
1
, x
2
)}.
С понятием полноты связано понятие замыкания и замкну-
того класса.
Пусть
M
– произвольное множество функций из
P
k
. Замы-
канием M
называется множество
[M]
всех функций из
P
k
, пред-
ставимых в виде формул через функции множества
М.
Класс (множество)
M
называется (функционально) замкну-
тым, если
[M]=M
.
Функция
f(x
1
, x
2
, …, x
n
)
из
P
k
(n
≥
0
) называется
линейной
,
если она представима в виде
a
0
+a
1
⋅
x
1
+…+ a
n
⋅
x
n
, где
a
j
∈
E
k
(j=0, 1,
…, n) и сумма, и произведение берутся по модулю
k
. Множество
всех линейных функций из
P
k
образует замкнутый класс линей-
ных функций, который обозначается через
L
k
(или
L
). Класс
L
k
отличен от
P
k
при всяком
k
≥
3
.
Полиномом (или многочленом) по модулю
k
от переменных
x
1
, x
2
, …, x
n
называется выражение вида
a
0
+a
1
⋅
X
1
+…+ a
m
⋅
X
m
,
где
коэффициенты
a
i
принадлежат множеству
E
k
и
X
j
– либо некото-
рая переменная из
{x
1
, x
2
, …, x
n
},
либо произведение переменных
этого множества (j=0, 1, …, n).
Говорят, что некоторая функция из
P
k
представима (или
реализуется) полиномом по модулю
k,
если существует полином
по модулю
k,
равный этой функции. Множество всех функций из
P
k
, представимых полиномами по модулю
k
(или, короче, множе-
ство всех полиномов по модулю
k
), является замкнутым классом
в
P
k
.
Теорема (критерий полноты класса полиномов в
P
k
). Пред-
ставление каждой функции из
P
k
полиномом по модулю
k
воз-
можно в том и только том случае, когда
k
– простое число (ины-
ми словами, система полиномов по модулю
k
в
P
k
тогда и только
тогда, когда
k
– простое число).
Необходимо отметить некоторые свойства, связанные с
полной. Приведем их без доказательств:
1.
Существует алгоритм для распознавания полноты.
2.
Из всякой полной в
P
k
системы
S
можно выделить конеч-
ную подсистему, являющуюся также полной.
44
3.
Класс
M
всех функций, сохраняющих
R,
является замк-
нутым. Функция
f(x
1
, x
2
, …, x
n
)
сохраняет множество
R
, если для
любых функций
h
i1
(y
1
, y
2
, …, y
n
), h
i2
(y
1
, y
2
, …, y
n
), …, h
in
(y
1
, y
2
,
…, y
n
)
из
R
f(h
i1
(y
1
, y
2
, …, y
n
), h
i2
(y
1
, y
2
, …, y
n
), …, h
in
(y
1
, y
2
, …, y
n
))
∈
R.
4.
(О функциональной полноте). Можно построить систему
замкнутых классов в
P
k
M
1
, M
2
, …, M
s
, каждый из которых цели-
ком не содержит ни одного из остальных классов, и такую, что
подсистема функций из
P
k
полна тогда и только тогда, когда она
целиком не содержится ни в одном из классов
M
1
, M
2
, …, M
s
.
5.
Пусть система функций
S
функций из
P
k
,
где k
≥3, содер-
жит все функции одной переменной. Тогда для полноты системы
S
необходимо и достаточно, чтобы
S
содержала существенную
функцию
f(x
1
, x
2
, …, x
n
),
принимающую все
k
значений.
6.
Для всякого
k (k
≥
3)
существует в
P
k
замкнутый класс, не
имеющий базиса.
7.
Для всякого
k (k
≥
3)
существует в
P
k
замкнутый класс, со
счетным базисом.
4.4
Задачи
и
упражнения
Пример 1.
Докажите справедливость неравенства
x
~
)
x
(
=
−
Доказательство:
1)
)
k
(mod
1
x
x
+
=
2)
))
k
(mod
1
x
(
)
x
(
+
−
=
−
получаем 2 случая:
а) получаемое число становится менее нуля,
из определения разности по модулю k:
1
x
k
)
1
x
(
k
)
0
))
k
(mod
1
x
((
k
)
x
(
−
−
=
+
−
=
−
+
−
=
−
.
б) получаемое число становится равным нулю,
1
k
1
))
k
(mod
1
0
(
)
x
(
−
=
−
=
+
−
=
−
.
С другой стороны:
x
)
1
k
(
x
~
−
−
=
.
Таким образом, в случаях а) и б) формулы приобретают
одинаковые значения, что и требовалось доказать.
45
Пример 2.
Для k=3 представить функцию
x
f
= в первой и второй фор-
мах (полученные выражения упростить)
Для представления функции в первой форме:
{
}
)
x
(
J
),...,
x
(
J
),
x
(
J
),
,...
,
(
f
min(
max
)
x
,...,
x
,
x
(
f
n
2
2
1
n
2
1
~
n
2
1
n
1
σ
σ
σ
σ
σ
σ
σ
=
{
}
{
}
))
x
(
J
,
0
min(
)),
x
(
J
,
2
min(
)),
x
(
J
,
1
min(
max
))
x
(
J
,
2
min(
)),
x
(
J
,
1
min(
)),
x
(
J
,
0
min(
max
x
2
1
0
2
1
0
=
=
Для представления функции во второй форме:
)
x
(
j
...
)
x
(
j
)
x
(
j
)
~
(
f
)
x
~
(
f
n
n
~
2
2
1
n
1
σ
σ
σ
σ
σ
∑
⋅
⋅
⋅
⋅
=
)
x
(
j
2
)
x
(
j
)
x
(
j
0
)
x
(
j
2
)
x
(
j
1
)
x
(
j
2
)
x
(
j
1
)
x
(
j
0
x
1
0
2
1
0
2
1
0
⋅
+
=
⋅
+
⋅
+
⋅
=
⋅
+
⋅
+
⋅
=
I. Докажите справедливость следующих неравенств
1)
(
)
2
1
2
1
x
x
~
x
x
÷
=
⊃
;
2)
(
)
(
)
2
1
2
1
1
x
,
x
min
x
x
x
=
÷
÷
;
3)
(
)
(
)
2
1
2
2
1
x
,
x
max
x
x
x
=
⊃
⊃
;
4)
(
)
)
x
,
x
min(
x
x
x
2
1
1
2
1
=
+
⊃
;
5)
)
x
,
x
min(
x
x
x
2
1
1
2
1
−
=
÷
;
6)
2
2
1
2
1
x
)
x
,
x
max(
x
x
−
=
÷
;
7)
)
x
,
x
max(
~
)
x
x
(
)
x
(~
2
1
1
2
1
=
÷
÷
;
8)
1
2
2
1
x
x
)
x
(~
)
x
(~
÷
=
÷
;
9)
)
x
(~
)
x
(~
)
x
x
(
~
2
1
2
1
+
=
+
;
10)
(
) (
)
2
1
2
1
x
x
~
x
x
~
⋅
=
⋅
;
11)
x
))
x
(
J
,
1
)
2
x
max((
2
k
=
÷
+
−
;
12)
x
)
x
)
2
k
(
),
x
(
J
min(~
1
k
=
⊃
−
−
;
13)
)
x
(
j
x
)
x
(
j
x
)
x
x
(
x
x
1
1
k
2
2
1
k
1
2
1
2
1
−
−
⋅
+
⋅
+
÷
=
÷
;
14)
)
x
,
x
max(
)
x
(
j
x
)
x
(
j
x
)
x
,
x
(
v
2
1
1
1
k
2
2
1
k
1
2
1
k
=
⋅
+
⋅
+
−
−
;
15)
)
x
,
x
max(
x
)
x
(
j
)
x
x
(
j
)
x
,
x
max(
2
1
2
1
k
1
2
0
2
1
=
⋅
+
÷
+
;
16)
)
x
,
x
min(
x
)
x
(
j
)
x
x
(
J
)
x
x
min(
2
1
2
1
1
k
1
2
0
2
,
1
=
⋅
−
÷
+
−
;
17)
(
)
)
x
(
J
))
x
(
J
),...,
x
(
J
),
x
(
J
max(
J
1
k
2
k
1
0
0
−
−
=
;
18)
(
)
(
)
)
x
(
J
)
x
(
J
),...,
x
(
J
),
x
(
J
,
1
,
x
max
J
0
2
k
2
1
1
=
−
;