$\newcommand{\block}[2]{\begin{#1} #2 \end{#1}}$ $\newcommand{\cases}[1]{\block{cases}{#1}}$ $\newcommand{\up}[2]{\stackrel{#1}{#2}}$ $\def\dn#1#2{\mathrel{\mathop{#2}\limits_{#1}}}$ $\def\ident{\Longleftrightarrow}$ $\def\thus{\Rightarrow}$ $\newcommand{\set}[1]{ \{ #1 \} }$ $\newcommand{\bigset}[1]{ \left \{ #1 \right \} }$ $\newcommand{\bracs}[1]{ ( #1 ) }$ $\newcommand{\bigbracs}[1]{ \left ( #1 \right ) }$ $\newcommand{\bkets}[1]{\langle #1 \rangle}$ $\newcommand{\bigbkets}[1]{\left \langle #1 \right \rangle}$ $\newcommand{\mat}[1]{\block{Vmatrix}{#1}}$ $\newcommand{\det}[1]{\block{vmatrix}{#1}}$ $\newcommand{\pmat}[1]{\block{pmatrix}{#1}}$ $\newcommand{\emat}[1]{\block{matrix}{#1}}$ $\renewcommand{\geq}{\geqslant}$ $\renewcommand{\leq}{\leqslant}$ $\newcommand{\upline}[1]{\overline{#1}}$ $\newcommand{\dnline}[1]{\underline{#1}}$ $\def\ex{\exists}$ $\def\exo{\ex!}$ $\renewcommand{\fal}{\forall}$ $\renewcommand{\int}{\intop}$ $\def\inf{\infty}$ $\renewcommand{\tg}{\tan}$ $\renewcommand{\phi}{\varphi}$ $\renewcommand{\epsilon}{\varepsilon}$ $\def\alp{\alpha}$ $\def\lam{\lambda}$ $\def\gam{\gamma}$ $\def\eps{\epsilon}$ $\def\sig{\sigma}$ $\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\CC}{\mathbb{C}}$ $\newcommand{\FF}{\mathbb{F}}$ $\newcommand{\QQ}{\mathbb{Q}}$ $\newcommand{\EE}{\mathbb{E}}$ $\newcommand{\UU}{\mathcal{U}}$ $\newcommand\E{\mathbbold{e}}$ $\newcommand\F{\mathbbold{f}}$ $\newcommand\G{\mathbbold{g}}$ $\newcommand{\rawOlim}[3]{\dn{{#1}\rightarrow{#2}}{#3}}$ $\newcommand{\lim}[2]{\rawOlim{#1}{#2}{lim}}$ $\newcommand{\uplim}[2]{\rawOlim{#1}{#2}{\upline{lim}}}$ $\newcommand{\dnlim}[2]{\rawOlim{#1}{#2}{\dnline{lim}}}$ $\newcommand{\norm}[1]{\left \lVert #1 \right \rVert}$ $\newcommand{\ord}[1]{\operatorname{ord}(#1)}$ $\newcommand{\ans}[1]{\textbf{Ответ}: #1.}$ $\renewcommand{\gcd}{\text{НОД}}$ $\newcommand{\lcm}{\text{НОК}}$ $\newcommand{\proj}[2]{\text{пр.}_{#1}{#2}}$ $\newcommand{\U}[2]{U_{#1}(#2)}$ # Дискретная математика ```{contents} Содержание --- depth: 2 ``` Шапкин Павел Александрович p.shapkin@gmail.com Дать свои контакты [сюда](https://bit.ly/3RkZHhC) Выполняем дз, сдаём преподу семинара Контрольные через online.mephi.ru (Modle LMS) ## Литература - Гаврилов, Сапоженко - Задачи и управжнения по Д. М. - Новиков - Дискретная математика для программистов - Гильбер, Аккерман - Основы теоретическогй логики - Горбатов - Фундаментальные основы Д. М. - Вольфенгаген - Логика ## Разбалловка 100 баллов 60 мин 3 раздела, каждый раздел по 20 баллов: - 10 баллов за дз - 8 баллов за контрольную - 2 балла за работу на семах (мин по 12) до 40 баллов за экзамен / зачёт (мин 24) ## ЛЕК 1 Множество $\mathbb{R}$ (вещественные числа) - непрерывно Множество $\mathbb{N}$ (целые числа) - дискретно Значения истинности (булавы значения / boolean): 0, 1 - False, True - $\Downupsilon$, $\Upupsilon$ Карри-Говард (система типизации 🤝 логика) Логика - наука о получении истинных суждений на основе других истинных суждений Высказывание (суждение) - любое истинное или ложное предложение Например: "Москва - столица франции" Приказ, вопрос, опредение - не высказывание Два высказывания называются равными, если их значения истинности совпадают Значит $a = b$ Высказывание: - значение / экстенсия (объём) - смысл / интенсия (содержание) <фоточка> Высказывательная переменная - переменная, пробегающая (принимающая) значения истинности (a, b, c, d ...) Высказывания могут быть: - постоянные - переменные Высказывание могут быть: - простыми (никакая часть не является высказыванием само по себе) - составными ## ЛЕК 2 > Функцией называется некое соответствие, по которому каждому значению аргумента функции ставится одно и только одно значение функции. > Область значений (кодомен) Область определения (домен) Область определения и область значения функции — часть определения функции. $f: A \rightarrow B$ $f(x) =x^2\ \ f: x \rightarrow x^2$ > Высказывательная функция — это функция, у которой и область определения и область значений — это значения истинности. > > > > Функция, которая определена на области значений истинности и принимает значения истинности: > > $\{0,1\} \rightarrow \{0,1\}$ > Число различных комбинаций из $0, 1$ длинны $N$ — $2^N$ > Функции называются равными, если они принимают равные значения на всех совпадающих наборах аргументов. > Число различных высказывательных функций от N аргументов: $2^{2^N}$ Таблица истинности высказывательной функции — таблица, в которой записаны значения функции для всех возможных значений её аргументов. Основные высказывательные функции: 1. Отрицание (унарная связка) Отрицанием высказывания $A$ называется высказывание истинное, если $A$ - ложное, и ложное в противном случае.
$\bar a,\ \ \text{NOT }a,\ \lnot a$
”Не $a$” “Неверно, что $a$”
2. Дизъюнкция — логическое сложение Дизъюнкцией двух высказываний называется высказывание истинное тогда, когда истинно хотя бы одно из исходны высказываний и ложное в противном случае.
$a \vee b$
$a + b$
OR ”$a$ или $b$” — включающее или
3. Конъюнкция — логическое умножение: Конъюнкцией двух высказываний называется высказывание истинное в том случае, если истины оба исходных высказывания и ложное в противном случае.
$a \cdot b, ab, a \wedge b$
AND ”$a\text{ и }b$”
“Известно, что: 1) a, 2) b” 4. Импликация — логическое следование, слабое неравенство Импликацией двух высказываний называется такое высказывание, которое ложно, если первое высказывание истинно, а второе ложно, и истинное в противным случае. $a \rightarrow b$ $a$ ≤ $b$ $a \Rightarrow b$
$a \rightarrow b=\bar a \lor b$
”если $a$, то $b$” “$b$, если $a$” если = когда

