|
|
Булевы функции. Теорема о существовании и единственности сднф
|
Скачать 26.98 Kb.
| Дата |
01.10.2016 |
| Размер |
26.98 Kb. |
|
-
Высказывания. Примеры высказываний. Формулы логики высказываний. Интерпретации. Выполнимые, невыполнимые формулы и тавтологии. Эквивалентные формулы. Законы логики высказываний и их применение (пример).
-
Булевы функции. Теорема о существовании и единственности СДНФ.
-
Булевы функции. Принцип двойственности. Теорема о существовании и единственности СКНФ.
-
Принцип двойственности. ДНФ и КНФ. Карты Карно (на примере). Применение булевых функций к упрощению контактных схем.
-
Суперпозиция (композиция) булевых функций (примеры). Замкнутые и полные классы (пример). Доказательство замкнутости классов T0 и T1. Теорема Поста (доказательство без лемм)
-
Самодвойственные функции. Проверка по таблице истинности на самодвойственность (на примере). Доказательство замкнутости класса самодвойственных функций. Лемма о наличии 0 и 1 в замыкании класса, содержащего отрицание и несамодвойственную функцию.
-
Монотонные функции. Пример монотонной функции существенно зависящей от трех переменных. Доказательство замкнутости класса монотонных функций. Лемма о наличии отрицания в замыкании класса, содержащего немонотонную функцию и константы.
-
Многочлены Жегалкина, общий вид многочлена Жегалкина от трех переменных. Построение многочлена Жегалкина для дизъюнкции. Теорема о существовании и единственности многочлена Жегалкина.
-
Линейные функции. Лемма о наличии конъюнкции и дизъюнкции в замыкании класса, содержащего нелинейную функцию, константы и отрицание.
-
Логическое следование. Пример. Теорема об альтернативных способах проверки логического следования.
-
Идея метода резолюций в логике высказываний. Пример полного семантического дерева для трех переменных. Опровергающие и выводящие узлы для набора дизъюнктов S. Замкнутое семантическое поддерево. Теорема Эрбрана.
-
Идея метода резолюций для логики высказываний. Теорема, обосновывающая метод резолюций.
-
Предикаты (2 определения). Кванторы. Свободные и связанные переменные. Замкнутые формулы. Примеры замкнутых и незамкнутых формул. Функциональные символы и термы. Примеры. Формула логики предикатов (логики первого порядка).
-
Интерпретации в логике предикатов. Выполнимые и невыполнимые формулы. Законы логики высказываний. Алгоритм приведения к предваренной нормальной форме (на примере).
-
Логическое следование в логике предикатов. Идея метода резолюций в логике предикатов. Алгоритм приведения к сколемовской нормальной форме на примере.
-
Идея метода резолюций в логике предикатов. Подстановки и унификаторы. Правила резолюций и склейки на примере.
-
Свободный моноид. Слова: длина слова, префиксы, суффиксы, подслова. Языки, примеры формальных языков. Операции над языками. Регулярные выражения. Пример использования регулярного выражения «из жизни». Построение регулярного выражения по автомату (на примере).
-
Детерминированный конечный автомат. Способы его задания: управляющая таблица, ориентированный граф. Продолжение функции перехода автомата на свободный моноид. Язык, распознаваемый автоматом. Рациональные языки.
-
Доказательство замкнутости класса рациональных языков относительно дополнения и пересечения.
-
Недетерминированный конечный автомат (эпсилон НКА). Язык, распознаваемый НКА. Теорема Клини (о том, что любое регулярный язык распознается некоторым НКА).
-
Эпсилон-замыкания в НКА. Теорема Рабина-Скотта (о существовании ДКА, распознающего тот же язык, что данный НКА): идея доказательства и пример. Формулировка теоремы Клини о связях между регулярными и рациональными языками.
-
Минимизация ДКА, идея и пример.
-
Нерациональные языки: лемма о накачке. Пример ее применения.
-
Порождающие грамматики, контекстно-свободные грамматики (КС), вывод в КС грамматиках, дерево вывода. Языки, порождаемые грамматиками, КС языки. Пример грамматики для языка арифметических выражений. Неоднозначные грамматики.
-
Замкнутость класса КС языков относительно сложения, умножения и итерации Клини. Пример не контекстно-свободного языка.
-
Автоматы с магазинной памятью, принципы его функционирования. Два типа распознаваемости слова МП-автоматом. Пример автомата с одним состоянием, заканчивающего работу при пустом стеке (взять слово и показать, как автомат работает).
Основная теорема об МП-автоматах и КС языках.
|
|
|