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

Булевы функции и способы их задания

 

1.1. Найти вектор значений функции, заданной формулой над множеством {f,g,h}, если функциональным символам f,g,h сопоставлены функции, заданные соответственно векторами (10), (1011) и (1000):

1) g( f( h( x, f(y) ) ), y ) (показать решение)

2) f( g( x, h( g(x,y), f(y) ) ) ) (показать ответ)

 

1.2. Построить таблицы функций, реализуемых формулами:

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

2) ¬x → (¬z ~ (y+x&z) ) (показать ответ)

 

1.3. Эквивалентны ли формулы (см. [1], стр. 14):

1) A=((x V y) V z) → ((x V y) (x V z)), B=x~z (показать решение)

2) A= ¬ ((x→y) V ((x→z)&y)), B=(x & ¬y)( ¬y→(x & ¬z )) (показать ответ)

 

1.4. Выяснить, можно ли реализовать функцию f формулой глубины k над множеством M (см. [1], стр. 30):

1) f=xy, k=2, M={|} (штрих Шеффера) (показать ответ)

2) f=x+y+z, k=2, M={→, &} (показать ответ)

3) f=x&y, k=999, M={→} (показать ответ)

 

1.5. Доказать, что если f реализуема формулой глубины k над множеством M, то она реализуема некоторой формулой над M, глубина которой больше k.

 

1.6. Методом эквивалентных преобразований проверить справедливость соотношений (см. [1], стр. 29)

1) x V (y~z)=(x V y) ~ (x V z) (показать решение)

2) x→(y&z)=(x→y)&(x→z)

3) x+(y→z)=(x+y)→(x+z)

 

1.7. Реализовать f формулой над M

f=x~y, M={&,→}

 

1.8. С помощью эквивалентных преобразований (см. [1], стр. 29) привести к ДНФ формулу

( x V y & ¬z ) & (x V z) (показать решение)

 

1.9. Построить совершенную ДНФ

(x+y)→yz

 

1.10. Построить полином Жегалкина методом неопределенных коэффициентов (см. [1], стр. 53)

f=(01101000) (показать ответ)

 

1.11. Найти все существенные переменные функции

1) f=(x V y V z¬y V ¬x¬y¬z) w

2) f=(00110011)

 

1.12. Найти все коммутативные операции от двух переменных.

 

1.13. Указать все пары функций от двух переменных, которые дистрибутивны.

 

1.14. Указать все пары дистрибутивных функций от двух переменных без условия коммутативности.

 

 

Литература

1. Г.П. Гаврилов, А.А. Сапоженко. Сборник задач по дискретной математике.

 

 

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

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