Алгебра Буля

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

     - \(( x \wedge y) \vee z \equiv ( x \vee z) \wedge ( y \vee z )\),

     - \(x \wedge ( y \vee x) \equiv x\),

     -\(x \vee ( y\wedge x) \equiv x\),

     - \(\overline{ x \wedge y} \equiv \bar{x} \vee \bar{y}\),

     - \(\overline {x \vee y } \equiv \bar{x} \wedge \bar{y}\) и т.д.
    Эта особенность позволяет прийти и к далеко идущим обобщениям.
   Рассмотрим не пустое множество \(M\) элементов любой природы \(\begin{Bmatrix} x, y, z, ... \end{Bmatrix}\), в котором определены отношение "=" (равно) и три операции: "+" (сложение), "\(\cdot\) " (умножение) и "-" (отрицание), подчиняющиеся следующим аксиомам:

Коммутативные законы:

    1а. \(x + y = y + x\),
    1б. \(x \cdot y = y \cdot x\).
Ассоциативные законы:

    2а. \(x + ( y+ z) = ( x+ y ) + z\),
    2б. \(x \cdot ( y \cdot z) = ( x \cdot y ) \cdot z\).
Дистрибутивные законы законы:

    3а. \(( x + y) \cdot z = ( x \cdot z ) + ( y \cdot z)\),
    3б. \(( x \cdot y) + z = ( x + z ) \cdot ( y + z)\).
Законы идемпотентности:

    4а. \(x + x = x\),
    4б. \(x \cdot x = x\).
Закон двойного отрицания:

    5. \(\bar{\bar{x}} = x\).
Законы де-Моргана:

    6а. \(\overline {x + y } = \bar{x} \cdot \bar{y}\),
    6б. \(\overline{x \cdot y} = \bar{x} + \bar{y}\).
Законы поглощения:

    7а. \(x + ( y \cdot x ) = x\),
    7б. \(x \cdot ( y + x ) = x\).
    Такое множество \(M\) называется булевой алгеброй.
    Если под основными элементами \(x, y, z, ...\) подразумевать высказывания, под операциями "+", "\(\cdot\)", "-" дизъюнкцию, конъюнкцию, отрицание соответственно, а знак равенства рассматривать как знак равносильности, то, как следует из равносильностей I, II, III групп, все аксиомы булевой алгебры выполняются.
    В тех случаях, когда для некоторой системы аксиом удается подобрать конкретные объекты и конкретные соотношения между ними так, что все аксиомы выполняются, говорят, что найдена интерпретация (или модель) данной системы аксиом.
    Значит, алгебра логики является интерпретацией булевой алгебры. Алгебра Буля имеет и другие интерпретации. Например, если под основными элементами \(x, y, z, ...\) множества \(M\) подразумевать множества, под операциями "+", "\(\cdot\)", "-" объединение, пересечение, дополнение соответственно, а под знаком равенства - знак равенства множеств, то мы приходим к алгебре множеств. В алгебре множеств все аксиомы алгебры Буля выполняются.


2012-11-03 • Просмотров [ 2918 ]