Функции алгебры логики способы их задания

Функции алгебры логики способы их задания

СБОРНИК ЗАДАЧ ПО АЛГЕБРЕ ЛОГИКИ

УЧЕБНОЕ ПОСОБИЕ

К практическим занятиям

по курсу «Теория дискретных устройств»

(рукопись)

УДК 62.50

Туйгунова А.Г., Худоногов И.А.Сборник задач по алгебре логики: Учебное пособие к практическим занятиям по курсу «Теория дискретных устройств». – Красноярск: КрИЖТ ИрГУПС, 2014. – 49 с.

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

Ил. 26. Табл. 16. Библиогр. 8 назв.

Авторы: А.Г. Туйгунова, канд. техн. наук, доцент кафедры «Транспортные системы» КрИЖТ ИрГУПС;

И.А. Худоногов, д-р техн. наук, профессор кафедры «Электроснабжение железнодорожного транспорта» ИрГУПС

ОГЛАВЛЕНИЕ

1. СПОСОБЫ ЗАДАНИЯ ФУКЦИИ АЛГЕБРЫ ЛОГИКИ. 5

2. МИНИМИЗАЦИя ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ. 12

3. Преобразование логических функций. 26

4. ПРЕДСТАВЛЕНИЕ ФАЛ В РАЗЛИЧНЫХ БАЗИСАХ. 27

5. Реализация ФАЛ на контактных и бесконтактных элементах 28

6. СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ. 35

6.1. Синтез комбинационных схем с несколькими выходами. 35

6.2. Синтез специальных комбинационных схем. 40

Задания для самостоятельной работы. 44

БИБЛИОГРАФИЧЕСКИЙ СПИСОК. 49

Введение

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

Сборник задач состоит из семи разделов. Первый раздел позволяет закрепить знания по способам задания и основным законам функций алгебры логики (ФАЛ). Задачи минимизации полностью определенных логических выражений ФАЛ приведены во втором разделе. Третий раздел посвящен преобразованию и упрощению булевых выражений. В четвертом разделе показано представление ФАЛ в различных базисах. Способ реализации ФАЛ на релейно-контактных схемах приведен в пятом разделе. В шестом разделе показан синтез комбинационных схем с несколькими выходами. В седьмом разделе приведены примеры для самостоятельного углубления знаний студентами в теории булевых функций. Решение задач позволит студенту освоить методику формализации содержательной постановки задачи в виде булевого уравнения, логической диаграммы или релейно-контактной схемы и овладеть приемами решения задач.

СПОСОБЫ ЗАДАНИЯ ФУКЦИИ АЛГЕБРЫ ЛОГИКИ

Методы анализа и синтеза всех классов дискретных автоматов строят на базе алгебры логики. Алгебра логики — это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Начало алгебры логики было положено ирландским математиком Д.Булем (1815-1864).

Функцию f (х1, х2, . хп) называют функцией алгебры логики (ФАЛ), если она, как и ее переменные (аргументы), может принимать только два значения: логического 0 и логической 1. Переменные ФАЛ сопоставляют со значениями сигналов на входах дискретного автомата, а значения функции алгебры логики — со значениями сигналов на его выходах.

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

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

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

Решение вопросов анализа и синтеза схем дискретных уст­ройств железнодорожной автоматики, телемеханики и связи связано с преобразованием выражений, которые содержат ФАЛ основного базиса. Запись, содержащая двоичные переменные, соединенные знаками логического сложения, умножения и инверсии, называют логическим выражением. Такое выражение однозначно определяет комбинационное устройство, построенное на элементах И, ИЛИ, НЕ.

При табличном способе ФАЛ задают таблицей ее значений в зависимости от значений переменных. Таблицу, в которой для всех наборов переменных приводятся значения ФАЛ, называют таблицей истинности. Например, в таблице 1 заданы две ФАЛ трех переменных: f (x1, х2, . хn) и φ1, x2, . хn).

Номер x1 х2 х 3 f φ

Совокупность значений переменных называют набором (точкой). Каждому набору переменных соответствует определенное значение функции. Если ФАЛ содержит п переменных, двоичные числа будут разрядные и, следовательно, общее число наборов определяется по формуле k = 2 п . При трех аргументах можно образовать восемь наборов. Следовательно, приведенные в табл. 1 функции f (x1, х2, . хп) и φ (х1, x2, . хп) определены на восьми наборах. При этом каждый набор представляет собой трехразрядное двоичное число.

Читайте также:  Конфигурация системы через командную строку

