Метод проб

Разбить на страницы

Показывать лекцию целиком

Рассмотрим произвольную ДНФ. Если в ней выбросить любое произведение, то оставшееся выражение будет принимать нулевое значение на тех наборах, что и исходная форма, т.к. $$x_{1}^{\alpha 1} x_{2}^{\alpha 2} \dots x_{i}^{\alpha i} = 0$$ только тогда все члены $$x_{1}^{\alpha 1} x_{2}^{\alpha 2} \dots x_{i}^{\alpha i} = 0$$.

Однако, если отброшенное произведение (импликанта) обращалось в единицу, и функция принимала единичное значение на этом единственном наборе, то оставшееся выражение может уже не принять единичное значение на данном наборе. Это означает, что импликанта не была лишней. Если же с помощью проверки установить, что оставшееся выражение обращается в единицу, импликанта – лишняя, и ее можно отбросить.

Пример 1:

Пусть дана $$f(x_{1}x_{2}x_{3}) = \overline{x}_{1}\overline{x}_{2} \vee x_{1}x_{3} \vee \overline{x}_{2}x_{3}$$

Отбросим член x₁x₂:

$$f^{l} = x_{1}x_{3} \vee \overline{x}_{2}x_{3}$$

x₁x₂ = 1 => x₁ = 0, x₂ = 0

$$f^{l} = 0 \cdot x_{3} \vee 1 \cdot x_{3} = x_{3}$$

Т.к. $$x_{3} \ne 1$$ то x₁x₂ исключить нельзя

Отбросим член x₁x₃:

$$f^{ll} = \overline{x}_{1}\overline{x}_{2} \vee \overline{x}_{2}x_{3}$$

x₁x₃ = 1  => x₁ = 1, x₃ = 1

$$f^{ll} = 0 \cdot \overline{x}_{2} \vee \overline{x}_{2} \cdot 1$$ $$\ne$$ 1 => x₁x₃ исключить нельзя.

Отбросим член x₂x₃:

$$f^{lll} = \overline{x}_{1}\overline{x}_{2} \vee x_{1}x_{3};$$

x₂x₃ = 1 => x₂ = 0, x₃ = 1

$$f^{lll} = \overline{x}_{1} \vee x_{1} \cdot 1 = 1$$ => x₂x₃ - член лишний.

Если проверка показывает, что несколько импликант одновременно являются лишними, то исключить их одновременно из выражения ДНФ нельзя. Это можно выполнять лишь поочередно.

Пример 2:

$$f(x_{1}x_{2}x_{3}x_{4}) = \overline{x}_{1}x_{3}x_{4} \vee \overline{x}_{2}x_{3}x_{4} \vee x_{1}\overline{x}_{2}x_{4} \vee x_{1}\overline{x}_{2}\overline{x}_{3} \vee \overline{x}_{2}\overline{x}_{3}\overline{x}_{4}$$

испытаем 1 член: x₁x₃x₄ = 1; x₁ = 0; x₃ = 1; x₄ = 1

$$f(x_{1}x_{2}x_{3}x_{4}) = \overline{x}_{2} \vee 0 \vee 0 \vee 0=\overline{x}_{2}$$ Т.е. член x₁x₃x₄ исключить нельзя.

испытаем 2 член: x₂x₃x₄ = 1; x₂ = 0; x₃ = x₄ = 1

$$f(x_{1}x_{2}x_{3}x_{4}) = \overline{x}_{1} \vee x_{1} \vee 0 \vee 0 = 1$$ Т.е. член x₂x₃x₄ лишний.

испытаем 3 член: x₁x₂x₄ ; x₁ = 1; x₂ = 0 x₄ = 1

$$f(x_{1}x_{2}x_{3}x_{4}) = 0 \vee x_{3} \vee \overline{x}_{3} \vee 0 = 1$$ Т.е. член x₁x₂x₄ лишний.

испытаем 4 член: x₁x₂x₃ ; x₁ = 1; x₂ = x₃ = 0

$$f(x_{1}x_{2}x_{3}x_{4}) = 0 \vee 0 \vee x_{4} \vee \overline{x}_{4} = 1$$, Т.е. член x₁x₂x₃ лишний.

испытаем 5 член: x₂x₃x₄ ; x₂ = x₃ = x₄ = 0

$$f(x_{1}x_{2}x_{3}x_{4}) = 0 \vee 0 \vee 0 \vee x_{1} = x_{1}$$, Т.е. член x₂x₃x₄ не лишний.

