Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

В этой теме рассматриваются всюду определенные функции, заданные на множестве B={0,1}. Такие функции называются булевыми. Основная цель темы – доказать критерий полноты класса функций – теорему Поста.

§1. Замкнутость и полнота

§2. Самодвойственные функции

§3. Монотонные функции

§4. Линейные функции

§5. Критерий полноты

Задачи

1. Доказать, что [KÇL]Í[K]Ç[L], [K]È[L]Í[KÈL].


2. Содержит ли замыкание класса {i(x), x×y, xÚy} функции q(x), n(x)?


3. Является ли функция f двойственной к функции g

а) f=x+y, g=x«y, б) f=x®y, g=y®x,
в) f=x®y, g=n(x)×y, г) f=(x+y)×z, g=(x+y)×(z+1),
д) f=(x×y)Ú(x×z)Ú(y×z), g=x×y+x×z+y×z,
е) f=x«y, g=(n(x)×y)Ú(x×n(y))?

4. Будут ли следующие функции самодвойственными:

n(x), xy, x+y+z, (x×y)Ú(x×z)Ú(y×z), (xÚy)×(xÚz)×(yÚz)?


5. Показать, что не существует самодвойственной функции,

существенно зависящей от двух переменных.


6. Доказать монотонность функций x×(yÚz), xÚ(y×z), max(x,y,z),

min(x,y,z).


7. Будут ли следующие функции монотонны: yx+y, xy+y+x, x«y,

x®(y®x), x®(x®y), (x×y)Ú(x×z)Ú(y×z)?


8. Доказать, что функция, двойственная монотонной, сама монотонна.


9. Система функций С называется базисом замкнутого класса K, если замыкание системы С совпадает с K, но замыкание любой собственной подсистемы системы С уже не совпадает с K. Доказать, что система {q(x),i(x),x×y,xÚy} образует базис в классе всех монотонных функций.


10. Будут ли следующие функции линейными: x¯y, n(x«n(y)), (x«y)«z, x®(y®x)?


11. Сведением к известным полным классам доказать полноту классов функций:

а) {x®y, n(x))}, б) {x®y, q(x)),
в) {x¯y}, г) {x®y, x+y},
д) {xÚy, x+y, i(x)), е) {x«y, i(x), xÚy}.

12. Используя теорему Поста, доказать полноту классов функций:

а) {xÚy, n(x))}, б) {x®y, n(x)},
в) {x×y+x, x+y, i(x))}, г) {x+y, x«(y×z)},
д) {x×y, x+y, x«(x×y)}, е) {x«y, i(x), xÚy}.

13. Будут ли полными следующие классы функций:

а) {xy, x+y+1}, б) {q(x), i(x), (x×y)Úz},
в) {q(x), i(x), x«y}, г) {x×y+x, x«y, q(x)},
д) {xÚy, x×y+x×z}, е) {n(x), (x×y)Ú(x×z)Ú(y×z)},
ж) {i(x), n(x), x+y+max(x,y,z)}, з) {x+y, xÚyÚn(z)}?

14. Функцию назовем полной, если класс, единственным элементом которого является эта функция, будет полным. Доказать. Что штрих Шеффера и стрелка Пирса – единственные полные функции среди всех двухместных функций.

Ответы, указания и решения

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru