Лекция Логические переменные в двузначной логике Определение Логической переменной в двузначной логике называется перемен ная величина x, принимающая значения из некоторого двухэлементного множества

• Название: Лекция Логические переменные в двузначной логике Определение Логической переменной в двузначной логике называется перемен ная величина x, принимающая значения из некоторого двухэлементного множества
• Дата: 03.04.2019
• Размер: 283.73 Kb.
• Имя файла: diskr2с.pdf
• Тип: Лекция; #72512
• страница: 2 из 2

) = a ?
j max j=1
?(x i
1
? · · · ? x i
k
),
где
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
j max
? IN,
k ? IN,
m ? IN,
1 ? m ? k,
i m
? IN,
1 ? i m
? n.
Пример 2. Докажем, что
Ї
x = 1 ? x.
(6)
Доказательство.
Таблица 1
x
Ї
x
1 ? x
0 1 1
1 0 0
Упражнение 1 (д/з). Доказать:
x ? y = x ? y ? (x ? y).
(7)
Доказательство.
Таблица 2
x y
x ? y x ? y x ? y x ? y ? (x ? y)
0 0 0
0 0
0 0 1 1
1 0
1 1 0 1
1 0
1 1 1 1
0 1
1
Замечание 2. Известно, что любую композицию логических функций всегда можно представить в виде полинома Жегалкина, причем единственным образом. Для этого нужно:
14

1) заменить логические функции на соответствующие эквивалентные функции, яв- ляющиеся полиномами Жегалкина (см. (6), (7)),
2) произвести упрощения в полученной формуле, используя следующие свойства функций ? (см. лекции) и ?:
Группа I.
1.
x ? y = y ? x;
2.
x ? (y ? z) = (x ? y) ? z = x ? y ? z;
3.
x ? x = x;
4.
x ? 0 = 0;
5.
x ? 1 = x.
Группа II.
1.
x ? y = y ? x;
2.
(x ? y) ? z = x ? (y ? z) = x ? y ? z;
3.
x ? x = 0;
4.
x ? 0 = x.
Группа III.
1.
x ? (y ? z) = (x ? y) ? (x ? z).
(8)
Результат операций 1)2) и будет полиномом Жегалкина для данной композиции.
Замечание 3. Cоотношения (8) легко проверить табличным способом.
Пример 3. Проверим соотношение II.3 из (8).
Решение.
Таблица 3
x x ? x
0 0
1 0
Упражнение 2 (д/з). Проверить другие соотношения из (8).
Пример 4. Представить в виде полинома Жегалкина функцию f(x, y) = Їx?(x?y).
Решение. f(x, y)
(6),(7)
=
1?x?x?y ?(x?y)
(8):II.3
=
1?0?y ?(x?y)
(8):II.4
=
1?y ?(x?y)
Упражнение 3 (д/з). Представить в виде полинома Жегалкина функцию f(x, y) =
(x ? Ї
y) ? (Ї
x ? y)
Решение. f(x, y) = (x?Їy)?(Їx?y)
(6)
= (x?(1?y))?((1?x)?y)
(7)

= x?(1?y)?(x?(1?
y))?(1?x)?y?((1?x)?y)
(8):III.1
=
x?(1?y)?(x?1)?(x?y)?(1?x)?y?(1?y)?(x?y)
(8):II.2
=
x ? 1 ? y ? (x ? 1) ? (x ? y) ? 1 ? x ? y ? (1 ? y) ? (x ? y)
(8):I.5

= x ? 1 ? y ? x ? (x ? y) ? 1 ? x ? y ?
y ? (x ? y)
(8):II.3
=
0 ? 1 ? y ? (x ? y) ? 1 ? x ? 0 ? (x ? y)
(8):II.3
=
0 ? 0 ? 0 ? 0 ? x ? y
(8):II.4
=
x ? y
Теорема (без доква). Любая логическая функция может быть представлена в виде полинома Жегалкина и притом единственным образом.
Замечание 4. Полином Жегалкина также можно найти методом неопределенных коэффициентов. Рассмотрим этот метод на следующем примере.
15

Пример 5. Представить в виде полинома Жегалкина функцию двух переменных,
заданную таблицей 4.
Таблица 4
x y
f (x, y)
0 0 0
0 1 1
1 0 1
1 1 0
Решение. Полином Жегалкина для функции двух переменных ищем в следующем виде:
f (x, y) = a
0
? a
1
? x ? a
2
? y ? a
3
? x ? y,
(9)
где a i
? {0, 1}
, i = 0, . . . , 3. Очевидно, если a i
= 0
, то соответствующее слагаемое фактически не входит в полином, а если a i
= 1
, то входит.
Для определения коэффициентов полинома нужно подставить значения неизвест- ных и соответствующее значение функции в (9) согласно таблице 4. Последовательно подставляя все возможные наборы значений переменных в (9), получим:
?
?
?
?
?
?
?
(0, 0) : 0 = a
0
? a
1
? 0 ? a
2
? 0 ? a
3
? 0 ? 0 ? a
0
= 0;
(0, 1) : 1 = 1 ? a
1
? 0 ? a
2
? 1 ? a
3
? 0 ? 1 ? a
2
= 1;
(1, 0) : 1 = 1 ? a
1
? 1 ? 1 ? 0 ? a
3
? 1 ? 0 ? a
1
= 1;
(1, 1) : 0 = 1 ? 1 ? 1 ? 1 ? 1 ? a
3
? 1 ? 1 ? a
3
= 0.
Подставляя в (9) найденные значения коэффициентов, получим искомый полином
Жегалкина для данной функции: f(x, y) = x ? y.
Замечание 6. Сравним результат примера 5 и упражнения 3. Для комбинации функций и эквивалентной ей функции, заданной табличным способом, мы получаем один и тот же полином Жегалкина, что согласуется с утверждением теоремы о его единственности.
Упражнение 4 (д/з). Представить в виде полинома Жегалкина функцию двух переменных, заданную таблицей 5.
Таблица 5
x y
f (x, y)
0 0 1
0 1 0
1 0 1
1 1 1
Ответ. f(x, y) = 1 ? y ? (x ? y).
Замечание 7. Pезультат примера 4 и упражнения 4 совпадают аналогично заме- чанию 6.
16

Лекция 6. Совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ и СКНФ) логических функций
Любая логическая функция эквивалентна некоторым стандартным композициям конъюнкций, дизъюнкций и отрицаний ее аргументов, называемым совершенными нор- мальными формами. Чтобы определить эти композиции, введем
Определение 1. Пусть x  некоторая логическая переменная со значениями из
E
2
= {0, 1}
, а ?  число 0 или 1. Тогда положим x
?
=
Ї
x,
если ? = 0,
x,
если ? = 1,
т.е. 0 0
= 1
, 0 1
= 0
, 1 0
= 0
, 1 1
= 1
Далее пусть x i
(i = 1, . . . , n)
 логические переменные со значениями из E
2
, а ?
i
(i =
1, . . . , n)
 некоторые значения переменных x i
. Тогда x
?
i i
=
Ї
x i
,
если ?
i
= 0,
x i
,
если ?
i
= 1.
В этих обозначениях имеет место
Утверждение 1. Для любой логической функции n переменных x
1
, . . . , x n
справед- лива формула f (x
1
, . . . , x n
) =
?
1
,...,?
n
: f (?
1
,...,?
n
)=1
x
?
1 1
? · · · · · ?x
?
n n
(10)
Упражнение 1 (д/з). Доказать утверждение 1.
Определение 2. Равенство (10) называется совершенной дизъюнктивной нормаль- ной формой (СДНФ) функции f(x
1
, . . . , x n
)
Для того чтобы составить СДНФ для функции f, заданной табличным способом,
нужно рассмотреть строки значений аргументов, для которых значение функции равно
1. Каждой строке соответствует элементарная конъюнкция вида x
?
1 1
? · · · ? x
?
n n
, где
?
i
(i = 1, . . . , n)
 значение переменной x i
в данной строке. СДНФ представляет собой дизъюнкцию этих элементарных конъюнкций.
Пример 1. Зададим некоторую логическую функцию трех переменных таблицей
1. Построим СДНФ для этой функции.
Таблица 1
x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
0 0
0 0
0 0
1 1
0 1
0 0
0 1
1 0
1 0
0 1
1 0
1 1
1 1
0 0
1 1
1 0
17

Решение. Столбец значений функции содержит три единицы во второй, пятой и шестой строках. Вторая строка таблицы содержит значения ?
1
= 0
, ?
2
= 0
и ?
3
= 1
Им соответствует элементарная конъюнкция Їx
1
? Ї
x
2
? x
3
. Аналогично пятой строке соответствует x
1
? Ї
x
2
? Ї
x
3
, а шестой  x
1
? Ї
x
2
?x
3
. Следовательно, СДНФ данной функции имеет вид f (x
1
, x
2
, x
3
) = (Ї
x
1
? Ї
x
2
? x
3
) ? (x
1
? Ї
x
2
? Ї
x
3
) ? (x
1
? Ї
x
2
? x
3
).
Упражнение 2 (д/з). Проверить эквивалентность полученной СДНФ исходной функции.
Упражнение 3 (д/з). Построить СДНФ для функции, заданной таблицей 2.
Таблица 2
x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
0 0
0 1
0 0
1 0
0 1
0 0
0 1
1 0
1 0
0 0
1 0
1 1
1 1
0 1
1 1
1 0
Справедливо также
Утверждение 2. Для любой логической функции n переменных справедлива фор- мула f (x
1
, . . . , x n
) =
?
1
,...,?
n
: f (?
1
,...,?
n
)=0
x
1??
1 1
? · · · ? x
1??
n n
(11)
Упражнение 4 (д/з). Доказать утверждение 2.
Определение 2. Равенство (11) называется совершенной конъюнктивной нормаль- ной формой (СКНФ) функции f(x
1
, . . . , x n
)
Для того чтобы составить СКНФ для функции f, заданной табличным способом,
нужно рассмотреть строки значений аргументов, для которых значение функции равно
0. Каждой такой строке соответствует элементарная дизъюнкция вида x
1??
1 1
?· · ·?x
1??
n n
,
где ?
i
(i = 1, . . . , n)
 значение переменной x i
в данной строке и x
1??
i i
=
Ї
x i
,
если ?
i
= 1,
x i
,
если ?
i
= 0.
СКНФ представляет собой конъюнкцию этих элементарных дизъюнкций.
Пример 2. Построим СКНФ для функции из примера 1.
Таблица 1 18

x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
0 0
0 0
0 0
1 1
0 1
0 0
0 1
1 0
1 0
0 1
1 0
1 1
1 1
0 0
1 1
1 0
Решение. Значения функции равны 0 для первой, третьей, четвертой, седьмой и восьмой строк, причем первой строке соответствует элементарная дизъюнкция x
1
? x
2
?
x
3
, третьей  x
1
? Ї
x
2
? x
3
, четвертой  x
1
? Ї
x
2
? Ї
x
3
, седьмой  Їx
1
? Ї
x
2
? x
3
и восьмой 
Ї
x
1
? Ї
x
2
? Ї
x
3
. Следовательно, СКНФ данной функции имеет вид f (x
1
, x
2
, x
3
) = (x
1
? x
2
? x
3
) ? (x
1
? Ї
x
2
? x
3
) ? (x
1
? Ї
x
2
? Ї
x
3
) ? (Ї
x
1
? Ї
x
2
? x
3
) ? (Ї
x
1
? Ї
x
2
? Ї
x
3
).
Упражнение 5 (д/з). Проверить эквивалентность полученной СКНФ исходной функции.
Упражнение 6 (д/з). Построить СКНФ для функции, заданной таблицей 2.
Замечание 1. Способ задания логических функций полиномами Жегалкина, со- вершенными дизъюнктивными и конъюнктивными нормальными формами и другими композициями заданных функций называется формульным.
19

Лекция 7. Полные системы и замкнутые классы логических функций
Ранее рассматривались два способа задания логической функции  табличный и формульный. Табличный способ универсален (т.е. пригоден для любой функции), но громоздок. Формула  более компактный способ, но она задает функцию через дру- гие функции. Поэтому возникает вопрос: любая ли логическая функция может быть представлена формулой через функции некоторой заданной системы?
Определение 1. Система логических функций {f
1
, . . . , f n
}
называется (функци- онально) полной, если любая логическая функция может быть представлена в виде некоторой композиции, в которую входят только функции данной системы.
Пример 1. Система функций {1, x
1
?x
2
, x
1
?x
2
}
является полной, так как любая ло- гическая функция может быть представлена полиномом Жегалкина, т.е. композицией,
в которую входят только функции данной системы.
Упражнение 1 (д/з). Привести другие примеры полных систем логических функций.
Определение 2. Множество логических функций называется замкнутым классом,
если любая композиция функций из этого множества снова принадлежит ему.
Рассмотрим основные замкнутые классы логических функций:
Определение 3. Логическая функция f(x
1
, . . . , x n
)
называется сохраняющей ноль,
если для нее выполняется равенство: f(0, . . . , 0) = 0. Класс всех логических функций любого числа переменных, сохраняющих ноль, обозначается T
0
Пример 2. Проверить, что следующие функции принадлежат классу T
0
: a) кон- станта 0, б) тождественная функция x, в) конъюнкция x
1
? x
2
Упражнение 2 (д/з). Проверить, что следующие функции принадлежат классу
T
0
: а) дизъюнкция x
1
? x
2
, б) сложение по модулю 2 x
1
? x
2
Упражнение 3 (д/з). Проверить, что следующие функции не принадлежат клас- су T
0
: a) константа 1, б) отрицание Їx.
Утверждение 1. T
0
 замкнутый класс.
Доказательство. Пусть функции f(x
1
, . . . , x m
)
, а также f
1
(x
1,1
, . . . , x
1,n
1
), . . . , f m
(x m,1
, . . . , x m,n m
)
(некоторые из этих переменных могут совпадать между собой) принадлежат T
0
. Дока- жем, что функция F = f(f
1
, . . . , f m
)
принадлежит T
0
. Последнее соотношение вытекает из следующей цепочки равенств:
F (0, . . . , 0) = f (f
1
(0, . . . , 0), . . . , f m
(0, . . . , 0)) = f (0, . . . , 0) = 0.
Определение 4. Логическая функция f(x
1
, . . . , x n
)
называется сохраняющей еди- ницу, если для нее выполняется равенство: f(1, . . . , 1) = 1. Класс всех логических функ- ций любого числа переменных, сохраняющих единицу, обозначается T
1
Пример 3. Проверить, что следующие функции принадлежат классу T
1
: a) кон- станта 1, б) конъюнкция x
1
? x
2 20

Упражнение 4 (д/з). Проверить, что следующие функции принадлежат классу
T
1
: а) тождественная функция x, б) дизъюнкция x
1
? x
2
Упражнение 5 (д/з). Проверить, что следующие функции не принадлежат клас- су T
1
: a) константа 0, б) отрицание Їx.
Утверждение 2. T
1
 замкнутый класс.
Упражнение 6 (д/з). Доказать утверждение 2.
Определение 5. Функция f
?
(x
1
, . . . , x n
)
называется двойственной функцией к функ- ции f(x
1
, . . . , x n
)
, если она определяется равенством f
?
(x
1
, . . . , x n
) = Ї
f (Ї
x
1
, . . . , Ї
x n
)
Определение 6. Операция замены 0 на 1 и 1 на 0 в столбце значений функции называется инвертированием.
Замечание 1. Очевидно, что таблица для двойственной функции f
?
(x
1
, . . . , x n
)
получается из таблицы функции f(x
1
, . . . , x n
)
двумя последовательными операциями: а)
инвертированием столбца значений функции и б) переворачиванием инвертированного столбца. Проиллюстрируем это на примере функции трех переменных.
Таблица 1
x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
Ї
f (x
1
, x
2
, x
3
)
f
?
(x
1
, x
2
, x
3
)
0 0
0 1
0 0
0 0
1 1
0 1
0 1
0 0
1 0
0 1
1 0
1 1
1 0
0 0
1 1
1 0
1 1
0 1
1 1
0 0
1 0
1 1
1 1
0 0
Упражнение 7 (д/з). Доказать, что следующие функции двойственны друг дру- гу: а) константа 0 и константа 1, б) тождественная функция x и отрицание Їx, в) конъ- юнкция x
1
? x
2
и дизъюнкция x
1
? x
2
Упражнение 8 (д/з). Доказать, что отношение двойственности между функци- ями f и f
?
симметрично.
Определение 7. Функция f(x
1
, . . . , x n
)
называется самодвойственной, если она равна своей двойственной, т.е. выполняется следующее условие: f(x
1
, . . . , x n
) = f
?
(x
1
, . . . , x n
)
или f (x
1
, . . . , x n
) = Ї
f (Ї
x
1
, . . . , Ї
x n
).
(12)
Замечание 2. Для того чтобы функция была самодвойственной, нужно, чтобы значения функции на противоположных наборах переменных (т.е. на наборах, равно- удаленных от начала и конца таблицы) были противоположны.
21

