Метод Блейка - Порецкого
Метод позволяет получать сокращенную ДНФ булевой функции f из ее произвольной ДНФ. Базируется на применении формулы обобщенного склеивания:
,
справедливость которой легко доказать. Действительно,
, .
Следовательно,
В основу метода положено следующее утверждение: если в произвольной ДНФ булевой функции f произвести все возможные oбобщенные склеивания, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции f.
Рассмотрим пример. Пусть булева функция f задана произвольной ДНФ.
Необходимо, используя метод Блейка – Порецкого, получить сокращенную ДНФ функции f. Проводим обобщенные склеивания. Легко видеть, что первый и второй элемент исходной ДНФ допускают обобщенное склеивание по переменной х1. В результате склеивания получим:
Первый и третий элемент исходной ДНФ допускают обобщенное склеивание как по переменной х1, так и по х2. После склеивания по x1 имеем:
После склеивания по x2 имеем:
Второй и третий элемент ДНФ допускают обобщенное склеивание по переменной х2. После склеивания получаем:
Выполнив последнее обобщенное склеивание, приходим к ДНФ:
После выполнения поглощений получаем:
Попытки дальнейшего применения операции обобщенного склеивания и поглощения не дают результата. Следовательно, получена сокращенная ДНФ функции f. Далее задача поиска минимальной ДНФ решается с помощью импликантной матрицы точно так же, как в методе Квайна.
Дата добавления: 2022-02-05; просмотров: 232;