Докажи, что ¬(A → B) эквивалентно A ∧ ¬B

Привет! Давай разберёмся с этими логическими задачками. Это похоже на головоломки, где нужно доказать, что две фразы означают одно и то же. В этих заданиях мы будем использовать законы алгебры логики. ### Законы логики Давай вспомним основные обозначения: * $A \wedge B$ — это «И» (конъюнкция). Истинно, только если и $A$, и $B$ истинны. * $A \vee B$ — это «ИЛИ» (дизъюнкция). Истинно, если хотя бы одно из $A$ или $B$ истинно. * $\overline{A}$ (или $¬A$) — это «НЕ» (отрицание). Меняет истину на ложь и наоборот. * $A \to B$ — это «ЕСЛИ...ТО» (импликация). Ложно, только если $A$ истинно, а $B$ ложно. * $A \leftrightarrow B$ — это «ТОГДА И ТОЛЬКО ТОГДА» (эквивалентность). Истинно, если $A$ и $B$ оба истинны или оба ложны. А теперь по порядку: 1) Докажем, что $\overline{(A \to B)}$ это то же самое, что и $A \wedge \overline{B}$. * Выражение $A \to B$ («если A, то B») — это как обещание. Оно нарушается (становится ложным) только в одном случае: если условие $A$ выполнилось, а следствие $B$ — нет. * Значит, отрицание $\overline{(A \to B)}$ будет истинным, только когда $A$ — истинно, а $B$ — ложно. * Выражение $A \wedge \overline{B}$ как раз и означает «$A$ истинно И $B$ ложно». * Получается, оба выражения описывают одну и ту же ситуацию. Они эквивалентны! 2) Докажем, что $A \to \overline{B}$ это то же самое, что и $B \to \overline{A}$. Это правило называется законом контрапозиции. Давай на примере: * Пусть $A$ — «идёт дождь», а $B$ — «на улице сухо». * $A \to \overline{B}$ читается: «Если идёт дождь, то на улице НЕ сухо (т.е. мокро)». * $B \to \overline{A}$ читается: «Если на улице сухо, то дождь НЕ идёт». * Оба утверждения говорят об одном и том же. Они эквивалентны. 3) Докажем, что $A \leftrightarrow B$ это то же самое, что и $\overline{A} \leftrightarrow \overline{B}$. * $A \leftrightarrow B$ означает, что $A$ и $B$ всегда принимают одинаковое значение: либо оба истинны, либо оба ложны. * $\overline{A} \leftrightarrow \overline{B}$ означает, что отрицания $A$ и $B$ тоже всегда одинаковы. А это возможно только если сами $A$ и $B$ были одинаковыми. * Например, если $A$ и $B$ оба истинны, то $\overline{A}$ и $\overline{B}$ оба ложны — эквивалентность верна. Если $A$ и $B$ оба ложны, то $\overline{A}$ и $\overline{B}$ оба истинны — тоже верна. Они эквивалентны. 4) Докажем, что $A \vee (\overline{A} \wedge B)$ это то же самое, что и $A \vee B$. Это можно доказать, раскрыв скобки по распределительному закону: $$A \vee (\overline{A} \wedge B) = (A \vee \overline{A}) \wedge (A \vee B)$$ Выражение $(A \vee \overline{A})$ всегда истинно (ведь что-то одно из них точно правда). Обозначим истину как $1$. $$1 \wedge (A \vee B) = A \vee B$$ Что и требовалось доказать. 5) Докажем, что $(A \vee B) \wedge (A \vee \overline{B})$ это то же самое, что и $A$. Снова используем распределительный закон, но в обратную сторону: $$(A \vee B) \wedge (A \vee \overline{B}) = A \vee (B \wedge \overline{B})$$ Выражение $(B \wedge \overline{B})$ всегда ложно (не может быть одновременно и $B$, и не-$B$). Обозначим ложь как $0$. $$A \vee 0 = A$$ Доказано! 6) Докажем, что $A \to (B \to C)$ это то же самое, что и $(A \wedge B) \to C$. Представим, что $A$ — «на улице солнечно», $B$ — «у меня есть свободное время», $C$ — «я пойду гулять». * $A \to (B \to C)$ означает: «Если на улице солнечно, то (если у меня есть свободное время, то я пойду гулять)». * $(A \wedge B) \to C$ означает: «Если на улице солнечно И у меня есть свободное время, то я пойду гулять». * Оба предложения передают одну и ту же мысль. Значит, они эквивалентны. 7) Докажем, что $A \wedge (C \to B) \vee (A \to C) \wedge B$ это то же самое, что и $(A \vee B) \wedge (B \vee \overline{C})$. Это выглядит сложнее, но решается так же, через упрощение. Сначала заменим импликации ($X \to Y = \overline{X} \vee Y$): $$A \wedge (\overline{C} \vee B) \vee (\overline{A} \vee C) \wedge B$$ Раскроем скобки: $$(A \wedge \overline{C}) \vee (A \wedge B) \vee (\overline{A} \wedge B) \vee (C \wedge B)$$ Сгруппируем слагаемые с $B$: $$(A \wedge \overline{C}) \vee ((A \vee \overline{A}) \wedge B) \vee (C \wedge B)$$ Так как $A \vee \overline{A} = 1$ (истина): $$(A \wedge \overline{C}) \vee B \vee (C \wedge B)$$ По закону поглощения $B \vee (C \wedge B) = B$, получаем: $$(A \wedge \overline{C}) \vee B$$ Теперь применим распределительный закон: $$(A \vee B) \wedge (\overline{C} \vee B)$$ Это в точности правая часть исходного выражения. Доказано! 8) Упростим выражение $(A \wedge B) \vee (\overline{A} \wedge B) \vee (A \wedge \overline{B})$ и приведём свой пример. **Упрощение:** Сгруппируем первые два слагаемых и вынесем $B$ за скобку: $$((A \vee \overline{A}) \wedge B) \vee (A \wedge \overline{B})$$ Так как $A \vee \overline{A}$ всегда истинно (равно 1): $$(1 \wedge B) \vee (A \wedge \overline{B}) = B \vee (A \wedge \overline{B})$$ Теперь раскроем скобки по распределительному закону: $$(B \vee A) \wedge (B \vee \overline{B})$$ Так как $B \vee \overline{B}$ всегда истинно (равно 1): $$(B \vee A) \wedge 1 = B \vee A$$ **Ответ:** Исходное выражение упрощается до $A \vee B$. **Мой пример логической эквивалентности:** Давайте докажем один из законов де Моргана: $\overline{(A \wedge B)}$ эквивалентно $\overline{A} \vee \overline{B}$. * Пусть $A$ — «я надену шапку», $B$ — «я надену шарф». * $A \wedge B$: «я надену шапку И шарф». * $\overline{(A \wedge B)}$: «НЕВЕРНО, что я надену шапку и шарф». Это значит, я не надену что-то одно из них или не надену оба предмета. * $\overline{A} \vee \overline{B}$: «я НЕ надену шапку ИЛИ я НЕ надену шарф». * Как видишь, оба выражения означают одно и то же! Они эквивалентны.