[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]

Нормальные формы алгебры логики

Определение 1
Элементарная конъюнкция (дизъюнкция) называется правильной, если в нее каждая переменная входит не более одного раза (включая ее вхождения со знаком отрицания).
Определение 2
Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).
Определение 3
Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ).

Алгоритм приведения к КНФ и ДНФ

  1. Использовать законы:
    XY=(XY)&(YX)
    XY=XvY
    чтобы устранить логические связки и

  2. Несколько раз использовать закон
    X=X
    и законы Де Моргана:
    (XvY)=X&Y
    (X&Y) = XvY
    чтобы перенести знак отрицания внутрь формул.

  3. Несколько раз использовать законы дистрибутивности:
    Xv(Y&Z)=(XvY)&(XvZ) - для построения КНФ
    X&(YvZ)=(X&Y)v(X&Z) - для построения ДНФ

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]