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

Реферат на тему:

Бульові функції

1. Алгебри бульових виразів і бульових функцій

1.1. Основні поняття

Множину {0, 1} позначимо літерою B. Множину всіх можливих послідовностей з 0 і 1 — Bn. Такі послідовності за традицією будемо називати наборами або векторами довжини n. Очевидно, Bn містить 2n елементів. Значення 0 і 1 називаються протилежними одне до одного.

Означення. Всюди визначена функція з Bn у B називається n-місною функцією алгебри логіки або n-місною бульовою функцією.

Послідовність змінних (x1, x2, …, xn) із значеннями у B позначимо $${\tilde{x}}^n$$

. Бульова функція f (.

) задається у вигляді таблиці, або графіка зі стандартним розташуванням наборів:

Зауважимо, що в стандартному розташуванні набори можна розглядати як двійкові записи послідовних чисел від 0 до 2n-1. Функцію, задану зі стандартним розташуванням наборів, можна ототожнити з набором довжини 2n. Наприклад, двомісну функцію, задану таблицею.

можна ототожнити з вектором (1011).

Далі іноді будемо позначати n-місну функцію f ($${\tilde{x}}^n$$

) як f (n)(.

), підкреслюючи кількість змінних, від яких вона залежить.

Очевидно, що множина всіх можливих наборів довжини 2n, тобто множина n-місних бульових функцій, складається з 22n елементів. При n=0 це 2, при n=1 — 4, при n=2 — 16, при n=3 — 256 тощо.

Нуль-місними функціями є сталі 0 і 1.

Одномісні функції подано у наступній таблиці разом з виразами, якими ці функції позначаються:

Функції 0 і 1 називаються тотожними нулем і одиницею, функція x — тотожною, запереченням. Замість виразу вживається ще вираз $$\stackrel{}{x}$$. Ці вирази читаються як «не x» .

Подамо також деякі з 16 двомісних функцій разом із їх позначеннями:

Функція, позначена виразом xназивається кон’юнкцією і позначається ще як x&-y, xабо xy. Усі ці вирази читаються як «x і y» .

Функція, позначена виразом xназивається диз’юнкцією. Вираз читається як «x або y» .

Функція, позначена виразом xназивається імплікацією і позначається ще як xЦі вирази читаються як «x імплікує y» або «з x випливає y» .

Функція, позначена виразом xназивається еквівалентністю і позначається ще як x~y або xЦі вирази читаються як «x еквівалентно y», що в даному випадку збігається з «x дорівнює y» .

Функція, позначена виразом xназивається додаванням за модулем 2 або «виключним або». Зауважимо, що її значення є протилежними до значень еквівалентності.

Функція, позначена виразом x|y, називається штрихом Шеффера і має значення, протилежні значенням кон’юнкції. Її вираз читається як «не x або не y» .

Функція, позначена виразом xназивається стрілкою Пірса і має значення, протилежні значенням диз’юнкції. Її вираз читається як «не x і не y» .

Зауважимо, що інфіксні позначення наведених функцій вигляду x f y, де f — відповідний знак, склалися історично. Їх так само можна позначати й у вигляді f (x, y), наприклад, y).

З тримісних функцій наведемо лише так звану функцію голосування m (x, y, z), графік якої має такий вигляд:

Її назва зумовлена тим, що її значення на кожному наборі збігається з більшістю значень змінних у цьому наборі.

Множину всіх n-місних функцій позначимо P (n), а множину всіх функцій, тобто об'єднання P (n) по всіх n — P2.

Перейдемо до означення таких понять, як алгебра бульових функцій і алгебра формул.

Алгебри бульових функцій, як і всі інші алгебри, визначаються своїми носіями та сигнатурами операцій. Носіями в алгебрах бульових функцій є множини функцій. Сигнатуру складає операція суперпозиції, або підстановки.

