- Главная
- Математика
- Булевы (гулевы) функции
Содержание
- 2. Что такое булева алгебра? Булевой алгеброй называется непустое множество AA с двумя бинарными операциями ∧∧ (аналог
- 3. Суперпозиции Суперпозиция функций, композиция функций — функция, полученная из некоторого множества функций путем подстановки одной функции
- 4. ДНФ и КНФ Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, выражение является ДНФ. Конъюнктивной
- 5. Двойственная функция Будем называть булеву функцию f*(x1,x2,…,xn), n1, двойственной относительно функции f(x1,x2,…,xn), если она получена из
- 7. Скачать презентацию
Слайд 2Что такое булева алгебра?
Булевой алгеброй называется непустое множество AA с двумя бинарными операциями ∧∧ (аналог конъюнкции), ∨∨ (аналог дизъюнкции),
Что такое булева алгебра?
Булевой алгеброй называется непустое множество AA с двумя бинарными операциями ∧∧ (аналог конъюнкции), ∨∨ (аналог дизъюнкции),
В алгебре логики основными (элементарными) операциями являются отрицание, логическое сложение (дизъюнкция), логическое умножение (конъюнкция), импликация, эквивалентность.
При упрощении булевых формул или высказываний, связанных скобками и логическими операциями, используют следующие правила приоритета (или старшинства) логических операций - от наиболее сильной - к слабой:
¬∧∨→↔
Словесно: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.
Слайд 3Суперпозиции
Суперпозиция функций, композиция функций — функция, полученная из некоторого множества функций путем подстановки
Суперпозиции
Суперпозиция функций, композиция функций — функция, полученная из некоторого множества функций путем подстановки
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.
Пусть нам дан некоторый набор булевых функций K. Получить новую функцию, являющеюся композицией функций из K, мы можем следующими способами:
1) Подстановкой одной функции в качестве некоторого аргумента для другой;
2) Отождествлением аргументов функций.
Слайд 4ДНФ и КНФ
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, выражение
ДНФ и КНФ
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, выражение
Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций. Например, выражение является КНФ.
Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные (либо сами, либо их отрицания). Например, выражение является ДНФ, но не СДНФ. Выражение же представляет собой СДНФ.
Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные (либо сами, либо их отрицания). Например, выражение представляет собой СКНФ.
Слайд 5Двойственная функция
Будем называть булеву функцию f*(x1,x2,…,xn), n1, двойственной относительно функции f(x1,x2,…,xn), если
Двойственная функция
Будем называть булеву функцию f*(x1,x2,…,xn), n1, двойственной относительно функции f(x1,x2,…,xn), если
f*(x1, x2,…, xn) f '(x1', x2',…, xn').
Замечание. При n=0 полагают, что функция 0 двойственна 1, а 1 двойственна 0.