Презентации лекций / Презентация лекции 5 ДМ 20

МинимальнаяДНФфункцииявляетсятупиковойДНФ.

Какдоказать?

Последовательнообосноватьследующее:

(1)МинимальнаяДНФ задаетфункцию

(2)Ее элементарные конъюнкциипростыеимпликантыфункции

(3)Если удалить изнеелюбую из ее э.к. (простую импликанту), то получившаяся «укороченная»формула не будет задаватьфункцию.

(1)Имеет место согласноопределению минимальной ДНФ.

(2)Рассуждатьот противного.Предположить,что найдетсятакаяминимальная ДНФ, среди э.к. которойесть импликанта , котораянеявляетсяпростой.

Выделить из простую импликанту , опустив частьбукв, и заменитьв нашей минимальной ДНФ на . Показать,что новаяДНФ также задаетфункцию.

Уновой ДНФ сложностьменьше, чем у исходной,– противоречиес тем, что исходнаяДНФминимальная.

(3). Рассуждатьот противного.Пустьестьтакаяминимальная ДНФ, «усеченная»от которой задаетфункцию, – противоречие, с тем, что у минимальная ДНФимеет наименьшую сложностьсредивсех ДНФ функции.

О

б

о

с

н

о

в

а

н

и

я

21