Вопросы к экзамену по дискретной математике

Так же их в печатном виде можно получить у меня (староста 106-ой группы).


Экзаменационная программа курса "Дискретная математика"
8 ф-т, I семестр 2006/07 уч. года, лектор -- проф. Осипова В.А.
1. Понятие множества. Основные принципы интуитивной теории множеств.
2. Операции над множествами. Основные тождества алгебры множеств.
3. Отношения. Примеры и свойства. Прямое произведение множеств. Операции над отношениями.
4. Отношение эквивалентности. Классы эквивалентности.
5. Разбиение множества. Теорема о связи между отношением эквивалентности на множестве и разбиением множества. Фактор-множество.
6. Понятие функции. Композиция и обращение функций, свойства.
7. Отношение порядка. Частичный и линейный порядок. Примеры. Максимальные и наибольшие элементы.
8. Равномощность множеств. Счетные множества. Примеры.
9. Равномощность множеств [0, 1] и (0, 1).
10. Несчетные множества. Теорема Кантора о несчетности отрезка [0, 1]. Континуум. Примеры.
11. Высказывания. Логические операции. Формулы логики высказываний.
12. Основные равносильности логики высказываний. Правило равносильных преобразований.
13. Закон двойственности в логике высказываний.
14. ДНФ и КНФ. Теоремы о приведении к ДНФ и КНФ.
15. СДНФ и СКНФ. Теоремы о приведении к СДНФ и СКНФ.
16. Тождественно истинные формулы логики высказываний. Проблема разрешимости.
17. Косвенный метод доказательства. Правильные рассуждения.
18. Булевы алгебры, примеры, свойства. Связь с логикой высказываний и алгеброй множеств.
19. Булевы функции. Теорема о представлении булевой функции формулой логики высказывании.
20. Полные системы булевых функций. Примеры.
21. Представление булевых функций многочленами Жегалкина.
22. Функционально замкнутые классы. Примеры.
23. Теорема Поста.
24. Независимые системы булевых функций. Базис функционально замкнутого класса.
25. Переключательные схемы. Понятие о минимизации в классе ДНФ. Сокращенные и минимальные ДНФ.
26. Формальные аксиоматические теории. Основные свойства выводимости.
Исчисление высказываний как формальная аксиоматическая теория.
27. Доказать, что выводима формула A A , где A - произвольная формула исчисления высказываний.
28. Доказать теорему о дедукции.
29. Доказать правило силлогизма.
30. Доказать, что выводимая в исчислении высказываний формула общезначима. Непротиворечивость исчисления высказываний.
31. Понятие полноты и непротиворечивости аксиоматической теории. Полнота исчисления высказываний.
32. Доказать полноту исчисления высказываний в узком смысле.
33. Независимость аксиом исчисления высказываний.
34. Понятие предиката. Кванторы. Формулы. Интерпретации.
35. Равносильность формул логики предикатов. Определение. Правило переноса квантора через отрицание. Правило выноса квантора за скобки.
36. Приведенная нормальная форма формул логики предикатов.
37. Выполнимость, общезначимость формул логики предикатов. Примеры. Проблема разрешимости. Теорема Черча.
38. Исчисление предикатов как аксиоматическая теория.



//--------------------------
"Я не боюсь потерять голову, я опасаюсь потерять лицо"

27 вопрос, что там за формула все-таки?

[slil.ru]
вот это мне отправила Виктория Аркадьевна.
В любом случае можно (и даже нужно) спросить ее во вторник.



//--------------------------
"Я не боюсь потерять голову, я опасаюсь потерять лицо"

Не хотел бы я это узнать во _вторник_!

Лучше на консультации спросим ^_^



______________________
|
|O
/\
/\

«Just hanging around..» © Melhesedek

Вы что?! Там стоит знак импликации! Своей группе и старостам остальных групп (по силу возможности) я раздал исправленную версию.



//--------------------------
"Я не боюсь потерять голову, я опасаюсь потерять лицо"