Математическая логика и теория алгоритмов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Математическая логика и теория алгоритмов, слайд №1

Математическая логика и теория алгоритмов, слайд №2

Математическая логика и теория алгоритмов, слайд №3

Математическая логика и теория алгоритмов, слайд №4

Математическая логика и теория алгоритмов, слайд №5

Математическая логика и теория алгоритмов, слайд №6

Математическая логика и теория алгоритмов, слайд №7

Математическая логика и теория алгоритмов, слайд №8

Математическая логика и теория алгоритмов, слайд №9

Математическая логика и теория алгоритмов, слайд №10

Математическая логика и теория алгоритмов, слайд №11

Математическая логика и теория алгоритмов, слайд №12

Математическая логика и теория алгоритмов, слайд №13

Математическая логика и теория алгоритмов, слайд №14

Математическая логика и теория алгоритмов, слайд №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

Математическая логика и теория алгоритмов, слайд №44

Математическая логика и теория алгоритмов, слайд №45

Математическая логика и теория алгоритмов, слайд №46

Математическая логика и теория алгоритмов, слайд №47

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Математическая логика и теория алгоритмов. Доклад-сообщение содержит 47 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Математическая логика и теория алгоритмов каф. ПМиК доцент , к. ф.-м. н. Мачикина Елена Павловна

Слайд 2

Описание слайда:

Электронные ресурсы Режим доступа: Балюкевич Э.Л. Математическая логика и теория алгоритмов [Электронный ресурс]: учебное пособие/ Балюкевич Э.Л., Ковалева Л.Ф.— Электрон. текстовые данные.— М.: Евразийский открытый институт, 2009.— 188 c.— Маньшин М.Е. Математическая логика и теория алгоритмов [Электронный ресурс]: учебное пособие/ Маньшин М.Е.— Электрон. текстовые данные.— Волгоград: Волгоградский институт бизнеса, Вузовское образование, 2009.— 106 c. Жоль К.К. Логика [Электронный ресурс]: учебное пособие для вузов/ Жоль К.К.— Электрон. текстовые данные.— М.: ЮНИТИ-ДАНА, 2012.— 400 c. Новиков Ф. А. Дискретная математика для программистов: учеб. пособие /. - 3- изд. - СПб.: ПИТЕР, 2009. - 383с.

Слайд 3

Описание слайда:

Электронные ресурсы Режим доступа: ЭБС «IPRbooks», по паролю Лавров И.А. Задачи по теории множеств, математической логике и теории алгоритмов Верещагин Н.К. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления Верещагин Н.К. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции

Слайд 4

Описание слайда:

Электронные ресурсы Бесплатный доступ после регистрации

Слайд 5

Описание слайда:

1. Теория булевых функций 2. Логические исчисления 3. Алгоритмические системы

Слайд 6

Описание слайда:

1. Булевы функции

Слайд 7

Описание слайда:

1.1 Определения

Слайд 8

Описание слайда:

Функция f:{0,1}n{0,1} от n переменных x1, x2, …, xn называется булевой

Слайд 9

Описание слайда:

Утверждение Для булевой функции от n аргументов существует 2n различных наборов аргументов.

Слайд 10

Описание слайда:

Поскольку каждая булева функция имеет конечное количество наборов аргументов, то булеву функцию можно задать в виде таблицы

Слайд 11

Описание слайда:

Базовые логические связки – отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция

Слайд 12

Описание слайда:

Слайд 13

Описание слайда:

Из логических переменных с помощью логических связок можно составлять конструкции, которые образуют формулы алгебры логики Пусть {xi | iI} – некоторое множество логических переменных. Определим рекурсивно понятие формулы алгебры логики: любая логическая переменная является формулой (атомарной); если  и  – формулы, то выражения ,  x , где x – логическая операция, являются формулами; никаких других формул нет.

Слайд 14

Описание слайда:

Пусть даны формулы булевых функций F(y1, y2, …, ym ), f1(x1, x2, …, xn ), …, fm(x1, x2, …, xn ). Тогда подстановкой формул fi в формулу F называется следующая конструкция: (F| yi fi )(x1, x2, …, xn)  F(f1(x1, x2, …, xn ), …, fm(x1, x2, …, xn )).

Слайд 15

Описание слайда:

Пример F(y1, y2 )= y1~ y2 f1(x1, x2 )= x1 f2(x1, x2 )= x1& x2 (F| yi fi )(x1, x2) = x1 ~ (x1& x2)

Слайд 16

Описание слайда:

Теорема (О подстановке формул) Если F(y1, y2, …, ym ) и fi (x1, x2, …, xn ) – формулы алгебры логики, то (F| yi fi )(x1, x2, …, xn ) также является формулой.

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

Правило подстановки Если в равносильных формулах: F(y1, y2, …, ym ) G(y1, …, ym ) – вместо всех вхождений некоторой переменной yi подставить одну и ту же формулу, то получатся равносильные формулы. Правило замены Если в формуле F заменить некоторую подформулу yi на равносильную gi, то получатся равносильные формулы.

Слайд 19

Описание слайда:

ФАЛ, при образовании которых используются только операции отрицания, конъюнкции и дизъюнкции, называются булевыми формулами. Теорема Для любой формулы алгебры логики существует равносильная ей булева формула.

Слайд 20

Описание слайда:

Множество булевых функций с определенными на нем операциями отрицания, конъюнкции и дизъюнкции называется булевой алгеброй. Множество булевых функций от n аргументов будем обозначать Pn.

Слайд 21

Описание слайда:

Для булевых функций выполняется ряд равносильностей Операции с константами: 1) A  1  1;A & 1  A; 2)A  0  A; A & 0  0. Противоречие: A & A  0. Исключение третьего: A  A  1. Идемпотентность: A & A  A; A  A  A. Двойное отрицание:  A  A. Коммутативность:A & B  B & A; A  B  B  A. Ассоциативность: (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). Законы де Моргана: (A&B)  A  B; (AB)  A & B.

Слайд 22

Описание слайда:

при выполнении преобразований часто используются законы поглощения: 1) A & (A  B)  A; A  A & B  A; 2)A & (A  B)  A & B; A  A & B  A  B. А также А→В ¬АvВ; А~В  (А→В )&(В →А)

Слайд 23

Описание слайда:

1.2 Принцип двойственности

Слайд 24

Описание слайда:

Пусть f(x1, x2, …, xn ) – булева функция. Двойственной к ней называется функция f*(x1, x2, …, xn )  ¬f (¬ x1, ¬ x2, …, ¬ xn ). Из определения видно, что f**=f. Если двойственная функция f* совпадает с исходной функцией f, то такая функция f называется самодвойственной.

Слайд 25

Описание слайда:

Пример f1(x1 )= x1 f2(x1, x2 )= x1& x2 f1 *(x1 )= ¬f1(¬ x1 )= x1 f2* (x1, x2 )= ¬ f2(¬ x1, ¬ x2 )= = ¬ (¬ x1& ¬ x2)= x1V x2

Слайд 26

Описание слайда:

Теорема (Общий принцип двойственности) Если G(x1, …, xn ) получена подстановкой формул fi из F(y1, …, ym ) G(x1, …, xn ) (F| yi fi )(x1, …, xn ), то G*(x1, …, xn ) (F*| yi f*i )(x1, …, xn ).

Слайд 27

Описание слайда:

Теорема (Принцип двойственности для булевых функций) Двойственная к булевой функции может быть получена заменой констант 0 на 1, 1 на 0, дизъюнкции на конъюнкцию, конъюнкции на дизъюнкцию и сохранением структуры формулы (т.е. соответствующего исходному порядка действий).

Слайд 28

Описание слайда:

Булевы функции с операциями умножения и сложения по модулю 2 образуют алгебру Жегалкина. Аксиомы алгебры Жегалкина: Операции с константами: A1  A; A0  0; A  0  A. Идемпотентность: AA  A; A  A  0. Коммутативность: AB  BA; A  B  B  A. Ассоциативность: (A  B)  C  A (B  C); (AB)C  A(BC). Дистрибутивность: A(B  C)  AB  AC. Можно перейти от алгебры Буля к алгебре Жегалкина, используя следующие соотношения: A  1 A; AB=A  B  AB. И наоборот, от алгебры Жегалкина к алгебре Буля: A  B =AB AB Перейти к выражению булевой алгебры: (x  1)y (x  1) = xy x = xyx  xxy = (x y)x  0 =xy.

Слайд 29

Описание слайда:

1.3 Нормальные формы

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

Элементарной дизъюнкцией (конъюнкцией) называется дизъюнкция переменных и/или их отрицаний ДНФ – это дизъюнкция элементарных конъюнкций. КНФ – это конъюнкция элементарных дизъюнкций.

Слайд 32

Описание слайда:

ДНФ (КНФ) называется совершенной, если каждая переменная формулы входит в каждую элементарную конъюнкцию (дизъюнкцию) ровно один раз.

Слайд 33

Описание слайда:

Примеры Элементарные дизъюнкции: xy, z. Элементарные конъюнкции: x&¬y&z, x. f(x,y,z) = x&y&z ¬x&y – ДНФ f(x,y,z) = (xy)&z – КНФ.

Слайд 34

Описание слайда:

X & Y

Слайд 35

Описание слайда:

Введем обозначения

Слайд 36

Описание слайда:

Теорема О разложении булевой функции по k переменным

Слайд 37

Описание слайда:

n=3, k=2

Слайд 38

Описание слайда:

Доказательство Выберем какой-либо набор значений для переменных x1, …, xn. Пусть это будет 1, …, n. Заметим, что

Слайд 39

Описание слайда:

Подставим в правую часть формулировки теоремы вместо x1, …, xn набор 1, …, n. Получим. Поскольку коэффициент перед функцией равен 1 только при равных значениях i и i, в разложении останется только один член и i=i, т.е.

Слайд 40

Описание слайда:

Получена левая часть формулы теоремы. Поскольку набор был выбран произвольно, получаем, что утверждение верно любого набора x1, …, xn

Слайд 41

Описание слайда:

Следствие 1 Разложение Шеннона

Слайд 42

Описание слайда:

Следствие 2 При k=n

Слайд 43

Описание слайда:

Построение СДНФ 1. Найти строки в таблице истинности , где значение функции f истинное. 2. Каждому найденному набору 1, …, n. поставить в соответствие конъюнкцию где 3. Составить дизъюнкцию из полученных конъюнкций

Слайд 44

Описание слайда:

Построение СКНФ 1. Найти строки в таблице истинности , где значение функции f ложное. 2. Каждому найденному набору 1, …, n. поставить в соответствие дизъюнкцию где 3. Составить конъюнкцию из полученных дизъюнкций

Слайд 45

Описание слайда:

Получение из ДНФ. Если некоторое произведение ДНФ не содержит какой-либо переменной, то необходимо домножить это произведение на дизъюнкцию этой переменной и ее отрицания и применить дистрибутивный закон.

Слайд 46

Описание слайда:

Получение из КНФ. Если некоторая элементарная дизъюнкция КНФ не содержит какой-либо переменной, то необходимо дизъюнктивно добавить в нее произведение этой переменной и ее отрицания и применить дистрибутивный закон.