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

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

Закон поглощения:

для логического сложения: А  (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-диодов).

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

Законы мира, сущность предметов, общее в них мы познаем посредством абстрактного мышления. Основными формами абстрактного мышления являются понятия, суждения и умозаключения.

Понятие - форма мышления, в которой отражаются существенные признаки отдельного предмета или класса однородных предметов. Понятия в языке выражаются словами.

Объем понятия - множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятия. Выделяют понятия общие и единичные.

Выделяют следующие отношения понятий по объему:

• тождество или совпадение объемов, означающее, что объем одного понятия равен объему другого понятия;
• подчинение или включение объемов: объем одного из понятий полностью включен в объем другого;
• исключение объемов - случай, в котором нет ни одного признака, который бы находился в двух объемах;
• пересечение или частичное совпадение объемов;
• соподчинение объемов - случай, когда объемы двух понятий, исключающие друг друга, входят в объем третьего.

Суждение - это форма мышления, в которой что-либо утверждается или отрицается о предметах, признаках или их отношениях.

Умозаключение - форма мышления, посредством которой из одного или нескольких суждений, называемых посылками, мы по определенным правилам вывода получаем суждение-заключение.

Алгебра в широком смысле этого слова наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только над числами, но и над другими математическими объектами.

Примеры алгебр: алгебра натуральных чисел, алгебра рациональных чисел, алгебра многочленов, алгебра векторов, алгебра матриц, алгебра множеств и т.д. Объектами алгебры логики или булевой алгебры являются высказывания.

Высказывание - это любое предложение какого-либо языка (утверждение), содержание которого можно определить как истинное или ложное.

Всякое высказывание или истинно, или ложно; быть одновременно и тем и другим оно не может.

В естественном языке высказывания выражаются повествовательными предложениями. Восклицательные и вопросительные предложения высказываниями не являются.

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

Высказывание называется простым (элементарным), если никакая его часть сама не является высказыванием.

Высказывание, состоящее из простых высказываний, называются составным (сложным).

Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:
А = {Аристотель - основоположник логики},
В = {На яблонях растут бананы}.

Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания: "Сумма углов треугольника равна 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

Логические операции имеют следующий приоритет: действия в скобках, инверсия, &, , ~.

Таблицу, показывающую, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности составного высказывания.

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

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в логическом выражении;
2. определить число строк в таблице m = 2 n ;
3. подсчитать количество логических операций в формуле;
4. установить последовательность выполнения логических операций с учетом скобок и приоритетов;
5. определить количество столбцов в таблице: число переменных плюс число операций;
6. выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n-разрядных двоичных чисел от 0 до 2 n -1;
7. провести заполнение таблицы истинности по столбикам, выполняя логические операции в соответствии с установленной в п.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 различных логических функций от двух переменных.

Логические выражения называются равносильными , если их истинностные значения совпадают при любых значениях, входящих в них логических переменных.

В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.

1. Закон двойного отрицания:
   не (не А) = A.
   Двойное отрицание исключает отрицание.
2. Переместительный (коммутативный) закон:
   - для логического сложения:
   А B = B A;

   
   A & B = B & A.

   Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

3. Сочетательный (ассоциативный) закон:
   - для логического сложения:
   (A B) C = A (B C);

   Для логического умножения:
   (A & B) & C = A & (B & C).

   При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

4. Распределительный (дистрибутивный) закон:
   - для логического сложения:
   (A B) & C = (A & C) (B & C);

   Для логического умножения:
   (A & B) C = (A C) & (B C).

   Определяет правило выноса общего высказывания за скобку.

5. Закон общей инверсии (законы де Моргана):
   - для логического сложения:
   ;

   Для логического умножения:
   .

6. Закон идемпотентности (от латинских слов idem - тот же самый и potens -сильный; дословно - равносильный):
   - для логического сложения:
   A A = A;

   Для логического умножения:
   A & A = A.

   Закон означает отсутствие показателей степени.

7. Законы исключения констант:
   - для логического сложения:
   A 1 = 1, A 0 = A;

   Для логического умножения:
   A & 1 = A, A & 0 = 0.

8. Закон противоречия:
   A & (не A)= 0.

   Невозможно, чтобы противоречащие высказывания были одновременно истинными.

9. Закон исключения третьего:
   A (не A) = 1.

   Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе - ложно, третьего не дано.

10. Закон поглощения:
    - для логического сложения:
    A (A & B) = A;

    Для логического умножения:
    A & (A B) = A.

11. Закон исключения (склеивания):
    - для логического сложения:
    (A & B) (& B) = B;

    Для логического умножения:
    (A B) & ( B) = B.

12. Закон контрапозиции (правило перевертывания):
    (AB) = (BA).

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

Пример. Упростить логическое выражение:

1. Ефимова О., Морозов В., Угринович Н. Курс компьютерной технологии с основами информатики. Учебное пособие для старших классов. - М.: ООО "Издательство АСТ"; АВF, 2000 г.
2. Задачник-практикум по информатике. В 2-х томах/Под ред. И.Семакина, Е.Хеннера. - М.: Лаборатория Базовых Знаний, 2001 г.
3. Угринович Н. Информатика и информационные технологии. 10-11 класс- М.: Лаборатория Базовых Знаний, АО "Московские учебники", 2001 г.

Задачи и тесты по теме "Основы формальной логики"

• Логика СУБД Access - Логико-математические модели 10 класс

  Уроков: 5 Заданий: 9 Тестов: 1

• Решение логических задач средствами математической логики

  Уроков: 4 Заданий: 6 Тестов: 1

Уважаемый ученик!

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

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

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

Тема "Логика" обычно вызывает некоторое недоумение учащихся, не все понимают важность изучения данной темы. Хочется отметить, что знание логики важно не только как основа для дальнейшего изучения языков программирования и принципов работы с базами данных, но и как "тренажер" для развития особого типа мышления. Человек, преуспевший в изучении логики, имеет огромные преимущества в общении. Очень лестно услышать в свой адрес: "Логично", "в Ваших рассуждениях присутствует логика".

§4. Равносильные, ТИ и ТЛ формулы алгебры логики. Основные равносильности. (Законы логических операций). Закон двойственности.

Определение.

Две формулы алгебры логики А и В называются РАВНОСИЛЬНЫМИ, если они принимают одинаковые логические значения на любом наборе входящих в формулы элементарных высказываний. Равносильность формул будем обозначать знаком º, а запись А ºВ означает, что формулы А и В равносильны.

Формула А называется ТОЖДЕСТВЕННО ИСТИННОЙ (или ТАВТОЛОГИЕЙ), если она принимает значение 1 при всех значениях входящих в неё переменных.

Формула называется ТОЖДЕСТВЕННО ЛОЖНОЙ (или ПРОТИВОРЕЧИЕМ), если она принимает значение 0 при всех значениях входящих в неё переменных.

Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А«В – тавтология, и обратно, если формула А«В – тавтология, то формулы А и В равносильны.

Важнейшие равносильности алгебры логики можно разбить на три группы.

1. Основные равносильности.

Законы идемпотентности.

Закон противоречия

Закон исключенного третьего

Закон снятия двойного отрицания

законы поглощения

2. Равносильности, выражающие одни логические операции через другие.

Здесь 3, 4, 5, 6 – законы Моргана.

Ясно, что равносильности 5 и 6 получаются из равносильностей 3 и 4, соответственно, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания.

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

Так как при одинаковых логических значениях x и y истинными являются формулы https://pandia.ru/text/78/396/images/image018.gif" width="124" height="21">. Следовательно, в этом случае обе части равносильности имеют одинаковые истинные значения.

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

Таким образом, и в этом случае обе части равносильности имеют одинаковые логические значения.

Аналогично доказываются равносильности 2 и 4.

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

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

Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция “Штрих Шеффера”. Эта операция обозначается символом ½ left " style="border-collapse:collapse;border:none;margin-left:6.75pt;margin-right: 6.75pt">

Дискретная математика: Математическая логика

Лекция 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.

Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

Метод Квайна-МакКласки

Минимизация логических функций можно проводить с помощью метода Квайна-МакКласски, который состоит из четырех шагов:

1. 
   Представим наборы (конституенты), на которых функция истинна, в виде двоичных эквивалентов.
2. 
   Упорядочим двоичные эквиваленты по ярусам (по числу единиц двоечных эквивалентов) и провести склейку (применить правило склеивания к соответствующим конституентам) наборов в соседних ярусах, получая максимальные интервалы до тех пор, пока это возможно; помечаем каждый набор, участвовавший в склейке. Склеиваются только те наборы или интервалы, различие в которых заключается только в значении одного разряда: 001 и 000, 001- и 101-, и т.д.
3. 
   Построим таблицу Квайна, столбцы которой соответствуют двоичные наборы истинности функции, а строки – максимальным интервалам. Если i-ый набор покрывается j-ым интервалом, то ставим 1 на пересечении соответствующих строки и столбца, в противном случае ставим 0 или ничего.
4. 
   Находим минимальное покрытие таблицы Квайна, состоящее из минимального количества максимальных интервалов, включающих в себя (покрывающих) все наборы, на которых функция истинна.

Рассмотрим функцию F1, которая истинна на наборах {1, 3, 5, 7, 11, 13, 15}. Совершенная дизъюнктивная нормальная форма данной функции равна:

Двоичные эквиваленты истинных наборов следующие:

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.

ЛИТЕРАТУРА

1. 
   Гусева А.И. Учимся информатике: задачи и методы их решения.- М.: ДИАЛОГ-МИФИ, 2003.
2. 
   Горбатов В.А. Фундаментальные основы дискретной математики. - М.: Наука. Физматлит, 1999.-544с

Основные законы алгебры логики и правила преобразования логических выражений

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

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

1. Закон противоречия:

2. Закон исключенного третьего:

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

4. Законы де Моргана:

5. Законы повторения: A & A = A; A v A = A; В & В = В; В v В = В.

6. Законы поглощения: A ? (A & B) = A; A & (A ? B) = A.

7. Законы исключения констант: A ? 1 = 1; A ? 0 = A; A & 1 = A; A & 0 = 0; B ? 1 = 1; B ? 0 = B; B & 1 = B; B & 0 = 0.

8. Законы склеивания:

9. Закон контрапозиции: (A ? B) = (B ? A).

Для логических переменных справедливы и общематематические законы. Для простоты записи приведем общематематические законы для трех логических переменных A, В и С:

1. Коммутативный закон: A & B = B & A; A ? B = B ? A.

2. Ассоциативный закон: A & (B & C) = (A & B) & C; A ? (B ? C) = (A ? B) ? C.

3. Дистрибутивный закон: A & (B ? C) = (A & B) ? (A & C).

Как уже отмечалось, с помощью законов алгебры логики можно производить равносильные преобразования логических выражений с целью их упрощения. В алгебре логики на основе принятого соглашения установлены следующие правила (приоритеты) для выполнения логических операций: первыми выполняются операции в скобках, затем в следующем порядке: инверсия (отрицание), конъюнкция (&), дизъюнкция (v), импликация (?), эквиваленция (?)

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

применив соответствующие законы алгебры логики.

Урок Законы алгебры логики

• научиться применять законы алгебры логики для упрощения выражений;
• развивать логическое мышлении;
• прививать внимательность

Опрос законов алгебры логики (на доске).

Перечислим наиболее важные из них:

• X X Закон тождества.
• Закон противоречия
• Закон исключенного третьего
• Закон двойного отрицания
• Законы идемпотентности: X X X, X X C
• Законы коммутативности (переместительности): X Y Y X, X Y Y X
• Законы ассоциативности (сочетательности): (X Y) Z X (Y Z), (X Y) Z X (Y Z)
• Законы дистрибутивности (распределительности): X (Y Z) (X Y) (X Z), X (Y Z) (X Y) (X Z)
• Законы де Моргана ,
• X 1 X, X 0 X
• X 0 0, X 1 1

1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания — то же, что утверждать это высказывание.

“ Неверно, что 2*24”

Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.

Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.

В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.

Смысл законов де Моргана (Август де Морган (1806-1871) — шотландский математик и логик) можно выразить в кратких словесных формулировках:

— отрицание логического произведения эквивалентно логической сумме отрицаний множителей.

— отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

1. Установить эквивалентны ли высказывания.

3. С помощью таблиц истинности доказать законы поглощения и склеивания.

I. Подача нового материала.

1. Законы поглощения: X (X Y) X, X (X Y) X
2. Законы склеивания: (X Y) (Y) Y, (X Y) (Y) Y

Доказать законы логики можно:

1. с помощью таблиц истинности;
2. с помощью равносильностей.

Докажем законы склеивания и поглощения с помощью равносильностей:

