Преобразование логических выражений

 

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

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

Основные формулы преобразования логических выражений:

ØØA º A (закон двойного отрицания)

Ø(A & B) º ØA Ú ØB (закон д¢ Моргана)

Ø(A Ú B) º ØA & ØB (закон д¢ Моргана)

Ø(A ® B) º A & ØB

A ® B º ØB ® ØA º ØA Ú B º Ø(A & ØB)

A«Bº(A®B)&(B®A)º(A&B)Ú(ØA&ØB)º(ØAÚB)&(AÚØB)

A & (A Ú B) º A (закон поглощения)

A Ú A & B º A (закон поглощения)

ØA & (A Ú B) º ØA & B

A Ú ØA & B º AÚ B

(AÚ B) & (A Ú ØB) º A (закон склеивания)

(A & B) Ú (A & ØB) º A (закон склеивания)

(A Ú C) & (B Ú ØC) º (A Ú C) & (B Ú ØC) & (A Ú B)

(A & C) Ú (B & ØC) º (A & C) Ú (B & ØC) Ú (A & B)

(A ® B) & (B ® C) º (A ® C)

Законы коммутативности: A & B º B & A; A Ú B º B Ú A

Законы ассоциативности: (A Ú B) Ú С º A Ú (B ÚС);
(A & B) & С º A & (B & С)

Законы идемпотентности (лат idem– тот же самый, potens– сильный; дословно– равносильный): A Ú A º A; A & A º A

Законы дистрибутивности: A & (B Ú С) º (A&B) Ú (A&С);
A Ú (B & С) º (A Ú B) & (A Ú С)

A Ú 1 º 1; A & 0 º 0; A & 1 º A; А Ú 0 º А (законы исключения констант)

ØA Ú A º 1 (закон исключенного третьего)

A & ØA º 0 (закон противоречия)

Данные формулы позволяют без ущерба для смысла взаимозаменять суждения, устранять избыточную информацию, выделять новые суждения, если это нужно.

Упражнение №1 Упростите выражение:

1) Ø((A Ú B) ® Ø(B ÚС))

2) ØХ Ú Ø(Х Ú Y) Ú Ø(Y & Ø(X & Y))

3) Ø(X Ú Y Ú Ø(X & Y)) & Ø(Х Ú Y)

4) ((C Ú B) ® B) & (A & B) ® B

Упражнение №2 Упростите выражение:

1) ((C Ú B) ® B) & (A Ú B) ® B

2) (A ® B) & (B ® (C Ú ØA)) & (ØD ® (A & ØC)) & (D ® A)

3) X1 Ú X2 Ú X1 & X3 Ú Ø(X1 & X2)

4) (X1 Ú X3) & X1 & ØX2 Ú ØX1

5) X1 & X2 & ØX3 Ú X1 Ú X2

6) X1 & X2 Ú X1 Ú X3 & ØX1

 

Применение законов логики при решении задач

Для решения логических задач нужно:

1. Внимательно изучить условие

2. Выделить простые высказывания и обозначить их латинскими буквами

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

4. Упростить полученное выражение используя формулы преобразования.

5. Выбрать решение – набор значений простых высказываний, при котором выражение является истинным

6. Проверить, удовлетворяет ли полученное решение условию задачи.

Задача №1

Кто из учеников A, B, C, D играет, а кто не играет в шахматы, если известно:

1) если A или B играет, то С не играет;

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

3) С играет.

Задача №2

По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено следующее:

1) если Ивановне участвовал в преступлении или Петровучаствовал, то Сидоровучаствовал

2) если Иванов не участвовал, то Сидоров не участвовал

Виновен ли Иванов?

Задача №3

На вопрос, какая завтра будет погода, синоптик ответил:

1) если не будет ветра, то будет пасмурная погода без дождя

2) если будет дождь, то будет пасмурно и без ветра

3) если будет пасмурная погода, то будет дождь и не будет ветра

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