\documentclass[tikz,12pt,margin=0px]{article}

\usepackage[a4paper, margin=1in]{geometry}
\usepackage[magyar]{babel}
\usepackage[normalem]{ulem}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{enumitem}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{tikz}

\newcommand\ddfrac[2]{\frac{\displaystyle #1}{\displaystyle #2}}

 \geometry{
 a4paper,
 total={170mm,257mm},
 left=20mm,
 right=20mm,
 top=20mm,
 bottom=20mm
 }

\setlist[itemize,1]{label=$\bullet$}
\setlist[itemize,2]{label=$\circ$}
\setlist[itemize,3]{label=$\centerdot$}
\setlist[itemize,4]{label=$\cdot$}

\pagestyle{fancy}

\newcommand\blfootnote[1]{%
  \begingroup
  \renewcommand\thefootnote{}\footnote{#1}%
  \addtocounter{footnote}{-1}%
  \endgroup
}

\renewcommand{\figurename}{ábra}
\newenvironment{tetel}[1]{\paragraph{#1 \\}}{}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}

\makeatletter
\renewcommand\paragraph{%
	\@startsection{paragraph}{4}{0mm}%
	{-\baselineskip}%
	{.5\baselineskip}%
	{\normalfont\normalsize\bfseries}}
\makeatother

\newcommand\lword[1]{\leavevmode\nobreak\hskip0pt plus\linewidth\penalty50\hskip0pt plus-\linewidth\nobreak #1}

\useunder{\uline}{\ul}{}
\fancyhead{}
\cfoot{12. tétel | \thepage. oldal}

\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.4pt}

\begin{document}
    \thispagestyle{fancy}
    \hyphenation{oddword}
    \uchyph=0

    \begin{center}
        {\Large\bfseries\noindent 12. Logika és számításelmélet} \\
    \end{center}	
	
	\section*{Logika}
	
	\subsection*{Alapfogalmak}
	
	A logika tárgya az emberi gondolkodási folyamat vizsgálata és
	helyes gondolkodási formák keresése, illetve létrehozása.\\
	
	\noindent Fogalmak:
	\begin{enumerate}
		\item	\textbf{Állítás}: Olyan kijelentés, melynek logikai értéke (igaz
		volta) eldönthető, tetszőleges kontextusban igaz vagy hamis. Azt mondjuk,
		hogy egy állítás igaz, ha információtartalma megfelel a valóságnak (a tényeknek),
		és hamis az ellenkező esetben.
		
		A mindennapi beszédben használt kijelentő mondatok legtöbbször nem állítások, mivel
		a mondat tartalmába a kontextus is beleszámít: időpont, környezet állapota, általános műveltség
		bizonyos szintje, stb. (pl. nem állítás az, hogy "ma reggel 8-kor sütött a nap", de állítás pl. az, hogy
		"minden páros szám osztható 2-vel").
		
		\item	\textbf{Gondolkodási forma}: Gondolkodási forma alatt egy olyan $(F,A)$ párt értünk, ahol
		$A$ állítás, $F=\left\{A_{1},A_{2},\ldots,A_{n}\right\}$ pedig állítások egy halmaza.

		A gondolkodásforma helyes, ha minden esetben, amikor $F$ minden állítása igaz, akkor $A$ is igaz.

		\item	\textbf{Igazságérték}: Az igazságértékek halmaza $\mathbb{L}=\left\{igaz,hamis\right\}$.
	\end{enumerate}
	
	\subsection*{Ítéletkalkulus}
	
	\subsubsection*{Az ítéletlogika szintaxisa}
	
	\paragraph{Az ítéletlogika ábécéje}
	Az ítéletlogika ábécéje $V_{0}=V_{v} \cup \left\{(,)\right\} \cup \left\{\neg, \wedge, \vee, \supset\right\}$.\\
    Tehát $V_{0}$ tartalmazza az
    \begin{itemize}
        \item ítéletváltozókat $V_{v}$
        \item zárójeleket $\left\{(,)\right\}$
        \item logikai műveletek jeleit $\left\{\neg, \wedge, \vee, \supset\right\}$.
    \end{itemize}
	
	\paragraph{Az ítéletlogika nyelve}
	Az ítéletlogika nyelve ($\mathcal{L}_{0}$) ítéletlogikai formulákból áll, amelyek a következőképpen állnak elő:
	\begin{enumerate}
		\item	Minden ítéletváltozó ítéletlogikai formula (jff). Ezek az úgynevezett prímformulák (vagy atomi formulák).
		
		\item	Ha $A$ ítéletlogikai formula, akkor $\neg A$ is az.
		
		\item	Ha $A$ és $B$ ítéletlogikai formulák, akkor $(A \wedge B)$, $(A \vee B)$ és $(A \supset B)$ is
		ítéletlogikai formulák.
		
		\item	Minden ítéletlogikai formula az 1-3. szabályok véges sokszori alkalmazásával áll elő\\
        (Jól formált formulák).
	\end{enumerate}
	
	\noindent \textbf{Literál}: Ha $X$ ítéletváltozó, akkor az $X$ és $\neg X$ formulák literálok, amelyek alapja $X$.\\
	
	\noindent \textbf{Részformula}: Legyen $A \in \mathcal{L}_{0}$ egy ítéletlogikai formula.\\

    \noindent Ekkor $A$ részformuláinak halmaza a legszűkebb olyan halmaz, melynek
	\begin{enumerate}
		\item eleme az $A$ formula, és
		\item ha a C formula eleme, akkor C közvetlen részformulái is elemei.
	\end{enumerate}
	
	\noindent \textbf{Közvetlen részformula}:
	\begin{itemize}
		\item Prímformulának nincs közvetlen részformulája.
		\item $\neg A$ közvetlen részformulája $A$.
		\item $A \circ B$ ($\circ$ az $\wedge, \vee, \supset$ binér összekötőjelek egyike) közvetlen részformulái:
        \begin{itemize}
            \item $A$ (bal oldali) és
            \item $B$ (jobb oldali)
        \end{itemize}
            \begin{itemize}
                \item Egy formulának részformulája a közvetlen részformulája.
                \item Egy formulának részformulái minden részformulájának közvetlen részformulái is.
            \end{itemize}
	\end{itemize}

	\noindent \textbf{Szerkezeti fa}: Egy C formula szerkezeti fája egy olyan \textbf{\emph{véges rendezett fa}}, melynek csúcsai formulák,
	\begin{enumerate}
		\item	gyökere C,
		\item	a $\neg A$ csúcsának pontosan egy gyermeke van, az $A$,
		\item	a $A \circ B$ csúcsának pontosan két gyermeke van, rendre az $A$ és $B$ formulák,
		\item	levelei prímformulák.
	\end{enumerate}
	
	\begin{figure}[H]
		\centering
        \begin{tikzpicture}
          [
            grow                    = down,
            sibling distance        = 7em,
            level distance          = 2.5em,
            edge from parent/.style = {draw, -latex},
            every node/.style       = {font=\footnotesize},
            sloped
          ]
          \node {$ (\lnot(X \supset Y) \vee Z)$}
            child { node {$ \lnot(X \supset Y)$}
              child { node {$(X \supset Y)$}
                child { node {X} }
                child { node {Y} } } }
            child { node {Z} };
        \end{tikzpicture}
		\caption{Példa szerkezeti fára.}
		\label{fig:szerkfa}
	\end{figure}
	
	\noindent \textbf{Logikai összetettség l(X)}\\
    \noindent Egy formula logikai összetettsége a benne található logikai összekötőjelek száma.
	\begin{itemize}
        \item Ha $X$ ítéletlogikai változó, akkor $l(X) = 0$
        \item Ha $l(\neg X) = l(X) + 1$
        \item $l(X \circ Y) = l(X) + l(Y)+1$
    \end{itemize}
	\noindent \textbf{Művelet hatásköre}: Egy művelet hatásköre a formula részformulái közül
	a legkisebb logikai összetettségű, melyben az adott művelet előfordul.\\
	
	\noindent \textbf{Fő logikai összekötőjel}: Egy formula fő logikai összekötőjele az az összekötőjel, amelynek
	hatásköre maga a formula.\\
	
	\noindent \textbf{Precedencia}: A logikai összekötőjelek precedenciája csökkenő sorrendben a következő: $\neg, \wedge, \vee, \supset$.\\
	
    \noindent A definíciók alapján egyértelmű, hogy egy \textit{teljesen zárójelezett formulában} mi a logikai \lword{összekötőjelek} hatásköre és mi a fő logikai összekötőjel.\\

    \paragraph*{Zárójelek elhagyása}

     \noindent Nézzük, hogy egy formulában milyen esetekben és mely részformulákat határoló zárójelek hagyhatóak el úgy, hogy a logikai összekötőjelek hatásköre ne változzon.\\

     \noindent A részformulák közül a prímformuláknak és a negációs formuláknak nincs külső zárójelpárja, ezért csak az $(A \circ B)$ alakú részformulákról kell eldöntenünk, hogy írható-e helyettük $A \circ B$.\\
     A zárójelek elhagyását mindig a formula külső zárójelpárjának (ha van) elhagyásával kezdjük.\\

     \noindent Majd ha egy részformulában már megvizsgáltuk a külső zárójelelhagyás kérdését, utána ezen részformula közvetlen részformuláinak külső zárójeleivel foglalkozunk. Két eset lehetséges:
	
	\begin{enumerate}
		\item	A részformula egy negációs formula, melyben az $(A \circ B)$ alakú közvetlen részformula külső zárójelei nem hagyhatók el.
		
		\item	A részformula egy $(A \bullet B)$ vagy $A \bullet B$ alakú formula, melynek $A$ és $B$ közvetlen részformuláiban kell dönteni a külső zárójelek sorsáról.
        \begin{itemize}
            \item Ha az $A$ formula $A_{1} \circ A_{2}$ alakú, akkor $A$ külső zárójelpárja akkor hagyható el, ha $\circ$ nagyobb precedenciájú, mint $\bullet$.
            \item Ha a $B$ formula $B_{1} \circ B_{2}$ alakú, akkor $B$ külső zárójelpárja akkor hagyható el, ha $\circ$ nagyobb vagy egyenlő precedenciájú, mint $\bullet$.
        \end{itemize}
		
		\item	Ha egy $(A \wedge B)$ vagy $A \wedge B$ alakú formula valamely közvetlen részformulája szintén konjunkció, illetve egy
		$(A \vee B)$ vagy $A \vee B$ alakú formula valamely közvetlen részformulája szintén diszjunkció, akkor az ilyen részformulákból a külső zárójelpár elhagyható.
	\end{enumerate}
	
    \noindent \textbf{Formulaláncok}: A zárójelek elhagyására vonatkozó megállapodásokat figyelembe véve \lword{úgynevezett} konjunkciós, diszjunkciós, illetve implikációs formulaláncokat is nyerhetünk.\\

    \noindent Ezek alakja $A_{1} \wedge \ldots \wedge A_{n}$, $A_{1} \vee \ldots \vee A_{n}$, illetve
	$A_{1} \supset \ldots \supset A_{n}$.\\

     \noindent Ezeknek a láncformuláknak a fő logikai összekötőjelét a következő zárójelezési megállapodással fogjuk meghatározni:
     \[
        \Big(A_{1} \wedge \big(A_{2} \wedge \big( \ldots \wedge (A_{n-1} \wedge A_{n})\big)\ldots\big)\Big),\ \Big(A_{1} \vee \big(A_{2} \vee \big( \ldots \vee (A_{n-1} \vee A_{n})\big)\ldots\big)\Big)
     \]
     illetve
     \[
         \Big(A_{1} \supset \big(A_{2} \supset \big( \ldots \supset (A_{n-1} \supset A_{n})\big)\ldots\big)\Big)
     \]

\newpage	
	\subsection*{Az ítéletlogika szemantikája\\}
	
	\noindent \textbf{Bázis}: A formula ítéletváltozóinak egy rögzített sorrendje.\\

    \noindent \textbf{Interpretáció}: $\mathcal{L}_{0}$ interpretációján egy $\mathcal{I} : V_{v} \to \mathbb{L}$ függvényt értünk, mely minden ítéletváltozóhoz egyértelműen hozzárendel egy igazságértéket. Pl. $\mathcal{I}(X) = igaz$.\\

    \noindent \textbf{Boole-értékelés}: $\mathcal{L}_{0}$-beli formulák $\mathcal{I}$ \textit{interpretációbeli Boole-értékelése} a következő\\
    $\mathcal{B}_{\mathcal{I}} : \mathcal{L}_{0} \to \mathbb{L}$ függvény:
	
	\begin{enumerate}
		\item ha $A$ prímformula, akkor $\mathcal{B}_{\mathcal{I}}(A) = \mathcal{I}(A)$
		
		\item $\mathcal{B}_{\mathcal{I}}(\neg A)$ legyen $\neg \mathcal{B}_{\mathcal{I}}(A) $
		
		\item $\mathcal{B}_{\mathcal{I}}(A \wedge B)$ legyen $\mathcal{B}_{\mathcal{I}}(A) \wedge \mathcal{B}_{\mathcal{I}}(B)$
		
		\item $\mathcal{B}_{\mathcal{I}}(A \vee B)$ legyen $\mathcal{B}_{\mathcal{I}}(A) \vee \mathcal{B}_{\mathcal{I}}(B)$
		
		\item $\mathcal{B}_{\mathcal{I}}(A \supset B)$ legyen $\mathcal{B}_{\mathcal{I}}(A) \supset \mathcal{B}_{\mathcal{I}}(B)$
	\end{enumerate}

    \noindent Egy $B_I$ igazságkiértékelés kielégít egy $F$ formulahalmazt, ha $B_I$ az $F$ elemeihez az igaz értéket rendeli, vagyis a formulahalmaz elemei az $I$ interpretációban igazak.\\

    \noindent \textbf{Igazhalmaz, hamishalmaz}: Egy $A$ formula igazhalmaza $(A^{i})$ azon interpretációk halmaza, melyen a formula igazságértékelése igaz. Az $A$ formula hamishalmaza $(A^{h})$ pedig azon interpretációk halmaza, melyekre a formula igazságértékelése hamis.\\
	
    \noindent \textbf{Szemantikus fa}: Egy formula különböző interpretációit szemantikus fa segítségével \lword{szemléltethetjük}. A szemantikus fa egy olyan bináris fa, amelynek $i$. szintje ($i>=1$) a bázis $i$. ítéletváltozójához tartozik, és minden csúcsából két él indul, az egyik a szinthez rendelt ítéletváltozóval, a másik annak negáltjával címkézve. Az $X$ ítéletváltozó esetén az $X$ címke jelentse azt, hogy az $X$ \textit{igaz} az adott interpretációban, a $\neg X$ címke pedig azt, hogy \textit{hamis} az adott interpretációban.\\

    \noindent A szemantikus fa minden ága egy-egy lehetséges interpretációt reprezentál. Egy $n$ változós formula esetén minden ág $n$ hosszú, és a fának $2^{n}$ ága van és az összes lehetséges interpretációt tartalmazza.\\

    \begin{center}
        \begin{tikzpicture}
            \node[rectangle,draw] (G) {G};
            \node[rectangle,draw] (X1) at (-4,-1) {X1};
            \node[rectangle,draw] (X2) at (4,-1) {X2};

            \node[rectangle,draw] (Y1) at (-6,-2) {Y1};
            \node[rectangle,draw] (Y2) at (-2,-2) {Y2};
            \node[rectangle,draw] (Y3) at (2, -2) {Y3};
            \node[rectangle,draw] (Y4) at (6, -2) {Y4};

            \node[rectangle,draw] (Z1) at (-7,-4) {Z1};
            \node[rectangle,draw] (Z2) at (-5,-4) {Z2};
            \node[rectangle,draw] (Z3) at (-3,-4) {Z3};
            \node[rectangle,draw] (Z4) at (-1,-4) {Z4};
            \node[rectangle,draw] (Z5) at (1, -4) {Z5};
            \node[rectangle,draw] (Z6) at (3, -4) {Z6};
            \node[rectangle,draw] (Z7) at (5, -4) {Z7};
            \node[rectangle,draw] (Z8) at (7, -4) {Z8};

            \path[-] (G) edge node[above left] {$X$} (X1);
            \path[-] (G) edge node[above right] {$\neg X$} (X2);

            \path[-] (X1) edge node[above left] {$Y$} (Y1);
            \path[-] (X1) edge node[above right] {$\neg Y$} (Y2);

            \path[-] (Y1) edge node[above left] {$Z$} (Z1);
            \path[-] (Y1) edge node[above right] {$\neg Z$} (Z2);

            \path[-] (Y2) edge node[above left] {$Z$} (Z3);
            \path[-] (Y2) edge node[above right] {$\neg Z$} (Z4);

            \path[-] (X2) edge node[above left] {$Y$} (Y3);
            \path[-] (X2) edge node[above right] {$\neg Y$} (Y4);

            \path[-] (Y3) edge node[above left] {$Z$} (Z5);
            \path[-] (Y3) edge node[above right] {$\neg Z$} (Z6);

            \path[-] (Y4) edge node[above left] {$Z$} (Z7);
            \path[-] (Y4) edge node[above right] {$\neg Z$} (Z8);

        \end{tikzpicture}
    \end{center}

	\noindent \textbf{Igazságértékelés függvény}:  Olyan függvény, amely minden formulához hozzárendeli az igazhalmazát ($\varphi A^{i}$) vagy
	a hamishalmazát ($\varphi A^{h}$).\\
\newpage
	\noindent Legyen $A$ egy tetszőleges ítéletlogikai formula. Határozzuk meg $A$-hoz az interpretációira vonatkozó $\varphi A^{i}$, illetve
	$\varphi A^{h}$ feltételeket a következőképpen:
	
	\begin{enumerate}
		\item	Ha $A$ prímformula, a $\varphi A^{i}$ feltételt pontosan azok az $\mathcal{I}$ interpretációk elégítik ki,  melyekre
		$\mathcal{I}(A)=igaz$, a $\varphi A^{h}$ feltételt pedig pontosan azok melyekre	$\mathcal{I}(A)=hamis$.
		
		\item	A $\varphi (\neg A)^{i}$ feltételek pontosan akkor teljesülnek, ha teljesülnek a $\varphi A^{h}$ feltételek.
		
		\item	A $\varphi (A \wedge B)^{\textbf{i}}$ feltételek pontosan akkor teljesülnek, ha a $\varphi A^{\textbf{i}}$ \textbf{\emph{és}} a $\varphi B^{\textbf{i}}$ feltételek egyszerre teljesülnek.
		
		\item	A $\varphi (A \vee B)^{\textbf{i}}$ feltételek pontosan akkor teljesülnek, ha a $\varphi A^{\textbf{i}}$ \textbf{\emph{vagy}} a $\varphi B^{\textbf{i}}$ feltételek teljesülnek.
		
		\item	A $\varphi (A \supset B)^{\textbf{i}}$ feltételek pontosan akkor teljesülnek, ha a $\varphi A^{\textbf{h}}$ \textbf{\emph{vagy}} a $\varphi B^{\textbf{i}}$ feltételek teljesülnek.
	\end{enumerate}	
	
	\noindent \textbf{Tétel}: Tetszőleges $A$ ítéletlogikai formula esetén a  $\varphi A^{i}$ feltételeket pontosan az  $A^{i}$-beli
	interpretációk teljesítik.\\

	\noindent \textbf{Igazságértékelés-fa}:  Egy $A$ formula $\varphi A^{i}$, illetve $\varphi A^{h}$ feltételeket kielégítő interpretációit
	az igazságértékelés-fa segítségével szemléltethetjük. Az igazságértékelés-fát a formula szerkezeti fájának felhasználásával állítjuk elő.

    \noindent A gyökérhez hozzárendeljük, hogy $A$ melyik igazságértékre való igazságértékelés-feltételeit keressük, majd a gyökér alá $A$ közvetlen részformulái kerülnek a megfelelő feltétel-előírással, az alábbiak szerint:

    \begin{center}
        $\begin{array}{c|c|c|c}
        \begin{tikzpicture}[grow = down, sibling distance = 5em, edge from parent/.style = {draw, -latex},  every node/.style = {font=\footnotesize}, sloped, level distance=12mm, text depth=.1em]
            \node { $\varphi(\neg A)^{i}$ }
                child {
                    node { $\varphi A^{h}$ }
                };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[grow = down, sibling distance = 5em, edge from parent/.style = {draw, -latex},  every node/.style = {font=\footnotesize}, sloped, level distance=12mm, text depth=.1em]
            \node {$\varphi(A \wedge B)^{i}$}
                child {
                    node {$\varphi A^{i}$}
                        child {
                            node {$\varphi B^{i}$}
                        }
                };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[grow = down, sibling distance = 5em, edge from parent/.style = {draw, -latex},  every node/.style = {font=\footnotesize}, sloped, level distance=12mm, text depth=.1em]
            \node {$\varphi(A \vee B)^{i}$}
                    child { node {$\varphi A^{i}$} }
                    child { node {$\varphi B^{i}$} };
        \end{tikzpicture}
        &

        \begin{tikzpicture}[grow = down, sibling distance = 5em, edge from parent/.style = {draw, -latex},  every node/.style = {font=\footnotesize}, sloped, level distance=12mm, text depth=.1em]
            \node {$\varphi(A \supset B)^{i}$}
                    child { node {$\varphi A^{h}$} }
                    child { node {$\varphi B^{i}$} };
        \end{tikzpicture}

        \\ \hline

        \begin{tikzpicture}[grow = down, sibling distance = 5em, edge from parent/.style = {draw, -latex},  every node/.style = {font=\footnotesize}, sloped, level distance=12mm, text depth=.1em]
            \node { $\varphi(\neg A)^{h}$ }
                child {
                    node {$\varphi A^{i}$ }
                };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[grow = down, sibling distance = 5em, edge from parent/.style = {draw, -latex},  every node/.style = {font=\footnotesize}, sloped, level distance=12mm, text depth=.1em]
            \node {$\varphi(A \wedge B)^{h}$}
                    child { node {$\varphi A^{h}$} }
                    child { node {$\varphi B^{h}$} };
        \end{tikzpicture}
         &
        \begin{tikzpicture}[grow = down, sibling distance = 5em, edge from parent/.style = {draw, -latex},  every node/.style = {font=\footnotesize}, sloped, level distance=12mm, text depth=.1em]
            \node {$\varphi(A \vee B)^{h}$}
                child {
                    node {$\varphi A^{h}$}
                        child {
                            node {$\varphi B^{h}$}
                        }
                };
        \end{tikzpicture}
        &
        \begin{tikzpicture}[grow = down, sibling distance = 5em, edge from parent/.style = {draw, -latex},  every node/.style = {font=\footnotesize}, sloped, level distance=12mm, text depth=.1em]
            \node {$\varphi(A \supset B)^{h}$}
                child {
                    node {$\varphi A^{i}$}
                        child {
                            node {$\varphi B^{h}$}
                        }
                };
        \end{tikzpicture}
        \end{array}$
    \end{center}
	
	\noindent Ezután a gyökérhez a \checkmark (feldolgozott) jelet rendeljük. Az eljárást rekurzívan folytatjuk, amíg egy ágon a fel nem dolgozott formulák
	
	\begin{itemize}
		\item	(a) mind ítéletváltozók nem lesznek, vagy
		\item	(b) ugyanarra a formulára egymásnak ellentmondó előírás nem jelenik meg.
	\end{itemize}
	
    \noindent Az (a) esetben az ágon előforduló ítéletváltozóknak az ágon rögzített igazságértékeit tartalmazó $n$-esek mind elemei $\varphi A^{i}$	gyökér esetén a formula igazhalmazának, $\varphi A^{h}$ gyökér esetén a formula hamishalmazának.
	
	\noindent A (b) esetben nem áll elő ilyen igazságérték $n$-es.
	
	\begin{figure}[H]
		\centering
        \begin{tikzpicture}
          [
            grow                    = down,
            sibling distance        = 5em,
            edge from parent/.style = {draw, -latex},
            every node/.style       = {font=\footnotesize},
            sloped,
            level distance=12mm,
            text depth=.1em,
            level 1/.style={sibling distance=5em},
            level 2/.style={sibling distance=30em},
            level 3/.style={sibling distance=15em},
            level 4/.style={sibling distance=8em}
          ]
          \node {$ \varphi((Y \vee Z) \wedge (Z \supset \neg X))^{i} \quad \checkmark$}
            child { node {$ \varphi(Y \vee Z)^{i} \quad \checkmark$}
              child {
               node {$ \varphi (Z \supset \neg X)^{i} \quad \checkmark$}
                child { node {$\varphi Y^{i} $}
                    child { node {$\varphi Z^{h}$} }
                    child { node {$\varphi(\neg X^{i}) \quad \checkmark$}
                        child { node {$\varphi X^{h}$} }
                    }
                }
                child { node {$\varphi Z^{i} $}
                    child { node {$\underset{\times}{\varphi Z^{h}}$} }
                    child { node {$\varphi(\neg X^{i}) \quad \checkmark$}
                        child { node {$\varphi X^{h} $} }
                    }
                }
              }
            };
        \end{tikzpicture}
		\caption{Példa igazságértékelés fára.}
		\label{fig:szerkfa}
	\end{figure}
	
	\noindent Az elöbbi példában a formula igazhalmaza az igazságértékelés-fa alapján:
    \[
        \left\{(i,i,h),(h,i,i),(h,i,h),(h,h,i)\right\}
    \]
	
	\noindent \textbf{Igazságtábla}: Egy $n$ változós formula igazságtáblája egy $n+1$ oszlopból és $2^{n}$ sorból álló táblázat.
	A táblázat fejlécében az $i$. oszlophoz ($1<=i<=n$) a formula bázisának $i$. ítéletváltozója, az $n+1$. oszlophoz maga a formula
	van hozzárendelve. Az első $n$ oszlopban az egyes sorokhoz megadjuk rendre a formula különböző interpretációit, majd a formula
	oszlopába minden sorba beírjuk a formula - a sorhoz tartozó interpretációbeli Boole-értékeléssel kapott - igazságértékét.\\
	
	\noindent \textbf{A logikai műveletek igazságtáblája}:

    \begin{center}	
    	\begin{tabular}{|c|c||c|}
            \hline
    		\textbf{X} & \textbf{Y} & $\boldsymbol{\neg X}$  \\ \hline
    		\textbf{i} & \textbf{i} & h \\ \hline
    		\textbf{i} & h & h  \\ \hline
    		h & \textbf{i} & \textbf{i} \\ \hline
    		h & h & \textbf{i} \\ \hline
    	\end{tabular}\quad
    	\begin{tabular}{|c|c||c|}
            \hline
    		\textbf{X} & \textbf{Y} & $\boldsymbol{X \wedge Y}$   \\ \hline
    		\textbf{i} & \textbf{i} & \textbf{i} \\ \hline
    		\textbf{i} & h & h \\ \hline
    		h & \textbf{i} & h  \\ \hline
    		h & h & h \\ \hline
    	\end{tabular}\quad
    	\begin{tabular}{|c|c||c|}
            \hline
    		\textbf{X} & \textbf{Y} & $\boldsymbol{X \vee Y}$  \\ \hline
    		\textbf{i} & \textbf{i} & \textbf{i} \\ \hline
    		\textbf{i} & h & \textbf{i}  \\ \hline
    		h & \textbf{i} & \textbf{i} \\ \hline
    		h & h & h \\ \hline
    	\end{tabular}\quad
    	\begin{tabular}{|c|c||c|}
            \hline
    		\textbf{X} & \textbf{Y} & $\boldsymbol{X \supset Y}$  \\ \hline
    		\textbf{i} & \textbf{i} & \textbf{i} \\ \hline
    		\textbf{i} & h & h  \\ \hline
    		h & \textbf{i} & \textbf{i} \\ \hline
    		h & h & \textbf{i} \\ \hline
    	\end{tabular}
    \end{center}
	
	\noindent \textbf{Kiterjesztett igazságtábla}: Egy igazságtáblában a formula igazságértéke kiszámításának megkönnyítésére vezették
	be a kiterjesztett igazságtáblát. A kiterjesztett igazságtáblában az ítéletváltozókhoz és a formulához rendelt oszlopokon kívül rendre
	a formula részformuláihoz tartozó oszlopok is megjelennek. Tulajdonképpen a szerkezeti fában megjelenő részformulák vannak felsorolva.
	
    \begin{center}
        $\begin{array}{|c|c|c|c|c|c|c|}
          \hline
          \textbf{X} & \textbf{Y} & \textbf{Z} & \boldsymbol{Y \vee Z} & \boldsymbol{\neg X} & \boldsymbol{Z \supset \neg X} & \boldsymbol{(Y \vee Z) \wedge (Z \supset \neg X)} \\ \hline
          i & i & i & i & h & h & h \\ \hline
          i & i & h & i & h & i & i \\ \hline
          i & h & i & i & h & h & h \\ \hline
          i & h & h & h & h & i & h \\ \hline
          h & i & i & i & i & i & i \\ \hline
          h & i & h & i & i & i & i \\ \hline
          h & h & i & i & i & i & i \\ \hline
          h & h & h & h & i & i & h \\ \hline

        \end{array}$
    \end{center}

    \noindent \textbf{Formula kielégíthetősége, modellje}: Egy $A$ ítéletlogikai formula \textit{kielégíthető}, ha létezik olyan  $\mathcal{I}$ interpretáció, melyre $\mathcal{I} \models_{0} A$, azaz a $\mathcal{B}_{\mathcal{I}}$ Boole-értékelés $A$-hoz igaz értéket rendel. Egy ilyen interpretációt $A$ \textit{modelljének} nevezünk. Ha $A$-nak nincs modellje, akkor azt mondjuk, hogy \textit{kielégíthetetlen}.\\
	
    \noindent Ha $A$ igazságtáblájában van olyan sor, amelyben a formula oszlopában igaz érték szerepel, akkor a formula kielégíthető, különben kielégíthetetlen. Ugyanígy, ha $\varphi A^{i}$ nem üres, akkor kielégíthető, különben kielégíthetetlen.\\
	
    \noindent \textbf{Ítéletlogikai törvény, tautológia}: Egy $A$ ítéletlogikai formula \textit{ítéletlogikai törvény} vagy másképpen \textit{tautológia}, ha $\mathcal{L}_{0}$ minden interpretációja modellje $A$-nak. (jelölés: $\models_{0} A$)\\

    \subsection*{Eldöntésproblémák\\}

	\noindent \textbf{Eldöntésprobléma}: Eldöntésproblémának nevezzük a következő feladatokat:
	\begin{enumerate}
		\item	Döntsük el tetszőleges formuláról, hogy tautológia-e!
		
		\item	Döntsük el tetszőleges formuláról, hogy kielégíthetetlen-e!
	\end{enumerate}
	
    \noindent \textbf{Tautologikusan ekvivalens formulák}: Az $A$ és $B$ ítéletlogikai formulák \textit{tautologikusan ekvivalensek} (jelölés: $A \sim _{0} B$), ha $\mathcal{L}_{0}$ minden $\mathcal{I}$ interpretációjában $\mathcal{B}_{\mathcal{I}}(A)=\mathcal{B}_{\mathcal{I}}(B)$.\\
	
	\noindent \textbf{Formulahalmaz kielégíthetősége, modellje}: $\mathcal{L}_{0}$ formuláinak egy tetszőleges $\Gamma\ (gamma)$ halmaza
	kielégíthető, ha van $\mathcal{L}_{0}$-nak olyan $\mathcal{I}$ interpretációja, melyre: $\forall A \in \Gamma: \mathcal{I} \models_{0} A$.
	Egy ilyen $\mathcal{I}$ interpretáció modellje $\Gamma$-nak. Ha $\Gamma$-nak nincs modellje, akkor $\Gamma$ kielégíthetetlen.\\
	
	\noindent \textbf{Lemma}: Egy $\left\{A_{1},A_{2},\ldots,A_{n}\right\}$ formulahalmaznak pontosan azok az $\mathcal{I}$ interpretációk
	a modelljei, amelyek a $A_{1} \wedge A_{2} \wedge \ldots \wedge A_{n}$ formulának. Következésképpen $\left\{A_{1},A_{2},\ldots,A_{n}\right\}$
	pontosan akkor kielégíthetetlen, ha az $A_{1} \wedge A_{2} \wedge \ldots \wedge A_{n}$ formula kielégíthetlen.\\
	
	\noindent \textbf{Szemantikus következmény}: Legyen $\Gamma$ ítéletlogikai formulák tetszőleges halmaza, $B$ egy tetszőleges formula.
    Azt mondjuk, hogy a $B$ formula \textit{\textbf{tautologikus következménye}} a $\Gamma$ formulahalmaznak (jelölés: $\Gamma \models_{0} B$), ha minden olyan interpretáció, amely modellje $\Gamma$-nak, modellje $B$-nek is. A $\Gamma$-beli formulákat feltételformuláknak, vagy premisszáknak,
	a B formulát következményformulának (konklúziónak) hívjuk.\\
	
	\noindent \textbf{Tétel}: Legyen $\Gamma$ ítéletlogikai formulák tetszőleges halmaza, $A$,$B$,$C$ tetszőleges ítéletlogikai formulák.
	Ha $\Gamma \models_{0} A$, $\Gamma \models_{0} B$ és $\left\{A,B\right\} \models_{0} C$, akkor $\Gamma \models_{0} C$.\\
	
	\noindent \textbf{Tétel}: (\textbf{Eldöntésprobléma tétele (1)}) Legyenek $A_{1},A_{2},\ldots,A_{n}, B$ tetszőleges ítéletlogikai formulák.
	$\left\{A_{1},A_{2},\ldots,A_{n}\right\} \models_{0} B$ pontosan akkor, ha a $\left\{A_{1},A_{2},\ldots,A_{n}, \neg B\right\}$
	formulahalmaz kielégíthetetlen, azaz a\\
    $A_{1} \wedge A_{2} \wedge \ldots \wedge A_{n} \wedge \neg B$ formula kielégíthetetlen.\\

	\noindent \textbf{Tétel}: (\textbf{Dedukciós tétel}) Legyenek $A_{1},A_{2},\ldots,A_{n}, B$ tetszőleges ítéletlogikai formulák.\\
	$\left\{A_{1},A_{2},\ldots,A_{n}\right\} \models_{0} B$ pontosan akkor, ha
	$\left\{A_{1},A_{2},\ldots,A_{n}\right\} \supset B$.\\
	
	\noindent \textbf{Tétel}: (\textbf{Eldöntésprobléma tétele (2)}) Legyenek $A_{1},A_{2},\ldots,A_{n}, B$ tetszőleges ítéletlogikai formulák.
	$\left\{A_{1},A_{2},\ldots,A_{n}\right\} \models_{0} B$ pontosan akkor, ha
	$\models_{0} A_{1} \supset A_{2} \supset \ldots \supset A_{n} \supset B$.
\newpage	
	\paragraph{Ekvivalens átalakítások}
	Fogalmak:
	\begin{itemize}
		\item Egy prímformulát (ítéletváltozót), vagy annak a negáltját közös néven \textit{literálnak} nevezünk. A prímformula
		a \textit{literál alapja}. Egy literált bizonyos esetekben \textit{egységkonjunkciónak} vagy \textit{egységdiszjunkciónak}
		(\textit{egységklóznak}) is hívunk.
		
		\item \textit{Elemi konjunkció} az egységkonjunkció, illetve a különböző alapú literálok konjunkciója ($\wedge$ kapcsolat
		a literálok között).
        \item \textit{Elemi diszjunkció} vagy \textit{klóz} az egységdiszjunkció és a különböző alapú literálok
		diszjunkciója ($\vee$ kapcsolat a literálok között).
        \item Egy elemi konjunkció, illetve elemi diszjunkció \textit{teljes}
		egy $n$-változós logikai műveletre nézve, ha mind az $n$ ítéletváltozó alapja valamely literáljának.
		\item \textit{Diszjunktív normálformának} (DNF) nevezzük az elemi konjunkciók diszjunkcióját.
		\item \textit{Konjunktív normálformának} (KNF) nevezzük az elemi diszjunkciók konjunkcióját.
        \item \textit{Kitüntetett} diszjunktív, illetve konjunktív normálformákról (KDNF, ileltve KKNF) beszélünk, ha a bennük szereplő
		elemi konjunkciók, illetve elemi diszjunkciók teljesek.
	
	\end{itemize}	
	
	\noindent \textbf{Tetszőleges logikai műveletet leíró KDNF, KKNF előállítása}:	Legyen $b: \mathbb{L}^{n} \to \mathbb{L}$
	egy $n$-változós logikai művelet. Adjuk meg $b$ művelettábláját.\\

	\noindent Az első $n$ oszlop fejlécébe az $X_{1}$, $X_{2}$, \ldots $X_{n}$ ítéletváltozókat írjuk.\\
	
	\noindent A $b$-t leíró KDNF előállítása:
	
	\begin{enumerate}
        \item Válasszuk ki azokat a sorokat a művelettáblában, ahol az adott igazságérték $n$-eshez $b$ \textit{igaz} értéket rendel hozzá. Legyenek ezek a sorok rendre $s_{1}, s_{2}, \ldots, s_{r}$. Minden ilyen sorhoz rendeljünk hozzá egy $X_{1}' \wedge X_{2}' \wedge \ldots \wedge X_{n}'$ teljes elemi konjunkciót úgy, hogy az $X_{j}'$ literál $X_{j}$ vagy $\neg X_{j}$ legyen aszerint, hogy ebben a sorban $X_{j}$ \textit{igaz} vagy \textit{hamis} igazságérték szerepel. Az így nyert teljes elemi konjunkciók legyenek rendre $k_{s_{1}}, k_{s_{2}}, \ldots, k_{s_{r}}$.
		
		\item	Az így kapott teljes elemi konjunkciókból készítsünk egy diszjunkciós láncformulát:
        \[
		  k_{s_{1}} \vee k_{s_{2}} \vee \ldots \vee k_{s_{r}}
        \]
	\end{enumerate}

    \noindent Ez a formula lesz a $b$ művelet kitüntetett diszjunktív normálformája (KDNF).

	\begin{center}
      $\begin{array}{c|c|c||c|c|c}
        \textbf{X} & \textbf{Y} & \textbf{Z} & \textbf{b} &   & \text{a teljes elemi konjukciók} \\ \hline
        i & i & i & h &   & \\ \hline
        i & i & h & i & * & X \wedge Y \wedge \neg Z \\ \hline
        i & h & i & h &   & \\ \hline
        i & h & h & i & * & X \wedge \neg Y \wedge \neg Z \\ \hline
        h & i & i & i & * & X \neg \wedge Y \wedge Z \\ \hline
        h & i & h & h &   & \\ \hline
        h & h & i & i & * & \neg X \wedge \neg Y \wedge Z \\ \hline
        h & h & h & i & * & \neg X \wedge \neg Y \neg \wedge Z
      \end{array}$
	\end{center}
	
	\noindent A fenti példa $b$ műveletének kitüntetett diszjunktív normálformája a következő formula:
    \[
	   (X \wedge Y \wedge \neg Z) \vee (X \wedge \neg Y \wedge \neg Z) \vee (\neg X \wedge Y \wedge Z) \vee (\neg X \wedge \neg Y \wedge Z) \vee (\neg X \wedge \neg Y \wedge \neg Z)
    \]
\newpage	
	\noindent A $b$-t leíró KKNF előállítása:
	
	\begin{enumerate}
		\item	Válasszuk ki azokat a sorokat a művelettáblában, ahol az adott igazságérték $n$-eshez $b$ \textit{hamis}
		értéket rendel hozzá. Legyenek ezek a sorok rendre $s_{1}, s_{2}, .. s_{r}$. Minden ilyen sorhoz rendeljünk
		hozzá egy $X_{1}' \vee X_{2}' \vee \ldots \vee X_{n}'$ teljes elemi diszjunkciót úgy, hogy az $X_{j}'$ literál
		$X_{j}$ vagy $\neg X_{j}$ legyen aszerint, hogy ebben a sorban $X_{j}$ \textit{hamis} vagy \textit{igaz} igazságérték
		szerepel. Az így nyert teljes elemi diszjunkciók legyenek rendre $d_{s_{1}}, d_{s_{2}}, .. d_{s_{r}}$.
		
		\item	Az így kapott teljes elemi diszjunkciókból készítsünk egy konjunkciós láncformulát:
        \[
            d_{s_{1}} \wedge d_{s_{2}} \wedge \ldots \wedge d_{s_{r}}
        \]
        Ez a formula lesz a $b$ művelet kitüntetett konjunktív normálformája (KKNF).
	\end{enumerate}
	
	\begin{center}
      $\begin{array}{c|c|c||c|c|c}
        \textbf{X} & \textbf{Y} & \textbf{Z} & \textbf{b} &   & \text{a teljes elemi diszjunkciók} \\ \hline
        i & i & i & h & * & \neg X \vee \neg Y \vee \neg Z \\ \hline
        i & i & h & i &   & \\ \hline
        i & h & i & h & * & \neg X \vee Y \vee \neg Z \\ \hline
        i & h & h & i &   & \\ \hline
        h & i & i & i &   & \\ \hline
        h & i & h & i &   & \\ \hline
        h & h & i & h & * & X \vee Y \vee \neg Z \\ \hline
        h & h & h & i &   &
      \end{array}$
	\end{center}
	
	A fenti példa $b$ műveletének kitüntetett konjunktív normálformája a következő formula:
    \[
	   (\neg X \vee \neg Y \vee \neg Z) \wedge (\neg X \vee Y \vee \neg Z) \wedge (X \vee Y \vee \neg Z)
    \]
	
    \noindent \textbf{KNF, DNF egyszerűsítése}: Egy ítéletlogikai formula logikai összetettségén a formulában szereplő logikai összekötőjelek számát értettük. Ugyanazt a logikai műveletet leíró formulák közül azt tekintjük egyszerűbbnek, amelynek kisebb a logikai összetettsége (azaz kevesebb logikai összekötőjelet tartalmaz).\\
	
	\noindent Legyen $X$ egy ítéletváltozó $k$ egy az $X$-et nem tartalmazó elemi konjunkció, $d$ egy $X$-et nem tartalmazó elemi
	diszjunkció. Ekkor az
	
	\begin{itemize}
		\item	(a) $(X \wedge k) \vee (\neg X \wedge k) \sim_{0} k $ és
		
		\item	(b) $(X \vee d) \wedge (\neg X \vee d) \sim_{0} d $
	\end{itemize}
	egyszerűsítési szabályok alkalmazásával konjunktív és diszjunktív normálformákat írhatunk át egyszerűbb alakba.\\
	
	\noindent Klasszikus Quine--McCluskey-féle algoritmus KDNF egyszerűsítésére:
	
	\begin{enumerate}
		\item	Soroljuk fel a KDNF-ben szereplő összes teljes elemi konjunkciót az $L_{0}$ listában, $j:=0$.
		
		\item	Megvizsgáljuk az $L_{j}$-ben szereplő összes lehetséges elemi konjunkciópárt, hogy alkalmazható-e
		rájuk az (a) egyszerűsítési szabály. Ha igen, akkor a két kiválasztott konjunkciót $\checkmark$-val megjelöljük,
		és az eredmény konjunkciót beírjuk a $L_{j+1}$ listába. Azok az elemi konjunkciók, amelyek az $L_{j}$ vizsgálata
		során nem lesznek megjelölve, nem voltak egyszerűsíthetők, tehát bekerülnek az egyszerűsített diszjunktív
		normálformába.
		
		\item	Ha az $L_{j+1}$ konjunkciólista nem üres, akkor $j:=j+1$. Hajtsuk végre újból a 2. lépést.
		
		\item	Az algoritmus során kapott, de meg nem jelölt elemi konjunkciókból készítsünk egy diszjunkciós
		láncformulát. Így az eredeti KDNF-el logikailag ekvivalens, egyszerűsített DNF-et kapunk.
	\end{enumerate}
	
	\paragraph{Rezolúció}
	
    \noindent Legyenek $A_{1}, A_{2}, \ldots , A_{n}, B$ tetszőleges ítéletlogikai formulák. Azt szeretnénk bebizonyítani, hogy $\left\{A_{1}, A_{2}, \ldots , A_{n}\right\} \models_{0} B$, 	ami ekvivalens azzal, hogy $\left\{A_{1}, A_{2}, \ldots , A_{n}, \neg B\right\}$ kielégíthetetlen.\\

    \noindent Írjuk át ez utóbbi formulahalmaz formuláit KNF alakba.

    \noindent Ekkor a
    \[
        \left\{KNF_{A_{1}}, KNF_{A_{2}}, \ldots , KNF_{A_{n}}, KNF_{\neg B}\right\}
    \]
    formulahalmazt kapjuk, ami pontosan akkor kielégíthetetlen, ha a halmaz formuláiban szereplő klózok halmaza kielégíthetetlen.\\
	
    \noindent A klózokra vonatkozó egyszerűsítési szabály szerint ha $X$ ítéletváltozó, $C$ pedig $X$-et nem tartalmazó klóz, akkor
    \[
        (X \vee C) \wedge (\neg X \vee C) \sim_{0} C
    \]

    \noindent Az $X$ és a $\neg X$ egységklózok (azt mondjuk, hogy $X$ és $\neg X$ komplemens literálpár) konjunkciójával ekvivalens egyszerűbb.\\

    \noindent Egyetlen literált sem tartalmazó klóz az \textbf{\emph{üres klóz}}, melyet a $\square$ jellel jelölünk és definíció szerint minden interpretációban hamis igazságértékű.\\
	
    \noindent Legyenek most $C_{1}$ és $C_{2}$ olyan klózok, melyek pontosan egy komplemens literálpárt tartalmaznak, azaz $C_{1} = C_{1}' \vee L_{1}$ és $C_{2} = C_{2}' \vee L_{2}$, ahol $L_{1}$ és $L_{2}$ az egyetlen komplemens literálpár ($C_{1}'$ és $C_{2}'$ üres klózok is lehetnek). Világos, hogy ha a két klózban a komplemens literálpáron kívül is vannak literálok, és ezek nem mind azonosak, az egyszerűsítési szabály alkalmazhatósági feltétele nem áll fenn.\\
	
    \noindent \textbf{Tétel}: Ha $C_{1} = C_{1}' \vee L_{1}$ és $C_{2} = C_{2}' \vee L_{2}$, ahol $L_{1}$ és $L_{2}$ komplemens literálpár, akkor
    \[
        \left\{C_{1},C_{2}\right\} \models_{0} C_{1}' \vee C_{2}'
    \]
	
    \noindent \textbf{Rezolvens}: Legyenek $C_{1}$ és $C_{2}$ olyan klózok, melyek pontosan egy komplemens literálpárt tartalmaznak, azaz $C_{1} = C_{1}' \vee L_{1}$ és $C_{2} = C_{2}' \vee L_{2}$, ahol $L_{1}$ és $L_{2}$ a komplemens literálpár, a $C_{1}' \vee C_{2}'$ klózt a $(C_{1},C_{2})$ klózpár (vagy a $C_{1} \vee C_{2}$ formula) \textit{rezolvensének} nevezzük.\\

    \noindent Ha $C_{1} = L_{1}$ és $C_{2} = L_{2}$ (azaz $C_{1}'$ és $C_{2}'$ üres klózok), rezolvensük az üres klóz ($\square$).\\
    Az a tevékenység, melynek eredménye a rezolvens, a \textit{rezolválás}.
	\begin{center}
        $\begin{array}{r|l}
            \textbf{klózpár} & \textbf{rezolvens} \\ \hline
            (X \vee Y,\neg Y \vee Z) & X \vee Z \\
            (X \vee \neg Y, \neg Y \vee Z) & \text{nincs: mindkét azonos alapú literál negált} \\
            (X \vee \neg Y, Z \vee \neg V) & \text{nincs: nincs azonos alapú literál} \\
            (\neg X \vee \neg Y, X \vee Y \vee Z) & \text{nincs: két komplemens literálpár van} \\
            (X, \neg X) & \Box \\
        \end{array}$
    \end{center}
	
	\noindent \textbf{Tétel}: Ha a $C$ klóz a $(C_{1},C_{2})$ klózpár rezolvense, akkor azon $\mathcal{I}$ interpretációk
	a $\left\{C_{1}, C_{2}\right\}$ klózhalmazt nem elégíthetik ki, amelyekben $C$ igazságértéke hamis, azaz
	$\mathcal{B}_{\mathcal{I}}(C) = hamis$.\\
\newpage	
	\noindent \textbf{Rezolúciós levezetés}: Egy $S$ klózhalmazból a $C$ klóz rezolúciós levezetése egy olyan véges
	$k_{1}, k_{2}, \ldots ,k_{m}\ (m \geq 1)$ klózsorozat, ahol minden $j = 1, 2, \ldots, m$-re
	
	\begin{enumerate}
		\item	vagy $k_{j} \in S$,
		\item	vagy van olyan $1 \leq s,t \le j$, hogy $k_{j}$ a $(k_{s}, k_{t})$ klózpár rezolvense,
	\end{enumerate}
	\noindent és a klózsorozat utolsó tagja, $k_{m}$, éppen a $C$ klóz.\\
	
    \noindent Megállapodásunk szerint a \textbf{\emph{rezolúciós kalkulus eldöntésproblémája}}:
    \begin{center}
        levezethető-e $S$-ből az $\square$.
    \end{center}

    \noindent A rezolúciós levezetés célja tehát $\square$ levezetése $S$-ből. Azt, hogy $\square$ levezethető $S$-ből, úgy is ki lehet fejezni, hogy létezik $S$-nek rezolúciós cáfolata.\\
	
    \noindent Példa: Próbáljuk meg levezetni
    \[
        \square\text{-t az }S = \left\{\neg X \vee Y\boldsymbol{,}\ \neg Y \vee Z\boldsymbol{,}\ X \vee V\boldsymbol{,}\ \neg V \vee Y \vee Z\boldsymbol{,}\ \neg Z \right\}
    \]
	klózhalmazból. A levezetés bármelyik $S$-beli klózból indítható.
	
    \begin{center}
        $\begin{array}{rll}
        1. & \neg V \vee Y \vee Z & [\ \in S\ ] \\
        2. & \neg Z & [\ \in S\ ] \\
        3. & \neg V \vee Y & [\ 1,2\ rezolvense\ ] \\
        4. & \neg Y \vee Z & [\ \in S\ ] \\
        5. & \neg Y & [\ 2,4\ rezolvense\ ] \\
        6. & \neg V & [\ 3,5\ rezolvense\ ] \\
        7. & X \vee V & [\ \in S\ ] \\
        8. & X & [\ 6,7\ rezolvense\ ] \\
        9. & \neg X \vee Y & [\ \in S\ ] \\
        10. & Y & [\ 8,9\ rezolvense\ ] \\
        11. & \Box & [\ 5,10\ rezolvense\ ] \\
        \end{array}$
  \end{center}
	
	\noindent \textbf{Lemma}: Legyen $S$ tetszőleges klózhalmaz. $S$-ből történő rezolúciós levezetés esetén bármely $S$-ből
	levezetett klóz tautologikus következménye $S$-nek.\\
	
	\noindent \textbf{A rezolúciós kalkulus helyessége}: A rezolúciós kalkulus \textit{helyes}, azaz tetszőleges
	$S$ klózhalmaz esetén amennyiben $S$-ből levezethető $\square$, akkor $S$ \textit{kielégíthetetlen}.\\
	
	\noindent \textbf{A rezolúciós kalkulus teljessége}: A rezolúciós kalkulus \textit{teljes}, azaz bármely véges, kielégíthetetlen
	$S$ klózhalmaz esetén $S$-ből levezethető $\square$.\\	
	
	\noindent \textbf{Levezetési fa}: Egy rezolúciós levezetés szerkezetét \textit{levezetési fa} segítségével szemléltethetjük.
	A levezetési fa csúcsai klózok. Két csúcsból pontosan akkor vezet él egy harmadik, közös csúcsba, ha az a két klóz rezolvense.
	
	\begin{figure}[H]
		\centering
        \begin{tikzpicture}
          [
            grow                    = down,
            sibling distance        = 5em,
            edge from parent/.style = {draw, -latex},
            every node/.style       = {font=\footnotesize},
            sloped,
            level distance=12mm,
            text depth=.1em,
            level 1/.style={sibling distance=5em},
            level 2/.style={sibling distance=5em},
            level 3/.style={sibling distance=5em},
            level 4/.style={sibling distance=8em}
          ]
          \node {$ \underset{11}{\Box} $}[grow'=up]
            child { node { $\underset{5}{\neg Y}$ }}
            child { node {$\underset{10}{Y}$}
                child { node {$\underset{8}{X}$}
                    child { node { $\underset{6}{\neg V}$ }
                        child { node { $\underset{3}{\neg V \vee Y}$ }
                            child { node { $\underset{1}{\neg V \vee Y \vee Z}$ } }
                            child { node { $\underset{2}{\neg Z}$ } }
                        }
                        child { node { $\underset{5}{\neg Y}$ }
                            child { node { $\neg Z$ } }
                            child { node { $\underset{4}{\neg Y \vee Z}$ } }
                        }
                    }
                    child { node { $\underset{7}{X \vee V}$ } }
                }
            child { node { $\underset{9}{\neg X \vee Y}$ } }
        };
        \end{tikzpicture}
		\caption{Példa szerkezeti fára.}
		\label{fig:szerkfa}
	\end{figure}
	
	\noindent \textbf{Rezolúciós stratégiák}:
	
	\begin{itemize}
        \item \textit{Lineáris rezolúció}: Egy $S$ klózhalmazból való \textbf{\emph{lineáris rezolúciós levezetés}} egy olyan $k_{1},l_{1},k_{2},l_{2}, \ldots, k_{m-1},l_{m-1}, k_{m}$ rezolúciós levezetés, amelyben minden $j = 2, 3, \ldots, m$-re $k_{j}$ a $(k_{j-1},l_{j-1})$ klózpár rezolvense. A $k_{j}$ klózokat \emph{\textbf{centrális klóz}}oknak, az $l_{j}$ klózokat \textbf{\emph{mellékklóz}}oknak nevezzük.		
		
		\noindent Tetszőleges rezolúciós levezetés átírható lineárissá, azaz a \emph{lineáris rezolúciós kalkulus teljes}.
		
        \item \textit{Lineáris inputrezolúció}: Egy $S$ klózhalmazból való \textbf{\emph{lineáris inputrezolúciós levezetés}} egy olyan $k_{1},l_{1},k_{2},l_{2}, \ldots, k_{m-1},l_{m-1}, k_{m}$ lineáris rezolúciós levezetés, amelyben minden 	$j = 1, 2, \ldots, m-1$-re $l_{j} \in S$, azaz a lineáris inputrezolúciós levezetésben a mellékklózok $S$ elemei. Nem teljes (kivéve Horn-klózok).

        \item \textit{Egységrezolúció:} Egy $S$ klózhalmazból való \textbf{\emph{egységrezolúciós levezetés}} egy olyan $k_{1}, \ldots, k_{m}$ rezolúciós levezetés, ahol minden $j = 1, 2, \ldots, m$-re $k_{j} \in S$, ha $k_j \not \in S$, \\
        akkor $k_j$ két olyan őt a levezetésben megelőző $k_s, k_t$ klóznak a rezolvense, amelyek közül az egyik egségklóz. Nem teljes.
	\end{itemize}

    \noindent A lineáris inputrezolúciós stratégia nem teljes, de megadható olyan formulaosztály, melyre az.\\
    A legfeljebb egy negált literált tartalmazó klózokat \textbf{\emph{Horn-klózok}}nak nevezzük, a Horn-formulák pedig azok a formulák, melyek konjunktív normálformája Horn-klózok konjunkciója. \\
    A lineáris inputrezolúciós stratégia Horn-formulák esetén teljes.
	
	\subsection*{Predikátumkalkulus}
	
	\subsubsection*{Elsőrendű logikai nyelvek szintaxisa}
	
	Egy elsőrendű logikai nyelv ábécéje logikai és logikán kívüli szimbólumokat, továbbá elválasztójeleket tartalmaz.
	A logikán kívüli szimbólumhalmaz megadható $<Srt, Pr, Fn, Cnst>$ alakban, ahol:
	
	\begin{enumerate}
		\item	$Srt$ nemüres halmaz, elemei fajtákat szimbolizálnak,
		\item	$Pr$ nemüres halmaz, elemei predikátumszimbólumok,
		\item	$Fn$ halmaz elemei függvényszimbólumok,
		\item	$Cnst$ pedig a függvényszimbólumok halmaza.
	\end{enumerate}

\newpage
	\noindent Az $<Srt, Pr, Fn, Cnst>$ ábécé szignatúrája egy $<\nu_{1}, \nu_{2}, \nu_{3}>$ hármas, ahol
	
	\begin{enumerate}
		\item $\nu_{1}$ a $\forall P \in Pr$ \emph{predikátumszimbólumhoz} annak \emph{alakját},\\
%        azaz a $(\pi_{1}, \pi_{2}, \ldots, \pi_{k})$ fajtasorozatot,
		\item $\nu_{2}$ a $\forall f \in Fn$ \emph{függvényszimbólumhoz} annak \emph{alakját}, \\
%        azaz a $(\pi_{1}, \pi_{2}, \ldots, \pi_{k}, \pi)$ fajtasorozatot és
		\item $\nu_{3}$ $\forall c \in Cnst$ \emph{konstansszimbólumhoz} annak \emph{fajtáját}, \\
%        azaz $(\pi)$-t $\pi_{1}, \pi_{2}, \ldots, \pi_{k},\ \pi \in Srt\quad (k > 0)$
	\end{enumerate}
	\noindent rendeli.\\
	
    \noindent Logikai jelek az ítéletlogikában is használt logikai összekötőjelek, valamint az univerzális ($\forall$) és egzisztenciális ($\exists$) kvantorok és a különböző fajtájú individuumváltozók.\\

    \noindent Egy elsőrendű nyelv ábécéjében minden $\pi \in Srt$ fajtához szimbólumoknak megszámlálhatóan végtelen $v_{1}^{\pi}, v_{2}^{\pi}, \ldots$ rendszere tartozik, ezeket a szimbólumokat nevezzük $\pi$ fajtájú változóknak.\\
    Elválasztójel a nyitó és csukó zárójelek, és a vessző.\\
	
    \noindent Az elsőrendű logikai nyelvekben az elválasztójelek és a logikai jelek mindig ugyanazok, viszont a logikán kívüli jelek halmaza, illetve ezek szignatúrája nyelvről nyelvre lényegesen különbözhet. Ezért mindig megadjuk a $<Srt, Pr, Fn, Cnst>$ négyest és ennek $<\nu_{1}, \nu_{2}, \nu_{3}>$ szignatúráját, amikor egy elsőrendű logikai nyelv ábécéjére hivatkozunk.\\

    \noindent Jelölése $V[V_{\nu}]$, ahol $V_{\nu}$ adja meg a $<\nu_{1}, \nu_{2}, \nu_{3}>$ szignatúrájú $<Srt, Pr, Fn, Cnst>$ négyest.\\

	\noindent \textbf{Termek}: A $V[V_{\nu}]$ ábécé feletti termek halmaza $\mathcal{L}_{t}[V_{\nu}]$, ami a következő tulajdonságokkal bír:
	
	\begin{enumerate}
		\item Minden $\pi \in Srt$ fajtájú változó és konstans $\pi$ fajtájú term.
        \item Ha az $f \in Fn$ függvényszimbólum $(\pi_{1}, \pi_{2}, \ldots, \pi_{k}, \pi)$ alakú és $t_{1}, t_{2}, \ldots, t_{k}$ -- rendre\\
         $\pi_{1}, \pi_{2}, \ldots, \pi_{k}$ fajtájú -- termek, akkor az $f(s_{1}, s_{2}, \ldots, s_{k})$ egy $\pi$ fajtájú term.
		\item Minden term az 1-2. szabályok véges sokszori alkalmazásával áll elő.
	\end{enumerate}

	\noindent \textbf{Formulák}: A $V[V_{\nu}]$ ábécé feletti elsőrendű formulák halmaza $\mathcal{L}_{f}[V_{\nu}]$, ami a következő tulajdonságokkal bír:
	
	\begin{enumerate}
		\item	Ha a $\boldsymbol{P} \in Pr$ \textbf{\emph{predikátumszimbólum}} $(\pi_{1}, \pi_{2}, \ldots, \pi_{k})$ alakú
		és az $\boldsymbol{t_{1}, t_{2}, \ldots, t_{k}}$ -- rendre $\pi_{1}, \pi_{2}, \ldots, \pi_{k}$ fajtájú --
		\emph{\textbf{termek}}, akkor a $\boldsymbol{P(t_{1}, t_{2}, \ldots, t_{k})}$ \emph{\textbf{szó egy elsőrendű formula}}.
		Az így nyert formulákat atomi formuláknak nevezzük.
		
		\item	Ha $S$ elsőrendű formula, akkor $\neg S$ is az.
		
		\item	Ha $S$ és $T$ elsőrendű formulák és $\circ$ binér logikai összekötőjel,
		akkor $(S \circ T)$ is elsőrendű formula.
		
		\item	Ha $S$ eleme elsőrendű formula, $Q$ kvantor ($\forall$ vagy $\exists$) és $x$
		tetszőleges változó, akkor $QxS$ is elsőrendű formula. Az így nyert formulákat kvantált formuláknak nevezzük,
		a $\forall xS$ alakú formulák univerzálisan kvantált formulák, a $\exists xS$ alakú formulák
		pedig egzisztenciálisan kvantált formulák. A kvantált formulákban $Qx$ a formula prefixe, $S$
		pedig a magja.
		
		\item	Minden elsőrendű formula az 1-4. szabályok véges sokszori alkalmazásával áll elő.
	\end{enumerate}
	
    \noindent A $V[V_{\nu}]$ ábécé feletti elsőrendű logikai nyelv $\mathcal{L}[V_{\nu}] = \mathcal{L}_{t}[V_{\nu}] \cup \mathcal{L}_{f}[V_{\nu}]$, azaz $\mathcal{L}[V_{\nu}]$ minden szava vagy term, vagy formula.\\
	
	\noindent A negációs, konjunkciós, diszjunkciós, implikációs (ezek jelentése ua., mint nulladrendben) és kvantált formulák összetett formulák.\\
	
	\noindent Az elsőrendű logikai nyelv prímformulái az atomi formulák és a kvantált formulák.\\
	
	\noindent \textbf{Változóelőfordulás fajtái}: Egy formula $x$ változójának egy előfordulása:
	
	\begin{itemize}
		\item	szabad, ha nem esik $x$-re vonatkozó kvantor hatáskörébe,
		
		\item	kötött, ha $x$-re vonatkozó kvantor hatáskörébe esik.
	\end{itemize}
	
	\noindent \textbf{Változó fajtái}: \emph{Egy formula $x$ változója}:
	
	\begin{itemize}
		\item	\emph{szabad}, ha minden előfordulása szabad,
		\item	\emph{kötött}, ha minden előfordulása kötött, és
		\item	\emph{vegyes}, ha van szabad és kötött előfordulása is.
	\end{itemize}
	
	\noindent \textbf{Formula zártsága, nyíltsága}: \emph{Egy formula}:
	
	\begin{itemize}
		\item	\emph{zárt}, ha minden változója kötött,
		\item	\emph{nyílt}, ha legalább egy változójának van szabad előfordulása és
		\item	\emph{kvantormentes}, ha nincs benne kvantor
	\end{itemize}
	
	\noindent \emph{Megjegyzés}: a zárt formulák elsőrendű állításokat szimbolizálnak (egy elsőrendű állítás nem más, mint elemek egy halmazára megfogalmazott kijelentő mondat).
	
	\subsubsection*{Az elsőrendű logika szemantikája}
	
	\noindent \textbf{Matematikai struktúra}: Matematikai struktúrán egy $\Big<U, R, M, K\Big>$ négyest értünk, ahol:
	
	\begin{enumerate}
		\item	$U = \bigcup\limits_{\pi} U_{\pi}$ nem üres alaphalmaz (univerzum),
		
		\item	$R$ az $U$-n értelmezett logikai függvények (relációk) halmaza,
		
		\item	$M$ az $U$-n értelmezett matematikai függvények (alapműveletek) halmaza,
		
		\item	$K$ az $U$ kijelölt elemeinek (konstansainak) halmaza (lehet üres).
	\end{enumerate}
	
	\noindent \textbf{Interpretáció}: Az interpretáció egy $\Big<U, R, M, K\Big>$ matematikai struktúra és\\
	$\mathcal{I} = \Big<\mathcal{I}_{Srt}, \mathcal{I}_{Pr}, \mathcal{I}_{Fn}, \mathcal{I}_{Cnst}\Big>$
	függvénynégyes, ahol:
	
	\begin{itemize}
		\item az $\mathcal{I}_{Srt} : \pi \mapsto U_{\pi}$ függvény megad minden egyes $\pi \in Srt$ fajtához egy $U_{\pi}$ nemüres halmazt, a $\pi$ fajtájú individuumok halmazát,
        \item az $\mathcal{I}_{Pr} : P \mapsto P^{\mathcal{I}}$ függvény megad minden $(\pi_{1}, \pi_{2}, \ldots, \pi_{k})$ alakú $P \in Pr$ \lword{predikátumszimbólumhoz} egy $P^{\mathcal{I}} : U_{\pi_{1}} \times U_{\pi_{2}} \times \ldots \times U_{\pi_{k}} \to \mathbb{L}$ logikai függvényt (relációt),
        \item az $\mathcal{I}_{Fn} : f \mapsto f^{\mathcal{I}}$ függvény hozzárendel minden $(\pi_{1}, \pi_{2}, \ldots, \pi_{k}, \pi)$ alakú $f \in Fn$ \lword{függvényszimbólumhoz} egy $P^{\mathcal{I}} : U_{\pi_{1}} \times U_{\pi_{2}} \times \ldots \times U_{\pi_{k}} \to U_{\pi}$ matematikai függvényt (műveletet),
        \item	az $\mathcal{I}_{Cnst} : c \mapsto ct^{\mathcal{I}}$ pedig minden $\pi$ fajtájú $c \in Cnst$ konstansszimbólumhoz az $U_{\pi}$ individuumtartománynak egy individuumát
		rendeli, azaz $c^{\mathcal{I}} \in U_{\pi}$.
 	\end{itemize}
 	
    \noindent \textbf{Változókiértékelés}: Legyen az $\mathcal{L}[V_{\nu}]$ nyelvnek $\mathcal{I}$ egy interpretációja, az interpretáció univerzuma legyen U és jelölje V a nyelv változóinak halmazát. Egy olyan $\kappa : V \to U$ leképezést, ahol ha $x$ $\pi$ fajtájú változó, akkor $\kappa(x) \in U_{\pi}$, $\mathcal{I}$-beli \emph{\textbf{változókiértékelésnek}} nevezünk.\\
 	
 	\noindent \textbf{$\mathcal{L}_{t}[V_{\nu}]$ szemantikája}:
    Legyen az $\mathcal{L}[V_{\nu}]$ nyelvnek $\mathcal{I}$ egy interpretációja és $\kappa$ egy $\mathcal{I}$-beli változókiértékelés. Az $\mathcal{L}[V_{\nu}]$ nyelv egy $\pi$ fajtájú $t$ termjének értéke $\mathcal{I}$-ben a $\kappa$ változókiértékelés mellett az alábbi -- $|t|^{\mathcal{I},\kappa}$-val jelölt -- $U_{\pi}$-beli individuum:
 	
 	\begin{enumerate}
 		\item ha $c \in Cnst$ $\pi$ fajtájú konstansszimbólum, akkor $|c|^{\mathcal{I},\kappa}$ az $U_{\pi}$-beli $c^{\mathcal{I}}$ individuum,
 		
 		\item ha $x$ $\pi$ fajtájú változó, akkor $|x|^{\mathcal{I},\kappa}$ az $U_{\pi}$-beli $\kappa(x)$ individuum,
        \item ha $t_{1}, t_{2}, \ldots, t_{k}$ rendre $\pi_{1}, \pi_{2}, \ldots, \pi_{k}$ fajtájú termek és ezek értékei a $\kappa$ változókiértékelés mellett rendre az $U_{\pi_{1}}$-beli $|t_{1}|^{\mathcal{I},\kappa}$, az $U_{\pi_{2}}$-beli $|t_{2}|^{\mathcal{I},\kappa}$ \ldots és az $U_{\pi_{k}}$-beli $|t_{k}|^{\mathcal{I},\kappa}$ individuumok, akkor egy $(\pi_{1}, \pi_{2}, \ldots, \pi_{k}, \pi)$ alakú $f \in Fn$ függvényszimbólum esetén $|f(t_{1}, t_{2}, \ldots, t_{k})|^{\mathcal{I},\kappa}$ az $U_{\pi}$-beli
 		$f^{\mathcal{I}}(|t_{1}|^{\mathcal{I},\kappa}, |t_{2}|^{\mathcal{I},\kappa}, \ldots, |t_{k}|^{\mathcal{I},\kappa})$ individuum.
    \end{enumerate}
 	
    \noindent \textbf{Változókiértékelés $x$-variánsa}: Legyen $x$ egy változó. A $\kappa^{*}$ változókiértékelés a $\kappa$ változókiértékelés $x$-variánsa, ha $\kappa^{*}(y) = y$ minden $x$-től különböző $y$ változó esetén.\\
 	
 	\noindent \textbf{Elsőrendű logikai formula logikai értéke}:
    Legyen az $\mathcal{L}[V_{\nu}]$ nyelvnek $\mathcal{I}$ egy interpretációja és $\kappa$ egy $\mathcal{I}$-beli változókiértékelés. Az $\mathcal{L}[V_{\nu}]$ nyelv egy $C$ formulájához $\mathcal{I}$-ben a $\kappa$ változókiértékelés mellett az alábbi -- $|C|^{\mathcal{I},\kappa}$-val jelölt -- igazságértéket rendeljük:
 	
 	\begin{enumerate}
 		\item	$|P(t_{1}, t_{2}, \ldots, t_{k})|^{\mathcal{I},\kappa} = \left\{
		 		\begin{array}{lr}
		 		igaz & : P^{\mathcal{I}}(|t_{1}|^{\mathcal{I},\kappa}, |t_{2}|^{\mathcal{I},\kappa}, \ldots, |t_{k}|^{\mathcal{I},\kappa}) = igaz\\
		 		hamis & : \text{különben}
		 		\end{array}
	 		\right\}$
	 		
	 	\item	$|\neg A|^{\mathcal{I},\kappa}$ legyen $\neg |A|^{\mathcal{I},\kappa}$
	 	
	 	\item	$|A \wedge B|^{\mathcal{I},\kappa}$ legyen $|A|^{\mathcal{I},\kappa} \wedge |B|^{\mathcal{I},\kappa}$
	 	
	 	\item	$|A \vee B|^{\mathcal{I},\kappa}$ legyen $|A|^{\mathcal{I},\kappa} \vee |B|^{\mathcal{I},\kappa}$
	 	
	 	\item	$|A \supset B|^{\mathcal{I},\kappa}$ legyen $|A|^{\mathcal{I},\kappa} \supset |B|^{\mathcal{I},\kappa}$
	 	
	 	\item	$|\forall x A|^{\mathcal{I},\kappa} = \left\{
	 	\begin{array}{lr}
	 	igaz & : |A|^{\mathcal{I},\kappa^{*}} = igaz \ \kappa \ minden \ \kappa^{*} \ \text{x-variansára} \\
	 	hamis & : \text{különben}
	 	\end{array}
	 	\right\}$
	 	
	 	\item	$|\exists x A|^{\mathcal{I},\kappa} = \left\{
	 	\begin{array}{lr}
	 	igaz & : |A|^{\mathcal{I},\kappa^{*}} = igaz \ \kappa \ valamely \ \kappa^{*} \ \text{x-variansára} \\
	 	hamis & : \text{különben}
	 	\end{array}
	 	\right\}$
	 	
 	\end{enumerate}
	
    \noindent \textbf{Elsőrendű formula kielégíthetősége}: Egy $A$ elsőrendű formula kielégíthető, ha van olyan $\mathcal{I}$ interpretáció és $\kappa$ változókiértékelés, amelyre $|A|^{\mathcal{I},\kappa} = igaz$ (ekkor azt mondjuk, hogy az $\mathcal{I}$ interpretáció és $\kappa$ változókiértékelés kielégíti $A$-t),
	különben kielégíthetetlen.\\
	
    \noindent Amennyiben az $A$ formula zárt, igazságértékét egyedül az interpretáció határozza meg. Ha $|A|^{\mathcal{I}} = igaz$, azt mondjuk, hogy az $\mathcal{I}$ kielégíti $A$-t vagy másképpen: $\mathcal{I}$ modellje $A$-nak ($\mathcal{I} \models A$).\\
	
    \noindent \textbf{Logikailag igaz elsőrendű formula}: Egy $A$ elsőrendű logikai formula logikailag igaz, ha minden $\mathcal{I}$ interpretációban és $\mathcal{I}$ minden $\kappa$ változókiértékelése mellett $|A|^{\mathcal{I},\kappa} = igaz$.\\
    Jelölése: $\models A$.\\
	
	\noindent \textbf{Szemantikus következmény}: Azt mondjuk, hogy a $G$ formula \textit{szemantikus következménye} az
	$\mathcal{F}$ formulahalmaznak, ha minden olyan $\mathcal{I}$ interpretációra, amelyre $\mathcal{I} \models \mathcal{F}$
	fennáll, $\mathcal{I} \models G$ is igaz (jelölés: $\mathcal{F} \models G$).\\
	
	\noindent \textbf{Tétel}: Legyenek $A_{1}, A_{2}, \ldots, A_{n}, B$ ($n \geq 1$) tetszőleges, ugyanabból az elsőrendű logikai nyelvből való formulák. Ekkor
    \[
        \left\{A_{1}, A_{2}, \ldots, A_{n}\right\} \models B \Leftrightarrow A_{1} \wedge A_{2} \wedge \ldots \wedge A_{n} \wedge \neg B\ \text{kielégíthetetlen}
    \]
	
    \noindent \textbf{Rezolúció}: Elsőrendű predikátumkalkulusban is végezhető rezolúció, ráadásul a módszer helyes és teljes is. Nehézséget a klózok kialakítása okozhat, amelyek zárt,
	univerzálisan kvantált literálok konjunkciójából állnak. Ehhez eszközeink a prenex-, illetve skolem-formák.
	
	\section*{Számításelmélet}
	
	\subsection*{Kiszámíthatóság}

	\subsubsection*{Problémák mint formális nyelvek}	

    \noindent \emph{\textbf{Kiszámítási problémának}} nevezünk egy olyan, a matematika nyelvén megfogalmazott kérdést, amire egy algoritmussal szeretnénk megadni a választ. A gyakorlati élet szinte minden \lword{problémájához} rendelhető, megfelelő absztrakciót használva, egy kiszámítási probléma.\\
	
	\noindent Egy problémát a hozzá tartozó konkrét bementettel együtt \emph{\textbf{a probléma egy példányának}} nevezzük.\\
	
    \noindent Speciális kiszámítási probléma az eldöntési probléma. Ilyenkor a problémával kapcsolatos kérdés egy eldöntendő kérdés, tehát a probléma egy példányára a válasz "igen" vagy "nem" lesz.\\

    \noindent Egy kiszámítási probléma reprezentálható egy $f : A \to B$ függvénnyel. Az $A$ halmaz tartalmazza a probléma egyes bemeneteit, jellemzően egy megfelelő ábécé feletti szóban elkódolva, míg a $B$ halmaz tartalmazza a bemenetekre adott válaszokat, szintén valamely alkalmas ábécé feletti szóban elkódolva. Értelemszerűen, ha eldöntési problémáról van szó, akkor az $f$ értékkészlete, vagyis a $B$ 	egy két elemű halmaz: $\left\{igen, nem\right\}$, $\left\{1, 0\right\}$, stb.\\
	
    \noindent \textbf{Kiszámítható függvény}: Egy $f : A \to B$ függvényt \textit{kiszámíthatónak} nevezünk, ha minden $x \in A$ elemre az $f(x) \in B$ függvényérték kiszámítható valamilyen 	algoritmikus modellel.\\
	
    \noindent \textbf{Megoldható, eldönthető probléma}: Egy kiszámítási probléma \textit{megoldható} (eldöntési probléma esetén azt mondjuk, hogy \textit{eldönthető}), ha az általa meghatározott függvény kiszámítható.\\

    \noindent \textbf{Algoritmusok időigénye}: Legyenek $f,g: \mathbb{N} \to \mathbb{N}$ függvények.\\

    \noindent Azt mondjuk, hogy $f$ legfeljebb olyan gyorsan nő, mint $g$ (jelölése: $f(n) = \mathcal{O}(g(n))$), ha
    \[
        \exists c>0,\ n_{0} \in \mathbb{N} : f(n) \leq c * g(n)\ \ \forall n \geq n_{0}.
    \]

    \noindent Az $f(n) = \Omega(g(n))$ jelöli azt, hogy $g(n) = \mathcal{O}(f(n))$ teljesül. \\
    \noindent Az $f(n) = \Theta(g(n))$ jelöli azt, hogy  $f(n) = \mathcal{O}(g(n))$ és $f(n) = \Omega(g(n))$ is teljesül.\\
	
	\noindent \textbf{Példa}: $3n^{3} + 5n^{2} + 6 = \mathcal{O}(n^{3})$, $n^{k} = \mathcal{O}(2^{n}) \ \forall k \geq 0$, stb.\\
	
	\noindent \textbf{Tétel}: Minden polinomiális függvény lassabban nő, mint bármely exponenciális függvény, azaz minden $p(n)$ polinomhoz és $c>0$-hoz $\exists n_{0}$ egész szám, hogy $\forall n \geq n_{0}$ esetén $p(n) \leq 2^{cn}$\\
	
    \noindent \textbf{Kiszámítási probléma megfeleltetése eldöntési problémának}: Tekintsünk egy $P$ kiszámítási problémát és legyen $f: A \to B$ a $P$ által meghatározott függvény.\\

    \noindent Ekkor megadható $P$-hez egy $P'$ eldöntési probléma úgy, hogy $P'$ pontosan akkor eldönthető, ha $P$ kiszámítható. Állítsuk párba ugyanis minden $a \in A$ elemre az $a$ és $f(a)$ elemeket, és kódoljuk el az így kapott párokat egy-egy szóban.\\

    \noindent Ezek után legyen $P'$ az így kapott szavakból képzett formális nyelv.\\

    \noindent Nyilvánvaló, hogy ha minden $a \in A$ és $b \in B$ elemre az $(a,b) \in P'$ tartalmazás eldönthető (azaz $P'$ eldönthető), akkor $P$ kiszámítható és fordítva. E megfeleltetés miatt a továbbiakban jellemzően eldöntési problémákkal foglalkozunk.\\

    \noindent Az algoritmus fogalmának pontos megfogalmazásával a múlt század első felében többen is próbálkoztak. Ennek eredményeképpen több, egymástól különböző fogalom is megszületett, mint például a lambda-függvények, rekurzív függvények, Markov-gép és a Turing-gép. Ezek a fogalmak egyenrangúak egymással, egymásból kifejezhetők. A gyakorlatban leginkább a Turing-gép fogalma terjedt el.

    \subsection*{Turing gépek}

	\noindent Hasonlóan a véges automatához vagy a veremautomatához, a Turing-gép is egy véges sok állapottal rendelkező eszköz. \\

    \noindent A Turing-gép egy két irányban végtelen szalagon dolgozik. \\

    \noindent A szalag cellákra van osztva, tulajdonképpen ez a gép (korlátlan) memóriája. Kezdetben a szalagon csak a bemenő szó van, minden cellán egy betű. A szalag többi cellája egy úgynevezett blank vagy szóköz ($\sqcup$) szimbólumokkal van feltöltve. Kezdetben a gép úgynevezett író-olvasó feje a bemenő szó első betűjén áll és a gép a kezdőállapotában van. \\

    \noindent A gép az író-olvasó fejet tetszőlegesen képes mozgatni a szalagon. Képes továbbá a fej pozíciójában a szalag tartalmát kiolvasni és átírni. \\

    \noindent A gépnek van két kitüntetett állapota, a $q_{i}$ és a $q_{n}$ állapotok. Ha ezekbe az állapotokba kerül, akkor rendre elfogadja illetve elutasítja a bemenő szót. \\

    \noindent A vezérlő (legalább az) egyik állapota végállapot, s ha a gép ebbe kerül, akkor megáll. Az egyik kijelölt szalag üres jelektől különböző részét tekintjük a gép kimenetének (output). A vezérlő egy kijelölt állapotát kezdőállapotnak nevezzük, s a Turing-gép indulásakor a gép ebben az állapotban van.\\


    \noindent Szokás ilyenkor azt mondani, hogy az adott Turing-gép elfogadta ezt az inputot. A Turing-gépeket felhasználhatjuk függvények kiszámolására, azaz az argumentumokat a bemeneti szalagra írva, a gépet elindítva a Turing-gép a kimeneti szalagra a függvény végeredményét írva megáll.\\

    \noindent Felhasználhatjuk a Turing-gépeket nyelvek felismerésére is. Szavaknak nevezzük az A ábécé betűiből alkotott véges sorozatokat. Nyelvnek nevezzük szavak egy halmazát. A T Turing-gép által felismert LT nyelv pontosan azokból a szavakból áll, melyekkel mint bemenettel indítva a Turing-gép megáll.\\

    \noindent Egy L nyelvet rekurzívan felsorolhatónak nevezünk, ha van olyan Turing-gép amely által felismert nyelv éppen az L. Egy L nyelv rekurzív, ha létezik olyan Turing-gép, mely tetszőleges inputra megáll, és a szóhoz tartozó végállapot pontosan akkor egyezik meg az egyik előre kijelölt állapottal, ha a szó L-beli. Az f függvény parciálisan rekurzív, ha létezik olyan Turing-gép, amely kiszámolja. Az f függvény rekurzív, ha létezik olyan Turing-gép, amely kiszámolja; és az output minden bemenetre definiálva van.
	
	\subsubsection*{Algoritmusmodellek}
	
	\begin{itemize}
		\item	\textbf{Gödel}: rekurzív függvények (primitív rekurzív függvények 1931-ben, majd általánosabb 1934-ben)
		\item	\textbf{Church}: $\lambda$-kalkulus, $\lambda$-definiálható függvények: ekvivalensek a rekurzív függvényekkel (bizonyított)
		\item	\textbf{Turing}: Turing-gép (1936), a $\lambda$-definiálható és a Turing-géppel kiszámítható függvények megegyeznek (bizonyított)
	\end{itemize}
	
    \noindent \textbf{Church-Turing tézis}: A kiszámíthatóság ismert matematikai modelljei ekvivalensek az effektíven kiszámítható függvények osztályával(, azaz nem ismerünk a Turing gép által reprezentált algoritmus modellnél erősebb eszközt). A tézis nem tétel, mert elemeit nem tudjuk formálisan definiálni.\\
	
    \noindent Azaz, ami algoritmussal kiszámítható, az Turing-értelemben kiszámítható:
    \begin{itemize}
        \item Az f parciális függvény akkor és csak akkor kiszámítható, ha f parciálisan rekurzív.
        \item Az f függvény akkor és csak akkor kiszámítható, ha f rekurzív.
        \item Az L nyelvhez tartozás problémája algoritmussal csak akkor és akkor eldönthető, ha L rekurzív.
    \end{itemize}

    \noindent Ezekben az állításokban két fajta kiszámíthatóságról esik szó. A Turing-értelemben kiszámíthatóság jól definiált fogalom, míg az algoritmussal kiszámíthatóság nem az. Ennek megfelelően ez a tétel nem bizonyítható, viszont a gyakorlati tapasztalatokkal egybevág.\\

    \noindent \textbf{Állítás}. Van olyan nyelv, mely nem rekurzív felsorolható.\\
\newpage
    \noindent Formálisan a Turing-gépet a következő módon definiáljuk. \\
	
	\noindent \textbf{A Turing-gép formális definíciója}: A Turing-gép egy olyan
	$M = (Q, \Sigma, \Gamma, \delta, q_{0}, q_{i}, q_{n})$ rendszer, ahol:
	
	\begin{itemize}
		
		\item	$Q$ az állapotok véges, nem üres halmaza,
		
		\item	$q_{0}, q_{i}, q_{n} \in Q$,
        \begin{itemize}
            \item $q_{0}$ a kezdőállapot,
            \item $q_{i}$ az elfogadó állapot,
            \item $q_{n}$ pedig az elutasító állapot,
        \end{itemize}
		
		\item	$\Sigma$ és $\Gamma$ ábécék, a bemenő jelek és a szalagszimbólumok ábécéje úgy, hogy
		$\Sigma \subseteq \Gamma$ és $\Gamma - \Sigma$ tartalmaz egy speciális $\boldsymbol{\sqcup}$ szimbólumot,
		
		\item	$\delta : (Q - \left\{q_{i},q_{n}\right\}) \times \Gamma \to Q \times \Gamma \times \left\{L, R, S\right\}$
		az átmenetfüggvény.

	\end{itemize}
	
	\noindent Úgy mint a veremautomaták esetében, egy $M$ Turing-gép működésének fázisait	is konfigurációkkal írhatjuk le.\\
	
	\noindent \textbf{Turing-gép konfigurációja}: Az $M$ Turing-gép konfigurációja egy olyan $uqv$ szó, ahol
	$q \in Q$ és $u, v \in \Gamma^{*}$, $v \not = \varepsilon$. Ez a konfiguráció az $M$ azon állapotát tükrözi
	amikor a szalag tartalma $uv$ ($uv$ előtt és után a szalagon már csak $\sqcup$ van), a gép a $q$ állapotban van,
	és az író-olvasó fej a $v$ első betűjére mutat. $M$ összes konfigurációjának halmazát $\mathcal{C}_{M}$-el jelöljük.\\
	
	\noindent \textbf{Turing-gép kezdőkonfigurációja}: $M$ kezdőkonfigurációja egy olyan $q_{0}u\sqcup$ szó, ahol
	$u$ csak $\Sigma$-beli betűket tartalmaz.\\
	
    \noindent \textbf{Turing-gép konfigurációátmenete}: $M$ konfigurációátmenete egy olyan $\vdash\ \subseteq \mathcal{C}_{M} \times \mathcal{C}_{M}$ reláció, amit a következőképpen definiálunk.\\
	
    \noindent Legyen $uqav$ egy konfiguráció, ahol $a \in \Gamma$ és $u, v \in \Gamma^{*}$. A következő három esetet különböztetjük meg:
	
	\begin{enumerate}
		\item Ha $\delta(q,a) = (r, b, S)$, akkor $uqav \vdash urbv$.
		\item Ha $\delta(q,a) = (r, b, R)$, akkor $uqav \vdash ubrv'$, ahol $v' = v$, ha $v \not = \varepsilon$, különben	$v' = \sqcup$.
        \item Ha $\delta(q,a) = (r, b, L)$, akkor $uqav \vdash u'rcbv$, ahol $u'c = u$ valamely $u' \in \Gamma^{*}$-ra és $c \in \Gamma$-ra, ha $u \not = \varepsilon$, egyébként pedig $u' = \varepsilon$, $c = \sqcup$.
	\end{enumerate}
	
    \noindent Azt mondjuk, hogy $M$ \emph{véges sok lépésben eljut a} $C$ \emph{konfigurációból a}  $C'$ konfigurációba (jele $C \boldsymbol{\vdash^{*}} C'$), ha létezik olyan $n \geq 0$ és $C_{1}, \ldots C_{n}$ konfigurációsorozat, hogy $C_{1} = C$, $C_{n} = C'$ és minden $1 \leq i < n$-re $C_{i} \vdash C_{i+1}$.\\
	
    \noindent Ha $q \in \left\{q_{i}, q_{n}\right\}$, akkor azt mondjuk, hogy az $uqv$ konfiguráció egy \textbf{\emph{megállási konfiguráció}}. Továbbá, $q = q_{i}$ esetében elfogadó, míg $q = q_{n}$ esetében \textbf{\emph{elutasító konfiguráció}}ról beszélünk.\\
	
    \noindent \textbf{Turing-gép által felismert nyelv}: Az $M$ Turing-gép által felismert nyelv (jelölése $L(M)$) azoknak az $u \in \Sigma^{*}$ szavaknak a halmaza, melyekre igaz, hogy $q_{0}u\sqcup \vdash^{*} xq_{i}y$ valamely $x,y \in \Gamma^{*}$, $y \not = \varepsilon$ szavakra.
	
	\begin{figure}[H]
		\centering
		\includegraphics[width=0.6\linewidth]{img/turinggep_pelda}
		\caption{Egy, az $L = \left\{u\#u \ | \ u \in \left\{0,1\right\}^{+}\right\}$ felismerő Turing-gép.}
		\label{fig:turinggep_pelda}
	\end{figure}
	
	\noindent \textbf{Turing-gépek ekvivalenciája}: Két Turing-gépet ekvivalensnek nevezünk, ha ugyanazt a nyelvet ismerik fel.\\

	\noindent \textbf{Turing-felismerhető nyelv, rekurzívan felismerhető nyelvek osztálya}:
    Egy $L \subseteq \Sigma^{*}$ nyelv Turing-felismerhető, ha	$L = L(M)$ valamely $M$ Turing-gépre. A Turing-felismerhető nyelveket szokás \textit{rekurzívan felsorolhatónak} is nevezni. A rekurzívan felsorolható nyelvek osztályát \textbf{RE}-vel jelöljük.\\
	
	\noindent \textbf{Turing-eldönthető nyelv, rekurzív nyelvek osztálya}:
    Egy $L \subseteq \Sigma^{*}$ nyelv Turing-eldönthető, ha létezik olyan Turing-gép, amely minden bemeneten megállási konfigurációba jut és felismeri $L$-et. A Turing-felismerhető nyelveket szokás \textit{rekurzívnak} is nevezni. A rekurzív nyelvek osztályát $R$-rel jelöljük.\\
	
	\noindent \textbf{Turing-gép futási ideje, időigénye}:
    Tekintsünk egy $M = (Q, \Sigma, \Gamma, \delta, q_{0}, q_{i}, q_{n})$ Turing-gépet és annak egy s$u \in \Sigma^{*}$ bemenő szavát. Azt mondjuk, hogy $M$ futási ideje (időigénye) az $u$ szón $n$ ($n \geq 0$), ha $M$ a $q_{0}u\sqcup$ kezdőkonfigurációból $n$ lépésben el tud jutni egy megállási konfigurációba. Ha nincs ilyen szám, akkor $M$ futási ideje az $u$ szón végtelen.\\
	
    \noindent Legyen $f : \mathbb{N} \to \mathbb{N}$ egy függvény. Azt mondjuk, hogy $M$ időigénye $f(n)$ (vagy azt, hogy $M$ egy $f(n)$ időkorlátos gép), ha minden $u \in \Sigma^{*}$ input szóra $M$ időigénye az $u$ szón legfeljebb $f(l(u))$.

	\subsection*{Többszalagos Turing-gépek}
	
	A többszalagos Turing-gépek, értelemszerűen, egynél több szalaggal rendelkeznek.
	Mindegyik szalaghoz tartozik egy-egy író-olvasó fej, melyek egymástól
	függetlenül képesek mozogni a szalagon.\\
	
    \noindent \textbf{Többszalagos Turing-gép definíciója}: Legyen $k > 1$. Egy $k$-szalagos Turing-gép egy olyan $M = (Q, \Sigma, \Gamma, \delta, q_{0}, q_{i}, q_{n})$ rendszer, ahol a komponensek a $\delta$ kivételével megegyeznek az egyszalagos Turing-gép komponenseivel, $\delta$ pedig a következőképpen adódik.
	\[
        \delta : (Q - \left\{q_{i},q_{n}\right\}) \times \Gamma^{k} \to Q \times \Gamma^{k} \times \left\{L, R, S\right\}^{k}
    \]

    \noindent Legyenek $q, p \in Q$, $a_{1}, a_{2}, \ldots , a_{k}, b_{1}, b_{2}, \ldots, b_{k} \in \Gamma$ és $D_{1}, D_{2}, \ldots, D_{k} \in \left\{L, R, S\right\}$.\\

    \noindent Ha $\delta(q,a_{1}, a_{2}, \ldots , a_{k}) = (p,b_{1}, b_{2}, \ldots, b_{k}, D_{1}, D_{2}, \ldots, D_{k})$, akkor a gép akkor a gép a $q$ állapotból, ha a szalagjain rendre az
    \begin{itemize}
    	\item $a_{1}, a_{2}, \ldots , a_{k}$ betűket olvassa, át tud menni a $p$ állapotba, miközben az
    	\item $a_{1}, a_{2}, \ldots , a_{k}$ betűket átírja a $b_{1}, b_{2}, \ldots , b_{k}$ betűkre és a szalagokon a fejeket
    	\item $D_{1}, D_{2}, \ldots , D_{k}$ irányokba mozgatja.
    \end{itemize}
	
    \noindent A többszalagos Turing-gép konfigurációja, a konfigurációátmenet valamint a felismert illetve eldöntött nyelv definíciója az egyszalagos eset értelemszerű általánosítása. A többszalagos Turing-gép időigényét is az egyszalagoshoz hasonlóan definiáljuk.\\
	
	\noindent \textbf{Többszalagos és egyszalagos gépek ekvivalenciája}: Minden $k$-szalagos, $f(n)$ időkorlátos Turing-géphez
	van vele ekvivalens $\mathcal{O}(n*f(n))$ időkorlátos egyszalagos Turing-gép.
	
	\subsection*{Nemdeterminisztikus Turing-gépek}
	
	Egy $M$ nemdeterminisztikus Turing-gép állapotfüggvénye a következő alakú
    \[
	   \delta : (Q - \left\{q_{i},q_{n}\right\}) \times \mathcal{P}(\Gamma \to Q \times \Gamma \times \left\{L, R\right\})
    \]
	
    \noindent Tehát $M$ minden konfigurációjából néhány (esetleg nulla) különböző konfigurációba mehet át. Ily módon $M$ számítási sorozatai egy $u$ szón egy fával reprezentálhatók.\\

    \noindent  A fa csúcsa $M$ kezdőkonfigurációja, a szögpontjai pedig	$M$ konfigurációi. A fa minden levele megfelel $M$ egy számítási sorozatának az $u$-n. $M$ akkor fogadja el $u$-t, ha a fa valamelyik levele elfogadó konfiguráció.\\

    \noindent Nevezzük ezt a most leírt fát az $M$ nemdeterminisztikus számítási fájának az $u$-n. Az $M$ által felismert nyelv a determinisztikus esethez hasonlóan definiálható, a gép által eldöntött nyelv pedig a következőképpen.\\
	
    \noindent \textbf{Nemdeterminisztikus Turing-gép által eldöntött nyelv}: Azt mondjuk, hogy egy nemdeterminisztikus $M$ Turing-gép eldönt egy $L \subseteq \Gamma^{*}$ nyelvet, ha felismeri, és minden $u \in \Sigma^{*}$ szóra $M$ számítási sorozatai végesek és elfogadási vagy elutasítási konfigurációba vezetnek.\\

    \noindent \textbf{Nemdeterminisztikus Turing-gép időigénye}: Legyen $f : \mathbb{N} \to \mathbb{N}$ függvény, $M$ egy nemdeterminisztikus Turing-gép. Az $M$ időigénye $f(n)$, ha egy $n$ hosszú $u$ bemeneten nincsenek $M$-nek $f(n)$-nél hosszabb számítási sorozatai, azaz az $M$ számítási fája az $u$-n legfeljebb $f(n)$ magas.\\
	
	\noindent \textbf{Determinisztikus és nemdeterminisztikus Turing-gépek ekvivalenciája}:
    Minden $M$ nemdeterminisztikus Turing-géphez megadható egy ekvivalens $M'$ determinisztikus Turing-gép. Továbbá, ha $M$ $f(n)$ időigényű valamely $f : \mathbb{N} \to \mathbb{N}$ függvényre, akkor $M'$ $2^{\mathcal{O}(f(n))}$ időigényű.
	
	\subsection*{Eldönthetetlen problémák}
	
	\noindent A Turing-gép a lehető legáltalánosabb algoritmus modell, mégis vannak olyan problémák, melyek nem számíthatók ki Turing-géppel.\\
	
	\noindent \textbf{Emlékeztető}: A rekurzívan felsorolható (Turing-felismerhető) nyelvek osztályát $RE$-vel,	a rekurzív (Turing-eldönthető) nyelvek osztályát $R$-rel jelöljük.\\
	
    \noindent Világos, hogy $R \subseteq RE $. A célunk az, hogy megmutassuk: az $R$ valódi részhalmaza az $RE$-nek, azaz van olyan nyelv (probléma) ami	Turing-felismerhető, de nem eldönthető.\\
	
    \noindent Csak olyan Turing-gépeket fogunk vizsgálni, melyek bemenő ábécéje a $\left\{0, 1\right\}$ halmaz. Ez nem jelenti az általánosság megszorítását, hiszen ha	találunk egy olyan $\left\{0, 1\right\}$ feletti nyelvet, melyet nem lehet eldönteni ilyen Turing-géppel, akkor ezt a nyelvet egyáltalán nem lehet eldönteni.\\
	
	\subsubsection*{Turing-gépek kódolása}
	
    A $\left\{0, 1\right\}$ feletti szavak felsorolhatóak (vagyis megszámlálhatóak). Valóban, tekintsük azt a felsorolást, amelyben a szavak a	hosszuk szerint követik egymást, és két egyforma hosszú szó közül pedig az van előbb, amelyik az alfabetikus rendezés szerint megelőzi a másikat. Ily módon a $\left\{0, 1\right\}^{*}$ halmaz elemeinek egy felsorolása a következőképpen alakul: $w_{1} = \varepsilon$, $w_{2} = 0$, $w_{3} = 1$, $w_{4} = 00$, $w_{5} = 01$ és így tovább. Ebben a fejezetben tehát a $w_{i}$ szóval a $\left\{0, 1\right\}^{*}$ $i$. elemét jelöljük.\\
	
    \noindent Legyen továbbá $M$ egy $\left\{0, 1\right\}$ inputábécé feletti Turing-gép. Van olyan $k > 0$ szám, hogy $Q$-t felírhatjuk $Q = \left\{p_{1}, \ldots p_{k}\right\}$ alakban, ahol $p_{1} = q_{0}$, $p_{k-1} = q_{i}$, $p_{k} = q_{n}$.\\

    \noindent Továbbá, van olyan $m > 0$ szám, hogy $\Gamma$-t felírhatjuk $\Gamma = \left\{X_{1}, \ldots X_{m}\right\}$ alakban, ahol $X_{1} = 0$, $X_{2} = 1$, $X_{3} = \sqcup$, és $X_{4}, \ldots X_{m}$ az $M$ további szalagszimbólumai. Nevezzük végül az $L, R, S$ szimbólumokat (amelyek irányokat jelölnek) rendre $D_{1}$, $D_{2}$ és $D_{3}$-nak.\\

    \noindent Ezek után $M$ egy $\delta(p_{i},X_{j}) = (p_{r}, X_{s}, D_{t})$ ($0 \leq i,r \leq k$, $1 \leq j,s \leq m$ és $1 \leq t \leq 3$)	átmenete elkódolható a $0^{i}10^{j}10^{r}10^{s}10^{t}$ szóval. Mivel minden $0$-s blokk hossza legalább $1$, az átmenetet kódoló szóban nem szerepel az $11$ részszó. Tehát az M összes átmenetét kódoló szavakat összefűzhetjük egy olyan szóvá, melyben az átmeneteket az $11$ részszó választja el egymástól. Az így kapott szó pedig magát $M$-et kódolja.\\
	
    \noindent A továbbiakban $M_{i}$-vel jelöljük azt a Turing-gépet, amelyet a $w_{i}$ szó kódol ($i \geq 1$). Amennyiben $w_{i}$ nem a fent leírt kódolása egy Turing-gépnek, akkor tekintsük $M_{i}$-t olyannak, ami minden input esetén azonnal a $q_{n}$ állapotba megy, azaz $L(M_{i}) = \emptyset$.\\
	
    \noindent A későbbiekben szükségünk lesz arra, hogy elkódoljunk egy $(M, w)$ Turing-gép és bemenet párost egy $\left\{0, 1\right\}$ feletti szóban. Mivel a Turing-gépek kódolása nem tartalmazhat $111$-et, ezért $(M, w)$ kódja a következő: $M$ kódja után írunk $111$-et, majd utána $w$-t.
	
	\subsubsection*{Egy nem rekurzívan felsorolható nyelv}
	
    \noindent \textbf{Az $L_{\acute{a}tl\acute{o}}$ nyelv}: Az $L_{\acute{a}tl\acute{o}}$ nyelv azon $\left\{0, 1\right\}$ feletti Turing-gépek bináris kódjait tartalmazza, melyek nem fogadják el önmaguk kódját, mint bemenő szót, azaz
    \[
        L_{\text{átló}} = \Big\{w_{i} \ \Big| \ i \geq 1, w_{i} \notin L(M_{i}) \Big\}
    \]
	
	\noindent \textbf{Tétel}: $L_{\acute{a}tl\acute{o}} \notin RE$.
	
	\subsubsection*{Egy rekurzívan felsorolható, de nem eldönthető nyelv}
	
    \noindent \textbf{Az $L_{u}$ nyelv}: Tekintsük azon $(M, w)$ párok halmazát (egy megfelelő bináris szóban elkódolva), ahol $M$ egy $\left\{0, 1\right\}$	bemenő ábécé feletti Turing-gép, $w$ pedig egy $\left\{0, 1\right\}$ feletti szó úgy, hogy $w \in L(M)$, azaz $M$ elfogadja $w$-t.\\

    \noindent Ezt a nyelvet jelöljük $L_{u}$-val.
    \[
        L_{u} = \Big\{\langle w_{i},w_{j} \rangle \ \Big| \ i, j \geq 1, w_{j} \in L(M_{i}) \Big\}
    \]
	
	\noindent \textbf{Tétel}: $L_{u} \in RE$.\\
	
	\noindent \textbf{Tétel}: $L_{u} \notin R$.
	
	\subsubsection*{További tételek}
	
	\begin{enumerate}
		\item Legyen $L$ egy nyelv. Ha $L, \bar{L} \in RE$, akkor $L \in R$. \\
        \emph{Következmény}: a rekurzívan felsorolható nyelvek nem zártak a komplementerképzésre.
		\item	Ha $L \in R$, akkor $\bar{L} \in R$, azaz a rekurzív nyelvek zártak a komplementerképzésre.
	\end{enumerate}
	
	\subsubsection*{További eldönthetetlen problémák}
	
    \noindent \textbf{Kiszámítható függvény}: Legyen $\Sigma$ és $\Delta$ két ábécé és $f$ $\Sigma^{*}$ból $\Delta^{*}$-ba képző függvény. Azt mondjuk, hogy $f$ \emph{kiszámítható}, ha van olyan $M$ Turing-gép, hogy $M$-et egy $w \in \Sigma^{*}$ szóval a bemenetén elindítva, $M$ úgy áll meg, hogy a szalagján a $f(w) \in \Delta^{*}$ szó van.\\
	
    \noindent \textbf{Eldöntési problémák visszavezetése}: Legyen $L_{1} \subseteq \Sigma^{*}$ és $L_{2} \subseteq \Delta^{*}$ két eldöntési probléma. $L_{1}$ visszavezethető $L_{2}$-re ($L_{1} \leq L_{2}$), ha van olyan $f : \Sigma^{*} \to \Delta^{*}$ kiszámítható függvény, hogy minden $w \in \Sigma^{*}$ szóra $w \in L_{1}$ pontosan akkor teljesül, ha $f(w) \in L_{2}$ is teljesül.\\
	
    \noindent \textbf{Tétel}: Legyen $L_{1} \subseteq \Sigma^{*}$ és $L_{2} \subseteq \Delta^{*}$ két eldöntési probléma és tegyük fel, hogy $L_{1}$ visszavezethető $L_{2}$-re. Ekkor igazak a következő állítások:
	
	\begin{enumerate}
		\item Ha $L_{1}$ eldönthetetlen, akkor $L_{2}$ is.
		\item Ha $L_{1} \notin RE$ , akkor $L_{2} \notin RE$.
	\end{enumerate}
	
    \noindent \textbf{A megállási probléma}: Legyen $L_{h} = \left\{\langle M, w \rangle \ |\ M \ meg\acute{a}ll \ a \ w \ bemeneten \right\}$, azaz $L_{h}$ azon $\langle M, w \rangle$ Turing-gép és bemenet párosokat tartalmazza elkódolva, melyekre $M$ megáll a $w$ bemeneten. $L_{h}$ eldönthetetlen ($L_{u}$ visszavezethető $L_{h}$-ra), viszont $L_{h} \in RE$.\\
	
	\noindent \textbf{Az $L_{\ddot{u}res}$ probléma}: Legyen $L_{\ddot{u}res} = \Big\{\langle M \rangle \ |\ L(M) = \emptyset \Big\}$.\\
	$L_{\ddot{u}res}$ eldönthetetlen ($L_{u}$ visszavezethető $L_{\ddot{u}res}$-re), valamint $L_{\ddot{u}res} \notin RE$.\\
	
	\noindent \textbf{Rekurzívan felsorolható nyelvek (nem triviális) tulajdonsága}: Ha $\mathcal{P}$ a rekurzívan felsorolható
	nyelvek egy halmaza, akkor $\mathcal{P}$ a rekurzívan felsorolható nyelvek egy tulajdonsága. Ha $\mathcal{P} \not = \emptyset$ és
	$\mathcal{P} \not = RE$, akkor $\mathcal{P}$ nem triviális tulajdonsága a rekurzívan felsorolható nyelveknek.\\
	
	\noindent \textbf{Rice tétele}:
	Adott $\mathcal{P}$ tulajdonságra jelöljük $L_{\mathcal{P}}$-vel azon Turing-gépek kódjainak halmazát, amelyek
	$\mathcal{P}$-beli nyelvet ismernek fel. Ha $\mathcal{P}$ a rekurzívan felsorolható nyelvek egy nem triviális tulajdonsága, akkor
	$L_{\mathcal{P}}$ eldönthetetlen.\\

	\noindent \textbf{Post Megfelelkezési Probléma (röviden PMP)}: A PMP problémát a következőképpen definiáljuk. Legyen
	$\Sigma$ egy legalább két betűt tartalmazó ábécé és legyen $D = \left\{\Big[\ddfrac{u_{1}}{v_{1}}\Big], \ldots, \Big[\ddfrac{u_{n}}{v_{n}}\Big]\right\}$
	egy dominóhalmaz, melyben $n \geq 1$ és $u_{1}, \ldots, u_{n}, v_{1}, \ldots, v_{n} \in \Sigma^{+}$.\\

    \noindent A kérdés az, hogy van-e egy olyan	$1 \leq i_{1}, \ldots, i_{m} \leq m$ ($m \geq 1$) indexsorozat, melyre teljesül, hogy a $\Big[\ddfrac{u_{i_{1}}}{v_{i_{1}}}\Big], \ldots, \Big[\ddfrac{u_{i_{m}}}{v_{i_{m}}}\Big]$ dominókat egymás mellé írva alul és felül ugyanaz a szó adódik, azaz $u_{i_{1}} \ldots u_{i_{m}} = v_{i_{1}} \ldots v_{i_{m}}$. Ebben az esetben a fenti dominósorozatot a D egy megoldásának nevezzük.\\
	
	\noindent Formális nyelvként a következőképpen definiálhatjuk a PMP-t:\\
	PMP $= \Big\{ \langle D \rangle \ |\ \text{D-nek van megoldása} \Big\}$. PMP eldönthetetlen.
		
	\subsection*{Bonyolultságelmélet}
	
	A bonyolultságelmélet célja a megoldható (és ezen belül az eldönthető) problémák osztályozása a megoldáshoz szükséges
	erőforrások (jellemzően az idő és a tár) mennyisége szerint.
	
	\subsubsection*{Időbonyolultsági fogalmak}
	
    \noindent \textbf{TIME}: Legyen $f : \mathbb{N} \to \mathbb{N}$ függvény.
    \[
        \textbf{TIME}(f(n)) = \Big\{L \ \Big| \ L \ \text{eldönthető}\ \ \mathcal{O}(f(n)) \ \text{időigényű} \ \text{Turing-géppel} \Big\}
    \]
    Továbbá	
    \[
    \textbf{P} =\bigcup\limits_{k \geq 1} \textbf{TIME}(n^{k})
    \]

    \noindent Tehát \textbf{P} azon nyelveket tartalmazza, melyek eldönthetőek polinom időkorlátosdeterminisztikus Turing-géppel. Ilyen például az \textsc{Elérhetőség} probléma, melynek bemenete egy $G$ gráf és annak két kitüntetett csúcsa ($s$ és $t$). A kérdés az, hogy van-e a $G$-ben út $s$-ből $t$-be. Ha az \textsc{Elérhetőség} problémára nyelvként tekintünk, akkor írhatjuk azt, hogy\\
	
	\noindent \textsc{\textbf{Elérhetőség}}:
    \[
        \Big\{\langle G, s, t \rangle \ \Big| \ \text{\emph{G} irányított gráf ás \emph{G}-ben van út \emph{s}-ből \emph{t}-be} \Big\}
    \]
	
	\noindent Könnyen megadható az \textsc{Elérhetőség} problémáját polinom időben eldöntő determinisztikus Turing-gép, tehát \textsc{Elérhetőség} $\in$ \textbf{P}.\\

    \noindent \textbf{NTIME}: Legyen $f : \mathbb{N} \to \mathbb{N}$ függvény.
    \[
        \textbf{NTIME}(f(n)) = \Big\{L \ | \ L \ \text{eldönthető}\ \ \mathcal{O}(f(n)) \ \text{időigényű nem determinisztikus} \ \text{Turing-géppel} \Big\}
    \]

    \noindent Továbbá
    \[
        \textbf{P} =\bigcup\limits_{k \geq 1} \textbf{NTIME}(n^{k})
    \]
		
    \noindent Az \textbf{NP}-beli problémák rendelkeznek egy közös tulajdonsággal az alábbi értelemben. Ha tekintjük egy \textbf{NP}-beli probléma egy példányát és egy lehetséges "bizonyítékot" arra nézve, hogy ez a példány "igen" példánya az adott problémának, akkor ezen bizonyíték helyességének leellenőrzése polinom időben elvégezhető. Ennek megfelelően egy \textbf{NP}-beli problémát eldöntő nemdeterminisztikus Turing-gép általában úgy működik, hogy "megsejti" a probléma bemenetének egy lehetséges megoldását, és polinom időben leellenőrzi, hogy a megoldás helyes-e.\\

    \noindent Tekintsük a \textsc{Sat} problémát, amit a következőképpen definiálunk. Adott egy $\phi$ ítéletlogikai KNF. A kérdés az, hogy kielégíthető-e. Annak a bizonyítéka, hogy	a $\phi$ kielégíthető, egy olyan változó-hozzárendelés, ami mellett kiértékelve a $\phi$-t igaz értéket kapunk. Egy tetszőleges változó-hozzárendelés tehát a $\phi$ kielégíthetőségének egy lehetséges bizonyítéka .Annak leellenőrzése pedig, hogy ez a hozzárendelés tényleg igazzá teszi-e $\phi$-t, polinom időben elvégezhető. A \textsc{Sat}
	\textbf{NP}-beli probléma.\\
	
	\noindent Az a definíciókból következik, hogy fennáll a \textbf{P} $\subseteq$ \textbf{NP} tartalmazás.

    \subsection*{Polinomiális idejű visszavezetések\\}

	\noindent \textbf{\emph{Polinom időben kiszámítható függvény}}: Legyen $\Sigma$ és $\Delta$ két ábécé és $f$ $\Sigma^{*}$ból
	$\Delta^{*}$-ba képező függvény. Azt mondjuk, hogy $f$ polinom időben kiszámítható, ha kiszámítható egy polinom
	időigényű Turing-géppel.\\
	
	\noindent \textbf{\emph{Eldöntési problémák polinom idejű visszavezetése}}:
	Legyen $L_{1} \subseteq \Sigma^{*}$ és $L_{2} \subseteq \Delta^{*}$	két eldöntési probléma.
	$L_{1}$ polinom időben visszavezethető $L_{2}$-re ($L_{1} \leq_{p} L_{2}$), ha $L_{1} \leq L_{2}$ és
	a visszavezetésben használt $f$ függvény polinom időben kiszámítható.\\
	
	\noindent \textbf{Tétel}: Legyen $L_{1}$ és $L_{2}$ két probléma úgy, hogy $L_{1} \leq_{p} L_{2}$. Ha $L_{2}$
	
	\begin{enumerate}
		\item	\textbf{P}-beli, akkor $L_{1}$ is \textbf{P}-beli.
		
		\item	\textbf{NP}-beli, akkor $L_{1}$ is \textbf{NP}-beli.
	\end{enumerate}

    \noindent \textbf{P} és \textbf{NP} zártak a polinom idejű visszavezetésekre.\\
\newpage
	\subsection*{NP-teljes problémák\\}
	
	\noindent \textbf{NP-teljes probléma}: Legyen $L$ egy probléma. Azt mondjuk, hogy $L$ \textbf{NP}-teljes, ha
	
	\begin{enumerate}
		\item	\textbf{NP}-beli, és
		\item	minden további \textbf{NP}-beli probléma polinom időben visszavezethető $L$-re.
	\end{enumerate}

    \noindent Ha csak a második pont teljesül, akkor azt mondjuk, hogy L \textbf{NP}-nehéz.\\

	\noindent \textbf{Tétel}: Legyen $L$ egy \textbf{NP}-teljes probléma. Ha $L \in$ \textbf{P}, akkor \textbf{P} $=$ \textbf{NP}.\\
	
	\noindent \emph{Megjegyzés}: Jelenleg \textbf{NEM} tudunk \textbf{P}-beli \textbf{NP}-teljes problémáról!\\
	
	\noindent \textbf{Tétel}: Legyen $L_{1}$ egy \textbf{NP}-teljes, $L_{2}$ pedig \textbf{NP}-beli probléma.
	Ha $L_{1} \leq_{p} L_{2}$, akkor $L_{2}$ is \textbf{NP}-teljes.

    \subsubsection*{NP-teljes problémák\\}

    \noindent \textsc{Sat} azon konjunktív normálformákat tartalmazza, egy megfelelő ábécé felett kódolva, melyek kielégíthetőek.
    \[
        SAT = \Big\{(\phi)\ \Big|\ \phi\ \text{kielégíthető konjuknktív normálformában adott formula} \Big\}
    \]
	
	\noindent \textbf{Cook-Levin tétele}: \textsc{Sat} \textbf{NP}-teljes.\\
	
	\noindent Legyen $k \geq 1$. Ekkor k\textsc{Sat} a következő probléma:
    \[
	   k\textsc{Sat} = \Big\{\langle \phi \rangle \ \Big| \ \phi \ \text{minden tagjában \emph{k} literál van} \Big\}
    \]

	\noindent \textbf{Tétel}: 3\textsc{Sat} \textbf{NP}-teljes, ugyanis \textsc{Sat} $\leq_{p}$ 3\textsc{Sat}.\\
	
    \noindent \textsc{\textbf{Teljes részgráf}}:\\

	\noindent \textsc{Teljes részgráf}:
    \[
        \Big\{\langle G, k \rangle \ \Big| \ G \ \text{véges gráf},\ k \geq 1, \ \text{G-nek} \ \exists \ k\ \text{csúcsú teljes részgráfja} \Big\}
    \]

	\noindent Tehát a \textsc{Teljes részgráf} azon $G$ és $k$ párokat tartalmazza, megfelelő ábécé feletti
	szavakban elkódolva, melyekre igaz, hogy $G$-ben van $k$ csúcsú teljes részgráf, azaz olyan részgráf, melyben bármely két csúcs között van él.\\

    \noindent \textsc{\textbf{Független csúcshalmaz}}:\\
    \[
        \Big\{\langle G, k \rangle \ \Big| \ G \ \text{véges gráf}, k \geq 1, \ G-nek \ \exists \ k \ \text{elemű független csúcshalmaza} \Big\}
    \]
	Vagyis a  \textsc{Független csúcshalmaz} azon $G$ és $k$ párokat tartalmazza, melyekre
	igaz, hogy $G$-ben van $k$ olyan csúcs, melyek közül egyik sincs összekötve a
	másikkal.\\
	
	\noindent \textsc{\textbf{Csúcslefedés}}:\\
    \[
	\left\{\langle G, k \rangle \ \Big| \begin{array}{lr}
	\ G \ \text{véges gráf}, k \geq 1, \ \text{G-nek van olyan \emph{k} elemű csúcshalmaza}, \\ \text{mely tartalmazza \emph{G} minden élének legalább egy végpontját}
    \end{array}
	\right\}
    \]
	
	
	\noindent \textsc{Teljes részgráf}, \textsc{Független csúcshalmaz} és \textsc{Csúcslefedés} \textbf{NP}-teljesek\\
	(\textsc{Teljes részgráf} $\leq_{p}$ \textsc{Független csúcshalmaz} $\leq_{p}$ \textsc{Csúcslefedés}).\\
	
	\noindent \textsc{\textbf{Utazóügynök}}:\\
	\[\left\{\langle G, k \rangle \ \Big|
	\begin{array}{lr}
	 \text{\emph{G} véges irányítatlan gráf, az éleken egy-egy pozitív egész súllyal és van} \\ \text{\emph{G}-ben legfeljebb \emph{k} összsúlyú Hamilton kör}
	\end{array}
	 \right\}
    \]	
	
	\subsection*{Tárbonyolultság}

	A tárbonyolultságot egy speciális, úgynevezett offline Turing-gépen vizsgáljuk.\\
	
    \noindent \textbf{Off-line Turing-gép}: Offline Turing-gépnek nevezünk egy olyan többszalagos Turing-gépet, mely a bemenetet tartalmazó szalagot csak olvashatja, a többi, ún. munkaszalagokra	pedig írhat is. Az offline Turing-gép tárigényébe csak a munkaszalagokon felhasznált terület számít be.\\
	
	\noindent A továbbiakban Turing-gép alatt offline Turing-gépet értünk. \\
	
    \paragraph*{Tárbonyolultsággal kapcsolatos nyelvosztályok\\}

	\noindent \textbf{SPACE}(f(n)):
    \[
        \Big\{L\ \Big|\ L \ \text{eldönthető}\ \mathcal{O}(f(n))\ \text{tárigényű determinisztikus Turing-géppel} \Big\}
    \]


	\noindent \textbf{NSPACE}(f(n)):
    \[
        \Big\{L\ \Big|\ L\ \ \text{eldönthető}\ \mathcal{O}(f(n))\ \text{tárigényű nemdeterminisztikus Turing-géppel} \Big\}
    \]
	
    \noindent Ezek után a \textbf{P} és az \textbf{NP} osztályok tárbonyolultsági megfelelőit az alábbi módon definiálhatjuk.

	\noindent \textbf{Definíció.} \textbf{PSPACE} $=\bigcup\limits_{k > 0}$ \textbf{SPACE}($n^{k}$) és \noindent \textbf{NPSPACE} $=\bigcup\limits_{k > 0}$ \textbf{NSPACE}($n^{k}$)\\

    \noindent A szublineáris tárbonyolultságnak is van értelme, ezért valójában az alábbi tárbonyolultsági osztályokra lesz szükségünk.\\
	
	\noindent \textbf{Definíció.} \textbf{L} $=$ \textbf{SPACE}($\log_{2} n$) és \textbf{NL} $=$ \textbf{NSPACE}($\log_{2} n$) \\

    \noindent Egy nemdeterminisztikus Turing-gép determinisztikussal való szimulációja (jelenlegi tudásunk szerint) exponenciális idő-igény romlást eredményez. A tárbonyolultság esetében viszont bizonyított, hogy a determinisztikus Turing-gépek a tárbonyolultság négyzetes romlása árán képesek szimulálni a legalább logaritmikus tárbonyolultságú nemdeterminisztikus Turing-gépeket.\\
	
	\noindent \textbf{Savitch tétele}: Ha $f(n) \geq \log n$, akkor
    \[
        \textbf{NSPACE}(f(n)) \subseteq \textbf{SPACE}(f^{2}(n))
    \]

    \noindent \textbf{Következmény}. \textbf{PSPACE} = \textbf{NPSPACE}.
\end{document} 