a - посылка
b - следствие

Посылка — достаточное условие
Следствие — необходимое условие
”$a$ достаточно для $b$”
”$b$ необходимо для $a$”
5. Эквивалентность (алгебраическое равенство) Эквивалентностью двух высказываний называется высказывание истинное, если значение истинности двух исходных высказываний равны, ложное в противном случае. $a=b\ \ \ \ a \longleftrightarrow b$
$a \longleftrightarrow b=(a \rightarrow b) \land (b \rightarrow a) = ab \lor \bar{ab}$
”В точности тогда и только тогда” iff
6. Сложение по Жегалкину
$a \oplus b$
XOR - исключающее или
## ЛЕК 3 $2^{2^n}$ допустим $n=0$ $2^{2^0}=2^1=2$ - $0,1$ если $n=1$ $2^{2^1}=2^2=4$ - $1,0,1$ если $n=2$ $2^{2^n}=2^4=16$ Все уникальные функции: $x, y$ | $0$ | $x \cap y$ | $\upline {x \rightarrow y}, >$ | $x$ | $\upline {y \rightarrow x}, <$ | $y$ | $x\oplus y$ | $x\cup y$ | $\upline {x \cup y}, \downarrow, \circ$ | $x=y, \leftrightarrow$ | $\upline y$ | $y \rightarrow x, \geq$ | $\upline x$ | $x\rightarrow y, \supset, \leq, \rightarrow$ | $\upline {x \cap y}, \uparrow$ | $1$ ----|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|- 00 | 0|0|0|0|0|0|0|0|1|1|1|1|1|1|1|1 01 | 0|0|0|0|1|1|1|1|0|0|0|0|1|1|1|1 10 | 0|0|1|1|0|0|1|1|0|0|1|1|0|0|1|1 11 | 0|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1 $x,y$ | $x\rightarrow, x\leq y,\upline x \cup y$ -|- 00 | 1 01 | 1 10 |0 11|1 Высказывательная функиця (семантика) $\rightarrow$ Формулы (синтаксис) Определение (высказыватенльные функции) (1) переменные и функции - атомарные высказывательные формулы (x, y, ...) (0, 1) (2) если F - некоторая формула, то $\neg F$ - тоже формула (3) если F и G - формулы, а $\cdot$ - бинарная логическая связка, то $F \odot G$ - формула Алфавит: - $a, b, c \dots, x, y \dots$ - $0, 1$ - $\neg, \rightarrow, \cup, \cap$ $x \oplus z$ Приоритет операций (правила "восстановления" скобок) 1) $\neg$ 2) $\cup, \cap$ 3) все остальные ... $a \cap b \rightarrow c = (a\cap b) \rightarrow c$ $x \rightarrow y \rightarrow z$ - некоректна, невозможно "расставить скобки" $(x \rightarrow y) \rightarrow z \neq x \rightarrow (y \rightarrow z)$ $x \oplus y \rightarrow z = (c \oplus y) \rightarrow z$ Определение Две формулы являются равносильными, если они соответствуют одной и той де высказательной функции формулы равносильны, если все их интепретации совпадают Определение интерпретация формулы - подстановка значений (истинности) вместо переменных оттуда и берутся таблицы истинности в интепретации формула получает значение истинности таблица истинности (ТИ) - свод всех возможных интепетаций Определение 1) Тавтология - формулы, истинна в любой интерпретации 2) Противоречие - формула, ложная во всех интерпретациях 3) Выполнимая формула - имеющая хотя бы одну истинную интепретацию 4) Опровержиамя - формула, имеющая хотя бы одну ложную интерпертацию $Тавт \rightarrow Выполн$ $Опр \rightarrow not Тавт$ $Прот \rightarrow Опр$ $Выо \rightarrow not Прот$ $not Опров \rightarrow Тавт$ $not Выо \rightarrow Прот$ Теорема Если формулы F и G равносильны, то формула $F \leftrightarrow G$ - тавтология и наоборот Законы ложных высказываний - Законы Булевой алгебры 1) комутативность $a \cup b = b \cup a$ 2) ассоциативность $(a \cup b) \cup c = a \cup (b \cup c)$ 3) дистрибутивность $a \cap (b \cup c) = a \cap b \cup a \cap c$ 4) законы постоянных $a\cup1=a$ $a\cup0=0$ 5) знаконы отрицания $a\cup\upline a= 1$(закон исключения третьего), $a\cap\upline a = 0$(закон противоречия) - Другие законы $\cap \cup$ 1) Поглощения $a\cup ab = a$ $a \cap (a \cup b) = a$ 2) Склеивание $ab \cup a \upline b = a$ $(a\cup b) \cap (a \cup \upline b) = a$ - Законы отрицания 1) $\upline {\upline a} = a$ (закон инвалюции) 2) де Моргана $\upline {a \cup b} = \upline a \cap \upline b, \upline {a \cap b} = \upline a \cup \upline b$ - Законы доминирования $a\cap0=0$ $a\cup1=1$ - Законы идемпотентности $a\cap a = a$ $a \cup a=a$ $f(x)$ - идемпотентна, если $f(x)=f(f(x)) \thus f(\dots f(f(x)))$ Законы импликации 1) Modus poneus $(a \rightarrow b) \cap a \rightarrow b$ 2) Правила слединения/разединения посылок $a \rightarrow (b \rightarrow c) = a\cap \rightarrow c$ 3) Правила перестановки $a\rightarrow(b\rightarrow c)=b\rightarrow(a\rightarrow c)$ ## ЛЕК 3.10.22 Нормальная форма вычислительных функций | x y | f | | |-|-|-| | 0 0 | 1 | $x\rightarrow y$| | 0 1 | 1 | $\not x \cup y$| |1 0 | 0 | $\not {x \not {y}}$| |1 1 | 1 |($x\rightarrow y$) \cup 0| сементические 1 синтаксические $\inf$ Первичный терм - переменная или её отрицание $x, \not x$ - первичные $xy, \not{xy}$ - не первич Элементарная коньюнкция - конъюнкция первичных термов ДНФ - дизьюнкция элементарной конюнкции (влючаем одну элементарнцю коньнкцию) пример $\upline x \cup y$ - ДНФ $a\upline b \cup \upline {ab}$ - ДНФ $x(\upline y \cup \upline z)$ - не ДНФ Любая функция может бысть представлена в виде ДНФ док-во (алгоримт приведения к ДНФ) $(a \rightarrow b ) \cap c = \upline {\upline a \cup b} \cap c = \upline{\upline a} \cup \upline b \cup c = a\upline b c$ 1) приут через ОБО (по соответс значениям) 2) опуск отрицания (по д-моргану) 3) раскрытие скобок Теорема элементарная коньюнкция содержащая все переменные заданной функции принимает значение 1 в одной т элементарная коньюнкция содержащая все переменные заданной функции - конституэтнтая еденица опр совершенная ДНФ - дизюнкия конституэнтых единиц $k_1 \cup k_2 \cup \dots k_n$ теорема СДНФ соответствует функции (таблице истинности) Сведение к СДНФ 1) свести к ДНФ $\upline a c \cup b c = \upline a c(b \cup \upline b) \cup bc(b \cup \upline b) = \upline a b c \cup \upline {ab} c \cup abc\cup \upline a bc = \upline a b c \cup \upline {ab} c \cup abc$ Двойственность - $x \rightarrow x$ $\not \rightarrow \not$ $\cup \rightarrow \cap$ $\cap \rightarrow \cup$ $1 \rightarrow 0$ $0 \rightarrow 1$ КНФ - конюнкция элементарной дизюнкции конституэнтый ноль - элементарная дизбюнкция содержащая все Импликанта - ## ЛЕК 10.10.22 Функциональная полнота Логические базисы #### Определение Функция $f(x_1, \dots x_n)$ называется суперпозицией в некоторой системе функций, если функиця получена по следующим правилам: 1) порём переименованиям аргументов некой функции 2) петём подстановкий в .. агрументов в некоторую функцию 3) правила (1) и (2) могут применяться сколько угодно раз Пример $S = \set{\phi_1(x, y), \phi_2(a)}$ $f(x,y,z) = f_1(f_2(x), f_1(y, f_2(z)))$ $S = \set{\cup, \cap}$ $f(x, y, z) = x \cup (y \cap z)$ - инфексная запись $= f_1(x, f_2(y, z))$ - префиксная записать #### Определение Система (высказываний) фукнция называется функционально полной, если любую (высказывательная) функцию можно представить в виде суперпозиции этой системы Функцияльно полная система функция - базис Пример ОБО - функциально полная система - булевый базис $\set{\cap, \upline{}}$ - коньюктивный базис ... - дизюктивный базис Теорема Если система функция $S_1$ является функ полной и все фукнции системы представимы как суперпозиции функций системы $S_2$, то $S_2$ - функционально полна $x\cup y = \upline{\upline{x\cup y}} = \upline{\upline x \cap \upline y}$ $\set{\cup, \cap, \upline{}}$ - ф.п. $\thus \set{\cap, \upline{}}$ - ф.п. Штрих шейхера - $x|y = \upline{x \cap y}$ $x|x = \upline{x\cap x} = \upline x$ $x\cap y = \dots = (x|y)|(x|y)$ $x\cup y = \dots = (x|x)|(y|y)$ $\thus \set{|}$ - базис шейфера Определение Замкнутый класс/система функций называется замкнутым, если любая суперпозиция фунций этой системы является функцией из этой системы Критерий Поста-Яблонского (критерий функциональной полноты высказывательных функций) - если система полностью не лежит в одном из 5 "замечательных" классов 1) функции сохраняюще константу 0 2) функции сохраняюще константу 1 3) самодвойственные функции 4) монотонные функции 5) линейные функции Замечательные классы: Определение $f(x_1 \dots x_n)$ сохраняет константу 0, если $f$ от всех нулей = 0 Определение Функция $f(x_1 \dots x_n)$ монотонная, если для наборов значений $x_1 \dots x_n$ и $y_1 \dots y_n$ таких, что $x_i\leq y_i$ , то $f(x_1 \dots x_n) < f(y_1 \dots y_n)$ Определение Функция $f(x_1 \dots x_n)$ называется линейной (по жегалкину) если её можно представить в виде $f(x_1 \dots x_n) = C_0 \oplus C_1 x_1 \oplus \dots C_n x_n$ $C_i=$ 0 или 1 Примеры $x\leftrightarrow y = \upline{x\not\leftrightarrow y} = \upline{x \oplus y} = 1\oplus x \oplus y$ - для линейности $C_0=C_1=C_2=1$ Построим $f(a,b,c) = C_0 \oplus C_1 a \oplus C_2 b \oplus C_3 c$ $f(0,0,0) = C_0\oplus 0 \oplus 0 \oplus 0 = C_0$ если $f() = f$ для всех наборов, то $f$ линейный, если нет - то не линейный Проверка состемы по критериям | |T_0|T_1|S|M|L| |-|-|-|-|-|-| |$\cup$|+|+|-|+|-| |$\cap$|+|+|-|+|-| |$\upline{}$|-|-|+|-|+| Предикаты ## ЛЕК 31.10.22 Система называется разрешимой если существует метод проверки каждой формулы на общезначимость Логика предикатов не разрешима Логика высказываний разрешима #### Методы проверки формул логики предикатов на общезначимость 1) восходящий анализ 2) нисходящий анализ - метод семантических таблиц Бета (Beth) - цельсон минц, математическая теория логического вывода #### Метод семантических таблиц Бета: - строим систему таблиц, в которой заполняются области истинности - два столбца, левый и правый столбец - подтаблицы Пример $\fal x (P(x) \rightarrow Q(x)) \rightarrow (\fal x P(x) \rightarrow \fal x Q(x))$ |$\Downupsilon$|$\Upupsilon$| |-|-| |$(1) \fal x (P(x) \rightarrow Q(x))$ из (0)|$(0) \fal x (P(x) \rightarrow Q(x)) \rightarrow (\fal x P(x) \rightarrow \fal x Q(x))$| |$(3) \fal x P(x)$ из (2)|$(2) \fal x P(x) \rightarrow \fal x Q(x)$ из (0)| |$(6) P(a) \rightarrow Q(a)$ из (1) и а|$(4) \fal x Q(x)$ из (3)| |$(7) P(a)$ из (3) и а|$(5)Q(a)$ из (4)| Первый подстолбец |I|II| |-|-| ||$(9) Q(a)$ из (6)| Второй подстолбец |I|II| |-|-| |$(8) P(a)$ из (6)|| Кримерий остановки - таблица закрыта, значит формула общезначима Таблица закрыта, если все подтаблицы закрыты Во всех случаях пришли к противоречиям Значит формула общезначима Метод бета 1) исходная формула записывается в $\Upupsilon$ 2) по правилам в $\Upupsilon$ и $\Downupsilon$ заносятся в предположени Правила - $\rightarrow $ $A \rightarrow B$ в $\Upupsilon$ разделение A в $\Downupsilon$ B в $\Upupsilon$ - $\rightarrow $ $A \rightarrow B$ в $\Downupsilon$ А в $\Upupsilon$ B в $\Downupsilon$ - $\fal$ $\fal x F(x)$ в $\Upupsilon$ $F(p)$ в $\Upupsilon$ Для каждого предиката - $\fal$ $\fal x F(x)$ в $\Downupsilon$ Ввести новый предмет p и занети F(b) в $\Downupsilon$ - $\ex$ $\ex x F(x)$ в $\Upupsilon$ вводим новый предмет p и занести F(p) в $\Upupsilon$ - $\ex$ $\ex x F(x)$ в $\Downupsilon$ F(p) заносим в $\Downupsilon$ для каждого предмета p - $\upline F$ в $\Upupsilon$ F в $\Downupsilon$ - $\upline F$ в $\Downupsilon$ F в $\Upupsilon$ - $\cap$ $A \cap B$ в $\Upupsilon$ А в $\Upupsilon$ В в $\Downupsilon$ - $\cap$ $A \cap B$ в $\Downupsilon$ А в $\Downupsilon$ B в $\Upupsilon$ - $\cup$ $A \cup B$ в $\Upupsilon$ А в $\Upupsilon$ B в $\Upupsilon$ - $\cup$ $A\cup B$ в $\Downupsilon$ А в $\Downupsilon$ В в $\Downupsilon$ ## СЕМ 9.10.22 Трифоненков Андрей Владимирович avtrifonenkov@mephi.ru ### Метод семанитических таблиц Бета Эверт Виллей Бет - нидерландский логик Истользуется для проверки формул на общезначимость Общезначимость - истинность в любой интерпретации Интерпретация формулы - совокупность: 1) множества определения предикатов М 2) поставленных в соответствие значений - предикатным переменным - высказывательным переменных - предметным переменным $\fal x P(x)$ --- x - "действительное число" P(x) - "$x \in \RR$" --- x - "собака" P(x) - "х имеет 4 лапы" метод бета основан на построении контрпримера: такой интерпретации при которой формула, проверяемая на общезначимость формула ложна #### Задача 1 Проверить общезначимость формулы $\fal x (P(x) \cup Q(x)) \rightarrow \fal x P(x) \cup \fal x Q(x)$ |Истина|Ложь| |-|-| |$\fal x (P(x) \cup Q(x))$ (1)|$\fal x P(x) \cup \fal x Q(x)$ (2)| |$P(a) \cup Q(a)$ (7)|$\fal x P(x)$ (3)| |$P(b) \cup Q(b)$ (8)|$\fal x Q(x)$ (4)| ||$P(a)$ (5) ввели переменную а| ||$Q(b)$ (6) ввели предмет b| подразбиваем |I|II|I|II| |-|-|-|-| |$P(a)$ (9) - противоречит (5) закрываем|$Q(a)$ (10)|по (9) закрываем|| подразбиваем | | |III|IV| | |III|IV| |-|-|-|-|-|-|-|-| |||$P(b)$ (11)|$Q(b)$ (12) противоречит (6), закрываем||||по (12) закрываем| | |P(x)|Q(x)| |-|-|-| |a|0|1| |b|1|0| $M = \set{a,b}$ При интерпретации М исходная формула ЛОЖНА $\thus$ исходная формула НЕ общезначима 1) Все выводы об истинности любой части формулы - в левой части исходной таблицы ... о ложности, правой ... формулы ... в правой смотри ЛЕК 31.10.22 --- Все подтаблицы закрыты $\thus$ невозможно построить конрпример $\thus$ исходная формула общезначимости ## СЕМ 16.11.22 Приведение логики предикатов к нормальным формулам Приведённая и предварённая I) Предвоаённая нормальная форма (ПредНФ) $G(x_1, \dots, x_n)$ в которой используются кванторы равносильна $K_1x_1 \dots K_nx_n F(x_1, \dots, x_n)$ где F кванторов не содержит Любая формула ЛП логики предикатов может быть предствалена в ПредНФ Алгоритм приведения к ПредНФ - перейти к ОБО - "спустить" отрицания с кванторов на Элементарные формулы ЛП (по законам де-моргана) $\upline{\fal x P(x)} = \ex x \upline{P(x)}$, $\upline {\ex x P(x)} = \fal x \upline{P(x)}$ - переименовать переменные так, чтобы кванторы действовали на разноимённые переменные (избежать колизий) - вынести кванторы в начало формулы, в том числе пользуясь законами вынесения кванторов в начало: $\fal xP(x) \cap \fal x Q(x) = \fal x(P(x)\cap Q(x))$, $\fal x P(x) \cup \fal x Q(x) = \fal x \fal y (P(x)\cup Q(y))$, $\ex x P(x) \cap \ex x Q(x) = \ex x \ex y (P(x)\cap Q(y))$, $\ex x P(x) \cup \ex x Q(x) = \ex x(P(x) \cup Q(x))$ II) Приведённая нормальная форма (ПравНФ) - применяется ОБО - отрицание действует только на элементарные формулы ЛП #### Задача 1 $\ex y (\ex x P(x) \cap \upline{Q(y)}) \cup R(z) =$ $= \ex y \ex x (P(x) \cap \upline{Q(y)}) \cup R(z) =$ $= \ex y \ex x (P(x) \cap \upline{Q(y)} \cup R(z)) =$ $= \ex x \ex y (P(x) \cap \upline{Q(y)} \cup R(z))$ - ПредНФ #### Задача 2 $\fal x \ex y P(x,y) \cap \upline{\ex x \fal y Q(x,y)} =$ $= \fal x \ex y P(x,y) \cap \fal x \ex y \upline{Q(x,y)} =$ $= \fal x (\ex y P(x,y) \cap \ex y \upline{Q(x,y)}) =$ $= \fal x (\ex y_1 P(x,y_1) \cap \ex y_2 \upline{Q(x,y_2)}) =$ $= \fal x \ex y_1 \ex y_2 (P(x,y_1) \cap \upline{Q(x,y_2)})$ #### Задача 3 $\fal x \ex x P(x,y,z) \leftrightarrow R(y,z) =$ $= (\upline{\fal z\ex x P(x,y,z)} \cup R(y,z)) \cap (R(y,z) \cup \fal z \ex x P(x,y,z)) =$ $= (\ex z \fal x \cup R(y,z)) \cap (\upline{R(x,z) \cup \fal z \ex x P(x,y,z)})$ или $= (\fal z \ex x P(x,y,z) \cap R(y,z) \cup (\upline{\fal z \ex x P(x,y,z)} \cap \upline{R(y,z)})) =$ $= (\fal z \ex x P(x,y,z) \cap R(y,z) \cup (\ex z \fal x \upline{P(x,y,z)} \cap \upline{R(y,z)})) =$ #### Задача 4 $\upline{\ex P(x,y,z) \rightarrow \fal x \ex y R(x,y,z)} \downarrow T(x,z) =$ $$