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

Двоїстість. Принцип двоїстості.

Правило рівносильних перетворень

Нехай для формул A й B справедливе твердження A º B. Нехай C_A – формула, що містить A у якості своєї підформули. Нехай C_B виходить із C_A заміною A на B. Тоді C_A º C_B.

Приклад 4.5.

Нехай A = x É y, B = Ø x V y.

Рівносильність 12 дозволяє стверджувати, що A º B.

Нехай C_A = (x É y) & z, тобто A є підформула C_A. Тоді C_B = (Ø x V y) & z і C_A º C_B, тобто (x É y) & z º (Ø x V y) & z.

Символи &, V називаються двоїстими.

Формула А^* називається двоїстій формулі A, якщо вона отримана з A одночасною заміною всіх символів &, V на двоїсті.

Наприклад,

A = x V(y &Ø z);

A ^* = x & (y VØ z).

Теорема 4.1. (Принцип двоїстості).

Якщо A º B, то A ^* º B ^*.

Доведення принципу двоїстості можна знайти, наприклад, в [3].

Принцип двоїстості можна використати для знаходження нових правил. Наприклад, для 1-го закону поглинання (рівносильність 6а) маємо:

A &(A V B) º A.

Дотримуючись принципу двоїстості, одержимо нову рівносильність:

A V A & B º A (2- ий закон поглинання).

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

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

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

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

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

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

A É B ºØ A V B.

ЛІТЕРАТУРА

1. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцькиц Г.М., Печорін М.К. Основи дискретної математики. – К.: Наукова думка, 2002. – С.6-15.

2. Кужель О.В. Елементи теорії множин і математичної логіки. – К.: Рад. школа, 1977. – С. 4-24.

3. Новиков Ф.А. Дискретная математика для програмистов. – СПб.: Питер, 2002. – С.19-32.

4. Федосеева Л.И. Дискретная математика: Учеб.-практич. пособие. – Пенза: Изд-во Пенз. технол. ин-та, 1998. – С. 3-30.

Дата добавления: 2014-10-17