1591141
столько раз учителя, ученики и родители
посетили сайт «Инфоурок»
за прошедшие 24 часа
Добавить материал и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
ИнфоурокИнформатикаПрезентацииОсновы дискретной математики

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

библиотека
материалов
Костанайский Государственный Университет им. Ахмета Байтурсынова Автор презен...
“Теперь в математике остаются только целые числа и конечные... системы целых...
Основное отличие дискретной математики от классической заключается в отсутств...
Тема: Основы дискретной математики
Цель: Цель: Рассмотреть основные понятия множества, основ логики, теории граф...
Задачи Лекции: 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.Информатика Учеб. для студентов эконом. спец. вузов/под ред.Мак...
??? Контрольные вопросы: Что такое множества? Что такое функция? Какие сущест...
Спасибо За Внимание!!!
Labirint.ru - ваш проводник по лабиринту книг

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

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 слайд Спасибо За Внимание!!!
Описание слайда:

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

Курс профессиональной переподготовки
Учитель информатики
Labirint.ru - ваш проводник по лабиринту книг
Найдите материал к любому уроку,
указав свой предмет (категорию), класс, учебник и тему:
также Вы можете выбрать тип материала:
Краткое описание документа:
Первые учения о формах и способах рассуждений возникли в странах Древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные в 4 веке до нашей эры древне-греческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы речи от ее содержания –это явилось первым этапом в развитии логики. Второй этап – математическая логика, основы которой заложил в своей работе «Об искусстве комбинаторики» (1666) великий немецкий философ, математик, физик и  языковед Готфрид Вильгельм Лейбниц(1646-1716). Великий русский и швейцарский ученый Леонард  Эйлер (1707-1783)  с  1727г.  по 1741г.  работал в России. С 1766г. был избран академиком Петербургской АН. Ученый необычайной широты интересов. Автор свыше 800 работ  по  математике, физике, небесной  механике, оптике, баллистике, кораблестроению, теории музыки. Предложил так называемые круги Эйлера, ставшие основой формальной логики. Однако основоположником математической  логики  считается  Джордж Буль (1815-1864),английский математик, отец всемирно известной писательницы Этель Лилиан Войнич (роман «Овод»). Поэтому начальный раздел математической логики часто называют булевой алгеброй или алгеброй логики.             Для анализа и синтеза схем в ЭВМ при алгоритмизации и программировании решения задач широко используется математический аппарат алгебры логики.
Общая информация
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону N273-ФЗ «Об образовании в Российской Федерации» педагогическая деятельность требует от педагога наличия системы специальных знаний в области обучения и воспитания детей с ОВЗ. Поэтому для всех педагогов является актуальным повышение квалификации по этому направлению!

Дистанционный курс «Обучающиеся с ОВЗ: Особенности организации учебной деятельности в соответствии с ФГОС» от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (72 часа).

Подать заявку на курс

Вам будут интересны эти курсы:

Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
Курс профессиональной переподготовки «Информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Облачные технологии в образовании»
Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»
Курс профессиональной переподготовки «Информационные технологии в профессиональной деятельности: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Введение в программирование на языке С (СИ)»
Курс профессиональной переподготовки «Управление в сфере информационных технологий в образовательной организации»
Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»
Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Специфика преподавания дисциплины «Информационные технологии» в условиях реализации ФГОС СПО по ТОП-50»
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.
Labirint.ru - ваш проводник по лабиринту книг
Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.