Материалы базового контроля знаний

по дисциплине «Элементы математической логики»

специальности

230115«Программное обеспечение вычислительной техники автоматизированных систем»

Номер вопроса / задания	Содержание вопроса / задания	Правильный (достаточный) ответ	Литература
Раздел 1 Математическая логика
	Дайте определение высказывания.	Высказывание – это предложение (утверждение), которое либо истинно, либо ложно.	[1, с. 141]
	Приведите пример высказывания.	Утверждение «Москва – столица России» - является высказыванием, потому что это утверждение истинно.	[1, с. 141]
	Дайте определение высказывательной формы.	Предложение, которое содержит хотя бы одну переменную и становится высказыванием при подстановке вместо всех переменных их значений, называется высказывательной формой.	[1, с. 141]
	Приведите пример высказывательной формы.	Утверждение «Произведение двух чисел и равно четырем» является высказывательной формой.	[1, с. 141]
	Дайте определение логических связок.	Союзы «и», «или», «если …., то..», «тогда и только тогда, когда …», частицу «не» называются логическими связками.	[1, с. 141]
	Дайте определение логической операции.	Образование составного высказывания с помощью логической связки называют логической операцией.	[1, с. 141]
	Дайте определение логической операции -конъюнкция.	Операция, соответствующая союзу «и», называется конъюнкцией.	[1, с. 142]
	Как обозначается логическая операция конъюнкция?	Логическая операция конъюнкция обозначается или &	[1, с. 142]
	Запишите определение конъюнкции в форме таблицы истинности	А В А & В И И И И Л Л Л И Л Л Л Л	[1, с. 142]
	Дайте определение логической операции -дизъюнкция.	Операция, соответствующая союзу «или», называется дизъюнкцией.	[1, с. 142]
	Как обозначается логическая операция дизъюнкция?	Логическая операция дизъюнкция обозначается	[1, с. 142]
	Запишите определение дизъюнкции в форме таблицы истинности	А В А В И И И И Л И Л И И Л Л Л	[1, с. 144]
	Дайте определение логической операции - отрицание	Операция, соответствующая союзу «не», называется отрицанием.	[1, с. 142]
	Как обозначается логическая операция отрицание?	Логическая операция отрицание обозначается __	[1, с. 142]
	Запишите определение отрицания в форме таблицы истинности	И Л Л И	[1, с. 144]
	Дайте определение логической операции – импликация.	Операция, соответствующая союзу «если …, то..», называется импликацией.	[1, с. 142]
	Как обозначается логическая операция импликация?	Логическая операция импликация обозначается	[1, с. 142]
	Запишите определение импликации в форме таблицы истинности	А В А В И И И И Л Л Л И И Л Л И	[1, с. 144]
	Дайте определение логической операции – эквиваленция.	Операция, соответствующая союзу «тогда и только тогда, когда …», называется эквиваленцией.	[1, с. 142]
	Как обозначается логическая операция эквиваленция?	Логическая операция эквиваленция обозначается	[1, с. 142]
	Запишите определение эквиваленции в форме таблицы истинности	А В А В И И И И Л Л Л И Л Л Л И	[1, с. 142]
	Составьте для данной формулы таблицу истинности	В первых двух столбцах таблицы выпишем всевозможные пары значений переменных. В последующие столбцы запишем значения формул согласно определениям логических операций. В результате получим таблицу: X Y И И Л И Л Л И Л Л Л И И Л И И И Л Л Л Л И И И И	[1, с. 145 - 147]
	Дайте определение тождественно истинной формулы	Формула, которая при любом наборе значений переменных принимает значение истина, называется тождественно истинной.	[1, с. 155]
	Дайте определение тождественно ложной формулы	Формула, которая при любом наборе значений переменных принимает значение ложь, называется тождественно ложной.	[1, с. 155]
	Дайте определение КНФ.	Формула вида , где - переменна или отрицание переменой, дизъюнкция переменных или их отрицаний, называется конъюнктивной нормальной формой (КНФ)	[1, с. 171-172]
	Приведите пример КНФ.	Например, для формулы имеем КНФ . Для формулы имеем КНФ	[1, с. 171-172]
	Дайте определение ДНФ	Формула вида , где - переменная или отрицание переменной, конъюнкция переменных или их отрицаний, называется дизъюнктивной нормальной формой (ДНФ)	[1, с. 170-171]
	Приведите пример ДНФ.	Например, для формулы имеем ДНФ . Для формулы имеем ДНФ )	[1, с. 170-171]
	Раздел 2 Логика предикатов
	Дайте определение предиката.	Функция, все значения которой принадлежат множеству , называется предикатом.	[1, с. 224]
	Дайте определение объединения двух множеств А и В.	Объединением двух множеств А и В называется множество, состоящее из тех элементов, которые принадлежат или множеству А или множеству В.	[1, с. 14, 19]
	Как обозначается объединение двух множеств А и В.	Объединение двух множеств А и В обозначается	[1, с. 19]
	Дайте определение пересечения двух множеств А и В.	Пересечением двух множеств А и В называется множество, состоящее из тех элементов, которые принадлежат и множеству А и множеству В одновременно.	[1, с. 18-19]
	Как обозначается пересечение двух множеств А и В?	Пересечение двух множеств А и В обозначается	[1, с. 19]
	Дайте определение разности двух множеств.	Разностью двух множеств А и В называется множество, состоящее из тех элементов, которые принадлежат множеству А и не принадлежат множеству В.	[1, с. 18-19]
	Как обозначается пересечение двух множеств А и В.	Разность двух множеств А и В обозначается	[1, с. 19]
	Даны множества и . Найдите	, ,	[1, с. 20]
Раздел 3 Теория графов
	Дайте определение графа.	Графом называется множество точек (вершин), некоторые из которых соединены отрезками (ребрами).	[1, с. 69-70]
	Дайте определение смежных вершин.	Две вершины графа называются смежными, если существует ребро их соединяющее.	[1, с. 71]
	Дайте определение смежных ребер.	Два ребра называются смежными, если у них есть общая вершина.	[1, с. 71]
	Что называется степенью вершины?	Степень вершины – это число ребер, выходящих из данной вершины. Степень вершины 1 обозначается deg(1).	[1, с. 71]
	Какая вершина называется четной?	Если степень вершины – четное число, то вершина называется четной.	[1, с. 71]
	Какая вершина называется нечетной?	Если степень вершины – нечетное число, то вершина называется нечетной.	[1, с. 71]
	В данном графе определите степени вершин 1 и 2	deg(1) = 2, deg(2) = 4	[1, с. 70-71]
	Что называется маршрутом в графе?	Маршрутом в графе называется последовательность ребер, каждая следующая из которых начинается в конце предыдущего.	[1, с. 72]
	Какой маршрут называется цепью?	Маршрут называется цепью, если все его ребра различны.	[1, с. 73]
	Какая цепь называется циклом?	Замкнутая простая цепь называется циклом.	[1, с. 73]
	Какой граф называется связным?	Граф, в котором любые две вершины соединены маршрутом, называется связным.	[1, с. 73-74]
	Дайте определение эйлерова графа.	Если связный граф имеет цикл (не обязательно простой), содержащий ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом. Эйлеровы графы можно изобразить «одним росчерком пера», причем процесс изображения начинается и заканчивается в одной вершине.	[1, с. 77]
	Приведите пример эйлерова графа.	Данный граф является эйлеровым графом.	[1, с.77]
	Дайте определение гамильтонова графа.	Если связный граф имеет простой цикл, проходящий по всем вершинам один раз, то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом.	[1, с. 77]
	Приведите пример гамильтонова графа.	Данный граф является гамильтоновым графом.	[1, с. 77]
	Дайте определение дерева графа.	Деревом графа называется связный граф без цикла.	[1, с. 80]
	Дайте определение остовного дерева.	Если в связном графе удалить по одному ребру, не нарушая связности, из каждого цикла, то получим дерево графа, связывающее все его вершины. Такое дерево графа называется остовным деревом.	[1, с. 83-84]
	Дайте определение циклического числа	Число удаленных ребер графа называется циклическим числом.	[1, с. 83-84]

Литература:

1. Спирина М.С., П.А.Спирин «Дискретная математика: учебник для студ. Учреждений сред. Проф. образования». - М.: Академия, 2004.- 368 с.