Означення. Нехай є n-місна функція f (n)($${\tilde{x}}^n$$) і n функцій g1(y1,1, y1,2, …, y1, m1), g2(y2,1, y2,2, …, y2, m2), …, gn (yn, 1, yn, 2, …, yn, mn), залежні від змінних з деякої їх множини Y={y1, y2, …, yk}. Суперпозицією, або підстановкою функцій g1, g2, …, gn у функцію f (n) називається функція h (m)(y1, y2, …, ym), кожне значення якої h (…, визначається як.

f (n)(g1(,, …, 1), g2(,, …, 2), …, gn (,, …, n)).

Суперпозиція ще позначається як.

S (f (n) — g1(y1,1, y1,2, …, y1, m1), g2(y2,1, y2,2, …, y2, m2), …, gn (yn, 1, yn, 2, …, yn, mn)).

Приклади.

1. h1(x, y, z)=S (yзадається наступною таблицею:

2. h2(x, y)=S (yзадається таблицею:

Нехай є множина бульових функцій F. Утворюючи з них та їх суперпозицій усі можливі суперпозиції, ми одержимо множину функцій, яку позначимо [F]. Отже, маємо алгебру ([F]- S), породжену множиною функцій F. Інша множина функцій F1 буде породжувати, взагалі кажучи, іншу алгебру ([F1]- S). Наприклад, алгебри (111), (0001)}) і (0), (0001)}).

Розглянемо тепер поняття алгебри формул (термів, або виразів). Нехай є множина функцій F. Кожній n-місній функції з F поставимо у взаємно однозначну відповідність символ, що її позначає (функціональний символ) f (n). Нехай X — зліченна множина змінних (точніше, їх імен).

Означення.

1. Ім'я змінної є формулою.

2. Якщо f (n) — функціональний символ, а T1, T2, …, Tn є формулами, то f (n)(T1, T2, …, Tn) є формулою.

3. Інших формул немає.

Це означення задає множину формул із функціональними символами з множини F, які одержуються за допомогою підстановок, тобто суперпозицій. Таким чином, ми маємо алгебру формул, породжену множиною функціональних символів F. Інша множина функціональних символів буде породжувати й іншу алгебру формул.

Зв’язки між алгебрами функцій і алгебрами формул встановлюють наступні два означення.

Означення. Значенням формули T на наборі значень змінних з множини X є:

1) значення змінної x, якщо T є змінною x;

