Закон общей инверсии де моргана

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

Законы алгебры высказываний

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

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

Законы алгебры высказываний (алгебры логики) — это тавтологии.

Иногда эти законы называются теоремами.

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

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

Закон тождества:

А=А

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

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

Например, рассуждение Правильно говорят, что язык до Киева доведет, а я купил вчера копченый язык, значит, теперь смело могу идти в Киев неверно, так как первое и второе слова «язык» обозначают разные понятия.

В рассуждении: Движение вечно. Хождение в школу — движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое — в философском смысле — как атрибут материи, второе — в обыденном смысле — как действие по перемещению в пространстве), что приводит к ложному выводу.

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

В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано. Истинно либо А, либо не А. Примеры выполнения закона исключенного третьего:

1. Число 12345 либо четное, либо нечетное, третьего не дано.

2. Предприятие работает убыточно или безубыточно.

3. Эта жидкость является или не является кислотой.

Закон исключенного третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жесткой ситуацией: «либо — либо», «истина—ложь». Там же, где встречается неопределенность (например, в рассуждениях о будущем), закон исключенного третьего часто не может быть применен.

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

Парадокс (греч. paradoxos — неожиданный, странный) в этом примере возникает из-за того, что предложение ссылается само на себя. Другим известным парадоксом является задача о парикмахере: В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам.

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

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

Например, определим, чему эквивалентно (равносильно) А (двойное отрицание А, т. е. отрицание отрицания А).Для этого построим таблицу истинности:

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

Таким образом, мы можем сформулировать закон двойного отрицания:

Если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание. Например, высказывание А = Матроскин — кот эквивалентно высказыванию А = Неверно, что Матроскин не кот.

Аналогичным образом можно вывести и проверить следующие законы:

Свойства констант:

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

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

Законы коммутативности:

A v B = B v A

А & В = В & А

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

Законы ассоциативности:

A v(B v C) = (A v B) v C;

А & (В & C) = (A & В) & С.

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

Законы дистрибутивности:

A v (B & C) = (A v B) &(A v C)

(дистрибутивность дизъюнкции
относительно конъюнкции)

А & (B v C) = (A & B) v (А & C)

(дистрибутивность конъюнкции
относительно дизъюнкции)

Закон дистрибутивности конъюнкции относительно дизъюнкции аналогичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике. Поэтому необходимо его доказать. Доказательство удобнее всего провести с помощью таблицы истинности:

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

A v (A & B) = A

A & (A v B) = A

Проведите доказательство законов поглощения самостоятельно.

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

Словесные формулировки законов де Моргана:

Мнемоническое правило: в левой части тождества операция отрицания стоит над всем высказыванием. В правой части она как бы разрывается и отрицание стоит над каждым из простых высказываний, но одновременно меняется операция: дизъюнкция на конъюнкцию и наоборот.

Примеры выполнения закона де Моргана:

1) Высказывание Неверно, что я знаю арабский или китайский язык тождественно высказыванию Я не знаю арабского языка и не знаю китайского языка.

2) Высказывание Неверно, что я выучил урок и получил по нему двойку тождественно высказыванию Или я не выучил урок, или я не получил по нему двойку.

Замена операций импликации и эквивалентности

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

Так, заменить операцию импликации можно в соответствии со следующим правилом:

Для замены операции эквивалентности существует два правила:

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

Знание правил замены операций импликации и эквивалентности помогает, например, правильно построить отрицание импликации.

Рассмотрим следующий пример.

Пусть дано высказывание:

Е = Неверно, что если я выиграю конкурс, то получу приз.

Пусть А = Я выиграю конкурс,

В = Я получу приз.

Тогда

Отсюда, Е = Я выиграю конкурс, но приз не получу.

Пропустить Навигация

В начало
- Страницы сайта
  - Теги
  - Календарь
  - Новости сайта
- Курсы
  - Дистанционные курсы
  - Школьные площадки
    - Волжский район
    - Заводской район
    - Кировский район
    - Ленинский район
    - Октябрьский район
    - Фрунзенский район
    - ОУ городского подчинения и ГБУ
    - Саратовская область
      - Александрово – Гайский район
      - Аткарский район
      - Балаковский район
      - Балашовский район
      - Вольский район
      - Воскресенский район
      - Дергачевский район
      - Духовницкий район
      - Ершовский район
      - Ивантеевка
      - Калининский район
      - Красноармейский район
      - Краснокутский район
      - Лысогорский район
      - Марксовский район
      - Новобурасский район
      - Новоузенский район
      - Озинский район
      - Перелюбский район
      - Петровский район
      - Пугачевский район
      - Ровенский район
      - Ртищево
      - Саратовский район
      - Советский район
      - Татищевский район
      - Турковский район
      - Хвалынский район
      - Энгельсский район
      - МОУ “СОШ №12 ЗАТО Шиханы”
      - ЗАТО “Светлый”
    - СОИРО
  - Дистанционное обучение детей-инвалидов
  - О портале
  - Нормативные документы
  - Системы дистанционного образования
  - конференция
  - Семинары
  - Региональный Краеведческий марафон “Саратовская кр…
  - Областной конкурс видео и дистанционных курсов “До…
  - Виртуальный исторический класс
  - Методическое объединение дистанционных педагогов
  - Региональная инновационная площадка
  - Областной Фестиваль-конкурс “Экология и Я”
  - Президентские состязания

Пропустить Специальные возможности

Page 3

Пропустить Навигация

В начало
- Страницы сайта
  - Теги
  - Календарь
  - Новости сайта
- Курсы
  - Дистанционные курсы
  - Школьные площадки
    - Волжский район
    - Заводской район
    - Кировский район
    - Ленинский район
    - Октябрьский район
    - Фрунзенский район
    - ОУ городского подчинения и ГБУ
    - Саратовская область
    - СОИРО
  - Дистанционное обучение детей-инвалидов
  - О портале
  - Нормативные документы
  - Системы дистанционного образования
  - конференция
  - Семинары
  - Региональный Краеведческий марафон “Саратовская кр…
  - Областной конкурс видео и дистанционных курсов “До…
  - Виртуальный исторический класс
  - Методическое объединение дистанционных педагогов
  - Региональная инновационная площадка
  - Областной Фестиваль-конкурс “Экология и Я”
  - Президентские состязания

Пропустить Специальные возможности

Закон общей инверсии (законы де Моргана)

Закон общей инверсии де моргана

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

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

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

Законы исключения констант:
- для логического сложения: А1 = 1, А0 = A;
- для логического умножения:A & 1 = A, A & 0 = 0.
Закон противоречия:
- A &= 0.

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

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

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

Поделитесь с Вашими друзьями:

Архитектура ЭВМ.

Архитектура “звезда”.Здесь процессор (ЦУ) (рис.1.3.2, а) соединен непосредственно в ВУ и управляет их работой (ранние модели машин).

Этот тип также именуется классическая архитектура – одно арифметико-логическое устройство (АЛУ), через которое проходит поток данных, и одно устройство управления (УУ), через которое проходит поток команд – программа. Это однопроцессорный компьютер.

Рис. 1.3.2. Основные классы архитектур ЭВМ: а – централизованная; б – иерархическая; в – магистральная; г – общая структура персонального компьютера (архитектураTriton 430 TX – Northbridge/ Southbridge)

Поделитесь с Вашими друзьями:

Page 4

Растровые изображения представляют собой однослойную сетку точек, называемых пикселями (pixel, от англ. picture element). Код пикселя содержит информации о его цвете.

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

Она описывается одним числом, поэтому для кодирования одного пикселя требуется от 1 до 8 бит: чёрный цвет – 0, белый цвет – N = 2k-l, где k – число разрядов, которые отводятся для кодирования цвета. Например, при длине ячейки в 8 бит это 256-1 = 255.

Человеческий глаз в состоянии различить от 100 до 200 оттенков серого цвета, поэтому восьми разрядов для этого вполне хватает.

Цветные изображения воспринимаются нами как сумма трёх основных цветов – красного, зелёного и синего. Например, сиреневый = красный + синий; жёлтый = красный + зелёный; оранжевый = красный + зелёный, но в другой пропорции.

Поэтому достаточно закодировать цвет тремя числами – яркостью его красной, зелёной и синей составляющих. Этот способ кодирования называется RGB (Red – Green – Blue). Его используют в устройствах, способных излучать свет (мониторы).

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

