Размещено на http://www.allbest.ru/

Введение

Информация (данные, машинные команды и т. д.) в компьютере представлена в двоичной системе счисления, в которой используется две цифры - 0 и 1. Электрический сигнал, проходящий по электронным схемам и соединительным проводникам (шинам) компьютера, может принимать значения 1 (высокий уровень электрического напряжения) и 0 (низкий уровень электрического напряжения) и рассматривается как импульсный сигнал, который математически может быть описан в виде двоичной переменной, принимающей также значения 0 или 1. Для решения различных логических задач, например, связанных с анализом и синтезом цифровых схем и электронных блоков компьютера, широко используются логические функции и логические операции с двоичными переменными, которые называются также логическими переменными [1].

Логические переменные изучаются в специальном разделе математики, который носит название алгебры логики (высказываний), или булевой алгебры. Булева алгебра названа по имени английского математика Джорджа Буля (1815-1864), внесшего значительный вклад в разработку алгебры логики. Предметом изучения алгебры логики являются высказывания, при этом анализу подвергается истинность или ложность высказываний, а не их смысловое содержание. Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами: А, В, С, D,… и т. д. Составные высказывания на естественном языке образуются с помощью союзов. В алгебре логики эти союзы заменяются логическими операциями. В соответствии с алгеброй логики любое составное высказывание можно рассматривать как логическую функцию F(А, В, С, …), аргументами которой являются логические переменные А, В, С… (простые высказывания). Логические функции и логические переменные (аргументы) принимают только два значения: «истина», которая обозначается логической единицей - 1 и «ложь», обозначаемая логическим нулем - 0 [1].

1. Логические функции

1.1 Основные сведения

Логическая функция -- это функция, устанавливающая соответствие между одним или несколькими высказываниями, которые называются аргументами функции, и высказыванием, которое называется значением функции.

Алгебра логики (алгебра высказываний) -- раздел математической логики, в котором изучаются логические операции над высказываниями. Чаще всего предполагается, что высказывания могут быть только истинными или ложными [2].

Булева функция (или логическая функция, или функция алгебры логики) от n аргументов -- в дискретной математике -- отображение Bⁿ > B, где B = {0,1} -- булево множество. Элементы булева множества {1, 0} обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла [8].

Булевы переменные -- переменные, принимающие значения из булева множества.

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

Арность функции -- количество аргументов, или операндов. Неотрицательное целое число n называют арностью или местностью функции, в случае n = 0 булева функция превращается в булеву константу. Элементы декартова произведения (n-я прямая степень) Bⁿ называют булевыми векторами. Множество всех булевых функций от любого числа аргументов часто обозначается P₂, а от n аргументов -- P₂(n) [8].

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

Таблица истинности -- это таблица, описывающая логическую функцию [9].

1.2 Возникновение логики

Понятие логики как науки появилось ещё в XIX в., т.е. задолго до появления науки информатики и компьютеров. Элементы математической логики можно найти уже в работах древнегреческих философов. В XVII в. Г. В. Лейбниц высказал идею о том, что рассуждения могут быть сведены к механическому выполнению определенных действий по установленным правилам. Однако как самостоятельный раздел математики логика начала формироваться только с середины XIX в. [3].

Для того чтобы рассуждать, человеку необходим какой-либо язык. Не удивительно, что математическая логика начиналась с анализа того, как говорят и пишут люди на естественных языках. Этот анализ привёл к тому, что выяснилось существование формулировок, которые невозможно разделить на истинные и ложные, но, тем не менее, выглядят осмысленным образом. Это приводило к возникновению парадоксов, в том числе в одной из фундаментальных наук математики. Тогда было решено создать искусственные формальные языки, лишённого «вольностей» языка естественного [3].

1.3 Операции в алгебре логики

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказывания строятся над множеством {B, , &, ?, 0, 1}, где B -- непустое множество, над элементами которого определены три операции:

· отрицание,

· конъюнкция,

· дизъюнкция,

а также константы -- логический ноль 0 и логическая единица 1.

1) Логическая операция инверсия (отрицание). В естественных языках соответствует словам неверно, ложь или частице не, в языках программирования обозначается Not, в алгебре логики обозначается . Инверсия каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается. Математическая запись данной операции для логической переменной А будет иметь вид: F= [1].

2) Логическая операция конъюнкция (логическое умножение). В естественных языках соответствует союзу и, в языках программирования обозначается And, в алгебре логики обозначается &. Конъюнкция каждым простым высказываниям ставит в соответствие составное высказывание, являющееся только тогда истинным, когда являются истинными простые высказывания, образующие составное высказывание. Математическая запись данной операции для логических переменных A, B, С, будет иметь вид: F = A & B & C [1].

