shkolageo.ru 1

Законы логики и правила преобразования логических выражений.

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

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

А = .

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

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

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

A V B = B V A

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

A&B = B&A.

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

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

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

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

(A Ú B) Ú C = A Ú (BÚ 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 Ú B)&C  = (A&C) Ú (B&C);

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

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

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

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

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

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

 = & ;


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

 =  Ú

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

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

A Ú A = A;

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

A&A = A.

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

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

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

A Ú 1 = 1,      A Ú 0 = A;

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

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

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

A& = 0.

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

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

A Ú = 1.

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

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

A Ú (A&B) = A;

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

A&(A Ú B) = A.

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

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

(A&B) Ú ( &B) = B;

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

(A Ú B)&( Ú B) = B.

12. Закон контрапозиции (правило перевертывания):

(A Û  B) = (BÛ A).
┐(А→В) = А&┐В
┐А&(АÚВ)= ┐А&В
АÚ┐А&В=АÚВ

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


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

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

  ( & ) Ú ( &A)

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

&( Ú A)

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

&1 =

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

= В

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

X =  .

 Пример 2. Упростите логическое выражение (A Ú B Ú C)&

Посмотрите на выражение, посмотрите на законы, что можно сделать?

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


(A Ú B Ú C)& = (A Ú B Ú C)&( &B& )

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

(A Ú B Ú C)&( &B& ) = (A& ) Ú (B& ) Ú (C& ) Ú (A&B) Ú (B&B) Ú (C&B) Ú (A& ) Ú (B& ) Ú (C& )

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

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

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

(B&B) = B

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

0 Ú (A&B) Ú ( &B) Ú B Ú (C&B) Ú ( &B) Ú (C& ) Ú (A& ) Ú 0


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

(A&B) Ú ( &B) = B
(C&B) Ú ( &B) = B

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

0 Ú B Ú B Ú B Ú (C& ) Ú (A& ) Ú 0

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

  0 Ú B Ú 0 Ú B Ú B = B

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

B Ú (C& ) Ú (A& )

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

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


  1. (АÚ┐А) &В

  2. А& (АÚВ) & (ВÚ┐В)

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

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

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

(А&В&┐В) Ú (А&┐А) Ú (В&С&┐С)

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

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

(А&В&┐С) Ú (А&В&С) Ú┐(АÚВ)

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


Решение. Определим следующие простые высказывания:

П - «пасмурная погода»;
Д -  «идет дождь»;
В - «дует ветер».

Тогда  соответствующее  логическое  выражение  запишется так:

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

4. Задача

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

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

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

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

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

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

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

X = АÚВ.

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

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, то есть соответствующие им высказывания истинны.

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

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


  1. АÚ (┐А&В)

  2. А& (┐АÚВ)

  3. (АÚВ) & (┐ВÚА) & (┐СÚВ)

Продолжаем решать задачи и упрощать логические выражения

6. Задача

Кто из учеников А, В, С и D играет, а кто не играет в шахматы, если известно следующее:

  • а) если А или В играет, то С не играет;

  • б) если В не играет, то играют С и D;

  • в)  С играет

Решение. Определим следующие простые высказывания:

  • А — «ученик А играет в шахматы»;

  • В — «ученик В играет в шахматы»;

  • С — «ученик С играет в шахматы»;

  • D — «ученик D играет в шахматы».

Запишем высказывания:

  • а)  (A v В) → С;

  • б)  В → С & D;

  • в)  С.


Запишем произведение указанных сложных высказываний:

((A v В) → С) & (В → С & D) & С.

Упростим эту формулу:

((A v В) → С) & (В → С & D) & С = ((А v В) v С) & (В v С & D) & С = (А & В) v С) & (В v С & D) & C = A & B & C & D =1.

Отсюда А = 0, В = 1, С = 1, D = 1.

Ответ: в шахматы играют ученики В,С и D, а ученик А не играет.