Главная > Документ


Этап 3.

Записать 0 в качестве значения функции в остальные строки таблицы.

Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

1

0

0

1

1

Продолжение

Номер набора

x

y

z

f(x,y,z)

2

0

1

0

1

3

0

1

1

0

4

1

0

0

0

5

1

0

1

1

6

1

1

0

0

7

1

1

1

1

Таблица истинности получена.

Получение СКНФ.

Получение СКНФ по ТИ описано в примере 2.1.

Результатом будет:

f(x,y,z)СКНФ = ∏(3,4,6) = (x V ¯y Vz ) & (x V y V z ) & (x Vy Vz)

Пример 2.3

Пусть ФАЛ задана сокращенной записью СКНФ:

f(x,y,z)СКНФ = (2,3,4,5,7)

Получить полную и сокращенную записи СДНФ этой функции.

Решение

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

Этап 1.

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

f(x,y,z)СДНФ = (0,1,6)

Этап 2.

Получить полную запись СДНФ согласно указаниям примера 2.1. Результатом будет:

f(x,y,z)СДНФ =xyz Vxyz V xyz

Пример 2.4

Пусть ФАЛ задана в виде СДНФ:

f(x,y,z)СКНФ = xyz Vxyz Vxyz V xyz

Получить полную и сокращенную записи СКНФ этой функции.

Решение

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

f(x,y,z)СКНФ=xyz Vxyz VxyzV xyz

1 0 0 0 0 1 0 1 0 1 1 1

Затем представим эти наборы в десятичном коде и перечислим их под знаком обобщенной дизъюнкции :

f(x,y,z)СДНФ=(4,1,2,7)

По полученной сокращенной записи СДНФ функции получим сокращенную запись СКНФ, перечислив под знаком обобщенной конъюнкции  номера наборов, не вошедших в сокращенную запись СДНФ:

f(x,y,z)СКНФ=(0,3,5,6)

По сокращенной записи СКНФ получим ее полную запись согласно методике, изложенной в примере 2.1.

f(x,y,z)СКНФ =(x V y V z) & (xVy Vz) & (x V y Vz) & (x Vy V z)

Пример 2.5

Пусть ФАЛ задана в виде СКНФ:

f(x,y,z)СКНФ =(x Vy V z) & (x Vy Vz) & (x V y Vz)

Получить полную и сокращенную записи СДНФ этой функции.

Решение

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

f(x,y,z)СКНФ =(x Vy V z) & (x Vy Vz) & (x V y Vz)

0 1 0 0 1 1 1 0 1

Затем представим эти наборы в десятичном коде и перечислим их под знаком обобщенной конъюнкции :

f(x,y,z)СКНФ=(2,3,5)

По полученной сокращенной записи СКНФ функции получим сокращенную запись СДНФ, перечислив под знаком обобщенной дизъюнкции  номера наборов, не вошедших в сокращенную запись СКНФ:

f(x,y,z)СДНФ=(0,1,4,6,7)

По сокращенной записи СДНФ получим ее полную запись согласно методике, изложенной в примере 2.1:

f(x,y,z)СКНФ=xyzVxyz Vxyz Vxyz Vxyz

Пример 2.6

Пусть ФАЛ задана в виде дизъюнктивной нормальной формы, не являющейся совершенной. Например:

f(x,y,z)=xVxyVxyz

Получить полную и сокращенную записи СКНФ этой функции.

Решение

Для решения этой задачи можно сначала получить СДНФ функции.

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

a =ab V ab

Тогда, последовательно повышая ранг для термов, зависящих не от всех переменных, получим:

x =xy Vxy =xyz Vxyz Vxyz Vxyz

xy = xyz V xyz

f(x,y,z) =x V xy V xyz =

=xyz Vxyz Vxyz Vxyz V xyz V xyz V xyz

После выполнения преобразования на основе эквивалентности

aVa = a

получим полную, а затем и сокращенную записи СДНФ:

f(x,y,z)СДНФ =xyz Vxyz Vxyz Vxyz V xyz V xyz

f(x,y,z)СДНФ = (3,2,1,0,7,6)

Последующие шаги по решению поставленной задачи рассмотрены ранее.

В результате получим:

f(x,y,z)СКНФ = (4,5)

f(x,y,z)СКНФ = (x V y V z) & (x V y Vz)

Пример 2.7

