Лекции, шпаргалки, информация по предметам, статьи, лабораторные, тех.задания


Кафедра ИС(АВТ)

Основы дискретной математики - Вопрос 19

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

Вопрос 19

Примеры функционально полных систем лог функций. Пример 3.14. Доказать, что система E1={-,/\,} функционально полна. Решение. Действительно, из закона де Моргана и двойного отрицания следует, что в E1 недостающая до Eo дизъюнкция выражается через конъюнкцию и отрицание: x1vx2=NE(nex1/\x2) (3.22) т.е. может быть заменена на комбинацию конъюнкций и отрицаний, составляющих систему £/. В частности, в ней, как нетрудно убедиться, булева формула f1=x1/\ х2vnex2/\(x3vх1) (3.23) перейдет в формулу f1= NE(х1/\ x2)/\NE(nex2/\NE(nex3/\nex4)). Эта формула уже не может быть представлена комбинационной схемой, состоящей из последовательно и параллельно соединенных нормально разомкнутых и нормально замкнутых контактов. Пример 3.15. Доказать, что система E2 ={-,v} функционально полна. Решение. Из второго тождества де Моргана и двойного отрицания следует, что в этой системе недостающая до Eo конъюнкция выражается через дизъюнкцию и отрицание: x1/\х2=NE(neх1vneх2). (3.24)

В этой системе булева формула (3.23) перейдет в формулу f1= NE(nex1vх2) v(NE[x2v(NE[x3vx4])]). Она также не может быть описана простой комбинационной цепью. С точки зрения функциональной полноты систему Eo={~,/\,v} можно считать избыточной: она сохраняет свойство полноты и при удалении из нее дизъюнкции иди конъюнкции. Но, как видно из последних двух примеров, за неизбыточность систем Е1 и E2 приходится платить избыточностью формул: ведь каждая замена одной операции на другую по соотношениям (3.22) и (3.24) вносит в формулу потри лишних отрицания.

Обсудить вопрос в студенческом форуме

 

Сайт содержит информацию о учебном заведении и студенческой общине и не является официальным