Минимизация логических функций

СОДЕРЖАНИЕ

 

Введение…………………………………………………………….. 3

 

Основные логические функции……………………………………. 4

 

        Свойства конъюнкции, дизъюнкции и отрицания………………...  6

 

ДНФ, СДНФ, КНФ, СКНФ………………………………………... 7

 

Представление логических функций в виде СДНФ (СКНФ)…… 8

 

Минимизация логических функций………………………………. 10

 

Реализация функций алгебры логики схемами………………….. 12

 

Заключение…………………………………………………………. 15

 

Список литературы………………………………………………… 16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Математической основой преобразования логических функций является алгебра логики. Алгебра логики - это раздел математики, оперирующий с независимыми переменными, которые могут принимать только два значения: «истинно» или «ложно». В цифровой электронике им присвоены значения «1», т.е. полный сигнал на выходе и «0», т.е. полное отсутствие сигнала на выходе.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Основные логические функции

Обозначим через E = {0, 1} - множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной математике. Часто они интерпретируются как «ложь» (л ={0}) и как «истина» (и ={1}). Декартово произведение E* Е* Е* …* E=En является множеством упорядоченных наборов, состоящих из n чисел (нулей и единиц). Как известно, Еn содержит 2n элементов (упорядоченных наборов).

Само множество Еn можно естественным образом упорядочить, для чего достаточно считать каждый набор двоичным разложением целого числа k (0≤k≤ 2n –1), записанного с помощью n знаков. Упорядочение наборов проводится по числу k . Например, при n = 3 множество Е3 может быть упорядочено следующим образом (рис.1).

Рис.1. Упорядочение «скользящая единица»

Этот естественный порядок элементов Еn  является самым распространенным, но, как будет видно в разд. 6, иногда удобен другой способ упорядочения.

Логической (булевой) функцией (или просто функцией) n переменных y = f(x1, x2, …, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1. Переменные, которые могут принимать только два значения 0 и 1 называются логическими переменными (или просто переменными). Заметим, что логическая переменная х может подразумевать под числом 0 некоторое высказывание, которое ложно, и под числом 1 высказывание, которое истинно.

Логическая функция может быть задана словесно, алгебраическим выражением или таблицей, которая называется таблицей соответствия или истинности. Из определения логической функции следует, что функция n переменных - это отображение Еn в Е, которое можно задать непосредственно таблицей, называемой таблицей истинности данной функции. Например, функция трех переменных f(x,y,z) может определяться следующей таблицей истинности.

Таблица 1

Это означает, что f(0,0,0) = 1, f(0,0,1) = 0, f(0,1,0) = 1 и т. д.

 

Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных).

При таком задании наборы Еn всегда упорядочены естественным образом, это позволяет определять функцию только последним столбцом (который иногда для экономии места записывается в строчку). Например, в нашем примере функцию f(x,y,z) можно задать так: f(x,y,z) = (10110100).

Заметим, что все функции n переменных также можно перенумеровать по принципу «скользящей единицы». Число таких функций – 22n .

Если фактически функция не зависит от некоторой переменной, то такую переменную называют фиктивной.

Теперь можно описать основные функции дискретной математики.

Перенумеруем четыре функции одной переменной y=f(x) естественным образом и расположим в виде таблицы 2:

Таблица 2

Видно, что f0 (х) = 0, a f3 (х) =1, т. е. эти две функции не зависят от х,

f1 (х)=х, т. е. она не меняет аргумента. Функция f2 (х) действительно содержательная функция. Она принимает значения, противоположные значениям аргумента, обозначается f2 (х)= и называется отрицанием.

Число функций двух переменных f(x,y) функций равно 24 = 16.

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

Таблица 3

 

 

 

 

 

 

 

 

 

 

 

Из перечисленных функций особую роль играют три функции, а именно

конъюнкция, дизъюнкция и отрицание, поэтому рассмотрим более подробно их свойства.

В алгебраических выражениях конъюнкция обозначается знаком ∧ или &,

дизъюнкция – знаком ∨ , а отрицание - чертой над обозначением переменной или знаком ¬ .

 

Свойства конъюнкции, дизъюнкции и отрицания

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

Конъюнкцией n переменных f (x1, x2, …, xn) = x1 x2…xn называется

функция, которая принимает значение 1, если и только если все

переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих

переменных равна 0).

    Дизъюнкцией n переменных f (x1, x2, …, xn) = x1 ∨ x2 ∨… ∨ xn

называется такая функция, которая равна 0 если и только если все

переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя

бы одна переменная равна 1).

   Из этих определений видно, что конъюнкция и дизъюнкция

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

   Будем обозначать через f (x1, x2, … , xn) новую функцию, которая на

