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

Особая роль двух функций (из этих трех) определяется тем обстоятельством, что определение этих функций легко может быть перенесено на любое число переменных:

Конъюнкцией 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. В этом случае говорят, что на этих объектах введена булева алгебра.

Например, пусть W – некоторое множество точек (или элементарных событий в теории вероятности), Â – множество подмножеств из W . Если A, B принадлежат Â , то можно ввести сумму множеств (дизъюнкцию) A+B = AÚ B (равную объединению точек из А и В), произведение множеств (конъюнкцию) АВ = АÙ В (равное набору точек, входящих и в А, и в B одновременно) и дополнение (отрицание А), т. е. – множество точек из W , не входящих в А. Тогда для этих операций (и это легко проверить) будут выполнены свойства 1–6. Таким образом, множество всех подмножеств из W является булевой алгеброй.