Карта Карно, булевы функции

[Xaositect]

Нет, потому что сокращенная ДНФ состоит только из максимальных граней(тех, которые не покрываются никакой другой гранью), а грани внутри зеленого квадрата этим самым квадратом покрываются.

-- Вт май 19, 2009 14:43:08 --

rar в сообщении #215247 писал(а):

Все-таки с ядровыми я не совсем разобрался. Можете объяснить, что такое ядровые и каков их смысл. Я этого не понимаю, пока. И как на карте Карно их определять, по какому принципу.

Смысл в том, что ядровые грани нельзя выкинуть из ДНФ, потому что в них есть точки, которые покрываются только ими.
Вот например.
У вас единица в правом верхнем углу покрывается только одной гранью(желтым прямоугольником). Значит, эта грань входит в ядро. Она будет присутствовать в любой тупиковой ДНФ, потому что если ее выкинуть, правая верхняя единица пропадет.

[rar]

Xaositect в сообщении #215254 писал(а):

Нет, потому что сокращенная ДНФ состоит только из максимальных граней(тех, которые не покрываются никакой другой гранью), а грани внутри зеленого квадрата этим самым квадратом покрываются.

Интересно, а что на последней картинке получается? СДНФ что ли?

[Xaositect]

СДНФ получится, если просто обвести все единицы кружочками
А это просто получается что-то типа $xy\vee xyz\vee xy\bar{z}\vee xyt\vee xy\bar{t}$

[rar]

А можно еще несколько вопросов.

В чем смысл совершенной ДНФ (КНФ)? Может быть только одна?
В чем смысл сокращенной ДНФ (КНФ)? Может быть только одна?
В чем смысл тупиковой(ых) ДНФ (КНФ)? Их может быть: ни одной, одна и более?
В чем смысл минимальной(ых) ДНФ (КНФ)? Их может быть: ни одной, одна и более?
Яровых ДНФ (КНФ) может быть ни одной, одна и более?

Буду благодарен за компетентные ответы.

[Xaositect]

rar в сообщении #215264 писал(а):

В чем смысл совершенной ДНФ (КНФ)? Может быть только одна?

Совершенная ДНФ показывает все единичные наборы. Единственна.
Это исходная форма представления в некоторых алгоритмах работы с функцией.

rar в сообщении #215264 писал(а):

В чем смысл сокращенной ДНФ (КНФ)? Может быть только одна?

Сокращенная ДНФ показывает все максимальные грани. Единственна.
Основной ее смысл в том, что из нее получают тупиковые ДНФ.
Несмотря на то, что она называется "сокращенной", в ней может быть даже больше конъюнкций, чем в СДНФ.

rar в сообщении #215264 писал(а):

В чем смысл тупиковой(ых) ДНФ (КНФ)? Их может быть: ни одной, одна и более?

Тупиковая ДНФ - это ДНФ, из которой нельзя выкинуть ни одной конъюнкции(грани). Их может быть одна и более.
Есть две полезные для синтеза теоремы:
Минимальная ДНФ всегдя является тупиковой.
Среди тупиковых ДНФ всегда содержится кратчайшая (одна или несколько).

rar в сообщении #215264 писал(а):

В чем смысл минимальной(ых) ДНФ (КНФ)? Их может быть: ни одной, одна и более?

Минимальная ДНФ - это ДНФ, имеющая наименьшее среди всех число вхождений переменных. МДНФ может быть одна или несколько.
Это цель задачи минимизации. Минимальная ДНФ - это самая простая ДНФ, которая может быть у функции. На ее основе можно строить достаточно простые (по количеству элементов) схемы, реализующие функцию.

rar в сообщении #215264 писал(а):

Яровых ДНФ (КНФ) может быть ни одной, одна и более?

Ядровая ДНФ единственна и может быть пустой. Она является общей частью всех тупиковых ДНФ. Поэтому иногда(в частности, Ложкин, который у меня читал лекции) называется ДНФ-пересечение тупиковых.

[Mike1]

Объясните пожалуйста, почему в карте Карно получаются именно такие конъюнкции? Каким образом?

[nshell32]

А как работать с картами более 6 переменных? В интернете было описание, но в нем вообще ничего непонятно. Где можно найти инфу об этом?