Исключим одновременно члены 2, 3, 4

$$f = \overline{x}_{1}x_{3}x_{4} \vee \overline{x}_{2}\overline{x}_{3}\overline{x}_{4}$$

Проверим значения f одновременно на тех наборах, на которых обращаются в единицу все отброшенные члены.

$$\overline{x}_{2}x_{3}x_{4}; x_{1}\overline{x}_{2}x_{4}; x_{1}\overline{x}_{2}\overline{x}_{3}; => \overline{x}_{1}x_{3}x_{4} \vee \overline{x}_{2}\overline{x}_{3}\overline{x}_{4}x_{1}\overline{x}_{2}\overline{x}_{3}$$

$$x_{2} = 0; x_{3} = x_{4} = 1 => f_{1} = \overline{x}_{1} \vee 0$$

$$x_{1} = 1; x_{2} = 0; x_{4} = 1 => f_{2} = 0 \vee 0$$

$$x_{1} = 1; x_{2} = x_{3} = 0 => f_{3} = 0 \vee \overline{x}_{4}$$

т.е. видно, что во всей совокупности этого сделать нельзя

Исключим член x₂x₃x₄, получим:

$$f(x_{1}x_{2}x_{3}x_{4}) = \overline{x}_{1}x_{3}x_{4} \vee x_{1}\overline{x}_{2}x_{4} \vee x_{1}\overline{x}_{2}\overline{x}_{3} \vee \overline{x}_{2}\overline{x}_{3}\overline{x}_{4}$$

Проверим, не являются ли в этом выражении лишними те члены, которые оказались лишними в исходном выражении, т.е.: x₁x₂x₄ и x₁x₂x₃.

проверим x₁x₂x₄:

x₁ = 1; x₂ = 0; x₄ = 1

$$f(x_{1}x_{2}x_{3}x_{4}) = 0 \vee \overline{x}_{3} \vee 0 = \overline{x}_{3}$$ т.е. член x₁x₂x₄ не лишний

проверим x₁x₂x₃:

x₁ = 1; x₂ = x₃ = 0

$$f (x_{1}x_{2}x_{3}x_{4}) = 0 \vee x_{4} \vee \overline{x}_{4} = 1$$, т.е. член x₁x₂x₃ лишний,

Поэтому $$f(x_{1}x_{2}x_{3}x_{4}) = \overline{x}_{1}x_{3}x_{4} \vee x_{1}\overline{x}_{2}\overline{x}_{4} \vee \overline{x}_{2}\overline{x}_{3}\overline{x}_{4}$$ - тупиковая форма.

Проверяя затем, начав с исключения третьего члена, получим другую тупиковую форму. Затем выберем из них минимальную.

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

Метод Квайна – Мак – Класки

Основное неудобство метода Квайна состоит в том, что при поиске простых импликант необходимо производить попарные сравнения вначале всех конститутент единицы, затем полученных в результате склеивания произведений.

С целью упрощения этой процедуры Мак – Класки предложил алгоритм, существо которого сводится к следующему:

вводится понятие цифрового эквивалента для каждого произведения по следующему правилу: некоторому произведению ставится в соответствие цифровой эквивалент с использованием цифр 0 и 1 и – (прочерк). Переменной, входящей в произведение в прямом виде ставится в соответствие единица ( 1 ), в инверсном – нуль ( 0 ), отсутствие переменной обозначается прочерком;

в любом произведении переменные располагаются только в одном порядке, а именно – по возрастанию индексов;

склейке подлежат только те произведения, в которых прочерки расположены соответственно, количество нулей (или единиц) отличается на единицу и они расположены так же соответственно.

Пример:

Произведению x₁x₂x₄ для функции, зависящей от пяти переменных нужно поставить в соответствие следующий цифровой набор: x₁x₂x₄: 11-0-

Приведем графическое изображение процесса поиска простых импликант для функции, представленной в следующей СДНФ:

$$f(x_{1}x_{2}x_{3}x_{4}) = x_{1}x_{2}\overline{x}_{3}x_{4} \vee x_{1}\overline{x}_{2}x_{3}\overline{x}_{4} \vee \overline{x}_{1}x_{2}\overline{x}_{3}x_{4} \vee x_{1}\overline{x}_{2}\overline{x}_{3}\overline{x}_{4}$$

запишем выражение функции в виде дизъюнкции цифровых эквивалентов:

$$f(x_{1}x_{2}x_{3}x_{4}) = 1101 \vee 1010 \vee 0101 \vee 1000$$

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

Для нашего примера это выглядит так:

Цифровые эквиваленты конституенты единицы	Отметки о склейке	Результат склейки	Отметки о склейке
`1000`	`*`	`10-0`	-
`0101`	`*`	`10-0`	-
`1010`	`*`	`-101`	-
`1101`	`*`	`-101`	-

Итак, простые импликанты:

10-0 и -101, т.е. $$f(x_{1}x_{2}x_{3}x_{4}) = x_{1}\overline{x}_{2}\overline{x}_{4} \vee x_{2}\overline{x}_{3}x_{4}$$

Метод импликантных матриц

Для поиска минимальной формы функции пользуются методом импликантных матриц. Существо метода заключается в следующем: составляется импликантная матрица, колонки которой именуются конституентами единицы, а строки – простыми импликантами. Затем находится минимальное покрытие всех конституент единицы простейшими импликантами. При этом ищется такая минимальная совокупность простых импликант, которые совместно покрывают все конституенты единицы исходной функции. Факт покрытия отмечается в клетке матрицы символом * (звездочка) в случае, когда импликанта покрывает соответствующую конституенту (является ее собственной частью). Из всех простых импликант выбираются вначале только такие, которые только одни покрывают конституенты единицы (в колонке матрицы только один символ покрытия), затем производится перебор.

Пример:

Простые импликанты	Конституенты единицы
Простые импликанты	`A`	`B`	`C`	`D`	`E`	`F`
`r`	`*`			`*`	`*`
`p`	`*`	`*`			`*`
`q`			`*`		`*`
`m`			`*`
`n`	`*`					`*`

Из матрицы видно, что в минимальную форму функции обязательно войдут импликанты n (покрывает конституенту F ), импликанта r (покрывает конституенту D ). То же справедливо отностительно импликанты p. Что касается остальных, то нужно выбрать минимальную совокупность.

Итак:

$$f^{1}_{min} = n \vee r \vee p \vee q \\ f^{2}_{min} = n \vee r \vee p \vee m$$

Т.е. данная функция имеет две одинаково минимальные формы.

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

Минимизирующие диаграммы

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

Рассмотрим существо способа для функций, зависящих от 2, 3 и 4-х переменных.

Функции 2-х переменных

Диаграмма – матрица, столбцам и строкам которой приписывается смысл переменных, входящих в функцию в прямом или инверсном виде.

В клетках матрицы ставится произведение, образованное из букв, которыми названы строки и столбцы матрицы.

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

Так склейке подлежат все произведения, расположенные в соседних по вертикали и горизонтали клетках.

xy склеивается с xy и с xy ;

Более того, эта же диаграмма дает и результат склейки: это название или строки, или столбца. При минимизации по данному методу заполняется диаграмма функции 2-х переменных по следующему правилу: если то или иное произведение входит в СДНФ функции, то в соответствующую ему клетку диаграммы ставится единица, и нуль – в противном случае. Если в диаграмме находится хотя бы две соседние единицы, то это означает, что два произведения склеиваются, а результатом склейки является произведение (в данном случае из одной буквы), именем которого названа данная строка или столбец.

Пример:

$$f(x,y) = x\overline{y} \vee \overline{x}y \vee \overline{x}\overline{y}$$

Выделим в диаграмме соседние единицы, и результат склейки дает минимальную форму функции: $$f_{min}(x,y) = \overline{x} \vee \overline{y}$$

Заметим, что результатом склейки является результат покрытия конституент единицы исходной функции простыми импликантами. В данном случае переменными, которыми названы строки и столбцы диаграммы.

Функции 3-х переменных

Для минимизации функций, зависящих от трех переменных, применяется следующая диаграмма:

Из диаграммы видно, что склейке подлежат все произведения, расположенные в соседних клетках, а также в клетках, расположенных на краях диаграммы. Результат склейки – есть произведения, содержащее на одну букву меньше. Видно также, что возможна и дальнейшая склейка, однако уже между произведениями, расположенными во взаимно перпендикулярном направлении.

Рассмотрим, например, левую половину диаграммы:

x₁x₂x₃	x₁x₂x₃
x₁x₂x₃	x₁x₂x₃

Склеим попарно произведения, стоящие в строках:

x₁x₂	x₁x₂
x₁x₂	x₁x₂

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

x₂	x₂
x₂	x₂

Как видно, результат склейки – произведение x₂. Именно эта переменная покрывает все четыре конституенты единицы СДНФ функции.

