📚 Коллекция ответов по предмету Математическая логика и теория алгоритмов в Синергии – большая база! 💯

Даны два множества: А = {1, 2, 3}, B = {4, 5}. Укажите Декартово (прямое) произведение множеств А и В.

Установите соответствие между формулой и названием закона алгебры множеств:

1. A ∩ (B ∩ C) = (A ∩ B) ∩ C
2. A ∩ B ∪ A ∩ B̅ = B
3. A ∩ (A ∪ B) = A
4. A ∪ A = A ∩ A = A
5. закон склеивания
6. закон идемпотентности
7. закон ассоциативности
8. закон поглощения

Расположите недостающие слова в формулировке теоремы Кантора–Бернштейна в правильном порядке
«Пусть даны два множества A и B. Тогда если существуют … … f : A → B и g : B → A, то существует и … h : A ↔ B, то есть множества A и B …»

Расположите недостающие слова в определении в правильном порядке:
Пусть R⊆A× A. Тогда бинарное отношение R называется:

1. ..., если для любых a∈A пара (a,a)∈R
2. ..., если (x,y)∈R, то и (y,x)∈R;
3. ..., если (x,y)∈R и (y,x)∈R, то x=y;
4. ..., если (x,y)∈R и (y,z)∈R, то (x,z)∈R.

Множество 2^А называется ... множества А.

Операции, при выполнении которых появляются новые элементы, называют … операциями.

Всякое множество, элементам которого можно поставить во взаимно однозначное соответствие множество натуральных чисел, называется …

Укажите операцию, не относящуюся к основным алгебраическим операциям над множествами:

Даны четыре линейных рекуррентных соотношения.
Запишите их по следующему правилу: от рекуррентного соотношения меньшего порядка до рекуррентного соотношения большего порядка.

1. a_n + 2 = 2a_n+1 – 3a_n + 2a_n-1
2. a_n + 2 = 4a_n+1 – 2a_n + 3a_n-1 - a_n-2
3. a_n + 2 = 4a_n+1 – 3
4. a_n + 2 = 3a_n+1 + 2a_n
   
   
   
   

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

Подмножество, составленное из элементов некоторого конечного множества, называют … данного множества.

Какая из указанных последовательностей, не является разбиением числа 5?

Какое из рекуррентных соотношений указанных ниже является линейным?

Установите соответствие между операцией над высказываниями и её определением:

1. Конъюнкция
2. Эквиваленция
3. Импликация
4. Дизъюнкция
5. Логическая операция, образующая сложное высказывание, истинное тогда и только тогда, когда истинны оба исходных высказывания
6. Логическая операция, образующая сложное высказывание, которое является истинным тогда, когда оба простых логических выражения имеют одинаковую истинность.
7. Логическая операция, которая двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда из истины следует ложь.
8. Логическая операция, образующая сложное высказывание, истинное в том случае, когда хотя бы одно из высказываний истинно

Элементарная конъюнкция называется …, если в неё каждая переменная входит не более одного раза, включая её вхождение и под знаком отрицания.

Элементарная дизъюнкция называется ____ относительно переменных x, y, z, ..., если в неё входит каждая из этих переменных не менее одного раза, включая и их вхождение под знаком отрицания.

Множество формул алгебры логики {f1,f2,…,fm} называется ..., если при всяком наборе значений переменных, входящих в эти формулы, по крайней мере одна из формул принимает значение 0.

Число различных булевых (логических) функций, зависящих от n переменных вычисляется по формуле:

Установите соответствие между видом графа и его определением.

1. Полный граф
2. Нулевой граф
3. Регулярный граф
4. Связный граф
5. граф, в котором проведены все возможные ребра.
6. граф, состоящий только из изолированных вершин, т.е. граф, не содержащий ни одного ребра.
7. связный граф, все вершины которого имеют одинаковую степень.
8. граф, между любыми вершинами которого существует путь.

Вставьте недостающие слова в определения в правильной последовательности. «Матрица … – это … матрица, в которой и число строк, и число столбцов равно n – числу … графа. Матрица … – это матрица размера n x m, где n – число вершин графа, m – число рёбер графа»

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

Согласно теореме Кэли, число деревьев, которые можно построить на 4-х нумерованных вершинах будет равно:

Для связного плоского графа, где V – количество вершин графа, E – количество ребер графа, F – количество граней графа, справедлива формула Эйлера:

Число ребер на дереве с 6-ю вершинами будет равно

Граф является … тогда и только тогда, когда степени всех его вершин четные.

Установите соответствие между условием задачи и методом её решения:

1. На тарелке лежат 5 груш и 4 яблока. Сколькими способами можно выбрать один фрукт?
2. В канцелярском магазине продают 5 видов шариковых ручек и 4 вида тетрадей. Сколькими способами можно выбрать набор из ручки и тетради (т.е. одну ручку и одну тетрадь)?
3. Каждый ученик класса побывал в театре или в кино. В театр сходили 22 человека. В кино были 15 человек. И в театре, и в кино были 7 человек. Сколько учеников в классе?
4. Сколькими способами можно развесить 5 цветных шаров на гирлянде?
5. Правило суммы
6. Правило произведения
7. Формула включений и исключений для двух множеств
8. Формула перестановки