Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

тематике Часть 1 Что такое высказываниеПредложение представляющее собой некое утверждение которому

Работа добавлена на сайт samzan.net: 2015-07-05

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 16.5.2024

Вопросы к экзамену по «Дискретной математике. Часть 1»

  1. Что такое высказывание?
    Предложение, представляющее собой некое утверждение, которому можно приписать значение «истина» или «ложь»
  2. Что обозначается с помощью пропозициональных переменных?
    Высказывания
  3. Что такое логическая операция?
    Операция над логическими величинами, результат – логическая величина
  4. Перечислите логические операции.
    Отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.
  5. Что обозначается с помощью пропозициональных связок?
    Логические операции
  6. Назовите синоним для термина пропозициональная форма.
    Формула
  7. Что такое истинностная таблица?
    Таблица, в которой для всех сочетаний истинностных значений входящих в формулу пропозициональных переменных указываются истинностные значения формулы
  8. Что такое тавтология?
    Тождественно истинная формула
  9. Что такое противоречие?
    Тождественно ложная формула
  10. Объясните термин логическое следствие.
    Формула В является логическим следствием формулы А, если формула «А импликация В» является тавтологией.
  11. Объясните термин логическая эквивалентность.
    Формулы А и В логически эквивалентны, если в является логическим следствием А и А является логическим следствием В
  12. Укажите старшинство логических операций.
    Отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.
  13. Сформулируйте законы коммутативности для высказываний.
    Формулы «А конъюнкция В» и «В конъюнкция А» - логически эквивалентны
    Формулы «А дизъюнкция В» и «В дизъюнкция А» - логически эквивалентны
  14. Сформулируйте законы ассоциативности для высказываний.
    Результат вычисления нескольких одноуровневых конъюнкций (дизъюнкций) не зависит от порядка их выполнения
  15. Сформулируйте законы дистрибутивности для высказываний.
    Конъюнкция (произведение) логической величины с дизъюнкцией (суммой) двух логических величин равна дизъюнкции (сумме) конъюнкций (произведений) этой величины с каждым из слагаемых.
    Дизъюнкция (сумма) логической величины с конъюнкцией (произведением) двух логических величин равна конъюнкции (произведению) дизъюнкций (сумм) этой величины с каждым из сомножителей.
  16. Сформулируйте законы де Моргана для высказываний.
    Отрицание конъюнкции есть дизъюнкция отрицаний
    Отрицание дизъюнкции есть конъюнкция отрицаний.
  17. Что такое дизъюнктивная (ДНФ) нормальная форма?
    Дизъюнкция элементарных конъюнкций
  18. Что такое конъюнктивная (КНФ) нормальная форма?
    Конъюнкция элементарных дизъюнкций
  19. Как построить ДНФ для заданной пропозициональной формы?
    Объединить дизъюнкцией все истинные элементарные конъюнкции, содержащие все пропозициональные переменные формулы
  20. Как построить КНФ для заданной пропозициональной формы?
    Объединить конъюнкцией все ложные элементарные дизъюнкции, содержащие все пропозициональные переменные формулы
  21. Что такое двойственные пропозициональные формы?
    Двойственной называется формула, полученная из формулы, содержащей лишь связки «отрицание», «конъюнкция» и «дизъюнкция», заменой конъюнкций на дизъюнкции и дизъюнкций на конъюнкции.
  22. Как можно получить КНФ, используя двойственность?
    Для двойственной формулы построить ДНФ и перейти к двойственной
  23. Что такое выполнимая формула в классическом исчислении высказываний?
    Формула, не являющаяся противоречием.
  24. Что нужно для определения формальной (аксиоматической) теории?
    Задать алфавит, множество осмысленных слов, множество аксиом и правила вывода
  25. Объясните термины алфавит, слово, формула.
    Алфавит – не более чем счетное множество символов, слово – конечные цепочки символов, формула – «осмысленное» слово
  26. Объясните термины аксиома и правило вывода
    Аксиомы – выделенное подмножество формул, правила вывода – отношения, заданные на конечных наборах формул
  27. Что означает непосредственное следствие формулы из конечного набора формул?
    Если эта формула вместе с конечным набором формул обращает в истину одно из правил вывода
  28. Что называется выводом в теории?
    Цепочка формул, каждая из которых либо аксиома, либо непосредственно следует из набора предшествующих формул.
  29. Что такое теорема теории?
    Если существует вывод, заканчивающийся этой формулой
  30. Какая теория называется эффективно аксиоматизированной?
    Существует алгоритм определения, является ли данная формула аксиомой
  31. Какая теория называется разрешимой теорией?
    Существует алгоритм определения, является ли данная формула теоремой
  32. Что такое полнота теории.
    Всякое истинное утверждение доказуемо
  33. Что такое непротиворечивость теории.
    Не всякая формула есть теорема
  34. Что означает, что формула является следствием множества формул в теории?
    Существует цепочка формул, заканчивающаяся данной формулой, каждая из формул цепочки либо принадлежит данному множеству формул, либо является аксиомой, либо непосредственно следует из предыдущих формул.
  35. Сформулируйте правило вывода в классическом исчислении высказываний L.
    Если «А» и «А импликация В», то «В»
  36. Сформулируйте теорему дедукции для классического исчисления высказываний L.
    Если из множества формул Г и формулы А выводима формула В, то из Г выводима «А импликация В»
  37. Сформулируйте теорему о полноте для классического исчисления высказываний.
    Всякая тавтология есть теорема
  38. Что такое литерал?
    Формула, состоящая из одиночной пропозициональной переменной, возможно с отрицанием.
  39. Сформулируйте лемму о выводимости из литералов.
    Для произвольной строки таблицы истинности данной формулы формируем полный набор литералов, истинных в этой строке. Из этого набора литералов выводима сама формула (если она принимает в этой строке значение истина), либо ее отрицание (в противном случае)
  40. Дайте понятия предметных констант и предметных переменных в исчислении предикатов.
    Предметные константы – конкретные элементы множества интерпретации, предметные переменные – переменные с областью определения на множестве интерпретации.
  41. Что обозначают с помощью функциональных букв в исчислении предикатов?
    Функции на множестве интерпретации
  42. Что обозначают с помощью предикатных букв в исчислении предикатов?
    Предикаты на множестве интерпретации
  43. Что такое терм в исчислении предикатов?
    Предметные константы и переменные – термы, функциональная буква с термами в качестве аргументов – тоже терм
  44. Дайте определение формулы в исчислении предикатов.
    Предикатная буква с термами в качестве аргументов – формула, формулы, связанные логическими операциями – тоже формулы.
  45. Как связаны между собой кванторы общности и существования?
    «Существует х, что А» означает «неверно, что для любого х не А»
  46. Что такое область действия квантора?
    Формула, непосредственно записанная после квантора
  47. Объясните понятия связного и свободного вхождения переменной в формулу.
    х – входит в формулу «связно», если х расположен непосредственно за квантором или находится в области действия квантора по х. Остальные вхождения свободны
  48. Что такое свободная переменная в формуле.
    Если существует её свободное вхождение
  49. Какая формула называется замкнутой?
    Нет свободных переменных
  50. Какой терм является свободным для заданной переменной в заданной формуле?
    Терм t свободен для переменной х в А, если никакое свободное вхождение х в А не попадает под действие никакого квантора ни по какой переменной, входящей в t.
  51. Что такое интерпретация в исчислении предикатов?
    Это множество. Каждой предметной переменной сопоставляется переменная на этом множестве, каждой предметной константе сопоставляется элемент этого множества, каждой функциональной букве – функция на этом множестве, каждой предикатной букве – отношение на этом множестве.
  52. Что такое модель на заданном множестве формул в исчислении предикатов?
    Это интерпретация, в которой формулы заданного множества истинны.
  53. Что такое логически общезначимая формула?
    Формула истинная во всех интерпретациях
  54. Что такое выполнимая формула в исчислении предикатов?
    Формула, истинная хотя бы в одной интерпретации каких-то значениях входящих в нее параметров.
  55. Перечислите правила вывода в исчислении предикатов.
    Modus ponens, generalization
  56. Какие предметные константы, функциональные и предикатные буквы используются в формальной арифметике?
    Константа «ноль», функции «следующий», «сумма», «произведение», предикат «равно»
  57. Сформулируйте теорему о полноте для исчисления предикатов.
    Логически общезначимая формула является теоремой исчисления предикатов.
  58. Дайте понятие вычислимости объекта.
    Объект вычислим, если он может быть получен в результате работы какого-нибудь алгоритма.
  59. Дайте понятие разрешимости объекта по отношению к заданному свойству.
    Если существует алгоритм, устанавливающий обладание объекта этим свойством
  60. Разрешима ли формула классического исчисления высказываний по отношению к свойству «быть теоремой»? Почему?
    Да. Можно проверить, является ли формула тавтологией.
  61. Является ли доказательство теоремы в классическом исчислении высказываний вычислимым? Почему?
    Да. Можно перебирать все доказательства как слова некоторого алфавита.
  62. Какое множество называется счетным?
    Множество, элементы которого можно перенумеровать (то есть, каждому элементу будет приписан хотя бы один порядковый номер).
  63. Что такое «хорошая» нумерация элементов множества?
    Каждому элементу множества приписан ровно один номер, причём, каждому номеру соответствует ровно один элемент.
  64. Докажите, что если есть какая-то нумерация элементов множества, то можно получить «хорошую».
    Перебирая номера существующей нумерации, последовательно нумеруем встречающиеся непомеченные элементы множества, помечая их.
  65. Докажите, что множество всех целых положительных чисел счетно.
    Число, которое соответствует элементу множества, можно считать его номером
  66. Докажите, что любое подмножество целых положительных чисел счетно.
    Число, которое соответствует элементу множества, можно считать его номером
  67. Докажите, что объединение двух счётных множеств счётно.
    Строим новую нумерацию, используя существующие нумерации так: первый элемент первого множества, первый элемент второго множества, второй элемент первого множества, второй элемент второго множества, третий…
  68. Докажите, что счётное множество счётных множеств счётно.
    Элементы каждого множества перенумерованы. Нумеруем 1 элемент 1 множества, затем 1 и2 элементы 1 и 2 множества, затем 1,2 и 3 элементы 1,2 и 3 множеств и т.д.
  69. Что содержит инструкция машины Тьюринга?
    Символ на ленте, состояние, действие, новое состояние
  70. Какие действия может выполнять машина Тьюринга?
    Сдвиг влево, сдвиг вправо, запись нового символа на ленте
  71. Сформулируйте тезис Чёрча о вычислимых функциях: ВФ=ВТ.
    Все вычислимые функции вычислимы по Тьюрингу
  72.  Докажите, что существуют невычислимые функции.
    Функций на множестве целых неотрицательных чисел несчетное число, машин Тьюринга, а следовательно и вычислимых функций, – счетное  число.
  73. Что такое частичная функция?
    Функция, определенная на некотором подмножестве множества целых неотрицательных чисел
  74. Является ли частичной всюду определённая функция?
    Да
  75. Что такое вычислимая функция?
    Существует алгоритм, который за конечное число шагов для аргумента из области определения выдает результат, для остальных аргументов результата не выдает.
  76. Дайте определение частично рекурсивной функции.
    Частичная функция, вычислимая какой-нибудь машиной Тьюринга
  77.  Дайте определение рекурсивной функции.
    Частично-рекурсивная, всюду определенная
  78. Является ли рекурсивная функция частично-рекурсивной?
    Да
  79. Сформулируйте тезис Чёрча о частично рекурсивных функциях: ВФ=ЧРФ.
    Множество вычислимых функций совпадает со множеством частично-рекурсивных функций
  80.  Что такое частичная характеристическая функция для множества?
    Функция с областью определения на данном множестве, возвращающая значение 0 на элементах этого множества
  81. Что такое характеристическая функция для множества?
    Всюду определенная функция, возвращающая 0 на элементах множества, 1 в противном случае
  82. Дайте определение рекурсивно перечислимого множества.
    Множество, частичная характеристическая функция которого частично-рекурсивна
  83. Дайте определение рекурсивного множества.
    Множество, характеристическая функция которого рекурсивна
  84. Является ли рекурсивное множество рекурсивно-перечислимым?
    Да
  85. Является ли рекурсивно-перечислимое множество рекурсивным?
    Нет. (Вспомните множество W).
  86. Является ли объединение двух рекурсивно перечислимых множеств рекурсивно-перечислимым?
    Да.
  87. Является ли объединение двух рекурсивных множеств рекурсивным?
    Да.
  88. Является ли разность двух рекурсивно-перечислимых множеств рекурсивно-перечислимым?
    Нет. (Вспомните множество W).
  89. Является ли разность двух рекурсивных множеств рекурсивным?
    Да.
  90. Доказать, что существует множество натуральных чисел, не являющееся рекурсивно перечислимым.
    Всего множеств – несчетное число, рекурсивно-перечислимых – счетное число.
  91. Дайте понятия алфавита и лексики языка
    Алфавит – не более чем счетное множество символов, лексика языка – множество осмысленных слов
  92. Дайте понятия синтаксиса и семантики языка
    Синтаксис – описание правильных предложений, семантика – смысл предложений
  93. Что такое метаязык?
    Язык для изучения другого языка
  94. Что такое транслятор?
    Программа, переписывающая текст с одного языка на другой с сохранением семантики
  95. Дайте понятие компиляции и интерпретации, как методов трансляции.
    Генерация кода при компиляции осуществляется после анализа всего текста, при интерпретации генерация кода и выполнение осуществляется в процессе чтения текста
  96. Этапы трансляции.
    Лексический анализ, синтаксический анализ, семантический анализ, генерация кода.
  97. Что такое бэкусовы нормальные формы (БНФ)?
    Средства описания синтаксиса
  98. Дайте определение порождающей грамматики.
    Автомат, генерирующий множество слов основного алфавита из стартового символа по правилам вывода
  99. Что такое непосредственная выводимость в порождающей грамматике?
    Слово непосредственно выводимо из другого слова, если оно получено однократным применением одной из продукций.
  100. Что такое выводимость в порождающей грамматике?
    Слово терминального алфавита выводимо, если существует цепочка непосредственно выводимых друг из друга слов, начинающаяся со стартового символа, заканчивающаяся данным словом.
  101. Что такое порожденный грамматикой язык?
    Совокупность порождаемых грамматикой слов
  102. Какие языки называются распознаваемыми и легко распознаваемыми?
    Существует алгоритм, определяющий принадлежность слова данной грамматике. Легко распознаваем, если количество шагов алгоритма зависит лишь от длины слова.
  103. Перечислите классы языков по Хомскому.
    0, 1, 2, 3
  104. Какие ограничения накладываются на продукции грамматик класса 0?
    Никаких
  105. Какие ограничения накладываются на продукции грамматик класса 1?
    Нетерминал «с контекстом» заменяется на слово объединенного алфавита «с контекстом»
  106. Какие ограничения накладываются на продукции грамматик класса 2?
    Нетерминал заменяется на слово объединенного алфафита
  107. Какие ограничения накладываются на продукции грамматик класса 3?
    Нетерминал заменяется на терминал, или на терминал-нетерминал.
  108. Какими автоматами распознаются языки класса 0?
    Машинами Тьюринга
  109. Что такое синтаксический анализ?
    Анализ правильности написания предложений.
  110. Какими автоматами распознают контекстно-свободные грамматики?
    Автоматами с магазинной памятью
  111. Что такое лексический анализ?
    Анализ слов текста на предмет принадлежности лексике языка
  112. Какими автоматами распознают регулярные грамматики?
    Конечными автоматами
  113. Что такое конечный автомат?
    Машина Тьюринга, действие – сдвиг вправо
  114. Какие автоматы называются детерминированными?
    Выбор очередной функции перехода определяется однозначно
  115. Что собой представляет дескрипторный текст в лексическом анализе?
    Последовательность «метасимволов»
  116. Что такое магазинный автомат?
    Машина Тьюринга с дополнительной лентой (стеком).



