Преобразование логических выражений
Табличный способ определения истинности сложного выражения имеет ограниченное применение, так как при увеличении числа логических переменных приходится перебирать слишком много вариантов. В таких случаях используют способ приведения формул к нормальной форме Формула имеет нормальную форму, если в ней отсутствуют знаки эквивалентности, импликации, двойного отрицания, при этом знаки отрицания находятся только при переменных. Основные формулы преобразования логических выражений: ØØ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 ÚС); Законы идемпотентности (лат idem– тот же самый, potens– сильный; дословно– равносильный): A Ú A º A; A & A º 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) если будет пасмурная погода, то будет дождь и не будет ветра Подумав немного, синоптик уточнил, что его три высказывания можно лаконично записать в виде одного сложного суждения. Сформулируйте его.
|