Свойства конъюнкции, дизъюнкции и отрицания. (указываются достоинства, недостатки отчета, вопросы)

(указываются достоинства, недостатки отчета, вопросы)

 

 

 

Результат рецензирования ___________________________

(отчет допущен к защите; не допущен к защите)

 

Подпись рецензента __________________________________

 

«____» _________________________ 2012 г.

 

Отметка о прохождении практики _____________________

 

 

Отметка о защите отчета ______________________________

 

 

«____» _______________________ 2012 г.

 

(подписи преподавателей, принимающих зачет)

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

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

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