2) f (n)(…, якщо T=f (n)(T1, T2, …, Tn), а формули T1, T2, …, Tn мають на цьому наборі значення відповідно …, /p>

Означення. n-місна бульова функція f (n) задається формулою T, якщо всі змінні у формулі T є змінними з множини X, і при будь-якому наборі значень (…, цих змінних x1, x2, …, xn значення формули дорівнює значенню f (n)(…,.

Звідси випливає інше означення суперпозиції функцій.

Означення. n-місна бульова функція f (n) є суперпозицією функцій f1, f2, …, fn, якщо її можна задати формулою, усі функціональні символи якої є серед символів функцій f1, f2, …, fn.

З наведених прикладів 1 і 2 видно, що функція h1(x, y, z) задається формулою y), z)), або в інфіксному записі (x Аналогічно функція h2(x, y) задається формулою y), x)), або (x Як бачимо, обидві функції задаються формулами з тими самими функціональними символами тобто є суперпозиціями цих функцій.

Наостанок наведемо узгодження, які склалися в математиці й дозволяють у формулах з функціональними символами, аписувати не всі необхідні дужки. ****.

1.2. Суттєві та несуттєві змінні

Розглянемо поняття суттєвої залежності функції від її змінних. Почнемо з прикладів: значення функції h2(x, y) з прикладу 2 на кожному з наборів збігаються зі значеннями x. Отже, зміна значення y не впливає на значення функції, тобто вона фактично не залежить від y. В той час як зміна значення x веде до зміни значення h2. Уточнимо ці міркування наступними означеннями.

Означення. Змінна xi функції f (n)(x1, x2, …, xi, …, xn) називається суттєвою, якщо існує хоча б одна пара наборів значень змінних.

(…,, 0,, …, і (…,, 1,, …,.

така, що.

f (n)(…,, 0,, …, n)(…,, 1,, …,.

Змінна xi називається несуттєвою у противному разі, тобто коли за всіх можливих пар наборів значень.

(…,, 0,, …, і (…,, 1,, …, /p>

мають місце рівності:

f (n)(…,, 0,, …, = f (n)(…,, 1,, …,.

Наприклад, неважко переконатися, що всі змінні функції h1 з прикладу 1 є суттєвими. Функція h2 має суттєву змінну x і несуттєву y. Функція двох змінних, задана як вектор (1111), не має суттєвих змінних.

1.3. Еквівалентні формули та закони

Одна й та сама бульова функція задається, взагалі кажучи, багатьма різними формулами. Наприклад, неважко переконатися, що формули xі обидві задають функцію (1101). Таким чином, можна говорити про еквівалентність цих двох формул.

Означення. Нехай **** Формули і називаються еквівалентними, якщо.

1.4. Канонічні формули для подання бульових функцій

Задачі

1. Побудувати графік функції за формулою, що її задає:

1. 1)/p>

2. 2)x.

3. 3)((xz).

4. 4)((xx;

5. 5).

6. 6)((xx;

7. 7)x (y;

8. 8)x (z.

9. 9)x (y;

10. 10)x (y.

11. 11)x (y;

12. 12)x (y;

13. 13)x (y;

14. 14)x (z;

15. 15)x;

16. 16)x (z;

17. 17)x (y;

18. 18)x (z;

2. Указати суттєві та несуттєві змінні функції, заданої вектором значень при стандартному розташуванні наборів (за зростанням у лексикографічному порядку):

1. 1)(0000 1111 1100 0011);

2. 2)(0000 1111 1111 0010);

3. 3)(0000 1111 0110 0101);

4. 4)(0000 1111 0011 1010);

5. 5)(0000 1111 0011 0110);

6. 6)(0000 1111 1100 1010);

7. 7)(0000 1100 0011 0101);

8. 8)(0000 0011 0011 1101);

9. 9)(0000 0011 1100 0010);

10. 10)(0000 0011 1001 0101);

11. 11)(0000 0011 0101 1111);

12. 12)(0011 1100 0111 1100);

13. 13)(0011 1100 1001 0101);

14. 14)(0011 0011 0011 1010);

15. 15)(0011 0011 1100 1100);

16. 16)(0011 0011 1001 1001);

17. 17)(1001 1001 1100 1100);

18. 18)(1001 1001 1001 0001).

3. За виразом побудувати еквівалентні йому вирази у ДДНФ, ДКНФ, у вигляді полінома Жегалкіна (варіанти 1−18 відповідають варіантам задачі 1).

4. Побудувати формулу з трьома змінними, істинну тоді й тільки тоді, коли:

1. 1)рівно одна змінна має значення 1;

2. 2)не менше ніж одна змінна має значення 1;

3. 3)рівно дві змінні мають значення 1;

4. 4)не менше двох змінних мають значення 1;

5. 5)непарна кількість змінних має значення 1;

6. 6)парна кількість змінних має значення 1.

5. Побудувати формулу з чотирма змінними, істинну тоді й тільки тоді, коли:

1. 1)рівно одна змінна має значення 1;

2. 2)не менше ніж одна змінна має значення 1;

3. 3)рівно дві змінні мають значення 1;

4. 4)не менше двох змінних мають значення 1;

5. 5)рівно три змінні мають значення 1;

6. 6)не менше трьох змінних мають значення 1;

7. 7)непарна кількість змінних має значення 1;

8. 8)парна кількість змінних має значення 1.

2. Бульові функції та комбінаційні схеми