Математическая логика и теория алгоритмов (стр. 2 )

4-балльная шкала (уровень освоения)	Показатели	Критерии
Отлично (повышенный уровень)	Полнота изложения теоретического материала; Полнота и правильность решения практического задания; Правильность и/или аргументированность изложения (последовательность действий); Самостоятельность ответа; Культура речи; и т. д.	Студентом дан полный, в логической последовательности развернутый ответ на поставленный вопрос, где он продемонстрировал знания предмета в полном объеме учебной программы, достаточно глубоко осмысливает дисциплину, самостоятельно, и исчерпывающе отвечает на дополнительные вопросы, приводит собственные примеры по проблематике поставленного вопроса, решил предложенные практические задания без ошибок.
Хорошо (базовый уровень)	Студентом дан развернутый ответ на поставленный вопрос, где студент демонстрирует знания, приобретенные на лекционных и семинарских занятиях, а также полученные посредством изучения обязательных учебных материалов по курсу, дает аргументированные ответы, приводит примеры, в ответе присутствует свободное владение монологической речью, логичность и последовательность ответа. Однако допускается неточность в ответе. Решил предложенные практические задания с небольшими неточностями.
Удовлетворительно (пороговый уровень)	Студентом дан ответ, свидетельствующий в основном о знании процессов изучаемой дисциплины, отличающийся недостаточной глубиной и полнотой раскрытия темы, знанием основных вопросов теории, слабо сформированными навыками анализа явлений, процессов, недостаточным умением давать аргументированные ответы и приводить примеры, недостаточно свободным владением монологической речью, логичностью и последовательностью ответа. Допускается несколько ошибок в содержании ответа и решении практических заданий.
Неудовлетвори-тельно (уровень не сформирован)	Студентом дан ответ, который содержит ряд серьезных неточностей, обнаруживающий незнание процессов изучаемой предметной области, отличающийся неглубоким раскрытием темы, незнанием основных вопросов теории, несформированными навыками анализа явлений, процессов, неумением давать аргументированные ответы, слабым владением монологической речью, отсутствием логичности и последовательности. Выводы поверхностны. Решение практических заданий не выполнено. Т. е студент не способен ответить на вопросы даже при дополнительных наводящих вопросах преподавателя.

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

Преподаватель самостоятельно определяет перечень типовых контрольных заданий, включает типовые контрольные задания в фонд оценочных средств, размещаемый в ЭИОС АлтГУ, ознакомляет обучающихся с ним вначале изучения учебной дисциплины.

ТЕСТОВЫЕ ЗАДАНИЯ

Перечень заданий / вопросов