Подобное же утверждение справедливо и для конституент, расположенных в строках и столбцах диаграммы по краям таблицы.

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

Пример:

$$f(x_{1}x_{2}x_{3}) = x_{1}\overline{x}_{2}x_{3} \vee x_{1}x_{2}\overline{x}_{3} \vee x_{1}\overline{x}_{2}\overline{x}_{3} \vee \overline{x}_{1}x_{2}\overline{x}_{3} \vee \overline{x}_{1}\overline{x}_{2}\overline{x}_{3}$$

$$f_{min}(x_{1}x_{2}x_{3}) = \overline{x}_{3} \vee x_{1}\overline{x}_{2}$$

Видим, что две единицы, соответствующие конституентам x₁x₂x₃ и x₁x₂x₃, покрываются произведением x₁x₂.

Функции 4-х переменных

Для функций 4-х переменных применяются диаграммы следующего вида:

Все, что было сказано относительно функций 2-х, 3-х переменных справедливо и в данном случае. Но данная диаграмма обладает дополнительной особенностью: при поиске минимальной формы функции необходимо считать склееными правый край с левым и верхний с нижним.

Говорят, что для удобства целесообразно считать данную диаграмму написанной на поверхность тора.

Пример:

$$f(x_{1},x_{2},x_{3},x_{4}) = x_{1}x_{2}\overline{x}_{3}\overline{x}_{4} \vee x_{1}x_{2}x_{3}\overline{x}_{4} \vee x_{1}\overline{x}_{2}x_{3}\overline{x}_{4} \vee x_{1}\overline{x}_{2}\overline{x}_{3}\overline{x}_{4} \vee \overline{x}_{1}x_{2}\overline{x}_{3}\overline{x}_{4} \vee \overline{x}_{1}\overline{x}_{2}\overline{x}_{3}\overline{x}_{4}$$

Составим диаграмму:

$$f_{min}(x_{1},x_{2},x_{3},x_{4}) = x_{1}\overline{x}_{4} \vee \overline{x}_{3}\overline{x}_{4}$$

Заметим, что на основании свойства диаграммы четыре единицы, стоящие в угловых клетках диаграммы соответствуют конституентам, которые склеиваются между собой.

Итак, дадим формализированное описание метода.

Определение. Правильной конфигурацией ранга К называется совокупность единиц (нулей), образующая прямоугольник площадью 2^к.

Для минимизации функции, зависящей от n аргументов, отыскиваются правильные конфигурации вначале n-1 ранга, затем n-2 ранга и т.д.

Далее определяется накрытие найденных правильных конфигураций совместной проекцией соответствующих строк и столбцов, которая выделяет данную правильную конфигурацию.

(рис 4.1) Определение правильных конфигураций

C – правильная конфигурация

A,B,D – проекции конфигурации

А*В – результат склеек

Свойства диаграмм Вейча

С помощью диаграмм Вейча можно находить:

минимальную форму по СКНФ

минимальную форму по ДНФ и КНФ функции

все одинаково минимальные формы

минимальную форму неполностью определенных функций.

Пусть f(x₁x₂x₃) задана не в виде СДНФ, а в ДНФ:

$$f(x_{1}x_{2}x_{3}) = x_{1}\overline{x}_{2} \vee x_{1}x_{2}\overline{x}_{3} \vee \overline{x}_{1}x_{2}$$

Заполним соответствующую диаграмму:

Так как $$x_{1}\overline{x}_{2} = x_{1}\overline{x}_{2} (x_{3} \vee \overline{x}_{3}) = x_{1}\overline{x}_{2}x_{3} \vee x_{1}\overline{x}_{2}\overline{x}_{3}$$, то в соответствующие клетки диаграммы поставлены единицы.

Поэтому: $$f_{min}(x_{1},x_{2},x_{3}) = x_{2}\overline{x}_{3} \vee x_{1}\overline{x}_{2} \vee \overline{x}_{1}x_{2}$$

Преимущество метода: простота и наглядность для небольшого числа аргументов.

Недостатки: неприменяемость метода для большого числа аргументов (> 6) вследствие сложности диаграмм и потери наглядности.

Страницы:

Пример 1:

Пусть дана $$f(x_{1}x_{2}x_{3}) = \overline{x}_{1}\overline{x}_{2} \vee x_{1}x_{3} \vee \overline{x}_{2}x_{3}$$

Отбросим член x₁x₂:

$$f^{l} = x_{1}x_{3} \vee \overline{x}_{2}x_{3}$$

x₁x₂ = 1 => x₁ = 0, x₂ = 0

$$f^{l} = 0 \cdot x_{3} \vee 1 \cdot x_{3} = x_{3}$$

Т.к. $$x_{3} \ne 1$$ то x₁x₂ исключить нельзя

Отбросим член x₁x₃:

$$f^{ll} = \overline{x}_{1}\overline{x}_{2} \vee \overline{x}_{2}x_{3}$$

x₁x₃ = 1  => x₁ = 1, x₃ = 1

$$f^{ll} = 0 \cdot \overline{x}_{2} \vee \overline{x}_{2} \cdot 1$$ $$\ne$$ 1 => x₁x₃ исключить нельзя.

Отбросим член x₂x₃:

$$f^{lll} = \overline{x}_{1}\overline{x}_{2} \vee x_{1}x_{3};$$

x₂x₃ = 1 => x₂ = 0, x₃ = 1

$$f^{lll} = \overline{x}_{1} \vee x_{1} \cdot 1 = 1$$ => x₂x₃ - член лишний.

Пример 2:

испытаем 1 член: x₁x₃x₄ = 1; x₁ = 0; x₃ = 1; x₄ = 1

$$f(x_{1}x_{2}x_{3}x_{4}) = \overline{x}_{2} \vee 0 \vee 0 \vee 0=\overline{x}_{2}$$ Т.е. член x₁x₃x₄ исключить нельзя.

испытаем 2 член: x₂x₃x₄ = 1; x₂ = 0; x₃ = x₄ = 1

$$f(x_{1}x_{2}x_{3}x_{4}) = \overline{x}_{1} \vee x_{1} \vee 0 \vee 0 = 1$$ Т.е. член x₂x₃x₄ лишний.

испытаем 3 член: x₁x₂x₄ ; x₁ = 1; x₂ = 0 x₄ = 1

$$f(x_{1}x_{2}x_{3}x_{4}) = 0 \vee x_{3} \vee \overline{x}_{3} \vee 0 = 1$$ Т.е. член x₁x₂x₄ лишний.

испытаем 4 член: x₁x₂x₃ ; x₁ = 1; x₂ = x₃ = 0

$$f(x_{1}x_{2}x_{3}x_{4}) = 0 \vee 0 \vee x_{4} \vee \overline{x}_{4} = 1$$, Т.е. член x₁x₂x₃ лишний.

испытаем 5 член: x₂x₃x₄ ; x₂ = x₃ = x₄ = 0

$$f(x_{1}x_{2}x_{3}x_{4}) = 0 \vee 0 \vee 0 \vee x_{1} = x_{1}$$, Т.е. член x₂x₃x₄ не лишний.

Исключим одновременно члены 2, 3, 4

$$f = \overline{x}_{1}x_{3}x_{4} \vee \overline{x}_{2}\overline{x}_{3}\overline{x}_{4}$$

Проверим значения f одновременно на тех наборах, на которых обращаются в единицу все отброшенные члены.

$$x_{2} = 0; x_{3} = x_{4} = 1 => f_{1} = \overline{x}_{1} \vee 0$$

$$x_{1} = 1; x_{2} = 0; x_{4} = 1 => f_{2} = 0 \vee 0$$

$$x_{1} = 1; x_{2} = x_{3} = 0 => f_{3} = 0 \vee \overline{x}_{4}$$

т.е. видно, что во всей совокупности этого сделать нельзя

Исключим член x₂x₃x₄, получим:

$$f(x_{1}x_{2}x_{3}x_{4}) = \overline{x}_{1}x_{3}x_{4} \vee x_{1}\overline{x}_{2}x_{4} \vee x_{1}\overline{x}_{2}\overline{x}_{3} \vee \overline{x}_{2}\overline{x}_{3}\overline{x}_{4}$$

проверим x₁x₂x₄:

x₁ = 1; x₂ = 0; x₄ = 1

$$f(x_{1}x_{2}x_{3}x_{4}) = 0 \vee \overline{x}_{3} \vee 0 = \overline{x}_{3}$$ т.е. член x₁x₂x₄ не лишний

проверим x₁x₂x₃:

x₁ = 1; x₂ = x₃ = 0

$$f (x_{1}x_{2}x_{3}x_{4}) = 0 \vee x_{4} \vee \overline{x}_{4} = 1$$, т.е. член x₁x₂x₃ лишний,