English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и лабораторий Проблем теоретической кибернетики и Математичеких проблем искусственного интеллекта механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Канал кафедры МаТИС в Телеграм
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов

Критерий полноты в P2

 

3.1. Показать, что в P2 не существует предполных классов, отличных от T0, T1, L, S, M.

 

3.2. Полна ли система A:

1) A={ x→y, x→(z(y+1)) } (показать решение)

2) A={ 0, 1, x(y~z)V(x+1)(y+z) }

3) A={ (0110 1001), (1000 1101), (0001 1100) }

4) (S \ M) U (L \ (T0 U T1))

5) { f1, f2 }, где f1 ∈ S \ M, f2 ∉ L U S, f1 → f2=1 (показать решение)

6) { f1, f2, f3 }, где f1 ∉ L U (T0 ∩ T1), f2 ∈ M \ L, f1 → f2=1, f1 V f3=1

 

3.3. Из полной в P2 системы выделить всевозможные базисы:

1) A= { (x V y)( ¬x V ¬y ), xy+z, (x+y)~z, m(x,y,z) }, где m(x,y,z) = xy V xz V yz. (показать решение)

2) A= { 1, ¬x, xy(y~z), x+y+ m(x,y,z) }

3) A= { x V (x+y) V z, (x~y)~z, xy+zu, m(x, ¬y, ¬z) }

 

3.4. Привести по 3 примера базисов в P2, состоящих из 1, 2, 3 и 4 функций (показать ответ)

 

3.5. Можно ли расширить до базиса в P2 множество A?

1) A= { x+y, m(x,y,z) } (показать решение)

2) A= { x~y, x V yz }

3) A= M \ (T0 U T1)

4) A= L ∩ M

 

3.6. Доказать, что если f ∉ T0 U T1 U S, то f – шефферова. (показать решение)

 

3.7. При каких n (n>1) f является шефферовой?

f = (x1|x2)+(x2|x3)+…(xn-1|xn)+(xn|x1) (показать ответ)

 

3.8. Верно ли утверждение:

1) Если f ∉ (T0 U T1) \ S, то f ∈ L U M

2) Если f ∉ L U S U M, то f – шефферова

 

 

Список задач по P2

   © 2001- г. Кафедра Математической теории интеллектуальных систем, лаборатория ПТК, лаборатория МПИИ Написать вебмастеру   
Последние новости - в телеграм-канале кафедры МаТИС: Канал кафедры МаТИС в Телеграм Rambler's Top100 Рейтинг@Mail.ru