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

---

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

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

А = .

 Двойное отрицание исключает отрицание.

2. Переместительный (коммутативный) закон:

— для логического сложения:

A v B = B v A

— для логического умножения:

A&B = B&A.

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

 В обычной алгебре   2 + 3 = 3 + 2; 2 * 3 = 3 * 2.

3. Сочетательный (ассоциативный)  закон:

— для логического сложения:

(A v B) v C = A v (B v C);

— для логического умножения:

(A&B)&C = A&(B&C).

 При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

 В обычной алгебре:   

(2 + 3) + 4 = 2 + (3 + 4) = 2 + 3 + 4, 

5 * (6 * 7) = 5 * (6*7) = 5 * 6 * 7.

4. Распределительный (дистрибутивный) закон:

— для логического сложения:

(A v B)&C  = (A&C) v (B&C);

— для логического умножения:

(A&B) v C = (A v C)&(B v C).

 Определяет правило выноса общего высказывания за скобку.

 В обычной алгебре:   (2 + 3) * 4 = 2 * 4 + 3 * 4.

5. Закон общей инверсии (законы де Моргана):

— для логического сложения

  =  &  ;

— для логического умножения:

  =   v 

6. Закон идемпотентности

— для логического сложения:

A v A = A;

— для логического умножения:

A&A = A.

Закон означает отсутствие показателей степени.

7. Законы исключения констант:

— для логического сложения:

A v 1 = 1,      A v 0 = A;

— для логического умножения:

A & 1 = A,      A & 0 = 0.

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

A &  = 0.

 Невозможно, чтобы противоречащие высказывания были одновременно истинными.

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

A v  = 1.

10. Закон поглощения:

— для логического сложения:

A v (A&B) = A;

— для логического умножения:

A&(A v B) = A.

11. Закон исключения (склеивания):

— для логического сложения:

(A&B) v (  &B) = B;

— для логического умножения:

(A v B)&(  v B) = B.

 Пример 1. Найдите X, если  Ú  = В.

Упростим левую часть равенства. Какими законами воспользуемся? Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:

  ( & ) c ( &A)

Согласно распределительному закону для логического сложения:     

 &(  v A)

Согласно закону исключения третьего и закона исключения констант:

 &1 = 

Полученную левую часть приравняем правой:

 = В

Окончательно получим, что  

X =   .

 Пример 2. Упростите логическое выражение (A v B v C)& . Посмотрите на выражение, посмотрите на законы, что можно сделать?

Согласно закону общей инверсии для логического сложения (первому закону Моргана) и закону двойного отрицания:

(A v B v C)&  = (A v B v C)&(  & B &  )

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

(A v B v C)&(  &B&  ) = (A&  ) v (B&  ) v (C&  ) v (A&B) v (B&B) v (C&B) v (A&  ) v (B&  ) v (C&  )

Согласно закона противоречия:

 (A&  ) = 0; (C&  ) = 0

 Согласно закона идемпотентности

(B&B) = B

 Подставляем значения и, используя переместительный (коммутативный) закон и группируя слагаемые, получаем:

0 v (A&B) v (  &B) v B v (C&B) v (  &B) v (C&  ) v (A&  ) v 0

 Согласно закона исключения (склеивания)

(A&B) v (  &B) = B
(C&B) v (  &B) = B

 Подставляем значения и получаем:

0 v B v B v B v (C&  ) v (A&  ) v 0

 Согласно закона исключения констант для логического сложения и закона идемпотентности:

  0 v B v 0 v B v B = B

 Подставляем значения и получаем:

B v (C&  ) v (A&  )

С

Решение задач

1.Упростить логическое выражение

1. (А v ┐А) &В
2. А& (А v В) & (В v ┐В)

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

2. Логическое выражение называется тождественно – ложным, если оно принимает значения 0 на всех наборах входящих в него простых высказываний.

Упростить выражение и показать, что оно тождественно – ложное

(А&В& ┐В) v (А&┐А) v (В&С& ┐С)

3 .Логическое выражение называется тождественно – истинным, если оно принимает значения 1 на всех наборах входящих в него простых высказываний.

Упростить выражение и показать, что оно тождественно – истинное

(А&В&┐С) v (А&В&С) v ┐(Аv В)

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

Решение. Определим следующие простые высказывания: П - «пасмурная погода»;Д -  «идет дождь»;В - «дует ветер».

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

5. Задача

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

Решение задачи.

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

А = «В первой аудитории находится кабинет информатики»; 
В = «Во второй аудитории находится кабинет информатики».

Отрицаний этих высказывании:

А = «В первой аудитории находится кабинет физики»;
В = «Bo второй аудитории находится кабинет физики».

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

X = А v В.

Высказывание, содержащееся на табличке на двери вто­рой аудитории, соответствует логическому выражению:

Y = А.

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

(X&Y) v(X& Y) = 1.

 Подставим вместо X и Y соответствующие формулы:

(X &Y) v (X & Y) = ((А vB) &A)v ((A v B) & А).

 Упростим сначала первое слагаемое. В соответствии с законом дистрибутивности умножения относительно сложения:

((А vB) &A) = A&A v B&A

В соответствии с законом непротиворечия:

A&A v B&A = 0 v В&А

Упростим теперь второе слагаемое. В соответствии с первым законом де Моргана и законом двойного отрицания:

(A v B) & А = А&В&А = А&А&В

В соответствии с законом непротиворечия:

А&А&В = 0&В = 0

В результате получаем:

(0 v В & A) v 0 = В& А.

Для того чтобы выполнялось равенство  В & А = 1, В и А должны быть равны 1, то есть соответствующие им высказывания истинны.

Ответ: В первой аудитории находится кабинет физики, а во второй — кабинет информатики.

Домашнее задание

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

1. А v  (┐А&В)
2. А& (┐А v В)
3. (А v В) & (┐В v А) & (┐С v В)

2. В процессе составления расписания уроков учителя высказали свои пожелания. Учитель математики, высказал пожелание про­водить первый или второй урок, учитель информатики — первый или третий, а учитель физики  второй или третий урок. Сколько существует возможных вариантов расписания и каковы они?