Пусть ФАЛ задана в виде конъюнктивной нормальной формы, не являющейся совершенной. Например:

f(x,y,z)= (x V y) & (x Vz )

Получить полную и сокращенную записи СДНФ этой функции.

Решение

Решение этой задачи аналогично предыдущей.

Для получения СКНФ необходимо использовать следующие эквивалентности:

a = (aVb) & (a Vb)

a & a = a

Тогда получим:

xVy = (x V y V z) & (x V y Vz)

x Vz = (x V y Vz) & (x Vy Vz)

f(x,y,z) = (x V y V z) & (x V y Vz) & (x V y Vz) & (x Vy Vz)

f(x,y,z)СКНФ= (xVyVz) & (xVyVz) & (xVyVz)

f(x,y,z)СКНФ = (4,5,7)

Исходя из полученной СКНФ функции, определим ее СДНФ:

f(x,y,z)СДНФ = (0,1,2,3,6)

f(x,y,z)СДНФ =xyz V xyz V xyz V xyz V xyz

Пример 2.8

Пусть ФАЛ задана в виде совершенной дизъюнктивной нормальной формы:

f(x,y,z)СДНФ =xyz V xyz V xyz

Представить запись этой функции в базисе “Штрих Шеффера”.

Решение

Для перехода от представления ФАЛ в виде СДНФ к базису “Штрих Шеффера” необходимо выполнить следующее.

Этап 1.

Заменить все знаки дизъюнкции и конъюнкции на знак функции “Штрих Шеффера”. При этом вследствие невыполнения для данной функции ассоциативного закона (см. (1.32)) каждый конъюнктивный член должен быть заключен в скобки:

f(x,y,z) = (x /y / z ) / (x /y / z) / (x / y /z)

Этап 2.

Выразить функцию отрицания через функцию “Штрих Шеффера” согласно (1.29), также заключая эту операцию в скобки:

f(x,y,z) = ((x / x) / (y / y) / z) / (x / (y / y) / z) / (x / y / (z / z))

Пример 2.9

Пусть ФАЛ задана в виде:

f(x,y,z)СДНФ = x V xy V xyz

Представить запись этой функции в базисе “Штрих Шеффера”.

Решение

Особенность выполнения первого этапа обусловлена наличием в записи функции члена x, не являющегося конъюнкцией каких-либо переменных. Для приведения этой функции к дизъюнктивной нормальной форме воспользуемся выражением (1.10):

f(x,y,z)СДНФ = xx V xy V xyz

Дальнейшие действия в этом примере полностью совпадают с примером 2.8.

Результатом выполнения этапа 1 будет

f(x,y,z) = (x / x) / (x /y) / (x / y /z),

а окончательный результат:

f(x,y,z) = (x / x) / (x / (y / y)) / ((x / x) / y / (z / z))

3. Минимизация функций алгебры логики

3.1. метод Квайна – Мак-Класки

Минимальная форма представления ФАЛ – форма представления ФАЛ, которая содержит минимальное количество термов и переменных в термах.

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

Все рассматриваемые ниже методы минимизации предполагают, что ФАЛ задана в виде совершенных нормальных форм или таблицы истинности. Если исходная форма задания ФАЛ не является совершенной, ее следует привести к таковой, используя методику, описанную в примерах 2.6 и 2.7.

Минимизация функций алгебры логики, представленных в виде совершенной дизъюнктивной нормальной формы, базируется на следующих эквивалентных преобразованиях ФАЛ:

xy V xy = x – операция склеивания (3.1.1)

xy V xy = x V xy V xy – операция неполного склеивания (3.1.2)

x V xy = x – операция поглощения (3.1.3)

Здесь x и y могут представлять собой как отдельные переменные, так и ФАЛ, зависящие от нескольких переменных.

Минимизация функций алгебры логики, представленных в виде совершенной конъюнктивной нормальной формы, базируется на следующих эквивалентных преобразованиях ФАЛ:

(x V y) & ( x V y) = x – операция склеивания (3.1.4)

(x V y) & (x Vy) = x & (x V y) & (x V y) – операция неполного

склеивания (3.1.5)

x &(x V y) = x – операция поглощения (3.1.6)

Здесь x и y также могут представлять собой как отдельные переменные, так и ФАЛ, зависящие от нескольких переменных.

Пример 3.1

Минимизировать ФАЛ, заданую в виде совершенной дизъюнктивной нормальной формы, методом Квайна – Мак-Класки:

f(a,b,c,d)СДНФ = (3,7,8,10,11,12,15)

Решение

Этап 1.

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

(0011, 0111, 1000, 1010, 1011, 1100, 1111)

Этап 2.

Разбить полученные двоичные коды на группы, содержащие одинаковое количество единиц в коде. Для ФАЛ, зависящих от n переменных, таких групп может быть n+1 (ни одной единицы в коде, одна единица, две единицы, ... , n единиц в коде). Расположить группы по возрастанию количества единиц. Если количество получившихся групп меньше n+1, то отсутствующие группы пометить как пустые:

- - - -

1000

0011

1010

1100

0111

1011

1111

Этап 3.

Сравнить каждый код из одной группы с каждым кодом из соседних групп. Если найдены два кода, отличающиеся только в одном разряде (то есть они могут “склеиваться” между собой согласно 3.1.1), то пометить эти коды каким-либо особым символом, например "; * ";, и в новую группу поместить код, сохраняющий значение в совпадающих разрядах и имеющий какой-либо особый символ, например ";-";, на месте не­сов­па­да­ю­ще­го разряда. При этом образуется n-1 новая группа кодов. Если код попадает в несколько “склеек”, то он символом * может по­ме­чать­ся только один раз.

Эта процедура повторяется для вновь образованных групп до тех пор, пока возможна процедура “склеивания“ элементов соседних групп. Максимальное возможное число шагов на этом этапе равно n. На всех шагах, начиная со второго, необходимо следить за тем, чтобы два “склеиваемых” кода представляли собой термы, зависящие от одних и тех же логических переменных, то есть знаки ";-"; у них должны находиться в одних и тех же позициях. При появлении в одной группе нескольких одинаковых импликант для дальнейшего анализа следует оставить лишь одну из них, исходя из соотношения (1.21):

- - - -

- - - -

- - - -

1000*

10-0

1-00

- - - -

0011*

1010*

1100*

0-11*

-011*

101-

--11

--11

0111*

1011*

-111*

1-11*

1111*

шаг 1

шаг 2

Результат выполнения данного этапа – получение всех первичных импликант исходной ФАЛ., то есть сокращенной дизъюнктив­ной нормальной формы. Первичными импликантами будут все им­пликанты, полученные на последнем шаге этого этапа, а также все импликанты, полученные на всех предшествующих шагах и не во­шедшие ни в одну из ";склеек";, то есть, не помеченные симво­лом *.

Этап 4.

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

В ячейку таблицы ставится какой-либо отличительный символ, например "; + ";, если первичная импликанта, стоящая в заголовке строки, является собственной частью конституэнты единицы, стоящей в заголовке столбца. В противном случае ячейка остается пустой:

Первичные импликанты

Конституэты единицы

0011

0111

1000

1010

1011

1100

1111

--11

+

+

+

+

10-0

+

+

1-00

+

+

101-

+

+

-111

+

+

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



Скачать документ

Похожие документы:

  1. Библиографический указатель из фонда научной библиотеки

    Библиографический указатель
    ... -технических работ. МИФИ - городу Москве:Каталог.-М.,2001.-Б.п. 195. Московский государственный инженерно-физический ... .-26с. 4553. Гуров В.В. Синтезкомбинационныхсхем в примерах и решениях: Учеб.пособие/Гуров В.В.-М.:МИФИ,2001.-56с. 4554. Гусев ...
  2. Москва 2011 1 Цели и задачи дисциплины (3)

    Рабочая программа
    ... коммуникационные технологии Москва 2011 1. ... схемотехнических решений и ... и синтезасхем ЭВМ. Анализ комбинационныхсхем. Синтезкомбинационныхсхем: мультиплексор ... СПб.: БХВ-Петербург, 2001. 2. Пухальский Г.И., Новосельцева ... также примеры оценочных ...
  3. Программа обучения студентов ( syllabus ) (3)

    Программа обучения студентов
    ... домашних заданий, самостоятельное решение задач), итоги индивидуальных ... А.В. и др. «Информатика». – Москва.: ACADEMA, 1999 г. Информатика/ Под ... ДИАЛОГ-МИФИ,1993 Гуров В.В. Синтезкомбинационныхсхем в примерах М.: МИФИ, 2001 Гуров В.В., Ленский О.Д., ...
  4. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...
  5. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА (2)

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...

Другие похожие документы..