Булева алгебра (алгебра логіки). Повні системи булевих функцій

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

Булевою алгеброю або алгеброю логіки називається двохелементну множину B = {0, 1} разом з операціями кон’юнкції, диз'юнкції й заперечення.

Система булевих функцій {f₁, f₂, … , f_n} називається повної, якщо будь-яка булева функція може бути виражена у вигляді суперпозиції цих функцій. З правил 12 – 16 (розділ 4.3) потрібно, що всі логічні операції можуть бути виражені через операції кон’юнкції, диз'юнкції й заперечення. Тому система функцій {Ø, &, V} є повною. Також повними є наступні системи функцій:

а) {Ø, V}; б) {Ø, &}; в) {Ø, É}.

Повнота систем {Ø, V} и {Ø, &}потрібно з повноти системи {Ø, &, V}, а також законів де Моргана й подвійного заперечення, наслідком яких є можливість виразити кон’юнкцію через диз'юнкцію й навпаки: A&B ºØ(ØAVØB); AVB º Ø(ØA&ØB). Тому система {Ø, &, V} може бути скорочена на одну функцію:

Повнота системи {Ø, É} потрібно з повноти системи {Ø, V} і Рівносильністи 12 (розділ 4.3), що дозволяє виразити імплікацію через заперечення й диз'юнкцію:

AÉB ºØAVB.