Примерный перечень типовых задач. 1. Из 100 студентов-лингвистов польский язык изучают 42, чешский – 25, венгерский – 36, польский и чешский – 15

1. Из 100 студентов-лингвистов польский язык изучают 42, чешский – 25, венгерский – 36, польский и чешский – 15, польский и венгерский – 14, чешский и венгерский – 12, польский, чешский и венгерский – 5. Сколько студентов не изучают ни одного из перечисленных языков?

2. Найти все разбиения множества и множества .

3. На множестве заданы бинарные отношения и . Задать эти бинарные отношения перечислением элементов, указать свойства этих бинарных отношений, определить являются ли они отношениями эквивалентности (если являются, то найти классы эквивалентности их элементов).

4. У Олега десять книг, а у Ивана - двадцать. Сколькими способами можно осуществить обмен одной книги Олега на одну книгу Ивана?

5. Подсчитать число четных четырехзначных чисел, составленных из цифр , в десятичной записи которых соседние цифры различны.

6. Из города А в город В ведут четыре дороги. Сколькими способами можно съездить из А в В и обратно, если:

а) путешествие туда и обратно совершается по разным дорогам;

б) дороги туда и обратно выбираются независимо друг от друга?

7. Сколько имеется шестизначных чисел, в которых «четные» (0, 2, 4, 6, 8) и «нечетные» (1, 3, 5,7, 9) цифры чередуются?

8. Сколько имеется пятизначных чисел, в десятичной записи которых встречаются одинаковые цифры?

9. а) Сколькими способами можно разместить пять занумерованных шаров по девяти пронумерованным коробкам, если в одну коробку можно положить не более одного шара?

б) Сколькими способами можно разместить пять занумерованных шаров по девяти пронумерованным коробкам, если в одну коробку можно положить неограниченное число шаров?

10. Сколько разных шестибуквенных слов можно получить, переставляя буквы в слове «фартук»?

11. а) Сколькими способами на одной полке можно разместить шесть книг по физике и шесть книг по математике так, чтобы книги по физике стояли правее книг по математике?

б) Сколькими способами на одной полке можно разместить шесть книг по физике и шесть книг по математике так, чтобы книги по физике чередовались с книгами по математике?

12. а) Сколькими способами Маша может выбрать два предмета из восьми для сдачи экзамена по выбору?

б) Маша должна сдать два экзамена за восемь дней. Сколькими способами она может составить расписание экзаменов, если нельзя сдавать больше одного экзамена в день?

13. В киоске продаются 10 видов рождественских поздравительных открыток. Тане нужно купить 8 открыток. Сколькими способами Таня сможет это сделать, если:

а) она решила купить открытки только разных видов;

б) она решила купить по две открытки четырех видов;

в) Тане все равно, какие открытки покупать;

г) одна из открыток понравилась Тане больше других, и она решила купить хотя бы одну такую открытку?

14. Собрание из 50 человек выбирает председателя, секретаря и трех членов счетной комиссии. Сколькими способами это можно сделать?

15. Доказать тождества

а) ; б) ;

в) ; г) .

16. Сколько существует булевых векторов длины 8, которые одинаково читаются слева направо и справа налево?

17. Перечислить в порядке возрастания номеров булевы векторы длины 3.

18. Построить таблицу истинности и выписать вектор значений функции, заданной формулой:

а) ;

б) .

19. Учитывая соглашения о порядке выполнения операций, опустить «лишние» скобки и знак «» в формулах:

а) ; б) .

20. Показать, что формулы и задают равные функции.

21. Применяя равносильные преобразования, упростить формулу:

а) ; б) .

22. Задать вектором значений функцию, двойственную данной:

а) ; б) .

23. Найти функции, двойственные к сложению по модулю два, эквивалентности, штриху Шеффера и стрелке Пирса.

24. Задать формулой функцию, двойственную данной:

а) ; б) .

25. Задать вектором значений функцию, двойственную функции .

26. Задатьфункцию в виде СДНФ.

27. Задатьфункцию в виде СКНФ.

28. Перечислить все элементарные конъюнкции над множеством , обращающиеся в единицу на наборе .

29. Перечислить все простые импликанты функции .

30. Построить минимальные ДНФ функции:

а) ; б) .

31. Определить, принадлежит ли множествам и функция .

32. Определить число булевых функций от переменных:

а) сохраняющих 1;

б) сохраняющих как 0, так и 1, т.е. содержащихся в пересечении множеств и ;

в) содержащихся в объединении множеств и .

33. Выяснить, является ли самодвойственной функция .

34. Скольким булевым векторам предшествует вектор (1,0,1,0,0,0,1,0,1)?

35. Выяснить, монотонна или нет функция .

36. Используя метод равносильных преобразований, найти полином Жегалкина, реализующий функцию .

37. Методом неопределенных коэффициентов задать полиномом Жегалкина функцию:

а) ; б) .

38. Задать полиномами Жегалкина все линейные функции от 2-х переменных.

39. Определить, каким из классов Поста принадлежит функция .

40. Доказать, что функцию нельзя задать формулой над множеством , если:

а) , ;

б) , ;

в) , .

41. Используя критерий полноты, выяснить, полна ли система булевых функций :

а) ; б) .

42. Указать подмножества , являющиеся базисами:

а) ; б) .

Ответы

1. 33. 2. Разбиения : , , ; Разбиения : 1. ; 2. ; 3. ; 4. ; 5. ; 6. ; 7. ; 8. ; 9. ; 10. ; 11. ; 12. ; 13. ; 14. ; 15. .

3. - рефлексивно, симметрично, транзитивно, отношение эквивалентности; , ; - симметрично.

4. 200. 5. . 6 а) 12; б) 16. 7. . 8. . 9. а) ; б) . 10. . 11. а) ; б) . 12. а) ; б) . 13. а) ; б) ; в) ; г) . 14. 42375200. 16. 16. 17. , , , , , , , . 18. а) ; б) . 19. а) ; б) . 21. а) ; б) . 22. а) . б) . 23. , , , . 24. а) ; б) .

25. а) . 26. . 27. . 28. , , , , , , . 29. , . 30. а) , ; б) , . 31. , . 32. а) ; б) ; в) . 33. Нет. 34. 16. 35 монотонна. 36. . 37. а) ; б) . 38. . 39 , принадлежит только . 40 а) , а ; б) ; в) . 41. а) Полная; б) неполная. 42. а) Имеем один базис: . б) Имеем два базиса: и .