Существенные и несущественные переменные .

Булева функция y=f(x₁,x₂,…,x_n) существенно зависит от переменной x_k, если существует такой набор значений a ₁, a ₂,…, a _k-1, a _k+1, a _k+2,…, a_n, что

f(a₁,a₂,…,a_k-1, 0, a_k+1,a_k+2,…,a_n) ≠

                                         ≠ f(a₁,a₂,…,a_k-1, 1, a_k+1,a_k+2,…,a_n).

В этом случае x_k называют существенной переменной, в противном случае x_k называют несущественной (фиктивной) переменной. Другими словами, переменная является несущественной, если ее изменение не изменяет значения функции.

 

  Пример 1.4.1. Пусть булевы функции f₁(x₁,x₂) и f₂(x₁,x₂) заданы следующей таблицей истинности:

x1	x2	f1(x1,x2)	f2(x1,x2)
0	0	0	1
0	1	0	1
1	0	1	0
1	1	1	0

 

Для этих функций переменная x₁ — существенная, а переменная x₂—несущественная.

Очевидно, что булевы функции не изменяют свои значения путем введения (или удаления) несущественных переменных. Поэтому, в дальнейшем булевы функции рассматриваются с точностью до несущественных переменных (в примере можно записать: f₁(x₁,x₂)=x₁, f₂(x₁,x₂)=x₁).

                         

     §1.5. Таблицы истинности. Эквивалентные функции.

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

    Пример 1.5.1. F1=x₁˄x₂˅(x₁˄x₂˅x₁˄x₂ )

 

x1	x2	x1˄x2	x1˄x2	x1˄x2˅x1˄x2	x1˄x2	F1
0	0	0	0	0	0	0
0	1	0	1	1	0	1
1	0	1	0	1	0	1
1	1	0	0	0	1	1

 

Таким образом, формула F1 реализует дизъюнкцию.

 

Пример 1.5.2. F2=x₁˄x₂→x₁

Таким образом, формула F2 реализует константу 1.

x1	x2	x1˄x2	F2=x1˄x2→x1
0	0	0	1
0	1	0	1
1	0	0	1
1	1	0	1

 

Пример 1.5.3. F3=((x₁˄x₂)⊕x₁)⊕x₂.

x1	x2	x1˄x2	(x1˄x2)⊕x1	F3=((x1˄x2)⊕x1)⊕x2
0	0	0	0	0
0	1	0	0	1
1	0	0	1	1
1	1	1	0	1

 

Таким образом, формула F3 реализует дизъюнкцию.

 

Булевы функции f₁ и f₂ называются эквивалентными, если на всяком наборе (a ₁, a ₂,…, a_n) нулей и единиц значения функций совпадают. Обозначение эквивалентных функций следующее: f₁=f₂.

Согласно приведенным примерам 1-3, можно написать

• x₁˄x₂˅(x₁˄x₂˅x₁˄x₂ ) = x₁˄x₂;

• x₁˄x₂→x₁ =1;

• ((x₁˄x₂)⊕x₁)⊕x₂=x₁˅x₂.

 

    §1.6. Аксиоматика и основные законы алгебры логики.

Прежде всего остановимся на рассмотрении аксиом булевой алгебры.

 

   1. Аксиомы, утверждающие, что в булевой алгебре рассматриваются только двоичные переменные:

   х=0, если х 1;

   х=1, если х 0.

   2. Аксиомы, определяющие логические операции И и ИЛИ:

   0 ; 0 ;     1

   1+1=1;   1+0=0+1=1; 0+0=0.

 

   3. Аксиомы, определяющие операцию логического отрицания:

    

       

   4. Аксиома симметричности:

   если , то

 

    5. Аксиома транзитивности:

  если  и , то

 

  6. Аксиома рефлексивности:

  х= х.

 

    Аксиомы 4, 5, 6 формулируют свойства отношения эквивалентности. Из этих свойств следует принцип подстановки: если , то в любом логическом выражении, содержащем , вместо  можно подставить  и в результате будет получено эквивалентное логическое выражение.

 

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

    Основные законы алгебры логики принято разбивать на три группы.

 

  1. Законы одинарных элементов.

  а) Законы универсального множества:

   

  б) Законы нулевого множества:

   

      

  2. Законы отрицания.

  а) Закон двойного отрицания:

 

  б) Законы дополнительности:

    

  в)Законы двойственности (де-Моргана):

   .

 

  3. Комбинационные законы.

  а) Законы тавтологии (идемпотентности):

   

Отсюда следует, что булева алгебра является алгеброй без степенией и коэффициэнтов.

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

  ;    

 

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

  ;

 

 

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

  Распределительный закон первого рода (умножение относительно сложения):

 

  Распределительный закон второго рода (сложение относительно умножения):

 

 

  Для проверки истинности приведенных эквивалентностей достаточно построить соответствующие таблицы истинности.

 

  Отметим, что в обычной алгебре не действуют законы тавтологии и распределительный закон второго рода.