Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Раздел 4. Функции алгебры логики. Тема 4.2. Сумма по модулю два



Тема 4.2. Сумма по модулю два. Многочлен Жегалкина

Задание 5. Доказательство свойств суммы по модулю два для трех переменных – 1ч.

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

Задание для самостоятельной внеаудиторной работы:

&5.1. Вспомните определение и способы задания булевой функции сумма по модулю два. Изучите свойства этой функции.

&5.2. Выясните, какие существуют способы доказательства свойств булевой функции суммы по модулю два. Познакомьтесь с ними на конкретных примерах. Проанализируйте, в каких случаях нужно использовать каждый из способов доказательства.

Основные сведения из теории:

5.3. Закончите определение:

P Суммой по модулю два называется булева функция двух переменных, принимающая значение…

5.4. Установите соответствие:

СВОЙСТВО БУЛЕВОЙ ФУНКЦИИ СУММА ПО МОДУЛЮ ДВА РАВЕНСТВО, ВЫРАЖАЮЩЕЕ СВОЙСТВО БУЛЕВОЙ ФУНКЦИИ СУММА ПО МОДУЛЮ ДВА
1.коммутативности А.
2. ассоциативности Б.
  В.
  Г.
  Д.
Е.

5.5.Закончите утверждение:Доказательство свойств булевой функции сумма по модулю может осуществляться как с помощью… , так и …

Задачи и упражнения:

?5.6.Докажите путем построения таблицы значений, что булева функция сумма по модулю два обладает следующими свойствами:

а) ассоциативности: ;

б) дистрибутивности конъюнкции относительно суммы по модулю два: ; в) .

?5.7. Проверьте путем построения таблицы значений, будет ли справедливым свойство дистрибутивности булевой функции дизъюнкции относительно суммы по модулю два.

?5.8. Используя известные Вам и доказанные ранее свойства булевой функции сумма по модулю два, установите справедливость следующих свойств этой функции:

а) ; б) ; в) .

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

а) суммы по модулю два ;

б) суммы по модулю два и конъюнкции .

Методические указания по выполнению работы:

Для успешного решения задач и упражнений рекомендуется детально изучить следующий теоретический материал и рассмотреть примеры:

Булева функция двух переменных x и y, принимающая значение 1 тогда и только тогда, когда значения ее переменных не совпадают, называется суммой по модулю два и обозначается .



Данную функцию можно задать таблицей значений

x y f

и булевым вектором .

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

. Эквиваленцию можно реализовать в виде композиции суммы по модулю два и отрицания: .

Представим равенства, выражающие некоторые свойства булевой функции сумма по модулю два:

1) свойство коммутативности: ;

2) свойство ассоциативности: ;

3) свойство дистрибутивности конъюнкции относительно суммы по модулю два:

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) ;

11) , ;

12) , .

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

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

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

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

(f) (g)

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



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

Пример 2. Используя известные Вам и доказанные ранее свойства булевой функции суммы по модулю два, докажите справедливость следующего свойства .

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

[свойство 6 в обратном порядке: ]= [для скобки свойство коммутативности булевой функции суммы по модулю два: ]= [свойство ассоциативности булевой функции суммы по модулю два:

]= [свойство 6 для скобки: ]= [свойство коммутативности булевой функции суммы по модулю два: ]= .

Таким образом, . Следовательно, справедливость свойства доказана.

Список литературы:

1. Спирина М.С. Дискретная математика: учебник для студ. СПО / М.С. Спирина, П.А. Спирин. - М.: Академия, 2012. – 368 с. (глава 4, п.4.7, стр. 187).


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!