Пример 4. Докажем, что функция f, заданная таблицей 2, самодвойственна.
Таблица 2
x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
0 0
0 0
0 0
1 1
0 1
0 1
0 1
1 0
1 0
0 1
1 0
1 0
1 1
0 0
1 1
1 1
Доказательство. Действительно, инвертируя заданную функцию, получим Ї
f (x
1
, x
2
, x
3
)
Переворачивая столбец значений функции Ї
f (x
1
, x
2
, x
3
)
, получим двойственную функ- цию к f(x
1
, x
2
, x
3
)
, т.е. f
?
(x
1
, x
2
, x
3
)
:
Таблица 3
x
1
x
2
x
3
f (x
1
, x
2
, x
3
)
Ї
f (x
1
, x
2
, x
3
)
f
?
(x
1
, x
2
, x
3
)
0 0
0 0
1 0
0 0
1 1
0 1
0 1
0 1
0 1
0 1
1 0
1 0
1 0
0 1
0 1
1 0
1 0
1 0
1 1
0 0
1 0
1 1
1 1
0 1
Сравнивая значения функций f и f
?
, видим, что f(x
1
, x
2
, x
3
) = f
?
(x
1
, x
2
, x
3
)
при всех значениях аргументов. Следовательно, согласно (12) заданная функция самодвой- ственная.
Упражнение 9 (д/з). Доказать, что следующие функции являются самодвой- ственными: а) тождественная функция x, б) отрицание Їx.
Упражнение 10 (д/з). Доказать, что следующие функции не являются самодвой- ственными: а) конъюнкция x
1
? x
2
, б) дизъюнкция x
1
? x
2
Обозначение. Класс всех самодвойственных логических функций любого числа переменных обозначается S.
Утверждение 3 (без доказательства). S  замкнутый класс.
Определение 8. Для двух наборов значений логических переменных a = (a
1
, . . . , a n
)
и b = (b
1
, . . . , b n
)
будем писать a ? b, если a
1
? b
1
, . . . , a n
? b n
Пример 5. Для a = (0, 1, 0, 1) и b = (1, 1, 0, 1) выполнено a ? b.
22

Замечание 3. Следует отметить, что не для любых пар наборов значений перемен- ных имеет место a ? b или b ? a.
Пример 6. Для a = (0, 1) и b = (1, 0) ни a ? b, ни b ? a не имеет места.
Упражнение 11 (д/з). Показать, что: а) (a ? b) ? (a b)
; б) обратное, вообще говоря, неверно.
Определение 9. Логическая функция f(x
1
, . . . , x n
)
называется монотонной, если для любых двух наборов значений n переменных a и b таких, что a ? b, имеет место неравенство:
f (a) ? f (b).
(13)
Правило проверки логических функций, заданных таблицей с лексико- графическим порядком наборов значений аргументов, на монотонность:
1. Попытаться найти наборы значений переменных a
?
и b
?
такие, что a
?
? b
?
,
1 = f (a
?
) > f (b
?
) = 0.
(14)
Отметим, что в силу упражнения 11 при этом с необходимостью имеем a
?
b
?
, т.е.
достаточно проверить условие a
?
? b
?
для всех таких a
?
и b
?
, что a
?
b
?
,
1 = f (a
?
) > f (b
?
) = 0
(15)
(строка a
?
находится выше строки b
?
в таблице задания функции, но значение функции f (a
?
) = 1
больше, чем f(b
?
) = 0
).
2. Если найдутся a
?
и b
?
, для которых выполнено (14), то в силу определения 9
функция f не является монотонной.
3. Если не найдутся a
?
и b
?
, для которых выполнено (14), то в силу определения 9
функция f является монотонной.
Пример 7. Проверить монотонность следующих функций: а) константы 0, б) тож- дественной функции x, в) конъюнкции x
1
? x
2
, г) отрицания Їx.
Упражнение 12 (д/з). Проверить монотонность следующих функций: а) констан- ты 1, б) дизъюнкции x
1
? x
2
Пример 8. Проверить монотонность функций f
1
, f
2
и f
3
, заданных следующей таблицей:
Таблица 4
x
1
x
2
x
3
f
1
(x
1
, x
2
, x
3
)
f
2
(x
1
, x
2
, x
3
)
f
3
(x
1
, x
2
, x
3
)
0 0
0 0
0 0
0 0
1 0
1 0
0 1
0 0
0 1
0 1
1 1
1 1
1 0
0 1
1 0
1 0
1 1
0 1
1 1
0 1
0 1
1 1
1 1
1 1
23

