Что такое творческие кладовые по дискретной математике
портала "Русский след"?

                                                                   Поэзия всей сути чисел
                                                     Сравнима с россыпью светил,
                                                     Прекрасна как алмазный бисер
                                                    Родоначальница мерил. (Ю.Н. Пиллигримов)

---

                     27. Метод минимизации булевой функции Куайна .

                    Булевcкими  в качестве переменных имеют имеют булевские переменные. Булевские переменные - это
такие переменные. которые могут принимать только два значения: истина (1) и ложь (0). А булевские операции это три
логических  операции: конъюнкция, дизъюнкция и отрицание.

              Основным спектром использования булевских операции является логика и счисления высказываний. Для
минимизация логических выражений в исчислении высказываний используются два метода: метод минимизации
логических выражений Блейка-Порецкого  и метод Куайна. Рассмотрим метод минимизации Куайна. 

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

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

       Метод минимизации логических выражений  Куайна применим к совершенным нормальным формам в отличие от метода Блейка-Порецкого   и исходит из систематического выполнения следующих двух процедур, определяемых равнозначностями:

1. [Ax к Ax*] ≡ [Ax к Ax* к A] (это закон неполного склеивания, * - знак отрицания, к - дизъюнкция)

2. [A к A.B]  ≡ A (элементарное поглощение)

        Разберём пример применения метода.

Пусть задана функция  ψ(p,q,r) ≡ [pq* к pqr к qr], подлежащая минимизации. Для того, чтобы был применим метод Куайна, надо данное выражение p.q* к pqr к qr привсести сначала к совершенной дизъюнктивной форме, что даёт последовательно:

pq*r к p(qr)* к pqr к p*qr

pq*r к pq*r* к pqr к p*qr

pq*r к pq*r* к pqr к p*qr к pr к qr к pq*,

Откуда окончательно приходим к ψ^/(p,q,r) ≡pq* к pr к qr .

С целью тачной фиксации конца минимизационных процедур вводится так называемая тупиковая сокращённая  нормальная форма. Для этого на базе приведённого примера построим таблицу особого вида, в первой строке которой поместим выражение, подлежащее минимизации, а в первой колонке - выражение. получающееся в результате применения к исходной функции приёмов  минимизации. Эта таблица выглядит так:

Члены сокращённой нормальной формы	Члены исходного выражения
	pq*	pqr	qr
pq*	+
pqr		+
qr		+	+

    Здесь значком + в таблице соответствует поглощение (например , член pr поглощает член pqr,что отмечено знаком +), а * знак отрицания рядом стоящего слева переменной.

     Тупиковая сокращённая дизъюнктивная нормальная форма примет вид:   ψ ^// ≡ [pq* к  qr], поскольку члены pq* и qr  вместе поглощают всё выражение ψ в целом.

     Минимизация логических выражений имеет огромное значение. так как подчёркивается стремление повысить надёжность машин ( чем меньше элементов в схеме. тем выше надёжность), позволяет упростить процедуру сборки схем.