Вопрос 41: Равносильности логики высказываний и преобразование логических выражений.

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

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

Используя это понятие, можно установить связь между логическими операциями.

x→y

______

Любую формулу можно выразить через or,not,and.

Наиболее часто используются следующие равносильности: законы Моргана:

_____ _ _

1. (a v b)  (a ^ b)

_____ _ _

(a ^ b)  (a v b)

2. Закон снятия двойного отрицания

=

a=a

3. Коммутативные законы

(a^b)(b^a)

(avb)(bva)

4. Ассоциативные законы

((a^b)^c))(a^(b^c)

((a v b)v b)  (a v (b v c))

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

(av(b^c))((avb)^(avc))

(a^(b v c))  ((a^b) v (a^c))

6. x v x  x

x^xx

Так же полезны следующие равносильности:

_

a v a  1

_

a ^ a 

a v 1  1

a v   a

a ^   

a^ 1a

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

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

1. Выделяем все наборы переменных для которых функция принимает значение 1.

2. Каждому из этих наборов ставим соответствие конъюнкцию при этом если переменная равна 0 то в конъюнкцию она входит отрицанием.

3. Полученную конъюнкцию объединяются в общую формулу при помощи дизъюнкций.