Логические (булевы) функции основные логические функции

2. Свойства конъюнкции, дизъюнкции и отрицания

Особая роль двух функций (из этих трех) определяется тем обстоятельством, что определение этих функций легко может быть перенесено на любое число переменных:
Конъюнкцией n переменных f (x₁, x₂, …, x_n) = x₁ x₂…x_n называется функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).
Дизъюнкцией n переменных f (x₁, x₂, …, x_n) = x_1Ú x_2Ú … Ú x_n называется такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).
Из этих определений видно, что конъюнкция и дизъюнкция коммутативны, т. е. обе функции не зависят от порядка переменных.
Будем обозначать через   (x₁, x₂, … , x_n) новую функцию, которая на наборе переменных x₁, x₂, …, x_n принимает значение, противоположное f(x₁, x₂, …, x_n).
Заметим, что в перечисленных далее свойствах в роли x, y, z может выступать любая логическая функция. Все свойства легко могут быть доказаны из приведенных выше определений этих функций.
1. Универсальные границы:
x1 = 1; x0 = х; х1 = х; х0 = 0.

2. Ассоциативность конъюнкции и дизъюнкции:
x(yz) = (xy)z; x (y z) = (x y) z.
Это свойство означает, что в конъюнкции или дизъюнкции нескольких переменных можно как угодно расставлять скобки (а значит, можно вообще их не ставить).
3. Поглощение (“целое поглощает часть”):
х ху = х(1 у) = х.
4. Два распределительных закона:
х (y z) = x y  x z; х (y z) = (x y)(x z),
оба свойства могут быть доказаны простым рассуждением (например, если х = 0, тогда по свойству 1 справа выражение равно 0 и слева тоже 0, если х = 1, то справа стоит y z и слева будет то же самое).
5. Правила де Моргана:

оба эти правила обобщаются на любое число переменных:

6. Правило Блейка:
Пусть К₁ и К₂ – какие-то логические функции, тогда

что легко доказывается справа налево:

Следствием правила Блейка являются два правила обобщенного поглощения:

Заметим, что правила Блейка и следствия из него часто используются для упрощения дизъюнкции (см. разд. 5)
Замечание. Конъюнкция, дизъюнкция, отрицание были определены для объектов, принимающих лишь два значения 0 и 1. Однако бывают случаи, когда можно ввести такие операции для некоторых других объектов (эти операции также называют иногда конъюнкцией, дизъюнкцией и отрицанием), для которых также выполнены свойства 1–6. В этом случае говорят, что на этих объектах введена булева алгебра.
Например, пусть – некоторое множество точек (или элементарных событий в теории вероятности),  – множество подмножеств из  . Если A, B принадлежат  , то можно ввести суммумножеств (дизъюнкцию) A+B = AB (равную объединению точек из А и В), произведение множеств (конъюнкцию) АВ = А В (равное набору точек, входящих и в А, и в B одновременно) и дополнение  (отрицание А), т. е.  – множество точек из  , не входящих в А. Тогда для этих операций (и это легко проверить) будут выполнены свойства 1–6. Таким образом, множество всех подмножеств из  является булевой алгеброй.