- •1. Определение алгоритма и способы их записей.
- •2. Принятые обозначения при описании алгоритмов.
- •3. Пошаговое описание алгоритмов.
- •4. Описание алгоритмов в виде блок-схем.
- •5. Свойства алгоритмов.
- •6. Критерии эффективности и сложность алгоритмов.
- •7. Классификация задач по степени сложности.
- •8. Сущность метода математической индукции (ми).
- •9. Построение доказательства по методу ми.
- •10. Примеры доказательств с использованием метода ми.
- •11. Использование метода ми для исследования алгоритмов (на примере обобщенного алгоритма Евклида).
- •12. Недетерминированные и детерминированные алгоритмы.
- •13. Разделы математической логики, представление операций булевой логики через множества и их отображение с помощью диаграмм Эйлера-Венна.
- •14. Объединение множеств и переход от предметной переменной х к логическим переменным х1 и х2 .
- •15. Пересечение множеств, тавтология, противоречие, дополнение и области взаимодействия двух множеств на диаграмме Эйлера-Венна.
- •16. Таблицы истинности для дизъюнкции и конъюнкции.
- •17. Операции стрелка Пирса и штрих Шеффера.
- •18. Операции разности и импликации.
- •19. Операции симметрической разности и эквивалентности.
- •20. Формы представления булевых функций (сднф, скнф, спнф).
- •21. Двойственность в булевой логике.
- •22. Различия отображения логических функций в сднф. Скнф и спнф. Переход из сднф в спнф.
- •23. Минимальные нормальные формы логических функций.
- •24. Принцип суперпозиции в булевой логике и приоритеты логических операций.
- •25. Классы элементарных логических функций.
- •26. Законы логики Буля.
- •27. Применение закона поглощения для нескольких переменных.
- •28. Аксиоматический подход к доказательству логических выражений в булевой
- •29. Доказательство логических выражений с помощью диаграмм Эйлера-Венна.
- •30. Доказательство логических выражений с использованием таблиц истинности.
- •31. Способы доказательства логических выражений с использованием специальных приемов.
- •32. Логика высказываний и операции логики высказываний.
- •33. Таблицы истинности операций логики высказываний.
- •34. Различия логики Буля и логики высказываний.
- •35. Метаязык логики высказываний и переход от импликативной формы к высказываниям на метаязыке.
- •36. Аксиомы, противоречия и тавтологии в логике высказываний.
- •37. Конструктивный подход к доказательству логических выражений в логике высказываний.
- •38. Минимальная нормальная форма, минимальное и трансверсальные покрытия в логике высказываний.
- •39. Доказательство логических высказываний с помощью метода резолюций.
- •40. Логика предикатов.
- •41. Минимизация логических выражений методом Куайна (Квайна).
- •42. Минимизация логических выражений в логике Буля путем склеивания в сднф и скнф. Показать, в чем различие склеивания в этих двух формах.
- •43. Асимптотические представления и анализ алгоритмов.
31. Способы доказательства логических выражений с использованием специальных приемов.
Способ доказательства с использованием раскрытия Булевых операций их из определения и некоторых законов логики Буля.
1 пример. Доказать тождество
(a∩b∩c)→(a U b U c)=(a→b) U (b→c) U (c→a)
Доказательство: (a∩b∩c)→(a U b U c)=по определению операции импликации = = по закону де Моргана = = по определению импликации = ;
Доказательство:
Доказательство специального характера
Доказать, что если
Доказательство:
Доказательство и использованием “Умножения” слева и справа. На дополнительную импликанту.
Доказать закон де Моргана
умножим слева на (a U b):
умножим справа (a U b):
32. Логика высказываний и операции логики высказываний.
Высказывание – грамматически правильное предложение, про которое можно сказать истинно оно или ложно. ПРИМЕР : «Киев – столица Украины» (И) – истинна «Томск – столица Японии» (Λ) ложь
Пусть имеем два след. Высказывания: А = «на улице идет дождь» В = «над головой раскрыт. зонт»
С помощью логических связок можно образовать более сложное высказывание
- отрицание Ā = «на улице не идет дождь»; - дизъюнкция Ā U В = «на улице не идет дождь или/и над головой раскрыт зонт»; - конъюнкция = «На улице идет дождь и над головой не раскрыт зонт»; - импликация А → В «Если на улице идет дождь, то над головой раскрыт зонт»; - эквивалентность В ~ А = «Над головой раскрыт зонт, тогда и только тогда, когда идет дождь» Другие логические связи в логике высказываний не используются.
РАССМОТРИМ ПОДРОБНО:
1. ОТРИЦАНИЕ Ā. Высказывание А по другому можно прочитать так: « истинно то, что на улице идет дождь » Если А = 0, то это означает, что на улице нет дождя. Дополнение к А : Ā также отрицательно на истинное высказывание: «истинно то, что на улице не идет дождь» Тогда: Ā = 1 (отсутствие дождя)( А = 0 )
2. ДИЗЪЮНКЦИЯ В общем случае подразумевают так же конъюнкцию двух высказываний. Т. е. обознач. « или » однако часто возникает необходимость обязать высказывание только союзом «или»
ПРИМЕР: Р=«Петр находится в бассейне» Q=«Петр находится в театре»PVQ=«Петр находится в бассейне или в театре ». Если необходимо точно показать где находится Петр, то нужно записать, (P V Q)Λ( ) = (P V Q)Λ( ). C точки зрения логики Буля эта операция соответствует ассиметричной разности P + Q , + - не используется => необходимо применить запись показанную выше.
P |
Q |
P V Q |
|
||||
0 1 0 1 |
0 0 1 1 |
0 1 1 1 |
|
||||
|
|
|
|||||
|
|
|
|
|
|
1 0 1 0 |
1 1 0 0 |
1 1 1 0 |
4.ИМПЛИКАЦИЯ. Высказывания типа «если А,то В» имеют объясняющий характер(причина-следствие). Т. е. что имеет место событие В, потому, что произошло событие А.
Грамматически импликация может быть оформлена:«А является достаточным основанием для В»; «В потому,что А»;«В при условии выполнения А» и т.п. ~ причинно – следствие отношения можно записывать в виде таблицы истинности.
А |
В |
А → В |
Результат |
0 1 0 1 |
0 0 1 1 |
1 0 1 1 |
Останешься сухим Будешь мокрым Останешься сухим Останешься сухим |
Даная таблица является таблицей истинности для импликации, как в логике Буля, так и в логике высказывания.
5.ЭКВИВАЛЕНТНОСТЬ. Может интерпретироваться высказываниями
«А эквивалентно В»,а также «А равно В»,«А тождественно В»,«А равносильно В»,«А тогда и только тогда В»и т.п. Экв-ность выражается через конъюнкцию двух импликацийA~В=(А→В)Λ(В→А), такое отношение часто возникает при одновременном высказывании 2-х условий «из А следует В» и «из В следует А».=>при эквивалентности нельзя одному событию принимать только роль причину, а другому только следствие и наоборот. ПРИМЕР: R=«нарастание анархии в обществе», S=«падение авторитета власти».Это события являются разнопорядковыми, т.к. R происходит из-за S и наоборот S происходит из-за R, R и S образую здесь логический круг кот-ый называется СИЛЬНОСВЯЗАННЫМ и выражают следующими множествами R~S=(RΛS)~(RVS ) или l=(RVS)→(RΛS). Понятие сильной связанности совпадают с понятием экви-ти если речь идет о двух событиях.
А |
В |
А ~ В |
А → В |
B → A |
()V() |
0 1 0 1 |
0 0 1 1 |
1 0 0 1 |
1 0 1 1
|
1 1 0 1 |
1 0 0 1 |