Совершенные нормальные формы. Законы двойственности для сложения и умножения (законы де Моргана)

Законы двойственности для сложения и умножения (законы де Моргана).

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

а. Свойство ассоциативности (сочетательный закон):

Х₁+ (Х₂+ Х₃)= (Х₁+ Х₂) + Х₃

Х₁* (Х₂* Х₃)= (Х₁* Х₂) * Х₃

б. Свойство коммутативности (переместительный закон):

Х₁ + Х₂= Х₂ + Х₁

Х₁ * Х₂= Х₂ * Х₁

в. Свойство дистрибутивности (распределительный закон):

Х₁ + (Х₂ + Х₃)= Х₁ Х₂ + Х₁Х₃

Х₁ + x₂Х₃ = (Х₁ + Х₂)(Х₁+ Х₃)= Х₁Х₁+ Х₁Х₃+ Х₂Х₁+ Х₂Х₃= Х₁(1+Х₃+Х₂) + Х₂Х₃
=Х₁+ Х₂Х₃; т.к. 1+Х₃=1 и 1+Х₂=1, Х*Х =Х.

3.Законы поглощения_.

Х₁+ Х₁Х₂=Х₁(1+ Х₂)=Х₁, т.к. 1+ Х₂=1

Х1(Х1+ Х₂)= Х₁Х₁+ Х₁Х₁=Х₁+ Х₁Х₁=Х₁; т.к. Х₁Х₁=Х₁.

____

`A Ú`B = A Ù B

____

`A Ù`B = A Ú B

а. Проверка законов двойственности

Х1	Х2	______ Х1 Ù Х2	__ __ (Х1)Ú (Х2)	______ Х1+Х2	__ __ (Х1) * (Х2)

Пусть P и Q – некоторые высказывания. Тогда можно образовать сложные высказывания P или Q, P и Q, не P, введя операции дизъюнкции (ИЛИ), конъюнкции (И) и отрицания (НЕ).

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

В самом общем случае сколь угодно сложная логическая функция может быть представлена следующей формулой:

f(X₁,X₂,...,X_n),

где X₁,X₂,...,X_n- логические переменные, принимающие значения 0 или 1.

Логические переменные могут быть действительными и фиктивными. Переменная Х действительна, если значение функции, куда она входит, изменяется при изменении значения этой переменной. В противном случае она фиктивна.

Логические функции многих переменных могут задаваться таблично.

Рассмотрим табличное определение функции трёх переменных:

Х1	Х2	Х3	F(Х1, Х2, Х3)

Из таблицы видно, что переменные Х₁, Х₂ ‑ действительные, а переменная Х₃ - фиктивная, т.к. справедливо соотношение f(X₁,X₂, 0) = (X₁,X₂, 1), при любых комбинациях Х₁ и Х₂. Переменную X3 можно сократить из выражения булевой функции. Следовательно, для функций алгебры логики существует возможность сокращать (расширять) количество переменных устранением (введением) фиктивных.

Булевы функции могут задаваться аналитически, т.е. в виде формул. При этом сложные логические функции можно выражать через более простые логические функции. Минимальный набор простых логических функций, посредством которого может быть представлена любая ФАЛ, называется логическим базисом или полной системой. Базис минимален, если удаление хотя бы одной функции превращает систему ФАЛ в не полную. Примеры базисной системы функций: (И, НЕ); (ИЛИ, НЕ). На практике намного удобней использовать не минимальный базис И, ИЛИ, НЕ.

Любая таблично заданная логическая функция f (x1, x2,…. xn) может выражаться через набор конъюнктивных и дизъюнктивных термов или импликант:

f (x1, x2,…. xn) = F1 Ú F2 Ú … Ú Fn = Ф1 Ù Ф2 Ù … Ù Фm, где

Fi = x1`x2…xn – конъюнктивный терм - произведение переменных и их отрицаний; Фj = x1 Ú`x2 Ú…Ú`xn - дизъюнктивный терм - сумма переменных и их отрицаний. Если терм ФАЛ содержит полный набор переменных, связанных операцией конъюнкции, он носит название минтерм (конституента 1). Термы ФАЛ, состоящие из полного набора переменных, связанных операциями дизъюнкции, называются макстермами (конституенты 0).

Представление ФАЛ в аналитическом виде возможно в дизъюнктивной нормальной форме и в конъюнктивной нормальной форме.

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

Конъюнктивная нормальная форма (КНФ) – это произведение дизъюнкивных термов.

Дата добавления: 2014-01-06