Курс лекцій для студентів спеціальностей, пов’язаних з інформаційними технологіями та



Сторінка3/16
Дата конвертації27.01.2020
Розмір1,37 Mb.
ТипКурс лекцій
1   2   3   4   5   6   7   8   9   ...   16
Поняття булевої функції

Способи подання булевих функцій

Булевою функцією називається відображення виду , nN. Кількість n-арних булевих функцій дорівнює . Булева функція може мати ім’я.

Булеву функцію можна подати таблицею. Розглянемо приклад. Побудуємо тернарну булеву функцію f у вигляді таблиці:



x

y

z

f(x,y,z)

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

1

1

1

1

1

Набори значень аргументів 000, 001, 010, 011, 100, 101, 110, 111 функції f можна розглядати як послідовні невід’ємні цілі числа у двійковій системі числення. Таким чином, з кожним набором значень аргументів функції f можна зв’язати невід’ємне ціле число (будемо називати його номером цього набору): з набором 000 – число 0, з набором 001 – число 1, з набором 010 – число 2, з набором 011 – число 3, з набором 100 – число 4, з набором 101 – число 5, з набором 110 – число 6, з набором 111 – число 7. Надалі будемо вважати, що набори значень аргументів булевої функції розташовані у порядку зростання їх номерів.

Булева функція може також подаватися вектором значень аргументів (у векторній формі). При цьому значення булевої функції у векторі розташовані по порядку номерів наборів значень аргументів цієї функції. Наприклад, поданням у векторній формі функції f з попереднього прикладу є вектор (01100011).

Розглянемо булеві функції, які вважаються елементарними. Такими є: 0-арні булеві функції (позначаються 0 та 1 й називаються відповідно тотожним нулем й тотожною одиницею); функція f1(0)=0, f1(1)=1 (називається тотожною функцією, f1(х) позначається х); функція f2(0)=1, f2(1)=0 (називається запереченням, f2(х) позначається х або ). Решту елементарних булевих функцій подамо таблицею:


x

y

f3(x,y)

f4(x,y)

f5(x,y)

f6(x,y)

f7(x,y)

f8(x,y)

f9(x,y)

0

0

0

0

0

1

1

1

1

0

1

0

1

1

0

1

1

0

1

0

0

1

1

0

0

1

0

1

1

1

1

0

1

1

0

0

Функція f3 називається кон’юнкцією, f3(x,y) позначається xy (або xy, або xy). Функція f4 називається диз’юнкцією, f4(x,y) позначається xy. Функція f5 називається сумою за модулем 2, f5(x,y) позначається xy. Функція f6 називається еквівалентністю, f6(x,y) позначається xy (або x~y, або xy). Функція f7 називається імплікацією, f7(x,y) позначається xy (або xy). Функція f8 називається штрихом Шефера, f8(x,y) позначається x|y. Функція f9 називається стрілкою Пірса, f9(x,y) позначається xy.

Символи , , , , ~, , |,  та інші, що використовуються для позначення елементарних функцій, будемо називати логічними зв’язками.

Нехай Х – скінченна або зліченна множина змінних (алфавіт змін-них), Ф – множина функціональних символів. Функціональним символом будемо називати вираз виду fn, де nN; число n називається арністю (міс-ністю) функціонального символу. Іноді замість виразу «функціональний символ fn» використовуватимемо вирази «функціональний символ f арності n», «n-арний функціональний символ». Функціональні символи можуть мати нижні індекси. Надалі будемо вважати, що змінні, які вико-ристовуються, належать множині Х. Визначимо поняття формули над множиною Ф (формули над Ф):

1) 0-арний функціональний символ з множини Ф є формулою над Ф,

2) якщо f n-арний функціональний символ (nN+) з множини Ф, x1,…,xn – змінні, то f(x1,…,xn) є формулою над Ф,

3) якщо f m-арний функціональний символ (mN+) з множини Ф, ui – змінна або формула над Ф ( ), то f(u1,…,um) – формула над Ф,

4) інших формул над Ф немає.

Наведемо приклади формул над множиною функціональних символів. Нехай Х={x,y,z}, Ф={f0, t1, g1, s2}. Тоді f0 є формулою над Ф за правилом 1 означення поняття формули над множиною функціональних символів; t(х) та s(y,z) є формулами над Ф за правилом 2 того ж означення; g(s(y,z)) є формулою над Ф за правилом 3. Вираз h(x,y) не є формулою над Ф, адже символ h не належить множині Ф. Вираз g(хх) також не є формулою над Ф, оскільки хх не є ані змінною з множини Х, ані формулою над Ф.

Позначимо через S множину логічних зв’язок {, , , , ~, , |, }. Визначимо поняття формули над S:

1) змінна з множини Х є формулою над S,

2) якщо F1 та F2 – формули над S, то (F1), (F1)  (F2), (F1)  (F2), (F1)  (F2), (F1) ~ (F2), (F1)  (F2), (F1) | (F2), (F1)  (F2) – формули над S,

3) інших формул над S немає.

Для скорочення запису зовнішні дужки у формулі будемо опускати. Будемо вважати, що зв’язка  має найбільший ранг серед зв’язок множини S, а зв’язка  має більший ранг, ніж , , ~, , |, . Беручи до уваги зауваження щодо рангів логічних зв’язок, формулу ((х)((у)))  (z) можна записати так: хуz.

