Большая Советская Энциклопедия (АЛ)

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

XY		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&= 0 (закон противоречия);

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

(7) Х®Y ==ÚY, Х~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 не содержит одинаковых сомножителей и не содержит сомножителей вида Х и  одновременно и все Á_i — попарно различны. Здесь скобки опускаются, т. к. предполагается, что операция конъюнкции связывает «сильнее», чем дизъюнкция, т. е. при вычислении по заданным значениям переменных следует сначала вычислить значения Á_i .Эти выражения называются дизъюнктивными нормальными формами (днф). Каждую формулу Á, реализующую функцию, отличную от константы, в языке над &, Ú, ®, ~ , ^- , 0, 1 при помощи равенств (1) — (7) можно привести к равной ей днф, содержащей все переменные формулы Á и любое число других переменных, причем каждое Á в этой днф содержит одни и те же переменные. Такая днф называется совершенной днф формулы Á. Возможность приведения к совершенной днф лежит в основе алгоритма, устанавливающего равенство или неравенство двух наперёд заданных формул.

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