Равносильность булевых функций

⇐ ПредыдущаяСтр 8 из 8

Булевы функции f₁ и f₂ называются эквивалентными, если на всяком наборе ( ) нулей и единиц значения функций совпадают. Обозначение эквивалентных (равносильных) функций следующее: или .

Основные эквивалентности (Н, Н , Н , Н ... означают некоторые булевы функции):

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

2. Идемпотентность: ,

3. Коммутативность: , где символ означает одну из связок .

4. Ассоциативность: , где символ означает одну из связок .

5.Дистрибутивность: , .

6. Закон де Моргана: , ,

7. Правила поглощения: ,

8. Законы склеивания: , .

9. Законы инверсий: , .

10. Правила операций с константами: , , , .

Все проведенные соотношения легко проверяются по таблицам истинности.

Пример 5.4. Упростить формулы, используя основные законы эквивалентности:

1) ;

Пример 5.5. С помощью равносильных преобразований упростить формулу

Любую запись а) - д) можно считать ответом.

Пример 5.6. Проверьте, будут ли эквивалентны следующие функции:

С помощью равносильных преобразований получаем, что

т.е. функции эквивалентны.

Пример 5.7. Доказать равносильность

Задания для самостоятельного решения

5.2.1. Доказать следующие равносильности:

1. 8. 15.

2. 9. 16.

3. 10. 17.

4. 11. 18.

5. 12. 19.

6. 13. 20.

7. 14. 21.

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

5.2.3. Проверьте, будут ли эквивалентны следующие функции:

1. 11.

2. 12.

3. 13.

4. 14.

5. 15.

6. 16.

7. 17.

8. 18.

9. 19.

10. 20. .

5.2.4. Преобразуйте формулы, используя основные законы эквивалентности:

1. 11.

2. 12.

3. 13.

4. 14.

5. 15.

6. 16.

7. 17.

8. 18.

9. 19.

10. 20. .

5.2.5. Преобразовать следующие формулы так, чтобы знак отрицания был отнесен только к переменным:

1. 8. 15.

2. 9. 16.

3. 10. 17.

4. 11. 18.

5. 12. 19.

6. 13. 20.

7. 14. 21.

5.3. Преобразование булевых функций

Пример 5.8. Используя основные эквивалентности упростить формулы:

Пример 5.9. Доказать эквивалентность следующих функций:

Решение. Преобразуем обе функции.

Так как, правые части функций равны, то отсюда следует, что функции эквивалентны.

Пример 5.10. Доказать, что Для доказательства тождественной истинности формулы запишем цепочку равносильных формул:

Пример 5.11. Построить релейно-контактную схему для формулы .

Пример 5.12. Упростить РКС.

Решение.

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

Упростим РКС используя равносильности

Последняя формула соответствует схеме:

Задания для самостоятельного решения

5.3.1. Используя основные эквивалентности упростить формулы:

1. 11.

2. 12.

3. 13.

4. 14.

5. 15.

6. 16.

7. 17.

8. 18.

9. 19.

10. 20.

5.3.2. Используя законы логики, преобразуйте данные формулы:

1. 11.

2. 12.

3. 13.

4. 14.

5. 15.

6. 16.

7. 17.

8. 18.

9. 19.

10. 20.

5.15. Составьте РКС для формул:

1. 12.

2. 13.

3. 14.

4. 15.

5. 16.

6. 17.

7. 18.

8. 19.

9. 20.

10. 21.

11. 22.

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

5.3.5. Какие из приведенных формул являются тождественно истинными или тождественно ложными:

1. 12.

2. 13.

3. 14.

4. 15.

5. 16.

6. 17.

7. 18.

8. 19.

9. 20.

10. 21.

11.

5.3.6. Доказать эквивалентность следующих функций:

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

Функциональная полнота

Классы Поста.

1. Класс функций, сохраняющих константу 0, т.е. таких функций , что . Например,

2. Класс функций, сохраняющих константу 1, т.е. таких функций , что . Например, .

3. Класс самодвойственных функций, т.е. таких функций , что

4. Класс линейных функций, т.е. таких функций , которые могут быть представлены в виде где коэффициенты, которые могут принимать значение 0 или 1.

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

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

Критерий полноты (Теорема Поста). Система S булевых функций является полной тогда и только тогда, когда она включает хотя бы одну функцию: не сохраняющую константу 0, не сохраняющую константу 1, не самодвойственную, нелинейную и немонотонную.

1. Система функций образует базис. Для приведения булевой функции к виду содержащему лишь связки из базиса могут быть полезны следующие эквивалентности:

2. Система образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из а затем использовать соотношение

3. Система образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из а затем использовать соотношение

4. Система образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из а затем использовать соотношения

5. Система образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из а затем использовать соотношения

6. Система образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из а затем использовать соотношения

Примеры 5.13. Записать функцию в базисе .

Примеры 5.14. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения, выясните, является ли функция g (определена ниже) двойственной к функции

, . Значит, g не двойственна к f.

Пример 5.15. Используя критерий полноты (теорему Поста) проверить, является ли полной система функций

Решение: Проверим какими свойствами обладают данные функции.

1. Сохранимость константы 0. сохраняет константу 0. - не сохраняет константу 0.

2. Сохранимость константы 1. — не сохраняет константу 1. — не сохраняет константу 1.

3. Самодвойственность.

- не самодвойственна.

Составим таблицы истинности для функций: и

Из таблицы истинности видно, что т.е. -не самодвойственна.

4. Линейность. Построим полином Жегалкина для функции методом неопределенных коэффициентов. имеет вид:

Используя таблицу истинности для , полученную в п.3, имеем

Итак, - не линейна.

5. Монотонность. Очевидно, что наборы упорядочены следующим образом:

Проверим на монотонность функцию :

Итак, мы получили, что для , не выполняется следовательно, функция — не монотонна.

Проверим на монотонность функцию Итак, для мы не получили что . Следовательно, - не монотонна.

Сведем наши вычисления в таблицу.

Функция	Не сохр. 0	Не сохр. 1	Не самодв.	Не линейность	Не монотонность
	*	*	* *	* *	* *

Из теоремы Поста, заключаем, что система полная.

Пример 5.16. Найдем все импликанты и простые импликанты для формулы . Всего имеется 8 элементарных произведений с переменными и . Ниже, для наглядности, приведены их таблицы истинности:

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