Материал: 4553

31

вместо знака можно писать знак арифметического сложения: А+В. Этим знаком мы и будем пользоваться в дальнейшем.

Дизъюнкция, называемая иногда логическим сложением, определяется следующими аксиомами:

Конъюнкция обозначается знаком , но т.к. конъюнкция – «родня» арифметическому умножению, то вместо знака будем использовать точку, либо вообще не указывать никакого знака: А В = А·В = АВ.

Конъюнкция (логическое умножение) определяется следующими

Рассмотрим следующие основные свойства:

а) операции дизъюнкции и конъюнкции обладают свойством

коммутативности:

что позволяет удалять скобки во всех случаях, когда знаками дизъюнкции или

в) конъюнкция дистрибутивна относительно дизъюнкции: А(В + С) = АВ + АС,

32

что позволяет раскрывать скобки в выражениях и выносить общий множитель за скобки, например:

А(В + С + D + Е) = AB + AC + AD + AE,

АВС + ABD + ABEF = AB(C + D + EF);

г) дизъюнкция дистрибутивна относительно конъюнкции:

А + ВС = (А + В)(А + С); А + BCD = (A + B)(A + C)(A + D);

,

где последняя теорема отражает свойство инволюции.

Булевы формулы могут быть записаны в виде суммы либо в виде произведения каких-либо выражений. В первом случае говорят о

дизъюнктивной форме, во втором – о конъюнктивной. Например,

выражения

Представлены в дизъюнктивной форме, а выражения

– в конъюнктивной.

Если булева формула записана в виде суммы выражений, каждое из которых представляет собой либо отдельный аргумент (с отрицанием или без отрицания), либо произведение некоторых аргументов, то эта формула является представленной в дизъюнктивной нормальной форме (ДНФ). Например,

выражения

второе слагаемое не является ни отдельным аргументом, ни произведением переменных.

Если булева формула записана в виде произведения выражений, каждое из которых представляет собой либо отдельный аргумент (с отрицанием или без отрицания), либо сумму некоторых аргументов, то эта формула является представленной в конъюнктивной нормальной форме (КНФ). Например,

выражения

записаны в КНФ, а формула

КНФ не является, поскольку в первой паре скобок содержится произведение .

Выражение, представленное отдельным аргументом или его отрицанием либо суммой или произведением нескольких переменных, одновременно входит в класс ДНФ и КНФ. Например:

Теорема поглощения записывается в двух формах – дизъюнктивной и

Выражение второе можно получить из первого, если знаки сложения и умножения поменять местами.

Теорема склеивания также имеет две формы – дизъюнктивную и конъюнктивную:

;

Теорема поглощения, как и теорема склеивания, применяется при упрощении булевых формул, например:

;

;

.

34

Теорема де Моргана связывает все три основные операции булевой алгебры – дизъюнкцию, конъюнкцию и инверсию:

;

.

Первая теорема читается так: отрицание произведения есть сумма отрицаний. Вторая: отрицание суммы есть произведение отрицаний.

Теорема де Моргана применима и к большему числу переменных:

;

;

;

.

Булевы функции. Элементарные булевы функции

В общем случае функция – это некоторое правило (закон), согласно которому каждому элементу множества X, представляющего собой область значений независимого переменного x, ставится в соответствие определенный элемент множества F, под которым понимается область значений зависимого переменного f. В случае булевых функций . Правилом, при помощи которого задается функция, может служить любая булева формула, например:

полностью определяется значениями переменных и логическими связями между ними.

Булевы функции можно задавать таблицами. В таблице перечисляются все возможные наборы значений аргументов, и для каждого набора указывается значение функции. Такую таблицу называют таблицей соответствия

(истинности).

Приведем обозначения, названия и таблицы, определяющие так называемые элементарные булевы функции.

35

1)Функции 0 и 1 называются соответственно тождественным нулем

итождественной единицей.

2)Функция называется тождественной функцией и обозначается

через .

3)Функция называется отрицанием и обозначается .

Таблица 4.1

4)Функция называется конъюнкцией и , обозначается , или и часто читается «».

5)Функция называется дизъюнкцией и , обозначается

ичасто читается «».

6)Функция называется суммой по модулю 2 и ,обозначается

и часто читается « плюс » или «».

7)Функция называется эквивалентностью и , обозначается

«».

8)Функция называется импликацией и , обозначается →

и часто читается « имплицирует » или «».

9)Функция называется штрихом Шеффера и , обозначается

│ и часто читается « и » или «».

↓ и часто читается « или ».

Таблица 4.2