Какое свойство счетных множеств является неверным

Ответы на все модули по предмету дискретная математика, для итогового тестирования.

Ответы на модуль 1 (МНОЖЕСТВА И ОТНОШЕНИЯ) по предмету дискретная математика.

1) Как называется неорграф без циклов? ациклический.

2) Какое утверждение является верным? бинарное отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

3) Какое утверждение является неверным? конечное множество является равномощным любому своему собственному подмножеству.

4) Как называется замкнутый обход симметричного мультиграфа по всем вершинам по одному разу? гамилътоновым циклом.

5) Как называется бинарное отношение, рефлексивное, антисимметричное и транзитивное? квазипорядок.

6) Какое утверждение не является верным? элементы множества не могут сами являться множествами.

7) Что такое граф? вершины и дуги.

8) Что такое булеан? совокупность всех подмножеств множества А.

9) Что понимается под множеством? совокупность некоторых объектов.

10) Как называется множество непустых подмножеств множества, если каждый элемент данного множества принадлежит в точности одному из его подмножеств, каждое из которых не является пустым? разбиением множества.

11) Какое множество А называется подмножеством множества В? если все элементы множества А принадлежат В.

12) Какое множество называют счетным? любое множество, равномощное множеству всех натуральных чисел.

13) Как называется бинарное отношение, которое только рефлексивно и транзитивно? отношение предпорядка.

14) Какое множество называется универсальным или универсумом? множество, содержащее все элементы, находящиеся в рассмотрении.

15) Какое утверждение является неверным? в сетевом графике имеются циклы.

16) Как называется симметричный граф, если любые две его вершины соединены между собой ребром? полный граф.

17) Какой граф называется связным? если любые две вершины графа соединены хотя бы одним путем.

18) Как называются отличающиеся друг от друга хотя бы одним элементом выборки длины k, составленные из n-элементного множества? сочетания без повторений из n элементов по k.

19) Какое свойство счетных множеств является неверным? любое подмножество счетного множества бесконечно.

20) Какие множества А и В называются равными или совпадающими? если они состоят из одних и тех же элементов.

21) Что понимается под решением задачи оптимизации «в слабом смысле»? нахождение единственного произвольного элемента.

22) Что такое задача перечисления в комбинаторике? если необходимо выделить все элементы множества, удовлетворяющие заданным свойствам.

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

24) Что называется рacкраской (вершин) графа G? такое задание цветов вершинам G, что если [а, b] ребро, то вершины а и b имеют различные цвета.

25) Как называется замкнутый обход мультиграфа по всем ребрам по одному разу? эйлеровым циклом.

Ответы на модуль 2 (АЛГЕБРА И ТОПОЛОГИЯ) по предмету дискретная математика.

1) Что представляет собой тривиальный фильтр множества X? семейство F подмножеств X, состоящее лишь из самого множества X.

2) Как называется полугруппа с единицей? моноид.

3) Какой фильтр будет мажорировать любой фильтр окрестностей точки , если X — топологическое пространство? тривиальный фильтр.

4) Как называется нейтральный элемент мультипликативного группоида? единица.

5) Как называется совокупность предикатных и функциональных символов с указанием их местности? сигнатура.

6) Как называется формула, представляющая собой объединение, в которое входят по одному разу все множества (со знаками дополнения или без дополнений) на данном универсуме? конституента нуля.

7) Что называется алгебраическими системами? множества, на которых кроме операций заданы отношения.

8) В каком случае решетчатая топология является дискретной? когда разбиение состоит только из одноточечных подмножеств заданного множества.

9) Какой фильтр фильтрует множество X вплоть до одноточечного множества, состоящего из одной данной точки? ультрафильтр.

10) Какое утверждение является неверным? каждое множество, за исключением универсального, может быть задано объединением конституент единицы.

11) В каком случае решетчатая топология является тривиальной? когда разбиение состоит только из одной части заданного множества.

12) Что такое полная система булевых функций? набор булевых функций, если любая булева функция выражается через них при помощи операции суперпозиции в конечном числе раз.

13) Какой класс булевых функций называется замкнутым? если всякая суперпозиция функций данного класса будет функцией из этого класса.

14) Как называется нейтральный элемент аддитивного группоида? нуль.

15) Какое утверждение является неверным? любая топология мажорирует дискретную топологию.

16) Как называется 0-местный функциональный символ? константа.

17) Какое утверждение верно? циклическая группа всегда абелева.

18) Что не является условием, выполнение которого говорит о том, что семейство τ задает топологию во множестве X? (X — произвольное множество  —  некоторое семейство его подмножеств, множество индексов I может иметь произвольную мощность): пересечение конечного числа множеств из τ не принадлежит τ.

19) Как называется кольцо, в котором все отличные от нуля элементы составляют группу по умножению? тело.

20) Как называется формула алгебры множеств, представляющая собой пересечение, в которое входят по одному разу все множества (со знаками дополнения или без дополнений) на данном универсуме? конституента единицы.

21) Какие элементы а и b частично упорядоченного множества с нулем 0 и единицей 1 называются дополнительными друг для друга? если их пересечение равно нулевому элементу 0, а объединение дает единичный элемент 1.

22) Какая сигнатура называется функциональной? не содержащая предикатных (функциональных) символов.

23) Что называется мощностью алгебраической системы? мощность носителя системы.

24) Что такое терм? функциональное выражение, составленное с помощью сигнатурных функциональных символов.

25) Сколько будет всего разных булевых функций одной переменной? четыре.

Ответы на модуль 3 (АЛГЕБРА ЛОГИКИ) по предмету дискретная математика.

1) Какое высказывание истинно? никакая переменная не может быть одновременно свободной и связанной.

2) Какая дизъюнктивная нормальная форма (ДНФ) называется совершенной? дизъюнкция некоторых конституент единицы, среди которых нет одинаковых.

3) Какая формула аксиоматической теории называется теоремой? формула, которая выводится только из аксиом, не используя никаких гипотез.

4) В каком случае формула  называется выполнимой? если существует такой набор значений переменных, при котором формула принимает значение 1.

5) Какие формулы называются равносильными в данной интерпретации I = 〈М, Ф〉? формулы f и g, если формулы выражают в данной интерпретации один и тот же предикат.

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

7) Какая формула логики предикатов называется нормальной? приведенная формула, если она содержит все символы кванторов впереди или кванторов вовсе нет.

8) Какие два дизъюнкта называются резольвентной парой? если существует такая литера, которая участвует в одном дизъюнкте как положительная, а в другом — как отрицательная.

9) Какое высказывание истинно? любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ.

10) Что называется функцией алгебры логики (ФАЛ) от п переменных ? функция, которая произвольному набору  нулей и единиц ставит в соответствие значение .

11) Что называется элементарным произведением? конъюнкт, в который любая переменная входит не более одного раза.

12) Что такое предикат? повествовательное предложение с параметрами.

13) Чем полностью характеризуются формулы алгебры логики семантически? таблицами истинности.

14) Какой дизъюнкт называется хорновским? дизъюнкт, у которого среди литер не более одной положительной.

15) Какие формулы называются равносильными на множестве М? формулы f и g, если они равносильны во всех интерпретациях, заданных на множестве М.

16) Какое утверждение является неверным? формула φ опровержима тогда и только тогда, когда она является тождественно истинной.

17) Как называется конъюнкция литер? конъюнктом.

18) Какое свойство алгоритма означает, что описываемый им процесс и сам алгоритм могут быть разбиты на отдельные элементарные этапы, возможность выполнения которых на ЭВМ у пользователя не вызывает сомнений? дискретность.

19) В каком случае говорят, что формула φ представляет функцию f? если булева функция f и формула φ имеют одну и ту же таблицу истинности.

20) Что называется дизъюнктивной нормальной формой (ДНФ)? дизъюнкция конъюнктов.

21) Какое свойство алгоритма означает, что он должен приводить к получению результата за конечное число шагов? результативность.

22) Что называется высказыванием? повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно.

23) Какое высказывание является неверным? проблема распознавания применимых машин Тьюринга алгоритмически разрешима.

24) Какое утверждение является неверным? в аксиоматической теории можно одновременно иметь два доказательства некоторой теоремы и ее отрицания.

25) Какое высказывание является ложным? тела действуют друг на друга с силами, имеющими одинаковую природу, направленными вдоль одной и той же прямой, равными по модулю и противоположными по направлению.

Ответы на модуль 4 (КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ) по предмету дискретная математика.

1) Как называется логическая операция, соответствующая союзу «тогда и только тогда, когда»? эквивалентностью.

2) Что называется конъюнкцией? бинарная логическая операция, соединяющая две двоичных переменных а и b, принадлежащих множеству {0, 1}, в такую переключательную функцию с, которая равна 1 (истинна) только тогда, когда равны 1 (истинны) обе переменных.

3) Что называют словом или цепочкой в алфавите V? произвольный кортеж из множества  (k-й декартовой степени алфавита V) для различных k = 0, 1, 2,…

4) В каком случае код является исправляющим все ошибки? в случае, когда в передаваемом слове имеется не более k ошибок, тогда и только тогда, когда наименьшее расстояние между кодовыми словами .

5) Каждое правило какой грамматики имеет вид: в правой части правила может содержаться не более одного вхождения нетерминала? линейной грамматики.

6) В каком случае код является обнаруживающим? в случае, когда в передаваемом слове имеется не более чем k ошибок, тогда и только тогда, когда наименьшее расстояние между кодовыми словами .

7) Как называется зафиксированный порядок переменных, каждая из которых имеет свой вес? базой функции.

8) Как называется логическая операция, соответствующая союзу «или» в неразделительном смысле? дизъюнкцией.

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

10) Какой такт в функционировании автоматов называют неустойчивым? если очередное изменение состояния автомата происходит только за счет изменения внутреннего состояния — элементов памяти.

11) Какое утверждение является верным? автоматы Мура менее быстродействующие, чем автоматы Мили.

12) Как называется логическая операция, соответствующая союзу «если, … то»? импликацией.

13) Каждое правило какой грамматики имеет вид: левая часть каждого правила вывода есть нетерминал, а правая — произвольная (может быть и пустая) цепочка в объединенном алфавите? контекстно-свободной грамматики.

14) Как называется логическая операция, соответствующая частице «не», словосочетанию «неверно, что»? инверсией.

15) Какой код называется групповым? если множество всех кодовых слов образует группу.

16) При каком способе переключательная функция  задается таблицей ее значений — таблицей истинности — одномерной или двухмерной (картой Карно), где указываются наборы переменных и соответствующие значения функции? при матричном способе.

17) При каком способе переключательная функция  задается с помощью соответствующей отметки вершин n-мерного куба, который по сути является решеткой Хассэ, представляющей собой частично упорядоченное множество наборов (каждая вершина — точка n-мерного пространства)? при геометрическом способе.

18) Что называется дизъюнкцией? бинарная логическая операция, соединяющая две переменные а и b в такую переключательную функцию c, которая равна 0 (ложна) только тогда, когда ложны обе переменные (равны 0).

19) Какое утверждение является верным? при задании автомата ориентированным графом (орграфом) его вершины сопоставляют с внутренними состояниями.

20) Как называются конечные автоматы, имеющие больше, чем одно внутреннее состояние? последовательностными конечными автоматами.

21) Как называют объединение всех степеней языка L? итерацией.

22) Как называется автомат, если из любого его состояния достижимо любое другое состояние? сильно связанным.

23) Для какого основного класса грамматик характерно следующее: на правила вывода не накладывается никаких дополнительных ограничений? для грамматики типа 0.

24) Какую подцепочку х цепочки у называют началом (или префиксом) цепочки у? если у = xz для некоторой непустой цепочки z.

25) Что называется импликацией? логическая операция, соединяющая две переменных а и b в такую переключательную функцию c, которая равна 0 (ложна) только тогда, когда а истинно, а b ложно.