Алгебра логики как математическая основа преобразования логических функций. Основные свойства конъюнкции, дизъюнкции и отрицания. Методы составления таблицы истинности для импликации и сложения по модулю 2 совершенной дизъюнктивной нормальной формы.
Логической (булевой) функцией (или просто функцией) n переменных y = f(x1, x2, …, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1. Из определения логической функции следует, что функция n переменных - это отображение En в Е, которое можно задать непосредственно таблицей, называемой таблицей истинности данной функции. Из перечисленных функций особую роль играют три функции, а именно конъюнкция, дизъюнкция и отрицание, поэтому рассмотрим более подробно их свойства. Особая роль двух функций (из этих трех) определяется тем обстоятельством, что определение этих функций легко может быть перенесено на любое число переменных: Конъюнкцией n переменных f (x1, x2, …, xn) = x1 x2…xn называется функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0). По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х1, х2, …, хп), для которых f(x1, x2,…, xn) = 0, причем если хі = 1, то в этой дизъюнкции берем xi , если же хі = 0, то берем хі.В ходе выполнения курсовой работы, можно сделать вывод, что достаточно простые логические функции в автоматике решают с помощью специальных устройств - логических элементов. Таким образом, логические элементы в булевой алгебре могут принимать только два значения: «истинно» или «ложно».
Введение
При решении задач автоматизации необходимо решение логических функций разной сложности, т.е. выполнение определенного действия при достижении ряда необходимых условий. Достаточно простые логические функции в автоматике решают с помощью специальных устройств - логических элементов.
Математической основой преобразования логических функций является алгебра логики. Алгебра логики - это раздел математики, оперирующий с независимыми переменными, которые могут принимать только два значения: «истинно» или «ложно». В цифровой электронике им присвоены значения «1», т.е. полный сигнал на выходе и «0», т.е. полное отсутствие сигнала на выходе.
1. Основные логические функции
Обозначим через E = {0, 1} - множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной математике. Часто они интерпретируются как «ложь» (л ={0}) и как «истина» (и ={1}). Декартово произведение E* Е* Е* …* E=En является множеством упорядоченных наборов, состоящих из n чисел (нулей и единиц). Как известно, En содержит 2n элементов (упорядоченных наборов).
Само множество En можно естественным образом упорядочить, для чего достаточно считать каждый набор двоичным разложением целого числа k (0?k? 2n -1), записанного с помощью n знаков. Упорядочение наборов проводится по числу k . Например, при n = 3 множество Е3 может быть упорядочено следующим образом (рис. 1).
Рис. 1. Упорядочение «скользящая единица»
Этот естественный порядок элементов En является самым распространенным, но, иногда удобен другой способ упорядочения.
Логической (булевой) функцией (или просто функцией) n переменных y = f(x1, x2, …, xn) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1. Переменные, которые могут принимать только два значения 0 и 1 называются логическими переменными (или просто переменными). Заметим, что логическая переменная х может подразумевать под числом 0 некоторое высказывание, которое ложно, и под числом 1 высказывание, которое истинно.
Логическая функция может быть задана словесно, алгебраическим выражением или таблицей, которая называется таблицей соответствия или истинности. Из определения логической функции следует, что функция n переменных - это отображение En в Е, которое можно задать непосредственно таблицей, называемой таблицей истинности данной функции. Например, функция трех переменных f(x,y,z) может определяться следующей таблицей истинности.
Таблица 1
Это означает, что f(0,0,0) = 1, f(0,0,1) = 0, f(0,1,0) = 1 и т. д.
Две функции равны, если совпадают их таблицы истинности (на объединенном наборе переменных).
При таком задании наборы En всегда упорядочены естественным образом, это позволяет определять функцию только последним столбцом (который иногда для экономии места записывается в строчку). Например, в нашем примере функцию 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
Из перечисленных функций особую роль играют три функции, а именно конъюнкция, дизъюнкция и отрицание, поэтому рассмотрим более подробно их свойства.
В алгебраических выражениях конъюнкция обозначается знаком ? или &, дизъюнкция - знаком ?, а отрицание - чертой над обозначением переменной или знаком ¬.
2. Свойства конъюнкции, дизъюнкции и отрицания
Особая роль двух функций (из этих трех) определяется тем обстоятельством, что определение этих функций легко может быть перенесено на любое число переменных: Конъюнкцией 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 может выступать любая логическая функция. Все свойства легко могут быть доказаны из приведенных выше определений этих функций.
2. Ассоциативность конъюнкции и дизъюнкции: x(yz) = (xy)z; x? (y? z) = (x ?y)? z.
Это свойство означает, что в конъюнкции или дизъюнкции нескольких переменных можно как угодно расставлять скобки (а значит, можно вообще их не ставить).
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) является СКНФ.
3. Представление логических функций в виде СДНФ (СКНФ)
Если булева функция не равна тождественному нулю, то ее можно представить в виде СДНФ по ее таблице истинности следующим образом: берем только те наборы переменных (х1, х2, …,xn), для которых f(х1, х2, …,xn)=1, и составляем простую конъюнкцию для этого набора так: если хі = 0, то берем в этой конъюнкции xi, если хі = 1, то берем хі. Составляя дизъюнкцию этих простых конъюнкций, придем к СДНФ. Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание. По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х1, х2, …, хп), для которых f(x1, x2,…, xn) = 0, причем если хі = 1, то в этой дизъюнкции берем xi , если же хі = 0, то берем хі.
Пример 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
В совершенной дизъюнктивной нормальной форме заданная функция записывается в виде: у(а,b,c) = а ?в ?с ? а ? в ?с ? а ?в ?с ? а ?в ?с , т.е. функция записана для тех строк, где она обращается в 1.
В совершенной конъюнктивной нормальной форме заданная функция записывается в виде: у(а,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 применяют карты Карно.
4. Минимизация логических функций с помощью алгебраических преобразований
Рассмотрим пример минимизации логической функции. Упростим полученную в примере 2 СНДФ функции y, добавив в уравнение член а в с дважды (это допустимо, т.к. а ? а ? а = а): в с (а а) а с (в в) а в (с с) а в а с в с у а в с а в с а в с а в с а в с а в с
= ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ?
= ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =
Для упрощения более сложных функций приходится применять основные законы алгебры логики, наиболее употребительны законы отрицания и правило де Моргана, например: y =(а?в?с)?а?с?а?в?(а?в)=(а?в?с)?а?с?а?в?(а?в).
Первый и последний член преобразованы на основании закона отрицания.
Далее сгруппируем члены уравнения. у =(а?в?с?а?в)?(а?а)?с?в =а?в?(с?1)?а?с?в =а?в?а?с?в, т.к. с ? 1 = 1 ; а ? а = а Можно еще упростить, добавив а ? в (на основании аксиомы а ? а? а = а), и снова сгруппировав члены уравнения:
у = (а ? в ? в)? (а ? в ? а)? с = в ? (а ?1)? а ? (в ?1)? с = а ? а ? в ? с , (на основании закона поглощения), таким образом, мы имеем: у = (а ? в ? с)? а ? с ? а ? в ? (а ? в)= а ? а ? в ? с
5. Минимизация логических функций с помощью карт Карно
При большом числе переменных использование алгебраических преобразований резко усложняется, поэтому применяют карты Карно.
Карно - это представление таблицы истинности в виде прямоугольной таблицы с соответствующим числом клеток, каждая из которых отвечает определенной конъюнкции (произведению переменных). Переменные следуют так, чтобы в соседних клетках отличалась только одна из них, т.е. вместо чередования 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, каждому из них соответствует один член искомого уравнения. Для вертикального прямоугольника можно записать: а ? в ? с ? а ? в ? с = а ? в ? (с ? с) = а ? в .
Для двух оставшихся получаем в ? с и а ? с ; т.е. ту переменную, которая повторяется дважды - один раз «0», другой «1» - исключаем, а ту, которая не меняется, оставляем. Сокращенная ДНФ функции: у =а?в?а?с?в?с.
Заметим, что если для функции п переменных, заданных своей таблицей истинности, все возможные наборы переменных можно представить как вершины n-мерного куба со стороной равной 1 (всего вершин будет 2n) в «уравнения» этих прямых или гиперплоскостей, проведенные через те вершины, на которых значение функции равно 1. Карты Карно позволяют эти геометрические идеи использовать при п = 3, 4, 5, для функций, заданных своей таблицей истинности. При больших п карты Карно практически не используются. Надо учесть, что в карте Карно можно объединить клетки в крайних строках (таблица 8), рассматривая карту как цилиндр, и даже в углах, рассматривая карту как шар (таблица 9).
Таблица 8
Таблица 9
6. Реализация функций алгебры логики схемами
Рассмотрим построение электрических схем на логических элементах, реализующих простейшие логические функции (рис. 2).
Словесное определение функциям можно дать следующее: 1) Элемент И - на выходе появится «1», если на входе а И выходе в будет «1», в остальных случаях на входе «0», т.е. функция равна 0.
2) Элемент ИЛИ - на выходе появится «1», если ИЛИ на входе а, ИЛИ на входе в будет «1».
3) Элемент НЕ - состояние выхода всегда будет противоположно (инверсно) состоянию входа, т.е. на входе НЕ то, что на входе.
Рис. 2. Изображения логических элементов и таблицы истинности: а - конъюнкция (элемент И), б - дизъюнкция (элемент ИЛИ), в - отрицание (элемент НЕ)
С помощью этих схем можно реализовать любую логическую функцию, описывающую работу устройств компьютера. Обычно у схем бывает от двух до восьми входов и один или два выхода. Чтобы представить два логических состояния «1» и «0» в схемах, соответствующие им входные и выходные сигналы имеют один из двух установленных уровней напряжения, например, 5 вольт и 0 вольт. Высокий уровень обычно соответствует значению «истина» («1»), а низкий - значению «ложь» («0»).
Пример 3. Составить электрическую схему, реализующую функцию мажоритарной системы подсчета голосов, т.е. системы, дающей сигнал «1» на выходе, если более половины сигналов на входе «1» (пример 2).
Схема, соответствующая СДНФ у = а ? в ? с ? а ? в ? с ? а ? в ? с ? а ? в ? с , представлена на рисунке 3, а.
После минимизации функции схема, соответствующая сокращенной ДНФ, представлена на рисунке 3, б.
Таким образом, если исходное выражение требовало для реализации 8 элементов (четыре элемента «И», три элемента «НЕ» и один элемент «ИЛИ») при общем числе входов 19, то упрощенное выражение требует три элемента «И» и один элемент «ИЛИ» при общем числе входов 9. Сложность устройства уменьшена вдвое, если судить по числу входов 15
Рис. 3. Электрические схемы, соответствующие исходной СДНФ (а) и сокращенной ДНФ (б) заданной логической функции
Вывод
В ходе выполнения курсовой работы, можно сделать вывод, что достаточно простые логические функции в автоматике решают с помощью специальных устройств - логических элементов. Таким образом, логические элементы в булевой алгебре могут принимать только два значения: «истинно» или «ложно». В цифровой электронике им присвоены значения «1», т.е. полный сигнал на выходе и «0», т.е. полное отсутствие сигнала на выходе. Следовательно, мы приходим к выводу, что с помощью простой арифметики и логики можно добиться необходимого результата. Упрощения функций можно добиться с помощью математики или же чаще всего используется карта Карно. Подводя итоги анализа, следует отметить, что с упрощенной функцией можно облегчить схему устройства. Из всего сказанного следует вывод, что в современной электронике используются логические элементы. логический конъюнкция импликация дизъюнктивный
Список литературы
1. Новиков Ю.В., Основы цифровой схемотехники. Базовые элементы и схемы. Методы проектирования. - М.: Мир, 2001. - 379с.