Тесты проверки текущих знаний студентов Задачи по теме «ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ» 1. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей: ; ; ; ; ; ; ; ; ; ; . 2. Используя непосредственно определение двойственности булевых функций, а также основные эквивалентности и соотношения, выясните, является ли функция g двойственной к функции f: 1),                        ; 2) ,                                ; 3),         ; 4),        ; 5),                        ; 6),                        ; 7),                ; 8),                        ; 9),         ; 10),                ; 11),         ; 12),                . Ответы: 4), . Значит, g не двойственна к f.  6) – не является; 8),9),11) – является. 3. Указать все фиктивные переменные у функции f: 1) 2) 3) 4) 5) 6) Ответы:1) две фиктивные переменные;        3) одна фиктивная переменная; 5)фиктивные переменные x1 и x3. 4. Выяснить, можно ли из функции f, отождествляя и переименовывая в ней переменные, получить функцию g: 1),                                         2),                                         3),                                         4),                         5),                         6),                                 7),                                ; 8),        ; 9),        ; 10),        . Ответы: 1),2),5),7),8),9),10)можно.                3),4),6)нельзя. 5. Представить в СКНФ следующие функции: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Ответы: 1);        2); 6) ; 8) 6. Используя эквивалентные преобразования, построить КНФ функции : 1) 2); 3) 4) 5) 6) 7) Ответы: 1) 3) 6) 7. С помощью преобразований вида и построить из данной КНФ функции ее совершенную КНФ: 1) 2) 3) 4) 5) 6) 7) 8) Ответы: 1) 5) 8. Используя дистрибутивный закон и эквивалентности и перейти от заданной ДНФ функции к ее КНФ: 1) 2) 3) 4) 5) 6) 7) 8) Ответы: 2) 5) 9. Методом треугольника Паскаля построить полином Жегалкина для этой функции, если: 1)  2) 3)  4) 5)  6) 7)  8) 9)  10) Ответы: 1)  4)  7) 10. Построить множество всех функций, зависящих от переменных x1,x2 и принадлежащих замыканию множества А: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) Ответы:        1)        2)        3)                4)        5)        6) 11. Выписать все попарно неконгруэнтные функции , принадлежащие замыканию множества А: 1)        2)                3)        4) 5)        6)        7)        8)                9)                10) Ответы: 1)        2)        3)        4)  5) 12. Сведением к заведомо полным системам в P2 показать, что множество А является полной системой в P2: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Ответы: 1)система является полной в P2, поскольку всякая может быть представлена в виде ДНФ или КНФ. С другой стороны, 2) имеем Система полна, поскольку 3) имеем ; 4) имеем ; 5) имеем ; 13. Выяснить, является ли самодвойственной функция f, заданная векторно: 1)  2) 3)   4) 5)  6) 7)  8) 9)  10) 11)  12) 13)  14) 15) Ответы: 1),3),5),6),7),8) – является;        2),4),9),10) – не является. 14. Представив функцию f полиномом, выяснить, является ли она линейной: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) Ответы: 2),3),5),6),8),9)–является.        1),4),7),10)–не является. 15. Доказать, что система А полна в L. Выяснить, является ли система A базисом в L: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) Ответы: 1)с помощью суперпозиции из функции можно получить любую функцию вида , путем подстановки 1-любую функцию вида Система А является базисом; 2),3),4),5),7),8),9) – является;        6),10) – не является. 16. Подсчитать число функций, зависящих от переменных x1,…,xn и принадлежащих множеству А: 1); 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18) 19) 20) 21) 22) 23) 24) 25) 26) 27) 28) 29) 30) 31) 32) 33) 34) 35) 36) 37) 38) 39) 40) 41) 42) 43) 44) 45) Ответы: 1); 2);  3)22n;  4); 5)  6)2n;  7);  8); 9); 10);  15) 0. 17. Выяснить, является ли множество А базисом в классе К: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) Ответы: 1)да. Имеем ; 2) А не является базисом в T1,так как ; А не является базисом в T1,так как ; А не является базисом в T1,так как ; А не является базисом в T1,так как ; А – базис в . 18. Проверить, является ли функция f монотонной: 1) 2) 3) 4) 5) 6) 7) 8) Ответы: 1),2),4),6),7) – является;        3),5),8) – не является. 19. Выяснить, полна ли система А функций, заданых векторами своих значений: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Ответы: 3),5) – полна;        1)нет,  2)нет,  4)нет,  6)нет, 20. Проверить, является ли система функций А базисом в Р2: 1) 2) 3) 4) 5)6) 7) 8) Ответы:1) нет, так как подсистема полна; 2) является; 3) не является, 4)нет, можно удалить 21. Используя теоретико - множественные операции, выразить через известные замкнутые классы T0, T1, L, S, M и P2 замыкания множества А: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) Ответы: 1)P2;  2) 3) 4) 5) 6) 22. Выяснить, полна ли система функций 1) 2) 3) 4) Ответы: 1)вообще говоря, нет. Рассмотреть 2) да, имеем 3) вообще говоря, нет. Рассмотреть 4) вообще говоря, нет. Рассмотреть Задания для контроля итоговых (остаточных) знаний Задачи по теме «ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ» 1. Построить таблицы соответствующих функций, выяснить, эквивалентны ли формулы и : ,                        ; ,                         ,                                ; ,                  ; ,  ; ,                ; ,                 ; ,                 ; ,                ; ,                 . Ответы: 2), 6), 9), 10) – эквивалентны;                3), 7) – не эквивалентны. 2. Используя приведенные выше основные эквивалентности и соотношения докажите эквивалентность формул V и U: 1),                         ; 2),                 ; 3),                         ; 4),  ; 5),         ; 6),                 ; 7),                 ; 8),                         ; 9), ; 10),  . Ответы: 4); 9) 3. Используя принцип двойственности, постройте формулу, реализующую функцию, двойственную к функции f, и убедитесь в том, что полученная формула эквивалентна формуле V: 1),                        ; 2),                ; 3),                        ; 4),                                ; 5),        ; 6),        ; 7),        ; 8),                                ; 9),                        ; 10),        . Ответы: 1) 2);        5);        10). 4. Показать, что x1 – фиктивная переменная у функции f (реализовав для этой цели функцию f формулой, не содержащей явно переменную x1): 1);                 2); 3);                 4) 5)  6) 7) 8) 9) 10) Ответы:        4),8),10)        9) 5. Представить в СДНФ следующие функции: 1); 2) 3) 4) 5) 6) 7) 8) 9) 10) Ответы:  2);        4), 7) 6. С помощью эквивалентных преобразований построить ДНФ функции : 1) 2) 3) 4) 5) 6)                 7) 8) 9) 10) Ответы: 4) 10) 7. Применяя преобразования вида ипостроить из заданной ДНФ функции ее совершенную ДНФ: 1) 2) 3) 4) 5) 6) 7) 8) Ответы: 2) 5) 8. Используя дистрибутивный закон и эквивалентности и перейти от заданной КНФ функции к ДНФ: 1) 2) 3) 4) 5) 6) 7) Ответы: 3) 6) 9. Методом неопределенных коэффициентов найти полиномы Жегалкина для следующих функций: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Ответы: 1)  3)  6) 10) 10. Представив функцию формулой над множеством связок {&, }, преобразуйте полученную формулу в полином Жегалкина функции (используя эквивалентности ): 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Ответы: 1) 3) 9) 11. Покажите, что , выразив формулой над множеством А: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) Ответы: 1)                 2)                         3)        4)                5)                 6)                7) 12. Из полной для класса [A] системы выделить базис: 1)                                2)  3)                4) 5)                        6)         7)         8) 9)                 10) Ответы:        1)        2)        3)        4) 5) 13. Выяснить, является ли функция f самодвойственной: 1)  2) 3)  4) 5)  6) 7)                8) 9)  10) 11)  12) 13)  14) 15) Ответы: 1),3),4),8),10) – является;        2),5),6),7),9) – не является. 14. Выяснить, является ли множество А самодвойственным: 1) 2) 3) 4) 5)         6) 7) 8) 9) 10) 11) 12) 13) 14) 15) Ответы: 1),3),5-7),10) – является;        2),4),8),9) – не является. 15. Выяснить, является ли линейной функция f, заданная векторно: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) Ответы: 1),3),4),5),7),8),9),10) – является;        2),6) – не является. 16. Выяснить, принадлежит ли функция f множеству T1\T0: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Ответы: 1),3),4),6),8),9) – является;        2),5),7),10) – не является. 17. Доказать, что: Указание: если то если то 18. По вектору значений выяснить, является ли функция f монотонной: 1) 2) 3) 4) 5) 6) 7) 8) Ответы: 2),3),5),8) – является;        1),4),6),7) – не является. 19. Выяснить, полна ли система  функций: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Ответы: 2),4),6) – полна;        1)нет, 3)нет,  5)нет, 20. Выяснить, полна ли система А: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Ответы: 1),4),6) – полна;        2)нет,  3)нет,  5)нет, 21. Из полной в Р2 системы А выделить всевозможные базисы: 1) 2) 3) 4) 5) 6) 7) 8) Ответы: 1)где 2) 22. Выяснить, можно ли расширить до базиса в Р2 множество А: 1) 2) 3) 4) 5) 6) 7) 8) Ответы: 1) можно, – базис; 2) нельзя, функция x входит во все предполные классы; 3) можно, – базис; 4) нет, функции и принадлежат одним и тем же предполным классам.

ПРАКТИЧЕСКИЕ ЗАДАНИЯ