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

§ 3. Законы алгебры логики

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

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

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

1) Законы поглощения констант

2) Законы поглощения переменных

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

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

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

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

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

Переходим к группе законов, которые практически аналогичны законам алгебры чисел.

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

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

8) Законы ассоциативности

(x & y) & z = x & (y & z),

(x`vv`y) `vv` z = x `vv` (y `vv` z);

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

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

Кроме аксиом и алгебраических свойств операций ещё существуют особые законы алгебры логики.

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

`bar(x & y)= barx vv bary` ,

11) Загоны поглощения (не путать с аксиомами поглощения переменных нулём или единицей)

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

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

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

Наше начальное выражение: x `vv` (x & y) . Выносим x за скобки и получаем следующее выражение:

x &(1 `vv` y) . Используем закон поглощения переменной константой `1` и получаем следующее выражение: x & 1. И теперь используем закон поглощения константы и получаем просто x .

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

12) Закон преобразования импликации

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

3) Дизъюнкция, строгая дизъюнкция, эквивалентность

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

Словарь по логике. — М.: Туманит, изд. центр ВЛАДОС . А.А.Ивин, А.Л.Никифоров . 1997 .

Смотреть что такое «закон дистрибутивности» в других словарях:

ДИСТРИБУТИВНОСТИ ЗАКОН — (от лат. distributus – распределенный), р а с п р е д е л и тельный закон, – закон, выражающий дистрибутивность (распределительность) одной данной логич. или математич. операции относительно др. данной операции. Примером Д. з. может служить закон … Философская энциклопедия

Распределительный закон — Дистрибутивность (от латинского distributivus «распределительный») свойство согласованности двух бинарных операций, определённых на одном и том же множестве. Говорят, что две бинарные операции + и × удовлетворяют свойству дистрибутивности, если … Википедия

Дизъюнктивная нормальная форма — (ДНФ) в булевой логике нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон… … Википедия

АЛГЕБРА — раздел элементарной математики, в котором арифметические операции производятся над числами, значения которых заранее не заданы. Преимущества алгебраических методов обусловлены использованием достаточно компактных символических систем, что внешне… … Энциклопедия Кольера

неклассические логики — НЕКЛАССИЧЕСКИЕ ЛОГИКИ широкая область логических исследований, выходящая за пределы или, наоборот, сужающая область исследований классической логики высказываний и логики предикатов. Идеи для построения Н. л. были высказаны еще до … Энциклопедия эпистемологии и философии науки

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

ДИСТРИБУТИВНОСТИ ЗАКОН

Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия . Под редакцией Ф. В. Константинова . 1960—1970 .

Смотреть что такое «ДИСТРИБУТИВНОСТИ ЗАКОН» в других словарях:

закон дистрибутивности — (от англ. distribution распределение, размещение) общее название группы логических законов сходной структуры. Эти законы позволяют распределить одну логическую связь относительно другой. Полный 3. д. конъюнкции относительно дизъюнкции с… … Словарь терминов логики

Разместительный закон — Дистрибутивность (от латинского distributivus «распределительный») свойство согласованности двух бинарных операций, определённых на одном и том же множестве. Говорят, что две бинарные операции + и × удовлетворяют свойству дистрибутивности, если … Википедия

ДИСТРИБУТИВНОСТЬ — дистрибутивности закон, распределительность, некоторой операции относительно другой свойство пары бинарных алгебраических операций, выражающееся одним из тождеств: где , символы бинарных операций, а х, у, z предметные переменные. Если в множестве … Математическая энциклопедия

АЛГЕБРА ЛОГИКИ — раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логич. значений (истинности пли ложности), и логич. операций над ними. А. л. возникла в сер. 19 в. в трудах Дж. Буля (см. [1], [2]) и развилась затем в работах Ч … Математическая энциклопедия

АЛГЕБРА ЛОГИКИ — система алгебраич. методов решения логич. задач, а также совокупность задач, решаемых такими методами. А. л. в узком смысле слова алгебраич. (табличное, матричное) построение классич. логики высказываний, в котором рассматриваются… … Философская энциклопедия

АРИФМЕТИКА — искусство вычислений, производимых с положительными действительными числами. Краткая история арифметики. С глубокой древности работа с числами подразделялась на две различные области: одна касалась непосредственно свойств чисел, другая была… … Энциклопедия Кольера

ЛОГИКА КВАНТОВОЙ МЕХАНИКИ — логика, все законы к рой применимы в рассуждениях об объектах микромира и в частности об объектах, рассматриваемых в квантовой механике (отсюда и название этой логики). Обычная классич. логика не может служить логикой рассуждений о микрообъектах … Философская энциклопедия

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

ЗАКОН ДИСТРИБУТИВНОСТИ

Найдено 2 определения термина ЗАКОН ДИСТРИБУТИВНОСТИ

ЗАКОН ДИСТРИБУТИВНОСТИ

от англ. distribution — распределение, размещение)

— общее название группы логических законов сходной структуры. Эти законы позволяют распределить одну логическую связь относительно другой.

Полный 3. д. конъюнкции относительно дизъюнкции с использованием символики логической формулируется так (р, q, r — некоторые высказывания; & — конъюнкция, «и»; v — дизъюнкция, «или»; = — эквивалентность, «если и только если»):

первое и (второе или третье), если и только если (первое и второе) или (первое и третье). Напр.: «Сегодня идет дождь и завтра ясно или послезавтра ясно в том и только в том случае, когда сегодня идет дождь и завтра ясно или сегодня идет дождь и послезавтра ясно».

Полный 3. д. дизъюнкции относительно конъюнкции:

первое или (второе и третье), если и только если (первое или второе) и (первое или третье). Напр.: «Завтра будет солнечно или послезавтра будет мороз и снег тогда и только тогда, когда завтра будет солнечно или послезавтра будет мороз и завтра будет солнечно или послезавтра будет снег».

Закон самодистрибутивности импликации (->, «если, то») дает возможность распределять импликацию по импликации:

если (если первое, то (если второе, то третье)), то (если (если первое, то второе), то (если первое, то третье)). Этот закон верен для импликации материальной, но не имеет места для целого ряда иных импликаций, вводимых в современной логике.

ДИСТРИБУТИВНОСТИ ЗАКОН

от лат. distributus – распределенный), р а с п р е д е л и -тельный закон, – закон, выражающий дистрибутивность (распределительность) одной данной логич. или математич. операции относительно др. данной операции. Примером Д. з. может служить закон обычной арифметики: а (b + с) = аb + ас, выражающий распределительность умножения относительно сложения, т.е. то, что умножение любого числа а на сумму любых чисел b и с дает тот же результат, к-рый получается, если умножение на а «распределить» между слагаемыми и затем сложить произведения аb и ас; но в обычной арифметике сложение не дистрибутивно относительно умножения. В отличие от обычной арифметики, в логике высказываний имеется пара операций, из к-рых каждая дистрибутивна относительно другой, – это конъюнкция и дизъюнкция. Д. з. для этих операций выражаются эквивалентностями: А & (В/С) экв. (А & В) / (А & С) (дистрибутивность конъюнкции относительно дизъюнкции; А, В и С – любые высказывания, & и / – знаки конъюнкции и дизъюнкции, а экв. есть сокращение для слова «эквивалентно») и A / (B & С) экв. (А / В) & (А / С) (дистрибутивность дизъюнкции относительно конъюнкции). В логике предикатов операция связывания переменной квантором общности дистрибутивна относительно конъюнкции: ? х (Ф (х) & ? (?)) экв. ? х Ф (x) & ? х ? (x) (т.е. высказывания «для всякого x справедливо свойство ? и свойство ?» и «для всякого x справедливо свойство ? и для всякого x справедливо свойство ?» эквивалентны), но не дистрибутивна относительно дизъюнкции (т. к. из высказывания «для всякого x справедливо свойство ? или свойство ?» не следует высказывание «для всякого x справедливо свойство ? или для всякого x справедливо свойство ?», хотя обратное следование и имеет место). Операция же связывания переменной квантором существования дистрибутивна относительно дизъюнкции: (т.е. высказывания «существует такое x, для к-рого верно ? или ?» и «существует такое x, для к-рого верно Ф, или существует такое x, для к-рого верно ?» эквивалентны), но не дистрибутивна относительно конъюнкции (т.к., хотя из высказывания «существует такое x, для к-рого верно ? и ?» и следует высказывание «существует такое x, для к-рого верно Ф, и существует такое x, для к-рого верно ?», но обратное следование не имеет места). Д. з., позволяющие проводить т.н. «вынос за скобки» и (при использовании соответствующего закона ассоциативности, т.е. сочетательного закона) «раскрытие скобок», играют существ. роль в преобразованиях логич. и алгебраич. выражений. С выполнением Д. з. для тех или иных операций в логич. и алгебраич. системах связаны важные свойства этих систем (см. Структура). В алгебре логики упомянутые Д. з. для конъюнкции и дизъюнкции обычно записывают не в виде эквивалентностей, а в виде равенств, т.е. более сходно с арифметическим Д. з.: A(B / C) = AB / AC и A / BC = (A / B)(A / C). Там же используется и др. Д. з.: напр., А(В+С) = АВ+АС (дистрибутивность конъюнкции относительно разделительной дизъюнкции), AV(BДИСТРИБУТИВНОСТИ ЗАКО?НC) = (AVB) ДИСТРИБУТИВНОСТИ ЗАКО?Н (AVC) (дистрибутивность дизъюнкции относительно эквиваленции), А?(В?С) = (А?В) ? (А?С) (дистрибутивность импликации относительно импликации). Последний закон называют также законом самодистрибутивности импликации [или, вернее, левой самодистрибутивности импликации, т.к. для последней соответствующий п р а в о й Д. з. (А?В)?С = (А?С) ? (B?C) не верен и, тем более, не вытекает из вышеприведенного левой Д. з. из-за некоммутативности импликации, т.е. из-за отсутствия для нее переместительного закона. «Раскрывать скобки» этот закон не позволяет из-за неассоциативности импликации, т.е. из-за отсутствия для нее сочетательного закона]. Законом самодистрибутивности импликации наз. также формула ((А?(В?С)) ? ((А?В) ? (А?С)), играющая важную роль в исчислении высказываний и принимаемая часто в качестве одной из аксиом последнего, что удобно, напр., для доказательства теоремы о дедукции; последняя при этом является следствием уже того, что в исчислении постулированы закон, выражаемый указ. формулой, и более простой закон, выражаемый формулой (А?(В?А), а также обычное правило modus ponens. Иногда рассматривают Д. з. и для таких операций, к-рые не обязательно двуместны (т.е. могут быть функциями не двух переменных, а, напр., трех или четырех). Примеры таких Д. з.: А(В ДИСТРИБУТИВНОСТИ ЗАКО?Н (C ДИСТРИБУТИВНОСТИ ЗАКО?Н D)) = A · B ДИСТРИБУТИВНОСТИ ЗАКО?Н (AC ДИСТРИБУТИВНОСТИ ЗАКО?Н AD) (дистрибутивность конъюнкции относительно трехместной эквиваленции), (А ДИСТРИБУТИВНОСТИ ЗАКО?Н (ВДИСТРИБУТИВНОСТИ ЗАКО?НС)) ? D = (A?D) ДИСТРИБУТИВНОСТИ ЗАКО?Н ((B?D) ДИСТРИБУТИВНОСТИ ЗАКО?Н (C?D)), эакон самодистрибутивности медианы и др. В общем случае такого рода Д. з. можно выразить формулой: f(А1, . Ai-1, g(B1, . Вm), ?i+1, . An) = g(f(A1, . Аi-1, В1, Ai+1, . Аn), . f(A1, . Ai-1, ?m, ?i+1, . An)) [дистрибутивность операции f по i-му аргументу (месту) относительно операции g]. Примером применения общего понятия дистрибутивности может служить след. теорема: для того чтобы функция алгебры логики была ш е ф ф е р о в о й (т.е. чтобы через нее можно было бы представить всякую другую функцию алгебры логики), необходимо и достаточно, чтобы не имела места дистрибутивность отрицания медианы относительно этой функции. Лит.: Новиков П. С., Элементы математической логики, М., 1959; Ван-дер-Варден В. Л., Современная алгебра, пер. с нем., ч. 1, М.–Л., 1947; Биркгоф Г., Теория структур, пер. с англ., М., 1952; Черч А., Введение в математическую логику, т. 1, пер. с англ., М., 1960. Б. Бирюков. Москва. А. Кузнецов. Москва.

Найдено схем по теме ЗАКОН ДИСТРИБУТИВНОСТИ — 0

Найдено научныех статей по теме ЗАКОН ДИСТРИБУТИВНОСТИ — 0

Найдено книг по теме ЗАКОН ДИСТРИБУТИВНОСТИ — 0

Найдено презентаций по теме ЗАКОН ДИСТРИБУТИВНОСТИ — 0

Найдено рефератов по теме ЗАКОН ДИСТРИБУТИВНОСТИ — 0

Узнай стоимость написания

Ищете реферат, курсовую работу, дипломную работу, контрольную работу, отчет по практике или чертеж?
Узнай стоимость!

Конституентой нуля набора Δ называется дизъюнкт K 0 1 … δп) = .

Совершенной ДНФ называется дизъюнкция некоторых конституент единицы, среди которых нет одинаковых.

Совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых.

Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная хi из набора <x1. xn> входит ровно один раз, причем входит либо сама хi, либо ее отрицание .

Пример. Формула есть конституента единицы К 1 (1,0,1).

Формула есть конституента нуля К 0 (0,0,1).

Формула СДНФ.

Формула СКНФ.

Формула не является СДНФ.

Первая теорема Шеннона

Доказательство. Прежде всего, заметим, что . Подставим произвольно вместо первых k переменных их значения: . Тогда левая часть доказываемой формулы равна Правая часть представляет собой дизъюнкцию 2 k конъюнкций вида , которые этой подстановкой разбиваются на два класса. К первому классу относится конъюнкция, у которой набор 1, δ2,. δk) совпадает с набором :

=

= 1 1 . 1 =

Эта конъюнкция равна левой части формулы. Ко второму классу относится 2 k -1 конъюнкций, у каждой из которых хотя бы в одной переменной xi, выполнено условие. Следовательно, каждая из них равна нулю. Используя закон , получаем, что левая и правая части формул равны при любой подстановке переменныхx1, x2. xn.

Вторая теорема Шеннона

В силу принципа двойственности для булевых алгебр справедлива

Приведенные формулы позволяют сформулировать следующую теорему о функциональной полноте.

Теорема (о функциональной полноте). Для любой булевой функции f найдется формула φ, представляющая функцию f. Если f 0, то существует представляющая ее формула φ, находящаяся в СДНФ:

и такое представление единственно с точностью до порядка следования конституент единицы. Если f 1, то существует приставляющая ее формула φ, находящаяся в СКНФ:

,

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

Найти СДНФ и СКНФ функции f(x,y,z), заданной следующей таблицей истинности:

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

При совпадении слагаемых или сомножителей получаем n-кратное na или n-ю степень a n элемента a. При этом степень a n определена вообще лишь для натурального n, так как ее определение для требовало существование единицы и обратного элемента a -1 , что в кольце может не выполняться. Свойства степени (3) — (5) сохраняются также лишь для натуральных показателей. В отличие от этого понятие n-кратного na элемента a и его свойства (6) — (8) остаются верными в случае кольца (как группы по сложению) для любых целых чисел.

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

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

Прежде всего из VI и IV следует, очевидно, вторая форма закона дистрибутивности:

Далее, обе формы закона дистрибутивности оказываются верными также и для разности, т. е.

Для доказательства первого равенства надо проверить, что элемент (ab)c удовлетворяет определению разности элементов ac и bc. Но действительно

Закрыть меню