При каждом наборе переменных возможны два значения ФАЛ: логического 0 или 1. Поэтому в соответствие каждой ФАЛ можно поставить k-разрядное двоичное число. Значит, число функций алгебры логики п аргументов определяется формулой 2 k . При п переменных таблица содержит 2 п строк (по числу наборов), п столбцов (по числу переменных) и один столбец значений функции, соответствующих каждому набору (сочетанию) аргументов.

При графическом способе наборам значений переменных ФАЛ сопоставляются точки п-мерного пространства. Множество 2 п наборов определяет множество вершин п-мерного единичного куба. Вершинам куба соответствуют наборы значений переменных и приписаны значения функции на этих наборах, т.е. областью определения ФАЛ, зависящей от п переменных, является множество вершин единичного п-мерного куба. Куб называют единичным, так как каждое его ребро соединяет вершины, наборы которых различаются одной переменной. Функции f (x1, х2, . хп) и φ (х1, x2, . хп) — заданные таблицей истинности (см. табл. 1), можно задать графически (рис. 1).

При координатном способе функцию задают в виде координатной карты состояний, которую называют картой Карно. Карты представляют собой прямоугольные таблицы, разделенные горизонтальными и вертикальными линиями на клетки. Общее число клеток соответствует числу наборов функции. Все переменные функции разбивают на две группы, Одна группа переменных определяет выбор строки, другая — столбца. На пересечении строки и столбца находится клетка, в которую записывают значение функции при соответствующем наборе переменных. Аргументы разделяются на группы так, чтобы в соседних клетках наборы различались только значением одной переменной. Карты Карно для двух, трех и четырех и пяти переменных приведены соответственно на рис. 2,а, б, в, г. В каждую из клеток карты Карно трех переменных вписаны значения функции f (x1, х2, . хп) заданной таблицей истинности (см. табл. 1). На рис. 3 в скобках в каждой из клеток карты Карно проставлены десятичные номера соответствующих наборов.

Рисунок 1 — Графическое задание ФАЛ

При числовом способе каждому набору переменных ставят в соответствие определенное число в двоичной системе исчисления и присваивают соответствующий номер. Переменным x1, х2, . хп приписывают соответственно веса 2 ,2 ,…,2 ,2 . Функцию задают в виде десятичных номеров тех наборов переменных, на которых она принимает значение 1. Поскольку номер внутреннего состояния зависит от присвоенных переменным весов условимся записывать эти переменные в порядке уменьшения весов. Такую запись называют базой системы нумерации. Так, например, если имеются три переменные x1, х2, х3, причем переменной x1 присвоен вес 2 2 , переменной х2 – 2 1 , а переменной х3 — 2 0 , то база системы нумерации будет x1, х2, х3.

В тех случаях, когда при некоторых наборах аргументов значения функции «безразличны» (не определены), при задании ФАЛ табличным, координатным и графическим способами на таком наборе проставляются знаки «

Рисунок 2 — Координатный способ задания ФАЛ: а) для двух аргументов; б) для трех аргументов; в, г) для четырех аргументов

Рисунок 3 — Задание ФАЛ трех переменных координатным способом

Рисунок 4 — Табличное задание не полностью определенной функции

При числовом способе задания не полностью определенной функции указываются множества наборов, при которых ФАЛ принимает значения 1 (обязательные номера), и наборов, при которых функция равна 0 (запрещенные номера) или ее значения безразличны (условные номера):

.

; .

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

Таблица 2 — Перечень логических операций, используемых при записи логических выражений

Обозначение логических операций Таблица истинности Как читается Название операции
Х1
Х2
Х1 Х2 Х1 ۸ Х2 Х1 & Х2 Х1 и Х2 Конъюнкция; логическое И ; логическое произведение
Х1 ۷ Х2 Х1 + Х2 Х1 или Х2 Дизъюнкция; логическое ИЛИ; логическая сумма
Х1 Х2 + Х2 Х1→ Х2 Если Х1, то Х2; Х1 влечет Х2; Х1 имплицирует Х2 Импликация
Х1

Х2 Х1≡Х2 Х1↔Х2

Х1 эквивалентно Х2 Эквивалентность; функция равнозначности Х1 Х2 или Х1 или Х2; Х1 неэквивалентно Х2 Функция неэквивалентности; функция неравнозначности; исключающее ИЛИ; сумма по модулю 2 Х1∆Х2 Х1 Х2 Х1→Х2 Х1 запрет по Х2; Х1, но не Х2 Запрет; отрицание импликации Х1│ Х2 Х1 и Х2 не совместны Штрих-Шеффера; логическое И-НЕ; отрицание конъюнкции Х1↓ Х2 не Х1 не Х2 Стрелка Пирса; логическое И-НЕ; отрицание дизъюнкции Х не Х Инверсия; логическое отрицание; логическое НЕ У

Алгебраическое выражение может быть составлено из наборов аргументов, на которых функция принимает значение 1, или из наборов аргументов, на которых она принимает значение 0.

Читайте также:  Поворот вектора вокруг оси

Например, можно записать ФАЛ трех аргументов в виде:

f = ( )

f =

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

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

.

В булевой алгебре действуют следующие законы:

и ;

и ;

и .

;

;

;

;

и ;

;

и ;

;

§ инверсии, правило де Моргана:

и .

Определение. Пусть`х nn-мерный двоичный вектор. Функция f(`х n ),`х n Î E2 n , принимающая значения 0 и 1, называется булевой функцией или функцией алгебры логики.

По числу переменных n функции алгебры логики называют одноместными ( n = 1), двухместными ( n = 2 ) и т.д.

Способы представления функций алгебры логики f (х n )зависят от представления всех наборов значений E2 n , которые принимает вектор её переменных`х n . Наиболее просто все возможные наборы можно перечислить в таблице, где они располагаются в лексикографическом порядке по возрастанию соответствующих им двоичных чисел. Значения истинности функции f помещаются в отдельном столбце, который называется вектором истинности функции f (х n ). Вся конструкция называется таблицей истинности функции f (х n ).

Рассмотрим элементарные функции, которые являются базовыми в алгебре логики.

1. Константы. Функции, определенные при любом числе переменных n и принимающие на всех наборах только одно значение истинности (0 или 1 ).

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

х F1 f2

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

x y f3 f4 f5 f6 f7 f8 f9

Функцию f9называют функцией Вебба или стрелкой Пирса. Обозначают: f9(х, у) = х ¯ у .

Определение. Символы Ø , &, Ú, Å, º, ®, |, ¯ ― называют логическими связками.

Для упрощения записи выражений приняты следующие соглашения о силе логических связок:

1) Ø― самая сильная (при отсутствии скобок применяется ранее других),

2) & ― вторая по силе,

3) связки Ú, Å, ®,|,¯равносильны,

4) связка ºсамая слабая.

Равносильные связки выполняются в порядке слева направо.

Функции 0, 1, f1– f9 называют элементарными. При помощи этих функций можно выразить более сложные n-местные функции алгебры логики (n ³3).

Определение. Соседними по переменной хi называют пары булевых векторов`a=(a1. , ai-1, 0, ai+1,. , an`b=(a1,. , ai-1, 1,ai+1, . an), различающиеся только по одной переменной хi. Существенными называются такие переменные хi функции f(х n ), для которых существует хотя бы одна пара соседних по хi наборов значений переменных``b, на которой f(a)¹ f(b). Если же изменение только одной переменной не влечет изменение функции, то эта переменная называется фиктивной.

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

Пример 1. Найти существенные и фиктивные переменные функции трех переменных f(х, у, z), таблица истинности которой приведена ниже.

х у z f

1. На наборах (0, 0, 0), (1, 0, 0), соседних по х, f(0, 0, 0)¹ f(1, 0, 0), следовательно, переменная х ― существенная.

2. Так как на всех парах наборов, соседних по у ― (0, 0, 0) и (0, 1, 0), (0, 0, 1)и (0, 1, 1), (1, 0, 0)и (1, 1, 0), (1, 0, 1)и (1, 1, 1)―функция принимает одинаковые значения, то у ― фиктивная переменная.

3. На наборах (0, 0, 0), (0, 0, 1), различающихся только значениями переменной z, f(0, 0, 0) ¹ f(0, 0, 1), следовательно, переменная z ― существенная.

Ответ: переменные х, z ― существенные, у ― фиктивная.

Для функции из примера 1 можно предложить формулу f(х, у, z) = x Å`z, в которую не входит фиктивная переменная у.

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

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

Данные функции имеют очевидный логический смысл и простую физическую реализацию. К пороговым относятся обе одноместные функции, существенно зависящие от своей переменной ― тождественная функция f1(х) = х и отрицание f2(х) =`х. Среди двуместных функций пороговыми являются 4 функции: 1) конъюнкция f3 = &, 2) дизъюнкция f4= Ú, 3) штрих Шеффера f8=| , 4) функция Вебба f9 =¯.

Читайте также:  Новые модели смартфонов сяоми 2018

Пороговый (скачкообразный) принцип действия рассмотренных двухместных функций f3, f4, f8 , f9позволяет ввести их аналоги на случай произвольных n — местных функций.

Определение. Обобщенными пороговыми называют следующие n — местные функции:

1) обобщенная конъюнкция &(х n ), равная 1 при`х n = (1, 1, . 1)и 0 на всех остальных наборах,

2) обобщенная дизъюнкция Ú (х n ), равная 0 при `х n = (0, 0, . 0)и 1 на всех остальных наборах,

3) обобщенная функция Шеффера | (`х n ), равная 0 при `х n = (1, 1, . , 1) и 1 на всех остальных наборах,

4) обобщенная функция Вебба ¯ (`х n ), равная 1 при `х n =(0, 0, . , 0)и 0 на всех остальных наборах.

Принципиальная схема функционального элемента, реализующего обобщенную конъюнкцию &(х n ), может быть представлена (рис.2.1 а) в виде последовательного соединения входов 1. n, соответствующих переменным (х1. хn). Сигнал от входа В к выходу&схемы передается только при одновременной подаче дополнительных сигналов на все входы 1. ,n. В противном случае цепь разрывается. Схема обобщенной дизъюнкции Ú(`х n ), может быть представлена (рис.1.1 б) в виде параллельного соединения входов 1,. ,n. В ней для появления выходного сигнала достаточно его подачи хотя бы на один из входов.

Применяя дополнительно отрицание к входам схемы, аналогично можно представить обобщенные функции Вебба (Рис.1.2 а) и Шеффера (Рис 1.2 б).

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

Дата добавления: 2015-10-05 ; просмотров: 1498 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Определение. Функция f(x, x1, …, xn) называется логической (булевой), если ее аргументы x, x1, …, xn и значения функции могут принимать только два значения: логического 0 и логической 1.

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

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

1. Словесный. Взаимосвязь значений функции и ее аргументов описывается словесной формулировкой.

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

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

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

Логические функции одной переменной

Существует 4 функции одной переменной.

Таблица истинности для функций одной переменной

Аргумент х Функции
f f1 f2 f3

Функции одного аргумента имеют следующие аналитические записи и названия:

f2(х) = отрицание х, НЕ, инверсия, читается «не х»;

f3(х) = 1 — константа единицы.

Функции одной переменной f, f1, f3 не представляют интереса с точки зрения технической реализации. Практически применяется только функция
f2(х) = — инверсия.

Логические функции двух переменных

Существует 16 функций двух переменных (табл. 3.3).

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

Аргументы Функции
х1 х2 f f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15

Функции двух переменных имеют следующие записи и названия:

f81, x2) = Úх21¯х2 — стрелка Пирса, отрицание ИЛИ; ИЛИ-НЕ;

f101, x2)= —отрицание х2;

f121, x2) = отрицание х1;

f141, x2) = х1½х2 = — штрих Шеффера, отрицание И; И-НЕ;

Из функций двух переменных не имеют практического интереса f (константа 0), f3 (повторение x1), f5 (повторение х2), f15 (константа 1).

Приведем словесное описание некоторых функций.

Логическое сложение (дизъюнкция). Функция ИЛИ принимает единичное значение, когда хотя бы один из аргументов ИЛИ х1, ИЛИ х2 равен единице.

Логическое умножение (конъюнкция). Функция И принимает единичное значение, когда одновременно обе переменные И x1, И х2 равны единице.

Инверсия. Функция НЕ принимает значения, противоположные аргументу х.

Цифровую форму представления логической функции рассмотрим на примере функции f6, которая принимает единичные значения на наборах входных переменных (х1х2) в двоичном коде 01, 10, что соответствует десятичному эквиваленту 1; 2:

Функция f6 принимает нулевые значения на наборах входных переменных (х1х2) в двоичном коде 00,11. Это соответствует в десятичном коде 0; 3:

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

Ссылка на основную публикацию
Файловый менеджер для ubuntu server
Работа с файлами в операционной системе Ubuntu осуществляется через соответствующий менеджер. Все дистрибутивы, разработанные на ядре Linux, позволяют юзеру всячески...
Удалить одноклассники страницу с телефона айфон
Если вы хотите удалить свою страницу (профиль) в Одноклассниках, особенно если это требуется сделать со смартфона Android или iPhone —...
Удалить папку не удалось найти этот элемент
В этой инструкции подробно о том, как удалить файл или папку, если при попытке это сделать в Windows 10, 8...
Файлы dll чем открыть
Файлы формата DLL открываются специальными программами. Существует 2 типа форматов DLL, каждый из которых открывается разными программами. Чтобы открыть нужный...
Adblock detector