1. Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество: количество подмножеств конечного множества

16. Понятие предикатной формулы: свободные и связанные переменные. Построение отрицаний к предикатам, содержащим кванторные операции.
Переменная, на которую навешан квантор, называется связанной, остальные переменные свободные. Область действия квантора – выражение, на которое навешан квантор. Формулой логики предикатов называется выражение, удовлетворяющее следующим требованиям: 1) если Р-символ предиката, (x1, x2, … ,xn) – предметные переменные, то выражение Р(x1, x2, … ,xn) – формула атомарная. 2) если А — формула, то (не)¯А – тоже формула. Свободные и связанные переменные формулы А остаются такими же после проведения операции отрицания. 3) Пусть А и В – формулы, причем нет таких предметных переменных, которые были бы связанными в одной формуле и свободными в другой. 4) Пусть А формула содержащая свободную переменную Х. Тогда выражение ∃хА(х) и ∀хА(х) – формулы, но переменные в них уже связаны.
29. Понятие неориентированного графа, орграфа. Способы задания графа.
Графом называется двухосновная модель , где i – бинарное отношение множеств V и E, такое, что каждый элемент e О E находится в отношении i либо ровно с одним, либо ровно с двумя элементами множества V. При этом элементы множества V называются вершинами графа, элементы множества E называются рёбрами графа, а отношение i – отношением инцидентности. Вершины, инцидентные одному и тому же ребру, называются смежными. Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра – линиями, соединяющими те точки, соответствующим вершинам которых ребра инцидентны. Если ребро инцидентно только одной вершине, его называют петлей. Рёбра называются кратными, если они инцидентны одним и тем же вершинам. Если в наборе Х встречаются кратные ребра и петли, то про множество V и набор X будем говорить, что они задают псевдограф. Псевдограф без петель – мультиграф. Если в наборе Х ни одна пара не встретилась более 1-го раза, то такая структура называется графом. Если пары в наборе Х являются упорядоченными х=(Vi, Vj), где Vi – начало, Vj – конец ребра, то граф называется ориентированным или орграфом. Изображение графа на плоскости в виде рисунка, называется геометрической интерпретацией. Геометрическая интерпретация является произвольной, главное чтобы были реализованы элементы из множества V и набора X.