Я был бы признателен за помощь в поиске литературы, посвященной оптимальности K-карты.
Я понимаю, как, например, вы можете сопоставлять выражения SOP (сумма произведений) и K-карту, и почему в целом вы ожидаете, что выражение, оптимизированное для K-карты, будет проще, поскольку нахождение максимальной группировки единиц соответствует нахождению некоторых избыточностей в наивном выражении SOP.
Я смутно вижу, что метод К-карты может не давать оптимальных решений, потому что кажется, что единственное, что мы на самом деле делаем, — это пользуемся дистрибутивными и тождественными (А + А' = 1) свойствами булевой алгебры. Но я не очень понимаю, какие алгебраические операции мы не выполняем с K-картой, которые могли бы позволить нам достичь более оптимального решения.
В результате я не знаю, как начать доказательство, которое показало бы, что K-карты не всегда оптимальны.
Я пытался прочитать: это, но в этой статье просто цитируется, что проблема поиска оптимального булева выражения находится в NP, и я думаю, что автор просто неявно говорит, что K-карты не могут быть оптимальными, так как как алгоритм они не выполняются за NP-время.
Почему K-карты неоптимальны, а не только в качестве «контрпримера»… на самом деле, почему? Можете ли вы либо доказать это мне, либо направить меня к доказательству?
