Следствия. Гипотезы. Минимизация.

Следствия. Гипотезы. Минимизация. Совершенные и сокращённые днф и кнф используются
для решения задачи обзора всех гипотез и всех следствий заданной формулы.
Под гипотезой формулы понимается такая формула,
что , а под следствием формулы-
такая формула, что
Гипотеза формулыназ. простой, если она есть конъюнкция
переменных или их отрицаний и после отбрасывания любого из её сомножителей
перестаёт быть гипотезой формулы. Аналогично,
следствие формулы наз. простым, если оно есть дизъюнкция переменных или
их отрицаний и после отбрасывания любого из её слагаемых перестаёт быть
следствием формулы. Решение задачи обзора
гипотез и следствий основано на указании алгоритма, строящего все простые
гипотезы и следствия для заданной формулы и в получении из них при помощи
законов (2) - (7) всех остальных гипотез и следствий.

Сокращённая
днф имеет важные приложения. Следует отметить прежде всего задачу минимизации
функций А. л., являющуюся частью т. н. задачи синтеза управляющих систем.
Минимизация функций А, л, состоит в построении такой днф для заданной функции
А. л., к-рая реализует эту функцию и имеет наименьшее суммарное число сомножителей
в своих слагаемых, т. е. имеет минимальную "сложность". Такие днф наз.
минимальными. Каждая минимальная днф для заданной отличной от константы
функции А. л. получается из сокращённой днф любой формулы, реализующей
эту функцию, выбрасыванием нек-рых слагаемых
из этой сокращённой днф.

А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я