3) Логическая операция дизъюнкция (логическое сложение). В естественных языках соответствует союзу или, в языках программирования обозначается Or, в алгебре логики обозначается ?. Дизъюнкция каждым простым высказываниям ставит в соответствие составное высказывание, являющееся только тогда истинным, когда хотя бы одно из образующих его высказываний является истинным. Математическая запись данной операции для логических переменных A, В, С, … будет иметь вид: F = A?B?C [1].



1.4 Основные законы алгебры логики

В алгебре логики имеются законы, которые записываются в виде соотношений. Логические законы позволяют производить равносильные (эквивалентные) преобразования логических выражений. Преобразования называются равносильными, если истинные значения исходной и полученной после преобразования логической функции совпадают при любых значениях входящих в них логических переменных [1].

Для простоты записи приведем основные законы алгебры логики для двух логических переменных А и В. Эти законы распространяются и на другие логические переменные [1].

1. Закон противоречия: A&=0; B&=0.

2. Закон исключенного третьего: A?=1; B?=1.

3. Закон двойного отрицания: =A; =B.

4. Законы де Моргана: =&; =?.

1.5 Таблицы истинности

Соотношения между логическими переменными и логическими функциями в алгебре логики можно отобразить также с помощью соответствующих таблиц, которые носят название таблиц истинности. Таблицы истинности находят широкое применение, поскольку наглядно показывают, какие значения принимает логическая функция при всех сочетаниях значений ее логических переменных. Таблица истинности состоит из двух частей. Первая (левая) часть относится к логическим переменным и содержит полный перечень возможных комбинаций логических переменных А, В, С… и т. д. Вторая (правая) часть этой таблицы определяет выходные состояния как логическую функцию от комбинаций входных величин [1].

Например, для логической функции F=A?B?C (дизъюнкции) трех логических переменных А, В, и С таблица истинности будет иметь вид, показанный на рис. 1.1. Для записи значений логических переменных и логической функции данная таблица истинности содержит 8 строк и 4 столбца, т. е. число строк для записи значений аргументов и функции любой таблицы истинности будет равно 2ⁿ, где n - число аргументов логической функции, а число столбцов равно n + 1 [1].

Рис. 1.1 Таблица истинности для логической функции F=A?B?C [1]

Логические функции имеют соответствующие названия. Для двух двоичных переменных существует шестнадцать логических функций, названия которых приведены ниже. На рис. 1.2 представлена таблица, в которой приведены логические функции F₁, F₂, F₃, …, F₁₆ двух логических переменных A и В [1].

Функция F₁ = 0 и называется функцией константы нуля, или генератора нуля.

Рис. 1.2 Логические функции F₁, F₂, F₃,… F₁₆ двух аргументов А и В [1]

Функция

F₂ = A & B

называется функцией конъюнкции.

Функция

F₃ = A &

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

Функция

F₄ = А

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

Функция

F₅ = & B

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

Функция

F₆ = В

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

Функция

F₇ = & B ? A &

называется функцией исключающее «ИЛИ».

Функция

F₈ = A ? В

называется функцией дизъюнкции.

Функция

называется функцией Пирса.

Функция

называется функцией эквиваленции.

Функция

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

Функция

называется функцией импликации B A.

Функция

называется функцией отрицания (инверсии) по логической переменной А.

Функция

называется функцией импликации A B.

Функция

называется функцией Шеффера.

Функция

называется функцией генератора 1.

Среди перечисленных выше логических функций переменных можно выделить несколько логических функций, с помощью которых можно выразить другие логические функции. Операцию замены одной логической функции другой в алгебре логики называют операцией суперпозиции или методом суперпозиции. Например, функцию Шеффера можно выразить при помощи логических функций дизъюнкции и отрицания, используя закон де Моргана [1]:

.

Логические функции, с помощью которых можно выразить другие логические функции методом суперпозиции, называются базовыми логическими функциями. Такой набор базовых логических функций называется функционально полным набором логических функций. На практике наиболее широко в качестве такого набора используют три логических функции: конъюнкцию, дизъюнкцию и отрицание. Если логическая функция представлена с помощью базовых функций, то такая форма представления называется нормальной. В предыдущем примере логическая функция Шеффера, выраженная через базовые функции, представлена в нормальной форме [1].

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

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

· правильная, если каждая переменная входит в неё не более одного раза (включая отрицание);

· полная, если каждая переменная (или её отрицание) входит в неё ровно 1 раз;

· монотонная, если она не содержит отрицаний переменных.

Например: -- является ДНФ.

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

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции, отличной от тождественного нуля -- даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора построить конъюнкцию, где . Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации результатом является, что можно упростить до [2].

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

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

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

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:

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

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот [2].

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

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

Минимизация означает переход от СДНФ к ДНФ с минимумом слагаемых (избавиться от "совершенства"), при этом количество множителей в каждом слагаемом должно быть также минимальным, то есть максимально уменьшить количество переменных и операций в СДНФ [6].

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

· карта Карно (Вейча)

· Квайна

· Квайна- Мак-Класки

· Петрика

Отличие метода карт Карно от карт Вейча заключается в способе обозначения строк и столбцов карт. У карт Карно строки и столбцы обозначаются с помощью кода Грея. Однако, принципиальной разницы между ними нет.

Метод минимизационных карт Карно (или карт Вейча) хорошо работает при числе аргументов 3,4 и даже 5 и обеспечивает простоту получения результата. Этот метод основан на зрительном анализе таблиц (карт) и не может быть применен для обработки вычислительной техникой.

Карта Карно строится в соответствии с таблицей истинности логической функции. Столбцы и строки карты Карно обозначаются прямыми и инверсными переменными данной функции [6].

Рис. 1.3 Карта Карно для 2-х и для 3-х переменных [6]

Число клеток карты равно числу всех возможных комбинаций входных переменных, т.е. 2?, где n- число входных переменных. Это также значит, что число клеток карты равно максимальному числу минтерм СНДФ.

Каждая клетка карты соответствует логическому произведению (прямого или инверсного значения) переменных, на пересечении которых она находится, что соответствует минтерме СНДФ. В карту Карно заносятся соответствующие значения минтерм [6].

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

Клетки, находящиеся на границах одной строки или столбца, так же считаются соседними [6].

Рис. 1.4 Карта Карно строится на основании таблицы истинности [6]

Каждая клетка карты соответствует произведению переменных, на пересечении которых она находится.

Рис. 1.5 Принцип составления карты Карно [6]

Для минимизации функций используется закон «склеивания»:

ab + ab` = a

Если переменная (аргумент) изменяет свое значение, а функция при этом остается неизменной, то эту переменную можно исключить из выражения [6].

Правило минимизации.

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

Рис. 1.6 Пример составления карты Карно [6]

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

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

Рис. 1.7 Пример минимизации [6]

В данном примере, произведения, образующие общий зеленый квадрат 1, позволяют исключить из общего выражения две переменные: b и c. Эти переменные на протяжении всего квадрата изменяли свое значение. При этом количество минтерм также сократилось.

Соседними также являются произведения, образующие синий квадрат 2. Количество итоговых минтерн, подлежащих сложению равно количеству квадратов [6].

Рис. 1.8 Метод скручивания карты Карно [7]

Крайние квадраты карты являются соседними при ее скручивании. Это значит, что они тоже подлежат минимизации. На плоскости можно изобразить карту Карно для 4-х переменных. Для 5 и более переменных необходимы объемные фигуры [6].

1.9 Классификация булевых функций

· По количеству n входных операндов, от которых зависит значение на выходе функции, различают нульарные (n = 0), унарные (n = 1), бинарные (n = 2), тернарные (n = 3) булевы функции и функции от большего числа операндов [4].

· По количеству единиц и нулей в таблице истинности отличают узкий класс сбалансированных булевых функций (также называемых уравновешенными или равновероятноятными, поскольку при равновероятных случайных значениях на входе или при переборе всех комбинаций по таблице истинности вероятность получения на выходе значения 1 равна 1/2) от более широкого класса несбалансированных булевых функций (так же называемых неуравновешенными, поскольку вероятность получения на выходе значения 1 отлична от 1/2). Сбалансированные булевы функции в основном используются в криптографии [4].

· По зависимости значения функции от перестановки её входных битов различают симметричные булевы функции (значение которых зависит только от количества единиц на входе) и несимметричные булевы функции (значение которых так же зависит от перестановки её входных бит) [4].

· По значению функции на противоположных друг другу наборах значений аргументов отличают самодвойственные функции (значение которых инвертируется при инвертировании значения всех входов) от остальных булевых функций, не обладающих таким свойством. Нижняя часть таблицы истинности для самодвойственных функций является зеркальным отражением инвертированной верхней части (если расположить входные комбинации в таблице истинности в естественном порядке) [4].

· По алгебраической степени нелинейности отличают линейные булевы функции (АНФ которых сводится к линейной сумме по модулю 2 входных значений) и нелинейные булевы функции (АНФ которых содержит хотя бы одну нелинейную операцию конъюнкции входных значений). Примерами линейных функций являются: дизъюнкция («ИЛИ», OR), сложение по модулю 2 (исключающее «ИЛИ», XOR), а также все булевы функции, АНФ которых содержит лишь линейные операции сложения по модулю 2 без конъюнкций. Примерами нелинейных функций являются: конъюнкция («И», AND), штрих Шеффера («НЕ-И», NAND), стрелка Пирса («НЕ-ИЛИ», NOR), а также все булевы функции, АНФ которых содержит хотя бы одну нелинейную операцию конъюнкции [4].



Выводы

алгебра логика высказывание функция

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



2. Реализация логических функций

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

2.1 Логическая функция инвертирования

Простейшим логическим элементом является инвертор, который просто изменяет значение входного сигнала на прямо противоположное значение. В качестве логического инвертора можно использовать обычный транзисторный усилитель с транзистором, включенном по схеме с общим эмиттером или истоком. Схема, выполненная на биполярном n-p-n транзисторе, позволяющая реализовать функцию логического инвертирования приведена на рис.2.1 [5].

Рис. 2.1 Схема, позволяющая реализовать функцию логического инвертирования [5]

Схемы логических инверторов могут обладать различным временем распространения цифрового сигнала и могут работать на различные виды нагрузки. Они могут быть выполнены на одном или на нескольких транзисторах, но независимо от схемы и её параметров они осуществляют одну и ту же логическую функцию. Для того, чтобы особенности включения транзисторов не затеняли выполняемую логическую функцию, были введены специальные обозначения для цифровых микросхем -- условно-графические обозначения. Условно-графическое изображение логического инвертора приведено на рис.2.2 [5].

Рис. 2.2 Условно-графическое изображение логического инвертора [5]

2.2 Логическая функция "И" (конъюнкция)

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

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

Рис. 2.3 Принципиальная схема, реализующая логическую функцию "2И" [5]

Условно-графическое изображение электронной схемы, выполняющей логическую функцию "2И", на принципиальных схемах цифровых и вычислительных устройств приведено на рис. 2.4. Это изображение не зависит от конкретной принципиальной схемы устройства, реализующей функцию логического умножения.

Рис. 2.4 Условно-графическое изображение схемы, выполняющей логическую функцию "2И" [5]

2.3 Логический элемент "ИЛИ"

Как и в случае, рассмотренном для схемы логического умножения, воспользуемся для реализации схемы "2ИЛИ" ключами. На этот раз соединим ключи параллельно. Схема приведена на рис. 2.5. Как видно из приведённой схемы, уровень логической единицы появится на её выходе, как только будет замкнут любой из ключей [5].

Рис. 2.5 Принципиальная схема, реализующая логическую функцию "2ИЛИ" [5]

Так как функция логического суммирования может быть реализована различными принципиальными схемами, то для обозначения этой функции на принципиальных схемах используется специальный символ "1", как это приведено на рис. 2. 6 [5].

Рис. 2.6 Условно-графическое изображение логического элемента, выполняющего функцию "2ИЛИ" [5]



Список использованных источников

1. Nnre.ru библиотека [Электронный ресурс] Электрон.дан. Режим доступа: http://www.nnre.ru/kompyutery_i_internet/informatika_apparatnye_sredstva_personalnogo_kompyutera/p5.php#metkadoc4, свободный -- загл. с экрана.

2. Википедия [Электронный ресурс] Электрон.дан. Режим доступа: http://ru.wikipedia.org/wiki/%C1%F3%EB%E5%E2%E0_%F4%F3%ED%EA%F6%E8%FF#CITEREF.D0.98.D0.B3.D0.BE.D1.88.D0.B8.D0.BD2008, свободный -- загл. с экрана.

3. Алгебра логики [Электронный ресурс] Электрон.дан. Режим доступа: http://otherreferats.allbest.ru/mathematics/00000674_0.html, свободный -- загл. с экрана.

4. Дискретная математика [Электронный ресурс] Электрон.дан. Режим доступа: http://desolt.ru/glava-3.-bulevyi-funkczii.html, свободный -- загл. с экрана.

5. Применение цифровой техники в аппаратуре связи [Электронный ресурс] Электрон.дан. Режим доступа: http://digteh.ru/CVT/LOGIC/, свободный -- загл. с экрана.

6. Минимизация логических функций [Электронный ресурс] Электрон.дан. Режим доступа: http://www.e-ope.ee/_download/euni_repository/file/2156/LP2_LoogikaU.zip/LP2_Loogika/__4.html , свободный -- загл. с экрана.

7. Творческий проект по предмету "Информационные и электронные технологии" [Электронный ресурс] Электрон.дан. Режим доступа: http://exponenta.ru/educat/systemat/1006/3_projects/tebiakina.asp, свободный -- загл. с экрана.

8. Игошин В. И. Математическая логика и теория алгоритмов. 2-е изд., стереотип. М.: Издательский центр «Академия», 2008. 448 с.

9. Википедия [Электронный ресурс] Электрон.дан. Режим доступа: http://ru.wikipedia.org/wiki/Таблица_истинности, свободный -- загл. с экрана.

Размещено на Allbest.ru

...