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

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

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

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

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

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

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

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

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

А=А

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

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

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

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

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

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

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) Высказывание Неверно, что я выучил урок и получил по нему двойку тождественно высказыванию Или я не выучил урок, или я не получил по нему двойку.

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

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

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

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

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

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

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

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

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

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

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

Тогда

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

Примеры

Вещественные числа

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

Первый пример (умственное и письменное умножение)

Во время умственной арифметики, распределенность часто используются бессознательно:

Таким образом, для расчета 6 ⋅ 16 в вашей голове, сначала умножаем 6 · 10 и 6 · 6 и добавить промежуточные результаты. Письменное умножение также основано на распределительный закон.

Второй пример (с переменными)

Третий пример (с двумя суммами)

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

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

Матрицы

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

для всех -матрицах и -матрицах , а также

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

Другие примеры

Логика высказываний

Верховенство замены

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

а также

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

Правда функциональные связок

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

Распределение совокупности по совокупности

Распределение совместно над дизъюнкции

Распределение дизъюнкции над совместно

Распределение дизъюнкции над дизъюнкции

Распределение импликации

Распределение импликации над эквивалентности

Распределение дизъюнкции над эквивалентности

Двойное распределение

Дистрибутивность и округление

На практике, распределительное свойство умножения (и деления) над дополнением может показаться быть скомпрометировано или потеряли из — за ограничениями арифметической точности . Например, тождество ⅓ + ⅓ + ⅓ = (1 + 1 + 1) / 3 , как представляется , терпят неудачу , если добавление проводят в десятичной арифметики ; Однако, если много значащих цифр используются, то расчет приведет к более тесному приближению к правильным результатам. Например, если арифметическое вычисление принимает вид: 0,33333 + 0,33333 + 0,33333 = 0,99999 ≠ 1 , этот результат является более близким приближением , чем если бы меньше значащие цифры были использованы. Даже тогда , когда дробные числа могут быть представлены именно в арифметической форме, ошибки будут введены , если эти арифметические значения округлены или усечение. Например, покупая две книги, каждый по цене £ 14,99 до налогообложения в размере 17,5%, в двух отдельных сделок будет реально сэкономить £ 0,01, по сравнению с покупкой их вместе: £ 14,99 × 1,175 = £ 17,61 до ближайшего £ 0,01, что в общей сложности расходы £ 35,22, но £ 29,98 × 1,175 = £ 35,23 . Такие методы, как банковское округление могут помочь в некоторых случаях, как это может увеличить точность используемой, но в конечном счете , некоторые ошибки в расчетах неизбежны.

Дистрибутивность в кольцах

Дистрибутивность наиболее часто встречается в кольцах и дистрибутивных решеток .

Кольцо имеет две бинарные операции + и * (обычно), и одним из требований кольца является то , что * должна распределить выше +. Большинство видов чисел (пример 1) и матрицы (пример 4) образует кольцо. Решетка другой вид алгебраической структуры с двумя бинарными операциями, ∧ и ∨. Если какой- либо из этих операций (например ∧) распределяет над другими (∨), то ∨ должно также распространять через ∧, а решетка называется дистрибутивной. Смотрите также статью о дистрибутивности (теории порядка) .

Примеры 4 и 5 являются булевыми алгебрами , которые могут быть интерпретированы либо как особый вид кольца (а булево кольцо ) или специального вид распределительной решетки (а булева решетка ). Каждая интерпретация несет ответственность за различные дистрибутивные законы в булевой алгебре. Примеры 6 и 7 представляют собой распределительные решетки , которые не являются булевыми алгебрами.

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

Кольца и распределительные решетки являются специальными видами буровых установок , некоторые обобщениями колец. Эти цифры в примере 1 , которые не образуют кольца по меньшей мере , формы буровых установок.
Near-установки являются дальнейшим обобщением буровых установок, которые остались дистрибутивными , но не дистрибутивны справа; Пример 2 является почти вышкой.

«Дистрибутивность» перенаправляется сюда. Не следует путать с Distributivism .

Визуализация дистрибутивности для положительных чисел

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

Например, в арифметике :

2 ⋅ (1 + 3) = (2 ⋅ 1) + (2 ⋅ 3), но 2 / (1 + 3) ≠ (2/1) + (2/3).

В левой части первого уравнения, 2 умножает сумму 1 и 3; на правой стороне, он умножает 1 и 3 индивидуально, с продуктами , добавленным впоследствии. Поскольку они дают один и тот же окончательный ответ (8), умножение на 2 называется распределить над добавлением 1 и 3. Так как можно было бы поместить любые действительные числа вместо 2, 1 и 3 выше, и до сих пор получили истинное уравнение, умножение действительных чисел распределяет более того действительных чисел.

Определение

Учитывая множество S и две бинарные операторы * и + на S , операции:

* Является левым дистрибутивна над + , если для любых элементов х , у и г из S ,

* Является дистрибутивно справа над + , если для любых элементов х , у и г из S ,

а также

* Является дистрибутивной над + , если это левый и правый дистрибутивный.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *