Компьютерная дискретная математика. Нормальные формы - презентация, доклад, проект скачать

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

Компьютерная дискретная математика. Нормальные формы, слайд №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

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

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

Слайд 3

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

Обозначения x,σB={0,1}

Слайд 4

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

Теорема о дизъюнктивном разложении функции f(x1,…,xn) по k переменным Любую булеву функцию f(x1,x2,…,xn) можно представить в следующей форме:

Слайд 5

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

Теорема о дизъюнктивном разложении функции Запись означает многократную дизъюнкцию, которая берется по всем возможным наборам значений (1,2,…,k) при любом k (1≤k≤n). f(1,2,…,k,xk+1,…,xn) представляет значение функции на интерпретации x1,x2,…,xn, когда вместо значений переменных x1,x2,…,xk, по которым ведется разложение, подставлены значения 1,2,…,k.

Слайд 6

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

Пример Получить дизъюнктивное разложение функции по переменным x, z.

Слайд 7

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

Дизъюнктивное разложение булевой функции f(x1,x2,…,xn) по одной переменной Любую булеву функцию f(x1,x2,…,xn) можно представить в следующей форме: f(x1, x2, …, xn)=xiσi f(x1, x2, …, xi-1, i, xi+1, …, xn)

Слайд 8

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

Дизъюнктивное разложение булевой функции f(x1,x2,…,xn) по всем n переменным Любую булеву функцию f(x1,x2,…,xn)0 можно представить в следующей форме: f(x1,x2,…,xn) =  x11x22… xnn (1,2,…,n) f(1,2,…,n) = 1

Слайд 9

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

Пример Получить дизъюнктивное разложение функции по всем переменным. Определим значение функции на каждой из интерпретаций:

Слайд 10

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

Определения и понятия Элементарной конъюнкцией называется конъюнкция любого числа булевых переменных, взятых с отрицанием или без него, в которой каждая переменная встречается не более одного раза. Примеры Элементарными конъюнкциями для функции от одной переменной могут быть y, , двух переменных y, x трех переменных x z , x   , x yz .

Слайд 11

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

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

Слайд 12

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

Определения и понятия Элементарная конъюнкция x11x22… xnn называется конституентой единицы (минтермом) функции f(x1,x2,…,xn), если f(1,2,…,n)=1, то есть интерпретация, обращающая в единицу данную элементарную конъюнкцию, обращает в единицу и функцию f.

Слайд 13

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

Свойства конституенты единицы Конституента единицы функции n переменных имеет вид x11x22…xnn и соответствует интерпретации (1,2,…,n). Конституента единицы обладает следующими свойствами: Конституента единицы равна единице только на соответствующей ей интерпретации. Конституента единицы однозначно определяется номером соответствующей ей интерпретации. Конъюнкция любого числа различных конституент единицы функции равна нулю.

Слайд 14

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

Определение и понятия Совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции называется формула, представленная в виде дизъюнкции конституент единицы данной функции. Примеры:

Слайд 15

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

Определения и понятия Совершенной конъюнктивной нормальной формой (СКНФ) функции называется формула, представленная в виде конъюнкции конституент нуля данной функции. Примеры

Слайд 16

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

Следствия из определений СДНФ и СКНФ булевых функций Для каждой булевой функции f(x1,x2,…,xn), не являющейся константой нуля, существует представление в виде СДНФ. Для каждой булевой функции f(x1,x2,…,xn), не являющейся константой единицы, существует представление в виде СКНФ. Две различные булевы функции не могут иметь одинаковые СДНФ или СКНФ. Для каждой булевой функции f(x1,x2,…,xn) существует представление в виде формулы булевой алгебры, содержащей только операции дизъюнкции, конъюнкции и отрицания.

Слайд 17

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

Пример конституент 1 и конституент 0

Слайд 18

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

Алгоритм перехода от таблицы истинности булевой функции к СДНФ Выделить все интерпретации (1,2,…,n), на которых значение функции равно единице. Записать конституенты единицы вида x11x22…xnn, соответствующие отмеченным интерпретациям. Получить СДНФ функции посредством соединения операцией дизъюнкции записанных конституент единицы.

Слайд 19

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

Алгоритм перехода от таблицы истинности булевой функции к СДНФ. Пример Получить СДНФ для функций f13(x,y).

Слайд 20

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

Алгоритм перехода от таблицы истинности булевой функции к СКНФ Выделить все интерпретации (1,2,…,n), на которых значение функции равно нулю Записать конституенты нуля вида , соответствующие выделенным интерпретациям. Записав конъюнкцию конституент нуля, получить СКНФ функции.

Слайд 21

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

Алгоритм перехода от таблицы истинности булевой функции к СКНФ Пример Получить СКНФ для функций f7(x,y) и f9(x,y).

Слайд 22

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

Алгоритм построения таблицы истинности функции, заданной СДНФ Построить таблицу истинности, содержащую 2n интерпретаций вида (1,2,…,n). Отметить в таблице истинности все интерпретации (1,2,…,n), соответствующие конституентам единицы вида из заданной СДНФ. Напротив выделенных интерпретаций в столбец значения функции записать единицы. Напротив оставшихся интерпретаций в столбец значения функции записать нули.

Слайд 23

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

Алгоритм перехода от произвольной формулы алгебры логики к СДНФ Исключить константы, используя законы действий с константами. Опустить знаки отрицания непосредственно на переменные, используя законы де Моргана. Используя дистрибутивный закон, раскрыть скобки. К полученным элементарным конъюнкциям применить законы идемпотентности и противоречия, упростить их и привести подобные. Результатом выполнения указанных действий является получение ДНФ булевой функции.

Слайд 24

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

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