В настоящее время на вступительных экзаменах по информатике есть много заданий по теме “алгебра логики”.
Поэтому в этой статье рассмотрим пару примеров алгебры логики из ЕГЭ
Алгебра логики – раздел математической логики, изучающий строение сложных логических высказываний и способы установления их истинности с помощью алгебраических методов. Немного повторения из прошлой темы.
Логические операции:
¬ отрицание (инверсия)
&, /\ конъюнкция (“И”)
V дизъюнкция (“ИЛИ”)
логическое следование (импликация)
равнозначность (эквивалентность)
В чем смысл закона двойного отрицания:
Двойное отрицание исключает отрицание.
Законы де Моргана (законы общей инверсии).
Отрицание дизъюнкции является конъюнкцией отрицаний:
¬(A V B) = ¬A /\ ¬B
Отрицание конъюнкции является дизъюнкцией отрицаний:
¬(A /\B) = ¬A V ¬B
Закон идемпотентности (одинаковости).
A V A = A
A /\ A = A
Смысл закона исключения третьего
Из двух противоречащих высказываний об одном и том же одно всегда истинно, второе ложно, третьего не дано:
A V ¬А= 1
Закон противоречия
Не могут быть одновременно истинны утверждение и его отрицание:
A /\ ¬А= 0
Закон исключения констант.
Для логического сложения:
A V 1 = 1 A V 0 = A
Для логического умножения:
A /\ 1 = A A /\ 0 = 0
Ну а теперь примерчики
Пример 1. ( Задание А11 )
Для какого имени истинно высказывание:
¬ (Первая буква имени гласная -> Четвертая буква имени согласная)?
1) ЕЛЕНА
2) ВАДИМ
3) АНТОН
4) ФЕДОР
Решение. Сложное высказывание состоит из двух простых высказываний:
А – первая буква имени гласная,
В – четвертая буква имени согласная.
¬ (А ->В) = ¬ (¬A V В) = (¬ (¬А) /\ ¬B) = A /\ ¬B
Применяемые формулы:
1. Импликация через дизъюнкцию А ? В = ¬A V В
2. Закон де Моргана ¬(A V B) = ¬A /\ ¬B
3. Закон двойного отрицания.
(Первая буква имени гласная /\ Четвертая буква имени гласная) выразить импликацию через дизъюнкцию А :
В = ¬A V В
Ответ : 3
Пример 2. ( Задание А12 )
Какое логическое выражение равносильно выражению ¬ (А \/ ¬B)?
1) A \/ B
2) A /\ B
3) ¬A \/ ¬B
4) ¬A /\ B
Решение . ¬ (А \/ ¬B)= ¬ А \/ ¬ (¬B)= ¬ А \/ B
Ответ: 4
Пример 3 ( Задание В4 )
В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях.
Один считает, что первой будет Наташа, а Маша будет второй.
Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.
Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?
(В ответе перечислите подряд без пробелов числа, соответствующие местам девочек в указанном порядке имен.)
Решение:
Обозначим высказывания:
Н1 = “первой будет Наташа”;
М2 = “второй будет Маша”;
Л2 = “второй будет Люда”;
Р4 = “четвертой будет Рита”;
Р3 = “третьей будет Рита”;
Н2 = “второй будет Наташа”.
Согласно условию:
из высказываний 1 болельщика следует, что Н1VМ2 истинно;
из высказываний2 болельщика следует, что Л2VР4 истинно;
из высказываний 3 болельщика следует, что Р3VН2 истинно.
Следовательно, истинна и конъюнкция
(Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = 1.
Раскрыв скобки получим:
(Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = (Н1/\Л2V Н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.
Ответ: 1423
Задание ( Задание В4 демоверсии 2008г)
Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров:
A) Макс победит, Билл – второй;
B) Билл – третий. Ник – первый;
C) Макс – последний, а первый – Джон.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
Какое место на турнире заняли Джон, Ник, Билл, Макс?
(В ответе перечислите подряд без пробелов места участников в указанном порядке имен.)
Пишите правильный ответ в комментариях
Подписывайтесь на мой канал и палец вверх 👍🏻 если статья понравилась
Всем мира и добра💐🌹🌺