WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Бульові функції - Реферат

Бульові функції - Реферат

виходами: s = x y, d = x y. З цих формул видно, що схема має реалізувати додавання двох однорозрядних чисел із переносом. Виразимо s за допомогою функцій набору { , , }: s = x y x y. Тоді схема має вигляд:
x s
d
y
Задачі
6. З використанням І-, АБО- та НЕ-елементів накреслити комбінаційну схему, відповідну:
1) функції ;
2) функції ;
3) функції ;
4) функції |;
5) функції голосування xy xz yz;
6) арифметичному додаванню двох однорозрядних двійкових чисел із переносом, складену з функціональних елементів у мінімальній кількості;
7) арифметичному додаванню трьоходнорозрядних двійкових чисел із переносом;
8) арифметичному додаванню двох дворозрядних двійкових чисел із переносом у третій розряд;
9) додаванню 1 до дворозрядного двійкового числа із втратою переносу зі старшого розряду;
10) порівнянню "=" двох дворозрядних двійкових чисел;
11) порівнянню ">" двох дворозрядних двійкових чисел;
12) порівнянню " " двох дворозрядних двійкових чисел.
7. З використанням І- та -елементів, а також входів, на які подається 1, накреслити комбінаційну схему, відповідну:
1) функції ;
2) функції ;
3) функції ;
4) функції |;
5) функції голосування xy xz yz;
6) арифметичному додаванню двох однорозрядних двійкових чисел із переносом;
7) арифметичному додаванню трьох однорозрядних двійкових чисел із переносом;
8) арифметичному додаванню двох дворозрядних двійкових чисел із переносом у третій розряд;
9) додаванню 1 до дворозрядного двійкового числа із втратою переносу зі старшого розряду;
10) порівнянню "=" двох дворозрядних двійкових чисел;
11) порівнянню ">" двох дворозрядних двійкових чисел;
12) порівнянню " " двох дворозрядних двійкових чисел.
3. Замкнені та повні набори функцій. Критерій Поста повноти набору функцій
У підрозділі 7.1 ми побачили, що будь-яку бульову функцію можна задати як суперпозицію функцій з набору { , , } або з набору { , , 1}.
Означення. Множина всіх функцій, що є суперпозиціями функцій деякого набору F, і лише їх, називається замиканням цього набору й позначається [F].
Таким чином, якщо P2 позначає множину всіх бульових функцій, то
{ , , } = [{ , , 1}] = P2.
Означення. Множина функцій F називається функціонально повною, якщо F =P2.
Отже, множини { , , } і { , , 1} є функціонально повними.
Природним є питання про те, які властивості повинні мати функціонально повні множини функцій.
Видатний математик Еміль Пост сформулював і обгрунтував критерій повноти множини функцій у загальному випадку алгебри функцій з операцією суперпозиції. У цьому критерії, тобто необхідній і достатній умові, використовується поняття передповного класу. Розглянемо його.
Нехай F позначає множину всіх можливих функцій деякої алгебри функцій A з операцією суперпозиції.
Означення. Множина функцій S називається передповним класом алгебри A, якщо S F і за будь-якої функції f з множини FS набір S {f} є повним: S {f} =F.
Критерій Поста. Нехай S1, S2, … - усі передповні класи алгебри функцій F. Множина функцій M є повною тоді й тільки тоді, коли для кожного передповного класу Si множина M містить f MSi.
Приймемо це твердження без доведення.
Пост також дослідив передповні класи алгебри бульових функцій. Їх виявилося лише 5. Це множини всіх функцій:
що зберігають сталу 0,
що зберігають сталу 1,
самодвоїстих,
лінійних,
монотонних.
Означимо вказані функції.
Означення. Функція f(n) зберігає сталу 0, якщо на нульовому наборі має значення 0: f(n)(0, 0, …, 0)=0.
Означення. Функція f(n) зберігає сталу 1, якщо на одиничному наборі має значення 1: f(n)(1, 1, …, 1)=1.
Наприклад, тотожна функція f(x)=x зберігає сталі 0 і 1, функція f(x)= x не зберігає жодної.
****Двоїста до …
Означення. Функція f(n) є самодвоїстою, якщо для всіх пар протилежних наборів вона приймає на них протилежні значення:
f(n)( 1, 2, …, n) = ****f(n)( 1, 2, …, n) зберігає сталу 0, якщо на нульовому наборі має значення 0: f(n)(0, 0, …, 0)=0.
Означення. Функція f(n) зберігає сталу 1, якщо на одиничному наборі має значення 1: f(n)(1, 1, …, 1)=1.
Неважко переконатися, що множини означених функцій, позначені відповідно T0, T1, S, L, M, є замкненими класами.
Задачі
8. Визначити, чи є наступна множина функцій замкненим класом. Вважається, що з кожною функцією f із цієї множини до неї належать також усі функції, конгруентні f:
1) {0, 1};
2) { x};
3) {1, x};
4) {x1 … xn, n 1};
5) {1, x1 … x2n, n 1}
6) {0, x1 … xn, n 1}
7) {0, x1 … x2n, n 1}
8) {x1 … xn, n 1}
9) {0, x1 … x2n, n 1}
9. Визначити, чи істинно, що за будь-яких замкнених класів(будь-якого замкненого класу):
1) їх перетин є замкненим класом;
2) їх об'єднання є замкненим класом;
3) їх різниця є замкненим класом;
4) його доповнення не є замкненим класом.
10. Поставити один із знаків , , =, , , , яким за будь-яких множин F1 і F2 найточніше виражається теоретико-множинне відношення між множинами:
1) [F1 F2] і [F1] [F2];
2) [F1 F2] і [F1] [F2];
3) [F1F2] і [F1][F2].
11. Визначити, чи є двоїстими одна до одної функції:
1) x y і x y;
2) x y і y x;
3) xy xz yz і xy xz yz;
4) x y z і x y z;
5) x y і x y;
6) x y і x y;
7) x y і x|y;
8) x y і x|y.
Застосувавши критерій Поста повноти системи функцій, визначити, чи є повним наступний набір функцій, і якщо так, то виділити в ньому всі можливі базиси:
1) { , , };
2) { , , };
3) { , , };
4) { , 0, , };
5) { , 1, , };
6) { , 0, , };
7) { , , };
8) { , , };
9) {|, , };
10) {|, , };
11) { , 1, , };
12) {1, , , };
13) {1, , , };
14) { , 1, , };
15) {1, , , };
16) {1, , , };
17) { , , };
18) { , , };
19) { , 0, , };
20) {0, , , };
21) {0, , , };
22) { , 0, , };
23) {0, , , };
24) {0, , , }.
8. Обчислити кількість функцій від n змінних у множині:
1) T0 T1;
2) T0 T1;
3) T0 L;
4) T0 L;
5) L(T0 T1);
6) L(T0 T1);
7) Lk - лінійних функцій, що мають k суттєвих змінних;
8) S T1;
9) T0S;
10) L S T1;
11) S (T0 T1);
12) S (T0T1);
13) S(T0 T1);
14) Sk - самодвоїстих функцій, що мають k суттєвих змінних;
15) M(T0 T1);
16) M(T0 T1);
17) M L;
18) M L S;
19) L(M S).
Loading...

 
 

Цікаве