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

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

1. Законы идемпотентности
   A\/A = A
   A/\A = A
   

2. Законы коммутативности
   

   A/\B=B/\A
   A\/B=B\/A

3. Законы ассоциативности
   

   A\/ (B\/C) = (A\/B)\/C
   A/\ (B/\C) = (A/\B)/\C

4. Законы дистрибутивности
   

   A/\(B\/C) = (A/\B)\/(A/\C)
   A\/(B/\C) = (A\/B)/\(A\/C)

5. Законы поглощения
   

   A\/(A/\B)=A
   A/\(A\/B)=A

6. Законы двойного отрицания
   

   -(-A) = A

7. Законы нуля и единицы
   

   A\/0=A
   A/\1=A
   A\/1=1
   A/\0=0

8. Законы дополнения
   

   A\/-A=1
   A/\-A=0

9. Законы де Моргана
   

   -(A\/B)=-A/\-B
   -(A/\B)=-A\/-B

Примеры дополнительных операций

1. Импликация: A→B=-A\/B

2. Эквиваленция: A↔B=(A/\B)∨(-A/\-B).

Чтобы лучше понять, как работает алгебра логики, необходимо составить таблицы истинности. Они отлично иллюстрируют элементы алгебры логики.

1. Первый закон: Если A уже истинно (A=1), то неважно, истинно ли B — результат будет A. Если A=, результат также A, потому что A/\B не может быть истинным.

2. Второй закон: Если A ложно (A=0), результат всегда будет A, так как A∨B не делает выражение истинным, как и все выражения. 

Формулы простые, и потому видно, что:

1. A∨0=A: При объединении с ложью (0), результат равен A, потому что ничего не добавляется.

2. A∧1=A: При пересечении с истиной (1), результат равен A, так как 1 не изменяет исходное значение.

3. A∨1=1: Любое значение объединяется с истиной (1), давая истину, так как хотя бы один аргумент истинный.

4. A∧0=0: Любое значение пересекается с ложью (0), давая ложь, так как оба аргумента не могут быть истинными.

Согласно данным примерам можно построить типовые таблицы истинности для выражений любого вида. Более подробно примеры таблиц истинности можно найти в материале («таблицы логических операций»). 

Сейчас же можно рассмотреть примеры логических задач с использованием законов де Моргана, которые решаются табличным методом. Это – типовые задания ЕГЭ.

Задача 1.

Условие:
Есть два логических высказывания:

1. A: "Сотрудник вовремя завершил проект."

2. B: "Сотрудник не нарушил сроки по смежным задачам."

Руководитель хочет выяснить, при каких условиях утверждение

–(A\/B) (сотрудник не завершил проект вовремя и нарушил сроки по смежным задачам) будет истинным. Используя законы де Моргана, преобразуйте это выражение в эквивалентное и составьте таблицу истинности для проверки всех возможных комбинаций.

Решение:

1. Преобразуем выражение с помощью закона де Моргана:
   

   -(A\/B) = -A/\-B

   Это означает, что для выполнения исходного условия оба высказывания A и B должны быть ложными.

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

Начнем с построения таблицы.

Таблица истинности для задачи

Объяснение:

• В строках, где A=0 (проект не завершён вовремя) и B=0 (сроки нарушены), -A/\-B=1. Это соответствует случаю, когда исходное утверждение –(A\/B) также истинно.

• В других случаях хотя бы одно из A или B истинно, поэтому -(A\/B)=0.

Заключение:

С помощью таблицы мы подтвердили, что преобразование –(A\/B)=-A/\-B корректно, и нашли все комбинации, при которых выражение истинно. ​

Задача 2

Условие:
В компании существуют два правила:

1. A: "Работник сдал отчет в срок."

2. B: "Работник выполнил все требования к качеству отчета."

Менеджер хочет выяснить, при каких условиях сотрудник не выполнил хотя бы одно из этих правил, то есть условие

¬(A∨B) (сотрудник не сдал отчет в срок и не выполнил требования к качеству) будет истинным. Используя закон де Моргана, преобразуйте это выражение в эквивалентное и составьте таблицу истинности для проверки всех возможных комбинаций.

В рамках данной статьи мы не будем подробно разбирать решение этой задачи, потому что оно на 90% идентично решению предыдущей. Однако разница в условиях такова, что смотреть надо на последний столбец таблицы истинности и те строки, которые соответствуют поставленным вопросам.

«Не выполнил хотя бы одно условие» - это строка 2 и строка 3 таблицы истинности. Преобразование дает ответ (который может оказаться довольно неожиданным!). Будьте внимательны при решении подобных задач.

Задача 1: Закон идемпотентности

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

1. A: "Первый человек работает над проектом."

2. B: "Второй человек работает над проектом."

Менеджер хочет выяснить, при каких условиях будет истина выражение

A\/B

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

Задача 2: Закон ассоциативности

Условие:
На складе есть несколько типов товаров. Пусть:

1. A: "Есть товар типа 1."

2. B: "Есть товар типа 2."

3. C: "Есть товар типа 3."

Завсклада хочет проверить, при каких условиях утверждение

(A\/B)\/C

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

Задача 3: Закон дистрибутивности

Условие:
Предприятие решает, какие ресурсы будут выделены для проектов. Пусть:

1. A: "Ресурс 1 доступен."

2. B: "Ресурс 2 доступен."

3. C: "Ресурс 3 доступен."

Необходимо проверить, при каких условиях будет выполнено выражение

A∧(B∨C)

(Ресурс 1 доступен и хотя бы один из ресурсов 2 или 3 доступен). Используя закон дистрибутивности, преобразуйте это выражение в эквивалентное и составьте таблицу истинности для проверки всех возможных комбинаций.

Задача 4: Закон контрапозиции

Условие:
В компании существует правило:

1. A: "Работник прошел проверку на соблюдение стандартов."

2. B: "Работник может продолжить работать."

Если работник не прошел проверку, он не может продолжить работать. Это можно выразить следующим образом:

-B->-A

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

Для всех примеров задач необходимо составить полные таблицы истинности. При подготовке к ЕГЭ очень важно обращать внимание на все возможные варианты, чтобы не пропустить один из нескольких правильных ответов.