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

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

Законы исключения констант 0=1 1=0 А 0=АА 0=0 А 1=1А 1=А

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

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

Законы алгебры логики Законы де Моргана (инверсии) (А В) = А В Упростить: ( X Y )

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

Законы алгебры логики Закон исключения (склеивания) (А В) (A В)=А А В А В =А 1 = А А (В В) = Упростить: (А В )& (А В)

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

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

Пример Ответ

Решите задачи 1 Х 0 = 0 Х 0 = Х Х 1= 0 Х Х=

Какое логическое выражение равносильно выражению ¬ (А \/ ¬B)? 1) A \/ B 2) A /\ B 3) ¬A \/ ¬B 4) ¬A /\ B Ответ: 4

Задача В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях. Один считает, что первой будет Наташа, а Маша будет второй. Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место. Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?

1. Первой будет Наташа, а Маша будет второй Обозначим высказывания: Н1 = первой будет Наташа; М2 = второй будет Маша; Л2 = второй будет Люда; Р4 = четвертой будет Рита; Р3 = третьей будет Рита; Н2 = второй будет Наташа. Согласно условию: из высказываний 1 болельщика следует, что Н1 V М2=1 истинно; из высказываний 2 болельщика следует, что Л2 V Р4=1 истинно; из высказываний 3 болельщика следует, что Р3 V Н2=1 истинно. Следовательно, истинна и конъюнкция (Н1 V М2) /\ (Л2 V Р4) /\ (Р3 V Н2) = 1. Второе место - Люда, а Рита - четвертое место Рита займет третье место, а Наташа будет второй

(Н1 V М2) /\ (Л2 V Р4) /\ (Р3 V Н2) = 1. (Н1 V М2) /\ (Л2 V Р4) /\ (Р3 V Н2) = =((Н1/\Л2 V Н1/\Р4 )V (М2/\Л2 V М2/\Р4)) /\ (Р3VН2)= =(Н1/\ Л2/\Р3) V (Н1/\Р4/\Р3) V (М2/\Л2/\Р3) V (М2/\Р4/\Р3) V (Н1/\Л2/\Н2) V (Н1/\Р4/\Н2) V (М2/\Л2/\Н2) V (М2/\Р4/\Н2) = =Н1/\ Л2/\Р3 V 0 V 0 V 0 V 0 V 0 V 0 V= Н1/\ Л2/\Р3 Наташа-1, Люда-2, Рита-3, а Маша-4.

Составить таблицу истинности для формулы и упростите выражение ¬ (B /\ C) V (A/\C B) ABC(B /\ C)¬ (B /\ C)A/\C(A/\C B)¬ (B /\ C) V (A/\C B)

Составить таблицу истинности для формулы и упростите выражение ¬ (B C) V (A C B) упрощаем выражение применим формулу для импликации ¬ (B C) V ¬ (A C) V B = применим 1 и 2 законы де Моргана =(¬B V ¬C) V (¬A V ¬C) V B = уберём скобки =¬B V ¬C V ¬A V ¬C V B= применим переместительный закон =¬B V B V ¬C V ¬C V ¬A = закон исключения третьего, закон идемпотентности =1 V ¬С V ¬A = закон исключения констант =1 V ¬A = 1

19 ДОМАШНЯЯ РАБОТА 1. Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров: A) Макс победит, Билл – второй; B) Билл – третий. Ник – первый; C) Макс – последний, а первый – Джон. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс?

20 1. Упростите выражение: 1. F = ¬ (A&B) v ¬ (BvC). 2. F = A&CvĀ&C. 3. F = Av Bv CvAvBvC 2 Упростите выражение: 1. F = ¬(X&Yv ¬(X&Y)). 2. F = X&¬ ( YvX). 3. F = (XvZ) & (Xv Z) & ( YvZ). ДОМАШНЯЯ РАБОТА