Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс (1083731), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Имеют место следующие свойства:

1. [A]  A;

2. A  B  [A]  [B], причём, если в левой части импликации строгое вложение, то из него вовсе не следует строгое вложение в правой части — верно лишь

A  B  [A]  [B];

1. [[A]] = [A].

Определение 2. Система функций алгебры логики A называется полной, если [A] = P₂.

Определение 3. Пусть A  P₂. Тогда система A называется замкнутым классом, если замыкание A совпадает с самим A: [A] = A.

Утверждение. Пусть A — замкнутый класс, A  P₂ и B  A. Тогда B — неполная система (подмножество неполной системы будет также неполной системой).

Доказательство. B  A  [B]  [A] = A  P₂  [B]  P₂. Следовательно, B — неполная система. Утверждение доказано.

2°. Примеры замкнутых классов.

Класс T₀ = {f (x₁, …, x_n) | f (0, …, 0) = 0}.

Классу T₀ принадлежат, например, функции 0, x, xy, x  y, x  y.

Классу T₀ не принадлежат функции 1, , x  y, x | y, x  y, x ~ y.

Подсчитаем число функций в классе T₀. Для этого построим следующую таблицу:

.

Все функции, принадлежащие указанному классу, принимают на нулевом наборе нулевое значение. Таким образом, всего функций в классе T₀ столько, сколько существует булевых векторов длины 2ⁿ – 1 (первый разряд вектора длины 2ⁿ необходимо равен нулю), то есть .

Теорема 6. Класс T₀ —замкнутый.

Доказательство. Рассмотрим произвольную систему функций алгебры логики из T₀. Рассмотрим функцию

.

Среди переменных функций g_i могут встречаться и одинаковые, поэтому в качестве переменных функции h возьмём все различные из них. Тогда h (0, …, 0) = f (g₁ (0, …, 0), …, g_n (0, …, 0)) = f (0, …, 0) = 0 , следовательно, функция h также сохраняет ноль. Рассмотрен только частный случай (без переменных в качестве аргументов). Однако, поскольку тождественная функция сохраняет ноль, подстановка простых переменных эквивалентна подстановке тождественной функции, теорема доказана.

Класс T₁ = {f (x₁, …, x_n) | f (1, 1, …, 1) = 1}.

Классу T₁ принадлежат функции 1, x, xy, x  y, x  y, x ~ y.

Классу T₁ не принадлежат функции 0, , x  y, x | y, x  y.

Теорема 7. Класс T₁ замкнут.

Доказательство повторяет доказательство аналогичной теоремы для класса T₀.

Класс L линейных функций.

Определение 4. Функция алгебры логики f (x₁, …, x_n) называется линейной, если

f (x₁, …, x_n) = a₀  a₁ x₁  …  a_n x_n, где a_i  {0, 1}.

Иными словами, в полиноме линейной функции нет слагаемых, содержащих конъюнкцию.

Классу L принадлежат функции 0, 1, , x ~ y, x  y.

Классу L не принадлежат функции xy, x  y, x  y, x | y, x  y.

Теорема 8. Класс L замкнут.

Доказательство. Поскольку тождественная функция — линейная, достаточно (как и в теоремах 6 и 7) рассмотреть только случай подстановки в формулы функций: пусть f (x₁, …, x_n)  L и g_i  L. Достаточно доказать, что f (g₁, …, g_n)L. Действительно, если не учитывать слагаемых с коэффициентами a_i = 0, то всякую линейную функцию можно представить в виде . Если теперь вместо каждого подставить линейное выражение, то получится снова линейное выражение (или константа единица или нуль).

§6. Двойственность. Класс самодвойственных функций, его замкнутость.

1°. Двойственность.

Определение 1. Функцией, двойственной к функции алгебры логики f (x₁, …, x_n), называется функция .

Теорема 9 (принцип двойственности). Пусть

.

Тогда .

Доказательство. Рассмотрим

Теорема доказана.

Следствие. Пусть функция Φ (y₁, …, y_m) реализуется формулой над A = {f₁, f₂, …}. Тогда если в этой формуле всюду заменить вхождения f_i на f_i^*, то получится формула, реализующая Φ^* (y₁, …, y_m).

