Дисциплина «Математическая логика и теория алгоритмов» (стр. 2 )

4.1. Перечень компетенций программы:

Дисциплина «Математическая логика и теория алгоритмов» обеспечивает инструментарий формирования следующих компетенций бакалавра направления «Информационная безопасность»:

- способностью применять соответствующий математический аппарат для решения профессиональных задач (ОПК-2).

В результате освоения дисциплины обучающийся должен:

знать:

?  место математической логики, теории алгоритмов в системе современного научного знания и ее значение как науки,

? основные исторические сведения и главные направления развития математической логики, теории алгоритмов,

?  основные положения логики высказываний,  предикатов, аксиоматических теорий, теорий первого порядка, их свойства, теории кодирования;

уметь:

? решать типовые задачи в указанной предметной области;

?  работать самостоятельно с учебной и дополнительной литературой;

? анализировать и осуществлять поиск различных путей решения задач, в том числе и задач повышенной сложности;

владеть:

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

? методами определения общезначимости формул при изучении алгебры высказываний и предикатов; способами построения машин Тьюринга;

?  логической символикой, основами теории логического вывода.

4.2. Описание показателей и критериев оценивания компетенций:

Итоговой формой контроля знаний, умений и навыков по дисциплине является экзамен, который оценивается оценками – «отлично», «хорошо», «удовлетворительно», «неудовлетворительно». Эти оценки проставляются в аттестационную ведомость.

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

При выставлении оценки могут быть применены рекомендательные критерии:

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

Оценка «хорошо» выставляется студенту, если он  усвоил программный материал;  логично его излагает, умеет увязывать теорию с практикой, но не в достаточной мере справляется с задачами, вопросами и другими видами применения знаний.

Оценка «удовлетворительно» выставляется студенту, если он слабо усвоил программный материал; с трудом излагает его содержимое, постоянно сбивается, не справляется в должной степени с задачами, вопросами и другими видами применения знаний.

Оценка «неудовлетворительно» выставляется студенту, который не знает значительной части программного материала, допускает существенные ошибки, с большим затруднениями выполняет практические работы. Как правило, оценка «неудовлетворительно» ставится студентам, которые не могут продолжить обучение без дополнительных занятий по дисциплине.

Оценку знаний студентов следует производить на практических или лабораторных занятиях по данной дисциплине, что является одной из форм их подготовки к экзамену. Основу системы контроля учебной работы студентов по дисциплине составляет контроль посещаемости лекционных и лабораторных занятий, выполнения РГР (контрольной работы).

Результаты контроля анализируются и при необходимости принимаются оперативные решения по улучшению организации и содержанию учебно-воспитательной работы в рамках данной дисциплины. При этом, особое внимание обращается на выявление отстающих студентов, на умение студентов четко организовать свой труд, на обеспечение ритмичной работы.

4.3 Типовые контрольные задания

Контрольная работа по математической логике 

№1. Исходя из данных условий, определите истинностные значения высказываний P, Q,R, S,T. Найдите самое короткое решение.

0	P?Q=1	Q?R=0	R?S=0	S?T=1
1	P?Q=1	Q?R=0	R?S=0	S?T=0
2	P?Q=0	Q?R=0	R?S=1	S?T=1
3	P?Q=1	Q?R=1	R?S=1	S?T=0
4	P?Q=1	Q?R=0	R?S=0	S?T=1
5	P?Q=0	Q?R=0	R?S=1	S?T=0
6	P?Q=1	Q?R=1	R?S=1	S?T=1
7	P?Q=1	Q?R=0	R?S=0	S?T=0
8	P?Q=0	Q?R=0	R?S=1	S?T=1
9	P?Q=1	Q?R=1	R?S=1	S?T=0
10	P?Q=1	Q?R=0	R?S=0	S?T=1

Решение варианта 0. По определению импликации из R?S?0 следует R?1 и S?0. По определению отрицания ?S?1. По определению эквивалентности из ?S?T?0 и ?S?1 следует T?0. По определению конъюнкции из Q?R?0 и R?1 следует Q?0. По определению дизъюнкции из P?Q?1 и Q?0 следуетP?1. Ответ: (P, Q,R, S,T)?(1,0,1,0,0).

№2. Докажите двумя способами (при помощи таблицы истинности и методом доказательства от противного), что формула X – тавтология. Решение 2-м способом постройте так, чтобы на каждом шаге истинностное значение определялось бы однозначно.

0	X=[A?(B?C)]?[(A?B)?(A?C)]
1	X=[(A?B)?(A?C)]?[A?(B?C)]
2	X=[(A?C)?(B?C)]?[(A?B)?C]
3	X=[A?(B?C)]?[(A?B)?(A?C)]
4	X=[(A?B)?C]?[(A?C)?(B?C)]
5	X=[A?(B?C)]?[(A?B)?(A?C)]
6	X=[(A?B)?(A?C)]?[A?(B?C)]
7	X=[(A?B)?C]?[(A?C)?(B?C)]
8	X=[(A?C)?(B?C)]?[(A?B)?C]
9	X=[(A?B)?(A?C)]?[A?(B?C)]
10	X=[(A?C)?(B?C)]?[(A?B)?C]

Решение варианта 0.1-й способ (построение таблицы истинности).

A	B	C	B?C	A?(B?C)	A?B	A?C	(A?B)?(A?C)	X
1	1	1	1	1	1	1	1	1
1	1	0	0	0	1	0	0	1
1	0	1	1	1	0	1	1	1
1	0	0	1	1	0	0	1	1
0	1	1	1	1	1	1	1	1
0	1	0	0	1	1	1	1	1
0	0	1	1	1	1	1	1	1
0	0	0	1	1	1	1	1	1

Переменным A, B, C приписываются все возможные распределения истинностных значений 1 (истинно) и 0 (ложно). Истинностные значения формулB?C, A?(B?C), A?B, A?C, (A?B)?(A?C),X вычисляются по таблице истинности для импликации. Видно, что формула X принимает истинностное значение 1 при любом распределении истинностных значениях букв A, B, C. Значит, формула X – тавтология.

2-й способ (доказательство от противного). Пусть формула X принимает истинностное значение 0 при некотором распределении истинностных значений букв A, B, C.

Тогда: (1) A?(B?C)=1 по определению импликации;

(2) (A?B)?(A?C)=0 по определению импликации;

(3) A?B=1,

(4) A?C=0, – в силу (2), по определению импликации;

(5) A=1,

(6) C=0, – в силу (4), по определению импликации;

(7) B?C=1, в силу (1) и (5), по определению импликации;

(8) B=1, в силу (3) и (5), по определению импликации;

(9) C=1, в силу (7) и (8), по определению импликации.

Конъюнкция условий (6) и (9) есть противоречие. Значит, формула X принимает истинностное значение 1 при любом распределении истинностных значений букв A, B, C, и поэтому является тавтологией.

№3. Постройте переключательную схему с переключателями A, B и C, удовлетворяющую заданию. Запишите ее формулу. Упростите схему, преобразуя формулу при помощи булевых преобразований.

0	Должно выполняться хотя бы одно из следующих трех условий: 1) переключатель A включен, а переключатели B и C выключены; 2) переключатели A иB включены, а переключатель C выключен; 3) если переключатель Bвключен, то переключатели A иC выключены.
1	Хотя бы один из переключателей A, B и C выключен, а переключатель A включен тогда и только тогда, когда переключатели B и C выключены.
2	Если переключатель A выключен, то переключатели B и C включены, и переключатель B выключен тогда и только тогда, когда переключатели A и C включены.
3	Ровно два из трех переключателей A, B и C включены, а один из переключателей B и Cвыключен.
4	Переключатели A, B и C одновременно включены или одновременно выключены, или переключатель A включен, а один из переключателей B и C выключен.
5	Если переключатель C выключен, то переключатели A и B включены, и переключатель A выключен тогда и только тогда, когда переключатели B и C включены.
6	Хотя бы один из переключателей A, B и C включен, а переключатель A выключен тогда и только тогда, когда переключатели B и C включены.
7	Если переключатель B выключен, то переключатели A и C включены, и переключатель C выключен тогда и только тогда, когда переключатели A и B включены.
8	Переключатели A, B и C одновременно включены или одновременно выключены, или переключатель B выключен, а один из переключателей A и C включен.
9	Ровно два из трех переключателей A, B и C выключены, а один из переключателей A и B включен.
10	Переключатели A, B и C одновременно включены или одновременно выключены, или один из переключателей A и B выключен, а переключатель C включен.

Решение варианта 0. Пусть буква X обозначает включенный переключатель X, а отрицание X– выключенный переключатель X. Тогда задание можно записать в виде следующей формулы: (A?B?C)?(A?B?C)?(B?(A?C)).