Поэтому при печати цветных изображений используют метод CMY (Cyan – Magenta – Yellow) – голубой, сиреневый, жёлтый цвета. При таком кодировании красный = сиреневый + жёлтый; зелёный = голубой + жёлтый.

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

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

) Сложные объекты (ломаные линии, различные геометрические фигуры) представляются в виде совокупности элементарных графических объектов.

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

Кодирование звука

Как всякий звук, музыка является не чем иным, как звуковыми колебаниями, зарегистрировав которые достаточно точно, можно этот звук безошибочно воспроизвести. Нужно только непрерывный сигнал, которым является звук, преобразовать в последовательность нулей и единиц.

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

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

Например, при записи музыки на компакт-диски используются 16-разрядные значения и частота дискретизации 44 032 Гц.

Описанный способ кодирования звуковой информации достаточно универсален, он позволяет представить любой звук и преобразовывать его самыми разными способами. Но бывают случаи, когда выгодней действовать по-иному.

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

ведущие производители компьютеров и музыкальных синтезаторов разработали стандарт, определивший такую систему кодов. Он получил название MIDI (Musical Instrument Digital Interface).

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

Конечно, такая система кодирования позволяет записать далеко не всякий звук, она годится только для инструментальной музыки. Но есть у нее и преимущества: чрезвычайно компактная запись, естественность для музыканта (практически любой MIDI-редактор позволяет работать с музыкой в виде обычных нот), легкость замены инструментов, изменения темпа и тональности мелодии.

Есть и другие форматы записи музыки. Среди них – формат MP3, позволяющий с очень большим качеством и степенью сжатия кодировать музыку, при этом вместо 18 – 20 музыкальных композиций на стандартном компакт-диске (CDROM) помещается около 200. Одна песня занимает примерно 3,5 Mb, что позволяет пользователям сети Интернет легко обмениваться музыкальными композициями.

Поделитесь с Вашими друзьями:

Page 5

Триггер как элемент памяти. Схема RS-триггера

Память (устройство, предназначенное для хранения данных и команд) является важной частью компьютера. Можно сказать, что она его и определяет: если вычислительное устройство не имеет памяти, то оно уже не компьютер.

Элементарной единицей компьютерной памяти является бит. Поэтому требуется устройство, способное находиться в двух состояниях, т.е. хранить единицу или ноль.

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

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

Устройством, способным запоминать, хранить и позволяющим считывать информацию, является триггер. Он был изобретен в начале XX века Бонч-Бруевичем.

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

Рис. Кольцо из двух инверторов

Разнообразие триггеров весьма велико. Наиболее простой из них так называемый RS-триггер, который собирается из двух вентилей. Обычно используют вентили ИЛИ-НЕ или И-НЕ.

Поделитесь с Вашими друзьями:

Page 6

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

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

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

Законы исключения констант:
- для логического сложения: А1 = 1, А0 = A;
- для логического умножения:A & 1 = A, A & 0 = 0.
Закон противоречия:
- A &= 0.

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

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

Поделитесь с Вашими друзьями:

Логические формулы де Моргана

Закон общей инверсии де моргана

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

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

Формула де Моргана является одним из таких законов.

Краткая историческая справка

Огастес, или же Август де Морган жил в середине XIX века в Шотландии. Он был первым президентом Лондонского математического общества, но прославился в основном благодаря своим работам в сфере логики.

Ему принадлежит множество научных трудов. Среди них работы по теме пропозиционной логики и логики классов. А также, разумеется, формулирование всемирно известной формулы де Моргана, названной в его честь. В дополнение ко всему этому Август де Морган написал множество статей и книг, в том числе “Логика – это ничто”, которую, к сожалению, так и не перевели на русский язык.

Суть логической науки

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

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

Например, переменная “a” может означать “завтра грянет гром” или “девушка говорит неправду”, а под переменной “b” будут иметь в виду, что “завтра будет солнечно” или “парень говорит правду”.

В пример можно привести одну из самых простых логических формул. Переменная “a” означает то, что “девушка говорит неправду”, а под переменной “b” имеется в виду, что “парень говорит правду”.

А вот и сама формула: a = b. Она означает, что тот факт, что девушка говорит неправду равносилен тому, что парень говорит правду. Можно сказать, что она говорит неправду только в том случае, если он говорит правду.

Суть формул де Моргана

На самом деле все довольно очевидно. Формула закона де Моргана записывается вот так:

Не (а и b) = (не а) или (не b)

Если переводить эту формулу на слова, то отсутствие и “a”, и “b” означает либо отсутствие “a”, либо отсутствие “b”. Если говорить на более простом языке, то если нет и “a”, и “b”, значит нет “a” или нет “b”.

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

(Не а) или (не b) = Не (а и b)

Отрицание конъюнкции равно дизъюнкции отрицаний.

Конъюнкция – это операция, которую в сфере логики связывают с союзом “и”.

Дизъюнкция – это операция, которую в сфере логики связывают с союзом “или”. Например, “или одно, или второе, или оба сразу”.

Простейшие примеры из жизни

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

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

Нельзя сказать, что учащийся знаком с физикой и химией в том случае, если он не знает физики или не знает химии.

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

Зачем было искать доказательства и формулировать законы?

Формула де Моргана в логике открыла новую эпоху. Стали возможны новые варианты вычисления логических задач.

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

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

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

И напоследок

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

От моноидов к алгебрам де Моргана. Строим абстракции на Haskell

Закон общей инверсии де моргана

операция образует моноид с нейтральным элементом $inline$0$inline$:

операция образует моноид с нейтральным элементом :

выполняется мультипликативное свойство нуля:
свойство инволюции:
дуальность нуля и единицы относительно инволюции:
законы де Моргана:

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

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

Это выполняется для булевой алгебры и алгебры сопротивлений, но неверно для таблиц.

Абстракция алгебры де Моргана на Haskell

Перед началом работы подключим несколько расширений:

{-# LANGUAGE DeriveFunctor, FlexibleInstances, GeneralizedNewtypeDeriving #-}

Определим для алгебр де Моргана класс типов:

class DeMorgan a where {-# MINIMAL inv,(()|()),(zero|one) #-} inv :: a -> a zero :: a zero = inv one one :: a one = inv zero () :: a -> a -> a a b = inv (inv a inv b) () :: a -> a -> a a b = inv (inv a inv b)

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

Создадим первый экземпляр класса DeMorgan для логических данных:

instance DeMorgan Bool where zero = False inv = not () = (&&)

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

> True FalseTrue> one :: BoolTrue

Булева алгебра, это хорошо, но уж больно просто. Давайте её обобщим, построив алгебру для нечёткой логики в духе Лотфи Заде. Для этого определим тип-обёртку Fuzzy и потребуем у компилятора вывести для него числовые свойства:

newtype Fuzzy = Fuzzy { deFuzzify :: Double } deriving (Show, Num, Fractional, Ord, Eq) instance DeMorgan Fuzzy where zero = 0 inv x = fuzzify $ 1 – x a b = fuzzify $ max a b fuzzify x = 0 `max` x `min` 1
> deFuzzify $ one1> deFuzzify $ 0.2 0.40.2 > deFuzzify $ 0.8 0.4 0.50.5> deFuzzify $ 0.3 0.4 0.50.4

Определим простейшую алгебру де Моргана для таблиц, представленных вложенными списками:

instance DeMorgan [[a]] where zero = [] () = (++) inv = transpose

здесь мы использовали функцию transpose из библиотеки Data.List. Вот как работает эта алгебра:

> inv [[1,2],[3,4]][[1,3],[2,4]]> [[1,2],[3,4]] [[5],[6]][[1,2,5],[3,4,6]]> [[1,2],[3,4]] [[5,6]][[1,2],[3,4],[5,6]]

Давайте применим её для написания простенькой табулирующей функции table

table :: (Show a, Show b) => (a -> a -> b) -> [a] -> [[String]]table f vals = ([[” “]] h) (inv h c) where h = [show vals] c = [show [ f x y | x DeMorgan (Frac a) where zero = 0 inv = (1/) () = (+)
> getFrac $ 2 68.0> getFrac $ 2 61.5> getFrac $ 1 (2 (1 1))2.0

В качестве примера, выразим эффективное сопротивление цепи, показанной на рисунке и вычислим силу тока при напряжении 12 V:

> getFrac $ ((6 12) 4) (3 5)4.0> getFrac $ 12 / ((6 12) 4) (3 5)3.0

Дуальная алгебра

Для расчёта эффективной жёсткости сложной системы пружин, или ёмкости батареи конденсаторов, тоже годится тип Frac, но для этих расчётов нужно поменять местами операторы и , а также элементы zero и one.

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

Было бы хорошо сохранить семантику операторов, но изменить способ вычислений.

Тут математика снова даёт нам возможность воспользоваться её плодами. Как и для любого моноида, для любой алгебры де Моргана определена дуальная ей алгебра, в которой “всё наоборот”. Опишем это обстоятельство на языке Haskell. Создадим новый тип-обёртку Dual для дуальных алгебр и сообщим, что если алгебра a является алгеброй де Моргана, то и дуальная ей тоже будет алгеброй де Моргана.

newtype Dual a = Dual {getDual :: a} deriving (Show, Num, Fractional, Eq, Ord, Functor) instance DeMorgan a => DeMorgan (Dual a) where zero = Dual one one = Dual zero inv x = inv x Dual a Dual b = Dual $ a b Dual a Dual b = Dual $ a b
Теперь можно рассчитать эффективную жёсткость системы из трёх пружин, одна из которых последовательно соединяется с парой других, соединёных параллельно:
> getFrac . getDual $ 600 (200 300)450.0

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

Свободная алгебра

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

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

Инволюция или инверсия для элемента цепи не имеет определённого смысла, но для корректности и общности мы включили её в описание типа.

Самый первый и естественный гомоморфизм — это преобразование типа Circuit в произвольный тип, для которого определена алгебра де Моргана:

reduce :: DeMorgan a => Circuit a -> areduce circ = case circ of Zero -> zero One -> one Elem b -> b Inv a -> inv (reduce a) Par a b -> reduce a reduce b Seq a b -> reduce a reduce b

Функция reduce подобна функции fold, которая сворачивает список моноидов в произвольный моноид. Таким же образом, как от функции fold для функторов можно произвести функцию foldMap, можно образовать функцию reduceMap:

reduceMap :: DeMorgan b => (a -> b) -> Circuit a -> breduceMap = reduce . fmap f

Эта функция позволяет явно указать какую именно алгебру де Моргана следует использовать при интерпретации цепи.

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

Различные задачи расчёта цепей

Для построения цепей организуем предметно-ориентированный тип Lumped, который позволит нам кроме значений параметров элементов цепи Value a, явно представить короткое замыкание Short и разрыв цепи Break:

data Lumped a = Short | Value a | Break deriving (Show, Functor) instance DeMorgan s => DeMorgan (Lumped s) where zero = Break Value r1 Value r2 = Value $ r1 r2 Short r = r r Short = r _ Break = Break Break _ = Break inv Short = Break inv Break = Short inv (Value r) = Value (inv r)

Введём тип для элементов: сопротивлений, ёмкостей и индуктивностей, а также конструкторы элементов цепи:

data Element = R Double | C Double | L Double deriving Show res = Elem . Rcap = Elem . Ccoil = Elem . Lkey True = Zerokey False = One

Наконец, напишем простенькую цепь для опытов.

s :: Bool -> Circuit Elements k = res 10 ((res 2 coil 5e-3 key k) cap 10e-9)

Теперь мы готовы строить различные интерпретации нашей свободной алгебры.

Функция connect определяет является ли цепь замкнутой, используя булеву алгебру:

connected :: Circuit Element -> Boolconnected = reduceMap f where f el = case el of R _ -> True C _ -> False L _ -> True
> connected (s True)True> connected (s False)False

Функция resistance определяет эффективное сопротивление цепи для постоянного тока, используя алгебру для дробных чисел:

resistance :: Circuit Element -> Lumped Doubleresistance = fmap getFrac . reduceMap (fmap Frac . f) where f el = case el of R r -> Value r C _ -> Break L _ -> Short
Здесь вычислительная работа производится внутри типа Lumped, Который мы объявили функтором.
> resistance (s True)Value 12> resistance (s False)Break

Для расчёта импеданса цепи потребуетcя подключить модуль Data.Complex:

impedance :: Double -> Circuit Element -> Lumped (Complex Double)impedance w = fmap getFrac . reduceMap (fmap Frac . f) where f el = Value $ case el of R r -> r :+ 0 C c -> 1 / (0 :+ w*c) L l -> 0 :+ w*l
> impedance 1e3 (s False)Value (10.0 :+ (-99999.99999999997))> impedance 1e3 (s True)Value (12.00020001420084 :+ 5.0002100065000405)> impedance 1e6 (s False)Value (10.0 :+ (-100.0))> impedance 1e6 (s True)Value (10.000832986116954 :+ (-102.04081598653629))

Если речь идёт о расчёте батареи конденсаторов, то нужно поменять алгебру на дуальную:

capacity :: Circuit Element -> Lumped Doublecapacity = fmap (getFrac . getDual) . reduceMap (fmap (Dual . Frac) . f) where f el = case el of R _ -> Short C c -> Value c L _ -> Short

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

А если нам нужно будет изобразить цепь, то можно воспользоваться великолепной библиотекой Diagrams для построения векторной графики. Она предоставляет два комбинатора для относительного расположения изображений: (|||) — рядом по горизонтали и (===) — рядом по вертикали.

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

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

Заключение

Мы не рассмотрели всех возможностей, которые даёт использование абстракции для алгебры де Моргана. Можно было привести пример расчёта теплоизоляции здания с окнами и сложным покрытием стен; или моделирование неньютоновских жидкостей цепями из элементов жёсткости и вязкости.

Для моноидов и алгебры де Моргана выполняется ряд простых теорем, например, известно, что произведение типов-моноидов тоже образует моноид. Эвивалентное утверждение верно для алгебр де Моргана, оно даёт возможность за один проход по структуре вычислять сразу несколько характеристик.

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

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

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

Эту процедуру можно выполнить во время выполнения программы, то есть с произвольными данными, но перед интенсивными вычислениями.

На что способны свободные структуры показывает Wolfram Mathematica, в которой все выражения, по существу, представляют собой свободные алгебры.

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

Но эти ограничения дают новые возможности — можно существенно снизить трение, увеличить скорость и построить сложную и эффективную автоматическую систему управления движением сотен составов. На автомагистрали нельзя ездить на мопеде или на тракторе. Это ограничение.

Но если мы гарантируем его, то можем рассчитывать на высокие скорости и высокую пропускную способность трассы.

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

Это может раздражать, но вместе с этими ограничениями и законами приходят гарантии, что код будет работать именно так, а не иначе.

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

Закон общей инверсии де моргана

Следовательно, результат логического сложения высказывания и его отрицания всегда принимает значение “истина”. 3. Закон непротиворечия X/\ ¬X = 0 Высказывание не может быть одновременно истинным и ложным. Если высказывание Х истинно, то его отрицание НЕ Х должно быть ложным.

6. Сочетательный (ассоциативный) закон (X \/Y) \/Z = X \/ (Y \/Z) (X/\Y)/\Z=X/\(Y/\Z) При одинаковых знаках скобки можно ставить произвольно или вообще опускать. 5. Распределительный (дистрибутивный) закон

Logika / 12. Законы де Моргана, Скота, Клавия

Закон можно передать так: ложное высказывание влечет любое высказывание.

Напр.:

«Если дважды два не равно четырем, то, если дважды два четыре, вся математика ничего не значит»

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

Напр.:

«Если снег бел и вместе с тем не бел, трава бывает только черной»

. С использованием символики логической (р, q — некоторые высказывания; ~ — отрицание, «неверно, что»; —> импликация, «если, то») 3. Д. С. выражается формулой: ~p->(p->q), если неверно, что p, то если р, то q; или эквивалентной ей в классической логике формулой: (p/\~p)->q, если р и не-р, то q.

_02Л_Законы АЛ

Закон де Моргана.

Законы де Моргана доказаны. 5. Законы повторения — для дизъюнкции.

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

6. Закон двойного отрицания Двойное отрицание логической переменной равно самой логической перемененной.

Законы де Моргана

{\displaystyle {\begin{matrix}(A\cap B){C}=A{C}\cup B{C},\\(A\cup B){C}=A{C}\cap B{C}.

\end{matrix}}} Эти правила также действительны для множества элементов (семейств): ⋂ i ∈ I A i ¯ = ⋃ i ∈ I A i ¯ {\displaystyle {\overline {\bigcap _{i\in I}A_{i}}}=\bigcup _{i\in I}{\overline {A_{i}}}} 00000 и 00000 ⋃ i ∈ I A i ¯ = ⋂ i ∈ I A i ¯ {\displaystyle {\overline {\bigcup _{i\in I}A_{i}}}=\bigcap _{i\in I}{\overline {A_{i}}}} .

В исчислении предикатов: ¬ ∀ x P ( x ) ≡ ∃ x ¬ P ( x ) , {\displaystyle eg \forall x\,P(x)\equiv \exists x\,eg P(x),} ¬ ∃ x P ( x ) ≡ ∀ x ¬ P ( x ) . {\displaystyle eg \exists x\,P(x)\equiv \forall x\,eg P(x).

} Следствия: Используя законы Де Моргана можно выразить конъюнкцию через дизъюнкцию и три отрицания.

Аналогично можно выразить дизъюнкцию: a ∧ b = ¬ ( ¬ a ∨ ¬ b ) {\displaystyle a\wedge b=eg (eg {a}\vee eg {b})} a ∨ b = ¬ ( ¬ a ∧ ¬ b ) {\displaystyle a\vee b=eg (eg {a}\wedge eg {b})}

Теоремы поглощения, склеивания и де Моргана

Найдем инверсию выражения АВ + CD,представленного в виде дизъюнкции конъюнкций.

Введем обозначения: АВ = Х; CD = Y, тогда Найдем

и подставим в выражение (22): Таким образом: Рассмотрим выражение, представленное в конъюнктивной форме: (А + В)(С + D) Найдем его инверсию в виде Введем обозначения: А + В = X; С + D =Y,тогда Найдем

и подставим их в выражение (23): Таким образом: При инвертировании сложных выражений можно пользоваться следующим правилом.

functio — исполнение, соответствие, отображение)

Закон инверсии (закон де Моргана)

Значение логической функции на выходе цепи

определяют по индикатору логических уровней.

Переключатель индикатора логических уровней устанавливают в положение «ТТЛ 5 В». Входы неиспользуемых элементов подключают к шинам питания 0 или +5 В.

Перечень аппаратуры Обозначение Наименование Тип Параметры G1 Однофазный источник питания 218 ~ 220 В / 16 А А1 Блок испытания цифровых устройств 219 Индикаторы и источники логических сигналов.

Питание +5 В, 1 А Набор миниблоков 600.11 24 миниблока Указания по проведению эксперимента Убедитесь, что устройства, используемые в эксперименте, отключены от сети электропитания.

Соедините аппаратуру в соответствии со схемой электропитания.

Соберите исследуемую логическую цепь на наборном поле блока испытания цифровых устройств А1.

Тема : Преобразование логических выражений.
Формулы де Моргана

исходное выражение истинно только тогда, когда

, то есть только при

(в таблице истинности одна единица, остальные – нули) выражение истинно, если хотя бы одна из переменных равна нулю, то есть, оно будет ложно только при

(в таблице истинности один нуль, остальные – единицы) аналогично выражение ложно только при

, а в остальных случаях – истинно выражение истинно только при

, а в остальных случаях – ложно выражение

истинно только при

, а в остальных случаях – ложно объединяя все эти результаты в таблицу, получаем:

Закон де моргана

Названы именем англ. логика XIX в. А. де Моргана. Один из этих законов можно выразить так: отрицание конъюнкции эквивалентно дизъюнкции отрицаний. Напр.:

«Неверно, что завтра будет холодно и завтра будет дождливо, тогда и только тогда, когда завтра не будет холодно или завтра не будет дождливо»

Другой закон: отрицание дизъюнкции эквивалентно конъюнкции отрицаний. Напр.:

«Неверно, что ученик знает арифметику или знает геометрию, тогда и только тогда, когда он не знает ни арифметики, ни геометрии»