Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

1) ;

2)

 

3)

 

4)

 

Пример 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. Используя основные эквивалентности упростить формулы:

1)

 

2)

 

3)

 

Пример 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. Доказать эквивалентность следующих функций:

1.

2.

3.

4.

5.

6.

7.

8.

9.

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 элементарных произведений с переменными и . Ниже, для наглядности, приведены их таблицы истинности:

 

 

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

 

 

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

5.19. Используя теорему Поста покажите, что следующие системы не являются полными.

1. , 2. 3. , 4. , 5. , 6. , 7. , 8. ,

9. , 10. , 11. , 12.

5.20. Следующие формулы преобразовать так, чтобы они содержали только а) б) в)

1. 8. 15.

2. 9. 16.

3. 10. 17.

4. 11. 18.

5. 12. 19.

6. 13. 20.

7. 14. 21.

 

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

 

1. 8. 15.

2. 9. 16.

3. 10. 17.

4. 11. 18.

5. 12. 19.

6. 13. 20.

7. 14. 21.

 

5.22. Записать функции из задачи 1.4 (§1) в базисах , , , , , .

 

5.23. Выяснить, является ли функция самодвойственной; монотонной:

1. 11.

2. 12.

3. 13.

4. 14.

5. 15.

6. 16.

7. 17.

8. 18.

9. 19.

10. 20.

 

5.24. Выяснить, является ли самодвойственной функция , заданная векторно:

1. 11.

2. 12.

3. 13.

4. 14.

5. 15.

6. 16.

7. 17.

8. 18.

9. 19.

10. 20.

 


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-05-28; Просмотров: 1903; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.164 с.)
Главная | Случайная страница | Обратная связь