Зазначимо, що множина функціональних символів Ф може містити й логічні зв’язки. У таких випадках використовується мішана форма запису формул. Нехай, наприклад, Ф = {h3, , g1, }. Формулу (g1(х), h3(х, у, х)) у мішаній формі можна подати таким чином: g1(х)  h3(х, у, х), а формулу (х, (g1(х),у)) – таким чином: х  (g1(х)  у).

Нехай Ф – множина функціональних символів. Нехай з кожним символом fn з множини Ф зв’язана булева функція tf: {0,1}n  {0,1} (nN) (тобто задано відображення множини Ф у множину булевих функцій, яке зберігає арність).



Нехай, наприклад, Ф={f1, f2, f3}. Зв’яжемо з функціональним символом f1 булеву функцію {<0,1>,<1,0>}, з символом f2 – булеву функцію додавання за модулем 2, з символом f3 – булеву функцію (00101110). Іноді зручно (але не обов’язково) вважати, що функціональний символ fn зв’язано з n-арною булевою функцією, що має ім’я f, й, навпаки, булева функція арності n й з іменем f зв’язана з функціональним символом fn.

Визначимо поняття функції F, що реалізується формулою F над множиною Ф:

1) якщо F = fn(x1,…,xn), де fnФ, x1,…,xn – змінні, то для кожного набору (a1an) значень змінних x1,…,xn значення функції F дорівнює tf(a1,...,an); функцію F будемо позначати tf(х1,..,хn),

2) якщо F = f(u1,…,um), де fФ, а uі – змінна з множини Х або формула Fi( ,…, ) над Ф, й на наборі виду … значень змінних ,…, функція приймає значення ( ), то



( , ,…, ,…, , ,…, ,…, , ,…, )=tf( ,…, ,…, ),

функцію F будемо позначати tf(t1,…,tm), де ti – це ui, якщо ui – змінна, й ti – це позначення функції, що реалізується формулою ui, якщо ui не є змінною.

Розглянемо приклади функцій, що реалізуються формулами над множиною функціональних символів. Нехай Х={x,y,z}, Ф={f2, g3}. Нехай з функціональним символом f2 зв’язана булева функція tf, що визначається таким чином: tf(0,0) = tf(0,1) = 0, tf(1,0) = tf(1,1) = 1, а з функціональним сим-волом g3 – функція, що визначається так: нехай tg(0,0,0) = tg(1,1,1) = 0, а на усіх інших наборах значень аргументів значення tg дорівнює 1. Побудуємо формулу над Ф: F = g(x,y,х). Тоді за правилом 1 означення функції, що реалізується формулою над множиною функціональних символів, функцією F, що реалізується формулою F, є функція tg(х,у,х). Розглянемо формулу F1=f(х, g(у,f(z,х),z)) над Ф. За правилом 2 означення функції, що реалізується формулою над множиною функціональних символів, функцією F1, що реалізується формулою F1, є функція tf(x,tg(y,tf(z,x),z)). Розглянемо приклад обчислення значення функції, що реалізується формулою F1, на наборі 011 значень змінних х, у, z (тобто при х=0, у=z=1). Підставимо ці значення у вираз tf(x,tg(y,tf(z,x),z)) та обчислимо його. Маємо: tf(0,tg(1,tf(1,0),1)) = tf(0,tg(1,1,1)) = tf(0,0) = 0.

Визначимо поняття функції F, що реалізується формулою F над множиною звязок S (над множиною логічних звязок):

1) якщо F = х, де xX, то F є тотожна функція, тобто F(х)=х,

2) якщо F = (F1), то F = F1, де  – позначення елементарної булевої функції f2,

3) якщо F = (F1)  (F2) (або (F1)  (F2), або (F1)  (F2), або (F1) ~ (F2), або (F1)  (F2), або (F1) | (F2), або (F1)  (F2)), то F = F1F2, де  – позначення елементарної булевої функції f3 (відповідно F1F2, F1F2, F1 ~ F2, F1F2, F1 | F2, F1F2, де символи , , ~, , |,  є позначеннями елементарних булевих функцій f4, f5, f6, f7, f8, f9).

Таким чином, булева функція може бути подана: таблицею, вектором, формулою.




Каталог: bitstream -> 123456789
123456789 -> Тема: Безпека вулиці: азбука дороги
123456789 -> Методичні вказівки до вивчення дисципліни сво «доктор філософії»
123456789 -> Регіональний підхід до дослідження формування ціннісних орієнтацій студентів мистецьких вишів україни н. Г. Тарарак
123456789 -> Методологічне підґрунтя дослідження формування ціннісних орієнтацій студентів вищих навчальних закладів мистецького профілю україни
123456789 -> Загальна характеристика роботи
123456789 -> Інформаційне суспільство в контексті політичної культури суспільства
123456789 -> Заліщицька районна державна адміністрація Відділ з питань освіти Районний методичний кабінет Використання активних та інноваційних технологій як засіб активізації
123456789 -> Україна тернопільська область опис досвіду роботи учителя біології


Поділіться з Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   16


База даних захищена авторським правом ©pedagogi.org 2019
звернутися до адміністрації

    Головна сторінка