Законы алгебры логики. Эквивалентные преобразования формул

Вопросы для проверки знаний.

1. В чем смысл понятия эквивалентности формул?

2. Могут ли функции, соответствующие эквивалентным фор­мулам, иметь на нулевом наборе переменных различные логические значения?

3. Какие формулы называют тождественно истинными, а ка­кие – тождественно ложными?

Практические задания.

1. Какие из предложенных формул эквивалентны формуле F ₁=Ø(х & у): 1) Ø(х Ú у)Ú ху; 2) `х Ú `у; 3) (х Ú у)Ú `х.

2. Выяснить, какие из перечисленных формул будут тождест­венно ложными: 1) Ø(х Ú у)Ú xуz; 2) (х ® уz)&Ø(х Ú у Ú z); 3) х`у z ÅØ х; 4) Ø(х Ú у Ú z)& х.

3. Выяснить, какие из приведенных пар формул, зависящих от переменных х, у, дадут в сумме по модулю 2 тождественно истинную формулу:

1) `у и Ø(х Ú у); 2) (х ® у) и (у ® х); 3) `у и `xу Ú ху; 4) ху Å `х и х Ú у.

4. Какое логическое выражение равносильно выражению F= А ÙØ(Ø В Ú С): 1) Ø А ÚØ В Ú С 2) А ÙØ В ÙØ С 3) А Ù В ÙØ С 4) А ÙØ В Ù С?

Эквивалентным называют такое преобразование формулы F ₁, при котором вид ее записи изменяется (обозначим ее F ₂), но вновь получаемая формула F ₂ эквивалентна прежней F ₁, т.е. реализуемые ими функции f (F ₁) и f (F ₂) имеют одинаковые векторы истин­ности.

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

Пример 1. Рассмотрим простейшие случаи эквивалентной замены. Без изменения эквивалентности любой формулы в ней можно заменить любое вхождение переменной x на выражения вида x Ú x или x & x. Также эквивалентность формулы не нарушится при обрат­ной замене в ней выражений x Ú x или x & x на x.

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

1. Коммутативные законы сложения и умножения:

х Ú у = у Ú х, х & у = у & х.

2. Ассоциативные законы сложения и умножения:

(х Ú у)Ú z = х Ú(у Ú z)= х Ú у Ú z,

(х & у)& z = х &(у & z)= х & у & z.

3. Дистрибутивные законы:

х &(у Ú z)= х & у Ú х & z,

х Ú у & z =(х Ú у)&(х Ú z).

4. Правила де Моргана снятия отрицания:

Ø(х & у)= `х Ú `у, Ø(х Ú у)= `х&`у.

5. Закон двойного отрицания:

ØØ х = х.

6. Идемпотентность:

х Ú х = х, х & х = х.

7. Правила поглощения:

х Ú(х & у)= х, х &(х Ú у)= х.

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

х & `х =0.

9. Закон исключения третьего:

х Ú `х =1.

10. Операции с константами:

х Ú0= х, х Ú1=1, х &0=0, х &1= х.

Справедливость законов не нарушается, если правую и левую части в них меняют местами. Например, в прямой формулировке дистрибутивные законы задают правила внесения сомножителя и слагаемого в скобки, а обратная запись данных законов задает правила вынесения одинаковых членов из скобок: х & у Ú х & z = х &(у Ú z), (х Ú у)&(х Ú z) = х Ú у & z.

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

Пример 2. Доказать первое правило де Моргана.

Решение. Построим векторы значений истинности функций для формул Ø(х & у) и `х Ú `у. Как видно из приведенных ниже таблиц, они полностью совпадают (столбцы 4 и 7).

x	y	х & у	Ø(х & у)	` х	` y	` х Ú` y

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

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

Частные случаи обратной записи дистрибутивных законов при z = Ø у называют правилами расщепления. Они c учетом (у ÚØ у = 1) и (у &Ø у = 0)принимают вид: х & у Ú х &Ø у = х, (х Ú у)&(х ÚØ у) = х.

При z = Ø х частные случаи дистрибутивных законов называют законами поглощения Блейка-Порецкого. Они c учетом (х &Ø х= 0) и (х ÚØ х = 1) принимают вид: х &(у ÚØ х)= х & у, х Ú у &Ø х =(х Ú у).

Ассоциативные и коммутативные законы справедливы при любом числе входящих в них логических переменных. Также они справедливы для всех логических операций, которые эквивалентны относительно перестановки своих переменных – {Å, º, ¯, ê}.

В общем случае для произвольного числа переменных (у ₁, у ₂, …, у_n) справедливы обобщенные дистрибутивные законы:

х &(у ₁Ú у ₂Ú…Ú у_n)= х & у ₁ Ú х & у ₂ Ú …Ú х & у_n,

х Ú(у ₁& у ₂&…& у_n)= (х Ú у ₁) & (х Ú у ₂)& …&(х Ú у_n).

Также для произвольного числа переменных (х ₁, х ₂,…, х_n) выполняются обобщенные правила де Моргана:

Ø(х ₁& х ₂&…& х_n) = `х <sub>1</sub> Ú `х ₂ Ú … Ú `х_n,

Ø(х ₁Ú х ₂ Ú…Ú х_n) = `х <sub>1</sub> & `х ₂ & … & `х_n.

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

Поскольку законы сформулированы с помощью логических связок (Ø,&,Ú), то в том случае, когда формула содержит в своей записи другие логические связ­ки, их необходимо выразить через этот базовый набор элементарных функций. Для этого используют следующие формульные зависимости:

x ® y =Ø x Ú у;

x º y = (x ® у) (у ® x)= (Ø x Ú у)(x ÚØ у);

x Å y =` x у Ú x ` у;

x ¯ y = (` x ` у);

x ½ y = (` x Ú` у).

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

1) логическое значение 1, следовательно, формула является тавтологией,

2) логическое значение 0, при этом исходная формула является противоречием,

3) логическая сумма (дизъюнкция) логических произведений переменных или их отрицаний (например, `x`y z Ú у`z; х у z Ú `x`z Ú `y), такой вид функций называют дизъюнктивной нормальной формой (сокращенно - ДНФ);

4) логическое произведение (конъюнкцию) логических сумм переменных или их отрицаний (например, (`x Ú `y Ú z)(у Ú `z); (х Ú у Ú z)(`x Ú `z)), такой вид функций называют конъюнктивной нормальной формой (сокращенно - КНФ).

Если ДНФ и КНФ больше не допускают сокращений, то реализующие их функции принимают как единичные, так и нулевые логические значения.

Полученные в итоге сокращения формулы ДНФ (КНФ) могут содержать только одно произведение (слагаемое). Это не влияет на их свойства.

Пример 3. Упростить формулу F =Ø(x Ú `у)& у.

Решение. Для начала вносим отрицание вглубь суммы (x Ú `у). Для этого используем правило де Моргана снятия отрицания(Ø(x Ú у)= `x & `у). Применяя его в данном примере, получим:

Ø(x Ú `у)& у = (`x &Ø `y) & у.

Применим закон двойного отрицания (ØØ y = y) и, дважды используя ассоциативность умножения, вначале раскрываем умножение скобок на y, а затем выделяем в полученном выражении произведение y & y:

(`x &Ø `y) & у = (`x & y) & у = `x & y & у = `x &(y & у).

Применяя к выделенному произведению свойство идемпотентности (y & y = y), получим максимально упрощенное выражение для исходной формулы в виде произведения: F ₁= `x & у.

Ответ:`х&у.

Пример 4. Упростить формулу F = x & (x ¯ z)Å(у ï(x ¯ y)).

Решение. Выражаем функцию Пирса через связки (Ø,&,Ú):

F = x & (`x & ` z) Å (у ï(`x & `y)).

Используя ассоциативность умножения, преобразуем первое слагаемое формулы, выражаем функцию Шеффера ï через (Ø,&,Ú):

F = (x & `x) & ` z Å (`у ÚØ (`x & `y)).

Применим закон противоречия (х &`х=0) и используем правило де Моргана:

F = 0 &`z Å (`у Ú (Ø`x ÚØ`y)).

Используем свойства операций с константами (х&0=0) и закон двойного отрицания:

F = 0 Å (`у Ú (x Ú y)).

Используем ассоциативность и коммутативность сложения, а также закон исключения третьего (х Ú `х = 1):

F = 0 Å (`у Ú x Ú y) = 0 Å (`у Ú y Ú x) = 0 Å (1Ú x).

Используем свойства операций с константами (х Ú 1 = 1):

F = 0 Å 1 =1.

Ответ: формула является тавтологией.

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

Дата добавления: 2014-01-20