Совершенная дизъюнктивная нормальная форма — различия между версиями
Материал из ALL
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
м |
||
(не показано 7 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
'''Совершенная дизъюнктивная нормальная форма (СДНФ)''' для '''[[Логическая функция|логической функции]]''' – это дизъюнкция различных элементарных конъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. | '''Совершенная дизъюнктивная нормальная форма (СДНФ)''' для '''[[Логическая функция|логической функции]]''' – это дизъюнкция различных элементарных конъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. | ||
При этом '''[[Таблица истинности|таблицы истинности]]''' для логической функции и её СДНФ совпадают. | При этом '''[[Таблица истинности|таблицы истинности]]''' для логической функции и её СДНФ совпадают. | ||
− | + | == Обозначения == | |
− | == | + | |
− | + | ||
− | + | ||
'''n''' – число аргументов функции; | '''n''' – число аргументов функции; | ||
Строка 16: | Строка 13: | ||
'''arg<sub>j</sub>[f(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)=1]''' – значение аргумента '''x<sub>j</sub>''' в фиксированном наборе аргументов. | '''arg<sub>j</sub>[f(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>n</sub>)=1]''' – значение аргумента '''x<sub>j</sub>''' в фиксированном наборе аргументов. | ||
− | + | == Формула == | |
[[файл:СДНФ01.JPG]] | [[файл:СДНФ01.JPG]] | ||
[[файл:СДНФ10.JPG]] – элементарная конъюнкция. | [[файл:СДНФ10.JPG]] – элементарная конъюнкция. | ||
− | + | *Для логической функции выбираются лишь те комбинации, которые приводят логическое выражение в состояние единицы. | |
− | * Для логической функции выбираются лишь те комбинации, которые приводят логическое выражение в состояние единицы. | + | |
В элементарную конъюнкцию записывается переменная без инверсии, если она в наборе равна 1, и с инверсией, если она равна 0. | В элементарную конъюнкцию записывается переменная без инверсии, если она в наборе равна 1, и с инверсией, если она равна 0. | ||
− | |||
== Пример == | == Пример == | ||
[[файл:СДНФ11.JPG]] | [[файл:СДНФ11.JPG]] | ||
− | + | == [[Логическая функция|Другие формы:]] == | |
− | == Другие формы: == | + | {{Список ЛФор}} |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
== Ссылки == | == Ссылки == | ||
− | * [[Участник:Logic-samara]] | + | *[[Участник:Logic-samara]] |
− | [[Категория:Дискретная математика]][[Категория:Логика]] | + | [[Категория:Математика]][[Категория:Дискретная математика]][[Категория:Логика]] |
Текущая версия на 10:29, 13 января 2024
Совершенная дизъюнктивная нормальная форма (СДНФ) для логической функции – это дизъюнкция различных элементарных конъюнкций всех аргументов (либо самих, либо их отрицаний) данной функции, причём в одинаковом порядке. При этом таблицы истинности для логической функции и её СДНФ совпадают.
Содержание
Обозначения
n – число аргументов функции;
(x1,x2,…,xn) – набор аргументов функции;
f(x1,x2,…,xn) – логическая функция;
fСДНФ(x1,x2,…,xn) – СДНФ логической функции;
arg[f(x1,x2,…,xn)=1] – фиксированный набор аргументов функции, обращающий функцию в 1;
argj[f(x1,x2,…,xn)=1] – значение аргумента xj в фиксированном наборе аргументов.
Формула
- Для логической функции выбираются лишь те комбинации, которые приводят логическое выражение в состояние единицы.
В элементарную конъюнкцию записывается переменная без инверсии, если она в наборе равна 1, и с инверсией, если она равна 0.