Ядровая точка функции f — единичный набор, который лежит только в одной максимальной грани \(N_f\). Эта единственная максимальная грань называется ядровой, а совокупность всех ядровых граней образует ядро функции
ДНФ пересечения тупиковых ∩T состоит из простых импликант, входящих в каждую тупиковую ДНФ. По лемме курса это именно импликанты ядровых граней. ДНФ Квайна получают из сокращённой ДНФ удалением неядровых импликант, грани которых покрываются ядром. Она содержит ДНФ суммы тупиковых и сама содержится в сокращённой
Что важно запомнить
- Ядровая точка покрывается ровно одной максимальной гранью.
- Ядро — совокупность всех ядровых максимальных граней.
- ДНФ ∩T — общая обязательная часть всех тупиковых ДНФ и состоит из ядровых простых импликант.
- ДНФ Квайна находится между ДНФ суммы тупиковых и сокращённой
Ядровые точки и ядро
Рассмотрим все максимальные грани множества единиц \(N_f\). Если единичная вершина α входит только в одну из этих граней, α называется ядровой точкой. Максимальная грань, единственная покрывающая такую точку, является ядровой гранью. Совокупность всех различных ядровых граней называется ядром
Почему ядровая грань обязательна? Любая ДНФ должна покрыть соответствующую ядровую точку. Других максимальных граней, способных сделать это, нет. Поэтому простая импликанта ядровой грани обязана присутствовать в любой тупиковой ДНФ.
ДНФ пересечения тупиковых
ДНФ \(\cap T\) определяется как дизъюнкция всех различных простых импликант, которые входят в каждую тупиковую ДНФ функции. Лемма курса утверждает точное соответствие: ДНФ ∩T состоит из тех и только тех простых импликант, которые соответствуют ядровым
Важно, что ДНФ ∩T сама по себе может не реализовывать f. Это не «ещё одна оптимальная ДНФ», а обязательная общая часть всех тупиковых реализаций.
ДНФ Квайна
ДНФ Квайна строится на основе сокращённой ДНФ. Из неё удаляют те простые импликанты K, для которых грань \(N_K\) покрывается ядром функции, но сама в ядро не входит. В результате сохраняются все ядровые импликанты и другие импликанты, которые нельзя исключить по этому
По множеству членов выполняется цепочка включений: ДНФ ∩T ⊆ ДНФ \(\Sigma T\) ⊆ ДНФ Квайна ⊆ сокращённая ДНФ. Здесь ДНФ \(\Sigma T\) рассматривается подробнее в следующем
Пример простыми словами
Для функции большинства трёх переменных максимальные грани множества единиц — x₁x₂, x₁x₃ и x₂x₃. Точки 110, 101 и 011 входят соответственно только в одну из этих граней, поэтому все три грани ядровые. Следовательно, ядро состоит из всех трёх максимальных граней, а ДНФ ∩T равна x₁x₂ ∨ x₁x₃ ∨ x₂x₃ и совпадает с сокращённой ДНФ. Неядровых простых импликант здесь нет, поэтому ДНФ Квайна также совпадает с сокращённой ДНФ.
Частые ошибки
- Считать ядром множество ядровых точек. В курсе ядро — совокупность ядровых максимальных граней.
- Считать ДНФ ∩T полноценной реализацией f во всех случаях. Она может не покрывать всё \(N_f\).
- Отождествлять ДНФ Квайна с сокращённой ДНФ. Они совпадают только для некоторых функций.
