Уроки

Слайд 1

Логические законы и правила преобразования логических выражений

Слайд 2

Законы формальной логики Закон тождества: в процессе определенного рассуждения всякое понятие и суждение должны быть тождественны самим себе. Закон непротиворечия: невозможно что-либо одновременно утверждать и отрицать. Закон исключения третьего : из двух противоречащих суждений одно истинно, другое ложно, а третьего не дано. Закон достаточного основания: всякая истинная мысль должна быть достаточно обоснована. Сформулированы Аристотилем. Сформулирован Лейбницем

Слайд 3

Доказать можно только истинные мысли, ложные доказать нельзя. «Ошибаться свойственно всякому человеку, но настаивать на ошибке свойственно только глупцу». Только содержательный характер.

Слайд 4

Законы алгебры высказываний При решении многих логических задач часто приходится упрощать формулы, полученные при формализации их условий. Упрощение формул в алгебре высказываний производится на основе эквивалентных преобразований, опирающихся на основные логические законы. Законы алгебры высказываний (алгебры логики) – это тавтологии.

Слайд 5

Основные законы алгебры высказываний (содержат одну переменную) Закон тождества. А = А Всякое понятие и суждение тождественно самому себе . Закон тождества означает, что в процессе рассуждения нельзя подменять одну мысль другой, одно понятие другим. При нарушении этого закона возможны логические ошибки. Примеры Движение вечно. Хождение в школу – движение. Следовательно, хождение в школу вечно.

Слайд 6

Закон непротиворечия. A & A = 1 A & A = 0 Примеры: На Марсе есть жизнь и на Марсе жизни нет. Светлана окончила среднюю школу и учится в 10 классе. Закон исключения третьего. А \/ А = 1 Примеры: Число 12345 либо четное либо нечетное, третьего не дано. Ученик учится или хорошо или плохо. Эта жидкость является или не является кислотой.

Слайд 7

Закон двойного отрицания. А = А А А А 0 1 0 1 0 1 Пример А = Матроскин - кот А = Неверно, что Матроскин не кот А = А

Слайд 8

Свойства констант: 0 = 1 ( отрицание лжи есть истина) А \/ 0 = А А \/ 1 =1 1 = 0 ( отрицание истины есть ложь) А & 0 = 0 А & 1 = A Законы идемпотентности А \/ А = А (отсутствие коэффициентов) А & А = А (отсутствие степеней)

Слайд 9

Законы коммутативности А \/ В = В \/ А А & В = В & А Законы ассоциативности A \/(B \/ C) = (A \/ B) \/ C A &(B & C) = (A & B) & C Законы дистрибутивности A \/(B & C) = (A \/ B) & (A \/ C) ( дистрибутивность дизъюнкции относительно конъюнкции) A &(B \/ C) = (A & B) \/ (A & C) ( дистрибутивность конъюнкции относительно дизъюнкции) Доказать

Слайд 10

Законы поглощения: А \/ (А & В ) =A А & (А \/ В ) =A Доказать

Слайд 11

Законы де Моргана: A \/ B = A & B ( отрицание вариантов вместе ) A & B = A \/ B ( отрицание одновременной истинности) Словесная формулировка законов де Моргана дизъюнкции конъюнкция Отрицание есть отрицаний конъюнкции дизъюнкция

Слайд 12

Законы де Моргана: A \/ B = A & B ( отрицание вариантов вместе) A & B = A \/ B ( отрицание одновременной истинности) Мнемоническое правило: в левой части тождества операция отрицания стоит над всем высказыванием. В правой она как бы разрывается и отрицание стоит над каждым из простых высказываний, но одновременно меняется операция: дизъюнкция на конъюнкцию и наоборот.

Слайд 13

Примеры: Высказывание Неверно, что я знаю арабский или китайский язык тождественно высказыванию Я не знаю арабского языка и не знаю китайского языка. Неверно, что я выучил урок и получил по нему двойку тождественно высказыванию Или я не выучил урок или я не получил по нему двойку.

Слайд 14

Замена операции импликации и эквивалентности: A => B = A \/ B - замена импликации. Для замены операции эквивалентности существует два правила: A  B = (A & B) \/ (A & B); A  B = (A \/ B) & (A \/ B). Доказать! A => B = A & B - замена импликации.

Слайд 15

Пример: Е = Неверно, что если я выиграю конкурс, то получу приз. А = Я выиграю конкурс В = Я получу приз. Е = A =>B = A \/ B = A & B = A & B Е = Я выиграю конкурс, но приз не получу.

Слайд 16

Интерес представляют следующие правила: A => B = B => A A  B = (A =>B) & (B => A) Фраза Если Винни-Пух съел мед, то он сыт тождественна фразе Если Винни-Пух не сыт, то меда он не ел.

Слайд 17

Историческая справка Аристотель Готфрид Вильгельм Лейбниц Огастес де Морган Джордж Буль Джордж Венн

Слайд 1

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

Слайд 2

При проектировании компьютерных сетей, телефонных линий, трубопроводов и строительстве дорог необходимо минимизировать затраты на прокладку коммуникаций. Прежде всего целесообразно выбрать минимальный по длине маршрут Пример Необходимо соединить телефонным или компьютерным кабелем шесть зданий, расстояния между которыми различны. Кабель должен быть минимальной длины и подходить к каждому зданию 1 6 2 4 3 5 7 2 4 2 6 1 3 2 1 8 Задача прокладки коммуникации Для решения таких задач используется теория графов.

Слайд 3

Основные понятия теории графов. Граф G задается с помощью пары множеств. G =(V,R ) , где V – множество (совокупность) вершин, R – множество ребер, соединяющих пары вершин. Множество ребер может быть пустым, если ни одна из вершин не соединена с другими вершинами. Обычно граф представляется в виде схемы, на которой некоторые вершины, соединены линиями ( ребрами ). V 2 V 3 V 1 V 4 V 5 R 25 R 15 R 35 R 45 R 14 Вершинами могут служить объекты любой природы: населенные пункты, компьютеры сети, элементы блок-схем алгоритмов и т.д. Под ребрами могут подразумеваться дороги между соседними городами, стороны геометрических фигур, линии связи между компьютерами и т.д . V 2 V 3 V 1 V 4 V 5 R 25 R 15 R 35 R 45 R 14 V 2 V 3 V 1 V 4 V 5 R 23 R 25 R 15 R 35 R 45 R 34 V 2 V 3 V 1 V 4 V 5 R 12 R 25 R 15 R 35 R 45 R 14

Слайд 4

V 2 V 3 V 1 V 4 V 5 R 12 R 23 R 25 R 15 R 35 R 45 R 14 Вершины называют смежными , если их соединяет ребро . Например, V 1 и V 2 - смежные вершины , так как их соединяет ребро R 12 Ребро и любая из его двух вершин называются инцидентными . Под степенью вершины подразумевается количество инцидентных ей ребер . Так степень вершины V 1 равна 3 , а степень вершины V 5 равна 4 . V 2 V 3 V 1 V 4 V 5 R 12 R 25 R 15 R 35 R 45 R 14 V 2 V 3 V 1 V 4 V 5 R 12 R 25 R 15 R 35 R 45 V 2 V 3 V 1 V 4 V 5 R 12 R 25 R 15 R 35 R 45 R 14 R 34 Любую систему улиц в городе можно представить в виде графа. Здесь вершины – это перекрестки. Множества V и R являются конечными, так как можно перечислить все вершины и ребра графа. Количество вершин и количество ребер графа определяют мощности множества V и R . Так количество вершин графа G равно 5 , а количество ребер равно 8.

Слайд 5

V 2 V 3 V 1 V 4 V 5 R 15 R 45 Одна вершина достижима из другой, если между ними проложен маршрут. Граф считается связанным, если каждая его вершина достижима из любой другой. Например, маршрут между вершинами V1 и V 4 может быть следующим: V 1 R 12 V 2 R 23 V 3 R 34 V 4 Вершины, которые не имеют инцидентных ребер, называются изолированными вершинами. Можно также сказать, сто их степень нулевая. Изолированные вершины недостижимы из любых других вершин. V 2 V 3 V 1 V 4 V 5 R 15 R 45 V 2 V 3 V 1 V 4 V 5 R 23 R 15 R 45 V 2 V 3 V 1 V 4 V 5 R 12 R 25 R 15 R 35 R 14 R 34 Маршрут графа – это последовательность чередующихся вершин и ребер . В графах можно выделить различные маршруты. Маршрут является замкнутым (циклом ), если его начальные и конечные вершины совпадают. Циклические маршруты графа G –V 1 R 12 V 2 R 23 V 3 R 34 V 4 R 14 V 1 , …. Маршрут называется простой цепью, если все его вершины и ребра различны. Длина маршрута равна количеству ребер, входящих в него.

Слайд 6

Граф, в котором каждое ребро имеет одно направление называется ориентированным (орграф), а ребра в таком графе называют дугами. Другими словами, ребро – это неупорядоченная пара вершин, а дуга – упорядоченная. Дуги R12 и R21 не совпадают в орграфе. Для орграфа вводятся такие понятия, как входящая и исходящая степени вершин. Число входящих в вершину дуг . Число исходящих из вершины дуг. Расширяя терминологию теории графов, математика вводит понятие взвешенного графа , или более обобщенно – сети. Взвешенный граф ( сеть ) – это такой граф, ребрам или дугам которого поставлены в соответствие числовые величины . Вес сети равен сумме весов ее ребер.

Слайд 7

V 2 V 3 V 1 V 4 V 5 V 2 V 3 V 1 V 4 V 5 V 2 V 3 V 1 V 4 V 5 R 23 R 45 V 2 V 3 V 1 V 4 V 5 R 12 R 25 R 15 R 35 R 14 R 34 Описание графа с помощью матрицы смежности. Для наглядного представления графа используют схемы Для математических расчетов удобно использовать представление графа в форме матрицы . 1 2 3 4 5 1 0 1 0 1 1 2 1 0 1 0 1 3 0 1 0 1 1 4 1 0 1 0 1 5 1 1 1 1 0 Для смежных вершин элементы матрицы смежности равны 1, а для несмежных – 0. Диагональные элементы матрицы равны 0.

Слайд 8

V 2 V 3 V 1 V 4 V 5 V 2 V 3 V 1 V 4 V 5 V 2 V 3 V 1 V 4 V 5 R 23 =25 R 45 = 15 V 2 V 3 V 1 V 4 V 5 R 12 =50 R 25 =30 R 15 =10 R 35 =35 R 14 =25 R 34 = 50 Описание графа с помощью матрицы смежности. Преобразуем граф G в сеть, т.е. Присвоим ребрам, соединяющим смежные вершины , 1 2 3 4 5 1 0 50 0 25 10 2 50 0 25 0 30 3 0 25 0 50 35 4 25 0 50 0 15 5 10 30 35 15 0

Слайд 9

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

Слайд 10

V 2 V 2 V 2 R 23 V 2 V 3 V 1 V 4 V 5 R 12 R 35 R 14 R 34 V 1 V 5 V 1 V 5 V 1 V 5 R 23 R 14 V 2 V 3 V 1 V 4 V 5 R 35 R 34 R 14 V 2 V 5 V 3 Подграф графа G Остовной связный подграф графа G Остовное связное дерево

Слайд 11

Преобразование графа в остовное связное дерево минимального веса Пусть G = (V,R) – связный взвешенный неориентированный граф, где V множество вершин, а R – множество ребер. R nk и R kn считаются одним и тем же ребром, поэтому в матрице смежности не учитываются дублирующие друг друга ребра. 1 2 3 4 5 1 0 50 0 25 10 2 50 0 25 0 30 3 0 25 0 50 35 4 25 0 50 0 15 5 10 30 35 15 0 Введем понятие цикломатического числа γ , показывающего , сколько ребер надо удалить, чтобы в нем не осталось ни единого цикла. γ = m – n + 1 , где m – количество ребер, n – количество вершин. Для графа G γ = 8 – 5 + 1 = 4

Слайд 12

Для остовного связного дерева необходимо убрать 4 ребра, и тогда в нем не будет ни одного цикла. Для каждого графа существует несколько остовных связных деревьев, которые обладают различными весами R 25 V 2 V 1 V 4 V 3 V 5 V 2 V 3 V 5 V 1 V 1 V 4 V 2 V 1 V 5 V 3 V 4 R 23 R 34 R 14 R 23 R 35 R 45 R 14 R 12 R 14 R 34 R 15 Вес графа - 130 Вес графа - 100 Вес графа - 135

Слайд 13

Для построения остовного связного дерева минимального веса используется алгоритм Крускала. Первоначально из графа удаляются все ребра, получается остовной подграф, где все вершины изолированы. Ребра сортируются по возрастанию весов. Ребра последовательно по возрастанию весов, включаются в остовное дерево Существуют четыре случая: Обе вершины включаемого ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое связное множество; Одна из вершин принадлежит связному подмножеству, а другая нет, тогда включаем вторую в подмножество, которому принадлежит первая; Обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества.; Обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро. Алгоритм заканчивает работу, когда все вершины будут объединены в одно множество, при этом оставшиеся ребра не включаются в остовное дерево

Слайд 14

№ Выполняемые действия Множество вершин Граф 1 Построим остовной граф, содержащий только изолированные вершины Каждая вершина исходного графа помещается в одноэлементное подмножество, получаем пять одноэлементных подмножеств. {V 1 }, {V 2 }, {V 3 }, {V 4 }, {V 5 } V 2 V 3 V 4 V 1 V 5