Кафедра информационных систем

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

By 29.11.2007 No Comments

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

Вопрос 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) вносит в формулу потри лишних отрицания.

Leave a Reply