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

     Лабораторная  работа №1. Булевы функции 

     Функцией  алгебры логики (булевой функцией) от переменных называется функция, принимающая значения 1,0 и аргументы которой также принимают значения 1,0.

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

 

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

        - константа 0;

        - константа 1;

        - тождественная функция;

        - отрицание  ;

        - конъюнкция  и ;

       - дизъюнкция  и ;

       - импликация  и ;

       - эквивалентность  и ;

        - сложение и по 2;

       - функция Шеффера;

       - функция Пирса. 

     Данные  функции задаются следующими таблицами  истинности 

 

     Приведем  определение формулы алгебры  логики:

1. каждая элементарная булева функция – формула;
2. если некоторое выражение есть формула, то тоже формула;
3. если некоторые выражения и есть формулы, то выражения

 

, , , , + , , тоже формулы; 

     

4. других  формул: кроме построенных по п.п.

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

     Две формулы  и называются равносильными, если они определяют одну и ту же булеву функцию (запись = будет означать, что формулы и равносильны).

     Приведем  перечень важнейших равносильностей (законов) алгебры логики. 

     1.   - закон тождества;

     2.   - закон противоречия;

     3.   - закон исключения третьего;

     4.   - закон двойного отрицания;

     5. ,  - законы идемпотентности;

     6. ,   

     - законы коммутативности; 

     7. ,  

     - законы дистрибутивности; 

       

     8. ,  

     - законы ассоциативности; 

     9. ,  - законы де Моргана;

       

     10. , ,

       , . 

     11. ,  

     - законы поглощения;

 

     12. ,   

     - законы склеивания.

     Отметим следующие важнейшие равносильности 

     13.

     14.

     15.

     16.

     17.

     18.

     19.  

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

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

     Формула алгебры логики называется выполнимой, если найдется такой набор значений переменных при котором ее значение истинно. 

     Пример 1. Является ли формула  

       тавтологией?

 

     1 способ (табличный)

 

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

     

     

       

     Пример 2. Является ли формула  

      ?  

     Метод от противного.

     Пусть  

      .  

     Тогда

 

       Отсюда 

       

     Из  последнего следует, что  . Тогда , , что невозможно.

     Пример 3. Равносильны ли формулы? 

      ;  

     

     

     

     

       

     Следовательно, формулы равносильны.

     Пример 4. Упростить 

       

 

     

       

     Пример 5. Решить уравнение  

       

     Это уравнение равносильно следующей  системе 

       

     Из  второго уравнения следует, что  , . Ясно, что тогда . Подставляя в третье уравнение . Следовательно, . Итак, , , - решение искомого уравнения. 

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

     I. Построить таблицы истинности  для формул 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

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

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     III. Без построения таблиц истинности  докажите, что следующие формулы  являются противоречием 

 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     IV. Решить уравнения 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)

 

     V. Какие из приведенных ниже  формул являются тавтологиями, противоречиями, выполнимыми 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     VI. Упростить  

     1)

     2)

     3)

     4)