Булева алгебра

Булевата алгебра (или алгебрата на съжденията) е клон от алгебрата. За разлика от училищната алгебра тук променливите могат да имат две стойности, наричани „ЛЪЖА“ и „ИСТИНА“, записвани също като „0“ и „1“. Друга основна разлика от обичайната алгебра е, че вместо аритметични действия се използват бинарните логическите оператори „И“, „ИЛИ“ и унарната операция „НЕ“. Работата с логическите операции има пряка връзка с операциите над множества сечение, обединение и допълнение.

Тя е формулирана за първи път от британския математик Джордж Бул (1815 – 1864) през 19 век, с цел да се използват алгебрични методи в логиката. Булевата алгебра и булевите операции стоят в основата на информатиката, програмирането и функционирането на компютърните системи, които работят чрез споменатите логически операции.

Операторите се срещат често написани по различен начин, напр. И, ИЛИ, НЕ (англ. AND, OR, NOT); ∧, ∨, ¬; математиците често използват + за ИЛИ, · за И и черта над символа за НЕ.

Тук са използвани логическите символи ∧, ∨ и ¬.

Дефиниция

Булева алгебра е множество S с дефинирани функции Λ (конюнкция И), V (дизюнкция ИЛИ) и ¬ (отрицание НЕ)

Булева алгебра с два елемента X1 X2

Теорията се базира на действия над „съждения“, които се интерпретират само или като верни, или като неверни.

Съждението:

„2 по 2 е равно на четири" е истинно. В булевата алгебра се отбелязва, че верността му е 1.

Съждението:

„Желязото е карбонат“ е лъжовно. В булевата алгебра се отбелязва, че верността му е 0.

При съставянето на сложни съждения се използват логическите операции „и“ (конюнкция), „или“ (дизюнкция), „не“ (отрицание), „следва“ (импликация).

Най-висок приоритет има отрицанието, следвано от конюнкцията и дизюнкцията.

Изразите в тази алгебра се наричат булеви изрази.

Операциите сe дефинират, както следва:

Логическа операция Оператор Записване Алтернативно записване Определение Конюнкция И x ∧ y x AND y x ∧ y = 1 ако x = y = 1, иначе x ∧ y = 0 Дизюнкция ИЛИ x ∨ y x OR y x ∨ y = 0 ako x = y = 0, иначе x ∨ y = 1 Отрицание НЕ ¬x NOT x, Nx, x̅ ¬x = 0 ако x = 1, ¬x = 1 ако x = 0

Често логическите операции се дефинират чрез табулирането на техните стойности:

$x$ $y$ $x\wedge y$ $x\vee y$ 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

$x$ $\neg x$ 0 1 1 0

Тази алгебра намира приложение в логиката, където 0 се интерпретира като „невярно“, а 1 като „вярно“. Изрази в тази алгебра се наричат булеви изрази.

Аксиоми

1. ${\bar {\bar {x}}}=x$: Инволюция на отрицанието, отрицанието е операция, обратна на самата себе си.
2. $x\lor {\bar {x}}=1$
3. $\ x\lor 1=1$
4. $\ x\lor x=x$
5. $\ x\lor 0=x$
6. $\ x\land {\bar {x}}=0$
7. $\ x\land x=x$
8. $\ x\land 0=0$
9. $\ x\land 1=x$

Вижте също

• Побитова операция