1. Определение алгебры и подалгебры. Определение алгебры логики. Выписать таблицу с функциями алгебры логики
 Скачать 1.82 Mb.
|
|
1.Определение алгебры и подалгебры. Определение алгебры логики. Выписать таблицу с функциями алгебры логики. Алгебра логики - непустое множество A с двумя бинарными операциями ( конъюнкция ), ( дизъюнкция), унарной операцией ( отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 Подалгебра — подмножество алгебры над кольцом (алгебраической системы), замкнутое относительно всех операций этой алгебры, и само являющееся алгеброй. Другими словами, если результат бинарной операции над множеством А, не выходит за пределы этого множества. 2. Соответствия в теории множеств. Функциональное, сюръективное, взаимно- однозначное соответствие. Область определения и область значения соответствия. Функциональное соответствие – соответствие, при котором любому элементу множества соответствует единственный элемент множества Сюръективное соответствие – соответствие, при котором каждому элементу множества соответствует хотя бы один прообраз во множестве Взаимнооднозначное соответствие - соответствие, при котором любому элементу множества соответствует единственный элемент множества , и наоборот. Можно сказать также, что соответствие является взаимнооднозначным, если оно является полностью определѐнным, сюръективным, функциональным, и при этом каждый элемент множества имеет единственный прообраз. 3. Определения булевой алгебры, подалгебры. Выписать свойства булевых операций (ассоциативность и т.д.). Булева алгебра - непустое множество A с двумя бинарными операциями ( конъюнкция ), ( дизъюнкция), унарной операцией ( отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 Подалгебра — подмножество алгебры над кольцом (алгебраической системы), замкнутое относительно всех операций этой алгебры, и само являющееся алгеброй. Другими словами, если результат бинарной операции над множеством А, не выходит за пределы этого множества. 4. Определение фиктивных и существенных переменных . 5. Определение композиции, суперпозиции. Определение глубины формулы. Суперпозицией функций f1,…,fm называется функция f, полученная с помощью подстановок этих функций друг в друга, а формулой называется выражение, описывающее эту суперпозиции Композиция функций ( суперпозиция функций ) — это применение одной функции к результату другой. 6. Определение двойственности и самодвойственности функций, принцип двойственности, табличное определение двойственности. Функция двойственная сама себе называется самодвойственной. Таблица для двойственности функции при фиксированном порядке наборов получается из таблицы для функции заменой 0 на 1, 1 на 0 и переворачиванием столбца. 7. Исчисление высказываний. Алфавит исчисления высказываний, определение формул, общезначимость, противоречивость, логическое следствие. 8. Построение СДНФ для функции, заданной таблицей. 9. Построение СКНФ для функции, заданной таблицей. 10. Метод резолюций для исчисления высказываний. 11 . Определение минимальной, кратчайшей и неизбыточной ДНФ. 12. Полином Жегалкина. Определение в общем виде. Частные случаи для 2 и 3 переменных. На примере для 2 переменных показать переход от любой логической функции к ПЖ. Полином Жегалкина — многочлен над кольцом , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берѐтся конъюнкция, а в качестве сложения — исключающее или. Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина. Полином Жегалкина представляет собой сумму по модулю два произведений неинвертированных переменных, а также (если необходимо) константы 1. Формально полином Жегалкина можно представить в виде 13 . Класс функций T0. Определение и доказательство замкнутости. 14 . Класс функций T1. Определение и доказательство замкнутости. 15 . Теорема о функциональной полноте (без доказательства). 2.1. СДНФ: Определение ЭК, ОЭК, ДНФ, СДНФ. Теорема о разложении функций по переменным с доказательством. 2 следствия (частные случаи для теоремы) – разложение по одной и по всем переменным. Теорема о разложении функций по переменным с доказательством. 2 следствия (частные случаи для теоремы) – разложение по одной и по всем переменным. 2.2. СКНФ: Определение ЭД, ОЭД, КНФ, СКНФ. Представление функции, тождественно не равной единице через СКНФ (воспользоваться двойственностью и СДНФ). Элементарная дизъюнкция (ЭД) - дизъюнкция литералов Основная элементарная дизъюнкция (ОЭД) - элементарная дизъюнкция, в которую включены все переменные Конъюнктивная нормальная форма ( КНФ ) – нормальная форма, в которой формула имеет вид конъюнкции дизъюнкций литералов Совершенная конъюнктивная нормальная форма (СКНФ) — это такая КНФ, которая удовлетворяет трѐм условиям: 1) в ней нет одинаковых элементарных дизъюнкций 2) в каждой дизъюнкции нет одинаковых пропозициональных переменных 3) каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв. 2.3. Основные эквивалентные преобразования и их доказательства (поглощение, склеивание, обобщенное склеивание, расщепление). 2. 4. Определение логического следствия. 2 теоремы о логическом следствии с доказательством. 2. 5. Определение импликанта, простого импликанта. Теорема о представлении функции через простые имликанты. 2.6. Определение дополнения ЭК. Теорема о дополнениях импликанта с доказательством. 2.7. Алгоритм перечисления простых импликантов (Куайна - МакКлоски). Перечислить все шаги алгоритма в общем виде. 2.8. Определение полной системы функций. Теорема о двух полных системах функций. Следствия из теоремы. Определение замыкания. 2.9. Класс функций S. Определение класса и лемма о несамодвойственной функции с доказательством . 2.10. Класс функций M. Определение класса и лемма о немонотонной функции с доказательством. 2. 11. Класс функций L. Определение класса и лемма о нелинейной функции с доказательством . 2.12. Определение дизъюнкта, резольвенты, пустого дизъюнкта. Теорема о резольвенте с доказательством. 2.13. Определение предиката. Кванторы, свободные и связанные переменные. Алфавит исчисления предикатов. Определение терма, атома и формулы. 2.14. Определение предваренной нормальной формы. 10 правил – преобразований для ПНФ (без доказательства). Алгоритм преобразования формул в предваренную нормальную форму. 2.15. Определение ССФ. Процедура преобразования формул в скулемовскую стандартную форму. |