Логика - наука, изучающая законы и формы мышления; учение о способах рассуждений и доказательств.
Законы мира, сущность предметов, общее в них мы познаем посредством абстрактного мышления. Основными формами абстрактного мышления являются понятия, суждения и умозаключения.
Понятие - форма мышления, в которой отражаются существенные признаки отдельного предмета или класса однородных предметов. Понятия в языке выражаются словами.
Объем понятия - множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятия. Выделяют понятия общие и единичные.
Выделяют следующие отношения понятий по объему:
- тождество или совпадение объемов, означающее, что объем одного понятия равен объему другого понятия;
- подчинение или включение объемов: объем одного из понятий полностью включен в объем другого;
- исключение объемов - случай, в котором нет ни одного признака, который бы находился в двух объемах;
- пересечение или частичное совпадение объемов;
- соподчинение объемов - случай, когда объемы двух понятий, исключающие друг друга, входят в объем третьего.
Суждение - это форма мышления, в которой что-либо утверждается или отрицается о предметах, признаках или их отношениях.
Умозаключение - форма мышления, посредством которой из одного или нескольких суждений, называемых посылками, мы по определенным правилам вывода получаем суждение-заключение.
Алгебра в широком смысле этого слова наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только над числами, но и над другими математическими объектами.
Примеры алгебр: алгебра натуральных чисел, алгебра рациональных чисел, алгебра многочленов, алгебра векторов, алгебра матриц, алгебра множеств и т.д. Объектами алгебры логики или булевой алгебры являются высказывания.
Высказывание - это любое предложение какого-либо языка (утверждение), содержание которого можно определить как истинное или ложное.
Всякое высказывание или истинно, или ложно; быть одновременно и тем и другим оно не может.
В естественном языке высказывания выражаются повествовательными предложениями. Восклицательные и вопросительные предложения высказываниями не являются.
Высказывания могут выражаться с помощью математических, физических, химических и прочих знаков. Из двух числовых выражений можно составить высказывания, соединив их знаками равенства или неравенства.
Высказывание называется простым (элементарным), если никакая его часть сама не является высказыванием.
Высказывание, состоящее из простых высказываний, называются составным (сложным).
Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:
А
= {Аристотель - основоположник логики},
В
= {На яблонях растут бананы}.
Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания: "Сумма углов треугольника равна 180 градусов" устанавливается геометрией, причем - в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского - ложным.
Истинному высказыванию ставится в соответствие 1, ложному - 0. Таким образом, А = 1, В = 0.
Алгебра логики отвлекается от смысловой содержательности высказываний. Ее интересует только один факт - истинно или ложно данное высказывание, что дает возможность определять истинность или ложность составных высказываний алгебраическими методами.
Основные операции алгебры высказываний.
Логическая операция КОНЪЮНКЦИЯ (лат. conjunctio - связываю):
- в естественном языке соответствует союзу и ;
- обозначение: & ;
- в языках программирования обозначение: and ;
- иное название: логическое умножение .
Конъюнкция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.
Таблица истинности конъюнкции:
| А | В | А &В |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Логическая операция ДИЗЪЮНКЦИЯ (лат. disjunctio - различаю):
Дизъюнкция - это логическая операция, которая каждым двум простым высказываниям ставит в соответствие составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны и истинным, когда хотя бы одно из двух образующих его высказываний истинно.
Таблица истинности дизъюнкции:
| А | В | А В |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Логическая операция ИНВЕРСИЯ (лат. inversio - переворачиваю):
Отрицание - это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.
Таблица истинности отрицания:
| А | не А |
| 0 | 1 |
| 1 | 0 |
Функция логического сложения ИЛИ (ЛогЗнач1;ЛогЗнач2;…) дает значение TRUE (Истина), только тогда, когда хотя бы один логический аргумент имеют значение TRUE (1).
Функция логического отрицания НЕ(ЛогЗнач) дает значение TRUE (Истина), когда логический аргумент имеют значение FALSE (0) и, наоборот, значение FALSE (Ложь), когда логический аргумент имеют значение TRUE (1).
Логическая операция ИМПЛИКАЦИЯ (лат. implicatio - тесно связываю):
Импликация - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.
Таблица истинности импликации:
| А | В | А В |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Логическая операция ЭКВИВАЛЕНЦИЯ (лат. аequivalens - равноценное):
- в естественном языке соответствует оборотам речи тогда и только тогда и в том и только в том случае ;
- обозначение: ~ ;
- иное название: равнозначность .
Эквиваленция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны.
Таблица истинности эквиваленции:
| А | В | А ~В |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Логические операции имеют следующий приоритет: действия в скобках, инверсия, &, , ~.
Таблицу, показывающую, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности составного высказывания.
Составные высказывания в алгебре логики записываются с помощью логических выражений. Для любого логического выражения достаточно просто построить таблицу истинности.
Алгоритм построения таблицы истинности:
- подсчитать количество переменных n в логическом выражении;
- определить число строк в таблице m = 2 n ;
- подсчитать количество логических операций в формуле;
- установить последовательность выполнения логических операций с учетом скобок и приоритетов;
- определить количество столбцов в таблице: число переменных плюс число операций;
- выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n-разрядных двоичных чисел от 0 до 2 n -1;
- провести заполнение таблицы истинности по столбикам, выполняя логические операции в соответствии с установленной в п.4 последовательностью.
Наборы входных переменных, во избежание ошибок, рекомендуют перечислять следующим образом:
а) определить количество наборов входных переменных;
б) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки 0, а нижнюю -1;
в) разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами 0 или 1, начиная с группы 0;
г) продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами 0 или 1 до тех пор, пока группы 0 и 1 не будут состоять из одного символа.
Пример. Для формулы A&(B C) построить таблицу истинности алгебраически и с использованием электронных таблиц.
Количество логических переменных 3, следовательно, количество строк в таблице истинности должно быть 2 3 = 8.
Количество логических операций в формуле 5, следовательно, количество столбцов в таблице истинности должно быть 3 + 5 = 8.
| А | В | C | В C | А & (В C ) |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Логической (булевой) функцией называют функцию F(Х 1 , Х 2 , ..., Х n) , аргументы которой Х 1 , Х 2 , ..., Х n (независимые переменные) и сама функция (зависимая переменная) принимают значения 0 или 1.
Таблицу, показывающую, какие значения принимает логическая функция при всех сочетаниях значений ее аргументов, называют таблицей истинности логической функции. Таблица истинности логической функции n аргументов содержит 2 n строк, n столбцов значений аргументов и 1 столбец значений функции.
Логические функции могут быть заданы табличным способом или аналитически - в виде соответствующих формул.
Если логическая функция представлена с помощью дизъюнкций, конъюнкций и инверсий, то такая форма представления называется нормальной .
Существует 16 различных логических функций от двух переменных.
Логические выражения называются равносильными , если их истинностные значения совпадают при любых значениях, входящих в них логических переменных.
В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.
- Закон двойного отрицания:
не (не А) = A.
Двойное отрицание исключает отрицание. - Переместительный (коммутативный) закон:
- для логического сложения:
А B = B A;
A & B = B & A.Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.
- Сочетательный (ассоциативный) закон:
- для логического сложения:
(A B) C = A (B C);Для логического умножения:
(A & B) & C = A & (B & C).При одинаковых знаках скобки можно ставить произвольно или вообще опускать.
- Распределительный (дистрибутивный) закон:
- для логического сложения:
(A B) & C = (A & C) (B & C);Для логического умножения:
(A & B) C = (A C) & (B C).Определяет правило выноса общего высказывания за скобку.
- Закон общей инверсии (законы де Моргана):
- для логического сложения:
;Для логического умножения:
. - Закон идемпотентности (от латинских слов idem - тот же самый и potens -сильный; дословно - равносильный):
- для логического сложения:
A A = A;Для логического умножения:
A & A = A.Закон означает отсутствие показателей степени.
- Законы исключения констант:
- для логического сложения:
A 1 = 1, A 0 = A;Для логического умножения:
A & 1 = A, A & 0 = 0. - Закон противоречия:
A & (не A)= 0.Невозможно, чтобы противоречащие высказывания были одновременно истинными.
- Закон исключения третьего:
A (не A) = 1.Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе - ложно, третьего не дано.
- Закон поглощения:
- для логического сложения:
A (A & B) = A;Для логического умножения:
A & (A B) = A. - Закон исключения (склеивания):
- для логического сложения:
(A & B) (& B) = B;Для логического умножения:
(A B) & ( B) = B. - Закон контрапозиции (правило перевертывания):
(AB) = (BA).Справедливость приведенных законов можно доказать табличным способом: выписать все наборы значений А и В, вычислить на них значения левой и правой частей доказываемого выражения и убедиться, что результирующие столбцы совпадут.
Пример. Упростить логическое выражение:
- Ефимова О., Морозов В., Угринович Н. Курс компьютерной технологии с основами информатики. Учебное пособие для старших классов. - М.: ООО "Издательство АСТ"; АВF, 2000 г.
- Задачник-практикум по информатике. В 2-х томах/Под ред. И.Семакина, Е.Хеннера. - М.: Лаборатория Базовых Знаний, 2001 г.
- Угринович Н. Информатика и информационные технологии. 10-11 класс- М.: Лаборатория Базовых Знаний, АО "Московские учебники", 2001 г.
Задачи и тесты по теме "Основы формальной логики"
- Логика СУБД Access - Логико-математические модели 10 класс
Уроков: 5 Заданий: 9 Тестов: 1
- Решение логических задач средствами математической логики
Уроков: 4 Заданий: 6 Тестов: 1
Уважаемый ученик!
В Работе 1 представлены три темы, лежащие в основе курса "Информационные технологии". Надеемся, что Вы уже имеете минимальный опыт работы с компьютером и познакомились с его устройством еще в средних классах школы.
Тема "Компьютерные коммуникации. Интернет" вызывает большой интерес в последнее время, многие молодые люди проводят в глобальной сети почти все свое свободное время. Хочется напомнить, что виртуозное владение Интернет подразумевает не просто умение "бродить" в сети и посещать время от времени интересные "чат"ы", но и разбираться в принципах организации информации в глобальной сети, разбираться в ее структуре, протоколах, уметь настраивать браузер и почтовые программы, знать и соблюдать этику работы в Интернет. Ну и конечно использовать сеть по самому важному из ее назначений - для расширения своего кругозора.
Мы не рассматривали в этом курсе технологию создания Web-сайтов, полагая, что минимальные знания для создания домашней веб-страницы можно почерпнуть из дополнительной литературы. Создание же сайтов на профессиональном уровне требует определенной подготовки, в основе которой лежат навыки работы с текстом и графикой, а также умение программировать.
Тема "Логика" обычно вызывает некоторое недоумение учащихся, не все понимают важность изучения данной темы. Хочется отметить, что знание логики важно не только как основа для дальнейшего изучения языков программирования и принципов работы с базами данных, но и как "тренажер" для развития особого типа мышления. Человек, преуспевший в изучении логики, имеет огромные преимущества в общении. Очень лестно услышать в свой адрес: "Логично", "в Ваших рассуждениях присутствует логика".
Если рассматривать приложение исчисления высказываний для анализа и оптимизации контактно-релейных схем, схем автоматики и других приложений и, зная. что уменьшение числа элементов и/или связей приводит к повышению надёжности устройств, использующих эти схемы, то становится очевидным важность изучения таких формул в дискретной математике, которые позволяют произвести оптимизацию самой формулы.
К законам, позволяющим уменьшать элементы и операции логических высказываний, относятся законы поглощения и склеивания.
Закон поглощения:
для логического сложения: А (A & B) = A ;
для логического умножения: A & (A B) = A .
Знание законов логики позволяет проверять правильность рассуждений и доказательств. Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), другие - основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
Нарушения законов логики приводят к логическим ошибкам и вытекающим из них противоречиям.
8. Правило склеивания
;
(2.11)
.
(2.12)
Доказательство
(2.11):
.
Доказательство(2.12):
9. Закон обобщённого склеивания . (2.13) . (2.14) Доказательства(2.13): Доказательство (2.14). Раскроем скобки сначала левой части равенства (2.14) а, затем, правой его части. ; .
9. Правило де Моргана
Законы де Моргана (правила де Моргана ) - логические правила, связывающие пары дуальных логических операторов при помощи логического отрицания.
История и определение
Огастес де Морган первоначально заметил, что в классической пропозициональной логике справедливы следующие соотношения:
not (P and Q) = (not P) or (not Q)
not (P or Q) = (not P) and (not Q)
Обычная запись этих законов в формальной логике:
в теории множеств:
Формулы де-Моргана применимы при любом числе аргументов. Они иллюстрируют глубокую взаимную симметрию операций И и ИЛИ: если операция И избирательно реагирует на совпадение прямых сигналов, то операция ИЛИ так же избирательно реагирует на совпадение их инверсий. Элемент ИЛИ прозрачен для любого сигнала, элемент И - для любой инверсии. Пользуясь формулами де-Моргана, можно легко переводить логические схемы из базиса НЕ, И, ИЛИ, в котором человеку привычнее всего мыслить и составлять исходные логические выражения, в инвертирующие базисы, которые эффективнее всего реализуются интегральной технологией.
10.Стрелка Пирса
Стрелка Пирса (логическое «ИЛИ-НЕ») высказываний a и b - это новое высказывание, которое будет истинно тогда и только тогда, когда оба высказывания ложны.
Знаком стрелки Пирса является ↓
Значения функции стрелки Пирса представлены в таблице:
Логическим элементом операции стрелки Пирса является:
Стре́лка Пи́рса - бинарная логическая операция, булева функция над двумя переменными. Введена в рассмотрение Чарльзом Пирсом (Сharles Peirce) в 1880-1881 г.г.
Стрелка Пирса, обычно обозначаемая ↓, эквивалентна операции ИЛИ-НЕ и задаётся следующей таблицей истинности:
Таким образом, высказывание «X ↓ Y» означает «ни X, ни Y». От перемены мест операндов результат операции не изменяется.
|
X ↓ Y |
||
11. Штрих Ше́ффера - бинарнаялогическая операция,булева функциянад двумя переменными. Введена в рассмотрениеГенри Шефферомв 1913 г. (вотдельных источниках именуется как Пунктир Чулкова) Штрих Шеффера, обычно обозначаемый |, эквивалентен операции И-НЕ и задаётся следующей таблицей истинности:
Таким образом, высказывание X | Y означает, что X и Y несовместны, т.е. не являются истинными одновременно. От перемены мест операндов результат операции не изменяется. Штрих Шеффера, как и стрелка Пирса, образует базис для пространства булевых функций от двух переменных. То есть используя только штрих Шеффера можно построить остальные операции. Например,
-отрицание
Дизъюнкция
Конъюнкция
Константа 1
В электронике это означает, что для реализации всего многообразия схем преобразования сигналов, представляющих логические значения, достаточно одного типового элемента. С другой стороны, такой подход увеличивает сложность реализующих логические выражения схем и тем самым снижает их надёжность. Примером может являться промышленная 155 серия.
Элемент 2И-НЕ (2-in NAND), реализующий штрих Шеффера обозначается следующим образом (по стандартам ANSI):
В европейских стандартах принято другое обозначение:
12. Диодные ключи. Общие сведения. Электронный ключ - это устройство, которое может находиться в одном из двух устойчивых состояний: замкнутом или разомкнутом. Основу электронного ключа составляет нелинейный активный элемент (полупроводниковый диод, транзистор, тиристор и др.), работающий в ключевом режиме. По типу используемого нелинейного элемента электронные ключи делятся на диодные, транзисторные, тиристорные и т. д.
Диодные ключи. Простейший тип электронных ключей – диодные ключи. В качестве активных элементов в них используются полупроводниковые или электровакуумные диоды.
При положительном входном напряжении диод открыт и ток через него
,
где -
прямое сопротивление диода.
Выходное напряжение
.
Обычно , тогда. При отрицательном входном напряжении ток идет через диод
,
где - обратное сопротивление диода.
При этом выходное напряжение
.
Как правило, и
.
При изменении полярности включения
диода график функцииповернется
на уголвокруг
начала координат.
Диодные ключи не позволяют электрически разделить управляющую и управляемые цепи, что часто требуется на практике. Для переключения (коммутации) напряжений и токов служат т.н. диодные ключи. Эти схемы позволяют при подаче определенного управляющего напряжения замыкать/размыкать электрическую цепь, по которой передается полезный сигнал (ток, напряжение). В простейших ключевых схемах в качестве управляющего может использоваться сам входной сигнал.
Говоря о диодных ключах нельзя не упомянуть особый класс полупроводниковых диодов - p-i-n-диоды. Они применяются только для коммутации ВЧ и СВЧ сигналов. Это возможно благодаря их уникальному свойству - регулируемой проводимости на частоте сигнала. Такое регулирование осуществляется обычно либо при подаче на диод внешнего постоянного напряжения смещения, либо непосредственно уровнем сигнала (для ограничительных p-i-n-диодов).
Опрос законов алгебры логики (на доске).
Перечислим наиболее важные из них:
1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.
Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”.
Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.
Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания — то же, что утверждать это высказывание.
“ Неверно, что 2*24”
Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.
Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.
В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.
Смысл законов де Моргана (Август де Морган (1806-1871) — шотландский математик и логик) можно выразить в кратких словесных формулировках:
— отрицание логического произведения эквивалентно логической сумме отрицаний множителей.
— отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.
1. Установить эквивалентны ли высказывания.
3. С помощью таблиц истинности доказать законы поглощения и склеивания.
I. Подача нового материала.
Доказать законы логики можно:
- с помощью таблиц истинности;
- с помощью равносильностей.
- (X Y) (Y) (X+Y) *(+Y) X* + Y* + Y*Y+ X*Y Y* + Y + X*Y Y* + Y(1+X) Y* +Y Y(+1) Y склеивания
- X (X Y) X*X+X*Y X+X*Y X(1+Y) X поглощения
- Раскроем скобки (A + B) * (A + C) A * A + A * C + B * A + B * C
- По закону идемпотентности A*A A , следовательно, A*A + A*C + B*A + B*C A + A*C + B*A + B*C
- В высказываниях А и А*C вынесем за скобки А и используя свойство А+1 1, получим А+А*С+ B*A + B*C A*(1 + С) + B*A + B*СA + B*A + B*С
- Аналогично пункту 3. вынесем за скобки высказывание А.
A + B*A + B*С A (1 + B) + B С A + B*С
Таким образом, мы доказали закон дистрибутивности. - Воспользуемся формулой де Моргана, получим:
- Для выражения применим еще раз формулу де Моргана, получим:
Докажем законы склеивания и поглощения с помощью равносильностей:
П. Практическая часть
1. Упрощение формул.
Пример 1. Упростить формулу (А+В)·* (А+С)
2. Преобразования “поглощение” и “склеивание”
Пример 2. Упростить выражение А+ A*B
Решение. A+A*B A (1 + B) A — поглощение
Пример 3. Упростить выражение A*B+A*
Решение . A*B + A* A (B + ) A — склеивание
3. Всякую формулу можно преобразовать так, что в ней не будет отрицаний сложных высказываний — все отрицания будут применяться только к простым высказываниям.
Пример 4. Преобразовать формулу так, чтобы не было отрицаний сложных высказываний.
4. Любую формулу можно тождественно преобразовать так, что в ней не будут использованы:
- знаки логического сложения;
- знаки логического умножения,
- будут использованы:
- знаки отрицания и логического умножения
- знаки отрицания и логического сложения.
- Что необходимо знать о вступлении в права наследства Оформление наследства, как вид перехода собственности недвижимого имущества, считается самым сложным по части сбора большого количества многочисленных […]
Пример 5. Преобразовать формулу так, чтобы в ней не использовались знаки логического сложения.
Решение. Воспользуемся законом двойного отрицания, а затем формулой де Моргана.
Вывод: В алгебре логики всякую логическую функцию можно выразить через другие логические функции, но их должно быть по меньшей мере 2 операции, при этом одной из них обязательно должно быть отрицание.
Все операции можно выразить через конъюнкцию и отрицание, дизъюнкцию и отрицание, импликацию и отрицание. Через эквиваленцию и отрицание остальные операции выразить нельзя.
Задание 1.
Установить истинность высказывания .
Задание 2
Установить является ли высказывание тавтологией?
Задание 3.
Установить эквивалентны ли высказывания.
1. Формулы данных высказываний преобразовать в эквивалентные, исключив логическое сложение:
2. Формулы данных высказываний преобразовать в эквивалентные, исключить логическое умножение.
lunina.21205s09.edusite.ru
Законы поглощения и склеивания
Изучим два метода получения сокращенной ДНФ, но прежде вспомним законы поглощения и склеивания конъюнкций и добавим к ним закон неполного склеивания.
Закон поглощения: K 1 K 1 K 2 = K 1 .
Закон склеивания: x K x K = K.
Закон неполного склеивания: x K x K = x K x K K.
Закон обобщенного склеивания: x K 1 x K 2 = x K 1 x K 2 K 1 K 2 .
Очевидно, что закон неполного склеивания следует из закона обобщенного склеивания (при K 1 =K 2 =K), а закон склеивания – из закона неполного склеивания (если в последнем выполнить поглощения конъюнкций).
Переведем эти законы на язык интервалов, используя интервалы и представляющие их троичные векторы как синонимы.
Закон поглощения говорит о том, что если объединение двух интервалов I и I’ совпадает с I, то интервал I’ содержится в интервале I (поглощается им). Значит, поглощаемый вектор должен получаться из поглощающего заменой некоторых его внутренних компонент (–) на внешние (0 или 1).
Пример.
В паре троичных векторов 
вектор β поглощается вектором α.
Закон склеивания объединяет два соседних интервала в один. Напомним, что соседние интервалы совпадают по номерам внешних компонент, но различаются по значению ровно одной из них (ортогональной). При склеивании получается интервал, который отличается от исходных лишь в ортогональной компоненте – она становится внутренней (операция склеивания соседних интервалов уже рассматривалась в подразделе 2.2.3).
Пример. Результатом склеивания соседних векторов α и β является вектор γ:
Закон неполного склеивания объединяет два соседних интервала и добавляет к результату исходные интервалы.
Пример. Результатом неполного склеивания векторов α и β из предыдущего примера являются три вектора: α, β и γ.
Закон обобщенного склеивания объединяет соседние части двух смежных интервалов. Смежные интервалы могут не совпадать по номерам внешних компонент, но должны быть ортогональны ровно по одной из них. Результатом обобщенного склеивания являются три интервала: два исходных и третий, который строится следующим образом:
– компоненты, по которым исходные векторы совпадают, сохраняют свои значения;
– компоненты, которые в одном из векторов являются внешними, а в другом – внутренними, принимают значения внешних компонент;
– ортогональная компонента становится внутренней.
Пример. Результатом обобщенного склеивания смежных векторов α и β являются векторы α, β и γ:
Законы алгебры логики и следствия из них
При решении многих логических задач часто приходится упрощать формулы, полученные при формализации их условий. Упрощение формул в алгебре логики производится на основе эквивалентных преобразований, опирающихся на основные логические законы. Законы алгебры логики – это тавтологии (или теоремы).
1. Закон тождества:
2. Закон непротиворечия:
3. Закон исключения третьего:
4. Закон двойного отрицания:
5. Законы истины и лжи (свойства констант):
6. Законы идемпотентности:
7. Коммутативные законы:
8. Ассоциативные законы:
– дизъюнкции
– конъюнкции
9. Дистрибутивные законы:
– 1‑ый дистрибутивный закон
– 2‑ой дистрибутивный закон
10. Законы поглощения:
11. Законы де Моргана:
12. Закон импликации:
13. Закон эквивалентности:
14. Свойства сложения «по модулю два»:
Справедливость этих законов можно доказать с помощью таблиц истинности сложных логических связей описываемых законов.
Следствия из законов алгебры логики (часто используются при упрощении логических выражений).
1. Правило поглощения. Данное правило является следствием из дистрибутивного закона. Оно может быть записано в следующем виде:
.
2. Правило свертки. Правило является следствием из второго дистрибутивного закона. Запись правила:
а) 
;
б) 
.
3. Правило расширения. Правило записывается в следующем виде:
4. Правило склеивания. Базируется на понятии соседних конъюнкций. Соседними называются конъюнкции, отличающиеся представлением одной переменной. Например, конъюнкции и , и являются попарно соседними. В первой паре конъюнкции отличаются представлением х 2 , а во второй – представлением х 1 . По этим переменным конъюнкции склеиваются.
Формулировка правила: две соседние конъюнкции склеиваются с образованием одной конъюнкции меньшего ранга; исчезает та переменная, по которой конъюнкция склеивается.
Современные компьютеры, основанные на «древних» электронно-вычислительных машинах, в качестве базовых принципов работы опираются на определенные постулаты. Они называются законы алгебры логики. Впервые подобная дисциплина была описана (конечно, не столь подробно, как в современном виде) древнегреческим ученым Аристотелем.
Представляя собой отдельный раздел математики, в рамках которого изучается исчисление высказываний, алгебра логики имеет ряд четко выстроенных выводов и заключений.
С тем чтобы лучше разобраться в теме, разберем понятия, которые помогут в дальнейшем узнать законы алгебры логики.
Пожалуй, основной термин в изучаемой дисциплине - высказывание. Это некое утверждение, которое не может быть одновременно ложным и истинным. Ему всегда присуща лишь одна из этих характеристик. При этом условно принято истинности придавать значение 1, ложности - 0, а само высказывание называть некой A, B, C. Иначе говоря, формула A=1 означает, что высказывание А истинно. С высказываниями можно поступать самым различным образом. Вкратце рассмотрим те действия, которые можно с ними совершать. Отметим также, что законы алгебры логики невозможно усвоить, не зная этих правил.
1. Дизъюнкция двух высказываний - результат операции «или». Может быть или ложной, или истинной. Используется символ «v».
2. Конъюнкция. Результатом подобного действия, совершаемого с двумя высказываниями, станет новое лишь в случае, когда оба исходных высказывания истинны. Используется операция «и», символ «^».
3. Импликация. Операция «если А, то В». Результатом является высказывание, ложное лишь в случае истинности А и ложности В. Применяется символ «->».
4. Эквиваленция. Операция «A тогда и только тогда В, когда». Данное высказывание истинно в случаях, когда обе переменные имеют одинаковые оценки. Используется символ «<->».
Существует также ряд операций, близких к импликации, но в данной статье они рассмотрены не будут.
Теперь подробным образом рассмотрим основные законы алгебры логики:
1. Коммутативный или переместительный гласит, что перемена мест логических слагаемых в операциях конъюнкции или дизъюнкции на результате не сказывается.
2. Сочетательный или ассоциативный. Согласно этому закону, переменные в операциях конъюнкции или дизъюнкции можно объединять в группы.
3. Распределительный или дистрибутивный. Суть закона в том, что одинаковые переменные в уравнениях можно вынести за скобки, не изменив логики.
4. Закон де Моргана (инверсии или отрицания). Отрицание операции конъюнкции равносильно дизъюнкции отрицания исходных переменных. Отрицание от дизъюнкции, в свою очередь, равно конъюнкции отрицания тех же переменных.
5. Двойное отрицание. Отрицание некоего высказывания дважды дает в результате исходное высказывание, трижды - его отрицание.
6. Закон идемпотентности выглядит следующим образом для логического сложения: x v x v x v x = x; для умножения: x^x^x^=x.
7. Закон непротиворечия гласит: два высказывания, если они противоречивы, одновременно быть истинными не могут.
8. Закон исключения третьего. Среди двух противоречивых высказываний одно - всегда истинное, другое - ложное, третьего не дано.
9. Закон поглощения можно записать таким образом для логического сложения: x v (x^y)=x, для умножения: x^ (x v y)=x.
10. Закон склеивания. Две соседние конъюнкции способны склеиться, образовав конъюнкцию меньшего ранга. При этом та переменная, по которой исходные конъюнкции склеивались, исчезает. Пример для логического сложения:
(x^y) v (-x^y)=y.
Мы рассмотрели лишь наиболее используемые законы алгебры логики, которых по факту может быть многим больше, поскольку нередко логические уравнения приобретают длинный и витиеватый вид, сократить который можно, применив ряд схожих законов.
Как правило, для удобства подсчета и выявления результатов используются специальные таблицы. Все существующие законы алгебры логики, таблица для которых имеет общую структуру сеточного прямоугольника, расписывают, распределяя каждую переменную в отдельную клеточку. Чем больше уравнение, тем проще с ним справиться, используя таблицы.
Дискретная математика: Математическая логика
Лекция 8
Минимизация булевых функций. Метод Квайна-МакКласки
Законы алгебры Буля
В математической логике определяется специальная алгебра, алгебра Буля, содержащая операции логического умножения, логического сложения и отрицания { ,+, - }, которые позволяет производить тождественные преобразования логических выражений. К этим законам относятсяЗакон идемпотентности (одинаковости)
Закон коммутативности
a b = b a
Закон ассоциативности
a + (b + c) = (a + b) + c
a (b c) = (a b) c
Законы дистрибутивности
Дистрибутивность конъюнкции относительно дизъюнкции
A (b + c) = a b + a c
Дистрибутивность дизъюнкции относительно конъюнкции
A + b c = (a + b) (a + c)
акон двойного отрицания
Законы де Моргана
Законы поглощения
a + a b = a
a (a + b) = a
Законы, определяющие действия с логическими константами 0 и 1
| a + 0 = a a 0 = 0 | a + 1 = 1 a 1 = a |
| 1 = 0 |
|
Правомерность всех рассмотренных выше законов может быть легко доказана, например, с использованием таблиц истинности.
Дополнительные законы
Дополнительные законы алгебры Буля являются следствиями из основных законов и очень полезны при упрощении записи логических функций.
Закон склеивания
Доказательство этого тождества проводится с использованием первого закона дистрибутивности:
Доказательство этого тождества проводится с использованием второго закона дистрибутивности:
Закон Блейка-Порецкого
Применяя законы действия с логическими константами, идемпотентности и склеивания, данное тождество можно доказать следующим образом:
Закон свертки логического выражения
Данное тождество можно доказать, последовательно используя законы работы с логическими константами, дистрибутивности, идемпотентности и склеивания:
Упрощение логических функций
Для нормальных форм представления функций определено понятие сложности функции, как число первичных термов в таком представлении. Преобразования нормальной формы с целью снижения сложности функции называется упрощением . Для упрощения логических функций используются все законы алгебры логики..Задачи.
Упростить СДНФ следующих функций:
1. (a b ) c
2. (a b ) c
Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:
3.
Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:
СДНФ = 
Дальнейшее упрощение невозможно.
4. 
Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:
СДНФ =
5. 
Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:
Метод Квайна-МакКласки
Минимизация логических функций можно проводить с помощью метода Квайна-МакКласски, который состоит из четырех шагов:
Представим наборы (конституенты), на которых функция истинна, в виде двоичных эквивалентов.
Упорядочим двоичные эквиваленты по ярусам (по числу единиц двоечных эквивалентов) и провести склейку (применить правило склеивания к соответствующим конституентам) наборов в соседних ярусах, получая максимальные интервалы до тех пор, пока это возможно; помечаем каждый набор, участвовавший в склейке. Склеиваются только те наборы или интервалы, различие в которых заключается только в значении одного разряда: 001 и 000, 001- и 101-, и т.д.
Построим таблицу Квайна, столбцы которой соответствуют двоичные наборы истинности функции, а строки – максимальным интервалам. Если i-ый набор покрывается j-ым интервалом, то ставим 1 на пересечении соответствующих строки и столбца, в противном случае ставим 0 или ничего.
Находим минимальное покрытие таблицы Квайна, состоящее из минимального количества максимальных интервалов, включающих в себя (покрывающих) все наборы, на которых функция истинна.
Двоичные эквиваленты истинных наборов следующие:
| 1 | 0001 |
| 3 | 0011 |
| 5 | 0101 |
| 7 | 0111 |
| 11 | 1011 |
| 13 | 1101 |
| 15 | 1111 |
Упорядочим двоичные наборы по ярусам и проведем склейки, до тех пор, пока это возможно
| 0001 | 00-1 | 0-1 |
| 0011 | 0-01 | --11 |
| 0101 | -011 | -1-1 |
| 0111 | 0-11 | |
| 1101 | -101 | |
| 1011 | 01-1 | |
| 1111 | 11-1 | |
| -111 | ||
| 1-11 |
Затем строим таблицу Квайна:
| 0001 | 0011 | 0101 | 0111 | 1011 | 1101 | 1111 |
|
| 0--1 | 1 | 1 | 1 | 1 | |||
| --11 | 1 | 1 | 1 | 1 | 1 |
||
| -1-1 | 1 | 1 | 1 | 1 |
В нашей таблице наборы 0001 и 1011 покрываются единственно возможным образом, следовательно, покрывающие их минимальные интервалы называются обязательными
и образуют ядро покрытия
, т.к. должны входить в любое покрытие. В таблице соответствующие единицы подчеркнуты, интервалы {0- -1,- -11} образуют не только ядро покрытие, но и покрывают всю таблицу Квайна.
Таким образом, мы получили минимальную форму исследуемой функции в виде:
МДНФ = {0 - - 1, - - 1 1} = 
Рассмотрим несколько примеров.
Задачи.
1. Найти МДНФ функции f 1 =
f1
| x1 x2 x3 x4 | |
| 0 0 0 0 | 0 |
| 0 0 0 1 | 1 |
| 0 0 1 0 | 1 |
| 0 0 1 1 | 1 |
| 0 1 0 0 | 1 |
| 0 1 0 1 | 0 |
| 0 1 1 0 | 0 |
| 0 1 1 1 | 1 |
| 1 0 0 0 | 0 |
| 1 0 0 1 | 1 |
| 1 0 1 0 | 1 |
| 1 0 1 1 | 1 |
| 1 1 0 0 | 0 |
| 1 1 0 1 | 1 |
| 1 1 1 0 | 0 |
| 1 1 1 1 | 1 |
Совершенная ДНФ исследуемой функции имеет вид:
| 0001 | 00-1 | -0-1 |
| 0010 | -001 | -01- |
| 0100 | 001- | --11 |
| 0011 | -010 | 1-1 |
| 1010 | 0-11 | |
| 1001 | -011 | |
| 0111 | 101- | |
| 1011 | 10-1 | |
| 1101 | 1-01 | |
| 1111 | -111 | |
| 1-11 | ||
| 11-1 |
В первом столбике присутствует набор, который не участвовал ни в одной склейке – он сам является максимальным интервалом 0100. В третьем столбике к нему добавляется еще четыре максимальных интервала: {-0-1, -01-, --11, 1--1}.
Строим таблицу Квайна:
| 0001 | 0010 | 0100 | 0011 | 1010 | 1001 | 0111 | 1011 | 1101 | 1111 |
|
| 0100 | 1 | |||||||||
| -0-1 | 1 | 1 | 1 | 1 | ||||||
| -01- | 1 | 1 | 1 | 1 | ||||||
| --11 | 1 | 1 | 1 | 1 |
||||||
| 1--1 | 1 | 1 | 1 | 1 |
Определим ядро покрытия, в которое войдут обязательные интервалы:
{0100, -0-1, -01-, --11}. В данном случае, ядро покрытия покрывает и всю таблицу в целом.
Минимальная дизъюнктивная нормальная форма f1 имеет вид:
2. Найти МДНФ функции f 2( x 1, x 2, x 3), которая принимает единичные значения на наборах 0,2,3,6 и 7.
Построим таблицу истинности для f 2
| x1 x2 x3 | F2 |
| 0 0 0 | 1 |
| 0 0 1 | 0 |
| 0 1 0 | 1 |
| 0 1 1 | 1 |
| 1 0 0 | 0 |
| 1 0 1 | 0 |
| 1 1 0 | 1 |
| 1 1 1 | 1 |
СДНФ =
Упорядочим двоичные наборы по ярусам и проведем склейку:
| 000 | 0-0 | --0 |
| 010 | -00 | |
| 100 | -10 | |
| 110 | 1-0 | |
| 111 | 11- |
В результате склейки у нас получилось всего два максимальных интервала: {11-, --0}. Без построения таблицы Квайна очевидно, что они образуют минимальное покрытие, т.к. удаление любого из этих интервалов приведет к потери наборов, на которых функция f2(x1, x2, x3) истинна. МДНФ = x1 x2 +x3.
ЛИТЕРАТУРА
Гусева А.И. Учимся информатике: задачи и методы их решения.- М.: ДИАЛОГ-МИФИ, 2003.
Горбатов В.А. Фундаментальные основы дискретной математики. - М.: Наука. Физматлит, 1999.-544с
