Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. IV. Предварительные данные о радиоактивных свойствах атомного взрыва
  2. VI. Влияние нагрева на структуру и свойства деформированного металла.
  3. VII. Механические свойства металлов
  4. XIII.Стали и сплавы с особыми физическими свойствами
  5. XXIII. Физические процессы в магнитных материалах и их свойства
  6. Алгебраические свойства операций над множествами
  7. Базисные свойства

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

Конъюнкцией n переменных f (x 1, x 2,…, xn) = x 1 x 2 …xn называется функция, которая принимает значение1, если и только если все переменные равны1(и, значит, равна 0, если хотя бы одна из этих переменных равна 0).

Дизъюнкцией n переменных f (x 1, x 2, , xn) = x x … Ú xn называется такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).

Из этих определений видно, что конъюнкция и дизъюнкция коммутативны, т. е. обе функции не зависят от порядка переменных.

Будем обозначать через (x 1, x 2, , xn)новую функцию, которая на наборе переменных x 1, x 2, …, xn принимает значение, противоположное f (x 1, x 2, …, xn).

Заметим, что в перечисленных далее свойствах в роли x, y, z может выступать любая логическая функция. Все свойства легко могут быть доказаны из приведенных выше определений этих функций.

1. Универсальные границы:

xÚ1 = 1; xÚ0 = х; х 1 = х; х 0 = 0.

2. Ассоциативность конъюнкции и дизъюнкции:

x (yz) = (xy) z; x Ú(y Ú z) = (x Ú yz.

Это свойство означает, что в конъюнкции или дизъюнкции нескольких переменных можно как угодно расставлять скобки (а значит, можно вообще их не ставить).

3. Поглощение (“целое поглощает часть”):

х Ú ху = х (1Ú у) = х.

4. Два распределительных закона:

х (y Ú z) = x y Ú x z; х Ú(y z) = (x Ú y)(x Ú z),

оба свойства могут быть доказаны простым рассуждением (например, если х = 0, тогда по свойству 1 справа выражение равно 0 и слева тоже 0, если х = 1, то справа стоит y Ú z и слева будет то же самое).

5. Правила де Моргана:

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

6. Правило Блейка:

Пусть К 1 и К 2 – какие-то логические функции, тогда

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

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

Заметим, что правила Блейка и следствия из него часто используются для упрощения дизъюнкции (см. разд. 5)

Замечание. Конъюнкция, дизъюнкция, отрицание были определены для объектов, принимающих лишь два значения 0 и 1. Однако бывают случаи, когда можно ввести такие операции для некоторых других объектов (эти операции также называют иногда конъюнкцией, дизъюнкцией и отрицанием), для которых также выполнены свойства 1–6. В этом случае говорят, что на этих объектах введена булева алгебра.

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


Дата добавления: 2015-10-21; просмотров: 87 | Нарушение авторских прав


Читайте в этой же книге: РИО СПбГУТ. 191186, СПб, наб. р. Мойки, 61 | ЛОГИЧЕСКИЕ (БУЛЕВЫ) ФУНКЦИИ | Представление логических функций в виде СДНФ (СКНФ) | Нахождение сокращенной ДНФ по таблице истинности (карты Карно) | Полиномы Жегалкина | Суперпозиция функций. Замыкание набора функций.Замкнутые классы функций. Полные наборы. Базисы | Функциональные элементы и схемы | Общие понятия теории графов | Эйлеровы и полуэйлеровы графы | Матрицы и графы. Нахождение путей и сечений с помощью структурной матрицы |
<== предыдущая страница | следующая страница ==>
Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных).| ДНФ, СДНФ, КНФ, СКНФ

mybiblioteka.su - 2015-2024 год. (0.006 сек.)