|
Равносильные преобразования формул
Используя равносильности 1, 2 и 3 групп можно часть формулы или формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными.
Равносильные преобразования используются для доказательства равносильностей, для приведения формул к заданному виду, для упрощения формул.
Формула А считается проще равносильной ей формулы В, если она содержит меньше букв, меньше логических операций. При этом обычно операции эквивалентность и импликация заменяются операциями дизъюнкции и конъюнкции, а отрицание относят к элементарным высказываниям. Рассмотрим ряд примеров.
- Доказать равносильность х у & х&у.
Используя равносильности 1, 2 и 3 групп запишем цепочку равносильных формул:
х у (х у)&(у х) ( у)&( х) & &х у& у&х &
& 0 0 у&х & у&х & х&у.
- Упростить формулу ( х у)&у.
Запишем цепочку равносильных формул:
( х у)&у (х у х у)&у (х у)&у у.
§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 Все материалы защищены законодательством РФ.
|