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

Основные законы формальной логики Закон тождества А = А Закон непротиворечия А& A=0 Закон исключения третьего А А=1 Закон двойного отрицания А=А В процессе рассуждения нельзя подменять одно понятие другим Не могут быть одновременно истинными суждение и его отрицание Высказывание может быть либо истинным либо ложным, третьего не дано Если отрицать дважды некоторое суждение, то получается исходное суждение

Свойства констант 0=1 1=0 А 0=АА&0=0 А 1=1А&1=А

Законы алгебры логики Идемпотентность А А=А А&А=А Коммутативность А В=В АА&В=В&А Ассоциативность А (В С)= (А В) С А &(В & С)= (А & В) &С

Законы алгебры логики Дистрибутивность А (В & С)= (А В) &(A С) А & (В С)= (А & В) (A&С) Поглощение А (А & В)=АА & (А В)=А Законы де Моргана (А В)= А& В (А &В)= А В

6 Огастес де МОРГАН Морган Огастес (Августус) де ( ) - шотландский математик и логик. Секретарь Королевcкого астрономического общества (1847г.), член Лондонского королевского общества. Первый президент Лондонского математического общества. Родился в Мадуре (Индия). Учился в Тринити-колледж (в Кембридже). Профессор математики в университетском колледже в Лондоне. Основные труды по алгебре, математическому анализу и математической логике. В теории рядов описал логарифмическую шкалу для критериев сходимости; занимался теорией расходящихся рядов. Один из основателей формальной алгебры. Продолжая работы Дж. Пикока, Морган в гг. опубликовал ряд работ по основам алгебры. В трактате "Формальная логика или исчисление выводов необходимых и возможных" (1847г.), Морган некоторыми своими положениями опередил Дж. Буля. Позднее Морган успешно изучал логику отношений - область, не охваченную исследованиями предшественников. Написал много исторических работ, в частности книгу "Бюджет парадоксов" (1872г.). Большой вклад внес также в дедуктивную логику вообще и математическую в частности. Лондонское математическое общество учредило медаль им. О. Моргана.

Правила замены операций Импликации А В = А B А В = B A Эквивалентности А В = (А&B) ( A& B) А В = (А B) ( A B) А В = (А B) & (B A)

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

Основные приемы замены X=X 1 X=X 0 1=А А 0=В В Z=Z Z Z C=C C C Е= Е - По свойствам констант - По закону исключения третьего - По закону непротиворечия -По закону идемпотентности - По закону двойного отрицания

Пример Упростить: А В А В По закону дистрибутивности вынесем А за скобки А В А В=А 1= А А (В В)= Упростить: (А В )& (А В) Упростить: ( X Y )

11 Задание 2. Упростите логическое выражение F= (A v B) (B v C). Избавимся от импликации и отрицания. Воспользуемся (¬(AB)=A& ¬ B). Получится: ¬((AvB) ¬(BvC))= (AvB)& ¬ (¬(BvC)). Применим закон двойного отрицания, получим: (A v В) & ¬(¬(В v С)) = (A v В) & (B v С). Применим правило дистрибутивности ((AB) +(AC) = A(B+C)). Получим: (AvВ)& (B v С)= (AvB)&Bv(AvB)&C Применим закон коммутативности (A&B=B&A ) и дистрибутивности (16). Получим: (AvB)&Bv(AvB)&C = A&BvB&BvA&CvB&C. Применим (А& A= A) и получим: A&BvB&BvA&CvB&C= A&BvBvA&CvB&C Применим ((A&B) v(A&C) = A&(BvC) ), т.е. вынесем за скобки В. Получим:A&BvBvA&CvB&C= B& (Av1)vA&CvB&C. Применим (Аv 1= 1 ). Получим:B& (Av1) vA&CvB&C= BvA&CvB&C. Переставим местами слагаемые, сгруппируем и вынесем В за скобки. Получим:BvA&CvB&C = B& (1vC)vA&C. Применим (Аv 1= 1 ) и получим ответ: B&(1vC)vA&C=BvA&C.

12 Закрепление изученного Упростите выражение: 1.F = ¬ (A&B) v ¬ (BvC). 2.F = (AB) v (BA). 3.F = A&CvĀ&C. 4.F = Av Bv CvAvBvC 2 Упростите выражение: 1. F = ¬(X&Yv ¬(X&Y)). 2. F = X&¬ ( YvX). 3. F = (XvZ) & (Xv Z) & ( YvZ).

13 Ответы к 2: 1.F = ¬(X&Yv ¬(X&Y)) = 0. 2.F = X&¬ ( YvX) = X&Y. 3.F = (XvZ) & (Xv Z) & ( YvZ) =X&( YvZ). Ответы к 1: 1.F = ¬ (A&B) v ¬ (BvC) = Av B. 2.F= (AB) v (BA) = 1. 3.F = A&CvĀ&C=C. 4.F = Av Bv CvAvBvC=1.

14 ДОМАШНЯЯ РАБОТА Упростите логические выражения: Х&X&1 F= не (Х и (не Х и не Y)) F= B&(AvA&B) 0&Xv0 F= не Х или (не (Х и Yи не Y)) F= (AvC)&(AvC)&(BvC) 0vX&1 F= не Х и (не(неY или Х)) F=A&B v A&Bv A&BvB&C

: - ) - радостное лицо : - ( - грустное лицо ; - ) - подмигивающая улыбка : 0 ) - клоун 8:-) - маленькая девочка