\(\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)}\)

Дискретная математика#

Шапкин Павел Александрович p.shapkin@gmail.com
Дать свои контакты сюда

Выполняем дз, сдаём преподу семинара
Контрольные через 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§ в \(\Upupsilon\)

    • \(\ex\) \(\ex x F(x)\) в \(\Downupsilon\)
      F§ заносим в \(\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) =\)
$$