Устимкина Л.И. 1 Законы и правила математической логики Упрощение сложных высказываний 900igr.net. - презентация

1 Устимкина Л.И. 1 Законы и правила математической логики Упрощение сложных высказываний 900igr.net

2 Устимкина Л.И. 2 Основные законы алгебры логики 1 А (АА)Закон тождества 2 A&Ā=0(А Ā= 0)Закон непротиворечия 3 A v Ā=l(A+ Ā= 1)Закон исключающего третьего 4 _ Ā=A Закон двойного отрицания 5 А& 0= 0 Av0=A А 0=0 A+0=A 6 А& 1= A Аv 1= 1 А 1= A А+ 1= 1 7 А& A= A Аv A= A А A= A А+ A= A 8 Аv Ā= 1 А+ Ā= 1 Закон Моргана 9 ______ _ (AB)=A& B _____ _ (AB)=AB 10 AB=Ā v BAB=Ā+B 11 A&(A v B)=A A(A+B)=AЗакон поглощения

3 Устимкина Л.И. 3 Основные законы алгебры логики 12A v A&B = AA+AB = AЗакон поглощения 13 Ā&(AvB) = Ā&B Ā(A+B) = ĀB 14AvĀ&B = AvBA+ĀB = A+B 15(AvB) vC =Av(BvC) (A&B)&C = A&(B&C) (A+B)+C=A+(B+C) (AB)C = A(BC) Правило ассоциативности 16(A&B) v (A&C) = A &(B vC)(AB) +(AC) = A(B+C) Правило дистрибутивности 17AvA = AA&A = AA+A = AAA = AПравило идемпотентности 18A v B=B v AA&B=B&AA+B=B+AAB=BAПравило коммутативности 19 ___ AB = A & B v A& В = (Ā+B) &(A+ B)

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

5 Устимкина Л.И. 5 Задание 1. Упростить выражение: _ X Y V X Y Воспользуемся распределительным законом: Х ( Y V Z ) = X Y V X Z (или вынесем общий множитель за скобку) 1 X Y V X Y = _ X (Y V Y ) = = Х 1 = Х

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

7 Устимкина Л.И. 7 IV. Закрепление изученного 1 Упростите выражение: 1.F = ¬ (A&B) v ¬ (BvC). 2.F = (AB) v (BA). 3.F = A&CvĀ&C. 4.F = Av Bv CvAvBvC Ответы: 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.

8 Устимкина Л.И. 8 2 Упростите выражение: 1. F = ¬(X&Yv ¬(X&Y)). 2. F = X&¬ ( YvX). 3. F = (XvZ) & (Xv Z) & ( YvZ). Ответы: 1.F = ¬(X&Yv ¬(X&Y)) = 0. 2.F = X&¬ ( YvX) = X&Y. 3.F = (XvZ) & (Xv Z) & ( YvZ) =X&( YvZ).

9 Устимкина Л.И. 9 Домашняя работа I. Упростите логические выражения: 1.F = Av ( A&B). 2.F = A& ( AvB). 3.F = (AvB) & ( BvA) & ( CvB). 4.F = (1V (AvB)) V ((AvC) &1). ¬ & & & ¬ ¬ V V A B C II. Дана следующая логическая схема. Упростите ее, используя минимальное количество вентилей. III. Как составить расписание. При составлении расписания учителя высказали следующие пожелания: учитель физики хочет иметь первый и второй урок; учитель химии - первый или третий; учитель информатики второй или третий. Предложите возможные варианты расписания.