|
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. Функцию
назовем полной, если класс, единственным элементом которого является эта
функция, будет полным. Доказать. Что штрих Шеффера и стрелка Пирса –
единственные полные функции среди всех двухместных функций.
|
Раздел 1. Математическая логика
Тема 1. Логика высказываний