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

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

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

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

n), якщо T=f(n)(T1, T2, …, Tn), а формули T1, T2, …, Tn мають на цьому наборі значення відповідно 1, 2, …, n.
Означення. n-місна бульова функція f(n) задається формулою T, якщо всі змінні у формулі T є змінними з множини X, і при будь-якому наборі значень ( 1, 2, …, n) цих змінних x1, x2, …, xn значення формули дорівнює значеннюf(n)( 1, 2, …, n).
Звідси випливає інше означення суперпозиції функцій.
Означення. n-місна бульова функція f(n) є суперпозицією функцій f1, f2, …, fn, якщо її можна задати формулою, усі функціональні символи якої є серед символів функцій f1, f2, …, fn.
З наведених прикладів 1 і 2 видно, що функція h1(x, y, z) задається формулою ( (x, y), (y, z)), або в інфіксному записі (x y) (y z). Аналогічно функція h2(x, y) задається формулою ( (x, y), (y, x)), або (x y) (y x). Як бачимо, обидві функції задаються формулами з тими самими функціональними символами , , , тобто є суперпозиціями цих функцій.
Наостанок наведемо узгодження, які склалися в математиці й дозволяють у формулах з функціональними символами , , , , , , |, записувати не всі необхідні дужки. ****
1.2. Суттєві та несуттєві змінні
Розглянемо поняття суттєвої залежності функції від її змінних. Почнемо з прикладів: значення функції h2(x, y) з прикладу 2 на кожному з наборів збігаються зі значеннями x. Отже, зміна значення y не впливає на значення функції, тобто вона фактично не залежить від y. В той час як зміна значення x веде до зміни значення h2. Уточнимо ці міркування наступними означеннями.
Означення. Змінна xi функції f(n)(x1, x2, …, xi, …, xn) називається суттєвою, якщо існує хоча б одна пара наборів значень змінних
( 1, 2, …, i-1, 0, i+1, …, n) і ( 1, 2, …, i-1, 1, i+1, …, n),
така, що
f(n)( 1, 2, …, i-1, 0, i+1, …, n) f(n)( 1, 2, …, i-1, 1, i+1, …, n).
Змінна xi називається несуттєвою у противному разі, тобто коли за всіх можливих пар наборів значень
( 1, 2, …, i-1, 0, i+1, …, n) і ( 1, 2, …, i-1, 1, i+1, …, n)
мають місце рівності:
f(n)( 1, 2, …, i-1, 0, i+1, …, n) = f(n)( 1, 2, …, i-1, 1, i+1, …, n).
Наприклад, неважко переконатися, що всі змінні функції h1 з прикладу 1 є суттєвими. Функція h2 має суттєву змінну x і несуттєву y. Функція двох змінних, задана як вектор (1111), не має суттєвих змінних.
1.3. Еквівалентні формули та закони
Одна й та сама бульова функція задається, взагалі кажучи, багатьма різними формулами. Наприклад, неважко переконатися, що формули x y і x y обидві задають функцію (1101). Таким чином, можна говорити про еквівалентність цих двох формул.
Означення. Нехай **** Формули 1 і 2 називаються еквівалентними, якщо
1.4. Канонічні формули для подання бульових функцій
Задачі
1. Побудувати графік функції за формулою, що її задає:
1) ((x y) z) x
2) x ( (x y) z);
3) ((x y) z) x;
4) ((x y) z) x;
5) ((x y) z) x;
6) ((x y) z) x;
7) x (y (z x));
8) x (y (z x);
9) x (y (z x));
10) x (y z x);
11) x (y (z x));
12) x (y (y x));
13) x (y (z x));
14) x (y (z x));
15) x ( y (z x));
16) x (y (z x));
17) x (y (z x));
18) x (y (z x));
2. Указати суттєві та несуттєві змінні функції, заданої вектором значень при стандартному розташуванні наборів (за зростанням у лексикографічному порядку):
1) (0000 1111 1100 0011);
2) (0000 1111 1111 0010);
3) (0000 1111 0110 0101);
4) (0000 1111 0011 1010);
5) (0000 1111 0011 0110);
6) (0000 1111 1100 1010);
7) (0000 1100 0011 0101);
8) (0000 0011 0011 1101);
9) (0000 0011 1100 0010);
10) (0000 0011 1001 0101);
11) (0000 0011 0101 1111);
12) (0011 1100 0111 1100);
13) (0011 1100 1001 0101);
14) (0011 0011 0011 1010);
15) (0011 0011 1100 1100);
16) (0011 0011 1001 1001);
17) (1001 1001 1100 1100);
18) (1001 1001 1001 0001).
3. За виразом побудувати еквівалентні йому вирази у ДДНФ, ДКНФ, у вигляді полінома Жегалкіна (варіанти 1-18 відповідають варіантам задачі 1).
4. Побудувати формулу з трьома змінними, істинну тоді й тільки тоді, коли:
1) рівно одна змінна має значення 1;
2) не менше ніж одна змінна має значення 1;
3) рівно дві змінні мають значення 1;
4) не менше двох змінних мають значення 1;
5) непарна кількість змінних має значення 1;
6) парна кількість змінних має значення 1.
5. Побудувати формулу з чотирма змінними, істинну тоді й тільки тоді, коли:
1) рівно одна змінна має значення 1;
2) не менше ніж одна змінна має значення 1;
3) рівно дві змінні мають значення 1;
4) не менше двох змінних мають значення 1;
5) рівно три змінні мають значення 1;
6) не менше трьох змінних мають значення 1;
7) непарна кількість змінних має значення 1;
8) парна кількість змінних має значення 1.
2. Бульові функції та комбінаційні схеми
І-елемент АБО-елемент -елемент НЕ-елемент
a a a
b r b r b r a r
r = a b r = a b r = a b r = a
Розглянемо реалізацію бульових функцій у вигляді комбінаційних схем. Найпростішими з них є логічні елементи, відповідні бульовим функціям: кон'юнкції , диз'юнкції , додавання за модулем 2 та заперечення . Вони позначаються й зображаються таким чином:
Входи перших трьох елементів вважаються симетричними згідно законів комутативності, яким задовольняють кон'юнкція, диз'юнкція та додавання за модулем 2.
З наведених логічних елементів будуються складніші схеми, які в загальному випадку мають n входів і m виходів і реалізують набір з m функцій від n аргументів:
a1 b1
a2 b2
.
.
.
an bm
Тут bj=fj(a1, a2, …, an), j=1, 2, …, m..
Приклади.
1. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує функцію . Виразимо її за допомогою функцій набору { , , }:
x y = x y x y.
x
y
Звідси відповідна схема має вигляд:
2. Побудуємо схему з І- та -елементів, яка реалізує функцію . Виразимо її за допомогою функцій набору { , , 1}:
x y = x y x y.
Звідси відповідна схема має вигляд:
x
y
3. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує так званий "однорозрядний напівсуматор"[****] з двома симетричними входами x, y і двома
Loading...

 
 

Цікаве