Функція, у|в,біля| якої аргументи пробігають множину|безліч| {0,1} і яка приймає значення з|із| тієї ж множини|безлічі| {0,1}, називається функцією алгебри логіки або булевою функцією.
Особливе значення мають так звані елементарні булеві функції. Двомісними елементарними булевими функціями є|з'являються,являються| кон'юнкція, диз'юнкція, імплікація, сума по модулю 2, эквіваленція|, штрих Шефера і стрільця Пірсу. Символи А1 і А2 з|із| табл. 2.2 слід в цьому випадку тлумачити як булеві змінні {0,1}.
Є|наявний| дві одномісні булеві функції, залежні від x: тотожна функція і заперечення . Це елементарні функції (табл. 2.3).
Таблиця 2.3
x
Є|наявний| дві нуль-місцеві елементарні булеві функції: це константи 0 і 1. Кожній пропозиціональній| формулі можна зіставити булеву| функцію. Булева функція, зіставлена пропозиціональній| формулі Н, називається функцією істинності формули Н.
Хай|нехай| – функція істинності (i =1, 2); хай|нехай| {} – безліч тих змінних, які зустрічаються хоч би в одній з функцій і . Пропозиціональні формули і називаються еквівалентними, якщо на всякому|усякому| наборі () значень змінних значення функцій і співпадають|збігаються| (еквівалентність позначають|значать| як: ).