Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Примеры

Читайте также:
  1. WEB-сервер - назначение, основные функции, программная реализация, конкретные примеры
  2. Виды ландшафтных карт, примеры
  3. Генные мутации, их виды. Примеры.
  4. Гетерогенные сети ЭВМ - необходимость использования, примеры, возможности, методы обеспечения взаимодействия ЭВМ.
  5. Графоаналитические примеры анализа карт.
  6. Дайте определение систематическому риску. Приведите примеры.
  7. Дать определение понятиям и привести примеры
  8. Демонстрационные примеры
  9. Задание 3. Перечислите важнейшие современные глобальные проблемы человечества. Охарактеризуйте основные направления их решения. Приведите конкретные примеры.
  10. Исторические примеры использования карт

1. Проверить принадлежность каждому из классов P 0, P 1, S, L, M функций Ú иÅ.

Решение. Выпишем соответствующие таблицы истинности:

xy | Ú Å

0 0 | 0 0

0 1 | 1 1

1 0 | 1 1

1 1 | 1 0

P 0: Из первой строки видно, что дизъюнкция и сложение Å сохраняют 0. Следовательно, Ú,ÅÎ P 0;

P 1: Из последней строки видно, что дизъюнкция сохраняет 1, а сложение Å – нет. Следовательно, ÚÎ P 1, а ÅÏ P 1.

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

Способ I. Для дизъюнкции имеем f *=(x Ú y)*= xy. Но

x Ú y ¹ xy, следовательно ÚÏ S.

Способ II. Для сложения Å воспользуемся таблицей:

x y | Å Å*

0 0 | 0 1

0 1 | 1 0

1 0 | 1 0

1 1 | 0 1

Последний столбец для двойственной функции был получен по следующему правилу: столбец функции инвертируется (замены 0«1), полученные значения записываются в инвертированные строки. Например, строка 0 1 ú 1 для Å превращается в строку 1 0ú 0 для Å*.

Из полученной таблицы следует, что ŹÅ*, т.е. ÅÏ S.

L: Представим исследуемые функции через 1, Ø и Å.

Для дизъюнкции имеем:

x Ú y =(xy ’)’=((1Å x)(1Å y))’=1Å((1Å x)(1Å y))=

=1Å(1Å x Å y Å xy)= x Å y Å xy.

Здесь мы воспользовались законом де Моргана, тождеством x ’=1Å x, дистрибутивностью сложения Å относительно Ù и ассоциативностью Å (’’привычные’’ правила раскрытия скобок).

Полученное выражение содержит нелинейное слагаемое xy. Отсюда следует, что ÚÏ L.

Для сложения по модулю два имеем: f = x Å y – линейная функция. Значит, ÅÎ L.

M: Вернемся к таблицам истинности обеих функций (см. пункт P 0). Необходимо сравнить значения функции для каждой сравнимой пары аргументов. Мы видим, что дизъюнкция монотонна, а Å — не монотонна. Следовательно, ÚÎ M, ÅÏ M.

2. Найти линейную булеву функцию f (x, y, z), удовлетворяющую условиям: f (1,0,0)=1, f (0,1,0)=1, f (1,1,1)=0 и f (1,1,0)=0.

Решение. Будем искать линейную функцию в виде

f (x, y, z)=a0Åa1 x Åa2 y Åa3 z.

Указанные условия приводят к системе линейных булевых уравнений

Воспользуемся методом Гаусса, учитывая, что 1Å1=0:

.

Следовательно, a0=0, a1=1, a2=1 и a3=0, т.е. f (x, y, z)= x Å y.

Вопросы и упражнения для самостоятельной работы

7. Проверить принадлежность каждому из классов P 0, P 1, S, L, M следующих функций: a) Ù, б) ¯, в) Ø.

8. Найти все булевы функции двух переменных, принадлежащие а) классу M, б) классу S.

9. Принадлежит ли классу L функция а) xy, б) x ½ y, в) x «y.

10. Построить булеву функцию, не принадлежащую ни одному из классов P 0, P 1, S, L, M.

11. Монотонны ли следующие функции:

а) x Ú yz, б) x ¯(y Ú z), в) xy Ú(xy ’Å z).

12. Найти линейную булеву функцию f (x, y), удовлетворяющую условиям:

а) f (0,1)=1, f (1,0)=0 и f (1,1)=0;

б) f (1,0)=0, f (0,1)=1 и f (1,1)=1.

13. Найти линейную булеву функцию f (x, y, z), удовлетворяющую условиям:

а) f (0,1,0)=1, f (0,0,1)=0, f (1,1,1)=1 и f (1,0,1)=1;

б) f (0,0,1)=0, f (0,1,0)=1, f (1,1,1)=1 и f (1,1,0)=1.




Дата добавления: 2015-04-11; просмотров: 24 | Поможем написать вашу работу | Нарушение авторских прав

1 | 2 | 3 | <== 4 ==> | 5 |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав