Способы представлений функций алгебры логики

Способы задания функций алгебры логики.

Дата добавления: 2015-08-31 ; просмотров: 9966 ; Нарушение авторских прав

При сопоставлении функций АЛ с дискретными автоматами аргументы функций, сопоставляются с входами, а сами функции с выходами дискретного автомата.

Поскольку дискретный автомат имеет конечное число входов, то мы будем иметь дело с функцией конечного числа аргументов. Если автомат имеет m входов, то количество входных переменных тоже m и число возможных комбинаций наборов значений этих входных аргументов (переменных) К=2 m .

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

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

Таблица истинности содержит 2 m строк, m столбцов (по количеству входов) и один столбец для записи значения функции.

Например: пусть требуется задать функцию трех переменных F1(Х1,Х2,Х3) (рис. 1.4), т.е. автомат на три входа и на один выход, следовательно, M=3, К=8.

Следующий способ задания дискретного автомата – числовой. В Этом случае функция задается в виде десятичных эквивалентов номеров наборов аргументов, при которых функция принимает единичное значение. Например, для рассмотренного выше примера функция F1 принимает единичные значения на наборах переменных со следующими номерами: 1, 2, 5, тогда числовой способ задания будет иметь вид

.

Координатный способ. При этом способе дискретный автомат задается с помощью карты его состояния, которая известна как карта Карно.

Карта Карно содержит 2 m клеток по числу наборов значений переменных. Каждая клетка определяется координатами строк и столбцов, соответствующими определенному набору переменных. Все входные переменные разбиваются на 2 группы так, что одна группа определяет координаты строк, а другая — координаты столбцов. В каждой клетке карты Карно проставляется соответствующее значение функции на заданном наборе. Пример задания функции трех переменных приведен на рис. 1.5. Числовое выражение этой функции выглядит так:

Пример построения карты Карно для функции 4-х переменных. Пусть функция задана в числовой форме и имеет вид:

,

следовательно, К=16, m=4.

Сначала проводим разметку координат карты Карно без указания значений функции. Для удобства воспользуемся указанием «шапки» в виде прямых линий, “под” которыми переменные входят в значение координат без отрицания (рис.1.6). Таким образом, по столбцам и по строкам переменные входят без отрицания в пределах линии-шапки.

Для наглядности координаты клеток карты Карно указаны в трех формах: в виде наборов переменных; в виде двоичного числа, соответствующего порядковому номеру набора переменных; в десятичном эквиваленте номеров наборов переменных. На практике координаты внутри клеток не записывают (рис. 1.7), в клетках указываются единичные значения функции, соответствующие “координатным” наборам переменных. Нулевые значения функции в клетки можно не записывать, т.е. клетки, координаты которых определяются наборами переменных с нулевыми значениями функции, можно оставить пустыми.

Следует отметить, что перестановка местами переменных Х1 и Х2, а так же переменных Х3 и Х4 допускается, допускается также перестановка местами переменных Х1Х2 и Х4Х3. При построении карты Карно, т.е. при задании логической функции, указывают лишь внешние элементы разметки координат (рис. 1.7).

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

Например: .

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

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

Из таблицы истинности видно, что функция принимает значение логической единицы только на трех наборах переменных, т.е. на 2, 4 и 5-м наборах. Для второй строки (второго набора переменных) можно записать: Х1=0, Х2=1, Х3=0, следовательно, функция f(0,1,0)=1. Принято (по умолчанию) считать, что если переменная в «нормальном» состоянии имеет значение логической единицы, а в инверсном — логического нуля, тогда функцию для второй строки можно представить в виде `X<sub>1</sub>Х<sub>2</sub>X<sub>3</sub> = 1. Для четвертой строки — `X₁X₂Х₃ = 1 и для пятой строки — Х₁X₂Х₃ = 1. Аналитическое выражение функции выглядит как

.

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

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

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

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

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

Например: .

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

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

Пример записи СНКФ. Пусть функция представлена в виде таблицы истинности (рис. 1.9).

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

Общее количество функций АЛ отm переменных R=2 k , где k=2 m . Рассмотрим элементарные функции от двух переменных

Источник

Национальная библиотека им. Н. Э. Баумана
Bauman National Library

Персональные инструменты

Функции алгебры логики

Содержание

Формы представления

Табличное представление функций алгебры логики

Функцию алгебры логики можно задать, перечислив её значения для каждого входного булевого вектора, например

x1	x2	…	xn-1	xn	f(x1,x2,…,xn)
0	0	…	0	0	1
0	0	…	0	1	0
0	0	…	1	0	0
0	0	…	1	1	0
⋮	⋮	⋮	⋮	⋮	⋮
1	1	…	0	0	0
1	1	…	0	1	1
1	1	…	1	0	0
1	1	…	1	1	0

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

Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее, чем таблицы истинности. При этом функция представляется в виде формулы над некоторой полной системой функций Σ = < f 1 , … , f n ><\displaystyle \Sigma = \> . При этом возникают следующие вопросы:

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

Дизъюнктивная нормальная форма (ДНФ)

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

Простой конъюнкцией называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза.

Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: a b ¯ c ∨ a b c ¯ ∨ a ¯ b c ¯ <\displaystyle a \overlinec\lor a b \overline\lor\overline b\overline> .

Конъюнктивная нормальная форма (КНФ)

Конъюнктивная нормальная форма или КНФ — это конъюнкция простых дизъюнкций.

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

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

Алгебраическая нормальная форма (АНФ или полином Жегалкина)

Алгебраическая нормальная форма или полином Жегалкина — форма представления логической функции в виде полинома с коэффициентами «0» и «1», в котором в качестве произведения используется операция конъюнкции («И», AND), а в качестве сложения — сложение по модулю 2 (исключающее «ИЛИ», XOR).

Способы получения АНФ:

Замкнутые классы булевых функций

Предполные классы

Другие замкнутые классы

Также можно выделить следующие замкнутые классы:

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

Полнота системы, критерий Поста

«

Система булевых функций F является полной тогда и только тогда, когда она целиком не принадлежит ни одному из замкнутых классов S , M , L , T 0 , T 1 <\displaystyle S,M,L,T_0,T_1>.

»

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

Классификация

Функции алгебры логики можно классифицировать:

• По количеству аргументов функции, различают нульарные (n = 0, булевы константы), унарные (n = 1), бинарные (n = 2), тернарные (n = 3) булевы функции и функции от большего числа операндов;
• По зависимости значения функции от перестановки её входных аргументов различают симметричные булевы функции (значение которых зависит только от количества единиц на входе) и несимметричные булевы функции (значение которых так же зависит от перестановки её аргументов);
• По принадлежности к основным замкнутым классам (линейные, самодвойственные функции);
• По количеству единиц и нулей в таблице истинности различают сбалансированные булевы функции (с одинаковым количеством «0» и «1» в векторе значений) и несбалансированные булевы функции.

Источник

Читайте также:  Суффиксальный способ словообразования с нулевым суффиксом