Что такое полная система логических операций

Что такое полная система логических операций

Практическая логика.

Полные системы логических операций

Каждая мыслимая логическая операция над n высказываниями определяется соответствующей функцией f(A₁,А₂. A_n) от n логических переменных, принимающей значения И или Л для каждого набора значений своих аргументов. Такая функция называется логической и задаётся таблицей

Теорема (об определении логических функций).

Любая n-местная (n>0) логическая функция определяется некоторой пропозициональной формулой, содержащей только операции ¬и Ъ .

Пример. Для операции «исключающая дизъюнкция» A Е B построение определяющей формулы, описанное в доказательстве теоремы, имеет вид

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

Существуют полные наборы операций, содержащие всего по одной операции. Это системы < Ї >и < ­ >, где операции Ї и ­ определяются формулами:

Это следует из тавтологичности формул

а также из полноты систем операций <¬, Ъ >и <¬, Щ >.

Источник

Функционально-полные системы логических функций. Свойства логических функций

Полнота системы логических функций

Теорема. Пусть даны две системы логических функций:

( 4.1)

( 4.2)

Если система (4.1) полна и каждая её функция может быть выражена как суперпозиция функций системы (4.2), тогда система (4.2) является полной.

Правила перехода от представления ФАЛ в виде ДНФ к функции, представленной в базисе «Штрих Шеффера»

Правила перехода от представления ФАЛ в виде КНФ к функции, представленной в базисе «Стрелка Пирса»

Свойства логических функций

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

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

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

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

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

000 и 111; 001 и 110; 010 и 101; 011 и 100.

Например, для функции дизъюнкции f (x1, x2) = x1 v x2 двойственной будет функция конъюнкции f * (x1, x2) = x₁ & x₂.

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

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

Например, если X = (0000) и Z = (0001), то наборы сравнимы, и X z₁, но x₂ функция называется монотонной, если для всех пар сравнимых наборов при любом возрастании набора значение этой функции не убывает, т.е. сохраняет свое значение или изменяется с 0 на 1. Здесь, аналогично обычной математике, можно рассматривать монотонно возрастающие и монотонно убывающие функции, но для наших дальнейших рассуждений это не будет иметь какого-либо значения.

Т.е. для монотонной логической функции должно выполняться условие: если для сравнимых наборов X = функция : F1(x₁, x₂) = x₂,

немонотонная функция :

Источник

Функционально полные системы логических функций

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

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

f = х₁ + х₂ = =

В наборе (ИЛИ, НЕ) функцию И можно выполнить через операции ИЛИ и НЕ следующим образом: f = х₁ + х₂ = = .

Таким образом, набор функций (И, ИЛИ, НЕ) обладает избыточностью.

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

Для вычисления переключательной функции путем выполнения операции И—НЕ ее необходимо вначале представить в ДНФ. Выполнив далее двойное отрица­ние и применив закон отрицания, мы приведем ЛФ к требуемому виду.

Например, ЛФ f = ₃ + х₃ в соответствии с описанными действиями при­водится к виду

f = =

По этому выражению логическая функция реализуется на элементах И—НЕ в соответствии с рис. 3.8.

Для реализации ЛФ в базисе ИЛИ—НЕ необходимо записать её сначало в КНФ. Выполнив далее двойное отрицание и применив закон отрицания, получим искомую форму.

Например, ЛФ f = (х₁+ ₂)( ₁ + х₃)( ₁+ х₂) в соответствии с этим примет вид

f = =

По этому выражению логическая функция реализуется на элементах ИЛИ—НЕ в соответствии с рис. 3.9.

3.3.1 Метод непосредственных преобразований

Метод Карно-Вейча

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

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

Целью минимизации логической функции является построение экономичных схем компьютеров и уменьшение стоимости её технической реализации. Критерий, соответственно которому выполняется минимизация, далеко не однозначный и зависит как от типа задачи, так и уровня развития технологии.

Основные требования к задаче синтеза: минимальное число элементарных конъюнкций или дизъюнкций в логической формуле и однородность исполь­зуемых операций. Кроме требований минимизации ставится ряд ограничений и условий на выбор элементной базы для синтезированного устройства.

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

3.3.1 Метод непосредственных преобразований

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

Важные теоремы, отражающие основные соотношения алгебры логики (Табл. 3.9)
x + 0 = x	x ∙ 1 = x
x + 1 = 1	x ∙ 0 = 0
x + x = x	x ∙ x = x
x +s w:ascii=»Cambria Math» w:h-ansi=»Cambria Math»/> x «> = 1	x ∙ = 0
= x	—
x + y = y + x	x ∙ y = y ∙ x
x + x ∙ y = x	x (x + y) = x
x + (y + z) = (x + y) + z	x (y ∙ z) = (x ∙ y) z
x + y ∙ z = (x + y) (x + z)	x (y + z) = x ∙ y + x ∙ z
=s w:ascii=»Cambria Math» w:h-ansi=»Cambria Math»/> x «> ∙s w:ascii=»Cambria Math» w:h-ansi=»Cambria Math»/> y «>	x ∙ y = x + y
(x + y) (s w:ascii=»Cambria Math» w:h-ansi=»Cambria Math»/> x «> + y) = y	(x ∙ y) +(s w:ascii=»Cambria Math» w:h-ansi=»Cambria Math»/> x «> ∙ y) = y

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

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

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

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

Метод Квайна применяется к функциям, задан­ным в СДНФ (возможно задание и в СКНФ), и проводится, как правило, в два этапа.

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

При этом получается конъюнкция А ранга п-1, а конъюнкции Ах и А помечаются и срав­ниваются также со всеми другими конъюнкциями ранга п с целью выполнения операции склеивания.

Результатом выполнения последовательности попарного сравнения и склеивания конъюнкций ранга п является группа конъюнкций ранга п —1 и непомеченные конъюнкции ранга г. Непомеченные конъюнкции ранга п не участ­вовали в склеивании, следовательно, являются простыми импликантами и включаются в сокращенную ДНФ.

Конъюнкции ранга п—1 вновь подвергаются попарному сравнению и склеиванию, как это было описано выше для конъюнкций ранга п; в результате имеем группу конъюнкций ранга п—2 и непомеченные конъюнкции ранга п—1, которые являются простыми импликантами, включаемыми далее в сокращенную ДНФ.

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

Рассмотрим реализацию первого этапа на примере функцииЛФf

f = + + + + (3.5)

где для удобства последующего изложения над конъюнк­циями записаны присвоенные им номера.

Анализируя в выражении всевозможные пары конъюнкций 1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5, находим, что операция склеивания выпол­няется между парами 1-3 по х₁, 2-5 по х₁, 3-4 по х₃, 4-5 по х₂.

Таким образом, все конъюнкции исходной СДНФ участвуют в склеивании и помечаются подчеркиванием. 1 2 3 4

Теперь исходная СДНФ (3.5) записывается в виде f= _{2 3} + х₂х₃ + х_{1 2} + х₁x₃. (3.6)

Продолжая для выражения (3.6) процедуру склеивания, сравниваем попарно конъюнкции 1-2, 1-3, 1-4, 2-3, 2-4 и 3-4. Эти пары конъюнкций между собой не скле­иваются. Поэтому полученная запись ЛФ (3.6) представ­ляет собой сокращенную ДНФ исходной ЛФ (3.5), содер­жащей только простые импликанты.

Второй этап заключается в переходе от сокращенной ДНФ к тупиковым ДНФ и выборе среди них МДНФ.

Тупиковой называется такая ДНФ, среди простых импликант которой нет ни одной лишней. При этом под лишней понимается такая простая импликанта, удаление которой не влияет на значение истинности этой функции.

Воз­можны случаи, когда в сокращенной форме нет лишних простых импликант. Тогда сокращенная ДНФ является тупиковой.

Для выявления лишних простых импликант строится импликантная матрица, которая называется также матри­цей (таблицей) покрытий. Каждая строка импликантной матрицы соответствует одной простой импликанте, а столбцы — конституантам единицы, которыми они и помечаются. Для рассматриваемого примера импли­кантная матрица приведена в табл. 3.14.

Нахождение тупиковых ДНФ по импликантой матри­це начинается с разметки матрицы. При этом каждая импликанта сравнивается со всеми конституантами еди­ницы. Если импликанта является собственной частью некоторой конституанты, то на пересечении строки и столбца ставится условный знак, например – плюс (+).

Кон­ституенты единицы, помеченные в строке с простой импликантой, поглощаются (покрываются) этой простой импликантой. Это значит, что на соответствующих набо­рах данная импликанта обеспечивает единичные значе­ния ЛФ.

Например, простая импликанта _{2 3} входящая в сокращенную ДНФ (3.6) рассматриваемого примера, является собственной частью конституант единиц и , и поэтому в строке с данной простой импли­кантой (табл. 3.13) поставлены две пометки X в соответ­ствующих колонках. Аналогично размечены другие стро­ки табл. 3.13.

Выявление лишних простых импликант выполняется следующим образом:

-В импликантной таблице условно вычеркивается строка с проверяемой простой импликан­той вместе с соответствующими пометками в строке.

-Если при этом окажется, что в каждом столбце импли­кантной таблицы остается, хотя бы по одной пометке, проверяемая импликанта является лишней и ее следует удалить.

-Оставшиеся простые импликанты покрывают все единичные значения ЛФ.

-Испытание каждой последую­щей простой импликанты возможно лишь после удаления уже выявленных лишних простых импликант.

-Изменение последовательности испытаний и удаления лишних членов сокращенной ДНФ может привести к различным тупико­вым формам ЛФ, из которых выбирается МДНФ.

Из табл. 3.13 видно, что только простая импликанта 1 обеспечивает единичное значение ЛФ на наборе 000, а импликанта 2 — на наборе 011 (соответствующие этим наборам столбцы обозначены конституантами единицы и ), поэтому эти простые импликанты обя­зательно войдут во все тупиковые ДНФ.

Простую импликанту 3 можно считать лишней. Однако, если ее сохра­нить, лишней можно считать простую импликанту 4.

Таким образом, для ЛФ возможны две тупиковые формы:

в которую не включена лишняя импликанта х_{1 2}

в которую не вошла лишняя импликанта x₁x₃.

Тупиковые формы (3.7) и (3.8) имеют одинаковое суммарное количество переменных, поэтому любую из них можно выбрать в качестве минимальной (МДНФ).

Эта ЛФ реализует­ся схемой с ценой С = 9 (3 х 2 + 3 = 9).

Пример 4. Логическую функцию F в виде СДНФF = х₂ +х₁ +х₁ х₃+х₁х₂ +x₁x₂x₃ можно минимизировать следующим образом:

1. Добавим к данной функции слагаемое х₁х₂ , которое уже есть в данной функции, используя правило 3 (x ∙ x = x).

F = х₂ + х₁ + х₁ х₃ +х₁х₂ + x₁x₂x₃ + х₁х₂

2. Применим метод склеивания (правило 11) к одинаково подчеркнутым элементарным конъюнкциям (x ∙ y + ∙ y = y):

Результат склеивания: F = х₂ + х₁ + x₁x₂

3. Применим тот же метод склеивания для двух последних элементарных конъюнкций:

Окончательный результат: Fmin =F_T = х₂ + x₁

Полученная в результате минимизации логическая функция называется тупиковой. Логическая функция может иметь несколько тупиковых форм.

Пример5.Найти минимальную форму функции, заданной СДНФ

F(a, b,c) =а c + c + + + ab = abc.

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

F(a,b,c) = + c + ac + ab + b + .

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

Очевидно, что анализируемой функции отвечают две минимальных нормаль­ных формы F₂(a,b,c) и F₃

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

1. Сначала к членам СКНФ применяют операцию полного склеивания.

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

3. Приводят подобные члены и применяют операцию поглощения.

4. Полученную таким способом ДНФ минимизируют в указанном выше по­рядке.

Метод Карно-Вейча

Метод диаграмм Вейча (карт Карно) удобен для минимизации ЛФ, содержащих обычно не более пяти переменных.

Метод диаграмм Вейча, усовершенствованный Карно, применяется в том слу­чае, если число аргументов не более 5. Представляют собой определенную таблицу истинности и отличаются друг от друга способом обозначения строк и столбцов таблицы истинности.

Каждой комбинации переменных можно поставить в соответствие клетку карты Карно.

В клетку записывается значение функции (0 или 1) для данной комбинации входных переменных.

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

х2	2
х1
1

Диаграмма Вейча для двух переменных х₁ и х_2.

х2х3	х2 3	2 3	2х3
х1
1

Диаграмма Вейча для трех переменных х₁, х₂ и х₃

х3х4	х3 4	3 4	3х4
х1х2
х1 2
1 2
1х2

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

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

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

При проведении контуров придерживаются следующих правил:

—1 в крайних клетках одного столбца или одной строки могут включаться в один контур;

-каждый контур должен включать как можно большее число клеток с 1, а общее число контуров должно быть как можно меньшим.

В простую импликанту, описывающую контур, включаются те переменные, которые во всех клетках контура имеют либо только прямое, либо только инверсное значение.

Пример 1. Минимизировать ЛФ F = х₂ + х₁ + ₁ с помощью диаграмм Вейча.

х2	2
х1
1

1. Заполняем диаграмму Вейча для двух переменных.

х2	2
х1	1
1

1. Проводим два контура, охватывающие клетки с единицами.

2. Находим простые импликанты описывающие контур, для чего выясняем от каких переменных не зависит данный контур.

а) вертикальный контур охватывает строки с х₁ и ₁, следовательно в простую импликанту, описывающую горизонтальный контур х₁ входить не будет.

б) горизонтальный контур охватывает строки с х₂ и ₂, следовательно в простую импликанту, описывающую вертикальный контур х₂ входить не будет.

4. Следовательно, ЛФ будет иметь МДНФ: F = ₁ + ₂.

Пример 2.Минимизировать ЛФ F=х₁х₂+х₁ х₃+ ₁ х₃+ ₁х₂ с помощью диаграмм Вейча.

1. Приводим логическую функцию к СДНФ:

F = х₁х₂ (х₃+ ) + х₁ х₃+ ₁ х₃ + ₁х₂ = х₁х₂х₃ + х₁х₂ + х₁ х₃+ ₁ х₃ + ₁х₂

х2х3	х2 3	2 3	2х3
х1
1

2. Заполняем диаграмму Вейча для трех переменных.

х2х3	х2 3	2 3	2х3
х1
1

3. Проводим три контура, охватывающие клетки с 1.

1 контур (зеленый) –охватывает клетки х₁х₂х₃ и х₁ х₃

2 контур (красный) –охватывает клетки х₁х_{2 1} х₃

3 контур (красный) –охватывает клетки х₁ х_{3 1} х₃

4. Находим простые импликанты описывающие контур, для чего выясняем от каких переменных не зависит данный контур.

5. Следовательно, ЛФ будет иметь МДНФ: F =х₁х₃ + х₂ + х₃

Карты Карно

Для минимизации функции с числом переменных n ≤ 6 используют карты Карно.

Карты Карно для функции трех переменных F(х₁ х₂, х₃) показаны на рис. 3.10.

· Каждая клетка карты Карно однозначно соответствует одному набору таблицы истинности для функции трех переменных (рис. 3.10, а) или минтермам этой функции (рис. 3.10, б).

· При минимизации для каждого минтерма, входящего в СДНФ функции, ставит­ся единица, а другие клетки не заполняются.

Рисунок 3.10 – Карты Карно для функций трех переменных

Например, заполнение карты Карно для функции, заданной табл. 3.12, показано на рис. 3.6, г.

Минтермы в соседних клетках карты Карно в строке (включая верхние и ниж­ние) или в столбце (включая крайние) отличаются значением одной переменной, что позволяет выполнить операцию склеивания по этой переменной.

Например, на рис. 3.6, г минтермы X₃ и Х₂ Х₃ (клетки с номерами 1 и 3) отличаются значением переменной Х₂, поэтому они склеиваются по ней и представляются конъюнкцией двух переменных Х₃.

Аналогично для минтермов Х₁ и Х₁ Х₂ (номера клеток 4 и 6) склеивание происходит по переменной Х₂ и получают конъюнкцию Х₁ .

В результате минимизации функции Р(Х₁ Х₂, Х₃) получают ее минимальное выражение

Р = Х₃vХ₂ Х₃vХ₁ .

Перечислим общие правила минимизации.

1.Изображают карту Карно для n переменных и производят разм

Источник