Булевы функции и их форма

     5)

     6)

     7)

     8)

     9)

     10)  

     VII. Равносильны ли следующие формулы 

     1)      

     2)      

     3)    

     4)    

     5)   

     6)        

     7)  

     8)     

     9)      

     10)     

     Контрольные вопросы 

     

1. Булевы  функции. Таблицы истинности.
2. Число булевых функций от переменных.
3. Элементарные булевы функции.
4. Формулы алгебры логики. Классификация формул.
5. Равносильные формулы. Законы равносильости.
6. Логические уравнения.

 

     Лабораторная  работа №2. Нормальные формы булевых функций 

     Введем  обозначение 

       

     Формула , где , , а среди переменных могут быть совпадающие, называется элементарной конъюнкцией.

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

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

     Правильная  элементарная конъюнкция называется полной относительно переменных , если в нее каждая из этих переменных входит один и только один раз.

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

     Всякую  булеву функцию  , не равную тождественно нулю, можно представить совершенной дизъюнктивной нормальной формой: 

       (1)

 

     Пример 1. Найти ДНФ для формулы  

      . 

       

     Пример 2. Найти СДНФ для формулы .

     1 способ (табличный). Данный способ  основан на разложении (1). Суть  его состоит в следующем:

     1. составляется таблица истинности  для данной формулы;

     2. в таблице истинности выделяются  наборы  , для которых значение формулы истинно;

     3. для каждого такого набора  составляются элементарные конъюнкции;

     4. составляем дизъюнкции построенных  элементарных конъюнкций. 

 

     

       

 

     2 способ (аналитический). 

     

      . 

     Формула вида называется элементарной дизъюнкцией.

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

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

     Правильная  элементарная конъюнкция называется полной относительно переменных , если каждая из этих переменных входит в нее один и только один раз (быть может под знаком отрицания).

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

     Всякую  функцию  отличную от тождественно истинной, можно представить совершенной конъюнктивной нормальной формой: 

       (2)

 

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

     Пример 3. Найти КНФ для формулы  

      . 

     

      . 

     Пример 4. Найти СКНФ для формулы  

      . 

     1 способ (табличный). Данный способ  основан на разложении (2). Суть  его состоит в следующем:

     1. составляется таблица истинности  для данной формулы;

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

     3. для каждого такого набора  составляются элементарная дизъюнкция  

      ;

 

     4. составляем конъюнкцию элементарных  дизъюнкций. 

 

      . 

     2 способ (аналитический). 

     

     

      . 

     Полиномом Жигалкина называется полином вида 

       

 

     причем  в каждом наборе все различны, а суммирование ведется по некоторому множеству таких не совпадающих наборов, - константа 0 или 1.

     Справедливы следующие равносильности: 

     21.

     22.

     23.

     24.

     25.  

     Каждая  булева функция может быть единственным образом выражена при помощи полинома Жегалкина.

     Пример 5. Выразить формулу в виде полинома Жегалкина.

     1 способ (метод неопределенных коэффициентов). 

       

     При  имеем: ;

     При  имеем: ;

     При  имеем: ;

     При  имеем:  

      , т.е.  . 

     Отсюда  

 

      . 

     2 способ.  

      . 

     Приведем  полиномы Жегалкина элементарных булевых  функций 

     

     

     

     

       

     Задания к лабораторной работе №2 

     I. Найти ДНФ для формулы

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     II. Найти СДНФ для формулы 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)