Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Презентации / Основы дискретной математики
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 24 мая.

Подать заявку на курс
  • Информатика

Основы дискретной математики

библиотека
материалов
Костанайский Государственный Университет им. Ахмета Байтурсынова Автор презен...
“Теперь в математике остаются только целые числа и конечные... системы целых...
Основное отличие дискретной математики от классической заключается в отсутств...
Тема: Основы дискретной математики
Цель: Цель: Рассмотреть основные понятия множества, основ логики, теории граф...
Задачи Лекции: 1 Дать определение множеств, отношений и функций 2 Рассмотреть...
План Лекции: 1. Функции, отношения и множества 2. Основы логики 3. Графы и де...
I. Функции, отношения и множества
X и Y – некоторые числовые множества. Если каждому элементу множества X единс...
Способы задания функции: Аналитический Табличный Графический
Аналитический При аналитическом способе задания функция задается с помощью фо...
Графический Соответствие между аргументом и функцией задается посредством гра...
Табличный Данный способ формирует соответствие между аргументом и функцией по...
Классификация элементарных функций Тригонометрическая: Y=sin x,y=cos x,y=tg x...
Совокупность каких-либо объектов, обладающих общими свойствами, называют Множ...
““ ““ Например: xA Например: хA Принадлежность элемента X множеству A При...
Понятие множества Счетное - Множество, каждый элемент которого можно индексир...
Если все элементы множества A являются также элементами множества B, то множе...
Пустое и универсальное множество Множество, не содержащее ни одного элемента,...
Множество, элементами которого являются подмножества, называют семейством под...
Алгебра множеств Функции, область определения и область значения которых прин...
Законы алгебры множеств Коммутативности: (AB)=(BA) и (AB)=(BA); Ассоциати...
Объединение множеств А и В есть множество, состоящее из всех тех элементов, к...
Пересечение множеств А и В есть множество, состоящее из всех тех элементов, к...
Обозначение: Разность множеств Разность множеств А и В есть множество, состоя...
Обозначение: Симметрическая Разность множеств Симметрическая разность множест...
Отображение, заданное между элементами одного множества Х, называют Отношение...
Бинарным или двуместным отношением между элементами множеств A и B называется...
Симметричность Антисимметричность Асимметричность Транзитивность Антирефлекси...
Бинарное отношение рефликсивно, если для каждого хiХ имеем r(xi; xi)=1. Таки...
Антисимметричность Бинарное отношение антисимметрично, если для любой пары (x...
Симметричность Бинарное отношение симметрично, если для любой пары (xi, xj)R...
Антирефлексивность Бинарное отношение антирефлексивно, если для каждого хiХ...
Транзитивность Бинарное отношение транзитивно, если для любых элементов xi, x...
Асимметричность Бинарное отношение асимметрично, если для любой пары (xi, xj)...
Бинарное отношение, удовлетворяющее условиям рефлексивности, симметричности и...
II. Основы логики
Первые учения о формах и способах рассуждений возникли в странах Древнего Вос...
Вильгельм Готфрид Лейбниц (1646 - 1716) Второй этап – математическая логика,...
Джордж Буль (1815-1864) Основоположник математической логики считается Джордж...
В современное время для анализа и синтеза схем в ЭВМ при алгоритмизации и про...
Алгебра логики – это раздел математики, изучающий высказывания, рассматриваем...
Типы формальных систем Логика высказываний Логика предикатов Логика отношений...
Логика предикатов Логика предикатов (predicate calculus) есть формальная сист...
Логика высказываний Логика высказываний (prepositional calculus) есть модель...
Нечеткая логика Логика нечеткая (fuzzi calculus) есть формальная система, пре...
Логика отношений Логика отношений (relation calculus) есть формальная система...
Любое повествовательное предложение, которое может быть признано истинным или...
Алгебра высказываний Модель алгебры высказываний. Множество T={A, B, C,…} с з...
Логические операции Логические операции бывают унарные (или одноместные) и би...
Отрицание Логические операции Конъюнкция Дизъюнкция Импликация Эквиваленция
Отрицание Отрицание (операция НЕ) есть одноместная операция, посредством кото...
Конъюнкция Конъюнкция есть двухместная операция, посредством которой из двух...
Дизъюнкция есть двухместная операция, посредством которой из двух формул F1 и...
Эквиваленция Таблица логической эквивалентности Обозначение: Эквиваленция ест...
Импликация есть двуместная операция, посредством ко­торой отражающую сложное...
Законы Алгебры Логики Законы Алгебры Логики Наименование закона	Равносильные...
III.Графы и деревья
Теория графов находит самое широкое применение в моделировании информационных...
Первая работа по теории графов была опубликована математиком Л. Эйлером в 173...
Совокупность объектов произвольной природы и отношений между каждой парой эти...
Вершинами графа могут быть операторы программы или команды операционной систе...
Ориентированный граф - это пара (V, E), где V - конечное множество вершин (уз...
Неориентированный граф G=(V, E) - это ориентированный граф, у которого для ка...
Деревья Деревья являются одним из интереснейших классов графов, используемых...
Способы обхода деревьев. Часто при обработке представленной в дереве информац...
Литература: 1.Информатика Учеб. для студентов эконом. спец. вузов/под ред.Мак...
??? Контрольные вопросы: Что такое множества? Что такое функция? Какие сущест...
Спасибо За Внимание!!!
69 1

Описание презентации по отдельным слайдам:

№ слайда 1 Костанайский Государственный Университет им. Ахмета Байтурсынова Автор презен
Описание слайда:

Костанайский Государственный Университет им. Ахмета Байтурсынова Автор презентации: ст. преподаватель кафедры ИиМ Ермагамбетова Гульмира Нурлановна

№ слайда 2 “Теперь в математике остаются только целые числа и конечные... системы целых
Описание слайда:

“Теперь в математике остаются только целые числа и конечные... системы целых чисел...” Анри Пуанкаре.

№ слайда 3 Основное отличие дискретной математики от классической заключается в отсутств
Описание слайда:

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

№ слайда 4 Тема: Основы дискретной математики
Описание слайда:

Тема: Основы дискретной математики

№ слайда 5 Цель: Цель: Рассмотреть основные понятия множества, основ логики, теории граф
Описание слайда:

Цель: Цель: Рассмотреть основные понятия множества, основ логики, теории графов.

№ слайда 6 Задачи Лекции: 1 Дать определение множеств, отношений и функций 2 Рассмотреть
Описание слайда:

Задачи Лекции: 1 Дать определение множеств, отношений и функций 2 Рассмотреть способы задания функций 3 Классифицировать функции 4 Рассмотреть основные понятия графов 5 Классифицировать основные логические операции 6 Изучить основные понятия о деревьях

№ слайда 7 План Лекции: 1. Функции, отношения и множества 2. Основы логики 3. Графы и де
Описание слайда:

План Лекции: 1. Функции, отношения и множества 2. Основы логики 3. Графы и деревья

№ слайда 8 I. Функции, отношения и множества
Описание слайда:

I. Функции, отношения и множества

№ слайда 9 X и Y – некоторые числовые множества. Если каждому элементу множества X единс
Описание слайда:

X и Y – некоторые числовые множества. Если каждому элементу множества X единственным образом соответствует элемент множества Y, то это соответствие называется Функцией. Обозначение: f : x →y; y = f(x) Здесь Y – зависимая переменная, X – независимая переменная (аргумент) Понятие функции

№ слайда 10 Способы задания функции: Аналитический Табличный Графический
Описание слайда:

Способы задания функции: Аналитический Табличный Графический

№ слайда 11 Аналитический При аналитическом способе задания функция задается с помощью фо
Описание слайда:

Аналитический При аналитическом способе задания функция задается с помощью формул: В явном виде Функция разрешена относительно y : y = х2 В неявном виде Функция не разрешена относительно y: F(x,y) = 0 При аналитическом способе функцию можно задать: Несколькими выражениями Параметрически В полярной системе координат

№ слайда 12 Графический Соответствие между аргументом и функцией задается посредством гра
Описание слайда:

Графический Соответствие между аргументом и функцией задается посредством графика. у x

№ слайда 13 Табличный Данный способ формирует соответствие между аргументом и функцией по
Описание слайда:

Табличный Данный способ формирует соответствие между аргументом и функцией посредством табличных значений X X1 X2 … Xn Y Y1 Y2 … Yn

№ слайда 14 Классификация элементарных функций Тригонометрическая: Y=sin x,y=cos x,y=tg x
Описание слайда:

Классификация элементарных функций Тригонометрическая: Y=sin x,y=cos x,y=tg x,y=ctg x; Обратно тригонометрическая: Y=arcsin X, Y=arccos X, Y =arctg X, X= arcctg Y Степенная: Y=xa; Показательная: Y=ax; Логарифмическая: Y=logax Логическая: Y = true; X = false;

№ слайда 15 Совокупность каких-либо объектов, обладающих общими свойствами, называют Множ
Описание слайда:

Совокупность каких-либо объектов, обладающих общими свойствами, называют Множеством. Понятие множества Обозначение: пара фигурных скобок ”{”, “}” между которыми перечисляют элементы множества. Например: {1, 3, 5, 7} или {a, b, c, d}. Для обозначения множества в тексте используют прописные буквы латинского алфавита A, B, C, ...X, Y, Z, а для его элементов - строчные буквы a, b, c,...x, y, z. Иногда эти буквы используют с индексами.

№ слайда 16 ““ ““ Например: xA Например: хA Принадлежность элемента X множеству A При
Описание слайда:

““ ““ Например: xA Например: хA Принадлежность элемента X множеству A Принадлежность множества Элемент Х не принадлежит множеству A Основное отношение между элементами и множеством - это отношение принадлежности элемента множеству.

№ слайда 17 Понятие множества Счетное - Множество, каждый элемент которого можно индексир
Описание слайда:

Понятие множества Счетное - Множество, каждый элемент которого можно индексировать целым числом 1,2,... N. Если N конечно, то множество называют конечным. Число элементов счетного конечного множества A называют его мощностью и обозначают так: |A|=n.

№ слайда 18 Если все элементы множества A являются также элементами множества B, то множе
Описание слайда:

Если все элементы множества A являются также элементами множества B, то множество A является подмножеством множества B. Понятие подмножества А={1, 2, 3} B={1, 2, 3, 4, 5} ““ Обозначение: знак включения: AB. знак невключения AB ““

№ слайда 19 Пустое и универсальное множество Множество, не содержащее ни одного элемента,
Описание слайда:

Пустое и универсальное множество Множество, не содержащее ни одного элемента, называют пустым множеством. Пустое множество является подмножеством любого множества. Обозначение:  Множество, содержащее все элементы всех подмножеств, принимающих участие в решении каких-либо задач, называют универсальным множеством.  ={ } (нет элементов) Обозначение: U U ={a, b, c, d}

№ слайда 20 Множество, элементами которого являются подмножества, называют семейством под
Описание слайда:

Множество, элементами которого являются подмножества, называют семейством подмножеств. Семейства и классы. Булеан. Множества, элементами которых являются другие множества, часто называют семействами или классами. Например, A{{a, b}, {b, c, d}}, B{{a, b}, {b, c, d}}. Максимально возможное число подмножеств универсального множества называют булеаном. Булеан включает в себя пустое подмножество и множества, сформированные из одного, двух, трех и т.д. до общего числа элементов универсального множества.

№ слайда 21 Алгебра множеств Функции, область определения и область значения которых прин
Описание слайда:

Алгебра множеств Функции, область определения и область значения которых принадлежит одному множеству, называют операцией. fi: XX или fi: XnX. Множество X вместе c заданным множеством операций F={f1, f2, ..} называют Алгеброй.

№ слайда 22 Законы алгебры множеств Коммутативности: (AB)=(BA) и (AB)=(BA); Ассоциати
Описание слайда:

Законы алгебры множеств Коммутативности: (AB)=(BA) и (AB)=(BA); Ассоциативности: A(BC)=(AB)C и A(BC)=(AB)C; Идемпотентности: AA=A и AA=A; Поглощения: A(AB)=A и A(AB)=A; Дистрибутивности: A(BC)=(AB)(AC) и A(BC)=(AB)(AC); “Третьего не дано” AA=U; Противоречия: AA=. Двойного отрицания:  (A)=A. - символ унарной операции – дополнения,  - символ бинарной операции – объединения,  -символ бинарной операции - пересечения.

№ слайда 23 Объединение множеств А и В есть множество, состоящее из всех тех элементов, к
Описание слайда:

Объединение множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному множеству А или В, т.е. С=(АВ)={x| xA или xB}. Если В=, то АВ=А=А. Если B=U, то АВ=АU=U. Если АС и ВС, то АВС. Обозначение: Объединение множеств

№ слайда 24 Пересечение множеств А и В есть множество, состоящее из всех тех элементов, к
Описание слайда:

Пересечение множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат множеству А и принадлежат множеству В, т.е. (АВ)={x|xA и xB}. Если В=, то АВ=А=. Если B=U, то АВ=АU=А. Если СА и СВ, то САВ. Если А и В, то при АВ= множества A и B не имеют общих элементов Обозначение: Пересечение множеств

№ слайда 25 Обозначение: Разность множеств Разность множеств А и В есть множество, состоя
Описание слайда:

Обозначение: Разность множеств Разность множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат множеству А и не принадлежат множеству В. “\” С=(А\В)= {x|xА и xВ},

№ слайда 26 Обозначение: Симметрическая Разность множеств Симметрическая разность множест
Описание слайда:

Обозначение: Симметрическая Разность множеств Симметрическая разность множеств А и В есть множество, состоящее из всех тех элементов, которые принадлежат разности (А\В) или (В\А). “” С=(АВ)=(АВ)(ВА) (АВ)=(АВ)(ВА)=, то А=В. *Это правило будет часто использоваться при доказательстве тождеств и поиске неизвестных множеств.

№ слайда 27 Отображение, заданное между элементами одного множества Х, называют Отношение
Описание слайда:

Отображение, заданное между элементами одного множества Х, называют Отношением. Между математическими объектами такими отношениями могут быть {=, , , , <, }. Между “нематематическими” объектами {“x принадлежит y”, “x часть y”, “x смежный y”, “x родственник y”, “x родитель y”, “x находится рядом с y”,..}. Отношение

№ слайда 28 Бинарным или двуместным отношением между элементами множеств A и B называется
Описание слайда:

Бинарным или двуместным отношением между элементами множеств A и B называется любое подмножество R их декартова произведения A × B . Говорят также, что R является отношением из A в B. При A = B отношение R называется бинарным отношением на A. Вместо (x,y) R часто пишут xRy.) R часто пишут xRy. Бинарное отношение Бинарные отношения между элементами множества X удобно описывать матрицами (ХХ), строки и столбцы которых есть элементы множества. На пересечении i-ой строки и j-го столбца ставят знак “1”, если задано отношение r(i, j) между i-м и j-м элементами и “0” в противном случае

№ слайда 29 Симметричность Антисимметричность Асимметричность Транзитивность Антирефлекси
Описание слайда:

Симметричность Антисимметричность Асимметричность Транзитивность Антирефлексивность Свойства отношений Рефлексивность

№ слайда 30 Бинарное отношение рефликсивно, если для каждого хiХ имеем r(xi; xi)=1. Таки
Описание слайда:

Бинарное отношение рефликсивно, если для каждого хiХ имеем r(xi; xi)=1. Такими отношениями являются “..=..”, “..быть похожим..”, “..быть изоморфным..”, и т.п. При матричном описании такого отношения на главной диагонали матрицы будут только “1”, т.е. r(xi, xi)=1. Рефлексивность

№ слайда 31 Антисимметричность Бинарное отношение антисимметрично, если для любой пары (x
Описание слайда:

Антисимметричность Бинарное отношение антисимметрично, если для любой пары (xi, xj) при ij имеем r(xi, xi)r(xj, xi), а при i=j имеем r(xi, xi)=1. Такими отношениями являются “....”, “....” и т.п.. При матричном задании такого отношения это означает несимметричное расположение “1” относительно главной диагонали и наличие “1” на главной диагонали.

№ слайда 32 Симметричность Бинарное отношение симметрично, если для любой пары (xi, xj)R
Описание слайда:

Симметричность Бинарное отношение симметрично, если для любой пары (xi, xj)R имеем r(xi, xi)=r(xj, xi)=1. Такими отношениями являются “....”, “..быть похожим..”, “..быть эквивалентным..”, “..быть родственником..” и т.п.. При матричном задании такого отношения будет симметричное расположение “1” относительно главной диагонали, т.е. r(xi, xi)=r-1(xj, xi).

№ слайда 33 Антирефлексивность Бинарное отношение антирефлексивно, если для каждого хiХ
Описание слайда:

Антирефлексивность Бинарное отношение антирефлексивно, если для каждого хiХ имеем r(xi, xi)=0. Такими отношениями являются “.... ”, “..<..”, “быть родителем” и т.п. При матричном описании такого отношения на главной диагонали матрицы будут только “0”, т.е. r(xi, xi)=0.

№ слайда 34 Транзитивность Бинарное отношение транзитивно, если для любых элементов xi, x
Описание слайда:

Транзитивность Бинарное отношение транзитивно, если для любых элементов xi, xj, xkХ существует r(xi, xi)=1 тогда и только тогда, когда существует r(xi, xk)=1 и r(xk, xi)=1. Такими отношениями являются “....”, “..<..”, “быть родителем”, “быть родственником” и т.п..

№ слайда 35 Асимметричность Бинарное отношение асимметрично, если для любой пары (xi, xj)
Описание слайда:

Асимметричность Бинарное отношение асимметрично, если для любой пары (xi, xj) при i j имеем r(xi, xi)  r(xj, xi), а при i=j имеем r(xi, xi)=0. Такими отношениями являются “..  ..”, “..<..”, “быть родителем” и т.п. При матричном задании такого отношения это означает несимметричное расположение “1” относительно главной диагонали и наличие “0” на главной диагонали.

№ слайда 36 Бинарное отношение, удовлетворяющее условиям рефлексивности, симметричности и
Описание слайда:

Бинарное отношение, удовлетворяющее условиям рефлексивности, симметричности и транзитивности называют Отношением Эквиваленции. Симметричность Асимметричность Рефлексивность Отношения Эквиваленций = + + Отношения Эквиваленций Отношение эквиваленции обозначают r~(xi, xi) или ~(xi, xi).

№ слайда 37 II. Основы логики
Описание слайда:

II. Основы логики

№ слайда 38 Первые учения о формах и способах рассуждений возникли в странах Древнего Вос
Описание слайда:

Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные в 4 веке до нашей эры древне-греческими мыслителями . История логики Первым этапом на пути в развитии логики заложил Аристотель, создав основы формальной логики, где впервые отделил логические формы речи от ее содержания.

№ слайда 39 Вильгельм Готфрид Лейбниц (1646 - 1716) Второй этап – математическая логика,
Описание слайда:

Вильгельм Готфрид Лейбниц (1646 - 1716) Второй этап – математическая логика, основы которой заложил в своей работе "Об искусстве комбинаторики" (1666) великий немецкий философ, математик, физик и языковед Готфрид Вильгельм Лейбниц.

№ слайда 40 Джордж Буль (1815-1864) Основоположник математической логики считается Джордж
Описание слайда:

Джордж Буль (1815-1864) Основоположник математической логики считается Джордж Буль (1815-1864),английский математик. Поэтому начальный раздел математической логики часто называют булевой алгеброй или алгеброй логики.

№ слайда 41 В современное время для анализа и синтеза схем в ЭВМ при алгоритмизации и про
Описание слайда:

В современное время для анализа и синтеза схем в ЭВМ при алгоритмизации и программировании решения задач широко используется математический аппарат алгебры логики.

№ слайда 42 Алгебра логики – это раздел математики, изучающий высказывания, рассматриваем
Описание слайда:

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

№ слайда 43 Типы формальных систем Логика высказываний Логика предикатов Логика отношений
Описание слайда:

Типы формальных систем Логика высказываний Логика предикатов Логика отношений Нечеткая логика

№ слайда 44 Логика предикатов Логика предикатов (predicate calculus) есть формальная сист
Описание слайда:

Логика предикатов Логика предикатов (predicate calculus) есть формальная система, предметом которой являются предложения с учетом их внутренних состава и структуры.

№ слайда 45 Логика высказываний Логика высказываний (prepositional calculus) есть модель
Описание слайда:

Логика высказываний Логика высказываний (prepositional calculus) есть модель формальной системы, предметом которой являются повествовательные предложения, взятые целиком без учета их внутренней структуры. Логическое высказывание – это любое повествовательное предложение, в отношении которого можно сказать, истинно оно или ложно. Например, предложение «6-четное число» следует считать высказыванием, так как оно истинное. Предложение «Рим – столица Франции» тоже высказывание, так как оно ложное.

№ слайда 46 Нечеткая логика Логика нечеткая (fuzzi calculus) есть формальная система, пре
Описание слайда:

Нечеткая логика Логика нечеткая (fuzzi calculus) есть формальная система, предметом которой являются предложения при нечетком задании характер­ных признаков отдельных составляющих элементов или отношений между ними.

№ слайда 47 Логика отношений Логика отношений (relation calculus) есть формальная система
Описание слайда:

Логика отношений Логика отношений (relation calculus) есть формальная система, предметом которой являются отношения в виде множества однородных предложений, существенно расширяющие логику предикатов. Также эту логику называют реляционной.

№ слайда 48 Любое повествовательное предложение, которое может быть признано истинным или
Описание слайда:

Любое повествовательное предложение, которое может быть признано истинным или ложным, называют высказыванием. Высказывания, которые получаются из простых предложений с помощью грамматических связок “не”, “и”, “или”, “если…, то…”, “… тогда и только тогда, когда…” и т.п., называют сложными. Для обозначения грамматических связок в формальном языке вводят дополнительные символы, которые называют логическими связками. :=”или”, &:=“и”, :=”не”, :=“если…, то…”, :=“…тогда и только тогда, когда …”. Для построения сложных высказываний используют также вспомогательные символы “(“, “)” - скобки. Высказывание

№ слайда 49 Алгебра высказываний Модель алгебры высказываний. Множество T={A, B, C,…} с з
Описание слайда:

Алгебра высказываний Модель алгебры высказываний. Множество T={A, B, C,…} с заданными над ним логическими операциями F={; ; ; ;  } формируют модель алгебры высказываний Aв=<T; F>. Сложное высказывание, которое может быть получено из элементарных высказываний посредством применения логических связок, называют формулой алгебры логики.

№ слайда 50 Логические операции Логические операции бывают унарные (или одноместные) и би
Описание слайда:

Логические операции Логические операции бывают унарные (или одноместные) и бинарные (или двухместные). Это определяется наличием одного или двух операндов у операции. Символы логических операций заданы логическими связками:  - отрицание,  - конъюнкция,  - дизъюнкция,  - импликация,  - эквиваленция. Различные значения логической формулы в зависимости от значений входящих в нее элементарных высказываний, могут быть полностью описаны с помощью таблицы истинности.

№ слайда 51 Отрицание Логические операции Конъюнкция Дизъюнкция Импликация Эквиваленция
Описание слайда:

Отрицание Логические операции Конъюнкция Дизъюнкция Импликация Эквиваленция

№ слайда 52 Отрицание Отрицание (операция НЕ) есть одноместная операция, посредством кото
Описание слайда:

Отрицание Отрицание (операция НЕ) есть одноместная операция, посредством которой ее значение есть отрицание значения операнда. ( F) Обозначение: Таблица логического отрицания А Х 0 1 1 0

№ слайда 53 Конъюнкция Конъюнкция есть двухместная операция, посредством которой из двух
Описание слайда:

Конъюнкция Конъюнкция есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F=(F1F2), описывающую сложное высказывание. Значение этого высказывания истинно тогда и только тогда, когда истинны значения двух операндов F1 и F2. (F1F2) Обозначение: Таблица логического умножения А В Х 0 0 0 0 1 0 1 0 0 1 1 1

№ слайда 54 Дизъюнкция есть двухместная операция, посредством которой из двух формул F1 и
Описание слайда:

Дизъюнкция есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F=(F1F2), описывающую сложное высказывание. Значение этого высказывания ложно тогда и только тогда, когда ложны значения двух операндов F1 или F2. (F1F2) Обозначение: Дизъюнкция Таблица логического сложения А В Х 0 0 0 0 1 1 1 0 1 1 1 1

№ слайда 55 Эквиваленция Таблица логической эквивалентности Обозначение: Эквиваленция ест
Описание слайда:

Эквиваленция Таблица логической эквивалентности Обозначение: Эквиваленция есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F=(F1F2), описывающую сложное высказывание. Значение этого высказывания истинно тогда и только тогда, когда оба операнда F1 и F2 имеют одинаковые значения. (F1F2) А В Х 0 0 1 0 1 1 1 0 0 1 1 1

№ слайда 56 Импликация есть двуместная операция, посредством ко­торой отражающую сложное
Описание слайда:

Импликация есть двуместная операция, посредством ко­торой отражающую сложное высказывание. Значение этого высказывания ложно тогда и только тогда, когда истинно значение F1 и ложно F2. (F1F2) Обозначение: Импликация Таблица логического следования А В Х 0 0 1 0 1 0 1 0 0 1 1 1

№ слайда 57 Законы Алгебры Логики Законы Алгебры Логики Наименование закона	Равносильные
Описание слайда:

Законы Алгебры Логики Законы Алгебры Логики Наименование закона Равносильные формулы Fi=Fj Коммутативности (F1F2)=(F2F1); (F1F2)=(F2F1) Ассоциативности F1(F2F3)=(F1F2)F3; F1(F2F3) = (F1F2) F3 Дистрибутивности F1(F2F3)=(F1F2)(F1F3); F1(F2F3)=F1F2F1F3 Идемпотентности FF = F; FF = F Исключенного третьего FF = и; Противоречия FF = л Де Моргана (F1F2) = F1F2; (F1F2) = F1F2 . Поглощения F1(F1F2) = F1; F1(F1F2) = F1 Дополнения (F) = F Свойства констант Fл = F; Fи = и; Fл= л; Fи = F

№ слайда 58 III.Графы и деревья
Описание слайда:

III.Графы и деревья

№ слайда 59 Теория графов находит самое широкое применение в моделировании информационных
Описание слайда:

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

№ слайда 60 Первая работа по теории графов была опубликована математиком Л. Эйлером в 173
Описание слайда:

Первая работа по теории графов была опубликована математиком Л. Эйлером в 1736г. в Трудах Академии наук Санкт-Петербурга в виде задачи о Кенигсбергских мостах. Суть задачи сводилась к следующему: мог ли житель Кенигсберга, выйдя из дома, находящегося на части суши A, B, С или D, пройти по семи мостам через реку Прегель в точности по одному разу и вернуться домой? Ответ на этот вопрос был отрицательным. История графов Для пояснения задачи представлена модель, где каждый участок суши замещен точкой на плоскости, а мосты – линиями, связывающими участки.

№ слайда 61 Совокупность объектов произвольной природы и отношений между каждой парой эти
Описание слайда:

Совокупность объектов произвольной природы и отношений между каждой парой этих объектов может быть изображена на плоскости в виде множества точек, являющихся образом множества объектов, и множества отрезков линий, соединяющих пары точек, что является образом множества отношений. Такой образ объектов и отношений принято называть графом. Множество точек, являющихся образом множества объектов, называют вершинами графа, а множество отрезков линий, являющихся образом множества отношений, - рёбрами или дугами графа.

№ слайда 62 Вершинами графа могут быть операторы программы или команды операционной систе
Описание слайда:

Вершинами графа могут быть операторы программы или команды операционной системы, контактные площадки на плате компьютера, узлы транспортной или электрической сети, события в любой сфере человеческой деятельности. Рёбрами или дугами – связи операторов программы, команд операционной системы, контактных площадок на плате компьютера, узлов в транспортной или в электрической сети или причинно-следственные связи событий в любой сфере человеческой деятельности. Вершина Ребро

№ слайда 63 Ориентированный граф - это пара (V, E), где V - конечное множество вершин (уз
Описание слайда:

Ориентированный граф - это пара (V, E), где V - конечное множество вершин (узлов, точек) графа, а E - некоторое множество пар вершин, т.е. подмножество множества V × V или бинарное отношение на V. Элементы E называют ребрами (дугами, стрелками, связями). Для ребра e=(u,v) E вершина u называется началом e, а вершина v - концом e, говорят, что ребро e ведет из u в v. V1={ a,b,c,d}, E1={ (a,b), (a,c), (b,b), (b,d), (d,a)}, G1=(V1, E1) Ориентированный граф

№ слайда 64 Неориентированный граф G=(V, E) - это ориентированный граф, у которого для ка
Описание слайда:

Неориентированный граф G=(V, E) - это ориентированный граф, у которого для каждого ребра (u,v) E имеется противоположное ребро (v,u) E, т.е. отношение E симметрично. Для его задания можно использовать обозначение для множества концов: {u, v}, но чаще используется указание одной из пар в круглых скобках. Если e= (u,v) E, то вершины u и v называются смежными в G, а ребро e и эти вершины называются инцидентными. Степенью вершины в неориентированном графе называется число смежных с ней вершин. Вершина степени 0 называется изолированной. Такая пара (u,v), (v,u) называется неориентированным ребром G2=(V2, E2 ) V2={ a,b,c,d}, E2={ (a,b), (a,c), (a,d), (b,d)} Неориентированный граф

№ слайда 65 Деревья Деревья являются одним из интереснейших классов графов, используемых
Описание слайда:

Деревья Деревья являются одним из интереснейших классов графов, используемых для представления различного рода иерархических структур. Неориентированный граф называется деревом, если он связный и в нем нет циклов. Ориентированный граф G=(V,E) называется (ориентированным) деревом, если: в нем есть одна вершина, в которую не входят ребра; она называется корнем дерева в каждую из остальных вершин входит ровно по одному ребру; все вершины достижимы из корня.

№ слайда 66 Способы обхода деревьев. Часто при обработке представленной в дереве информац
Описание слайда:

Способы обхода деревьев. Часто при обработке представленной в дереве информации требуется обойти некоторым регулярным способом все его вершины. Способы позволяют линейно упорядочить вершины дерева и тем самым представить его "двумерную структуру" в виде линейной последовательности вершин. Способы обхода деревьев Прямой Обратный основан на принципе: "сначала родитель, затем дети" основан на противоположном принципе: "сначала дети, затем родитель".

№ слайда 67 Литература: 1.Информатика Учеб. для студентов эконом. спец. вузов/под ред.Мак
Описание слайда:

Литература: 1.Информатика Учеб. для студентов эконом. спец. вузов/под ред.Макаровой.-3-е изд., - М.: Финансы и статистика, 2007.-с.124-127 2.Угринович Н.Д. Практикум по информатике и информационным технологиям. Учебное пособие для общеобразовательных учреждений. Изд.2-е, испр.-М.: БИНОМ. Лаборатория знаний, 2004, с.84-108 3.Дехтярь М.И. Лекции по дискретной математике. БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2007 4.Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений. БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2006 5.Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов. БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2007

№ слайда 68 ??? Контрольные вопросы: Что такое множества? Что такое функция? Какие сущест
Описание слайда:

??? Контрольные вопросы: Что такое множества? Что такое функция? Какие существуют функции? Способы заданий функций? Какие существуют операции над множествами? Что такое отношение? Что такое математическая логика? Перечислите логические операции? Что такое графы? Как представлены деревья? Как классифицируются графы?

№ слайда 69 Спасибо За Внимание!!!
Описание слайда:

Спасибо За Внимание!!!

Краткое описание документа:

Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные в 4 веке до нашей эры древне-греческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы речи от ее содержания –это явилось первым этапом в развитии логики. Второй этап – математическая логика, основы которой заложил в своей работе «Об искусстве комбинаторики» (1666) великий немецкий философ, математик, физик и  языковед Готфрид Вильгельм Лейбниц(1646-1716). Великий русский и швейцарский ученый Леонард  Эйлер (1707-1783)  с  1727г.  по 1741г.  работал в России. С 1766г. был избран академиком Петербургской АН. Ученый необычайной широты интересов. Автор свыше 800 работ  по  математике, физике, небесной  механике, оптике, баллистике, кораблестроению, теории музыки. Предложил так называемые круги Эйлера, ставшие основой формальной логики. Однако основоположником математической  логики  считается  Джордж Буль (1815-1864),английский математик, отец всемирно известной писательницы Этель Лилиан Войнич (роман «Овод»). Поэтому начальный раздел математической логики часто называют булевой алгеброй или алгеброй логики.             Для анализа и синтеза схем в ЭВМ при алгоритмизации и программировании решения задач широко используется математический аппарат алгебры логики.
Автор
Дата добавления 21.05.2014
Раздел Информатика
Подраздел Презентации
Просмотров1069
Номер материала 109947052120
Получить свидетельство о публикации

Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх