Булевы функции. Теорема о существовании и единственности сднф



Скачать 16.53 Kb.
Дата05.04.2017
Размер16.53 Kb.
Просмотров215
Скачиваний1

  1. Высказывания. Примеры высказываний. Формулы логики высказываний. Интерпретации. Выполнимые, невыполнимые формулы и тавтологии. Эквивалентные формулы. Законы логики высказываний и их применение (пример).

  2. Булевы функции. Теорема о существовании и единственности СДНФ.

  3. Булевы функции. Принцип двойственности. Теорема о существовании и единственности СКНФ.

  4. Принцип двойственности. ДНФ и КНФ. Карты Карно (на примере). Применение булевых функций к упрощению контактных схем.

  5. Суперпозиция (композиция) булевых функций (примеры). Замкнутые и полные классы (пример). Доказательство замкнутости классов T0 и T1. Теорема Поста (доказательство без лемм)

  6. Самодвойственные функции. Проверка по таблице истинности на самодвойственность (на примере). Доказательство замкнутости класса самодвойственных функций. Лемма о наличии 0 и 1 в замыкании класса, содержащего отрицание и несамодвойственную функцию.

  7. Монотонные функции. Пример монотонной функции существенно зависящей от трех переменных. Доказательство замкнутости класса монотонных функций. Лемма о наличии отрицания в замыкании класса, содержащего немонотонную функцию и константы.

  8. Многочлены Жегалкина, общий вид многочлена Жегалкина от трех переменных. Построение многочлена Жегалкина для дизъюнкции. Теорема о существовании и единственности многочлена Жегалкина.

  9. Линейные функции. Лемма о наличии конъюнкции и дизъюнкции в замыкании класса, содержащего нелинейную функцию, константы и отрицание.

  10. Логическое следование. Пример. Теорема об альтернативных способах проверки логического следования.

  11. Идея метода резолюций в логике высказываний. Пример полного семантического дерева для трех переменных. Опровергающие и выводящие узлы для набора дизъюнктов S. Замкнутое семантическое поддерево. Теорема Эрбрана.

  12. Идея метода резолюций для логики высказываний. Теорема, обосновывающая метод резолюций.

  13. Предикаты (2 определения). Кванторы. Свободные и связанные переменные. Замкнутые формулы. Примеры замкнутых и незамкнутых формул. Функциональные символы и термы. Примеры. Формула логики предикатов (логики первого порядка).

  14. Интерпретации в логике предикатов. Выполнимые и невыполнимые формулы. Законы логики высказываний. Алгоритм приведения к предваренной нормальной форме (на примере).

  15. Логическое следование в логике предикатов. Идея метода резолюций в логике предикатов. Алгоритм приведения к сколемовской нормальной форме на примере.

  16. Идея метода резолюций в логике предикатов. Подстановки и унификаторы. Правила резолюций и склейки на примере.

  17. Свободный моноид. Слова: длина слова, префиксы, суффиксы, подслова. Языки, примеры формальных языков. Операции над языками. Регулярные выражения. Пример использования регулярного выражения «из жизни». Построение регулярного выражения по автомату (на примере).

  18. Детерминированный конечный автомат. Способы его задания: управляющая таблица, ориентированный граф. Продолжение функции перехода автомата на свободный моноид. Язык, распознаваемый автоматом. Рациональные языки.

  19. Доказательство замкнутости класса рациональных языков относительно дополнения и пересечения.

  20. Недетерминированный конечный автомат (эпсилон НКА). Язык, распознаваемый НКА. Теорема Клини (о том, что любое регулярный язык распознается некоторым НКА).

  21. Эпсилон-замыкания в НКА. Теорема Рабина-Скотта (о существовании ДКА, распознающего тот же язык, что данный НКА): идея доказательства и пример. Формулировка теоремы Клини о связях между регулярными и рациональными языками.

  22. Минимизация ДКА, идея и пример.

  23. Нерациональные языки: лемма о накачке. Пример ее применения.

  24. Порождающие грамматики, контекстно-свободные грамматики (КС), вывод в КС грамматиках, дерево вывода. Языки, порождаемые грамматиками, КС языки. Пример грамматики для языка арифметических выражений. Неоднозначные грамматики.

  25. Замкнутость класса КС языков относительно сложения, умножения и итерации Клини. Пример не контекстно-свободного языка.

  26. Автоматы с магазинной памятью, принципы его функционирования. Два типа распознаваемости слова МП-автоматом. Пример автомата с одним состоянием, заканчивающего работу при пустом стеке (взять слово и показать, как автомат работает).

Основная теорема об МП-автоматах и КС языках.

Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал