\documentclass[norsk,a4paper]{article} \usepackage[latin1]{inputenc} \usepackage[T1]{fontenc} \usepackage[T1]{url} \usepackage{amsmath,amssymb} \usepackage{babel} \usepackage{qtree} % --- Ingen innrykk + avstand mellom avsnitt: \setlength{\parindent}{0pt} \setlength{\parskip}{1ex plus 0.5ex minus 0.2ex} \urlstyle{sf} % gir ``skrivemaskinskrift'' p? URL-er. \newenvironment{proof} {\textbf{Bevis:} \quad} {\hfill $\blacksquare$} \begin{document} \title{% L?sningsforslag - uke 5} \author{Christian Mahesh Hansen\\ \texttt{chrisha@ifi.uio.no}} \date{INF3170 - 29. januar 2004} \maketitle \section*{Oppgave 2.2.1} \newcommand{\IHA}{\ensuremath{b(X) = l(X) = r(X)}} For en utsagnslogisk formel $X$, la $b(X)$ v?re antall forekomster av \emph{bin?re logiske symboler}\footnote{logiske konnektiver som tar to argumenter} i $X$, $l(X)$ v?re antall venstreparenteser i $X$ og $r(X)$ v?re antall h?yreparenteser i $X$. \textbf{P?stand:} For enhver utsagnslogisk formel $X$ har vi at $\IHA,$ dvs. at det er like mange venstre- som h?yreparenteser i $X$. \begin{proof} Ved induksjon p? oppbygningen av utsagnslogiske formler (\emph{strukturell induksjon}). Induksjonshypotese ($I$): $\IHA$ \emph{Basissteg:} Anta $X$ atom?r. Da holder $I$ opplagt, siden $b(X) = l(X) = r(X) = 0$. \emph{Induksjonssteg:} Anta $X = \neg Y$, og at $I$ holder for $Y$. Vi ser at $b(X) = b(Y)$ ($\neg$ er et un?rt konnektiv), $l(X) = l(Y)$ og $r(X) = r(Y)$. $I$ gir oss at $b(Y) = l(Y) = r(Y)$. Vi kan derfor slutte at $I$ holder, siden $b(X) = l(X) = r(X)$. Anta $X = (Y \circ Z)$, og at $I$ holder for $Y$ og $Z$. Vi ser at $b(X) = b(Y) + b(Z) + 1$, $l(X) = l(Y) + l(Z) + 1$ og $r(X) = r(Y) + r(Z) + 1$. $I$ gir oss at $b(Y) = l(Y) = r(Y)$ og at $b(Z) = l(Z) = r(Z)$. Vi f?r da at $b(X) = l(X) = r(X)$ og $I$ holder, siden vi har lagt til $1$ til hvert av de tre m?ltallene $b$, $l$ og $r$. \end{proof} \emph{Merk:} Dette beviset er i overkant pedantisk! Normalt ville man n?yd seg med ? p?peke at negasjon ikke tilf?rer hverken bin?re konnektiver eller paranteser, og at sammensetting med bin?rt konnektiv tilf?rer n?yaktig \'{e}n av b?de bin?re konnektiver, venstre- og h?yreparanteser. \section*{Oppgave 2.2.2} Vi definerer en funksjon $d$ p? mengden av utsagnslogiske formler p? f?lgende m?te: Hvis $P$ er atom?r, s? er $d(P) = 0$. $d(\neg X) = d(X) + 1$. $d((X \circ Y)) = d(X) + d(Y) + 1$. For en utsagnslogisk formel $X$, kalles $d(X)$ \emph{graden} til $X$. Vi antar at $\to$ og $\lor$ er bin?re symboler. F?r da at \begin{align} d((\neg P \to \neg (Q \lor R))) &= d(\neg P) + d(\neg (Q \lor R)) + 1 \notag \\ &= d(P) + 1 + d(Q \lor R) + 1 + 1 \notag \\ &= 0 + 1 + d(Q) + d(R) + 1 + 1 + 1 \notag \\ &= 0 + 1 + 0 + 0 + 1 + 1 + 1 \notag \\ &= 4 \notag \end{align} \section*{Oppgave 2.6.1} Vi definerer en funksjon $r$ p? mengden $\textbf(P)$ av utsagnslogiske formler p? f?lgende m?te: Hvis $A$ er en utsagnsvariabel, s? er $r(A) = r(\neg A) = 0$. $r(\top) = r(\bot) = 0$. $r(\neg \top) = r(\neg \bot) = 1$. Videre definerer vi rekursivt at $r(\neg \neg Z) = r(Z) + 1$, $r(\alpha) = r(\alpha_{1}) + r(\alpha_{2}) + 1$ og $r(\beta) = r(\beta_{1}) + r(\beta_{2}) + 1$. For en utsagnslogisk variabel $X$, kalles $r(X)$ \emph{rangen}\footnote{Fitting bruker det engelske ordet \emph{rank}} til $X$. F?rer ikke opp selve utregningene, bare svarene: \begin{enumerate} \item La $X = (P \to Q) \to (Q \downarrow \neg R)$. Da er $d(X) = 4$ og $r(X) = 4$. \item La $X = (T \to P) \to Q$. Da er $d(X) = 2$ og $r(X) = 2$. \item La $X = Q \to (T \to P)$. Da er $d(X) = 2$ og $r(X) = 2$. \end{enumerate} Har her ikke f?rt opp selve utregningen. Det er verdt ? merke seg at \emph{graden} til en utsagnslogisk formel tilsvarer antall konnektiver i den, og at \emph{rangen} tilsvarer maksimalt antall tabl?-ekspansjoner mulig ? gj?re med formelen. \section*{Oppgave 2.9.4} Har her listet opp programmet uten ytterligere kommentarer. Programmet kan ogs? lastes ned fra gruppesiden p? kursets hjemmesider, under navnet \verb@degree_rank.pl@. \begin{verbatim} /* Degree and Rank Calculation Program - Exercise 2.9.4 Propositional operators are: neg, and, or, imp, revimp, uparrow, downarrow, notimp and notrevimp. */ ?-op(140, fy, neg). ?-op(160, xfy, [and, or, imp, revimp, uparrow, downarrow, notimp, notrevimp]). /* analyse(Z, X, Y) :- X and Y are the subformulas of Z. */ analyse(X and Y, X, Y). analyse(X or Y, X, Y). analyse(X imp Y, X, Y). analyse(X revimp Y, X, Y). analyse(X uparrow Y, X, Y). analyse(X downarrow Y, X, Y). analyse(X notimp Y, X, Y). analyse(X notrevimp Y, X, Y). /* components(X, Y, Z) :- Y and Z are the components of the formula X, as defined in the alpha and beta table. */ components(X and Y, X, Y). components(neg(X and Y), neg X, neg Y). components(X or Y, X, Y). components(neg(X or Y), neg X, neg Y). components(X imp Y, neg X, Y). components(neg(X imp Y), X, neg Y). components(X revimp Y, X, neg Y). components(neg(X revimp Y), neg X, Y). components(X uparrow Y, neg X, neg Y). components(neg(X uparrow Y), X, Y). components(X downarrow Y, neg X, neg Y). components(neg(X downarrow Y), X, Y). components(X notimp Y, X, neg Y). components(neg(X notimp Y), neg X, Y). components(X notrevimp Y, neg X, Y). components(neg(X notrevimp Y), X, neg Y). /* degree(F, D) :- D is the degree of the formula F. */ degree(neg Formula, Deg) :- degree(Formula, Degf), Deg is Degf + 1. degree(Formula, Deg) :- analyse(Formula, X, Y), degree(X, Degx), degree(Y, Degy), Deg is Degx + Degy + 1. degree(_, 0). /* rank(F, R) :- R is the rank of the formula F. */ rank(neg false, 1). rank(neg true, 1). rank(neg neg Z, Rank) :- rank(Z, Rankz), Rank is Rankz + 1. rank(Formula, Rank) :- components(Formula, X, Y), rank(X, Rankx), rank(Y, Ranky), Rank is Rankx + Ranky + 1. rank(_, 0). \end{verbatim} \section*{Oppgave 3.1.1} \newcommand{\Close}[1]{\ensuremath{\begin{matrix} #1 \\ \times \end{matrix}}} \newcommand{\FAA}{\ensuremath{P \to Q}} \newcommand{\FAB}{\ensuremath{Q \to R}} \newcommand{\FAC}{\ensuremath{(\FAA) \land (\FAB)}} \newcommand{\FAD}{\ensuremath{\neg R \land P}} \newcommand{\FAE}{\ensuremath{\neg (\FAD)}} \newcommand{\FAF}{\ensuremath{\neg ((\FAC) \to \FAE)}} \newcommand{\MatrA}{\ensuremath{\begin{matrix} \FAF \\ \FAC \\ \neg \FAE \\ \FAD \\ \FAA \\ \FAB \\ \neg R \\ P \end{matrix}}} \newcommand{\FBA}{\ensuremath{P \to Q}} \newcommand{\FBB}{\ensuremath{\neg \FBA}} \newcommand{\FBC}{\ensuremath{(\FBA) \to Q}} \newcommand{\FBD}{\ensuremath{\neg ((\neg \FBA) \to (\FBC))}} \newcommand{\MatrB}{\ensuremath{\begin{matrix} \FBD \\ \neg \FBA \\ \neg (\FBC) \\ \FBA \\ \neg Q \end{matrix}}} \newcommand{\FCA}{\ensuremath{P \to Q}} \newcommand{\FCB}{\ensuremath{(\FCA) \to P}} \newcommand{\FCC}{\ensuremath{\neg (\FCA)}} \newcommand{\FCD}{\ensuremath{\neg ((\FCB) \to P)}} \newcommand{\MatrCA}{\ensuremath{\begin{matrix} \FCD \\ \FCB \\ \neg P \end{matrix}}} \newcommand{\MatrCB}{\ensuremath{\begin{matrix} \FCC \\ P \\ \neg Q \end{matrix}}} \newcommand{\FDA}{\ensuremath{P \uparrow P}} \newcommand{\FDB}{\ensuremath{(\FDA) \uparrow P}} \newcommand{\FDC}{\ensuremath{\neg (\FDB)}} \newcommand{\MatrD}{\ensuremath{\begin{matrix} \FDC \\ \FDA \\ P \end{matrix}}} \begin{enumerate} \item \Tree [ .{\MatrA} {$\Close{\neg P}$} [ .{$Q$} {$\Close{\neg Q}$} {$\Close{R}$} ] ] \item \Tree [ .{\MatrB} [ .{$\neg P$} {$\Close{\neg \neg P}$} {$\Close{Q}$} ] {$\Close{Q}$} ] \item \Tree [ .{\MatrCA} {$\Close{\MatrCB}$} {$\Close{P}$} ] \item \Tree [ .{\MatrD} {$\Close{\neg P}$} {$\Close{\neg P}$} ] \end{enumerate} \end{document}