Бу́лева фу́нкція — це відображення [math] n[/math]-вимірної скінченої множини [math] \lbrace 0,1\rbrace^n[/math] у скінчену множину [math] \lbrace 0,1\rbrace[/math] .

[math]\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;f:\lbrace 0,1\rbrace^n \rightarrow \lbrace 0,1\rbrace[/math].

Названі на честь математика Джоржа Буля. Булеві функції є окремим випадком скінчених функцій, які відіграють важливу роль у дискретній математиці. Крім того булеві функції широко застосовуються в математичній логіці, тому їх часто називають логічними функціями або функціями алгебри логіки. Змінні в булевих функціях називають пропозиційними символами, а в програмуванні — булевими змінними. [math]0[/math] і [math]1[/math] — булеві константи.

Булеві функції можна записувати як і звичайні алгебраїчні функції: [math] y=f(x_1,x_2,\ldots,x_n)[/math] , де усі аргументи можуть набувати значення [math]0[/math] або [math]1[/math]. В алгебрі логіки їм відповідають терміни «хибність» та «істина».

Область визначення булевих функцій [math] \lbrace 0,1\rbrace^n[/math] називають булевим кубом. Його вершини — це точки [math]n[/math]-вимірного простору з координатами [math](x_1,x_2,\ldots,x_n)[/math] , де усі [math]x_i[/math] набувають значень [math]0[/math] або [math]1[/math]. Кількість вершин булевого куба дорівнює [math]2^n[/math] . Наприклад, при[math]\;n=2[/math] — булів куб є квадратом з вершинами [math](0;0), (0;1), (1;0)\; та\; (1;1)[/math], а при[math]\;n=3[/math] — кубом з вершинами [math](0;0;0), (0;0;1), (0;1;0), (0;1;1), (1;0;0), (1;0;1), (1;1;0)\;та\;(1;1;1).[/math]

Координати вершин часто записують простіше: замість, [math](x_1,x_2,\ldots,x_n)\;–\;\;x_1,x_2\ldots,x_n, [/math], наприклад, [math]000, 001[/math] і т. д. Кількість функцій, що задана на множині [math] \lbrace 0,1\rbrace^n[/math], дорівнює [math]2^{2^n}[/math] . При [math]n=0[/math] маємо дві функції [math]0[/math] та [math]1[/math], які ототожнюють з нульарними операціями.

При [math]n=1[/math] маємо чотири функції (унарні операції)

де [math]f_1[/math] — тотожна функція, [math]f_2[/math] — заперечення,[math]f_0[/math],[math]f_3[/math] — константи [math]0[/math] та [math]1[/math]. При [math]n=2[/math] булевих функцій — [math]16[/math]:

Функції записані у лексикографічному порядку, тобто номер функції — це десяткове число, записане у двійковій системі числення. Тут [math]f_0,f_{15}[/math] — константи ,[math]f_3,f_5,f_{10}[/math] та [math]f_{12}[/math] — функції від однієї змінної. Наприклад, [math]f_3(x_1,x_2)=x_1[/math] не залежить від [math]x_2[/math] і є тотожною функцією від [math]x_1[/math] , а [math]f_{12}[/math] збігається із запереченням [math]x_1[/math]. Оскільки усі функції, наведені в таблиці, є бінарними операціями, то замість [math]f(x_1,x_2)[/math] будемо записувати [math]x_1\;\circ\;x_2[/math]. Найбільш важливі з них:

1. [math]f_1:x_1\bigwedge x_2[/math] — кон’юнкція (в математичній логіці «[math]x_1[/math] і [math]x_2[/math] »);

2. [math]f_7: x_1\bigvee x_2[/math] — диз’юнкція (в математичній логіці « [math]x_1[/math] або [math]x_2[/math]»);

3.[math]f_6:x_1\bigoplus x_2[/math] — альтернативне або («тільки [math]x_1[/math] або тільки [math]x_2[/math]»);

4. [math]f_9:x_1\sim x_2[/math] — еквівалентність («[math]x_1[/math] тоді і тільки тоді, коли [math]x_2[/math]»);

5. [math]f_{13}:x_1 \to x_2[/math] — імплікація (логічне слідування: «якщо [math]x_1[/math], то [math]x_2[/math]»);

6. [math]f_8:x_1\downarrow x_2[/math] — стрілка Пірса (антидиз’юнкція);

7. [math]f_{14}:x_1 \mid x_2[/math] — штрих Шеффера (антикон’юнкція).

Таблиці булевих функцій (таблиці істинності) при [math]n=2[/math] зручно записувати інакше, наприклад для імплікації ([math]f_{13}[/math]):

Приклад:

Розглянемо два висловлювання: [math]x_1[/math] — «Сидоренко — футболіст», а [math]x_2[/math] — «Петренко — футболіст». Розглянемо такі висловлювання (функції від [math]x_1[/math],[math]x_2[/math] ):

• «Сидоренко і Петренко — футболісти»:([math]x_1\bigwedge x_2[/math]). Це висловлювання буде істинним, якщо обидва [math]x_1[/math] та [math]x_2[/math] істинні (обидва гравці — футболісти), в усіх інших випадках воно буде хибним. Таким чином, якщо [math]x_1=1 [/math]та [math]x_2=1 [/math], будемо мати [math]x_1\bigwedge x_2=1[/math]. В усіх інших випадках [math]x_1\bigwedge x_2=0 [/math] (див. таблицю істинності для функції [math]f_1[/math] — кон’юнкції).

• «Сидоренко або Петренко — футболісти»:([math]x_1\bigvee x_2[/math]). Це висловлювання правильне завжди, крім випадку, коли обидва гравці не є футболістами, тобто, коли [math]x_1=0[/math], та [math]x_2=0[/math] (див. таблицю істинності функції [math]f_7[/math] — диз’юнкції).

• «Тільки Сидоренко — футболіст або тільки Петренко — футболіст»:[math]x_1\bigoplus x_2[/math]. Це висловлювання є істинним, коли один із них — футболіст, а іншій — ні (див.[math]f_6[/math]).

У теоремах математики еквівалентності відповідає термін «необхідна і достатня умова», а імплікації відповідає термін «необхідна умова».

При [math]n=3[/math] булевих функцій буде вже 256.

Табличний спосіб задання булевих функцій при збільшенні кількості змінних є неефективним. Тому аналогічно до математичного аналізу їх записують у вигляді формул, що включають у себе елементарні функції (функції від однієї або двох змінних, наведені вище), наприклад: [math]f_1 = \min {(x_1,x_2,x_3)} = x_1\bigwedge x_2\bigwedge x_3[/math].

У теорії булевих функцій розглядається задача подання будь-якої булевої функції у вигляді формул, що містять строго визначену скінчену кількість елементарних функцій, які називають базисними. Існують різні базиси. Найчастіше використовують стандартний базис. Це функції «не», «і», та «або». Функцію «не» (заперечення) позначають символом [math]\lnot[/math]; функцію «і» (кон’юнкцію) — [math]\bigwedge[/math]; функцію «або» (диз’юнкцію) — [math]\bigvee[/math] . За допомогою цих трьох функцій можна записати у вигляді формул усі інші:

Будь-яку булеву функцію від змінних можна подати у вигляді диз’юнктивної нормальної форми:

де [math]\tilde{x_i}[/math] дорівнює [math]x_i[/math] або [math]\bar{x_i}[/math]. Якщо кожна з кон’юнкцій (кожна дужка) включає усі змінні, то цю форму називають досконалою. Аналогічно, для кожної функції існує кон’юнктивна нормальна форма

Цей базис є зручним для опису електричних кіл із паралельним та послідовним з’єднанням елементів. Існують також базиси:[math]\lbrace\bigvee,\neg\rbrace,\lbrace\bigwedge,\neg\rbrace,\lbrace\bigoplus,\bigwedge,1\rbrace[/math] — базис Жегалкіна та інші. Зокрема базис [math]\lbrace|\rbrace[/math], тобто усі булеві функції, які можна виразити через штрих Шеффера. Оскільки ця операція не є асоціативною, то таким базисом користуються рідко. Те ж саме стосується базису, що складається з однієї функції (стрілки Пірса).

Література

Бардачов Ю. М., Соколова Н. А., Ходаков В. Є. Дискретна математика. Київ : Вища школа, 2002. 287 с.
Anderson J. Discrete Mathematics With Combinatorics. 2nd ed. Upper Saddle River : Pearson Education, 2004. 784 p.
Ершов Ю. Л., Палютин Е. А. Математическая логика. 6-е изд., испр. Москва : Физматлит, 2011. 356 с.
Wu Ch.-K., Feng D. Boolean Functions and Their Applications in Cryptography. Berlin : Springer, 2016. 256 p.

Автор ВУЕ

А. Ю. Андрейцев

Покликання на цю статтю: Андрейцев А. Ю. Булева функція // Велика українська енциклопедія. URL: https://vue.gov.ua/Булева функція (дата звернення: 1.05.2024).

Статус гасла: Оприлюднено
Оприлюднено: 17.08.2021

Важливо!

Ворог не зупиняється у гібридній війні і постійно атакує наш інформаційний простір фейками.

Ми закликаємо послуговуватися інформацією лише з офіційних сторінок органів влади.

Збережіть собі офіційні сторінки Національної поліції України та обласних управлінь поліції, аби оперативно отримувати правдиву інформацію.

Отримуйте інформацію тільки з офіційних сайтів

Булева функція

Література

Автор ВУЕ

Важливо!

Офіс Президента України

Верховна Рада України

Кабінет Міністрів України

Служба безпеки України

Міністерство оборони України

Міністерство внутрішніх справ України

Генеральний штаб Збройних сил України

Державна прикордонна служба України

Кіберполіція

Національна поліція України