Решение. а) В таблице задания функции f
1
нет строк, удовлетворяющих (15)
(таких, что строка a
?
находится выше строки b
?
в таблице задания функции, но значение функции f
1
(a
?
) = 1
, а f
1
(b
?
) = 0
), а следовательно, нет и строк, удовлетворяющих (14).
Поэтому функция f
1
монотонна в силу пункта 3 правила.
б) В соответствии с правилом для функции f
2
вторую строку (f
2
(a
?
1
, a
?
2
, a
?
3
) = f (0, 0, 1) =
1)
можно сравнивать с третьей, шестой и седьмой строками, где f
2
(b
1
, b
2
, b
3
) = 0
. Набор значений переменных второй строки не находится в отношении ? с набором третьей строки, а с набором шестой строки находится в этом отношении, т.е. (0, 0, 1) ? (1, 0, 1)
(выполнено первое из условий (14)). Сравнивая значения функции f
2
для этих строк,
получим: 1 = f
2
(0, 0, 1) > f
2
(1, 0, 1) = 0
, т.е. второе из условий (14) также выполнено.
Следовательно, функция f
2
не является монотонной в силу пункта 2 правила.
в) Для функции f
3
наборы значений переменных третьей и четвертой строк, где f
3
(a
1
, a
2
, a
3
) = 1
, можно было бы сравнить с наборами пятой строки, для которой f
3
(b
?
1
, b
?
2
, b
?
3
) = f
3
(1, 0, 0) = 0
. Но наборы значений переменных этих строк не находятся в отношении ? с набором пятой строки (второе из условий (14) не выполнено для них),
поэтому эти строки не следует сравнивать. Другие строки также не следует сравнивать,
т.к. для них значение функции в предшествующей строке не больше значения функции в последующей строке (не выполнено первое из условий (14)). Следовательно, функция f
3
монотонна в силу пункта 3 правила.
Класс всех монотонных логических функций обозначается M.
Утверждение 4 (без доказательства). M  замкнутый класс.
Определение 10. Логическая функция называется линейной, если полином Же- галкина, представляющий данную функцию, содержит только линейные слагаемые, т.е.
f (x
1
, . . . , x n
) = a
0
? a
1
? x
1
? a
2
? x
2
? · · · ? a n
? x n
,
(16)
где a i
? {0, 1}, i = 1, . . . , n
Пример 9. Проверить, являются ли линейными следующие функции: а) константа
0, б) тождественная функция x, в) дизъюнкция x
1
? x
2
Упражнение 13 (д/з). Проверить, являются ли линейными следующие функции:
а) константа 1, б) отрицание Їx, в) сложение по модулю 2 x
1
? x
2
Для проверки функции на линейность полезна следующая теорема.
Теорема (без доказательства). Если в таблице задания функции количество значе- ний функции, равных 1, не равно количеству значений функции, равных 0, то функция не является линейной. Если равно, то надо проверять функцию на линейность.
Класс всех линейных логических функций обозначается L.
Утверждение 5 (без доказательства). L  замкнутый класс.
Теорема Поста (без доказательства). Для того чтобы система функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов T
0
, T
1
, S, M
и L.
Из данной теоремы следует, что при проверке системы на полноту надо все функции системы проверить на принадлежность одному классу, затем другому и т.д. При этом достаточно найти хотя бы одну функцию, не принадлежащую данному классу. Тогда
24

остальные функции системы на принадлежность этому классу можно не проверять.
Если при проверке окажется, что все функции системы принадлежат данному классу,
то проверку надо закончить, т.к. по теореме Поста такая система не будет полной.
Пример 10. Проверить на полноту следующую систему функций: {x
1
? x
2
, x
1
?x
2
}
Для проверки составим следующую таблицу (см. предыдущие примеры и упражнения).
Таблица 5
f
T
0
T
1
S
M
L
?

+ 


