Например, тождественно ложна формула:

      

     Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно,

     Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А В - тавтология, и обратно, если формула - тавтология, то формулы А и В равносильны.

  Важнейшие равносильности алгебры логики можно разбить на три группы.

1. Основные равносильности:

1.   законы  идемпотентности
7.   закон противоречия
8.    закон исключённого  третьего
9.          закон снятия двойного отрицания.
10.  законы   поглощения

2. Равносильности, выражающие одни   логические  операции через другие:

 

3.Равносильности, выражающие основные законы алгебры  логики:

1.   коммутативность конъюнкции
2.     коммутативность дизъюнкции
3. ассоциативность конъюнкции
4.    ассоциативность дизъюнкции
5. дистрибутивность конъюнкции относительно дизъюнкции.
6. дистрибутивность дизъюнкции относительно конъюнкции

РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ

 

     Используя равносильности I, H и III групп можно часть формулы или формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными.

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

     Формула А считается проще равносильной ей формулы В, если она содержит меньше букв, меньше логических операций. При этом обычно операции эквивалентность и импликация заменяются операциями дизъюнкции и конъюнкции, а отрицание относят к элементарным высказываниям. Рассмотрим пример.

1. Доказать равносильность:   Используя равносильности I, II и III групп запишем цепочку равносильных формул:

 

          

АЛГЕБРА БУЛЯ

 

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

     Эта особенность позволяет прийти и к далеко идущим обобщениям. Рассмотрим непустое множество М элементов любой природы     {x,y,z,...}, в котором определены отношение

«=» (равно) и три операции: «+» (сложение), «.» (умножение) и «-» (отрицание), подчиняющиеся следующим аксиомам:

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

     Ассоциативные законы:   х + (у + z) = (х + у) + z       и   

     Дистрибутивные  законы:    и   

     Законы идемпотентности: х + х = х                             и     х • х = х

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

     Законы  де-Моргана:                                    и   

     Законы  поглощения:                                 и  

     Такое множество М называется булевой алгеброй.

     Если  под основными элементами х, у, z, ... подразумевать высказывания, под операциями «+», «•», «-» дизъюнкцию, конъюнкцию, отрицание соответственно, а знак равенства рассматривать как знак равносильности, то, как следует из равносильностей I, II и III групп, все аксиомы булевой алгебры выполняются.

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

     Значит, алгебра логики является интерпретацией булевой алгебры. Алгебра Буля имеет и другие интерпретации. Например, если под основными элементами х, у, z, ,.. множества М подразумевать множества, под операциями «+», « • », «-» объединение, пересечение, дополнение соответственно, а под знаком равенства - знак равенства множеств, то мы приходим к алгебре множеств. Нетрудно убедиться, что в алгебре множеств все аксиомы алгебры Буля выполняются.

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

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

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

Например, формула:      является функцией  трех переменных   .

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

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

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

     В частности, различных функций одной  переменной четыре, а различных функций  двух переменных шестнадцать. Выпишем все функции алгебры логики одной и двух переменных.

Таблица истинности для всевозможных функций  двух переменных имеет вид:

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

 -единичная функция    -сложение  по  модулю 2

-дизъюнкция    -отрицание 

-импликация    функция сохранения второй переменной

- импликация    -стрелка Пирса

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

-функция  сохранения первой   

 переменной    

-эквивалентность   - конъюнкция

-отрицание     - нулевая функция

ФОРМЫ ПРЕДСТАВЛЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ

 

     Для удобства представления логических функций существуют различные формы:

•    дизъюнктивная нормальная форма

•    конъюнктивная нормальная форма.

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

Например, формы_  - дизъюнктивная нормальная форма, a   - нет.

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

Например, формы ( a +b)c, ab(c +b), , а- конъюнктивные нормальные формы.

       Теорема о ДНФ  Всякая сложная логическая функция может быть сведена к ДНФ.

Для того чтобы сделать это, необходимо:

•    записать булеву функцию в виде {+, •, -};

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

•    с помощью первого закона дистрибутивности уничтожить все произведения сумм и провести поглошение.

Полученная  форма удовлетворяет определению ДНФ.

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