Тавтологии, выражающие одни операции через другие.

А ® В«ù АÚ В

А ® В«ù(АÙù В)

АÚ В«ù А® В

АÚ В«ù(АÙù В)

АÚ В«ù(ùАÚù В)

(А«В) «(А® В)Ù(А® В)

Логическое следствие.

Определение 3. Формула В называется логическим следствием формул А₁, А₂, …А_n,если при любом выборе истинностных значений переменных, входящих в А₁, А₂, …А_n, формула В принимает значение «истина» тогда, когда каждая из формул А₁, А₂, …А_n принимает значение «истина».

А₁, А₂, …А_n╞ В

Например: А® В, А®ù В ╞ ù А

Вопросы для активизации и создания проблемной ситуации.

1. Как составляются формулы логики высказываний?

2. Что является основной задачей логики высказываний?

3. Что такое тавтология?

4. Что такое противоречие?

5. Что называют законом логики?

6. Дайте понятие высказыванию. Приведите примеры.

7. Какие значения может принимать высказывание? Приведите примеры истинных и ложных высказываний.

8. Являются ли высказываниями вопросительные предложения, восклицательные предложения, определения?

9. Какие виды операций над высказываниями вы знаете?

10. Что называется отрицанием высказывания? Пример.

11. Что называется конъюнкцией двух высказываний? Пример.

12. Что называется дизъюнкцией двух высказываний? Пример.

13. Что называется импликацией двух высказываний? Пример.

14. Что называется эквивалентностью двух высказываний? Пример.

15. Приведите таблицу истинности для операции отрицания.

16. Приведите таблицу истинности для операции конъюнкции.

17. Приведите таблицу истинности для операции дизъюнкции.

18. Приведите таблицу истинности для операции импликации.

19. Приведите таблицу истинности для операции эквивалентности.

Лекция №4. Графы и деревья: деревья, неориентированные графы, ориентированные графы, стратегии обхода графов. (1 час)

Цель лекции: Раскрыть практическую значимость графов как объектов, относящихся к графическим способам описания систем, процессов, явлений; определить граф и способы его задания; дать понятия орграфа, полного графа, петли, мультиграфа и дополнения графа. Определить цепи и циклы неориентированных графов; пути и контуры ориентированных графов; дать понятие связности в графах; рассмотреть понятия дерева, леса, прадерева.

Вопросы лекции:

1. Введение в теорию графов.

2. Понятие графа и способы его задания.

3. Ориентированные и неориентированные графы.

4. Цепи и циклы неориентированных графов.

5. Пути и контуры ориентированных графов.

6. Понятие связности в графах.

7. Частичные графы. Подграфы. Частичные подграфы.

8. Дерево и лес.

Содержание лекции:

Введение в теорию графов.

На практике часто бывает полезно изобразить некоторую ситуацию в виде рисунков, составленных из точек (вершин), представляющих основные ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такие рисунки известны под общим названием графов. Графы встречаются в разных областях под разными названиями: “структуры” в гражданском строительстве, “сети” в электротехнике, “социограммы” в социологии, “молекулярные структуры” в химии, и т. д.

Начало теории графов как математической дисциплины было положено Эйлером в знаменитом рассуждении о Кенигсбергских мостах. Однако эта статья, написанная в1736 г, была единственной в течение почти ста лет. Интерес к этой науке возродился в ХIХ в. в связи с развитием естественных наук (исследования электрических сетей, моделей кристаллов и структур молекул), формальной логики (бинарные отношения можно изучать в форме графов).

Последние 50 лет ознаменовали новый период интенсивных разработок в теории графов. Появились новые области приложения: теория игр и программирование, теория передачи сообщения, электрических сетей и контактных цепей, биология, психология, задачи сетевого планирования, задачи принятия решений.