1. Тема Профессиональная бронхиальная астма Клиника
2.  2013г. Список билетов предлагаемых на дифференцируемый зачет по дисциплине МДК 01
3. Волшебное Закарпатье 1 день Сбор группы на ж-д вокзале г
4. Сущность формы движения капитала Международное движение капитала это движение финансовых потоков
5. Курсовая работа- Экскурсия-помощник развития памяти младших школьников
6. 10-30 2 10-4512-15 10
7. АТекст научной работы размещён без изображений и формул
8. Горное давление и его влияние на сечение горной выработки
9. Волгоградский государственный социальнопедагогический университет ФГБОУ ВПО ВГСПУ Факультет эк.
10. Строительные машины
11. Конкурентная борьба способствует эффективному использованию ограниченных ресурсов
12. Технология оказания медицинских услуг в объеме 36 часов с 20 г
13. При планировании маркетинга руководствуются разработкой долговременных целей политики и стратегии кот
14. Изучение мер процессуального принуждения в уголовном судопроизводстве
15. тематике физике но и были известными философами
16. вариант ответа Ответы запишите в бланки ответов
17. до 1991 г. входила в состав Союза ССР как Литовская Советская Социалистическая Республика
18. тематически применяются вербальные и невербальные методы воздействия на пациента и группу и совместно прини.
19. Производственная структура АПК
20. распирающие боли в животе

Материалы собраны группой SamZan и находятся в свободном доступе