\documentclass[12pt,norsk]{article}

\usepackage[utf8]{inputenc}
\usepackage{babel}

\usepackage{bussproofs}
\usepackage{parskip}

\usepackage{amsmath}

\usepackage{enumerate}

\usepackage[colorlinks]{hyperref}

\title{INF3170 / INF4171\\Oblig 1}

\date{\textbf{Innleveringsfrist:} 28. september, 23:59}

\begin{document}

\maketitle

\section*{Innlevering}
Besvarelsen (TXT eller PDF) skal leveres gjennom \href{http://devilry.ifi.uio.no/}{Devilry}. Innleveringsfristen er \textbf{mandag 28. september, klokken 23:59.} Dette er en individuell oppgave. Dersom oppgaven er løst gjennom omfattende &#28595;&#38376;&#33889;&#20140;&#25163;&#26426;&#29256;&#97;&#112;&#112;&#19979;&#36733; er det fint om du lister opp navnene på de du har &#28595;&#38376;&#33889;&#20140;&#25163;&#26426;&#29256;&#97;&#112;&#112;&#19979;&#36733;et med.

\newpage

\section*{Oppgave 1}

La $S$ være et bevissystem (for eksempel naturlig deduksjon). En formel $A$ er $S$-konsistent dersom $S\not\vdash \neg A$, altså dersom $\neg A$ ikke er bevisbar i $S$. Hvilke, om noen, av de følgende påstandene er ekvivalente? Der du ikke finner ekvivalenser, kan du finne logisk konsekvens én vei?

\begin{enumerate}[a.]
    \item $S$ er sunn.
    \item $S$ er komplett.
    \item $S$ er usunn.
    \item $S$ er ukomplett.
    \item Det finnes en formel $F$ slik at både $S\vdash F$ og $S\vdash \neg F$.
    \item Enhver $S$-konsistent formel er oppfyllbar.
    \item Det finnes en $S$-konsistent formel som ikke er oppfyllbar.
    \item Enhver oppfyllbar formel er $S$-konsistent.
\end{enumerate}

Du kan ikke anta at $S$ er naturlig deduksjon, så du kan ikke gjøre noen antakelser om reglene i $S$, men du kan argumentere klassisk i disse bevisene, uavhengig av om $S$ er et bevissystem for klassisk eller intuisjonistisk logikk. Bevis svarene dine.

\section*{Oppgave 2}

La $\mathsf{Hyp}(\mathcal D)$ være en rekursiv funksjon fra utledninger til mengder av formler, slik at $\mathsf{Hyp}(\mathcal D)$ er nøyaktig de åpne antakelsene i $\mathcal D$. Du kan anta at vi alltid lukker alle de antakelsene vi kan lukke.

For eksempel, for $\land I$: Vi starter med \AxiomC{$\mathcal D_1$}\noLine\UnaryInfC{$\phi$}\DisplayProof og \AxiomC{$\mathcal D_2$}\noLine\UnaryInfC{$\psi$}\DisplayProof, og setter dem sammen til utledningen \AxiomC{$\mathcal D_1$}\noLine\UnaryInfC{$\phi$}\AxiomC{$\mathcal D_2$}\noLine\UnaryInfC{$\psi$}\BinaryInfC{$\phi\land\psi$}\DisplayProof. Da har vi
\begin{align*}
    \mathsf{Hyp}\left( \AxiomC{$\mathcal D_1$}\noLine\UnaryInfC{$\phi$}\AxiomC{$\mathcal D_2$}\noLine\UnaryInfC{$\psi$}\BinaryInfC{$\phi\land\psi$}\DisplayProof \right) = \mathsf{Hyp}\left(\AxiomC{$\mathcal D_1$}\noLine\UnaryInfC{$\phi$}\DisplayProof\right)\cup \mathsf{Hyp}\left(\AxiomC{$\mathcal D_2$}\noLine\UnaryInfC{$\psi$}\DisplayProof\right).
\end{align*}
Gi hele definisjonen av $\mathsf{Hyp}(\mathcal D)$.
\end{document} 