?
+ +  + 
В данной таблице знак + означает, что функция принадлежит соответствующему классу, а знак ?, что не принадлежит. Из таблицы видно, что все функции данной систе- мы принадлежат классу
1
. Следовательно, по теореме Поста данная система функций не является полной.
Пример 11. Проверить на полноту следующую систему функций: {Їx
1
, x
1
? x
2
}
Решение. Функция x не сохраняет 0, не сохраняет 1 и не является монотонной.
Функция x
1
? x
2
не является ни самодвойственной, ни линейной. Из этого следует, что в данной системе функций есть хотя бы одна функция, не принадлежащая каждому из пяти замкнутых классов. Следовательно, данная система функций полна.
Замечание 4. Можно показать, что если функция не принадлежит классам T
0
, T
1
и S, то она не принадлежит и классам M и L. Следовательно, по теореме Поста любая система, содержащая хотя бы одну такую функцию, полна.
Упражнение 14 (д/з). Исследовать на полноту следующие системы функций: а)
{x, 1}
, б) {x
1
? x
2
, x
1
? x
2
}
, в) {x
1
? x
2
, x
1
}
25

Лекция 8. Элементы теории кодирования
Пусть имеется канал связи, по которому передается двоичная информация (нули и единицы).
Определение 1. Если двоичная последовательность разбивается на блоки длины k
, которые в соответствии с процедурой кодирования преобразуются в блоки длины n ? k
, то такое кодирование называется блочным.
Пример 1. Код проверки на четность: двоичный блок (a
1
, . . . , a k
)
длины k преобра- зуется в блок (a
1
, . . . , a k
, a k+1
)
длины k + 1, где a k+1
=
k i=1
a i
. Код проверки на четность позволяет обнаруживать одиночную ошибку. Если в полученном сообщении k+1
i=1
a i
= 1
,
это свидетельствует о наличии по крайней мере одной ошибки или нечетного числа ошибок (почему?!)
Будем рассматривать множества Z
2
= {0, 1}
, Z
n
2
= {0, 1} Ч {0, 1} Ч · · · Ч {0, 1}
(n раз) как линейные пространства с операциями сложения по модулю 2 и умножения на
0 или 1.
Определение 2. Линейным (n, k)кодом будем называть линейное подпростран- ство C размерности k в линейном пространстве Z
n
2
Определение 3. Если u ? Z
n
2
, будем называть весом вектора w(u) число его еди- ничных координат.
Определение 4. Если u, v ? Z
n
2
, будем называть расстоянием между векторами u и v величину d(u, v)
=
def w(u + v)
(число координат с одинаковыми номерами, которые различаются у u и v).
Определение 5. Будем называть величину d(C) = min u,v?C
d(u, v)
весом кода C.
Определение 6. Матрицу G размера k Ч n, строки которой составлены из ко- ординат векторов g
1
, . . . , g n
некоторого базиса кода C, будем называть порождающей матрицей кода C.
Определение 7. Пусть Їa = (a
1
, . . . , a n
) ? Z
n
2
, Їb = (b
1
, . . . , b n
) ? Z
n
2
. Величину
(Ї
a, Ї
b) = a
1
b
1
+ · · · + a n
b n
mod 2
будем называть псевдоскалярным произведением векторов Їa и Їb. В случае (Їa, Їb) = 0
будем называть векторы Їa и Їb ортогональными. Если C  линейное подпространство
Z
n
2
, то множество C
?
= {Ї
b ? Z
n
2
: ?Ї
a ? C (Ї
a, Ї
b) = 0}
будем называть ортогональным дополнением C.
Замечание 1. Очевидно, C
?
само является линейным подпространством. Из курса линейной алгебры известно, что его размерность равна n ? k.
Замечание 2. Возможно, что (Їa, Їa) = 0 при Їa = 0, т.е. одна из аксиом скалярного произведения не выполняется для (Їa, Їb), поэтому такое произведение называют псевдо- скалярным.
Упражнение 1 (д/з). Привести пример Їa = 0 такого, что (Їa, Їa) = 0.
26

Определение 8. Пусть C
?
 ортогональное дополнение кода C. Тогда код C
?

называют двойственным к коду C, а его порождающую матрицу H размерности (n ?
k) Ч n
 проверочной матрицей кода C. Очевидно, Їb ? C
