Сделай Сам Свою Работу на 5

Равносильные преобразования формул





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

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

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

  1. Доказать равносильность х у & х&у.

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

х у у)&(у х) ( у)&( х) & у& у&х &

& 0 0 у&х & у&х & х&у.

  1. Упростить формулу ( х у)&у.

Запишем цепочку равносильных формул:

 

( х у)&у у х у)&у у)&у у.

§6. Алгебра Буля

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



Но в алгебре логики возможны и другие преобразования, основанные на использовании равносильностей:

(х&у) z (х z)&(у z),

х&(у х) х,

х (у&х) х,

,

& и т. д.

Рассмотрим непустое множество М элементов любой природы {х, у, z, …},в котором определены отношение «=» (равно) и три операции: «+» (сложение), «*» (умножение) и «-» (отрицание), подчиняющиеся следующим аксиомам:

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

1а. (х&у)(y&x), 1b. (х )(y &x)

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

2а. х+(у+z) = (х+у)+z,2б. х*(у*z) =(х*у)*z.

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

3а. (х+у)*z =(х*у)+(у*z), 3б. (х*у)+z =(х+z)*(у+z).

Законы идемпотентности:

4а. х+х = х, 4б. х*х = х.

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

5. = х.

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

6а. = * , 6б. = + .

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

7а. х+(у*х) = х, 7б. х*(у+х) = х.

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



Если под основными элементами х, у, z, …подразумевать высказывания, под операциями «+», «*», «-» дизъюнкцию, конъюнкцию, отрицание соответственно, а знак равенства рассматривать как знак равносильности, то, как следует из равносильностей 1, 2 и 3 групп, все аксиомы булевой алгебры выполняются.

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

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

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

Функции алгебры логики

 

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

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

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



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

Рассмотрим таблицу истинности для различных функций одной переменной. Она, очевидно, имеет вид:

x f1(x) f2(x) f3(x) f4(x)

Из этой таблицы следует, что две функции одной переменной будут постоянными: f1(x) 1, f2(x) 0, a f2(x) x, и f3(x)

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

 

 

fi fi(x, y)

x y f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16

 

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

f1 1, f5 , f9 , f13 ,

f2 x y, f6 x, f10 , f14 ,

f3 y x, f7 x y, f11 y, f15 x&y,

f4 x y, f8 , f12 , f16 0.

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.