ПРЕОБРАЗОВАНИЕ И УПРОЩЕНИЕ ФОРМУЛ

БУЛЕВА АЛГЕБРА

Логические функции, приведенные в табл. 2.1, можно рассматривать, как элементарные операции над одной или двумя двоичными переменными. Функционально полная система таких операций образует на множестве двузначных переменных алгебру логики. Таких алгебр можно представить столько же, сколько наберется подходящих функционально полных систем. Но наиболее распространена булева алгебра, в которой в качестве основных операций приняты конъюнкция х₁х₂ (И), дизъюнкция х₁+х₂ (ИЛИ) и отрицание `х (НЕ). Часто конъюнкцию и дизъюнкцию называют соответственно логическим произведением и суммой, а отрицание – инверсией. Используются также и другие варианты обозначений: для конъюнкции х₁Ùх₂, для дизъюнкции х₁Úх₂ и для отрицания х^/. Чтобы избежать в сложных формулах лишних скобок, которые появляются при суперпозиции функций, установлен жесткий порядок выполнения операций – конъюнкция предшествует дизъюнкции.

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

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

Свойства булевой алгебры используются для преобразования и упрощения логических формул, а также доказательства теоретических положений. Коммутативность и ассоциативность позволяют выполнять операции И или ИЛИ, группируя переменные в любом порядке. Первая формула дистрибутивности указывает на допустимость вынесения общего множителя за скобки, как в обычной алгебре. Но вторая форма в обычной алгебре аналога не имеет, что является одним из основных отличий ее от алгебры логики. Свойства отрицания подчеркивают взаимодополнительную природу логических переменных. Повторы переменой и константы позволяют избавляться от постоянных слагаемых и множителей или при необходимости вводить их. Двойное отрицание не изменяет переменную, что можно рассматривать как пустую операцию. На основе идемпотентности можно удалять повторяющиеся переменные, вследствие чего в булевой алгебре не имеют смысла показатели степени и числовые коэффициенты, что также существенно отличает ее от обычной алгебры. Законы де Моргана позволяют свести отрицание сложного выражения к отрицания отдельных переменных. Последние четыре свойства (склеивание, поглощение, замещение и выявление) полезны при различных преобразованиях и упрощениях булевых формул.

Таблица 2.2

Свойство	Первая форма	Вторая форма
1. Коммутативность	х+у=у+х	ху=ух
2. Ассоциативность	х+(y+z)=(x+y)+z	x(yz)=(xy)z
3. Дистрибутивность	x(y+z)=xy+xz	x+yz=(x+y)(x+z)
4. Дополнение	x+x=1	xx=0
5. Повтор переменной	x+0=x	x1=x
6. Повтор константы	x+1=1	x0=0
7. Двойное отрицание	X=x	x=x
8. Идемпотентность	x+x=x	xx=x
9. Законы де Моргана	x+y=xy	xy=x+y
10. Склеивание	xy+xy=x	(x+y)(x+y)=x
11. Поглошение	x+xy=x	x(x+y)=x
12. Замещение	x+xy=x+y	x(x+y)=xy
13. Выявление	xy+xz=xy+xz+yz	(x+y)(x+z)= =(x+y)(x+z)(y+z)

СТАНДАРТНЫЕ ФОРМЫ

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

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

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

Пример построения СДНФ

F(a,b,c) = ``ABC v A`BC v AB`C v ABC

ПРЕОБРАЗОВАНИЕ И УПРОЩЕНИЕ ФОРМУЛ

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

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

Склеивание х у + х`у = х (под х можно понимать любое выражение) позволяет заменить два минтерма, отличающихся вхождением только одной переменной (с отрицанием и без него), одним минтермом более низкого ранга. Пусть, например, функция задана в виде канонической суммы минтермов: у=`х₁ х₂`х<sub>3</sub> + `х₁ х₂ х₃ + х₁`х<sub>2</sub>`х₃ + х₁`х<sub>2</sub> х<sub>3</sub> + х<sub>1</sub>х<sub>2</sub>х<sub>3</sub>. Группируя члены и применяя операцию склеивания, имеем у= (`х₁ х₂`х<sub>3</sub> +`х₁х₂х₃ )+ (х₁`х<sub>2</sub>`х₃ + х₁`х<sub>2</sub> х<sub>3</sub> )+ х<sub>1</sub>х<sub>2</sub>х<sub>3</sub>=`х₁ х₂ + х₁`х<sub>2</sub> + х<sub>1</sub>х<sub>2</sub>х<sub>3</sub>. При другом варианте группирования получим у=`х₁ х₂`х<sub>3</sub> + (х<sub>1</sub>х<sub>2</sub>х<sub>3</sub> + х<sub>1</sub>х<sub>2</sub>х<sub>3</sub> )+ (х<sub>1</sub>`х₂`х<sub>3</sub> + х<sub>1</sub>`х₂ х₃ )= `х<sub>1</sub> х<sub>2</sub>`х₃ + х₁ х₂+х₁`х₂.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: