Реферат Курсовая Конспект
Теорема о достаточности четырех функций. - раздел Образование, УСМАНОВА Зинира Масгутовна Из Любой Полной В Р2 Системы Функций Можно Выделить Полную ...
|
Из любой полной в Р2 системы функций можно выделить полную подсистему, состоящую не более чем из четырех функций.
Доказательство. Пусть {f0, f1, fL, fM, fS} – полная система функций, тогда она не лежит целиком ни в одном из классов T0, T1, L, M, S. Следовательно, в системе есть функции f0ÏT0, f1ÏT1, fLÏL, fS ÏS и fmÏM. Система {f0, f1, fL, fM, fS} Í P2 и образует полную систему в Р2. Рассмотрим функцию f0: f0(0, ..., 0) = 1.
Если f0(1, ..., 1) = 0, то f0ÏT1 и f0ÏM, тогда {f0, fS, fL} – полная система из трех функций.
Если f0(1, ..., 1) = 1, то f0ÏS и {f0, f1, fL, fM } образует полную систему из четырех функций.
Пример 1, приведенный выше, показывает, что цифру 4 в общем случае уменьшить нельзя, из полной системы {x1x2,0,1,x1Åx2Åx3} нельзя выделить полную подсистему.
Следствие. Базис в Р2 может состоять максимум из четырех функций.
2.7. Функции k - значной логики
Введем обозначение: Eк={0, 1, 2, ..., k–1}.
Функция k-значной логики, зависящая от n переменных, – это закон, отображающий. Множество функций k-значной логики обозначается как Рk. Функция из Рk полностью определена, если задана ее таблица истинности, т.е. заданы значения на всех наборах. Наборы можно рассматривать как записи в k-ичной системе счисления чисел от 0 до k–1, всего наборов kn. Функций из Рk, зависящих от n переменных, будет kn. |P3(n)|, например, будет 3, если n = 2, то |P3(2)| = 39 = 19683 (k=3, n=2).
x1 x2 . . . xn-1 xn | f |
0 0 . . . 0 0 0 0 . . . 0 1 . . . . . . . . . . . . . . . . . . . 0 0 . . . 0 k–1 0 0 . . . 1 0 . . . . . . . . . . . . . . . . . . . k–1 k–1 . . . k–1 k–1 | . . . . . . . |
В k - значной логике также есть функции, которые называются элементарными. Приведем некоторые из них, примеры будем приводить для k = 3 и n = 2.
1. Циклический сдвиг или отрицание Поста: = x+1(mod k).
2. Зеркальное отображение или отрицание Лукосевича: Nx = k–1–x.
Эти две функции являются обобщением отрицания.
3. Ji(x)={k-1, x = i, I = 0, 1, 2, ..., k–1}.
x1 | x2 | Nx | J0(x) | J1(x) | J2(x) |
4. min(x1,x2) – обобщение конъюнкции;
5. x1×x2(mod k) – второе обобщение конъюнкции;
6. max(x1,x2) – обобщение дизъюнкции;
7. x1+x2(mod k) – сумма по mod k.
x1 | x2 | min(x1,x2) | x1x2(mod 3) | max(x1x2) | x1+x2(mod 3) |
Принято min(x1,x2) обозначать x1&x2, max(x1,x2) обозначать x1Úx2.
Как и в двузначной логике, можно ввести понятие формулы над множеством и ставить вопрос о полной в Рk системе функций.
Теорема о полной в Рk системе функций
Cистема функций {max(x1,x2), min(x1,x2), 0, 1, ..., k–1, J0(x), J1(x), ..., Jk-1(x)} является полной в Рk и любая функция f(x1, ..., xn) Î Pk выражается формулой над этой системой следующим образом:
.
Эта формула есть своеобразный аналог СДНФ.
Доказательство. Покажем справедливость этой формулы на любом произвольном наборе (a1, ..., an). Слева имеем f(a1, ..., an). Справа имеем .
Если для какого-нибудь j из {1, 2, ..., n} ij ¹ aj, то (aj) = 0 и min[J(a1), (a2), …, (an), f(i1,..,in)] = 0. Рассмотрим набор (i1, ..., in), где i1 = a1, i2 = a2, ..., in = an, тогда J(a1) = k–1, J(a2) = k–1, .., J(an) = k–1 и min[J(a1), ... , J(an) f(a1, …, an).] = min[(k–1), ..., (k–1), f(a1, …, an).] = f(a1, …, an), но тогда Так как набор (a1, ..., an) произвольный и равенство на нем справедливо, то формула верна. В этой формуле использованы функции Ji(x), (i = 0, ..., k–1), min(x1x2), max(x1x2) и константы 0, ..., k–1, так как функция f(i1, ..., in) есть число из {0, 1, ..., k–1}.
– Конец работы –
Эта тема принадлежит разделу:
АХМЕТОВА Наиля Абдулхамитовна УСМАНОВА Зинира... Замыкание и замкнутые классы...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Теорема о достаточности четырех функций.
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов