Поняття булевої функції. Способи задання

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

Означення 5.4.1. Булевою називають функцію, область визначення і множина значень якої належать заданій двоелементній множині.

Зафіксуємо цю двоелементну множину як {0,1}. Тоді п-місна булева функція (від п аргументів) є відображенням {0,1}^п на {0,1}.

Булеву функцію f(x₁, x₂, …, x_n) можна задати різними способами:

Спосіб 1: за допомогою таблиці істинності, за якою визначають, яке значення f відповідає кожній окремій п-ці (набору) значень аргументів x₁, x₂, …, x_n.

Оскільки кількість всіх наборів x₁, x₂, …, x_n становить 2^п, то кількість всіх булевих функцій дорівнює кількості розміщень з повтореннями з 2 елементів по 2^п:

.

Отже, для п=1 існує 4 одномісних булевих функцій.

Таблиця 5.1

Для п=2 існує 16 двомісних булевих функцій.

Таблиця 2

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

Спосіб 2: за допомогою формули, в якій задають логічні операції над аргументами x₁, x₂, …, x_n .

Наприклад, у таблиці 1: f₁ і f₄ – константи, f₂(х₁)=х₁, f₂(х₁)= .

У таблиці 2: f₁ (х₁,х₂) і f₁₆(х₁,х₂) – константи;

– кон’юнкція;

– антиімплікація;

;

– обернена антиімплікація;

;

– строга диз’юнкція (антиеквіваленція)

– диз’юнкція;

– антидиз’юнкція або стрілка Пірса;

– еквіваленція;

– заперечення х₂;

– обернена імплікація;

– заперечення х₁;

– імплікація;

– антикон’юнкція або штрих Шеффера.

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

Тема 5.5. ЛОГІКА ПРЕДИКАТІВ