наборе переменных x1, x2, …, xn принимает значение, противоположное    f(x1, x2,…, xn).

  Заметим, что в перечисленных далее свойствах в роли x, y, z может

выступать любая логическая функция. Все свойства легко могут быть

доказаны из приведенных выше определений этих функций.

1. Универсальные границы:

x∨1 = 1; x∨ 0 = х; х1 = х; х0 = 0.

2. Ассоциативность конъюнкции  и дизъюнкции:

x(yz) = (xy)z; x∨ (y∨ z) = (x ∨y)∨ z.

Это свойство означает, что в конъюнкции или дизъюнкции нескольких

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

3. Поглощение («целое поглощает  часть»):

х∨ ху = х(1∨ у) = х.

4. Распределительные законы:

х (y∨ z) = x y ∨ x z; х∨ (y z) = (x∨ y)(x∨ z),

5. Правила де Моргана

оба эти правила обобщаются на любое число переменных.

 

ДНФ, СДНФ, КНФ, СКНФ

   Простой конъюнкцией называется конъюнкция одной или нескольких

переменных, при этом каждая переменная встречается не более одного

раза (либо сама, либо ее отрицание).

Например, x ⋅ y ⋅ z является простой конъюнкцией.

    Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция

простых конъюнкций. Например, выражение x ⋅ y ∨ y ⋅z является ДНФ.

    Совершенной дизъюнктивной нормальной формой (СДНФ) называется

такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке. Например, выражение x ∨ y ⋅ z является ДНФ, но не СДНФ. Выражение x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z является СДНФ.

   Аналогичные определения (с заменой конъюнкции на дизъюнкцию и

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

(либо сама, либо ее отрицание). Например, выражение x ∨ y ∨ z – простая дизъюнкция.

    Конъюнктивной нормальной формой (КНФ) называется конъюнкция

простых дизъюнкций.

Например, выражение (x ∨ y ∨ z)⋅ (x ∨ z)⋅ (y ∨ z) – КНФ.

    Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все

переменные данного списка (либо сами, либо их отрицания), причем в

одинаковом порядке.

Например, выражение (x ∨ y ∨ z)⋅ (x ∨ z)⋅ (y ∨ z) является СКНФ.

 

Представление логических функций в виде СДНФ (СКНФ)

    Если булева функция не равна тождественному нулю, то ее можно

представить в виде СДНФ по ее таблице истинности следующим образом: берем только те наборы переменных (х1,х2, …,хn), для которых f(х1,х2, …,хn)=1, и составляем простую конъюнкцию для этого набора так: если хi = 0, то берем в этой конъюнкции xi , если хi = 1, то берем хi. Составляя дизъюнкцию этих простых конъюнкций, придем к СДНФ. Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание. По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х1, х2, …, хп), для которых f(x1, x2,…, xn) = 0, причем если хi = 1, то в этой дизъюнкции берем xi , если же хi = 0, то берем хi.

Пример 1. Составить для импликации и сложения по модулю 2 СДНФ и   СКНФ. Составим таблицу истинности для рассматриваемых функций.

  Таблица 4

 

СДНФ для этих функций: f (x, y) = x → y = xy ∨ xy ∨ xy 1 ;

f (x, y) = x + y = x y ∨ xy 2

СКНФ для этих функций: f (x, y) = x → y = x ∨ y 1

f (x, y) = x + y = (x ∨ y)(x ∨ y) 2

Пример 2. Составить СДНФ и СКНФ на примере мажоритарной системы подсчета голосов, т.е. системы, дающей сигнал «1» на выходе, если более половины сигналов на входе «1». Составим таблицу истинности для рассматриваемой функции (табл. 5).

 

 

 

Таблица 5

 

  В совершенной дизъюнктивной нормальной форме заданная функция

записывается в виде:

у(a,b,c) = а ⋅в ⋅с ∨ а ⋅ в ⋅с ∨ а ⋅в ⋅с ∨ а ⋅в ⋅с ,

т.е. функция записана для тех строк, где она обращается в 1.

  В совершенной конъюнктивной нормальной форме заданная функция

записывается в виде:

у(a,b,c) = (а ∨ в ∨ с)⋅ (а ∨ в ∨ с)⋅ (а ∨ в ∨ с)⋅ (а ∨ в ∨ с),

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

Как указано выше, в таблице 3 приведен полный набор логических

функций для 2-х переменных.

Покажем эквивалентность СНДФ и СКНФ на примере функции НЕ ИЛИ

(это функция f8 таблицы 3). Таблица истинности функции имеет  следующий вид:

Таблица 6

    Отсюда имеем СДНФ в виде f (x, y) = x ⋅ y 8 и СКНФ в виде -

f (x, y) = (x ∨ y)⋅ (x ∨ y)⋅ (x ∨ y) 8 . Добавим в выражение для СКНФ член (x ∨ y) и получим:

f (x, y) = (x ∨ y)⋅ (x ∨ y)⋅ (x ∨ y)⋅ (x ∨ y)= x ⋅ y 8 ,

т.к. (x ∨ y)⋅ (x ∨ y)= x ⋅ x ∨ x ⋅ y ∨ x ⋅ y ∨ y ⋅ y = x(y ∨ y)= x , x ⋅ x = 0 ;

y ⋅ y = 0 Аналогично (x ∨ y)⋅ (x ∨ y)= y . Таким образом, СДНФ и СКНФ

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

дизъюнкция и отрицание является полным набором. Упрощение логических выражений можно произвести с помощью методов минимизации. Для несложных функций используются алгебраические преобразования. Для более сложных с числом переменных от 3 до 6 применяют карты Карно.

 

Минимизация логических функций с помощью алгебраических

преобразований

    Рассмотрим пример минимизации логической функции. Упростим

полученную в примере 2 СНДФ функции y, добавив в уравнение член а в с

дважды (это допустимо, т.к. а ∨ а ∨ а = а):

в с (а а) а с (в в) а в (с с) а в а с в с

у а в с а в с а в с а в с а в с а в с

= ⋅ ⋅ ∨ ∨ ⋅ ⋅ ∨ ∨ ⋅ ⋅ ∨ = ⋅ ∨ ⋅ ∨ ⋅

= ⋅ ⋅ ∨ ⋅ ⋅ ∨ ⋅ ⋅ ∨ ⋅ ⋅ ∨ ⋅ ⋅ ∨ ⋅ ⋅ =

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

законы алгебры логики, наиболее употребительны законы отрицания и правило де Моргана, например:

 y =(a∨в∨с)∨a∨c∨a⋅в∨(а⋅в)=(а⋅в⋅с)∨а∨с∨а⋅в∨(а∨в).

    Первый и последний член преобразованы на основании закона отрицания.

Далее сгруппируем члены уравнения.

у =(а⋅в⋅с∨а⋅в)∨(а∨а)∨с∨в =а⋅в⋅(с∨1)∨а∨с∨в =а⋅в∨а∨с∨в,

т.к. с ∨ 1 = 1 ; а ∨ а = а

    Можно еще упростить, добавив а ⋅ в (на основании аксиомы а ∨ а∨ а = а)

и снова сгруппировав члены уравнения: у = (а ⋅ в ∨ в)∨ (а ⋅ в ∨ а)∨ с = в ⋅ (а ∨1)∨ а ⋅ (в ∨1)∨ с = а ∨ а ∨ в ∨ с ,

(на основании закона  поглощения), таким образом, мы имеем: у = (а ∨ в ∨ с)∨ а ∨ с ∨ а ⋅ в ∨ (а ⋅ в)= а ∨ а ∨ в ∨ с

 

Минимизация логических функций с помощью карт Карно

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

Карно – это представление таблицы истинности в виде прямоугольной таблицы с соответствующим числом клеток, каждая из которых отвечает определенной конъюнкции (произведению переменных). Переменные следуют так, чтобы в соседних клетках отличалась только одна из них, т.е. вместо чередования 00; 01; 10 и 11 используют код Грея 00; 01; 11 и 10. Внимание: необходимо учесть, что рабочей частью карты Карно является часть, выделенная жирным шрифтом (таблица 5) и содержащая в нашем случае 8 клеток, соответствующие 8 строкам таблицы истинности.

Например, левая верхняя клетка, которой соответствуют а;в (указаны

выше) и с (указана слева), очевидно, отвечает 1-ой строке таблицы с номером 0. Правая нижняя клетка карты, которой соответствуют переменные а;в и с , отвечает строке таблицы с номером 5, и т.д. Карта Карно для функции, рассмотренной выше в примере 2, представлена в таблице 7.

Таблица 7

 

В клетки карты заносим 0 или 1 в соответствии с таблицей истинности 5.

Далее необходимо в карте выделить один или несколько прямоугольников,

включающих возможно большее число клеток с «1». При этом прямоугольники могут содержать 2 n клеток, т.е.1, 2, 4, 8 и т.д.

    Одна и та же клетка может входить в несколько прямоугольников. В

нашем случае таких прямоугольников можно выделить 3, каждому из них соответствует один член искомого уравнения. Для вертикального прямоугольника можно записать а ⋅ в ⋅ с ∨ а ⋅ в ⋅ с = а ⋅ в ⋅ (с ∨ с) = а ⋅ в .