Экзаменационная программа (1075778)
Текст из файла
Кафедра математического моделированияИУ9, 4-й сем., МЛТА, 2008–2009 уч.г.Экзаменационная программа1. Алгебра высказываний. Истинностные функции. Типы формул исчислениявысказываний (общезначимые, выполнимые, опровержимые, противоречия).
Теорема оmodus ponens.2. Подстановки и замены в алгебре высказываний. Теорема о сохранении эквивалентности при подстановке. Теорема о замене эквивалентным. Следствия.3. Принцип двойственности в алгебре высказываний. Способы получения эквивалентных формул.4. Функции алгебры логики (булевы функции). Композиция функции. Множествофункций и его замыкание. Свойства замыкания. Замкнутые и полные множествафункций. Теорема о полном множестве.5. Понятие базиса в алгебре высказываний. Стандартный базис. ДНФ и КНФ.Совершенные нормальные формы. Теорема существования. Полнота стандартногобазиса.6. Базис Жегалкина, его полнота.
Порядок разложения булевой функции в полиномЖегалкина.7. Классы Поста и критерий Поста. Штрих Шеффера и стрелка Пирса. КлассыПоста как максимальные замнутые множества. Доказательство того, что максимальныхзамкнутых классов помимо классов Поста не существует.8. Основные положения теории N (язык, аксиомы, правила вывода). Понятие выводаи частного вывода (вывода из гипотез). Дерево вывода. Пример вывода.9. Теорема о дедукции в исчислении высказываний.10. Структурные и логические правила естественного вывода в исчислении высказываний.11.
Техника естественного вывода. Примеры обоснования выводимости формул наоснове правил естественного вывода (дополнительные правила естественного вывода).12. Основные свойства формальной теории: непротиворечивость, полнота, разрешимость. Доказательство непротиворечивости и разрешимости теории N .13. Основные свойства формальной теории: непротиворечивость, полнота, разрешимость. Полнота в широком смысле и полнота в узком смысле. Доказательство полнотытеории N в широком смысле.14.
Независимые аксиомы и независимые схемы аксиом. Доказательство независимости схем аксиом теории N .15. Предикаты в математической логике. Понятие логико-математического языка.Свободные и связанные переменные. Переименование и коллизия переменных при переименовании. Отношение конгруэнтности.16. Подстановки. Коллизия переменных при подстановке. Подстановка, свободнаядля данного выражения. Сохранение конгруэнтности при подстановке.
Свойство чистотыпеременных и лемма о чистоте переменных.17. Понятие интерпретации логико-математического языка. Оценка выражения.Типы формул алгебры предикатов. Пропозициональные тавтологии и общезначимыеформулы. Формулы, истинные (ложные) в данной интерпретации.18. Основные логические законы алгебры предикатов.19. Замены в формулах алгебры предикатов. Правило замены эквивалентным и егообоснование.20. Принцип двойственности в алгебре предикатов. Теорема об эквивалентностидвойственных формул.21. Предваренная нормальная форма и теорема о приведении.22.
Описание теории P : логико-математический язык, аксиомы, правила вывода.Вывод и частный вывод. Доказательство теоремы о дедукции в исчислении предикатов.23. Правила естественного вывода в исчислении предикатов.ИУ9, 4-й сем., МЛТА, 2008–2009 уч.г. Экзаменационная программа224. Теорема о сохранении истинности в частном выводе. Непротиворечивость теории P .25.
Понятие формальной теории и ее полноты. О полноте исчисления предикатов вшироком и узком смысле. Теорема об интерпретируемости непротиворечивой формальнойтеории.26. Генценовское исчисление высказываний. Дополнительные правила вывода в этомисчислении.27. Связь генценовского исчисления высказываний с гильбертовским. Теорема Генцена об устранении сечения в исчислении высказываний.28. Генценовское исчисление предикатов. Его связь с гильбертовским исчислениемпредикатов.29.
Построение формальной теории групп. Свойства предиката формального равенства. Простейшие теоремы этой теории.30. Аксиоматика формальной арифметики. Простейшие теоремы теории, связанныесо сложением.31. Аксиоматика формальной арифметики. Простейшие теоремы теории, связанные сумножением.32. Понятие скулемовской стандартной формы. Скулемовские функции.
Об эквивалентности скулемовской стандартной формы исходной формуле. Теорема о противоречивости скулемовской стандартной формы.33. Метод резолюций для исчисления высказываний. Теорема о полноте этого методав исчислении высказываний.34. Метод резолюций для исчисления предикатов. Унификация элементарных формул.Примеры резолютивного вывода.3ИУ9, 4-й сем., МЛТА, 2008–2009 уч.г. Экзаменационная программаТипы задач в экзаменационных билетах1.2.3.4.5.ЗадачиЗадачиЗадачиЗадачиЗадачинананананалинейную независимость и полноту систем функций.построение вывода в системах гильбертовского типа.построение вывода в системах генценовского типа.доказательство теорем в формальных теориях.построение скулемовской стандартной формы и метод резолюций.Примеры задач1.
Выяснить, является ли полной система функцийf (x, y, z) = x + y + z,g(x, y) = x ⊕ y,h(x) = x + x.2. Выяснить является ли независимой система функцийf (x) = 0,g(x) = 1,h(x, y, z) = xy + yz.3. С помощью техники естественного вывода установить, что в теории N выводимаследующая формула:(X → Y → (¬X → ¬Y ) → (¬X → Y ∧ Z)) ∼ (X ∨ Y ).4. С помощью техники естественного вывода установить, что в теории P выводимаx yформула ∀x ∀y P → ∀z P.z z5. В теории GV построить вывод секвенции> (X → Y → (¬X → ¬Y ) → (¬X → Y ∧ Z)) ∼ (X ∨ Y ).6.
В теории GP построить вывод секвенции > ∀x ∀y P → ∀z Px y.z z7. В формальной арифметике доказать теорему (X ≤ Y ) ∼ (X + Z ≤ Y + Z).8. Построить скулемовскую стандартную форму для формулы∀x ∀x p(x) → ∀z q(x, z) → ∀x p(x).9. Методом резолюций доказать общезначимость в алгебре предикатов формулы∀x ∀y p(x, y) → ∀y ∀x p(x, y)..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