3. (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 склеивания
4. X (X Y) X*X+X*Y X+X*Y X(1+Y) X поглощения

П. Практическая часть

1. Упрощение формул.

Пример 1. Упростить формулу (А+В)·* (А+С)

5. Раскроем скобки (A + B) * (A + C) A * A + A * C + B * A + B * C
6. По закону идемпотентности A*A A , следовательно, A*A + A*C + B*A + B*C A + A*C + B*A + B*C
7. В высказываниях А и А*C вынесем за скобки А и используя свойство А+1 1, получим А+А*С+ B*A + B*C A*(1 + С) + B*A + B*СA + B*A + B*С
8. Аналогично пункту 3. вынесем за скобки высказывание А.
   A + B*A + B*С A (1 + B) + B С A + B*С
   

2. Преобразования “поглощение” и “склеивание”

Пример 2. Упростить выражение А+ A*B

Решение. A+A*B A (1 + B) A — поглощение

Пример 3. Упростить выражение A*B+A*

Решение . A*B + A* A (B + ) A — склеивание

3. Всякую формулу можно преобразовать так, что в ней не будет отрицаний сложных высказываний — все отрицания будут применяться только к простым высказываниям.

Пример 4. Преобразовать формулу так, чтобы не было отрицаний сложных высказываний.

9. Воспользуемся формулой де Моргана, получим:
10. Для выражения применим еще раз формулу де Моргана, получим:
    

4. Любую формулу можно тождественно преобразовать так, что в ней не будут использованы:

11. знаки логического сложения;
12. знаки логического умножения,
13. будут использованы:
14. знаки отрицания и логического умножения
15. знаки отрицания и логического сложения.

Пример 5. Преобразовать формулу так, чтобы в ней не использовались знаки логического сложения.

Решение. Воспользуемся законом двойного отрицания, а затем формулой де Моргана.

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

Все операции можно выразить через конъюнкцию и отрицание, дизъюнкцию и отрицание, импликацию и отрицание. Через эквиваленцию и отрицание остальные операции выразить нельзя.

Задание 1. Установить истинность высказывания .
Задание 2 Установить является ли высказывание тавтологией?
Задание 3. Установить эквивалентны ли высказывания.

1. Формулы данных высказываний преобразовать в эквивалентные, исключив логическое сложение:

2. Формулы данных высказываний преобразовать в эквивалентные, исключить логическое умножение.

lunina.21205s09.edusite.ru

МИР ЛОГИКИ

Законы алгебры логики и правила преобразования логических выражений

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

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

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

Закон

Формулировка

1. Закон тождества

Всякое высказывание тождественно самому себе.

2. Закон исключенного третьего

Высказывание может быть либо истинным, либо ложным, третьего не дано. Следовательно, результат логического сложения высказывания и его отрицания всегда принимает значение «истина».

3. Закон непротиворечия

Высказывание не может быть одновременно истинным и ложным. Если высказывание Х истинно, то его отрицание НЕ Х должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно.

4. Закон двойного отрицания

Если дважды отрицать некоторое высказывание, то в результате получим исходное высказывание.

5. Переместительный (коммутативный) закон

6. Сочетательный (ассоциативный) закон

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

5. Распределительный (дистрибутивный) закон

(X /\ Y) \/ Z= (X /\ Z) \/ (Y /\ Z)

(X /\ Y) \/ Z = (X \/ Z) /\ (Y \/ Z)

Определяет правило выноса общего высказывания за скобку.

7. Закон общей инверсии Закон де Моргана

Закон общей инверсии.

8. Закон равносильности (идемпотентности)

от латинских слов idem - тот же самый и potens -сильный

Законы поглощения алгебра логики

Тема 3. Основы математической логики 1. Логические выражения и логические операции.
2. Построение таблиц истинности и логических функций.
3. Законы логики и преобразование логических выражений.
Лабораторная работа № 3. Основы математической логики.

3. Законы логики и правила преобразования логических выражений

Закон двойного отрицания (двойное отрицание исключает отрицание):

А = = Ú

Закон идемпотентности (от латинских слов idem - тот же самый и potens - сильный; дословно - равносильный):

для логического сложения: А Ú A = A ;

для логического умножения:A & A = A .

Закон означает отсутствие показателей степени.

для логического умножения:A & 1 = A, A & 0 = 0 .

A & = 0 .

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

A Ú = 1 .

Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе - ложно, третьего не дано.

для логического умножения:A & (A Ú B) = A .

Знание законов логики позволяет проверять правильность рассуждений и доказательств. Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.

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

Нарушения законов логики приводят к логическим ошибкам и вытекающим из них противоречиям.

Пример 1. Упростить формулу (А Ú В) & (А Ú С) .

Аналогично предыдущему пункту вынесем за скобки высказывание А .
A Ú B & A Ú B & C = A & (1 Ú B) Ú B & C = A Ú B & C .

Таким образом, мы доказали закон дистрибутивности.

Всякую формулу можно преобразовать так, что в ней не будет отрицаний сложных высказываний — все отрицания будут применяться только к простым высказываниям.

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

Решение: