Алгебра логики

раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности), и логические операции над ними. А. л. возникла в середине 19 в. в трудах Дж. Буля (См. Буль) и развивалась затем в работах Ч. Пирса, П. С. Порецкого (См. Порецкий), Б. Рассела, Д. Гильберта и др. Создание А. л. представляло собой попытку решать традиционные логические задачи алгебраическими методами. С появлением теории множеств (70-е гг. 19 в.), поглотившей часть первоначального предмета А. л., и дальнейшим развитием математической логики (последняя четверть 19 в. — 1-я половина 20 в.) предмет А. л. значительно изменился. Основным предметом А. л. стали высказывания (См. Высказывание). Под высказыванием понимается каждое предложение, относительно которого имеет смысл утверждать, истинно оно или ложно. Примеры высказываний: «кит — животное», «все углы — прямые» и т. п. Первое из этих высказываний является, очевидно, истинным, а второе — ложным. Употребляемые в обычной речи логические связки «и», «или», «если..., то...», «эквивалентно», частица «не» и т. д. позволяют из уже заданных высказываний строить новые, более «сложные» высказывания. Так, из высказываний «х > 2», «х ≤ 3» при помощи связки «и» можно получить высказывание «x>2 и х ≤ 3», при помощи связки «или» — высказывание «x>2 или х ≤ 3», при помощи связки «если..., то...» — высказывание «если x > 2, то х ≤ 3» и т. д. Истинность или ложность получаемых таким образом высказываний зависит от истинности и ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями.

Связки. Формулы. В А. л. для обозначения истинности вводится символ и для обозначения ложности — символ Л. Часто вместо этих символов употребляются числа 1 и 0. Связки «и», «или», «если..., то...», «эквивалентно» обозначаются соответственно знаками & (конъюнкция), ∨ (дизъюнкция), → (импликация), Алгебра логики (эквивалентность); для отрицания вводится знак ^- (чёрточка сверху). Наряду с индивидуальными высказываниями, примеры которых приводились выше, в А. л. используются также т. н. переменные высказывания, т. е. такие переменные, значениями которых могут быть любые наперёд заданные индивидуальные высказывания. Далее индуктивно вводится понятие формулы, являющееся формализацией понятия «сложного» высказывания; через А, В, С,... обозначаются индивидуальные, а через X, Y, Z ,... — переменные высказывания. Каждая из этих букв называются формулой. Если знаком * обозначить любую из перечисленных выше связок, а ℑ и ℜ суть формулы, то (ℑ* ℜ) и

Связки и частица «не» рассматриваются в А. л. как операции над величинами, принимающими значения 0 и 1, и результатом применения этих операций также являются числа 0 или 1. Конъюнкция X&Y равна 1 тогда и только тогда (т. и т. т.), когда и Х и Yравны 1; дизъюнкция X∨Y равна 0 т. и т. т., когда и Х и Y равны 0; импликация Х→Y равна 0 т. и т. т., когда Х равно 1, а Y равно 0; эквивалентность ХАлгебра логикиУ равна 1 т. и т. т., когда значения Х и Y совпадают; отрицание X̅ равно 1 т. и т. т., когда Х равно 0. Введённые операции позволяют каждой формуле при заданных значениях входящих в неё высказываний приписать одно из двух значений 0 или 1. Тем самым каждая формула может одновременно рассматриваться как некоторый способ задания или реализации т. н. функций А. л., т. е. таких функций, на наборах нулей и в качестве значений 0 или 1. Для задания функций А. л. иногда используются таблицы, содержащие все наборы значений переменных и значения функций на этих наборах. Так, например, сводная таблица, задающая функции `X̅, X&Y, X∨Y, X→Y и XАлгебра логикиY имеет вид:

----------------------------------------------------------------------------------

| XY     | X̅       | X&Y     | X/Y     | X→У       | ХАлгебра логикиY      |

|---------------------------------------------------------------------------------|

| 00      | 1        | 0          | 0   | 1     | 1    |

|---------------------------------------------------------------------------------|

| 01      | 1        | 0          | 1   | 1     | 0    |

|---------------------------------------------------------------------------------|

| 10      | 0        | 0          | 1   | 0     | 0    |

|---------------------------------------------------------------------------------|

| 11      | 0        | 1          | 1   | 1     | 1    |

----------------------------------------------------------------------------------

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

Для преобразований формул в равные формулы важную роль в А. л. играют следующие равенства:

(1) X&Y = Y&X, X∨Y = Y∨X (закон коммутативности);

(2) (X&Y)&Z = X&(Y&Z), (X∨Y)∨Z = X∨(Y∨Z) (закон ассоциативности);

(3) X&(X∨Y) = X, X∨ (Х&У) = X (закон поглощения);

(4) X& (Y∨Z) = (X&Y)∨(X&Z) (закон дистрибутивности);

(5) X&X̅= 0 (закон противоречия);

(6) X∨X̅= 1 (закон исключенного третьего);

(7) Х→Y ==X̅∨Y, ХАлгебра логикиY = (X&Y)∨(X̅&Y̅).

Эти равенства, устанавливаемые, например, с помощью истинностных таблиц, позволяют уже без помощи таблиц получать др. равенства. Методом получения последних являются т. н. тождественные преобразования, которые меняют, вообще говоря, выражение, но не функцию, реализуемую этим выражением. Например, при помощи законов поглощения получается закон идемпотентности Х∨Х = X. Упомянутые равенства в ряде случаев позволяют существенно упростить запись формул освобождением от «лишних скобок». Так, соотношения (1) и (2) дают возможность вместо формул (...(ℑ₁&ℑ₂)&...)& ℑ_s и (...(ℜ₁∨ℜ₂)∨...)∨ ℜ_s использовать более компактную запись ℑ₁&ℑ₂&...&ℑ_s и ℜ₁∨ℜ₂∨...ℜ_s Первое из этих выражений называется конъюнкцией сомножителей ℑ₁,..., ℑ_s, а второе — дизъюнкцией слагаемых ℜ₁,..., ℜ_s. Равенства (5), (6), (7) показывают также, что константы 0 и 1, импликацию и эквивалентность, рассматривая их как функции, можно выразить через конъюнкцию, дизъюнкцию и отрицание. Более того, всякая функция А. л. может быть реализована формулой, записываемой с помощью символов

Нормальные формы. Множество всех формул, в построении которых участвуют переменные высказывания, некоторые из символов &, ∨,→, Алгебра логики , ^- и констант 0 и 1, называются языком над данными символами и константами. Равенства (1) — (7) показывают, что для всякой формулы в языке над &, ∨,→, Алгебра логики , ^-,0, 1 найдётся равная ей формула в языке над &, ∨,^-,0, 1, например

Особую роль в последнем языке играет класс формул, которые могут быть записаны в виде ℑ₁∨ℑ₂∨...∨ℑ_s, 0 или 1, где s≥1,и каждое ℑ_i — либо переменное высказывание, либо его отрицание, либо конъюнкция таковых, при этом каждое ℑ_i не содержит одинаковых сомножителей и не содержит сомножителей вида Х и X̅ одновременно и все ℑ_i — попарно различны. Здесь скобки опускаются, т. к. предполагается, что операция конъюнкции связывает «сильнее», чем дизъюнкция, т. е. при вычислении по заданным значениям переменных следует сначала вычислить значения ℑ_i .Эти выражения называются дизъюнктивными нормальными формами (днф). Каждую формулу ℑ, реализующую функцию, отличную от константы, в языке над &, ∨, →, Алгебра логики , ^- , 0, 1 при помощи равенств (1) — (7) можно привести к равной ей днф, содержащей все переменные формулы ℑ и любое число других переменных, причем каждое ℑ в этой днф содержит одни и те же переменные. Такая днф называется совершенной днф формулы ℑ. Возможность приведения к совершенной днф лежит в основе алгоритма, устанавливающего равенство или неравенство двух наперёд заданных формул.

Важную роль в А. л. и её приложениях играет т. н. сокращённая днф. Днф называется сокращённой, если выполнены следующие условия: 1) в ней нет таких пар слагаемых ℑ_i и ℑ_j, что всякий сомножитель из ℑ_i имеется и в ℑ_I; 2) для всяких двух таких слагаемых ℑ_i и ℑ_i ,из которых один содержит сомножителем некоторое переменное, а другой — отрицание этого переменного (при условии, что в данной паре слагаемых нет другого переменного, для которого это же имеет место), имеется (в этой же днф) слагаемое ℑ_i, равное конъюнкции остальных сомножителей этих двух слагаемых. Всякая днф при помощи равенства (1) — (7) может быть приведена к равной ей сокращённой днф. Например, сокращённой днф для формулы ((X Алгебра логики (Y→Z)) → (X&Z)) является

Кроме днф, употребляются также конъюнктивные нормальные формы (кнф). Так называют выражения, которые можно получить из днф путём замены в них знаков ∨ на &, а & на ∨. Например, из днф

получается кнф

Операция (или функция) f называется двойственной для операции ψ, если таблица, задающая f получается из таблицы, задающей ψ, путём замены в ней всюду 0 на 1 и 1 на 0 (включая замену значений функций). Например, конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константы 1 и 0 двойственны друг другу и т. д. Преобразованием формул, при котором знаки всех операций в выражении заменяются на знаки двойственных им операций, константа 0 заменяется на 1, а 1 — на 0, называются преобразованием двойственности. Если верно равенство ℑ = ℜ и ℑ* двойственно ℑ, а ℜ* двойственно ℜ, то верно ℑ* = ℜ*, называемое двойственным предыдущему. Это т. н. принцип двойственности. Примерами двойственных равенств являются пары законов (1), (2), (3); равенство (5) двойственно равенству (6), каждая кнф двойственна некоторой днф. Совершенная кнф и сокращённая кнф определяются как такие кнф, что двойственные им выражения являются соответственно совершенной днф и сокращённой днф.

Следствия. Гипотезы. Минимизация. Совершенные и сокращённые днф и кнф используются для решения задачи обзора всех гипотез и всех следствий заданной формулы. Под гипотезой формулы ℑ понимается такая формула ℜ, что (ℜ→ℑ) = 1, а под следствием формулы ℑ — такая формула ℜ, что (ℑ→ℜ) = 1. Гипотеза формулы ℑ называется простой, если она есть конъюнкция переменных или их отрицаний и после отбрасывания любого из её сомножителей перестаёт быть гипотезой формулы ℑ. Аналогично, следствие формулы называется простым, если оно есть дизъюнкция переменных или их отрицаний и после отбрасывания любого из её слагаемых перестаёт быть следствием формулы ℑ. Решение задачи обзора гипотез и следствий основано на указании алгоритма, строящего все простые гипотезы и следствия для заданной формулы и в получении из них при помощи законов (2) — (7) всех остальных гипотез и следствий.

Сокращённая днф имеет важные приложения. Следует отметить прежде всего задачу минимизации функций А. л., являющуюся частью т. н. задачи синтеза управляющих систем. Минимизация функций А. л. состоит в построении такой днф для заданной функции А. л., которая реализует эту функцию и имеет наименьшее суммарное число сомножителей в своих слагаемых, т. е. имеет минимальную «сложность». Такие днф называются минимальными. Каждая минимальная днф для заданной отличной от константы функции А. л. получается из сокращённой днф любой формулы, реализующей эту функцию, выбрасыванием некоторых слагаемых ℑ_i, из этой сокращённой днф.

Языки. Интерпретации. В языке над &, ∨, →, Алгебра логики, 0, 1, + , где знак + интерпретируется как сложение по модулю два, устанавливаются следующие соотношения:

Эти равенства позволяют переводить формулы в языке над &, ∨, →, Алгебра логики, ^-, 0, 1 в равные им формулы в языке над &,+, 1 и обратно. Тождественные преобразования в последнем языке осуществляются при помощи равенств, установленных для конъюнкции и дополнительных:

(11) Х +Y=Y+ X;

(12) (Х+Y) + Z = Х+(Y + Z);

(13) Х&(Y + Z) = X&Y + X&Z;

(14) Х&Х = Х, X + (Y + Y) = X, X&1 = X,

здесь по-прежнему считается, что конъюнкция связывает «сильнее», чем знак +. Этих равенств достаточно для того, чтобы из них при помощи тождественных преобразований, так же как и при рассмотрении языка над &, ∨, →, Алгебра логики, ^-, 0, 1, можно было вывести любое верное равенство в языке над &, +, 1. Выражение в этом языке называется приведённым полиномом (п.п.), если оно либо имеет вид ℑ₁+ℑ₂+ ... ℑ_s, где каждое ℑ_i есть или 1, или переменное, или конъюнкция различных переменных без отрицаний, ℑ_i≠ℑ_j при i≠j и s≥1, либо равно 1 + 1. Например, выражение X&Y&Z + X&Y+1 является п. п. Всякую формулу А. л. можно привести к п. п.

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

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

Рассматривая тот или иной из упомянутых выше языков вместе с некоторой п. с. р. этого языка, иногда отвлекаются от табличного задания операций, лежащих в основе этого языка, и от того, что значениями его переменных являются высказывания. Вместо этого допускаются различные интерпретации языка, состоящие из той или иной совокупности объектов (служащих значениями переменных) и системы операций над объектами этого множества, удовлетворяющих равенствам из п. с. р. этого языка. Так, язык над &, ∨, ^-, 0, 1 в результате такого шага превращается в язык т. н. булевой алгебры, язык над &, +, 1 превращается в язык т. н. булевого кольца (с единицей), язык над &, ∨ в язык дистрибутивной структуры и т. п.

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

Лит.: Гильберт Д. и Аккерман Б., Основы теоретической логики, пер. с нем., М., 1947; Тарский А., Введение в логику и методологию дедуктивных наук, пер. с англ., М., 1948; Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; Новиков П. С., Элементы математической логики, М., 1959.

В. Б. Кудрявцев.

АЛГЕБРА ЛОГИКИ - система алгебраических методов решения логических задач и совокупность таких задач; в узком смысле - табличное, матричное построение логики высказываний, определяющее логические операции над ними.

algebra of logic

algebra of logic

АЛГЕБРА ЛОГИКИ

система алгебраич. методов решения логич. задач, а также совокупность задач, решаемых такими методами. А. л. в узком смысле слова — алгебраич. (табличное, матричное) построение классич. логики высказываний, в котором рассматриваются логические операции над высказываниями, каждое из которых имеет одно из двух значений истинности: «истина» (сокр. «и» или 1) и «ложь» («л» или 0). Элементами А. л. служат переменные, принимающие одно из этих двух значений, а также константы 1 и 0. Предмет А. л. составляет совокупность свойств логич. операций в этой двузначной алгебре, а также вытекающие из этих свойств правила преобразования и упрощения формул А. л. (интерпретируемых как высказывания) и приведения их к некоторым стандартным формам, пригодным для алгоритмизации (см. Алгоритм) решения логич. задач. А. л. в широком смысле включает распространение методов А. л. на понятия и задачи многозначной логики: вместо теории двузначных арифметич. функций от двух аргументов в n-значной логике рассматриваются nзначные функции от аргументов О, 1,..., n — 1, причём часть из этих значений, подобно истинному значению 1 в двузначной А. л., считается «выделенными», т. е. соответствующими «истине». Термин «А. л.», идущий от традиций первых работ по математич. логике 19 в. (Дж. Буль, У. С. Джевонс, Э. Шредер, П. С. Порецкий и др.), применяют иногда также в другом, расширит, смысле к алгебраич. задачам и методам логики предикатов, составляющим предмет теории моделей.

Гильберт Д., Аккерман В., Основы теоретич. логики, пер. с нем., М.,1947; Клини С. К., Математич. логика, пер. с англ., М., 1973.

а́лгебра ло́гики

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

* * *

А́ЛГЕБРА ЛО́ГИКИ, система алгебраических методов решения логических задач и совокупность таких задач; в узком смысле — табличное, матричное построение логики высказываний, определяющее логические операции над ними.

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

А. л. возникла в сер. 19 в. в трудах Дж. Буля (см. [1], [2]) и развилась затем в работах Ч. Пирса (С. S. Реirs), П. С. Порецкого, Б. Рассела (В. Russel), Д. Гильберта (D. Hilbert) и др. Создание А. л. представляло собой попытку решать традиционные логич. задачи алгебраич. методами. С появлением теории множеств (70-е гг. 19 в.) основным предметом А. л. стали высказывания и логич. операции над ними. Под высказываниями понимаются предложения, относительно к-рых имеет смысл утверждать, истинны они или ложны; напр., высказывание "кит - животное" истинно, в то время как высказывание "все углы - прямые" ложно. Употребляемые в обычной речи логич. связки "и", "или", "если..., то", "эквивалентно", частица "не" и т. д. позволяют из уже заданных высказываний строить новые, более "сложные" высказывания. Так, из высказываний при помощи связки "и" можно получить высказывание при помощи связки "или" - высказывание и т. д.

Истинность или ложность получаемых таким образом высказываний зависит от истинности или ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями. Для обозначения истинности вводится символ "И" и для обозначения ложности -символ "Л". Затем вместо этих символов стали употреблять числа 1 и 0. Связки "и", "или", "если..., то", "эквивалентно" обозначаются соответственно знаками (конъюнкция), (дизъюнкция), (импликация), (эквивалентность); для отрицания вводится знак - (черточка сверху). Наряду с индивидуальными высказываниями, примеры к-рых приводились выше, стали использоваться также переменные высказывания, т. е. такие переменные, значениями к-рых могут быть любые наперед заданные индивидуальные высказывания. Далее индуктивно вводится понятие формулы, являющееся формализацией понятия сложного высказывания. Пусть А, В, С,... обозначают индивидуальные, а - переменные высказывания. Каждая из этих букв наз. формулой. Если знак * обозначает любую из перечисленных выше связок, а суть формулы, то суть формулы, напр. Связки и частица "не" стали рассматриваться как операции над величинами, принимающими значения 0 и 1, и результатом применения этих операций также являются числа 0 и 1. Конъюнкция равна 1 тогда и только тогда, когда и х, и уравны 1; дизъюнкция равна 0 тогда и только тогда, когда и х, и уравны 0; импликация равна 0 тогда и только тогда, когда хравен 1, а уравен 0; эквивалентность равна 1 тогда и только тогда, когда значения хи усовпадают; отрицание равно 1 тогда и только тогда, когда хравен 0. Введенные операции позволяют каждой формуле при заданных значениях входящих в нее высказываний приписать одно из двух значений 0 или 1. Тем самым каждая формула может одновременно рассматриваться как нек-рый способ задания, или реализации, функций А. л., т. е. таких функций, к-рые определены на наборах из нулей и единиц и к-рые в качестве значений принимают также 0 или 1. При этом формулы наз. равными (обозначение ), если они реализуют равные функции. Объектом изучения А. л. стали функции А. л. и различные операции над ними. В последующем класс функций А. л. был расширен до класса функций, аргументы к-рых и сами функции принимают в качестве значений элементы фиксированного конечного множества Е;расширился также запас операций над функциями. Иногда под А. л. понимается как раз последняя концепция. Для приложений, однако, наибольшее значение имеет все-таки тот случай, когда мощность указанного множества Еравна двум, поэтому он будет рассмотрен особенно подробно. Излагаемые здесь результаты также тесно связаны с другим подходом в изучении высказываний - так наз. высказываний исчислением.

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

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

(закон коммутативности),

(закон ассоциативности),

(закон поглощения),

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

(закон противоречия),

(закон исключенного третьего),

Эти равенства позволяют уже без помощи таблиц получать другие равенства. Методом получения последних являются так наз. тождественные преобразования, к-рые меняют, вообще говоря, выражение, но не функцию, реализуемую этим выражением. Напр., при помощи законов поглощения получается закон идемпотентности Упомянутые равенства в ряде случаев позволяют существенно упростить запись формул освобождением от "лишних скобок". Так, соотношения (1) и (2) дают возможность вместо формул и использовать более компактную запись

Первое из этих соотношений наз. конъюнкцией сомножителей а второе - дизъюнкцией слагаемых Равенства (5), (6), (7) показывают также, что константы 0 и 1, импликацию и эквивалентность, рассматривая их как функции, можно выразить через конъюнкцию, дизъюнкцию и отрицание. Более того, всякая функция А. л. может быть реализована формулой, записываемой с помощью символов

Множество всех формул, в построении к-рых участвуют переменные высказывания и нек-рые из символов и констант 0 и 1, наз. языком над данными символами и константами. Равенства (1)- (7) показывают, что для всякой формулы в языке над найдется равная ей формула в языке над напр.:

Особую роль в последнем языке играет класс формул, к-рые могут быть записаны в виде 0 или 1, где и каждое - либо переменное высказывание, либо его отрицание, либо конъюнкция таковых, при этом каждое не содержит одинаковых сомножителей и не содержит сомножителей вида одновременно и все попарно не равны. Здесь скобки опускаются, т. к. предполагается, что операция конъюнкции связывает "сильнее", чем дизъюнкция, т. е. при вычислении по заданным значениям переменных следует сначала вычислять значения Эти выражения наз. дизъюнктивными нормальными формами (д. н. ф.). Каждую формулу ив языке над реализующую функцию А. л., отличную от 0, при помощи равенств (1) - (7), можно привести к равной ей д. н. ф., содержащей все переменные формулы и и любое число других переменных, причем каждое в этой д. н. ф. содержит одни и те же переменные. Такая д. н. ф. наз. севершенной д. н. ф. формулы и;для. 0 совершенной д. н. ф. является сама формула 0. Возможность приведения к совершенной д. н. ф. лежит в основе алгоритма, устанавливающего равенство или неравенство двух наперед заданных формул. Алгоритм этот состоит в следующем: приводят исследуемые формулы и ₁ и и ₂ к совершенным д. н. ф., содержащим все те переменные, к-рые есть как в так и в и смотрят, совпадают полученные выражения или нет; если совпадают, то если нет, то Важную роль в А. л. и ее приложениях играет сокращенная д. н. ф., т. е. такая, для к-рой выполнены следующие условия: 1) в ней нет таких пар слагаемых что всякий сомножитель из имеется и в ; 2.) для всяких двух слагаемых из к-рых одно содержит сомножителем нек-рое переменное, а другое - отрицание этого переменного (при условии, что другого переменного, для к-рого это же имеет место, в данной паре слагаемых нет), имеется (в этой же д. н. ф.) слагаемое равное конъюнкции остальных сомножителей этих двух слагаемых. Всякая д. н. ф. при помощи равенств (1) - (7) может быть приведена к равной ей сокращенной д. н. ф. Напр., сокращенной д. н. ф. для формулы является Формулы равны тогда и только тогда, когда их сокращенные д. н. ф. совпадают. Кроме д. н. ф., употребляются также конъюнктивные нормальные формы (к. н. ф.), т. е. выражения, к-рые можно получить из д. н. ф. путем замены в них знаков а на 1. Напр., из д. н. ф. получается к. н. ф. Операция (или функция) f наз. двойственной для операции если таблица, задающая f, получается из таблицы, задающей путем замены в ней всюду 0 на 1 и 1 на 0 (включая замену значений функций). Напр., конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константы 1 и 0 двойственны друг другу и т. д. Преобразование формул, при к-ром знаки всех операций в выражении заменяются на знаки двойственных им операций, константа 0 заменяется на 1, а 1 на 0, наз. преобразованием двойственности. Если верно равенство двойственно двойственно то верно равенство наз. двойственным предыдущему; это - так. наз. принцип двойственности. Примерами двойственных равенств являются пары законов (1), (2), (3); равенство (5) двойственно равенству (6), каждая к. н. ф. двойственна нек-рой д. н. ф. Совершенная к. н. ф. и сокращенная к. в. ф. определяются как такие к. н. ф., что двойственные им выражения являются соответственно совершенной д. н. ф. и сокращенной д. н. ф. Совершенные и сокращенные д. н. ф. и к. н. ф. используются для решения задачи обзора всех гипотез и всех следствий заданной формулы. Под гипотезой формулы понимается такая формула а под следствием формулы - такая формула

Гипотеза формулы наз. простой, если она есть конъюнкция переменных или их отрицаний и после отбрасывания любого из ее сомножителей перестает быть гипотезой формулы Аналогично следствие формулы наз. простым, если оно есть дизъюнкция переменных или их отрицаний и после отбрасывания любого из ее слагаемых перестает быть следствием формулы Решение задачи обзора гипотез и следствий основано на указании алгоритма, строящего все простые гипотезы и следствия для заданной формулы, и на получении из них при помощи законов (2) - (7) всех остальных гипотез и следствий. Алгоритм опирается па следующие факты. Если имеют одни и те же гипотезы и следствия, соответственно. Слагаемое д. н. ф. является гипотезой этой д. н. ф., сомножитель к. н. ф.- следствием этой к. н. ф. Если - гипотеза выражения есть тоже гипотеза для если - следствие выражения то есть тоже следствие из Если - гипотезы выражения - тоже гипотеза для если - следствия из - тоже следствие из У совершенной д. н. ф. нет других гипотез (не содержащих букв, не входящих в эту д. н. ф.), кроме дизъюнкций нек-рых ее слагаемых или д. н. ф., равных им. У совершенной к. н. ф. нет других следствий, кроме конъюнкций нек-рых ее сомножителей или равных им выражений. Сокращенная д. н. ф. есть дизъюнкция всех своих простых гипотез; сокращенная к. н. ф. есть конъюнкция всех своих простых следствий. Сокращенная д. н. ф. имеет важные приложения. Прежде всего следует отметить задачу минимизации функций А. л., являющуюся частью задачи синтеза управляющих систем. Минимизация функций А. л. состоит в построении такой д. н. ф. для заданной функций А. л., к-рая реализует эту функцию и имеет наименьшее суммарное число сомножителей в своих слагаемых, т. е. имеет минимальную сложность. Такие д. н. ф. наз. минимальным и. Каждая минимальная д. н. ф. для заданной отличной от константы функции А. л. получается из сокращенной д. н. ф. этой функции путем выбрасывания нек-рых слагаемых. Для отдельных функций сокращенная д. н. ф. может совпадать с минимальной д. н. ф. Это имеет место, напр., для монотонных функции, т. е. таких функций, к-рые реализуются формулами над

В языке над где знак интерпретируется как сложение по модулю 2, устанавливаются следующие соотношения:

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

здесь по-прежнему считается, что конъюнкция связывает сильнее, чем знак +. Этих равенств достаточно, для того чтобы из них при помощи тождественных преобразований так же, как и при рассмотрении языка над можно было вывести любое верное равенство в языке над Выражение в этом языке наз. приведенным полиномом, если оно либо имеет вид где есть или 1, или переменное, или конъюнкция различных переменных без отрицании, при либо равно 1 + l. Напр., выражение является приведенным полиномом. Всякую формулу А. л. при помощи тождественных преобразований можно привести к приведенному полиному. Равенство имеет место тогда и только тогда, когда приведенный полином для совпадает с приведенным полиномом для Кроме рассмотренных языков, существуют и другие языки, равносильные им (два языка наз. равносильными, если при помощи нек-рых правил преобразований каждая формула одного из этих языков переводится в нек-рую равную ей формулу в другом языке, и обратно). В основу такого языка достаточно положить любую систему операций (и констант), обладающую тем свойством, что через операции (и константы) этой системы можно представить всякую функцию А. л. Такие системы наз. функционально полными. Примерами полных систем являются и т. п. Существует алгоритм, к-рый по произвольной конечной системе функций А. л. устанавливает ее полноту или неполноту. Он основан на следующем факте. Система функций А. л. является полной тогда и только тогда, когда она содержит такие функции что а также функции не монотонная, а для приведенный полином содержит слагаемое в к-ром больше одного сомножителя. Рассматриваются и такие языки, в основе к-рых лежат системы операций, не являющиеся функционально полными, и таких языков бесконечно много. Среди них имеется бесконечно много попарно несравнимых языков (в смысле отсутствия пе-реводимости при помощи тождественных преобразований с одного языка на другой). Однако для всякого языка, построенного на основе тех или иных операций А. л., существует такая конечная система равенств этого языка, что всякое равенство выводимо при помощи тождественных преобразований из равенств этой системы. Такая система наз. дедуктивно полной системой равенств данного языка. Напр., равенства (1) - (6) составляют полную систему равенств языка над

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

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

Лит.:[1] Воо1е G., The mathematical analysis of logic, being an essay towards a calculus of deductive reasoning, Oxf., 1948; [2] его же, An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities, N.Y., 1951; [3] Порецкий П. С., О способах решения логических равенств и об обратном способе математической логики, в кн.: Собрание протоколов заседаний секции физико-матем. наук Общества естествоиспытателей при Казанском ун-те, т. 2, Казань, 1884. с. 161-,430; [4] Гильберт Д., Аккерман Б., Основы теоретической логики, пер. с нем., М., 1947; [5] Новиков П. С., Элементы математической логики, 2 изд.. М., 1973; [6] Яблонский С. В., Гаврилов Г. П., Кудрявцев В. В., Функции алгебры логики и классы Поста, М., 1964. В. Б. Кудрявцев.

раздел матем. логики, изучающий высказывания, рассматриваемые со стороны их логич. значений (истинности или ложности), и логич. операции над ними. В А. л. принято отождествлять истинность высказывания с числом 1, а ложность - с числом О (А = 1 и С = 0 означает, что А истинно и что С ложно). Предметом изучения А. л. являются ф-ции, к-рые принимают лишь два значения: 0 или 1. Объединение простых высказываний в сложные в А. л. производится без учёта внутр. содержания (смысла) этих высказываний.

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