Дискретна математика - форум студентів МТІ
1 Модуль 25 з 25
2 модуль 25 з 25
3 модуль 25 з 25
4 модуль 25 з 25
МОДУЛЬ 1. БЕЗЛІЧІ І ОТНОШЕНІЯ25 з 25
Як називається неорграф без циклів?
ациклический
Яке твердження є вірним?
бінарне відношення R називається відношенням еквівалентності, якщо воно рефлексивно, симетрично і транзитивній
Яке твердження є неправильним?
кінцеве безліч є рівнопотужності будь-якого свого власного подмножеству
Як називається замкнутий обхід симетричного мультиграфом по всіх вершин по одному разу?
гаміл'тоновим циклом
Як називається бінарне відношення, рефлексивне, антисиметричною і транзитивне?
частковий порядок
Яке твердження не є вірним?
елементи множини не можуть самі бути множинами
Що таке граф?
вершини і дуги
Що таке булеан?
сукупність всіх підмножин множини А
Що розуміється під безліччю?
сукупність деяких об'єктів
Як називається безліч непустих підмножин множини, якщо кожен елемент даної множини належить в точності одному з його підмножин, кожне з яких не є порожнім?
розбиттям безлічі
Яка безліч А називається підмножиною множини В?
якщо всі елементи множини А належать В
Яка безліч називають рахунковим?
будь-яка множина, рівносильне безлічі всіх натуральних чисел
Як називається бінарне відношення, яке тільки рефлексивно і транзитивно?
ставлення предпорядка
Яка безліч називається універсальним або універсумом?
безліч, що містить всі елементи, що знаходяться в розгляді
Яке твердження є неправильним?
в мережевому графіку є цикли
Як називається симетричний граф, якщо будь-які дві його вершини з'єднані між собою ребром?
повний граф
Який граф називається зв'язковим?
якщо будь-які дві вершини графа з'єднані хоча б одним шляхом
Як називаються відрізняються один від одного хоча б одним елементом вибірки довжини k, складені з n-елементного безлічі?
поєднання без повторень з n елементів по k
Яка властивість рахункових множин є невірним?
будь-яка підмножина рахункового безлічі нескінченно
Які безлічі А і В називаються рівними або збігаються?
якщо вони складаються з одних і тих же елементів
Що розуміється під рішенням задачі оптимізації «в слабкому сенсі»?
знаходження єдиного довільного елемента
Що таке завдання перерахування в комбінаториці?
якщо необхідно виділити всі елементи безлічі, що задовольняють заданим властивостям
Як називається послідовність дуг графа, таких, що кінець будь-якої дуги крім останньої збігається з початком наступної дуги?
шляхом в графі
Що називається рacкраской (вершин) графа G?
таке завдання квітів вершин G, що якщо [а, b] ребро, то вершини а і b мають різні кольори
Як називається замкнутий обхід мультиграфом по всіх ребрах по одному разу?
ейлеровим циклом
МОДУЛЬ 2. АЛГЕБРА І ТОПОЛОГІЯ25 з 25
Що являє собою тривіальний фільтр безлічі X?
сімейство F підмножин X, що складається лише з самого безлічі X
Як називається півгрупа з одиницею?
моноїд
Який фільтр буде мажоріровать будь-який фільтр околиць точки. якщо X - топологічний простір?
тривіальний фільтр
Як називається нейтральний елемент мультиплікативного группоід?
одиниця
Як називається сукупність предикатних і функціональних символів із зазначенням їх місцевості?
сигнатура
Як називається формула, що є об'єднанням, до якого входять по одному разу все безлічі (зі знаками доповнення або без доповнень) на даному универсуме?
конституента нуля
Що називається алгеброю системами?
безлічі, на яких крім операцій задані відносини
В якому випадку ґратчаста топологія є дискретною?
коли розбиття складається тільки з одноточкових підмножин заданої множини
Який фільтр фільтрує безліч X аж до одноточечного безлічі, що складається з однієї даної точки?
ультрафільтр
Яке твердження є неправильним?
кожне безліч, за винятком універсального, може бути задано об'єднанням констітуєнт одиниці
В якому випадку ґратчаста топологія є тривіальної?
коли розбиття складається тільки з однієї частини заданої множини
Що таке повна система булевих функцій?
набір булевих функцій, якщо будь-яка булева функція виражається через них за допомогою операції суперпозиції в кінцевому числі раз
Який клас булевих функцій називається замкнутим?
якщо будь-яка суперпозиція функцій даного класу буде функцією з цього класу
Як називається нейтральний елемент адитивного группоід?
нуль
Яке твердження є неправильним?
будь-яка топологія мажорірует дискретну топологію
Як називається 0-місний функціональний символ?
константа
Яке твердження вірне?
циклічна група завжди абелева
Що не є умовою, виконання якого говорить про те, що сімейство τ задає топологію в безлічі X? (X - довільна множина - деяке сімейство його підмножин, безліч індексів I може мати довільну потужність)
перетин кінцевого числа множин з τ не належить τ
Як називається кільце, в якому все відмінні від нуля елементи складають групу по множенню?
тіло
Як називається формула алгебри множин, що є перетин, в яке входять по одному разу все безлічі (зі знаками доповнення або без доповнень) на даному универсуме?
конституента одиниці
Які елементи а і b частково впорядкованої множини з нулем 0 і одиницею 1 називаються додатковими друг для друга?
якщо їх перетин одно нульового елементу 0, а об'єднання дає одиничний елемент 1
Яка сигнатура називається функціональної?
яка не містить предикатних (функціональних) символів
Що називається потужністю алгебри?
потужність носія системи
Що таке терм?
функціональне вираз, складене за допомогою сигнатурних функціональних символів
Скільки буде всього різних булевих функцій однієї змінної?
чотири
МОДУЛЬ 3. АЛГЕБРА ЛОГІКІ25 з 25
Який вислів істинно?
ніяка змінна не може бути одночасно вільної та зв'язаної
Яка діз'юнктівная нормальна форма (ДНФ) називається досконалою?
диз'юнкція деяких констітуєнт одиниці, серед яких немає однакових
Яка формула аксіоматичної теорії називається теоремою?
формула, яка виводиться тільки з аксіом, не використовуючи ніяких гіпотез
В якому випадку формула називається здійсненним?
якщо існує такий набір значень змінних, при якому формула приймає значення 1
Які формули називаються рівносильними в даній інтерпретації I = <М, Ф>?
формули f і g, якщо формули виражають в даній інтерпретації один і той же предикат
Що називається довжиною формули логіки предикатів?
загальне число входять до неї символів предикатів (атомарних формул), логічних символів і символів кванторів
Яка формула логіки предикатів називається нормальною?
наведена формула, якщо вона містить усі символи кванторів попереду або кванторів зовсім немає
Які два диз'юнкт називаються резольвентних парою?
якщо існує така літера, яка бере участь в одному диз'юнкт як позитивна, а в іншому - як негативна
Який вислів істинно?
будь-яка булева функція, яка не є константою 0, представимо у вигляді скороченої ДНФ
Що називається функцією алгебри логіки (ФАЛ) від п змінних?
функція, яка довільному набору нулів та одиниць ставить у відповідність значення
Що називається елементарним твором?
Кон'юнктів, в який будь-яка змінна входить не більше одного разу
Що таке предикат?
оповідної пропозицію з параметрами
Чим повністю характеризуються формули алгебри логіки семантично?
таблицями істинності
Який диз'юнкт називається хорновскім?
диз'юнкт, у якого серед літер не більше однієї позитивної
Які формули називаються рівносильними на множині М?
формули f і g, якщо вони рівносильні у всіх інтерпретаціях, заданих на множині М
Яке твердження є неправильним?
формула φ опровержімие тоді і тільки тоді, коли вона є тотожно істинною
Як називається кон'юнкція літер?
кон'юнктів
Яка властивість алгоритму означає, що описуваний їм процес і сам алгоритм можуть бути розбиті на окремі елементарні етапи, можливість виконання яких на ЕОМ у користувача не викликає сумнівів?
дискретність
В якому випадку кажуть, що формула φ являє функцію f?
якщо булева функція f і формула φ мають одну і ту ж таблицю істинності
Що називається диз'юнктивній нормальною формою (ДНФ)?
диз'юнкція кон'юнктів
Яка властивість алгоритму означає, що він повинен призводити до отримання результату за кінцеве число кроків?
результативність
Що називається висловленням?
оповідної пропозицію, про який в даній ситуації можна сказати, що воно істинно або хибно, але не те й інше одночасно
Який вислів є невірним?
проблема розпізнавання застосовних машин Тьюринга алгоритмічно розв'язна
Яке твердження є неправильним?
в аксіоматичної теорії можна одночасно мати два докази деякої теореми і її заперечення
Який вислів є помилковим?
в інерціальній системі відліку прискорення, яке отримує матеріальна точка, обернено пропорційно рівнодіючої всіх доданих до неї сил і прямо пропорційно її масі
МОДУЛЬ 4. КІНЦЕВІ АВТОМАТИ І РЕГУЛЯРНІ ЯЗИКІ25 з 25
Як називається логічна операція, відповідна союзу «тоді і тільки тоді, коли»?
еквівалентність
Що називається кон'юнкція?
бінарна логічна операція, що сполучає дві довічних змінних а і b, що належать безлічі, в таку Переключательная функцію з, яка дорівнює 1 (істинна) тільки тоді, коли рівні 1 (істинні) обидві змінних
Що називають словом або ланцюжком в алфавіті V?
довільний кортеж з безлічі (k-й декартовой ступеня алфавіту V) для різних k = 0, 1, 2.
В якому випадку код є виконуючим всі помилки?
в разі, коли в переданому слові є не більше k помилок, тоді і тільки тоді, коли найменша відстань між кодовими словами
Кожне правило який граматики має вигляд: в правій частині правила може містити не більше одного входження нетермінала?
лінійної граматики
В якому випадку код є виявляє?
в разі, коли в переданому слові є не більше ніж k помилок, тоді і тільки тоді, коли найменша відстань між кодовими словами
Як називається зафіксований порядок змінних, кожна з яких має свою вагу?
базою функції
Як називається логічна операція, відповідна союзу «або» в неразделітельном сенсі?
диз'юнкція
Що називається еквіваленціі?
логічна операція, що сполучає дві змінних в таку Переключательная функцію, яка істинна тоді, коли обидві утворюють її змінних одночасно істинними або одночасно хибними
Який такт в функціонуванні автоматів називають нестійким?
якщо чергова зміна стану автомата відбувається тільки за рахунок зміни внутрішнього стану - елементів пам'яті
Яке твердження є вірним?
автомати Мура менш швидкодіючі, ніж автомати Мілі
Як називається логічна операція, відповідна союзу «якщо. то »?
импликацией
Кожне правило який граматики має вигляд: ліва частина кожного правила виведення є нетермінал, а права - довільна (може бути і порожня) ланцюжок в об'єднаному алфавіті?
контекстно-вільної граматики
Як називається логічна операція, відповідна частці «не», словосполучення «невірно, що»?
інверсією
Які символи ви бачите називається груповим?
якщо безліч всіх кодових слів утворює групу
При якому способі перемикальна функція задається таблицею її значень - таблицею істинності - одновимірної або двомірної (картою Карно), де вказуються набори змінних і відповідні значення функції?
при матричному способі
При якому способі перемикальна функція задається за допомогою відповідної позначки вершин n-мірного куба, який по суті є гратами Хассе, що представляє собою частково впорядкована множина наборів (кожна вершина - точка n-мірного простору)?
при геометричному способі
Що називається диз'юнкція?
бінарна логічна операція, що сполучає дві змінні а і b в таку Переключательная функцію c, яка дорівнює 0 (помилкова) тільки тоді, коли помилкові обидві змінні (рівні 0)
Яке твердження є вірним?
при завданні автомата орієнтованим графом (Орграф) його вершини зіставляють з внутрішніми станами
Як називаються кінцеві автомати, які мають більше, ніж одне внутрішній стан?
послідовних кінцевими автоматами
Як називають об'єднання всіх ступенів мови L?
итерацией
Як називається автомат, якщо з будь-якого його стану можна досягти будь-яке інше стан?
сильно пов'язаним
Для якого основного класу граматик характерно наступне: на правила висновку не накладається ніяких додаткових обмежень?
для граматики типу 0
Яку подцепочку х ланцюжка у називають початком (або префіксом) ланцюжка у?
якщо у = xz для деякої непорожній ланцюжка z
Що називається импликацией?
логічна операція, що сполучає дві змінних а і b в таку Переключательная функцію c, яка дорівнює 0 (помилкова) тільки тоді, коли а істинно, а b помилково