\documentclass{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{titling}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amssymb}
\usepackage{amsthm}


\setlength{\droptitle}{-3.5cm}
\setlength{\parindent}{0cm}
\newcommand{\squad}{\hspace{0.5em}}

\author{Вишневский Глеб 187}
\title{Домашняя работа 1}
\usepackage
[
        a4paper,
        left=2cm,
        right=2cm,
        top=3cm,
        bottom=4cm
]
{geometry}

\begin{document}
\maketitle

\textbf{1.} a, b, c -- целые числа, для которых истинно высказывание
\begin{equation*}
    \neg (a = b) \wedge ((b < a) \to (2c > a)) \wedge ((a < b) \to (a > 2c))
\end{equation*}

Чему равно a, если c = 7, b = 16? \newline

\textbf{Решение} \newline
Для начала упростим данное выражение
\begin{equation*}
    \begin{array}{c}
        \neg (a = b) \wedge ((b < a) \to (2c > a)) \wedge ((a < b) \to (a > 2c) \Leftrightarrow \\
        \Leftrightarrow (a \ne b) \wedge (a \leq b \vee a < 2c) \wedge (a \geq b \vee a > 2c)
    \end{array}
\end{equation*}

Теперь подставим c = 7, b = 16 и получим:
\begin{equation*}
    (a \ne 16) \wedge (a \leq 16 \vee a < 14) \wedge (a \geq 16 \vee a > 14)
\end{equation*}

Единственное возможное значение a, при которых данное выражение истинно \textit{a = 15} \newline
\textbf{Ответ:} \textit{a = 15} \newline

\textbf{2.} Докажите, что
\begin{equation*}
    1 \oplus x_1 \oplus x_2 = (x_1 \to x_2) \wedge (x_2 \to x_1)
\end{equation*}

\textbf{Решение} \newline
Построим таблицу истинности для
$1 \oplus x_1 \oplus x_2 \quad \text{и} \quad (x_1 \to x_2) \wedge (x_2 \to x_1)$

\begin{displaymath}
    \begin{array}{|c c|c|c|}
        \hline
        x_1 & x_2 & 1 \oplus x_1 \oplus x_2 & (x_1 \to x_2) \wedge (x_2 \to x_1)\\
        \hline
        0 & 0 & 1 & 1\\
        0 & 1 & 0 & 0\\
        1 & 0 & 0 & 0\\
        1 & 1 & 1 & 1\\
        \hline
    \end{array}
\end{displaymath}

Заметим, что при любых $x_1 \quad \text{и} \quad x_2 \quad \text{значения} \quad 1 \oplus x_1 \oplus x_2 \quad \text{и} \quad (x_1 \to x_2) \wedge (x_2 \to x_1)$ равны. \\
Значит $1 \oplus x_1 \oplus x_2 = (x_1 \to x_2) \wedge (x_2 \to x_1) \qquad \blacktriangle$ \newline

\textbf{3.} Указать существенные и несущественные(фиктивные) переменные следующих функций:
\begin{equation*}
    \textbf{а)} \squad f(x_1, x_2, x_3) = 00111100 \qquad \textbf{б)} \squad g(x_1, x_2, x3) = (x_1 \to (x_1 \vee x_2)) \to x_3
\end{equation*}

\textbf{Решение} \newline
\textbf{а)} Построим таблицу истинности

\begin{displaymath}
    \begin{array}{|c c c|c|}
        \hline
        x_1 & x_2 & x_3 & f(x_1, x_2, x_3) \\
        \hline
        0 & 0 & 0 & 0\\
        0 & 0 & 1 & 0\\
        0 & 1 & 0 & 1\\
        0 & 1 & 1 & 1\\
        1 & 0 & 0 & 1\\
        1 & 0 & 1 & 1\\
        1 & 1 & 0 & 0\\
        1 & 1 & 1 & 0\\
        \hline
    \end{array}
\end{displaymath}

Заметим, что $f(0, 0, 0) = f(0, 0, 1), \squad f(0, 1, 0) = f(0, 1, 1), \squad f(1, 0, 0) = f(1, 0, 1), \squad f(1, 1, 0) = f(1, 1, 1)$. Значит, от изменения $x_3$ значение функции не меняется $\Rightarrow$ $x_3$ является несущественной(фиктивной) переменной. \newline

Так же $f(0, 0, 0) \ne f(1, 0, 0) \squad \text{и} \squad f(0, 0, 0) \ne f(0, 1, 0) \Rightarrow x_1 \squad \text{и} \squad x_2$ являются существенными переменными(при их изменении меняется значение функции) \newline
\textbf{Ответ:} $x_1$ и $x_2$ -- существенные переменные, $x_3$ -- несущественная переменная \newline

\textbf{б)} Упростим данное выражение
\begin{equation*}
    \begin{array}{c}
        ((x_1 \to (x_1 \vee x_2)) \to x_3 \Leftrightarrow \\
        \Leftrightarrow (\neg x_1 \vee x_1 \vee x2) \to x_3 \Leftrightarrow \\
        \Leftrightarrow x_2 \to x_3
    \end{array}
\end{equation*}

То есть $f(x_1, x_2, x_3) = x_2 \to x_3$. Значит, $x_1$ является несущественной переменной, а $x_2$ и  $x_3$ -- существенные переменные.

\textbf{Ответ:} $x_2$ и $x_3$ -- существенные переменные, $x_1$ -- несущественная переменная \newline

\textbf{4.} Постройте для функции f из предыдущей задачи \textbf{а) ДНФ; б) КНФ} \newline

\textbf{Решение} \newline
\textbf{а)} Из таблицы истинности построим \textit{ДНФ}

\begin{equation*}
    f(x_1, x_2, x_3) = (\neg x_1 \wedge x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge x_2 \wedge x_3) \vee (x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (x_1 \wedge \neg x_2 \wedge x_3)
\end{equation*}

\textbf{б)} Из таблицы истинности построим \textit{КНФ}

\begin{equation*}
    f(x_1, x_2, x_3) = (x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2 \vee \neg x_3)
\end{equation*}

\textbf{5.} Докажите формулу разложения:
\begin{equation*}
    f(x_1, \dots, x_n) = (x_1 \vee f(0, x_2, \dots, x_n)) \wedge (\neg x_1 \vee (f(1, x_2, \dots, x_n))
\end{equation*}

\textbf{Решение} \newline
Допустим $x_1 = 0$, тогда мы получим
\begin{equation}
    \begin{array}{c}
        (0 \vee f(0, x_2, \dots, x_n)) \wedge (1 \vee f(1, x_2, \dots, x_n)) \Leftrightarrow \\
        \Leftrightarrow f(0, x_2, \dots, x_n) \wedge 1 \Leftrightarrow f(0, x_2, \dots, x_n) = f(x_1, \dots, x_n)
    \end{array}
\end{equation}

Допустим $x_1 = 1$, тогда мы получим
\begin{equation}
    \begin{array}{c}
        (1 \vee f(0, x_2, \dots, x_n)) \wedge (0 \vee f(1, x_2, \dots, x_n)) \Leftrightarrow \\
        \Leftrightarrow 1 \wedge f(1, x_2, \dots, x_n) = f(x_1, \dots, x_n)
    \end{array}
\end{equation}
Из (1) и (2) следует, что при любом значении $x_1$ данная формула разложения является верной. $\qquad \blacktriangle$ \newline

\textbf{6.} Постройте ДНФ для функции $x_1 \to (x_3 \wedge \neg x_2 \leftrightarrow x_1)$. \newline

\textbf{Решение} \newline
Построим таблицу истинности

\begin{displaymath}
    \begin{array}{|c c c|c|}
        \hline
        x_1 & x_2 & x_3 & x_1 \to (x_3 \wedge \neg x_2 \leftrightarrow x_1) \\
        \hline
        0 & 0 & 0 & 1\\
        0 & 0 & 1 & 1\\
        0 & 1 & 0 & 1\\
        0 & 1 & 1 & 1\\
        1 & 0 & 0 & 0\\
        1 & 0 & 1 & 1\\
        1 & 1 & 0 & 0\\
        1 & 1 & 1 & 0\\
        \hline
    \end{array}
\end{displaymath}

Теперь из таблицы истинности построим ДНФ:
\begin{equation*}
    \begin{array}{c}
        x_1 \to (x_3 \wedge \neg x_2 \leftrightarrow x_1) \Leftrightarrow \\
        \Leftrightarrow (\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge \neg x_2 \wedge x_3) \vee (\neg x_1 \wedge x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge x_2 \wedge x_3) \vee (x_1 \wedge \neg x_2 \wedge x_3)
    \end{array}
\end{equation*}

\textbf{7.} Постройте ДНФ для функции $(x_1 \to x_2) \wedge (x_2 \to x_3) \wedge \dots \wedge (x_7 \to x_8)$. \newline

\textbf{Решение} \newline
Давайте исследуем данную функцию. Чтобы ее значение было истинной, надо чтобы каждая импликация была истинной. То есть, если какой-то $x_i = 1$, то $\forall j : j > i \; x_j = 1$, иначе мы получим $(x_i \to x_j) \Leftrightarrow (1 \to 0) \Leftrightarrow 0$. Итого мы имеем, что функция принимает 1 при наборах:

\begin{equation*}
    \begin{array}{c c c c c}
        x_1 & x_2 & x_3 & \dots & x_8 \\
        \hline
        1 & 1 & 1 & \dots & 1 \\
        0 & 1 & 1 & \dots & 1 \\
        0 & 0 & 1 & \dots & 1 \\
        0 & 0 & 0 & \dots & 0 \\
    \end{array}
\end{equation*}

Теперь давайте запишем ДНФ для данной функции

\begin{equation*}
    \begin{array}{c}
        (x_1 \to x_2) \wedge (x_2 \to x_3) \wedge \dots \wedge (x_7 \to x_8) \Leftrightarrow \\
        \Leftrightarrow \bigvee_{i = 0}^{8} ((\bigwedge_{j = 1}^{i} \neg x_j) \wedge (\bigwedge_{j = i + 1}^{8} x_j))
    \end{array}
\end{equation*}

\textbf{8.} Булевая функция $Phar(x_1, x_2, \dots, x_n)$ равна 1, если количество единиц нечетно и нулю, если четно. \newline

\textbf{а)} Выразите функцию $Phar(x_1, x_2, \dots, x_n)$ через известные булевые функции(можно использовать связки $\wedge$, $\vee$, $\neg$, $\oplus$, $\to$). \newline
\textbf{б)} Можно ли представить $Phar(x_1, x_2, \dots, x_n)$ в виде ДНФ без отрицаний? \newline

\textbf{Решение} \newline
\textbf{а)} Выразим данную функцию через $\oplus$
\begin{equation*}
    \begin{array}{c}
        Phar(x_1, x_2, \dots, x_n) = x_1 \oplus x_2 \oplus \dots \oplus x_n
    \end{array}
\end{equation*}

\textbf{б)} Если $n = 1$, то можно: $Phar(x_1) = x_1$. Если же $n > 1$, то нельзя. \newline
\textbf{Доказательство} \newline
(1) Если $n$ -- \textit{четное}, то в ДНФ всегда присутствует конъюнкт вида $(\neg x_1 \wedge x_2 \wedge \dots \wedge x_n)$, чтобы убрать отрицание с $x_1$, надо чтобы в ДНФ также присутствовал конъюнкт вида $(x_1 \wedge x_2 \wedge \dots \wedge x_n)$, но $Phar(1, 1, \dots, 1) = 0$ $\Rightarrow$ $(x_1 \wedge x_2 \wedge \dots \wedge x_n)$ нет в ДНФ $\Rightarrow$ мы не можем представить ДНФ без отрицаний. \newline
(2) Если же $n$ -- \textit{нечетное}, то в ДНФ всегда присутствует конъюнкт вида $(\neg x_1 \wedge \neg x_2 \wedge \dots \wedge \neg x_{n-1} \wedge x_n)$, чтобы убрать отрицание c $x_i \squad \forall i : 1 \leq i < n$, надо чтобы в ДНФ присутствовал конъюнкт вида $(\neg x_1 \wedge \dots \wedge \neg x_{i-1} \wedge x_i \wedge \neg x_{i+1} \wedge \dots \wedge \neg x_{n-1} \wedge x_n)$, но $Phar(0, \dots, 0, 1, 0, \dots, 0, 1) = 0$ $\Rightarrow$ такого конъюнкта нет в ДНФ $\Rightarrow$ мы не можем представить ДНФ без отрицаний. \newline

Из (1) и (2) $\Rightarrow$ при $n > 1$ $Phar(x_1, x_2, \dots, x_n)$ представить в виде ДНФ без отрицаний нельзя. $\qquad \blacktriangle$
\end{document}