Конспект лекций Губарь (Конспект лекций "Начальный курс информатики" А.М.Губарь), страница 12

Вданном случае сначала выполняется отрицание, затем – дизъюнкция и,наконец, – импликация.Таким образом, данное высказывание ложно в единственном случае:когда А и С истинны, а В ложно, и истинно при всех других комбинациях А,В, и С, то есть можем записать f (1,0,1) = 0.3.4. Логические функцииПоследняязаписьоченьнапоминаетпредставлениеобычныхалгебраических функций, но есть и существенные отличия. Например, ввыражении f(x) = 3x переменная x является аргументом, то есть независимойпеременной, которая в данном случае может принимать любые значения, азатем по формуле вычисляются соответствующие им значения функции.В алгебре логики логическая переменная может принимать только одноиз двух возможных значений – 0 (заменяет словесное обозначение "лжи") или1 (синоним "истины").

Логическая функция, аналогом которой можно считатьсоставное высказывание, также принимает только значения 0 или 1, причёмпоследние "вычисляются" в результате выполнения логических операций,входящих в соответствующую логическую формулу, на основе таблицистинности. Логические функции также называют булевыми функциями.Итак, в формулах алгебры логики переменные являются логическими,булевыми или двоичными. Каждая формула задает логическую функцию отлогических переменных, причем аргументы и функции алгебры логики такжемогут принимать только значения 1 или 0.

Любую такую булеву функциюfi(x1, …, xn) можно задать своей таблицей истинности, в левой части которойзанесены все наборы значений ее аргументов, а правая часть представляетсобой результирующий столбец значений функции, соответствующих этимнаборам, и число строк такой таблицы равно 2 n. Для этого на каждом набореаргументов последовательно выполняются действия, содержащиеся влогической формуле, с учетом «старшинства» операций, как это былопроделано в рассмотренном примере. С помощью указанных таблиц можнооценивать(определятьистинностьилиложность)любыесложныевысказывания, другими словами, от функции, заданной в виде формулы,всегда можно перейти к ее табличному заданию.

Решение обратной задачи –получение формулы логической функции по ее таблице истинности – мысейчас и реализуем.3.5. Получение логической формулы по таблице истинностиИтак, задать булеву функцию fi(x1, …, xn) от логических переменныхможно двумя способами: во-первых, можно записать формулу длявычисления значений логической функции, во-вторых, можно составитьтаблицу истинности, в которой содержатся все возможные комбинацииаргументов, то есть наборы нулей и единиц, и соответствующие им значенияфункции (также нули и единицы).

Оба эти способа эквивалентны. Удобствоформулы – в её компактности, преимущество таблицы истинностизаключается в ее наглядности.Мы рассмотрели, как составить таблицу истинности, имея логическуюформулу булевой функции, при оценке сложных высказываний. Теперьрешим обратную задачу: как получить формулу функции по её таблице. Дляеё решения применим такой алгоритм: для каждого набора аргументов, накотором функция равна 1, записываем логическое произведение переменных,причём, если какой-то аргумент в этом наборе равен 0, берется егоотрицание, затем все полученные произведения логически складываются.Пусть задана следующая таблица истинности (таблица 3.7), надоопределить, какой логической функции она соответствует.Т а б л и ц а 3.7Таблица истинности логической функции Fx1x2x3F00000010010101111000101111001110Эта таблица по внешнему виду несколько отличается от предыдущих: вней исходные данные развернуты по горизонтали, а переменные обозначеныкак xi.

Итак, имеем:f2(0,1,0) = f3(0,1,1) = f5(1,0,1) = 1.На основе заданного алгоритма можем записать:F = х1 ∙ х2 ∙ х3   х1 ∙ х2 ∙ x3  x1∙ x2 ∙ x3.В итоге мы получили выражение для логической функции, но его надопостараться упростить. Дело в том, что чем короче формула, тем меньшелогических элементов потребуется для её технической реализации приконструированииразличныхкомпонентовкомпьютера.Влогическихвыражениях, как и в алгебраических, можно приводить подобные члены,выносить общий множитель за скобки и т.п. Кроме того, полезно помнить,что в алгебре логики х  х = 1, так как 0  1 = 1  0 = 1.

С учётом этогопреобразуем полученное выражение, сгруппировав первые два слагаемых ивынеся общий множитель за скобки. Получим:F = х1 ∙ х2 ∙ ( х3  х3)  x1∙ x2 ∙ x3 = х1 ∙ х2  x1∙ x2 ∙ x3.Таким образом, на основе одной таблицы истинности можно получитьнесколько логических формул, но надо выбирать из них самую "короткую".В нашем случае имеемF = fi(x1,x2,x3) = x1 ∙ x2  x1∙ x2 ∙ x3.Полученнаяформуланазываетсясовершеннойдизъюнктивнойнормальной формой записи функции алгебры логики, задача ее минимизациирешаетсянаосновеэквивалентныхпреобразованийспомощьюсоответствующих аксиом, законов и свойств, к изучению которых мы иприступим.3.6.

Минимизация функций алгебры логикиРешение задачи минимизации логической функции достигается, какбыло отмечено, путем эквивалентных преобразований с использованиемследующих аксиом, законов и свойств алгебры логики:1. Ассоциативность (сочетательный закон):х1  (х2  х3) = (х1  х2)  х3 = х1  х2  х3; х1·(х2·х3) = (х1·х2)·х3 = х1·х2·х3.2. Дистрибутивность (распределительный закон):х1·(х2  х3) = х1·х2  х1·х3; х1  х2·х3 = (х1  х2)·(х1  х3).3. Коммутативность (переместительный закон):х1·х2 = х2·х1; х1  х2 = х2  х1.4.

Идемпотентность (отсутствие степеней и коэффициентов):х·х =х; х  x = х.5. Закон двойного отрицания: ┐┐х = х.6. Свойства констант 0 и 1:х  0 = х; х·0 = 0; x  1 = 1; х·1 = х,  0 = 1;  1 = 0.7. Законы де Моргана: ┐(х1·х2) = х1  х2; ┐(х1  х2) = х1 · х2.8. Следствия из 5 и 7: х1·х2 = ┐( х1  х2); х1  х2 = ┐( х1 · х2).9. Закон противоречия: х  х = 0.10. Закон исключенного третьего: х  х = 1.11. Законы поглощения: x1  x1·x2 = x1; x1·(x1  x2) = x1.12.

Закон склеивания: x1·x2  x1 · x2 = x1.Некоторогопояснениятребуетдистрибутивностьдизъюнкцииотносительно конъюнкции. Действительно:(х1  х2)·(х1  х3) = х1·х1  х1·х2  х1·х3  х2·х3 = x1  x1·x2  x1·x3  x2·x3 = =x1·(1  x2  x3)  x2·x3 = x1  x2·x3.Следует иметь в виду, что процесс минимизации логической функцииможет привести к неоднозначному результату. Рассмотрим такой пример:F = x1∙ x2 ∙ х3  x1∙ x2 ∙ x3  x1∙ x2 ∙ x3  х1 ∙ х2 ∙ х3  х1 ∙ х2 ∙ х3  х1 ∙х2 ∙ x3 = x1∙ x2 ∙( х3 x3)  x2 ∙ x3∙( x1 х1)  х1 ∙ х3∙( х2 х2) = x1∙ x2 x2∙ x3 х1 ∙ х3.Мы сгруппировали первое слагаемое со вторым, третье – с пятым, четвертое– с шестым, вынесли общие множители за скобку и воспользовались закономисключенного третьего, а также свойством константы 1.

Однако можносгруппировать слагаемые по-другому: первое – с третьим, второе – счетвертым, пятое – с шестым. Тогда после аналогичных преобразований мыполучим:F = x1∙ x2 ∙ х3  x1∙ x2 ∙ x3  x1∙ x2 ∙ x3  х1 ∙ х2 ∙ х3  х1 ∙ х2 ∙ х3  х1 ∙х2 ∙ x3 = x1∙ x3 ∙( х2 x2)  x2∙ x3 ∙( x1 х1)  х1∙х2∙( х3 х3) =  x1∙ x3   x2∙x3 х1 ∙ х2.Итак, мы получили две эквивалентные минимальные дизъюнктивныеформы, которые равноценны с точки зрения их последующей техническойреализации.3.7. Логические элементы, реализующие булевы функцииПреобразованиеинформациивкомпьютереосуществляетсяэлектронными устройствами двух классов: комбинационными схемами ицифровыми автоматами.В комбинационных схемах совокупность выходных сигналов y в каждыйдискретный момент времени ti однозначно определяется комбинациейвходных сигналов x, поступивших на входы схемы в этот же момент времени.Соответствие между входом и выходом комбинационной схемы может бытьзадано табличным способом, а также в аналитической форме:y1 = f1 ( x1, x2, …, xn),y2 = f2 ( x1, x2, …, xn),…ym = fm ( x1, x2, …, xn).Поскольку все хi и уi принимают только два значения: 0 или 1, функции fiявляются булевыми.Цифровой автомат, в отличие от комбинационных схем, обязательносодержит память.

Он имеет конечное число различных внутреннихсостояний, причем может переходить из одного из них в другое подвоздействием входного слова с получением соответствующих выходных слов.Переходотзаданныхусловийработыцифровогоавтоматакегофункциональной схеме осуществляется с помощью аппарата алгебры логики.Система элементарных логических функций f1, f2, …, fm, то есть таких,которые образуются путем использования однородных связей междудвоичными переменными, называется функционально полной или базисом,если любую функцию алгебры логики можно записать в виде формулы илиуравнения с помощью суперпозиции (совмещения) элементарных функций.Точно так же набор логических элементов, реализующих указанные функции,обладает функциональной полнотой, если при помощи конечного числа этихэлементов можно построить схему с любым законом функционирования.

Валгебре логики доказано, что базисом является набор функций И, ИЛИ, НЕ;функционально полными системами являются также наборы, состоящие изодной функции – стрелка Пирса (ИЛИ-НЕ) или штрих Шеффера (И-НЕ).Нафункциональныхсхемахлогическиеэлементыкомпьютера,реализующие указанные функции, обозначаются так, как показано на рисунке3.1:Рис.

3.1. Условные обозначения логических элементовна функциональных схемахРассмотренные логические функции являются элементарными, так какобразуются путем использования однородных связей между двоичнымипеременными. Из них можно строить и более сложные функции (на рисунке3.2 приведены два варианта представления одной и той же схемы), например:Или более компактное представление:Рис. 3.2.

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