Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

(Av^Bv^C)&(^vBv^C)&(^Av^vC). Второй метод построения с.к.н.ф. - метод равносильных преобразований - заключается в следующем. Для заданной формы А находим к.н.ф., которая имеет вид К1&К2&... &Кп, затем добиваемся выполнения указанных выше условий . Если в некоторое Ki входит некоторая буква вместе с ее отрицанием, то Ki - тавтология и из к.н.ф. множитель можно исключить. Если при такой процедуре нужно отбросить все множители из к.н.ф., то А - тавтология и с.к.н.ф. не существует. Если некоторый множитель к.н.ф., например Ki, не содержит букву А, то вводим ее согласно равносильности К,~(КМ)&(К,у-пА). Таким образом, добиваемся, чтобы каждый множитель к.н.ф. содержал все аргументы исходной формы Л. Если в некотором множителе окажутся одинаковые слагаемые, то оставляем только один из них. Если в полученной форме окажутся одинаковые множители, то оставляем только один из них. В результате получим с.к.н.ф. Вопросы и темы для самопроверки 1. Высказывание, логические операции их определения и таблицы истинности. 2. Пропозициональные формы или формулы логики высказываний, определение, примеры. Упрощение записей пропозициональных форм. 3. Методы составления таблиц истинности. 4. Тавтологии (общезначимые формулы), противоречия. Две теоремы о тавтологиях. 5. Равносильность пропозициональных форм (формул логики высказываний), свойства отношения равносильности. 6. Важнейшие пары равносильных пропозициональных форм (запишите). 7. Зависимости между пропозициональными связками. Две теоремы о выражении пропозициональных форм с помощью форм, содержащих связки 3-х видов, 2-х видов. 8. Закон двойственности. 9 Выполнимые пропозициональные формы. Как можно выяснить выполнимость пропозициональной формы? 10. Элементарные суммы и произведения, их свойства. 11. Нормальные формы (д.н.ф. и к.н.ф.). Алгоритмы нахождения к.н.ф.; единственна ли к.н.ф. для заданной формы? 12. Выяснение общезначимости пропозициональной формы по к.н.ф. 13. Совершенная конъюнктивная нормальная форма (с.к.н.ф.). Алгоритмы нахождения с.к.н.ф. 20