Курс: Элементы компьютерной математики компьютерной математики Лектор – Склярова Елена Александровна

Тема: Элементы компьютерной математики (ЭКМ) II. Элементы математической логики 1.Общие понятия 2.Способы создания логических функций 3.Законы алгебры логики 4.Операции над логическими функциями 5.Пять замечательных классов логических функций Лекция 5

« Всё ритм и бег. Бесцельное стремленье! Но страшен миг, когда стремленья нет. И.А.Бунин. «Ритм»

Общие понятия Математическая логика - одна из областей общей логики, развиваемая применительно к потребностям математики (и вычислительной техники). В ее составе - логика высказываний (исчисление высказываний; алгебра логики; алгебра Буля - булева алгебра) и логика предикатов (исчисление предикатов). Можно выделить и третий раздел - метаматематику, связанный с изучением аксиоматического построения наук, в частности той же математики.

Общие понятия Высказывание - любое утверждение (суждение), о котором можно сказать, истинно оно или ложно. Пример 1. (А) В прямоугольном треугольнике Пример 2. (В) Сегодня - 1 апреля 2001 года. Пример 3. (С)Ползучий страх к развалинам приник. И чайки кружатся, край моря очертив. И ветер повторяет чайки крик, Дождю-мечтателю дав утренний мотив.

Общие понятия Высказывания могут быть: - истинными или - ложными. Каждое высказывание характеризуется значением его истинности. Это двоичная величина, принимающая значения 0 (false), если высказывание ложно, и 1 (true) - в противном случае. Например, А = 0, В = 0 или 1, С = 0 или 1 и т. д.

Общие понятия Высказывания могут быть различные (А В) или эквивалентные (А = В). Некоторые высказывания оказываются сложными. Их можно расчленить на несколько простых (Пример 3). Таким образом, все сводится к двоичным величинам и двоичным функциям. Эти математические функции принимают только целочисленные значения, а именно 0 или 1. Исходя из области приложения будем называть такие функции логическими.

Общие понятия Другие названия: - переключательные функции (используются в «переключательных» схемах устройств вычислительной техники, систем управления и т.п.); - функции алгебры логики; - булевы функции.

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

Общие понятия Фактически в схеме проектирования (изучения - исследования, решения некоторой проблемы) присутствует обратная связь и реализуется метод последовательных приближений (итераций, «проб и ошибок»). Т.е. решается оптимизационная задача: при заданных требованиях (ограничениях) и критериях отыскивается экстремум целевой функции. Наша оптимизация будет связана с минимизацией логических функций, вообще - логических выражений (п. 8).

Общие понятия В отличие от логических функций (сложных высказываний) предикаты (praedico лат., «предсказание», «извещение») это функции, принимающие такие же значения - 0 (false) и 1 (true), но имеющие аргументы любого вида. Аргументы логических функций (ЛФ) - двоичные величины.

Способы задания логических функций Как и любые математические функции. ЛФ могут быть заданы: - аналитически (формулы с использованием специальных символов); - таблично; - графически (геометрически; используется эта форма редко - обычно для количества аргументов не более 3).

Способы задания логических функций Пример 1. Табличное задание ЛФ двух аргументов. Поскольку каждый аргумент принимает одно из двух значений, область определения любой ЛФ оказывается конечной. В примере эта область составлена четырьмя наборами двух элементов: (0, 0), (0, 1), (1, 0), (1, 1). Таким образом, набор аргументов ЛФ - это упорядоченная совокупность их значений. Количество наборов ЛФ n аргументов равно 2 n : Доказательство этого утверждения можно провести двумя способами (методами). х1х1 х2х2 f(x 1, x 2 )

Способы задания логических функций Метод полной математической индукции. Суть этого метода в двух этапах. На первом этапе строится так называемое основание индукции. Здесь фактически проводится проверка доказываемого утверждения для одного или нескольких значений параметра индукции. Обычно это i = 1. На втором этапе осуществляется переход i i + 1. Доказательство считается состоявшимся, если доказываемое утверждение остается истинным, т.е. изменяется только форма его - место i занимает i + 1.

Способы задания логических функций В нашем случае параметр индукции – n, это количество аргументов логической функции. При n = 1 получаем с очевидностью Эти два набора вырожденные: (0), (1).

Способы задания логических функций Теперь пусть формула верна для значения параметра индукции n. Добавляем еще один аргумент х n+1. Его значение 0 или 1 включаем в уже имеющиеся наборы аргументов. При этом Q нб (n) получают дополнительное значение 0 и столько же - 1. В результате Формула доказана.

Способы задания логических функций Второй способ связан с использованием двоичной системы счисления. Суть его в том, что каждому набору n аргументов можно поставить в соответствие n- разрядное двоичное число. Таким образом, речь идет о количестве различных двоичных чисел, имеющих n разрядов. Кстати, обычно наборы располагаются в порядке возрастания этих чисел (таб.1). Набор 0…0 называется нулевым, а 1…1 - единичным.таб.1

Способы задания логических функций Для ускорения расчетов наибольшее двоичное число увеличивают еще на 1: (n нулей) Значение результата, очевидно, составляет 2 n. Наибольшее число равно (2 n - 1). Учитывая еще и 0, получаем общее количество таких двоичных чисел 2 n, и формула доказана.

Способы задания логических функций Аналогично можно решить вопрос о количестве различных логических функций n аргументов. Здесь каждой ЛФ сопоставляется тоже двоичное число, но уже с 2 n разрядами. Оно ориентировано по вертикали (например, в таб. 4 для f 10 это число = 10. Тогда, очевидно,

Способы задания логических функций Количество ЛФ растет с увеличением n очень быстро (таб.2). Таблица 2 Аргументы и функции nQ нб (n)Q ЛФ (n) ~4,3*10 9 ………

Способы задания логических функций В обозначении ЛФ можно использовать значение «вертикального» двоичного числа в качестве индекса (табл. 3, 4). Конечно, важно еще и значение n: и т.д. Таблица 3 Логические функции одного аргумента хf0f0 f1f1 f2f2 f3f

Способы задания логических функций f 0 (x) - константа нуль. f 1 (x) - тривиальная функция, это просто переменная х. f 2 (x) = = x - инверсия (отрицание) х. Здесь происходит замена: 0 1, 1 0. f 3 (x) =1 - константа единица. Очевидно, функции вида f 0 … f 3 следует ожидать при любом количестве аргументов.

Способы задания логических функций Таблица 4 Логические функции двух аргументов x1x1 x2x2 f0f0 f1f1 f2f2 f3f3 f4f4 f5f5 f6f6 f7f7 f8f8 f9f9 f 10 f 11 f 12 f 13 f 14 f

Способы задания логических функций Характеризовать функции двух аргументов можно в порядке возрастания индекса (f 0, …, f 15 ) или поддерживая сначала аналогию с функциями одного аргумента. Выбираем второе. f 0 (x 1, x 2 ) = 0 - константа нуль. f 15 (x 1, x 2 ) = 1 - константа единица.

Способы задания логических функций Кстати, легко заметить, табл. 4. «инверсно» симметрична относительно вертикали, разделяющей f 7 и f 8. Т.е. справедливотабл. 4. Аналогия с ЛФ одного аргумента исчерпана. Осталось еще 10 функций.

Способы задания логических функций - конъюнкция. Другие названия конъюнкции: «функция И», «функция совпадения», «логическое умножение». Последнее оправдано тем, что фактически значения f 1 доставляют просто-напросто результат двоичного одноразрядного умножения. Конъюнкция может быть определена совершенно аналогично для любого количества аргументов (n 2): единичное значение ее - только на единичном наборе. - функция «штрих Шеффера». Это в своем роде замечательная функция.

Способы задания логических функций - дизъюнкция (функция ИЛИ, функция разделения, логическое сложение). Для n > 2 дизъюнкция определяется аналогично: она имеет единственное нулевое значение - на нулевом наборе аргументов. Различают строгую и нестрогую дизъюнкцию, или исключительное ИЛИ («ИЛИ-ИЛИ») и неисключительное ИЛИ. f 7 – это нестрогая дизъюнкция (неисключительное ИЛИ).

Способы задания логических функций Для строгой дизъюнкции в обычной логике используется символ. - функция Вебба (о), или «Стрелка Пирса» (). Это тоже, как и штрих Шеффера, замечательная функция.

Способы задания логических функций - сложение по модулю 2. Действительно, значения f 6 совпадают со значениями младшего разряда суммы одноразрядных двоичных чисел. Другое название этой функции - неравнозначность, исключительное ИЛИ (ХОR - мнемоника соответствующей машинной команды). Т.е. это и есть строгая дизъюнкция ( ). Вообще-то при n > 2 функции «сложение по модулю 2» и «неравнозначность» (строгая дизъюнкция) расходятся, если для последней считать единичными значениями только соответствующие наборам аргументов с единственной единицей (00 …01, 00 …010, …).

Способы задания логических функций -эквивалентность (равнозначность). - прямая импликация. В обычной логике - это очень важная функция. Она отражает причинно- следственную связь («если …, то…»), хотя и не строгую. Говорят «х 1 имплицирует (влечет) х 2 ».

Способы задания логических функций В качестве примера такой нежесткой причинно- следственной связи может служить настольная лампа с кнопочным включателем-выключателем (табл. 5). Таблица 5 Здесь х 1 - «Кнопка нажата», х 2 - «Лампа горит», f(х 1, х 2 ) - «Оценка ситуации» (0 - «ложно», 1 - «истинно»). х1х1 х2х2 f(x 1, x 2 ) 0: Кнопка не нажата0: Лампа не горитИстинно (возможно) 0: Кнопка не нажата1: Лампа горитИстинно (возможно) 1: Кнопка нажата0: Лампа не горитЛожно 1: Кнопка нажата1: Лампа горитИстинно

Способы задания логических функций Нежесткость связи в табл. 5. отражена в первых двух строках (кнопка могла быть нажата раньше). - инверсия прямой импликации. - обратная импликация. - инверсия обратной импликации.

Законы алгебры логики Основные законы алгебры логики имеют аналоги в обычной алгебре. Для конъюнкции и дизъюнкции справедлив переместительный закон. Эти функции обладают свойством коммутативности. (ab=ba), (a+b=b+a). Количество аргументов конъюнкции и дизъюнкции может быть любым. Этот и последующий законы доказываются путем перебора всех комбинаций (наборов) значений аргументов, а при любом количестве аргументов - методом математической индукции.

Законы алгебры логики Свойством коммутативности обладают и другие ЛФ, например: и т.п. Но: Сочетательный (ассоциативный) закон:, аналог (аb) с = а (bс),, аналог (а + b) + с = а + (b + с). Скобки задают порядок действий (сначала действие выполняется в скобках). Таким образом, речь идет о перестановке скобок, или об изменении порядка действий. Интересно, что коммутативная ЛФ штрих Шеффера неассоциативна: (х 1 / х 2 ) / х 3 х 1 / (х 2 / х 3 ). Например, (1/0)/0=1/0=1, 1 /(0/0) = 1 / 1 = 0 1.

Законы алгебры логики Распределительный (дистрибутивный) закон касается уже не одной, а двух функций. Есть распределительный закон конъюнкции относительно дизъюнкции: аналог: а (b + с) = а b + а с.

Законы алгебры логики И есть обратный закон, выражающий дистрибутивность дизъюнкции относительно конъюнкции: В обычной алгебре аналога такому закону нет: a + b c (a + b) (a + c), в общем случае. В наличии взаимной дистрибутивности конъюнкции и дизъюнкции проявляется двойственность этих функций. Она будет обнаруживаться и в дальнейшем.

Законы алгебры логики В преобразовании логических выражений (с целью их упрощения - минимизации, но с сохранением, конечно, эквивалентности) используются и другие полезные законы- свойства. Закон идемпотентности: Закон двойного отрицания:, аналог -(- а) = а.

Законы алгебры логики Законы де Моргана: Здесь снова видна двойственная природа функций & и v. Закон противоречия: Закон исключенного третьего: Можно видеть, что последние два закона получаются один из другого по «правилам» де Моргана и двойственного отрицания:

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

Операции над логическими функциями Пример. Результат суперпозиции: Здесь, конечно, возможны дальнейшие преобразования (упрощения).

Операции над логическими функциями Операция подстановки аргументов - это просто замена одних аргументов другими, перестановка их (перенумерация, изменение порядка записи). Пример. При синтезе логических схем только эти две операции имеют физическую интерпретацию. Иногда новую функцию (f 1 ), полученную из f, Y1, … путем многократного выполнения таких операций, называюn также суперпозицией функций f, Y 1, ….

Операции над логическими функциями В дальнейшем важную роль играют ЛФ специального вида, такие, как конституенты единицы и нуля. Конституента единицы - это ЛФ n аргументов, принимающая значение 1 только на одном наборе аргументов. Кстати, отсюда следует, что количество таких конституент в точности равно количеству наборов n аргументов, т.е. 2 n. Среди ЛФ двух аргументов конституент единицы - 4 (табл. 4): f 1, f 2, f 4, f 8.

Операции над логическими функциями Обычно конституенту единицы задают в виде конъюнкции всех аргументов, взятых прямо или инверсно - в зависимости от значения аргумента на соответствующем конституенте наборе (прямо, если это значение - 1; инверсно, если - 0). Здесь индекс при К - номер соответствующею набора Представленный в двоичной системе, этот индекс фактически определяет расстановку инверсий. Например:

Операции над логическими функциями Конституента нуля определяется аналогично. Это ЛФ, принимающая значение 0 только на одном наборе. Количество таких конституент тоже 2 n. Обычно конституенту нуля задают в виде дизъюнкции (дизъюнктивного терма) всех аргументов, взятых прямо или инверсно - в зависимости от значения аргумента на соответствующем наборе (прямо, если 0; инверсно, если 1). Для двух аргументов:

Операции над логическими функциями Теорема Жегалкина (И.И. Жегалкин [ ] - русский, советский математик, профессор МГУ). Любая ЛФ может быть представлена в виде многочлена (полинома) с использованием трех базовых функций (константа единицы, конъюнкция и сложение по модулю два): а 0, а 1, … - постоянные коэффициенты, 0 или 1.

Операции над логическими функциями Доказательство теоремы - конструктивное, т.е. не экзистенциальное («существовательное»). В процессе доказательства получается и сам многочлен Жегалкина. Итак, пусть ЛФ имеет единичное значение на наборах N 1, … N k, …. Тогда справедливо равенство: Действительно, на каждом таком наборе только одна из конституент единицы, … равна 1: А там, где функция равна 0, справа также получается 0:

Операции над логическими функциями Теперь нужно выполнить переход от суммы конституент к многочлену. Здесь можно выделить три этапа. Замена отрицаний (инверсий): Например, Раскрытие скобок на основании дистрибутивности конъюнкции относительно сложения по модулю два:

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

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

Пять замечательных классов логических функций Линейная ЛФ может быть представлена многочленом Жегалкина не выше первой степени: Таким образом, каждой линейной ЛФ можно поставить в соответствие (n+1)-разрядное число. Тогда количество различных линейных ЛФ n аргументов составит 2 n+1. Так, при n = 1 все = 4 функции линейны:

Пять замечательных классов логических функций Среди ЛФ двух аргументов (табл. 4.) линейных – = 8. Можно найти многочлены Жегалкина для всех 16 ЛФ двух аргументов, а затем выбрать из них линейные.табл. 4. Второй способ - выписать все возможные линейные многочлены:

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

Пять замечательных классов логических функций Доказательство. А: Суперпозиция. После подстановки выражений Y вместо х в f, раскрытия скобок и приведения подобных получается новая линейная функция Здесь надо заметить, что все произведения вила а i b jk тоже имеют значения 0 или 1.

Пять замечательных классов логических функций Пример. В: Подстановка аргументов. Здесь доказательство очевидно: линейность формы Жегалкина не зависит от порядка задания аргументов. Пример.

Пять замечательных классов логических функций Логическая функция, сохраняющая нуль, на нулевом наборе имеет значение 0. Очевидно, среди ЛФ n аргументов ровно половина функций, сохраняющих нуль, т.е. Q 0 =2 n-1. Так, для n = 2 (табл. 2.4) получаем Q 0 =2 4-1 =8. Это f 0 … f 7 (x 1, x 2 ).

Пять замечательных классов логических функций Теорема 2. В результате операций суперпозиции и подстановки аргументов из ЛФ, сохраняющих нуль, получаются также ЛФ, сохраняющие нуль, и только они. Доказательство. А: Суперпозиция. Тогда f 1 (у 1, …, у m ) 0…0 = 0, поскольку Y 1, …, Y n на этом же наборе имеют значение 0. Значит, и набор (х 1, …, x n ) - также нулевой, а здесь f (0, …, 0) = 0.

Пять замечательных классов логических функций В: Подстановка аргументов. Доказательство очевидно: перестановка аргументов, имеющих одинаковые значения (нуль), никакой роли не играет, нулевой набор остается нулевым и нулевое значение ЛФ сохраняется. Логическая функция, сохраняющая единицу, на единичном наборе имеет значение 1. Далее все аналогично предшествующему случаю. Так, Q 0 =2 n-1. Восемь ЛФ, сохраняющих единицу, при n=2 (табл. 4) – это f 1, f 3, f 5, f 7, f 9, f 11, f 13, f 15, т.е. все функции с нечетными номерами.

Пять замечательных классов логических функций Теорема 3 и ее доказательство вполне аналогичны случаю теоремы 2. Определение монотонной логической функции требует введения еще одного понятия - сравнимых и несравнимых наборов аргументов. Дело в том, что свойство монотонности обязательно только для пар сравнимых наборов. Итак, два набора аргументов сравнимы, если значению каждого аргумента в каком-то из них соответствует неменьшее значение того же аргумента в другом наборе, т.е. 0 соответствует 0 или 1, а 1 - только 1. Тогда первый из этих наборов считается меньшим, чем другой. Например, наборы (0, 0, 0, 1, 0) и (0, 1, 0, 1, 0) сравнимы, причем первый меньше второго. И, наоборот, наборы (0, 0, 0, 1, 0) и (0, 1, 0, 0, 1) несравнимы, здесь для четырех аргументов выполняется условие «меньше - равно» (0 0).

Пять замечательных классов логических функций Монотонная логическая функция при любом возрастании набора аргументов имеет неубывающее значение. Несравнимые наборы не рассматриваются. При n = 2 имеем = 6 пар наборов. Из них только одна пара (00 и 10) - несравнимые наборы. Таким образом, для анализа ЛФ на монотонность нужно сделать 5 проверок. Оказывается, среди ЛФ двух аргументов (табл. 4) - 6 монотонных: f 0, f 1, f 3, f 5 (наборы 01 и 10 несравнимы), f 7, f 15.

Пять замечательных классов логических функций Теорема 4. В результате операций суперпозиции и подстановки аргументов из монотонных ЛФ получаются также монотонные ЛФ, и только они. Доказательство. А: Суперпозиция. Рассмотрим некоторый набор. Ему соответствует набор. Имеем равенство:. Теперь увеличим набор k y, тогда любой набор не уменьшится. А значит, поскольку все функции Y также монотонные, не уменьшится набор k x. В силу монотонности функции f не уменьшится и ее значение, равное, кстати, значению функции f 1. Таким образом, монотонность f 1 доказана.

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

Пять замечательных классов логических функций Самодвойственная логическая функция на противоположных наборах имеет противоположные (взаимноинверсные) значения. Т.е. нулю соответствуют единицы, а единице - нуль. Среди ЛФ 2 аргументов - четыре самодвойственных функции: f 3, f 5, f 10, f 12 (табл. 4).

Пять замечательных классов логических функций Теорема 5. В результате операций суперпозиции и подстановки аргументов из самодвойственных ЛФ получаются также самодвойственные ЛФ, и только они. Доказательство. A: Суперпозиция. Набору соответствует набор, так, что. Теперь инвертируем набор k y. Поскольку все функции Y самодвойственные, набор k x также инвертируется, т.е. становится противоположным по отношению к себе. Самодвойственность функции f влечет при этом ее инверсию, а значит – инверсию f 1. Таким образом, самодвойственность f 1 доказана.

Пять замечательных классов логических функций В: Подстановка аргументов. Инверсия набора (х 1, х 2, …, х n ) влечет инверсию и набора (х 2, х 1,..., х n ), поскольку позиции аргументов при этом никакой роли не играют. В силу самодвойственности f ее значение f(х 2,..., х n ) инвертируется, а вместе с этим инвертируется и значение f 1. Таким образом, f 1 - самодвойственная функция.

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

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

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

Лекция окончена Нажмите клавишу для выхода