Тема „Булеві функції”

Англійський математик Джордж Буль (1815 – 1864) запропонував у формулах літерами позначати не числа, а висловлювання і показав, що можна так вибирати дії додавання та множення, щоб формули звичайної алгебри залишалися без змін. В алгебрі логіки висловлення розглядають не за їхнім змістом або значенням, а тільки відносно того, істинні вони чи хибні. Приймається, що кожне висловлювання може бути тільки істинним або хибним. Істинність висловлення будемо позначати 1, а хибність – 0.

Основним поняттям алгебри логіки є висловлення.

Висловлення – це деяке твердження, про яке можна сказати, що воно є істинним або хибним. Будь-яке висловлення можна позначити символом x і вважати, що x = 1 при істинності і x = 0 при хибності висловлення.

Будемо розглядати функції f(x₁, x₂, …, x_n), аргументи яких виз­начені на множині E₂ = {0, 1}, такі, що f(x₁, x₂, …, x_n)  E₂, коли x_i  E₂.

Означення 1. Логічними (булевими) змінними в булевій алгебрі називаються величини, які незалежно від їхньої конкретної суті можуть набувати лише двох значень, які позначатимемо (0) і (1).

Означення 2. Булевою або перемикальною функцією f(x₁, x₂, …, x_n) називають функцію, яка, як і її n аргументів, може набувати лише двох значень: 0 або 1. Булеві функції застосовуються для опису алгоритмів – дискретних пристроїв. Вони призначені для перетворення дискретної інформації на елементарні одиниці – біти, які в пристроях реалізуються сигналами, що описуються двійковими змінними.

Сукупність значень аргументів є кортежем, точкою або набором. Кожному і-му кортежу можна поставити у відповідність терм – довільний елементарний добуток двійкових змінних t_i = . Якщо в і-му кортежі x_j = 1, то в термі замість записується змінна x_j, а якщо x_j = 0, то .

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

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

Аналітичне задання функції – опис її формулою. Наприклад, f₁(x₁, x₂, x₃) = x₁x₂ + x₂( + x₁); f₂(a, b, c) = abc + b .

Табличний спосіб задання

			Таблиця 1
x2	x1	x0	f(x2, x1, x0)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

Будь-яке ціле невід’ємне число можна записати у вигляді суми

N = g₁r^{n– 1} + g₂r^{n– 2} + … + g_{n – 1}r¹ + g­_nr⁰,

де r – основна система числення, g – співмножник, що набуває значень від 0 до r – 1. Кількість доданків визначається розрядністю чисел.

Кортеж значень аргументів можна розглядати як запис цілого числа у двійковій системі числення (r = 2); тоді x₀ – розряд одиниць, x₁ – розряд двійок, x₂ – розряд четвірок. Наприклад, шостим набором у таблиці є 1  2² + 0  2 + 1  2⁰. Перший набір називається нульовим, а останній – одиничним.