Утверждение. Для любой функции алгебры логики f (x₁, …, x_n) справедливо равенство

f (x₁, …, x_n) = f ^** (x₁, …, x_n).

Доказательство. , и утверждение доказано.

2°. Класс S самодвойственных функций.

Определение 2. Функция алгебры логики f (x₁, …, x_n) называется самодвойственной, если

f (x₁, …, x_n) = f ^* (x₁, …, x_n).

Иначе говоря, S = {f | f = f ^*}.

Классу S принадлежат функции

x, , x  y  z  a, .

Классу S не принадлежат функции

0 ( ), 1,
x  y (поскольку ), xy.

Теорема 10. Класс S замкнут.

Доказательство. Пусть f (x₁, …, x_n)  S, i ,
i = 1, 2, …, n и

.

Тогда из принципа двойственности следует, что

= f (g₁ (…), …, g_n (…)).

Таким образом, мы получили, что Φ = Φ^* и Φ  S. Теорема доказана.

§7. Класс монотонных функций, его замкнутость.

Определение 1. Пусть и .
Тогда

.

Замечание. Существуют наборы, для которых неприменимо отношение упорядоченности, определённое выше. Так, например, наборы (0, 0, 1) и (0, 1, 0) несравнимы.

Определение 2. Функция алгебры логики f (x₁, …, x_n) называется монотонной, если для любых двух сравнимых наборов и выполняется импликация

.

Класс всех монотонных функций обозначим M.

Классу M принадлежат функции

0, 1, x, xy, x  y, m (x, y, z) = xy  yz  zx.

Классу M не принадлежат функции

, x | y , x  y , x  y , x ~ y , x  y.

Теорема 11. Класс M замкнут.

Доказательство. Поскольку тождественная функция монотонна, достаточно проверить лишь случай суперпозиции функций. Пусть
f (x₁, …, x_n)  M, для любого j g_j (y₁, …, y_m)  M и

Φ (y₁, …, y_m) = f (g₁ (y₁, …, y_m), …, g_n (y₁, …, y_m)).

Рассмотрим произвольные наборы , такие, что . Обозначим

.

Тогда для любого i имеем g_i  M и , то есть . Обозначим

.

Тогда по определению и, в силу монотонности функции f, . Но

, ,

откуда , следовательно, Ф  M. Теорема доказана.

§8. Лемма о несамодвойственной функции

Лемма (о несамодвойственной функции). Из любой несамодвойственной функции алгебры логики f (x₁, …, x_n), подставляя вместо всех переменных функции и x, можно получить φ (x)  const.

Доказательство. Пусть f  S. Тогда

.

Построим функцию φ (x) так: φ (x) = f (x  σ₁, …, x  σ_n). Тогда

 (0) = f (σ₁, …, σ_n),

и φ (0) = φ (1)  φ (x) = const. Заметим, что подстановка удовлетворяет условию теоремы, так как . Лемма доказана.

§9. Лемма о немонотонной функции

Лемма (о немонотонной функции). Из любой немонотонной функции алгебры логики f (x₁, …, x_n), подставляя вместо всех переменных функции x, 0, 1, можно получить функцию .

Доказательство. Пусть f  M. Тогда существуют такие наборы и , что (то есть j (α_j  β_j) и ) и . Выделим те разряды i₁, …, i_k наборов и , в которых они различаются. Очевидно, в наборе эти разряды равны 0, а в наборе — 1. Рассмотрим последовательность наборов таких, что , где получается из заменой одного из нулей, расположенного в одной из позиций i₁, …, i_k, на единицу (при этом наборы и — соседние). Поскольку , а , среди наборов найдутся два соседних и , такие что и . Пусть они различаются в r-ом разряде: , . Тогда определим функцию φ (x) так: φ (x) = f (α₁, α₂, …, α_{r – 1}, x, α_{r + 1}, …, α_n). Действительно, тогда , и . Лемма доказана.

§10. Лемма о нелинейной функции

Лемма (о нелинейной функции). Из любой нелинейной функции алгебры логики f (x₁, …, x_n), подставляя вместо всех переменных x, , y, , 0, 1, можно получить φ (x, y) = x · y или .

Доказательство. Пусть f (x₁, …, x_n)  L. Рассмотрим полином Жегалкина этой функции. Из её нелинейности следует, что в нём присутствуют слагаемые вида . Не ограничивая общности рассуждений, будем считать, что присутствует произведение x₁ · x₂ · …. Таким образом, полином Жегалкина этой функции выглядит так:

f (x₁, …, x_n) = x₁ · x₂ · P₁ (x₃, …, x_n)  x₁ · P₂ (x₃, …, x_n) 
 x₂ · P₃ (x₃, …, x_n)  P₄ (x₃, …, x_n),

причем P₁ (x₃, …, x_n)  0. Иначе говоря,  a₃, a₄, …, a_n  E₂ = {0, 1} такие, что P₁ (a₃, a₄, …, a_n) = 1. Рассмотрим вспомогательную функцию f (x₁, x₂, a₃, a₄, …, a_n) = x₁ x₂ · 1  x₁ · b  x₂ · c  d. Тогда функция

f (x  с, y  b, a₃, a₄, …, a_n) = (x  c)(y  b)  (x  c)b  (y  b)c  d =
= xy  x · b  y · c  b · c  x · b  b · c  y · c  b · c  d =
= xy  (bc  d) = .

Лемма доказана.

§11. Теорема Поста о полноте системы функций алгебры
логики

Теорема 12 (теорема Поста). Система функций алгебры логики
A = {f₁, f₂, …} является полной в P₂ тогда и только тогда, когда она не содержится целиком ни в одном из следующих классов: T₀, T₁, S, L, M.

Доказательство. Необходимость. Пусть A — полная система,
N — любой из классов T₀, T₁, S, L, M и пусть A  N. Тогда

[A]  [N] = N  P₂ и [A]  P₂.

Полученное противоречие завершает обоснование необходимости.

Достаточность. Пусть A  T₀, A  T₁, A  M, A  L, A  S. Тогда в A существуют функции f₀  T₀, f₁  T₁, f_M  M, f_L  L, f_S  S. Достаточно показать, что [A]  [f₀, f₁, f_M, f_L, f_S] = P₂. Разобьём доказательство на три части: получение отрицания, констант и конъюнкции.

1. Получение . Рассмотрим функцию f₀ (x₁, …, x_n)  T₀ и получим из нее функцию φ₀ (x) = f₀ (x, x, …, x). Так как функция f₀ не сохраняет нуль, φ₀ (0) = f (0, 0, …, 0) = 1. Возможны два случая: либо , либо φ₀ (x)  1. Рассмотрим функцию f₁ (x₁, …, x_n)  T₁ и аналогичным образом получим функцию
   φ₁ (x) = f₁ (x, x, …, x). Так как функция f₁ не сохраняет единицу, φ₁ (1) = f (1, 1, …, 1) = 0. Возможны также два случая: либо , либо φ₁ (x)  0. Если хотя бы в одном случае получилось искомое отрицание, пункт завершён. Если же в обоих случаях получились константы, то согласно лемме о немонотонной функции, подставляя в функцию f_M  M вместо всех переменных константы и тождественную функцию, можно получить отрицание. Отрицание получено.

2. Получение констант 0 и 1. Имеем f_S  S. Согласно лемме о несамодвойственной функции, подставляя вместо всех переменных функции f_S отрицание (которое получено в пункте a) и тождественную функцию, можно получить константы:
   [f_S, ]  [0, 1]. Константы получены.

3. Получение конъюнкции x · y. Имеем функцию f_L  L. Согласно лемме о нелинейной функции, подставляя в функцию f_L вместо всех переменных константы, переменные и отрицания переменных (которые были получены на предыдущих шагах доказательства), можно получить либо конъюнкцию, либо отрицание конъюнкции. Однако на первом этапе отрицание уже получено, следовательно, всегда можно получить конъюнкцию: [f_L, 0, 1, ]  [xy, ]. Конъюнкция получена.

В результате получено, что . Последнее равенство следует из пункта 2 теоремы 4. В силу леммы 2 достаточность доказана.

§12. Теорема о максимальном числе функций в базисе алгебры логики

Характеристики

Список файлов лекций