?
тогда и только тогда, когда
HЇ
b
T
= 0
Пример 2. Пусть процедура кодирования состоит в том, что двоичному вектору
(a
1
, a
2
, a
3
)
длины 3 сопоставляется двоичный вектор (a
1
, . . . , a
5
)
длины 5 по формулам a
4
= a
1
+ a
2
,
a
5
= a
2
+ a
3
Тогда код C есть множество решений этой системы линейных однородных уравнений ранга 2 с пятью неизвестными. Следовательно, код C имеет размерность 3. Фундамен- тальную систему решений можно выбрать из векторов
(10010)
(01011)
(00101).
Порождающая матрица кода C, таким образом, имеет вид
?
?
1 0 0 1 0 0 1 0 1 1 0 0 1 0 1
?
?
Ортогональным кодом C
?
будет множество решений системы уравнений
?
?
?
b
1
+ b
4
= 0,
b
2
+ b
4
+ b
5
= 0,
b
3
+ b
5
= 0.
Фундаментальная система решений имеет вид
(11010)
(01101).
Таким образом, проверочная матрица кода C есть
H =
1 1 0 1 0 0 1 1 0 1
Код C есть линейный (5, 3)-код.
Путем переименования неизвестных a
1
, . . . , a n
и линейных преобразований над стро- ками матрицы H можно всегда добиться, чтобы проверочная матрица имела вид H
0
=
[P, I
n?k
]
, где I
n?k
 единичная подматрица размерности n?k. В нашем примере H = H
0
Проверочная матрица может быть задана в виде G
0
= [I
k
, Q]
27

Связь между порождающей и проверочной матрицей дает
Предложение 1. Если H
0
= [P, I
n?k
]
 проверочная матрица (n, k)кода C, то
G
0
= [I
k
, ?P
T
]
 его порождающая матрица.
Наоборот, если G
0
= [I
k
, Q]
 порождающая матрица кода, то H
0
= [?Q
T
, I
n?k
]

его проверочная матрица.
Доказательство. Нужно лишь проверить, что H
0
· G
T
0
= 0
Предложение 2. Вес линейного (n, k)кода равен d тогда и только тогда, когда любые d ? 1 столбцов проверочной матрицы линейно независимы, но некоторые d столбцов линейно зависимы.
Доказательство. Достаточность. Допустим противное. Пусть вес кода равен d и столбцы с номерами i
1
< i
2
< · · · < i d?1
линейно зависимы. Тогда, взяв вектор Їb с единицами на местах i
1
, i
2
, . . . , i d?1
и нулями на всех остальных, получим, что HЇb
T
= 0
Но тогда Їa  кодовое слово с весом, меньшим d. Противоречие.
Необходимость. Любой вектор веса d не может быть кодовым словом, и существу- ет вектор Їa
?
, являющийся кодовым словом.
Предложение доказано.
Следствие. d ? n ? k + 1.
Доказательство. Число линейно независимых столбцов не превосходит числа строк матрицы H. Поэтому d ? 1 ? n ? k, ч.т.д.
Предложение 3. а) Линейный код C обнаруживает t ошибок тогда и только тогда, когда вес кода d ? t + 1.
б) Линейный код C исправляет t ошибок тогда и только тогда, когда вес кода d ? 2t + 1
Доказательство. а) Если вес кода равен m ? t, то найдутся два кодовых слова Їa и Їb, расстояние между которыми равно m. Тогда, сделав m ошибок, возможно, мы на приеме вместо слова Їa получим слово Їb. Но тогда у нас не будет оснований утверждать о наличии ошибок, так как полученное слово будет являться кодовым. Если же вес кода не менее t + 1, то при наличии не более t ошибок на приеме мы не получим кодового слова и, следовательно, сможем констатировать наличие ошибок.
б) Пусть w(C) ? 2t + 1. Если Їa ? C и r > 0, то множество B
r
(Ї
a) = {Ї ? Z
2
n
:
d(Ї
a,Ї) ? r}
назовем шаром радиуса r с центром в точке Їa. Очевидно, что если Їa, Їb ? C,
то шары B
t
(Ї
a)
и B
t
(Ї
b)
не могут пересекаться. Поэтому, если в слове Їa сделано не более t
ошибок, то полученное слово Їc декодируем как Їa, т.е. ошибки будут исправлены. Если же w(C) ? 2t, то некоторые шары B
t
(Ї
a)
и B
t
(Ї
b)
могут пересекаться, и тогда слово Їa,
после того как в нем сделано t ошибок, может попасть в шар B
t
(Ї
b)
, и в этом случае мы не сможем правильно декодировать его.
Предложение доказано.
28