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

Категория: Математика
Нажмите для полного просмотра!
Компьютерная дискретная математика. Нормальные формы, слайд №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 .
Описание слайда:
Совершенная нормальная форма Среди множества эквивалентных формул, представляющих выбранную булеву функцию f, выделяется одна формула, которая называется совершенной нормальной формой функции f, имеет регламентированную логическую структуру и однозначно определяется по функции f .

Слайд 3


Обозначения x,σB={0,1}
Описание слайда:
Обозначения x,σB={0,1}

Слайд 4


Теорема о дизъюнктивном разложении функции f(x1,…,xn) по k переменным Любую булеву функцию f(x1,x2,…,xn) можно представить в следующей форме:
Описание слайда:
Теорема о дизъюнктивном разложении функции 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.
Описание слайда:
Теорема о дизъюнктивном разложении функции Запись означает многократную дизъюнкцию, которая берется по всем возможным наборам значений (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.
Описание слайда:
Пример Получить дизъюнктивное разложение функции по переменным 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)
Описание слайда:
Дизъюнктивное разложение булевой функции 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
Описание слайда:
Дизъюнктивное разложение булевой функции 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 .
Описание слайда:
Определения и понятия Элементарной конъюнкцией называется конъюнкция любого числа булевых переменных, взятых с отрицанием или без него, в которой каждая переменная встречается не более одного раза. Примеры Элементарными конъюнкциями для функции от одной переменной могут быть 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.
Описание слайда:
Определения и понятия Элементарная конъюнкция 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). Конституента единицы обладает следующими свойствами: Конституента единицы равна единице только на соответствующей ей интерпретации. Конституента единицы однозначно определяется номером соответствующей ей интерпретации. Конъюнкция любого числа различных конституент единицы функции равна нулю.
Описание слайда:
Свойства конституенты единицы Конституента единицы функции 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) существует представление в виде формулы булевой алгебры, содержащей только операции дизъюнкции, конъюнкции и отрицания.
Описание слайда:
Следствия из определений СДНФ и СКНФ булевых функций Для каждой булевой функции f(x1,x2,…,xn), не являющейся константой нуля, существует представление в виде СДНФ. Для каждой булевой функции f(x1,x2,…,xn), не являющейся константой единицы, существует представление в виде СКНФ. Две различные булевы функции не могут иметь одинаковые СДНФ или СКНФ. Для каждой булевой функции f(x1,x2,…,xn) существует представление в виде формулы булевой алгебры, содержащей только операции дизъюнкции, конъюнкции и отрицания.

Слайд 17


Пример конституент 1 и конституент 0
Описание слайда:
Пример конституент 1 и конституент 0

Слайд 18


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

Слайд 19


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

Слайд 20


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

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


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

Слайд 25


Примеры Пример 1. Переход от СДНФ к таблице истинности Пример 2. Переход от СКНФ к таблице истинности
Описание слайда:
Примеры Пример 1. Переход от СДНФ к таблице истинности Пример 2. Переход от СКНФ к таблице истинности

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию