Zapisz do kolekcji
Zaloguj się, aby dodać zadanie do kolekcji.
Zgłoś zadanie
Dziękuję za przesłanie zgłoszenia!
Twoje zaangażowanie pomaga mi rozwijać tę stronę i tworzyć miejsce z jeszcze lepszymi materiałami.
Data publikacji: 2025-10-28 00:36:00
Udowodnij prawdziwość poniższego zdania logicznego $ \newcommand{\Forall}[1]{ \substack{\Huge \forall \\\\ \normalsize #1} } \newcommand{\Exists}[1]{ \substack{\Huge \exists \\\\ \normalsize #1} } $
$$\color{Cyan}
\Exists{x}\bigg( P(x) \lor Q(x) \bigg)\; \equiv \;\;\Exists{x}P(x)\, \lor \;\,\Exists{x}Q(x)
$$
Podejdziemy do tego problemu w całkiem sprytny sposób. Udowodnimy negację podanego wyrażenia:
$$\color{Cyan}
\neg \Exists{x}\bigg( P(x) \lor Q(x) \bigg)\; \equiv \;\;\neg\Bigg(\Exists{x}P(x)\, \lor \;\,\Exists{x}Q(x)\Bigg)
$$
Implikuje ona bowiem zdanie widniejące w poleceniu.
W tym celu wykorzystamy znane prawa logiczne, aby drogą przekształceń przejść z wyrażenia po lewej stronie do tego po prawej: \begin{gather*}\color{Cyan} \neg \Exists{x}\bigg( P(x) \lor Q(x) \bigg)\;\\\\ \quad \small\textrm{Prawo De Morgana} \LARGE \updownarrow \small\;\;\textrm{zaprzeczenie kwantyfikatora}\\\\\color{Cyan} \Forall{x} \bigg[\neg \Big( P(x) \lor Q(x) \Big) \bigg]\\\\ \quad \small\textrm{Prawo De Morgana} \LARGE \updownarrow \small\;\;\textrm{zaprzeczenie alternatywy}\\\\\color{Cyan} \Forall{x} \bigg(\neg P(x) \;\land \;\neg Q(x) \bigg)\\\\ \qquad \qquad \qquad \qquad \LARGE \updownarrow \small \substack{\textrm{prawo rozdzielności kwantyfikatora} \\ \textrm{ogólnego względem koniunkcji}} \\\\\color{Cyan} \Forall{x}\bigg(\neg P(x)\bigg) \;\land \;\Forall{x}\bigg(\neg Q(x)\bigg)\\\\ \quad \small\textrm{Prawo De Morgana} \LARGE \updownarrow \small\;\;\substack{\textrm{zaprzeczenie kwantyfikatora} \\ \textrm{(ale w drógą stronę)}}\\\\\color{Cyan}\normalsize \neg \Exists{x}P(x)\;\land \;\neg \Exists{x}Q(x)\\\\ \quad \small\textrm{Prawo De Morgana} \LARGE \updownarrow \small\;\; \substack{\textrm{zaprzeczenie alternatywy} \\ \textrm{(ale w drógą stronę)}}\\\\\color{Cyan} \neg\Bigg(\Exists{x}P(x)\, \lor \;\,\Exists{x}Q(x)\Bigg)\\\\ \textrm{A zatem:}\\\\\color{Cyan} \neg \Exists{x}\bigg( P(x) \lor Q(x) \bigg)\; \equiv \;\;\neg\Bigg(\Exists{x}P(x)\, \lor \;\,\Exists{x}Q(x)\Bigg)\\\\ \LARGE \Downarrow \normalsize\\\\\color{#00dd66} \Exists{x}\bigg( P(x) \lor Q(x) \bigg)\; \equiv \;\;\Exists{x}P(x)\, \lor \;\,\Exists{x}Q(x) \\\\ \blacksquare \end{gather*}
W tym celu wykorzystamy znane prawa logiczne, aby drogą przekształceń przejść z wyrażenia po lewej stronie do tego po prawej: \begin{gather*}\color{Cyan} \neg \Exists{x}\bigg( P(x) \lor Q(x) \bigg)\;\\\\ \quad \small\textrm{Prawo De Morgana} \LARGE \updownarrow \small\;\;\textrm{zaprzeczenie kwantyfikatora}\\\\\color{Cyan} \Forall{x} \bigg[\neg \Big( P(x) \lor Q(x) \Big) \bigg]\\\\ \quad \small\textrm{Prawo De Morgana} \LARGE \updownarrow \small\;\;\textrm{zaprzeczenie alternatywy}\\\\\color{Cyan} \Forall{x} \bigg(\neg P(x) \;\land \;\neg Q(x) \bigg)\\\\ \qquad \qquad \qquad \qquad \LARGE \updownarrow \small \substack{\textrm{prawo rozdzielności kwantyfikatora} \\ \textrm{ogólnego względem koniunkcji}} \\\\\color{Cyan} \Forall{x}\bigg(\neg P(x)\bigg) \;\land \;\Forall{x}\bigg(\neg Q(x)\bigg)\\\\ \quad \small\textrm{Prawo De Morgana} \LARGE \updownarrow \small\;\;\substack{\textrm{zaprzeczenie kwantyfikatora} \\ \textrm{(ale w drógą stronę)}}\\\\\color{Cyan}\normalsize \neg \Exists{x}P(x)\;\land \;\neg \Exists{x}Q(x)\\\\ \quad \small\textrm{Prawo De Morgana} \LARGE \updownarrow \small\;\; \substack{\textrm{zaprzeczenie alternatywy} \\ \textrm{(ale w drógą stronę)}}\\\\\color{Cyan} \neg\Bigg(\Exists{x}P(x)\, \lor \;\,\Exists{x}Q(x)\Bigg)\\\\ \textrm{A zatem:}\\\\\color{Cyan} \neg \Exists{x}\bigg( P(x) \lor Q(x) \bigg)\; \equiv \;\;\neg\Bigg(\Exists{x}P(x)\, \lor \;\,\Exists{x}Q(x)\Bigg)\\\\ \LARGE \Downarrow \normalsize\\\\\color{#00dd66} \Exists{x}\bigg( P(x) \lor Q(x) \bigg)\; \equiv \;\;\Exists{x}P(x)\, \lor \;\,\Exists{x}Q(x) \\\\ \blacksquare \end{gather*}