yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->1.3 Основные аксиомы и теоремы булевой алгебры:

Математическая логика

1.3 Основные аксиомы и теоремы булевой алгебры:

Пользуясь аксиомами (1-4). и определениями основных булевых функций можно вывести ряд предложений, являющихся теоремами булевой алгебры. Приведем полностью список аксиом и основных теорем булевой алгебры.

 

(1.1) a v b=b v a       ab=ba             коммутативные законы

(1.2) a v (bc) = (a v b)(a v c);           a(b v c)=(ab) v (ac) дистрибутивные законы.

(1.3)a v 0=a;        a1=a

(1.4) а v ¬ а=1 закон исключенного третьего

         а¬а=0 закон противоречия

(1.5) а v (Ь v с)=(а v Ь) v  с;    ас)=(аЬ) с   ассоциативные законы

(1.6) если для всех  а,   а v b = а, то b=0 если для всех а  .аЬ = а, то Ь=1

(1.7) если       аvЬ=1 и аЬ=0, то b=¬ а

(1.8)¬¬a=a

(1.9) ¬0=1                            ¬1=0

(1.10) а v 1=а,                      aa=a  законы равностепенности или идемпотентности

(1.11) а v 1=1                       a0=0

(1.12) а v (аЬ)=а              a(a v b)=a законы поглощения

(1.13)¬(a v b)=¬a¬b,    ¬(ab)=¬a v ¬b Законы де Моргана  

1.4. Булевы формулы

Булевы    функции    могут    быть    представлены    с    помощью    таблиц истинности иди в виде формулы.

 Определение 1.6.

*     Каждая переменная есть формула.

*     Если х, у - формулы, то формулами являются (¬x), (x v y), (х&у).

*     Других формул нет.

В изображении формул приняты следующие допущения: внешние скобки опускают; наивысшим приоритетом обладает операция отрицания, затем конъюнкция, затем дизъюнкция. С учетом этих приоритетов избыточные скобки также опускаются. Часто не изображается символ конъюнкции (& или л). В изображениях формул допускается использование логических связок импликации (-») и эквивалентности (а).

Для каждой булевой формулы можно построить таблицу истинности, вычисляя ее значения на каждом наборе. Например, мы можем проверить справедливость основных теорем (1.1) - (1.13) с помощью таблиц истинности. Покажем,' что формулы ау(Ь & с) и (а v Ь)&(а v с) равносильны. Построим их таблицы истинности (табл. 1.3)

 

 

 

 

 

 

 

 

 

 

Таблица 1.3

а

 

Ь

 

с

 

Ь & с

 

   a v(b&c)

 

a v b

 

a v c

 

(аvЬ)&' (avс)

 

0

 

0

 

0

 

0

 

0

 

0

 

0

 

0

 

0

 

0

 

1

 

0

 

0

 

0

 

1

 

0

 

0

 

1

 

0

 

0

 

0

 

1

 

0

 

0

 

0

 

1

 

1

 

1

 

1

 

1

 

1

 

1

 

1

 

0

 

0

 

0

 

1

 

1    ,.

 

1

 

1

 

1

 

0

 

1

 

0

 

1

 

1   

 

1

 

1

 

1

 

1

 

0

 

0

 

1

 

1

 

1

 

1

 

1

 

1

 

1

 

1

 

1

 

1

 

1

 

1

 

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

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

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

Ил определения следует, что тавтологии являются выполненными формулами, так как это такие формула, которые На каждом наборе равны единице.

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

 

8