Решение задач по логике №6, №7, №8, №9

Ниже представлено подробное решение задач №6, №7, №8 и №9, оформленное для переписывания в школьную тетрадь. Задача 6. Доказать равносильность формул \( \overline{x \leftrightarrow y} \) и \( \bar{x} \leftrightarrow y \). Доказательство проведем с помощью таблицы истинности: \[ \begin{array}{|c|c|c|c|c|c|} \hline x & y & x \leftrightarrow y & \overline{x \leftrightarrow y} & \bar{x} & \bar{x} \leftrightarrow y \\ \hline 0 & 0 & 1 & 0 & 1 & 0 \\ \hline 0 & 1 & 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 & 0 & 0 \\ \hline \end{array} \] Так как значения в столбцах для \( \overline{x \leftrightarrow y} \) и \( \bar{x} \leftrightarrow y \) полностью совпадают при всех наборах переменных, формулы равносильны. Что и требовалось доказать. Задача 7. Найти СДНФ и СКНФ для формулы \( f = x \lor y \to \overline{y \land z} \). 1) Составим таблицу истинности: \[ \begin{array}{|c|c|c|c|c|c|c|} \hline x & y & z & x \lor y & y \land z & \overline{y \land z} & f \\ \hline 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ \hline 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline \end{array} \] 2) СДНФ (составляем по строкам, где \( f=1 \)): \[ f_{СДНФ} = (\bar{x}\bar{y}\bar{z}) \lor (\bar{x}\bar{y}z) \lor (\bar{x}y\bar{z}) \lor (x\bar{y}\bar{z}) \lor (x\bar{y}z) \lor (xy\bar{z}) \] 3) СКНФ (составляем по строкам, где \( f=0 \), инвертируя значения переменных): Для строки (0,1,1): \( (x \lor \bar{y} \lor \bar{z}) \) Для строки (1,1,1): \( (\bar{x} \lor \bar{y} \lor \bar{z}) \) \[ f_{СКНФ} = (x \lor \bar{y} \lor \bar{z}) \land (\bar{x} \lor \bar{y} \lor \bar{z}) \] Задача 8. Найти область истинности предиката: \[ \frac{x^5 - 16x}{x^2 + 3x - 10} \le 0 \] Решение: 1) Разложим числитель: \( x(x^4 - 16) = x(x^2 - 4)(x^2 + 4) = x(x - 2)(x + 2)(x^2 + 4) \). 2) Разложим знаменатель: \( x^2 + 3x - 10 = (x + 5)(x - 2) \). 3) Перепишем неравенство: \[ \frac{x(x - 2)(x + 2)(x^2 + 4)}{(x + 5)(x - 2)} \le 0 \] ОДЗ: \( x \neq 2, x \neq -5 \). Сократим на \( (x - 2) \) и отбросим множитель \( (x^2 + 4) \), так как он всегда \( > 0 \): \[ \frac{x(x + 2)}{x + 5} \le 0, \quad x \neq 2 \] 4) Метод интервалов для точек \( -5, -2, 0 \): - На \( (-\infty; -5) \): знак \( (-) \) — подходит. - На \( (-5; -2] \): знак \( (+) \). - На \( [-2; 0] \): знак \( (-) \) — подходит. - На \( [0; 2) \cup (2; +\infty) \): знак \( (+) \). Ответ: \( x \in (-\infty; -5) \cup [-2; 0] \). Задача 9. 1) Привести к ПНФ формулу \( A \equiv \forall x (A(x) \to \exists y B(y)) \). Используем равносильность импликации \( P \to Q \equiv \neg P \lor Q \): \[ \forall x (\neg A(x) \lor \exists y B(y)) \] Выносим квантор \( \exists y \) за скобки (так как \( A(x) \) не зависит от \( y \)): \[ \forall x \exists y (\neg A(x) \lor B(y)) \] Это и есть предваренная нормальная форма. 2) Найти отрицание полученной формулы: \[ \neg (\forall x \exists y (\neg A(x) \lor B(y))) \equiv \exists x \forall y \neg (\neg A(x) \lor B(y)) \equiv \exists x \forall y (A(x) \land \neg B(y)) \] Ответ: ПНФ: \( \forall x \exists y (\neg A(x) \lor B(y)) \); Отрицание: \( \exists x \forall y (A(x) \land \neg B(y)) \).