\documentclass[% version=last,% a5paper,% 10pt,% headings=small,% bibliography=totoc,% %titlepage=false,% twoside,% open=any,% parskip=half,% this option takes 2.5% more space than parskip draft=true,% DIV=12,% headinclude=false,% pagesize]% {scrbook} %\usepackage[notcite,notref]{showkeys} \usepackage{cclicenses} % \usepackage[utf8]{inputenc} \usepackage[english,greek,turkish]{babel} \newcommand\gr[1]{\foreignlanguage{greek}{#1}} \newcommand{\grm}[1]{\ensuremath{\text{\foreignlanguage{greek}{#1}}}} \usepackage{scrpage2} \pagestyle{scrheadings} %\ohead{\pagemark} \ohead{} %\ihead{\headmark} \ifoot{\headmark} %\ofoot{} \usepackage{float} \floatstyle{boxed} \restylefloat{figure} \renewcommand{\captionformat}{ } \setcounter{tocdepth}{0} \usepackage{multicol} \usepackage{rotating} \usepackage{calc} \newcounter{hours}\newcounter{minutes} \newcommand\printtime{\setcounter{hours}{\time/60}% \setcounter{minutes}{\time-\value{hours}*60}% \ifthenelse{\value{minutes}>9}% {saat \thehours:\theminutes}% {saat \thehours:0\theminutes}} % code adapted from the % LaTeX Companion (2d ed), p. 871 %\usepackage{dblfnote} \usepackage{verbatim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\usepackage{auto-pst-pdf} \begin{comment} \usepackage{graphicx} \usepackage{color} \usepackage{eso-pic} \definecolor{lightgray}{gray}{.95} \AddToShipoutPicture{% \AtTextCenter{% \makebox(0,0)[c]{\resizebox{\textwidth}{!}{% \rotatebox{45}{\textsf{\textbf{\color{lightgray}TASLAK}}}}} } } \end{comment} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{hfoldsty} \renewcommand{\thefootnote}{\fnsymbol{footnote}} \usepackage[neverdecrease]{paralist} \usepackage{pstricks,pst-node,pst-tree} \usepackage{amsmath,amssymb,amsthm,url} \usepackage[all]{xy} \usepackage{bm} %\renewcommand{\theequation}{\fnsymbol{equation}} %\numberwithin{equation}{document} % doesn't work; see LaTeX Companion 2d ed. p. 851 %\swapnumbers \newtheorem{theorem}{Teorem} \newtheorem{lemma}{Yard\i mci teorem} \theoremstyle{definition} \newtheorem{exercise}{Al\i\c st\i rma} \newcommand{\cexercise}{\stepcounter{exercise}\textbf{Al\i\c st\i rma \theexercise}} \newcommand{\stnd}[1]{\mathbb{#1}} \newcommand{\N}{\stnd N} \newcommand{\Z}{\stnd Z} \newcommand{\Q}{\stnd Q} \newcommand{\Qp}{\stnd Q^+} \newcommand{\B}{\stnd B} \newcommand{\liff}{\Leftrightarrow} \newcommand{\lto}{\Rightarrow} \newcommand{\denktir}{\text{ denktir }} \newcommand{\gerektirir}{\text{ gerektirir }} \newcommand{\ile}{\text{ ile }} \newcommand{\ve}{\text{ ve }} \newcommand{\virgul}{,\ } \newcommand{\bd}[1]{\mathrm D_{#1}} \newcommand{\proves}[1][2]{\vdash_{#1}} %\newcommand{\sv}[1]{#1} \renewcommand{\leq}{\leqslant} \renewcommand{\geq}{\geqslant} \begin{document} \title{\"Onermeler mant\i\u g\i% ndaki\\ % bi\c cimsel kan\i tlar } \author{David Pierce} \date{\today, \printtime} \publishers{Matematik B\"ol\"um\"u\\ Mimar Sinan G\"uzel Sanatlar \"Universitesi\\ \.Istanbul\\ \mbox{}\\ \url{dpierce@msgsu.edu.tr}\\ \url{http://mat.msgsu.edu.tr/~dpierce/}} \uppertitleback{\centering Bu notlar\\ Creative Commons Attribution--Gayriticari--Share-Alike\\ 3.0 Unported Lisans\i\ ile lisansl\i d\i r.\\ Lisans\i n bir kopyas\i n\i\ g\"orebilmek i\c cin,\\ \url{http://creativecommons.org/licenses/by-nc-sa/3.0/deed.tr}\\ adresini ziyaret edin.\\ % ya da a\c sa\u g\i daki adrese yaz\i n:\\ %Creative Commons, 444 Castro Street, Suite 900,\\ %Mountain View, California, 94041, USA.\\ \mbox{}\\ \cc \ccby David Austin Pierce \ccnc \ccsa\\ } \lowertitleback{ Bu yaz\i n\i n ana kaynaklar\i, Church'un \cite{MR18:631a}, Shoenfield'in \cite{MR1809685}, Burris'in \cite{Burris}, ve Nesin'in \cite{Nesin-OM} kitaplar\i\ ve \foreignlanguage{english}{\emph{Foundations of Mathematical Practice}} (Eyl\"ul 2010) adl\i\ notlar\i md\i r. Baz{\i} terimler, \cite{Demirtas,MTS} kaynaklar{\i}ndan al{\i}nm\i\c st{\i}r. \tableofcontents} \maketitle %\addchap{\"Ons\"oz} % \tableofcontents %\listoffigures \chapter{\"Onermeler} \textbf{\"Onerme,} belli bir \emph{durumda} \emph{do\u gru} veya \emph{yanl{\i}\c s} denebilen \emph{c\"umledir.} Matematikte, \textbf{durum} \c co\u gunlukla bir \emph{yap{\i}d{\i}r.} \"Orne\u gin, `Her say{\i}n{\i}n tersi var' c\"umlesi, bir \"onermedir, ve bu \"onerme, \begin{compactenum}[1)] \item $(\N,+)$ yap{\i}s{\i}nda yanl{\i}\c s, \item $(\Z,+)$ yap{\i}s{\i}nda do\u gru, \item $(\N,{}\cdot{})$ yap{\i}s{\i}nda yanl{\i}\c s, \item $(\Qp,{}\cdot{})$ yap{\i}s{\i}nda do\u grudur. (Burada $\Qp=\{x\colon x\in\Q\land x>0\}$.) \end{compactenum} Do\u gru ve yanl\i\c s, \textbf{do\u gruluk de\u gerleridir.} \emph{Do\u gru} do\u gruluk de\u gerini $1$ olarak yazal\i m; \emph{yanl\i\c s} do\u gruluk de\u gerini de $0$ olarak.\footnote{$1$ ve $0$ yerine, $D$ ve $Y$, ya da $\top$ ve $\bot$, i\c saretleri kullan\i labilir.} Belli bir durumda, bir \"onerme do\u gru ise, o \"onermenin o durumdaki do\u gruluk de\u geri $1$'dir; yanl\i\c s ise, \"onermenin durumdaki do\u gruluk de\u geri $0$'d\i r. Her durum, bir \textbf{do\u gruluk g\"ondermesi} belirtir. Bu g\"onderme, her \"onermeyi o durumdaki do\u gruluk de\u gerine g\"onderir. Mesela, $d_1$ do\u gruluk g\"ondermesi, $(\N,+)$ yap\i s\i ndan taraf\i ndan belirtilsin. O zaman \begin{equation*} d_1(\text{`Her say\i n\i n tersi var'})=0. \end{equation*} Ancak, $d_2$ do\u gruluk g\"ondermesi, $(\Z,+)$ yap\i s\i ndan taraf\i ndan belirtilirse, o zaman \begin{equation*} d_2(\text{`Her say\i n\i n tersi var'})=1. \end{equation*} \chapter{Bile\c ske \"onermeler} Verilmi\c s \"onermelerden, \textbf{ba\u gla\c clarla, bile\c ske \"onermeler} yap{\i}labilir, ve onlar{\i}n de\u gerleri, verilmi\c s \"onermelerin de\u gerlerinden bulunabilir. Mesela, iki \"onermemiz olsun, ve onlara, $P$ ve $Q$ diyelim.\footnote{$Q$ harf{}i, \emph{k\"u} veya \emph{ky\"u} gibi telaffuz edilebilir.} O zaman `$P$ ve $Q$' \"onermesini olu\c sturabiliriz. Her durumda, bu yeni \"onerme do\u grudur ancak ve ancak $P$ do\u grudur ve $Q$ de do\u grudur. `$P$ ve $Q$' \"onermesini $P\land Q$ olarak yazal\i m, ve $d$, bir do\u gruluk g\"ondermesi olsun. O zaman \begin{center} $d(P\land Q)=1$ ancak ve ancak $d(P)=1$ ve $d(Q)=1$. \end{center} Genellikle $(d(P),d(Q))$ s\i ral\i\ ikilisi i\c cin, d\"ort tane se\c cenek vard\i r. Her se\c cenekteki $P\land Q$ \"onermesinin de\u geri, a\c sa\u g\i daki gibi bir \textbf{do\u gruluk tablosunda} g\"osterilir. \begin{equation*} \begin{array}{cc|c} P&Q&P\land Q\\\hline 0&0&0\\ 1&0&0\\ 0&1&0\\ 1&1&1 \end{array} \end{equation*} Bir\c cok \"onemli matematiksel \"onerme, `$P$ ise $Q$' bi\c cimindedir. Bu \"onermeyi, $P\lto Q$ olarak yazar\i z. Her $d$ do\u gruluk g\"ondermesi i\c cin, \begin{center} $d(P\lto Q)=1$ ancak ve ancak $d(P)=0$ veya $d(Q)=1$. \end{center} $P\lto Q$ \"onermesinin do\u gruluk tablosu a\c sa\u g\i daki gibidir: \begin{equation*} \begin{array}{cc|c} P&Q&P\lto Q\\\hline 0&0&1\\ 1&0&0\\ 0&1&1\\ 1&1&1 \end{array} \end{equation*} \"Orne\u gin, \"Oklid'in I.6 numaral\i\ \"onermesine bakal\i m: \begin{center} E\u ger bir \"u\c cgenin birbirine e\c sit iki a\c c\i s\i\ varsa,\\ e\c sit a\c c\i lar\i n g\"ord\"u\u g\"u kenarlar e\c sittir. \end{center} \c Simdi \begin{compactitem} \item $P$, `$B$ k\"o\c sesindeki a\c c\i, $C$ k\"o\c sesindeki a\c c\i ya e\c sittir' \"onermesi olsun, ve \item $Q$, `$AC$ kenar\i\, $AB$ kenar\i na e\c sittir' \"onermesi olsun. \end{compactitem} Bir $ABC$ \"u\c cgenini bir yap\i\ olarak d\"u\c s\"un\"ur\"uz, ve bu yap\i\ i\c cin, bir $d$ do\u gruluk g\"ondermesi vard\i r. O zaman \"Oklid'in I.6 numaral\i\ \"onermesine g\"ore, $d(P\lto Q)=1$, yani, \begin{center} ya $d(P)=0$, ya da $d(Q)=1$. \end{center} \begin{exercise} Yukar\i daki $P$ ve $Q$ i\c cin, \"oyle bir yap\i\ bulun ki, bu yap\i da $d(P\lto Q)=0$ olsun. \end{exercise} S\"ozc\"uklerde ve simgelerde\footnote{Baz\i\ kitaplarda $P\land Q$ yerine $P\mathrel{\&}Q$, $P\lto Q$ yerine $P\to Q$ veya $P\supset Q$, $P\liff Q$ yerine $P\leftrightarrow Q$, ve $\lnot P$ yerine $\mathord{\sim}P$ veya $P'$ kullan\i l\i r.} kullanaca\u g\i m\i z t\"um bile\c ske \"onermeler, bu \c sekildedir: \begin{align*} & \begin{gathered} \text{$P$ ve $Q$}\\ \text{$P$ veya $Q$}\\ \text{$P$ ise $Q$}\\ \text{$P$ ancak ve ancak $Q$}\\ \text{$P$ de\u gil} \end{gathered} && \begin{gathered} P\land Q\\ P\lor Q\\ P\lto Q\\ P\liff Q\\ \lnot P \end{gathered} \end{align*} Onlar\i n t\"um olas\i\ do\u gruluk de\u gerleri, \ref{fig:ilk-tt} numaral\i\ \c Sekildeki do\u gruluk tablolar\i nda g\"osterilmi\c stir. \begin{figure}[ht] \centering \mbox{}\hfill$\begin{array}{cc|cccc} P&Q&P\land Q&P\lor Q&P\lto Q&P\liff Q\\\hline 0&0&0&0&1&1\\ 1&0&0&1&0&0\\ 0&1&0&1&1&0\\ 1&1&1&1&1&1 \end{array}$ \hfill $\begin{array}{c|c} P&\lnot P\\\hline 0&1\\ 1&0 \end{array}$\hfill\mbox{} \caption{Basit form\"ullerin do\u gruluk tablolar\i}\label{fig:ilk-tt} \end{figure} $\land$, $\lor$, $\lto$, $\liff$, ve $\lnot$ i\c saretlerine \textbf{ba\u glay\i c\i} deriz.\footnote{Hat\i rlamak i\c cin: Latince \emph{VEL} s\"ozc\"u\u gu, `veya' demektir, onun i\c cin `veya', $\lor$ olarak yaz\i l\i r. \.Ingilizce \emph{AND} s\"ozc\"u\u gu, `ve' demektir, ve $\land$ i\c sareti, \emph A gibidir.} \"Oklid'in I.13 numaral\i\ \"onermesi, $P\lor Q$ bi\c cimindedir. O \"onerme a\c sa\u g\i daki gibidir: \begin{center} E\u ger bir do\u gru, konulursa bir do\u grunun \"uzerine,\\ yapt\i\u g\i\ a\c c\i lar, ya iki dik\\ ya da iki dik a\c c\i ya e\c sit olacak.\\ \end{center} $ABC$, bir do\u gru olsun, ve $BD$, ba\c ska bir do\u gru. Bu durum i\c cin, bir $d$ do\u gruluk g\"ondermesi var. O zaman \begin{compactitem} \item $P$, `$ABD$ ve $CBD$ a\c c\i lar\i, diktir' \"onermesi olsun, ve \item $Q$, `$ABD$ ve $CBD$ a\c c\i lar\i, iki dik a\c c\i ya e\c sittir' \"onermesi olsun. \end{compactitem} I.13 numaral\i\ \"onermeye g\"ore, \begin{center} ya $d(P)=1$, ya da $d(Q)=1$. \end{center} Bir \"onermede, birden fazla ba\u glay\i c\i\ bulunabilir. Asl\i nda, \"Oklid'in I.13 numaral\i\ \"onermesi b\"oyle d\"u\c s\"un\"ulebilir. \c Simdi $ABC$ ve $ABD$, biti\c sik a\c c\i lar olsun, ve $d$, bu durum i\c cin do\u gruluk g\"ondermesi olsun. \begin{compactitem} \item $P$ ve $Q$, yukar\i daki gibi olsun, \item $F$, $P\lor Q$ \"onermesi olsun, ve \item $R$, `$AB$ ve $BC$ do\u grular\i, bir do\u grudad\i r' \"onermesi olsun. \end{compactitem} O zaman I.13 numaral\i\ \"onermeye g\"ore, $d(R\lto F)=1$. \"Ustelik, I.14 numaral\i\ \"onermeye g\"ore, $d(Q\lto R)=1$; ve $d(P\lto R)=1$, dik a\c c\i n\i n tan\i m\i ndan ve d\"ord\"unc\"u postulattan. Bu \c sekilde $d(F\lto R)=1$. Sonunda, t\"um bunlara g\"ore, $d(R\liff F)=1$. Ba\c ska bir \"ornek i\c cin, \"Oklid'in I.4 numaral\i\ \"onermesine bakal\i m: \begin{center} E\u ger iki \"u\c cgenin iki kenar\i\ iki kenara e\c sit olursa, her biri birine,\\ ve a\c c\i\ a\c c\i ya e\c sit olursa, yani e\c sit do\u grular taraf\i ndan i\c cerilen,\\ hem taban tabana e\c sit olacak,\\ hem \"u\c cgen \"u\c cgene e\c sit olacak,\\ hem de geriye kalan a\c c\i lar geriye kalan a\c c\i lara e\c sit olacak, her biri birine,\\ yani e\c sit kenarlar\i\ g\"orenler. \end{center} Bu \"onerme, $F\lto G$ bi\c cimdedir, ama $F$ ve $G$ \"onermelerin kendisi, bile\c skedir. Asl\i nda, \begin{compactitem} \item $P_1$, `$AB$ kenar\i, $DE$ kenar\i na e\c sittir' \"onermesi olsun, \item $P_2$, `$AC$ kenar\i, $DF$ kenar\i na e\c sittir' \"onermesi olsun, \item $P_3$, `$BAC$ a\c c\i s\i, $EDF$ a\c c\i s\i na e\c sittir' \"onermesi olsun, \item $F$, $P_1\land P_2\land P_3$ \"onermesi olsun, \item $P_4$, `$BC$ kenar\i, $EF$ kenar\i na e\c sittir' \"onermesi olsun, \item $P_5$, `$ABC$ \"u\c cgeni, $DEF$ \"u\c cgenine e\c sittir' \"onermesi olsun, \item $P_6$, `$ABC$ a\c c\i s\i, $DEF$ a\c c\i s\i na e\c sittir' \"onermesi olsun, \item $P_7$, `$ACB$ a\c c\i s\i, $DFE$ a\c c\i s\i na e\c sittir' \"onermesi olsun, ve \item $G$, $P_4\land P_5\land P_6\land P_7$ \"onermesi olsun. \end{compactitem} $ABC$ ve $DEF$ \"u\c genleri i\c cin, bir $d$ do\u gruluk g\"ondermesi vard\i r, ve I.4 numaral\i\ \"onermeye g\"ore, $d(F\lto G)=1$ olur, yani $d(F)=0$ veya $d(G)=1$. \"Ustelik, $d(F)=1$ ancak ve ancak \begin{equation*} d(P_1)=d(P_2)=d(P_3)=1; \end{equation*} ve $d(G)=1$ ancak ve ancak \begin{equation*} d(P_4)=d(P_5)=d(P_6)=d(P_7)=1. \end{equation*} Bile\c ske bir \"onermenin ba\u glay\i c\i lar\i ndan sadece biri, \"onermenin \textbf{ana ba\u glay\i c\i s\i d\i r.} Tekrar I.13 ve I.14 numaral\i\ \"onermeler \"orne\u gine bakal\i m. Orada, $R\lto F$ \"onermesinin ana ba\u glay\i c\i s\i, $\lto$ ba\u glay\i c\i s\i d\i r. O \"onermede $\lor$ ba\u glay\i c\i s\i\ bulunur, ama bu, \"onermenin ana ba\u glay\i c\i s\i\ de\u gil, $F$ \"onermesinin ana ba\u glay\i c\i s\i d\i r. $R\lto F$ \"onermesi, \c simdi $R\lto P\lor Q$ olarak yaz\i lamaz, \c c\"unk\"u bu ifade, \"onermenin ana ba\u glay\i c\i s\i n\i\ g\"ostermez. $R\lto(P\lor Q)$ gibi bir ifade yaz\i labilir veya bir \emph{a\u ga\c c} \c cizilebilir: \begin{equation*} \xymatrix{ &\lto\ar@{-}[dl]\ar@{-}[drr]&&&\\ R&&&\lor\ar@{-}[dl]\ar@{-}[dr]&\\ &&P&&Q } \end{equation*} $P_1\land P_2\land P_3$ \"onermesinin ana ba\u glay\i c\i s\i, $\land$ ba\u glay\i c\i s\i d\i r, ama hangi $\land$? Bu \"onermede, $\land$ ba\u glay\i c\i s\i n\i n iki \textbf{ge\c ci\c si} var.\footnote{\emph{Ge\c ci\c s} terimini \cite{MTS} kitab\i ndan ald\i m; \.Ingilizcesi, \emph{occurrence.}} Hangisinin ana ba\u glay\i c\i\ oldu\u gu fark etmez. (Neden?) Kesinlik i\c cin, son ge\c ci\c s olsun diyelim. O zaman $P_1\land P_2\land P_3$ demek, $P_1\land(P_2\land P_3)$ demektir. Ayn\i\ \c sekilde, $P_4\land P_5\land P_6\land P_7$ demek $P_4\land (P_5\land (P_6\land P_7))$. Ancak $P\lto Q\lto R$ \"onermesindeki $\lto$ ba\u glay\i c\i s\i n\i n hangi ge\c ci\c sinin \"onermenin ana ba\u glay\i c\i s\i\ oldu\u gu \"onemlidir. (Neden?) Tekrar son ge\c ci\c s olsun diyelim: $P\lto Q\lto R$ demek $P\lto(Q\lto R)$ demek olsun. \chapter{\"Onerme form\"ulleri} Bundan sonra, daha bi\c cimsel olaca\u g\i z. $P$, $Q$, ve $R$ gibi Latin harf{}leri, ve $P_1$ ve $P_2$ gibi bile\c ske simgeler, \"onerme de\u gil, \textbf{\"onerme de\u gi\c skenleridir.} Onlardan \textbf{\"onerme form\"ulleri} olu\c stururuz, bu tan\i ma g\"ore: \begin{enumerate} \item Her \"onerme de\u gi\c skeni, bir \"onerme form\"ul\"ud\"ur. \item $F$ ve $G$, \"onerme form\"ulleriyse, $(F\land G)$, $(F\lor G)$, $(F\lto G)$, ve $(F\liff G)$ ifadeleri de \"onerme form\"ulleridir. \item $F$, \"onerme form\"ul\"uyse, $\lnot F$ ifadesi de bir \"onerme form\"ul\"ud\"ur. \item $1$ ve $0$ simgeleri, \"onerme form\"ulleridir. \end{enumerate} \"Orne\u gin, $P$, $(P\land Q)$, $(R\land 1)$, $((P\land Q)\lto(R\land1))$, ve $\lnot((P\land Q)\lto(R\land1))$, \"onerme form\"ulleridir. \begin{theorem} $F$, $G$, $H$, ve $K$, \"onerme form\"ulleri olsun, ve $*$ ile $\dag$, simgeler olsun. E\u ger \begin{align*} &(F*G)&&\text{ile}&&(H\mathbin{\dag}K) \end{align*} ayn\i\ form\"uld\"ur, o zaman $F$ ve $H$, birbiriyle ayn\i d\i r, ve $*$ olarak yaz\i lan simge, $\land$, $\lor$, $\lto$, ve $\liff$ simgelerinden biridir. \end{theorem} Bu teoremi ispatlam\i yoruz. Bundan sonra, $F$, $G$, $H$, ve $K$ gibi Latin harf{}leri her zaman \"onerme form\"ullerini g\"osterecek. Bu durumda, $(F*G)$ bir \"onerme form\"ul\"uyse, o zaman $*$ olarak yaz\i lan simge, $(F*G)$ form\"ul\"un\"un \textbf{ana ba\u glay\i c\i s\i d\i r.} $\lnot F$ form\"ul\"un\"un \textbf{ana ba\u glay\i c\i s\i,} $\lnot$ simgesidir. Ayr\i ca, $0$ veya $1$, kendisinin \textbf{ana ba\u glay\i c\i s\i} olarak kabul edilir. Ancak bir de\u gi\c skenin ana ba\u glay\i c\i s\i\ yoktur. Her de\u gi\c sken olmayan form\"ul\"un sadece bir tane ana ba\u glay\i c\i s\i\ vard\i r. Ayr\i ca, bir form\"ulde, her de\u gi\c sken veya ayra\c c olmayan simge, bir ve sadece bir \textbf{alt form\"ul\"un} ana ba\u glay\i c\i s\i d\i r. Bir form\"ul\"un \"onerme de\u gi\c skenleri de altform\"uller olur. \"Orne\u gin, $\lnot((P\land Q)\lto R)$ form\"ul\"un\"un alt form\"ulleri, %\ref{fig:alt-f} numaral\i\ \c Sekildeki a\c sa\u g\i daki tabloda s\i ralanm\i\c st\i r. %\begin{figure}[ht] \begin{equation*} \begin{array}{cc} \text{altform\"ul}&\text{ana ba\u glay\i c\i s\i}\\\hline \lnot((P\land Q)\lto(R\land1))&\lnot\\ P&\\ (P\land Q)&\land\\ Q&\\ ((P\land Q)\lto(R\land1))&\lto\\ R&\\ (R\land1)&\land\\ 1&1 \end{array} \end{equation*} %\caption{$\lnot((P\land Q)\lto(R\land1))$ form\"ul\"un alt form\"ulleri}\label{fig:alt-f} %\end{figure} Bundan sonra, \textbf{do\u gruluk g\"ondermesi,} t\"um \"onerme form\"ulleri k\"umesinden $\{0,1\}$ k\"umesine \ref{fig:ilk-tt} numaral\i\ \c Sekildeki gibi a\c sa\u g\i daki kurallara g\"ore tan\i mlanm\i\c s bir fonksiyon anlam\i na gelecektir. \begin{equation*} \begin{array}{cccccc} d(F)&d(G)&d((F\land G))&d((F\lor G))&d((F\lto G))&d((F\liff G))\\\hline 0&0&0&0&1&1\\ 1&0&0&1&0&0\\ 0&1&0&1&1&0\\ 1&1&1&1&1&1 \end{array}, \end{equation*} \begin{align*} & \begin{array}{cc} d(F)&d(\lnot F)\\\hline 0&1\\ 1&0 \end{array}, &d(1)&=1, &d(0)&=0. \end{align*} Genellikle, $F$ bir \"onerme form\"ul\"uyse, ve $d$ bir do\u gruluk g\"ondermesiyse, $d(F)$ de\u gerini hesaplamak i\c cin, $F$ form\"ul\"un\"un her $G$ alt form\"ul\"u i\c cin $d(G)$ de\u gerini hesaplamal\i y\i z. Bu $d(G)$ de\u geri, $F$ form\"ul\"un\"un do\u gruluk tablosunda, \begin{compactenum}[1)] \item e\u ger $G$ bir de\u gi\c skense, $G$ alt\i nda, \item e\u ger $G$ de\u gi\c sken de\u gilse, $G$ form\"ul\"un\"un ana ba\u glay\i c\i s\i\ alt\i nda, \end{compactenum} g\"osterilebilir. Mesela $\lnot((P\land Q)\lto(R\land1))$ form\"ul\"un\"un do\u gruluk tablosunu \ref{fig:tt} numaral\i\ \c Sekil% %a\c sa\u g\i% deki gibi olu\c stururuz. \begin{figure}[p] \centering $\begin{array}{cccccccccccccc} \lnot&(&(&P&\land&Q&)&\lto&(&R&\land&1&)&)\\\hline & & &0& &0& & & &0& &1& &\\ & & &1& &0& & & &0& &1& &\\ & & &0& &1& & & &0& &1& &\\ & & &1& &1& & & &0& &1& &\\ & & &0& &0& & & &1& &1& &\\ & & &1& &0& & & &1& &1& &\\ & & &0& &1& & & &1& &1& &\\ & & &1& &1& & & &1& &1& &\\\hline & & &0& 0&0& & & &0& 0&1& &\\ & & &1& 0&0& & & &0& 0&1& &\\ & & &0& 0&1& & & &0& 0&1& &\\ & & &1& 1&1& & & &0& 0&1& &\\ & & &0& 0&0& & & &1& 1&1& &\\ & & &1& 0&0& & & &1& 1&1& &\\ & & &0& 0&1& & & &1& 1&1& &\\ & & &1& 1&1& & & &1& 1&1& &\\\hline & & &0& 0&0& & 1& &0& 0&1& &\\ & & &1& 0&0& & 1& &0& 0&1& &\\ & & &0& 0&1& & 1& &0& 0&1& &\\ & & &1& 1&1& & 0& &0& 0&1& &\\ & & &0& 0&0& & 1& &1& 1&1& &\\ & & &1& 0&0& & 1& &1& 1&1& &\\ & & &0& 0&1& & 1& &1& 1&1& &\\ & & &1& 1&1& & 1& &1& 1&1& &\\\hline 0& & &0& 0&0& & 1& &0& 0&1& &\\ 0& & &1& 0&0& & 1& &0& 0&1& &\\ 0& & &0& 0&1& & 1& &0& 0&1& &\\ 1& & &1& 1&1& & 0& &0& 0&1& &\\ 0& & &0& 0&0& & 1& &1& 1&1& &\\ 0& & &1& 0&0& & 1& &1& 1&1& &\\ 0& & &0& 0&1& & 1& &1& 1&1& &\\ 0& & &1& 1&1& & 1& &1& 1&1& &\\ \end{array}$ \caption{Do\u gruluk tablosu hesaplanmas\i}\label{fig:tt} \end{figure} Sonu\c c olarak, form\"ul\"un do\u gruluk tablosu a\c sa\u g\i daki gibidir. \begin{equation*} \begin{array}{ccc|c} P&Q&R&\lnot((P\land Q)\lto(R\land1)\\\hline 0&0&0&0\\ 1&0&0&0\\ 0&1&0&0\\ 1&1&0&1\\ 0&0&1&0\\ 1&0&1&0\\ 0&1&1&0\\ 1&1&1&0\\ \end{array}. \end{equation*} \"Onerme form\"ullerinde, baz\i\ ayra\c clar gerekmez ve kullan\i lmayabilir. O zaman do\u gruluk de\u gerleri \c su s{\i}rada hesaplan{\i}r: \begin{compactenum}[1)] \item $0$ ve $1$; \item $\lnot$; \item $\land$ ve $\lor$; \item $\lto$ ve $\liff$; \item bir ba\u glay\i c\i n\i n iki ge\c ci\c si varsa, sa\u gdaki. \end{compactenum} \"Orne\u gin: \begin{compactenum}[a)] \item $F*G$ demek $(F*G)$; \item $\lnot F*G$ ve $\lnot(F*G)$ farkl\i d\i r; \item $F\lto G\lor H$ demek $F\lto(G\lor H)$; \item $F\land G\lor H$ belirsiz (onun i\c cin yaz\i lmaz); \item $F\land G\land H$ demek $F\land(G\land H)$; \item $F\lto G\lto H$ demek $F\lto(G\lto H)$; \item $F\lto G\land H\lto K$ demek $F\lto ((G\land H)\lto K)$. \end{compactenum} $\land$, $\lor$, $\lto$, $\liff$ ba\u glay\i c\i lar\i na \textbf{iki konumlu} denir; $\lnot$ ba\u glay\i c\i s\i na, \textbf{bir konumlu} denir; $0$ ve $1$, \textbf{s{\i}f{\i}r konumlu ba\u glay\i c\i lar} olarak d\"u\c s\"un\"ul\"ur. \begin{exercise} A\c sa\u g{\i}daki de\u gi\c skensiz form\"ulleri hesaplay{\i}n. \begin{compactenum}[a)] \item $1\lto 1\lto 1$; \item $1\lto 0\lto 1$; \item $(0\lto 1)\liff 1$; \item $(0\liff 1)\liff(0\liff 1)$; \item $\lnot\lnot\lnot 0$; \item $(1\lor 0)\land 0$; \item $1\lor (0\land 0)$. \end{compactenum} \end{exercise} \begin{exercise} A\c sa\u g{\i}daki form\"ullerin do\u gruluk tablolar\i n\i\ yap{\i}n: \begin{compactenum}[a)] \renewcommand{\labelenumii}{(\theenumii)} \item $P\lto Q\lto P$; \item $P\land Q\land R$; \item $\lnot(P\liff\lnot(Q\liff R))$; \item $(P\lto Q\lor R)\lto\lnot P\lor Q$; \item $(P\lto Q\lor\lnot R)\land(Q\lto P\land R)\lto P\lto R$; \item $\lnot(\lnot R\lto P\lto\lnot(R\lto Q))$. \end{compactenum} \end{exercise} \chapter{Denklik} \.Iki \"onermenin do\u gruluk de\u geri her durumda ayn\i ysa, o \"onermeler, mant\i ksal olarak birbirine \textbf{e\c sde\u ger} veya \textbf{denktir.} \.Iki \"onerme \emph{form\"ul\"un\"un} do\u gruluk tablolar\i\ ayn\i ysa, o form\"uller de birbirine \textbf{e\c sde\u ger} veya \textbf{denktir.} Yukar\i daki \"Oklid'in I.13 ve I.14 numaral\i\ \"onermeleri \"orne\u ginde zaten iki denklik kulland\i k. Mesela, $P\lor Q\lto R$ \"onermesi, $(P\lto R)\land(Q\lto R)$ \"onermesine denktir ($P\lor Q\lto R$ ifadesinin $(P\lor Q)\lto R$ demek oldu\u gunu hat\i rlay\i n). Bu \"onermelerin do\u gruluk tablolar\i n\i\ hesaplayal\i m: \begin{align*} &\begin{array}{ccccc} P&\lor&Q&\lto&R\\\hline 0& 0&0& 1&0\\ 1& 1&0& 0&0\\ 0& 1&1& 0&0\\ 1& 1&1& 0&0\\ 0& 0&0& 1&1\\ 1& 1&0& 1&1\\ 0& 1&1& 1&1\\ 1& 1&1& 1&1 \end{array} && \begin{array}{ccccccccccc} (&P&\lto&R&)&\land&(&Q&\lto&R&)\\\hline &0& 1&0& & 1& &0& 1&0&\\ &1& 0&0& & 0& &0& 1&0&\\ &0& 1&0& & 0& &1& 0&0&\\ &1& 0&0& & 0& &1& 0&0&\\ &0& 1&1& & 1& &0& 1&1&\\ &1& 1&1& & 1& &0& 1&1&\\ &0& 1&1& & 1& &1& 1&1&\\ &1& 1&1& & 1& &1& 1&1& \end{array} \end{align*} B\"oylece \ref{fig:tt-5} numaral\i\ \c Sekildeki %a\c sa\u g\i daki tablolar\i\ elde ederiz. \begin{figure}[ht] \mbox{}\hfill %\begin{align}\label{eqn:tt-5} $\begin{array}{ccc|c} P&Q&R&P\lor Q\lto R\\\hline 0&0&0&1\\ 1&0&0&0\\ 0&1&0&0\\ 1&1&0&0\\ 0&0&1&1\\ 1&0&1&1\\ 0&1&1&1\\ 1&1&1&1 \end{array}$ \hfill $\begin{array}{ccc|c} P&Q&R&(P\lto R)\land(Q\lto R)\\\hline 0&0&0&1\\ 1&0&0&0\\ 0&1&0&0\\ 1&1&0&0\\ 0&0&1&1\\ 1&0&1&1\\ 0&1&1&1\\ 1&1&1&1 \end{array}$ %\end{align} \hfill\mbox{} \caption%[$P\lor Q\lto R$ ve $(P\lto R)\land(Q\lto R)$ form\"ullerin tablolar\i] {%$P\lor Q\lto R$ ve $(P\lto R)\land(Q\lto R)$ \.Iki form\"ul\"un do\u gruluk tablolar\i}\label{fig:tt-5} \end{figure} Bu tablolar, birbiriyle ayn\i d\i r; onun i\c cin \begin{equation*} P\lor Q\lto R\denktir(P\lto R)\land(Q\lto R) \end{equation*} deriz. $F$ ve $G$ \"onerme form\"ulleri e\c sde\u ger ise, \begin{equation*} F\sim G \end{equation*} ifadesini yazabiliriz. \"Orne\u gin, \begin{equation*} P\lor Q\lto R\sim(P\lto R)\land(Q\lto R). \end{equation*} Ancak, dikkatli olunmal\i: $F\sim G$ ifadesi, \"onerme form\"ul\"u de\u gil; sadece `$F$ ve $G$ form\"ulleri, birbirine denktir', yani \begin{equation*} F\denktir G \end{equation*} c\"umlesi i\c cin bir k\i saltmad\i r. \begin{theorem}\label{thm:denk} A\c sa\u g\i daki e\c sde\u gerliklerimiz vard\i r. \begin{compactenum} \item (Her \"onerme, sadece $\lnot$ ve $\land$ ile yaz\i labilir:) \begin{gather*} P\lor Q\denktir\lnot(\lnot P\land\lnot Q),\\ P\lto Q\denktir \lnot P\lor Q,\\ P\liff Q\denktir(P\lto Q)\land (Q\lto P). \end{gather*} \item (Her \"onerme, sadece $\lnot$ ve $\lto$ ile yaz\i labilir:) \begin{equation*} P\land Q\denktir\lnot(P\lto\lnot Q). \end{equation*} \item (\c Cifte de\u gilleme kald\i r\i labilir:) \begin{equation*} \lnot\lnot P\denktir P. \end{equation*} \item (De Morgan\footnote{Augustus De Morgan, 1806--71, B\"uy\"uk Britanyal\i\ matematik\c ci ve mant\i k\c c\i\ \cite{Struik,Struik-TR}.} kurallar\i:) \begin{align*} \lnot (P\lor Q)& \denktir \lnot P\land \lnot Q,\\ \lnot (P\land Q)& \denktir \lnot P\lor \lnot Q. \end{align*} \item ($\land$ ve $\lor$ ba\u glay\i c\i lar\i n\i n de\u gi\c sme ve birle\c sme \"ozellikleri:) \begin{align*} P&\land Q \denktir Q\land P,& (P&\land Q)\land R \denktir P\land (Q \land R),\\ P&\lor Q \denktir Q\lor P,& (P& \lor Q)\lor R \denktir P\lor (Q\lor R). \end{align*} \item ($\land$ ve $\lor$ ba\u glay\i c\i lar\i\ birbiri \"uzerine da\u g\i l\i r:) \begin{align*} P&\land(Q\lor R)\denktir (P\land Q)\lor(P\land R),\\ P&\lor(Q\land R)\denktir (P\lor Q)\land(P\lor R). \end{align*} \item (Fazlal\i klar:) \begin{align*} & \begin{gathered} P\land P \denktir P,\\ P\land\lnot P \denktir 0,\\ P\land 1 \denktir P,\\ P\land 0 \denktir 0, \end{gathered}&& \begin{gathered} P\lor P \denktir P, \\ P\lor \lnot P \denktir 1,\\ P\lor 0 \denktir P,\\ P\lor 1 \denktir 1. \end{gathered} \end{align*} \item (Yeni de\u gi\c sken:) \begin{align*} P&\denktir (P\land Q)\lor (P\land \lnot Q),\\ P&\denktir (P\lor Q)\land (P\lor \lnot Q). \end{align*} \item (Yutma:) \begin{align*} P\land(P\lor Q)& \denktir P,\\ P\lor(P\land Q)& \denktir P. \end{align*} \end{compactenum} \end{theorem} \begin{proof} \cexercise. %Do\u gruluk tablolar\i yla kolayca g\"osterilebilir. %Okuyucuya b\i rak\i lm\i\c st\i r. \end{proof} Bu teoremden, a\c sa\u g\i daki teoremi kullanarak, sonsuz tane denklik elde edebiliriz. \"Orne\u gin, $P\lto Q$ form\"ul\"u $\lnot P\lor Q$ form\"un\"une denk oldu\u gundan \begin{equation*} P\land Q\lto R\denktir\lnot(P\land Q)\lor R \end{equation*} ifadesini elde ederiz. \begin{theorem}\label{th:sub} $F$ ve $G$, birbirine denk form\"uller olsun; $H$, bir \"onerme de\u gi\c skeni olsun; ve $H'$, bir \"onerme form\"ul\"u olsun. E\u ger $F$ form\"ul\"unde $H$ de\u gi\c skeninin ge\c cti\u gi her yere $H'$ konulursa, $F'$ form\"ul\"u elde edilsin; benzer \c sekilde, $G$ form\"ul\"unden $G'$ elde edilsin. O zaman \begin{equation*} F'\denktir G'. \end{equation*} \end{theorem} Bu teoremi, ispatlam\i yoruz. \"Ustelik, $\lnot(P\land Q)$ form\"ul\"u $\lnot P\lor\lnot Q$ form\"ul\"une denk oldu\u gundan, sonraki teorem sayesinde, \begin{equation*} \lnot(P\land Q)\lor R\denktir(\lnot P\lor\lnot Q)\lor R \end{equation*} ifadesini elde ederiz. \begin{theorem}\label{th:rep} $F$ form\"ul\"u, bir $G$ form\"ul\"un\"un bir alt form\"ul\"u olsun, ve $F$, bir $F^*$ form\"ul\"une denk olsun. E\u ger, $G$ form\"ul\"unde, $F$ alt form\"ul\"un\"un yerine $F^*$ konulursa, $G^*$ form\"ul\"u elde edilsin. O zaman \begin{equation*} G\denktir G^*. \end{equation*} \end{theorem} Bu teoremi de ispatlam\i yoruz. Ancak, \c simdi a\c sa\u g\i daki teorem ispatlanabilir: \begin{theorem} \begin{math} (P\lor Q)\land(R\lor S)\denktir(P\land R)\lor(Q\land R)\lor(P\land S)\lor(Q\land S). \end{math} \end{theorem} \begin{proof} A\c sa\u g\i daki denkliklerimiz vard\i r. \begin{align*} &\phantom{{}\sim{}}(P\lor Q)\land(R\lor S)&&\\ &\sim((P\lor Q)\land R)\lor((P\lor Q)\land S)&&\text{[da\u g\i lma]}\\ &\sim(R\land(P\lor Q))\lor(S\land(P\lor Q))&&\text{[de\u gi\c sme]}\\ &\sim((R\land P)\lor(R\land Q))\lor((S\land P)\lor(S\land Q))&&\text{[da\u g\i lma]}\\ &\sim(R\land P)\lor(R\land Q)\lor(S\land P)\lor(S\land Q)&&\text{[birle\c sme]}\\ &\sim(P\land R)\lor(Q\land R)\lor(P\land S)\lor(Q\land S)&&\text{[de\u gi\c sme]} \end{align*} Bu ispat\i n her ad\i m\i nda, \ref{th:sub} numaral\i\ ve \ref{th:rep} numaral\i\ Teoremleri kulland\i k. \end{proof} Benzer \c sekilde: \begin{theorem} % A\c sa\u g\i daki denkliklerimiz var: \begin{align*} \lnot P\lor(P\land Q)&\denktir\lnot P\lor Q,& \lnot P\land(P\lor Q)&\denktir\lnot P\land Q,\\ P\lor(\lnot P\land Q)&\denktir P\lor Q,& P\land(\lnot P\lor Q)&\denktir P\land Q. \end{align*} \end{theorem} \begin{proof} A\c sa\u g\i daki denkliklerimiz vard\i r. \begin{align*} &\phantom{{}\sim{}}\lnot P\lor(P\land Q)&&\\ &\sim(\lnot P\lor P)\land(\lnot P\lor Q)&&\text{[da\u g\i lma]}\\ &\sim 1\land(\lnot P\lor Q)&&\text{[fazlal\i k]}\\ &\sim\lnot P\lor Q&&\text{[fazlal\i k]} \end{align*} Di\u ger denklikler, \cexercise.% benzer \c sekilde ispatlan\i r. \end{proof} \chapter{Gerektirme} E\u ger, her $d$ do\u gruluk g\"ondermesi i\c cin, $d(F)=d(G)$ ise, o zaman $F$ ve $G$, birbirine denktir. Yani, $F\denktir G$, e\u ger, her $d$ i\c cin, \begin{compactenum}[1)] \item $d(F)=1$ ise $d(G)=1$, \item $d(G)=1$ ise $d(F)=1$. \end{compactenum} \c Simdi, her $d$ i\c cin, sadece $d(F)=1$ ise $d(G)=1$ oldu\u gunu varsayal\i m. O zaman $F$ form\"ul\"u, $G$ form\"ul\"un\"u \textbf{gerektirir} deriz. Mesela, \begin{equation*} P\lor Q\lto R\gerektirir P\lto R, \end{equation*} %\ref{fig:gerek} numaral\i\ \c Sekildeki a\c sa\u g\i daki do\u gruluk tablosundan: %\begin{figure} %\centering \begin{equation*} \begin{array}{ccc|c|c} P&Q&R&P\lor Q\lto R&P\lto R\\\hline 0&0&0&1&1\\ 1&0&0&0&0\\ 0&1&0&0&1\\ 1&1&0&0&0\\ 0&0&1&1&1\\ 1&0&1&1&1\\ 0&1&1&1&1\\ 1&1&1&1&1 \end{array} \end{equation*} % \caption{$P\lor Q\lto R\gerektirir P\lto R$}\label{fig:gerek} %\end{figure} Buradaki her sat\i rda, ya $P\lor Q\lto R$ form\"ul\"un\"un de\u geri $0$, ya da $P\lto R$ form\"ul\"un\"un de\u geri $1$. Tabii ki ikisi de olabilir. \begin{theorem} \mbox{} %A\c sa\u g\i daki gerektirmelerimiz vard\i r: \begin{description} \item[Basitle\c stirme:] \begin{align*} P\land Q&\gerektirir P,& P\land Q&\gerektirir Q. \end{align*} \item[Ekleme:] \begin{align*} P&\gerektirir P\lor Q,& Q&\gerektirir P\lor Q. \end{align*} \end{description} \end{theorem} \begin{proof} \cexercise. %Do\u gruluk tablolar\i yla kolayca g\"osterilebilir. Okuyucuya b\i rak\i lm\i\c st\i r. \end{proof} \.Iki form\"ul de bir form\"ul\"u gerektirebilir. $F$ ve $G$ form\"ulleri, $H$ form\"ul\"un\"u gerektirir, ancak ve ancak, her $d$ do\u gruluk g\"ondermesi i\c cin, ya $d(F)=0$, ya $d(G)=0$, ya da $d(H)=1$. Mesela, \begin{equation*} P\lto Q\ile Q\lto R\gerektirir P\lto R, \end{equation*} a\c sa\u g\i daki tablodan: \begin{equation*} \begin{array}{ccc|cc|c} P&Q&R&P\lto Q&Q\lto R&P\lto R\\\hline 0&0&0& 1&1&1\\ 1&0&0& 0&1&0\\ 0&1&0& 1&0&1\\ 1&1&0& 1&0&0\\ 0&0&1& 1&1&1\\ 1&0&1& 0&1&1\\ 0&1&1& 1&1&1\\ 1&1&1& 1&1&1 \end{array} \end{equation*} Asl\i nda, sadece 1., 5., 7., ve 8.\ sat\i rda, hem $P\lto Q$ ve $Q\lto R$ do\u gru, ve o sat\i rda, $P\lto R$ de do\u grudur. Ancak, $P\lto R$ ve $P\lto Q$, $Q\lto R$ form\"ul\"un\"u gerektirmez. \begin{theorem}\label{th:bag-etc} A\c sa\u g\i daki gerektirmelerimiz vard\i r. \begin{description} \item[Ba\u glama:] \begin{equation*} P\ile Q\gerektirir P\land Q. \end{equation*} \item[Ay\i rma:] \begin{align*} P\ile P\lto Q&\gerektirir Q,& P\lor Q\ile \lnot P&\gerektirir Q,\\ \lnot Q\ile P\lto Q&\gerektirir\lnot P,& P\lor Q\ile\lnot Q&\gerektirir P. \end{align*} \item[Hipotetik tas\i m:] \begin{equation*} P\lto Q\ile Q\lto R\gerektirir P\lto R. \end{equation*} \end{description} \end{theorem} \begin{proof} \cexercise. (Hipotetik tas\i m gerektirmesini zaten ispatlad\i k.) %\"Otekiler de, do\u gruluk tablolar\i yla kolayca g\"osterilebilir. \end{proof} \.Ikiden fazla form\"ul, bir form\"ul gerektirebilir. $\Gamma$ (\emph{Gamma}), bir \"onerme form\"ul\"u \emph{k\"umesi} olsun, ve $F$, bir \"onerme form\"ul\"u olsun. E\u ger her $d$ do\u gruluk g\"ondermesi i\c cin, \begin{compactenum}[1)] \item ya $\Gamma$ k\"umesindeki bir $G$ i\c cin, $d(G)=0$, \item ya da $d(F)=1$ \end{compactenum} sa\u glan\i yorsa, o zaman $\Gamma$, $F$ form\"ul\"un\"u \textbf{gerektirir.} Yani, $\Gamma$, $F$ form\"ul\"un\"u gerektirir, ancak ve ancak, $\Gamma\cup\{F\}$ k\"umesindeki b\"ut\"un form\"ullerin do\u gruluk tablosunun her sat\i r\i nda, \begin{compactenum}[1)] \item ya $\Gamma$ k\"umesindeki bir form\"ul yanl\i\c st\i r, \item ya da $F$ form\"ul\"u do\u grudur. \end{compactenum} \begin{theorem}\label{thm:olumlu} \mbox{} % A\c sa\u g\i daki gerektirmemiz var: \begin{description} \item[Olumlu dilemma:] \begin{equation*} P\lto Q\virgul R\lto S\ve P\lor R\gerektirir Q\lor S. \end{equation*} \end{description} \end{theorem} \begin{proof} Gerektirme, \ref{fig:tt4} numaral\i\ \c Sekildeki do\u gruluk tablosundan g\"or\"unebilir. \begin{figure}[ht] %\begin{equation*} \centering $\begin{array}{cccc|ccc|c} P&Q&R&S&P\lto Q&R\lto S&P\lor R&Q\lor S\\\hline 0&0&0&0&1&1&0&0\\ 1&0&0&0&0&1&1&0\\ 0&1&0&0&1&1&0&1\\ 1&1&0&0&1&1&1&1\\ 0&0&1&0&1&0&1&0\\ 1&0&1&0&0&0&1&0\\ 0&1&1&0&1&0&1&1\\ 1&1&1&0&1&0&1&1\\ 0&0&0&1&1&1&0&1\\ 1&0&0&1&0&1&1&1\\ 0&1&0&1&1&1&0&1\\ 1&1&0&1&1&1&1&1\\ 0&0&1&1&1&1&1&1\\ 1&0&1&1&0&1&1&1\\ 0&1&1&1&1&1&1&1\\ 1&1&1&1&1&1&1&1 \end{array}$ %\end{equation*} \caption{Teorem \ref{thm:olumlu} i\c cin do\u gruluk tablosu}\label{fig:tt4} \end{figure} Asl\i nda, sadece 4., 12., 13., 15., ve 16.\ sat\i rlarda, hem $P\lto Q$, hem $R\lto S$, hem de $P\lor R$ do\u gru, ve o sat\i rlarda, $Q\lor S$ de do\u gru. \end{proof} \begin{exercise}\label{exer:ger} $P\lor Q\lor R$, $P\lto Q$, ve $Q\lto R$ gerektirir $R$ oldu\u gunu g\"osterin. \end{exercise} Bir \"onerme form\"ul\"u, bo\c s k\"ume taraf\i ndan gerektirilebilir. Bu durumda, o form\"ule \textbf{do\u grusal ge\c cerli form\"ul,} veya \textbf{mant\i ksal do\u gru form\"ul,} veya \textbf{totoloji} denir.\footnote{Ali Nesin~\cite{Nesin-OM}, \"oyle form\"ullere \emph{hepdo\u gru} ad\i n\i\ verir.} O zaman $F$ bir totoloji, ancak ve ancak, her $d$ do\u gruluk g\"ondermesi i\c cin, $d(F)=1$. Mesela, \begin{align*} &P\lor\lnot P,&&1 \end{align*} form\"ulleri, totolojidirler. A\c sa\u g\i daki teoremden dolay\i\ yukar\i daki teoremleri kullanarak yeni totolojiler elde edebiliriz. \begin{theorem} \mbox{} \begin{compactenum} \item $F$ ve $G$ form\"ulleri birbirine denktir, ancak ve ancak \begin{equation*} F\liff G \end{equation*} form\"ul\"u bir totolojidir. \item $F$ form\"ul\"u, $G$ form\"ul\"un\"u gerektirir, ancak ve ancak \begin{equation*} F\lto G \end{equation*} form\"ul\"u bir totolojidir. \item $F$ ile $G$ form\"ulleri, $H$ form\"ul\"un\"u gerektir, ancak ve ancak \begin{equation*} F\land G\lto H \end{equation*} form\"ul\"u bir totolojidir. \item $F$, $G$, ve $H$ form\"ulleri, $K$ form\"ul\"un\"u gerektir, ancak ve ancak \begin{equation*} F\land G\land H\lto K \end{equation*} form\"ul\"u bir totolojidir. \end{compactenum} \end{theorem} \begin{proof} $F$ denktir $G$, ancak ve ancak, her $d$ do\u gruluk g\"ondermesi i\c cin, $d(F)=d(G)$, yani $d(F\liff G)=1$. Di\u ger b\"ol\"umler, \cexercise. %al\i\c st\i rma olarak b\i rak\i lm\i\c st\i r. \end{proof} Sonraki teoremi g\"ormek yararl\i\ olabilir. \begin{theorem}\label{th:subset} $\Gamma$, $\Delta$ (\emph{Delta}) k\"umesinin her eleman\i n\i\ i\c cersin. \begin{quote}\centering $\Delta\gerektirir F$ ise, o zaman $\Gamma\gerektirir F$. \end{quote} \end{theorem} \begin{proof} Gerektirme tan\i m\i ndan gelir. \end{proof} Bu teorem, sonraki teoremin \"ozel durumudur. \begin{theorem}\label{th:gerek-comp} $\Gamma$, $\Delta$ k\"umesindeki her form\"ul\"u gerektirsin. \begin{quote}\centering $\Delta\gerektirir F$ ise, o zaman $\Gamma\gerektirir F$. \end{quote} \begin{comment} \begin{equation*} \Gamma\gerektirir F \end{equation*} ise, o zaman \begin{equation*} \Delta\gerektirir F. \end{equation*} \end{comment} \end{theorem} \begin{proof} Gerektirme tan\i m\i ndan gelir. \end{proof} \pageref{th:sub}.\ sayfadaki Teorem \ref{th:sub} gibi bir teoremimiz var: \begin{theorem}\label{th:sub-2} $F$ form\"ul\"u, $G$ form\"ul\"un\"u gerektirsin; $H$, bir \"onerme de\u gi\c skeni olsun; ve $H'$, bir \"onerme form\"ul\"u olsun. E\u ger $F$ form\"ul\"unde $H$ de\u gi\c skeninin ge\c cti\u gi her yere $H'$ konulursa, $F'$ form\"ul\"u elde edilsin; e\u ger $G$ form\"ul\"unde $H$ de\u gi\c skeninin ge\c cti\u gi her yere $H'$ konulursa, $G'$ form\"ul\"u elde edilsin. O zaman \begin{equation*} F'\gerektirir G'. \end{equation*} \end{theorem} Tekrar bu teoremi, ispatlam\i yoruz. Bu teorem dolay\i s\i yla \begin{align*} P\lor\lnot Q\lor R\ile\lnot P\gerektirir\lnot Q\lor R,&&&\text{[Ay\i rma (Teorem \ref{th:bag-etc})]}\\ Q\gerektirir\lnot\lnot Q,&&&\text{[\c cifte de\u gilleme (Teorem \ref{thm:denk})]}\\ \lnot Q\lor R\ile\lnot\lnot Q\gerektirir R.&&&\text{[Ay\i rma]} \end{align*} O zaman \ref{th:subset} numaral\i\ Teoremlerden dolay\i \begin{equation*} P\lor\lnot Q\lor R\virgul\lnot P\ve Q\gerektirir\lnot Q\lor R\ve\lnot\lnot Q, \end{equation*} ve \ref{th:gerek-comp} numaral\i\ teoremlerden dolay\i \begin{equation*} P\lor\lnot Q\lor R\virgul\lnot P\ve Q\gerektirir R. \end{equation*} Bu gerektirmeyi, do\u gruluk tablolar\i\ kullanmadan ispatlad\i k. Kan\i tlamak i\c cin, sadece %\ref{fig:bk} numaral\i\ \c Sekildeki \begin{align}\label{eqn:bk} &P\lor\lnot Q\lor R,& &\lnot P,& &\lnot Q\lor R,& &Q,& &\lnot\lnot Q,& &R \end{align} form\"ulleri yazd\i k. \begin{comment} \begin{figure}[ht] \centering $\begin{gathered} P\lor\lnot Q\lor R\\ \lnot P\\ \lnot Q\lor R\\ Q\\ \lnot\lnot Q\\ R \end{gathered}$ \caption{Bi\c cimsel bir kan\i t}\label{fig:bk} \end{figure} \end{comment} Bu form\"uller listesi, \emph{bi\c cimsel bir kan\i tt\i r.} \chapter{Bi\c cimsel kan\i t} \c Simdi $\Gamma$, \begin{multline*} \{\lnot(S\land T),(R\land Q)\lor(T\land Q),P\lor(S\land\lnot T),\\ \lnot T\lor(Q\land(S\lor R)), \lnot R\lor T\} \end{multline*} k\"umesi olsun. O zaman \begin{equation}\label{eqn:Gamma} \Gamma\gerektirir P\land Q\land R\land\lnot S\land T; \end{equation} ama bunu do\u gruluk tablosu y\"ontemiyle g\"ostermek s\i k\i c\i\ olurdu. \emph{Bi\c cimsel kan\i t} y\"ontemi, bu durumda hem daha k\i sa, hem daha ilgin\c ctir. \textbf{Bi\c cimsel kan\i t,} bir form\"uller listesidir. \begin{equation*} F_1,\dots,F_n, \end{equation*} bi\c cimsel bir kan\i t olsun. Bu bi\c cimsel kan\i t\i n \textbf{sonucu,} $F_n$ form\"ul\"ud\"ur. $1\leq k\leq n$ varsay\i ls\i n. E\u ger $\{F_1,\dots,F_{k-1}\}$ k\"umesi, $F_k$ form\"ul\"un\"u \emph{gerektirmezse,} o zaman $F_k$, bi\c cimsel kan\i t\i n \textbf{hipotezlerinden} biridir. (E\u ger $k=1$ ise, o zaman $\{F_1,\dots,F_{k-1}\}$ k\"umesi bo\c stur.) Bu tan\i ma g\"ore, bi\c cimsel kan\i t\i n sonucu, bir hipotez de olabilir. Tekrar \eqref{eqn:bk} %numaral\i\ \c Sekildeki listesine bakal\i m. Bu bi\c cimsel kan\i t\i n hipotezleri, $P\lor\lnot Q\lor R$, $\lnot P$, ve $Q$ form\"ulleridir. $\lnot Q\lor R$, hipotez de\u gildir, \c c\"unk\"u onu, \"onceki form\"uller gerektirir; ayn\i\ nedenle, $R$ de hipotez de\u gildir. \begin{theorem}\label{th:kanit} $\Gamma$, bir \"onerme form\"ulleri k\"umesi olsun. E\u ger $F_1,\dots,F_n$ bi\c cimsel kan\i t\i n hipotezleri $\Gamma$ k\"umesinden geliyorsa, o zaman \begin{equation*} \Gamma\gerektirir F_n. \end{equation*} \end{theorem} \begin{proof} %$\Gamma=\{G_1,G_2,\dots\}$ olsun. O zaman \c C\"unk\"u \begin{gather*} % \{G_1,G_2,\dots\}\gerektirir F_1,\\ % \{F_1,G_1,G_2,\dots\}\gerektirir F_2,\\ % \{F_1,F_2,G_1,G_2,\dots\}\gerektirir F_3,\\ \Gamma\gerektirir F_1,\\ \Gamma\cup\{F_1\}\gerektirir F_2,\\ \Gamma\cup\{F_1,F_2\}\gerektirir F_3,\\ \makebox[4.5cm]{\dotfill},\\ % \{F_1,\dots,F_{n-1},G_1,G_2,\dots\}\gerektirir F_n, \Gamma\cup\{F_1,\dots,F_{n-1}\}\gerektirir F_n, \end{gather*} \ref{th:gerek-comp} numaral\i\ teorem dolay\i s\i yla $\Gamma\gerektirir F_n$. \end{proof} Bu teoremde, bi\c cimsel kan\i t, $\Gamma$ k\"umesinden $F_n$ form\"ul\"un\"u \textbf{kan\i tlar;} ve bi\c cimsel kan\i t, \textbf{$F_n$ form\"ul\"un\"un $\Gamma$ k\"umesinden} bi\c cimsel bir kan\i t\i d\i r. \emph{Sonlu} bir $\Gamma$ k\"umesi i\c cin, teoremin tersi de kolayd\i r. $\Gamma=\{F_1,\dots,F_{n-1}\}$ ise, ve $\Gamma\gerektirir F_n$ ise, o zaman $F_1,\dots,F_n$ listesi, $F_n$ form\"ul\"un\"un $\Gamma$ k\"umesinden bir bi\c cimsel kan\i t\i d\i r. Ama $\Gamma$ k\"umesinin $F_n$ form\"ul\"un\"u gerektirdi\u gini birine \emph{g\"ostermek} istersek, sadece $F_1,\dots,F_n$ listesini yazmak yeterli olmayabilir; daha fazla form\"uller yazmam\i z gerekebilir. \"Orne\u gin, \ref{exer:ger} numaral\i\ Al\i\c st\i rmay\i\ yapt\i ysak, a\c sa\u g\i daki listenin, $R$ form\"ul\"un\"un $P\lor Q\lor R$, $P\lto Q$, $Q\lto R$ hipotezlerinden bir bi\c cimsel kan\i t\i\ oldu\u gunu biliyoruz: \begin{align*} &P\lor Q\lor R,& &P\lto Q,& &Q\lto R,& &R. \end{align*} Ancak, o al\i\c st\i rmay\i\ yapmad\i ysak, daha fazla ad\i m gerekir, \ref{fig:3al} numaral\i\ \c Sekildeki %a\c sa\u g\i daki gibi. \begin{figure}[ht] \centering $\begin{gathered} P\lto Q\\ \lnot P\lor Q\\ \lnot P\lor Q\lor R\\ Q\lto R\\ \lnot Q\lor R\\ (\lnot P\lor Q\lor R)\land(\lnot Q\lor R)\\ ((\lnot P\lor Q)\land\lnot Q))\lor R\\ (\lnot P\land\lnot Q)\lor R\\ \lnot(P\lor Q)\lor R\\ P\lor Q\lor R\\ (\lnot(P\lor Q)\lor R)\land(P\lor Q\lor R)\\ (\lnot(P\lor Q)\lor P\lor Q)\land R\\ 1\land R\\ R \end{gathered}$ \caption{Bi\c cimsel bir kan\i t}\label{fig:3al} \end{figure} Ad\i mlar\i n nedenlerini ekleyebiliriz, \ref{fig:3al-ile} numaral\i\ \c Sekildeki gibi. \begin{figure}[ht] \centering \renewcommand{\arraystretch}{1.2} $\begin{array}{rcl} \text{1.}& P\lto Q&\text{hipotez}\\ \text{2.}&\lnot P\lor Q&\text{1.\ sat\i rdan}\\ & &\qquad\text{$P\lto Q\sim\lnot P\lor Q$ ile}\\ \text{3.}&\lnot P\lor Q\lor R&\text{2.\ sat\i rdan eklemeyle}\\ \text{4.}&Q\lto R&\text{hipotez}\\ \text{5.}&\lnot Q\lor R&\text{4.\ sat\i rdan}\\ & &\qquad\text{$P\lto Q\sim\lnot P\lor Q$ ile}\\ \text{6.}&(\lnot P\lor Q\lor R)\land(\lnot Q\lor R)&\text{3.\ ve 5.\ sat\i rdan ba\u glamayla}\\ \text{7.}&((\lnot P\lor Q)\land\lnot Q))\lor R&\text{6. sat\i rdan da\u g\i lmayla}\\ \text{8.}&(\lnot P\land\lnot Q)\lor R&\text{7.\ sat\i rdan}\\ & &\qquad \text{$\lnot P\land(P\lor Q)\sim \lnot P\land Q$ ile}\\ \text{9.}&\lnot(P\lor Q)\lor R&\text{8.\ sat\i rdan De Morgan kural\i yla}\\ \text{10.}&P\lor Q\lor R&\text{hipotez}\\ \text{11.}&(\lnot(P\lor Q)\lor R)\land(P\lor Q\lor R)&\text{9.\ ve 10.\ sat\i rdan ba\u glamayla}\\ \text{12.}&(\lnot(P\lor Q)\lor P\lor Q)\land R&\text{11.\ sat\i rdan da\u g\i lmayla}\\ \text{13.}&1\land R&\text{12.\ sat\i rdan fazlal\i kla}\\ \text{14.}&R&\text{13.\ sat\i rdan fazlal\i kla} \end{array}$ \caption{A\c c\i klamal\i\ bir kan\i t}\label{fig:3al-ile} \end{figure} \begin{figure}[p] \centering $\begin{gathered} (R\land Q)\lor(T\land Q)\\ (R\lor T)\land Q\\ Q\\ R\lor T\\ \lnot R\lor T\\ (R\lor T)\land(\lnot R\lor T)\\ (R\land\lnot R)\lor T\\ 1\lor T\\ T\\ \lnot(S\land T)\\ \lnot S\lor\lnot T\\ \lnot\lnot T\\ \lnot S \lnot S\land T\\ P\lor(S\land\lnot T)\\ \lnot S\lor\lnot\lnot T\\ \lnot(S\land\lnot T)\\ P\\ \lnot T\lor(Q\land(S\lor R))\\ Q\land(S\lor R)\\ S\lor R\\ R\\ R\land\lnot S\land T\\ Q\land R\land\lnot S\land T\\ P\land Q\land R\land\lnot S\land T \end{gathered}$ \caption{Bi\c cimsel bir kan\i t}\label{fig:kan} \end{figure} \begin{exercise} Yukar\i daki~\eqref{eqn:Gamma} gerektirmesinin, \ref{fig:kan} numaral\i\ \c Sekilde bi\c cimsel kan\i t\i\ vard\i r. Her sat\i r\i n nedenini verin. \end{exercise} \begin{exercise} A\c sa\u g\i daki totolojiler ve gerektirmeler i\c cin bi\c cimsel kan\i tlar yaz\i n. \begin{enumerate} \item $P\lto P\lto P$ bir totolojidir. \item $P\lto Q\lto P$ bir totolojidir. \item $P\lor(P\lto Q)$ bir totolojidir. \item $(P\lto Q)\lor\lnot Q$ bir totolojidir. \item $P\lto Q\land R\gerektirir P\lto Q$. \item $P\land\lnot P\gerektirir Q$. \item $P\land(Q\lor R)\gerektirir P\liff(\lnot Q\lor P)$. \item $P\lto Q\ile P\lto\lnot Q\gerektirir\lnot P$. \item $P\lto R\ile Q\lto R\gerektirir P\lor Q\lto R$. \item $P\lto R\ile Q\lto S\gerektirir P\lor Q\lto R\lor S$. \end{enumerate} \end{exercise} \chapter{\"Oklid'in \"onermeleri} \"Oklid'in \"onermelerinin g\"osterileri, daha bi\c cimsel olarak yaz\i labilir. \"Orne\u gin, onun I.5 numaral\i\ \"onermesine bakal\i m. Likyal\i\ Proklus'a g\"ore \cite[sayfa 159]{MR1200456}, \"Oklid'in her \"onermesinin 6 tane par\c cas\i\ var: \begin{inparaenum}[(1)] \item ilan, \item a\c c\i klama, \item belirtme, \item haz\i rlama, \item g\"osteri, ve \item bitirme. \end{inparaenum} A\c c\i klamada hipotezler bulunur; belirtmede sonu\c clar bulunur. \c Co\u gunlukla bir \"onermenin bir sonucu vard\i r; ama I.5 numaral\i\ \"onermenin iki sonucu vard\i r. Haz\i rlama ve g\"osteri, sonu\c clar\i n hipotezlerinden bi\c cimsel kan\i t olarak yaz\i labilir. G\"osterinin hipotezleri, haz\i rlamadan da gelebilir. \begin{description} \item[\.Ilan:] Bir ikizkenar \"u\c cgenin taban\i ndaki a\c c\i lar birbirine e\c sittir,\\ ve, e\c sit do\u grular uzat\i ld\i\u g\i nda,\\ taban\i n alt\i nda kalan a\c c\i lar birbirine e\c sit olacaklard\i r. \item[A\c c\i klama:] \grm{ABG} \"u\c cgeninde $\grm{AB}=\grm{AG}$% %[\ref{fig:I.5} numaral\i\ \c Sekile bak\i n] .\\ \grm{AB}, \grm D noktas\i na uzat\i lm\i\c s.\\ \grm{AG}, \grm E noktas\i na uzat\i lm\i\c s. \item[Belirtme:] \mbox{} \begin{enumerate} \item $\angle\grm{ABG}=\angle\grm{AGB}$ ve \item $\angle\grm{GBD}=\angle\grm{BGE}$. \end{enumerate} \item[Haz\i rlama:]\mbox{} \begin{enumerate} \item \grm Z noktas\i, \grm{BD} do\u grusundad\i r. \item \grm H noktas\i, \grm{GE} do\u grusundad\i r, ve $\grm{AH}=\grm{AZ}$.\hfill[I.3] \end{enumerate} \item[G\"osteri:]\mbox{} \begin{enumerate} \item $\grm{AZ}=\grm{AH}$\hfill[haz\i rlamadaki 2.\ sat\i rdan] \item $\grm{AB}=\grm{AG}$\hfill[hipotez] \item $\grm{ZG}=\grm{HB}$\hfill[1.\ ve 2.\ sat\i rdan I.4 ile] \item $\triangle\grm{AZG}=\triangle\grm{AHB}$\hfill[1.\ ve 2. sat\i rdan I.4 ile] \item $\angle\grm{AGZ}=\angle\grm{ABH}$\hfill[1.\ ve 2. sat\i rdan I.4 ile] \item $\angle\grm{AZG}=\angle\grm{AHB}$\hfill[1.\ ve 2. sat\i rdan I.4 ile] \item $\grm{BZ}=\grm{GH}$\hfill[1.\ ve 2.\ sat\i rdan genel kavram 3 ile] \item $\triangle\grm{BZG}=\triangle\grm{GHB}$\hfill[3., 6., ve 7.\ sat\i rdan I.4 ile] \item $\angle\grm{ZBG}=\angle\grm{HGB}$\hfill[3., 6., ve 7.\ sat\i rdan I.4 ile] \item $\angle\grm{BGZ}=\angle\grm{GBH}$\hfill[3., 6., ve 7.\ sat\i rdan I.4 ile] \item $\angle\grm{ABG}=\angle\grm{AGB}$\hfill[5.\ ve 10.\ sat\i rdan genel kavram 3 ile] \end{enumerate} \item[Bitirme:] Bir ikizkenar \"u\c cgenin taban\i ndaki a\c c\i lar birbirine e\c sittir,\\ ve, e\c sit do\u grular uzat\i ld\i\u g\i nda,\\ taban\i n alt\i nda kalan a\c c\i lar birbirine e\c sit olacaklar.\\ G\"osterilmesi gereken tam buydu. \end{description} %\begin{figure}[ht] % \centering \begin{center} \psset{xunit=5mm,yunit=5mm} \begin{pspicture}(-2,-6.5)(2,1) \psline(-2,-6)(0,0)(2,-6) \psline(1.67,-5)(-1,-3)(1,-3)(-1.67,-5) \uput[u](0,0){\grm A} \uput[l](-1,-3){\grm B} \uput[r](1,-3){\grm G} \uput[l](-2,-6){\grm D} \uput[r](2,-6){\grm E} \uput[l](-1.67,-5){\grm Z} \uput[r](1.67,-5){\grm H} \end{pspicture} \end{center} % \caption{\"Oklid'in I.5 numaral\i\ \"onermesinin \c sekli}\label{fig:I.5} %\end{figure} Burada, belirtmedeki 1.\ sonu\c c, g\"osterinin 11.\ sat\i r\i d\i r, ve 2.\ sonu\c c, g\"osterinin 9.\ sat\i r\i d\i r; $\angle\grm{ZBG}=\angle\grm{GBD}$ ve $\angle\grm{HGB}=\angle\grm{BGE}$ e\c sitliklerini tan\i mam\i z gerekir. \"Oklid, g\"osterinin 4.\ ve 8.\ sat\i r\i n\i\ verir, ama kullanmaz. \begin{exercise} Bi\c cimsel olarak \"Oklid'in her \"onermesini yaz\i n. \end{exercise} \chapter{T\i k\i zl\i k} \"Onceden dedi\u gimiz gibi, her \emph{sonlu} $\Gamma$ \"onermeler k\"umesi i\c cin, e\u ger $\Gamma$, bir $F$ form\"ul\"un\"u gerektiriyorsa, o zaman $F$ form\"ul\"un\"un $\Gamma$ k\"umesinden bir bi\c cimsel kan\i t\i\ vard\i r. Sonluluk ko\c sulu kald\i r\i labilir: bu ger\c ce\u ge \textbf{t\i k\i zl\i k} denir. $d$, bir do\u gruluk g\"ondermesiyse, ve $\Delta$, bir form\"uller k\"umesiyse, ve $\Delta$ k\"umesindeki her $G$ i\c cin, $d(G)=1$ ise, o zaman $d$ g\"ondermesine $\Delta$ k\"umesinin bir \textbf{modeli} denir. \begin{theorem} $\Gamma\gerektirir F$ ancak ve ancak $\Gamma\cup\{\lnot F\}$ k\"umesinin modeli yok. \end{theorem} \begin{proof} \cexercise. %Kolay bir al\i\c st\i rmad\i r. \end{proof} \begin{theorem}[T\i k\i zl\i k]\label{th:tkz} $\Gamma$, $F$ form\"ul\"un\"u gerektirirse, o zaman $F$ form\"ul\"un\"un $\Gamma$ k\"umesinden bir bi\c cimsel kan\i t\i\ vard\i r. \end{theorem} \begin{proof} Kar\c s\i t tersini ispatlayaca\u g\i z. $F$ form\"ul\"un\"un $\Gamma$ k\"umesinden hi\c c bi\c cimsel kan\i t\i\ olmad\i\u g\i n\i\ varsayal\i m. $\Gamma\cup\{\lnot F\}$ k\"umesinin bir modelini bulaca\u g\i z. $\Gamma$ k\"umesinin her sonlu $\{G_1,\dots,G_n\}$ altk\"umesi i\c cin, o altk\"ume, $F$ form\"ul\"un\"u gerektirmez. (Bildi\u gimiz gibi $\{G_1,\dots,G_n\}$, $F$ form\"ul\"un\"u gerektirirse, o zaman $G_1,\dots,G_n,F$ listesi, $F$ form\"ul\"un $\Gamma$ k\"umesinden bi\c cimsel bir kan\i t\i d\i r.) Dolay\i s\i yla $\{G_1,\dots,G_n,\lnot F\}$ k\"umesinin modeli vard\i r. T\"um \"onerme de\u gi\c skenlerinin, $\{P_1,P_2,P_3,\dots\}$ k\"umesini olu\c sturdu\u gunu varsayabiliriz. Her $n$ i\c cin, $\Gamma_n$, $\Gamma$ k\"umesinde olan ve de\u gi\c skenleri sadece $\{P_1,\dots,P_n\}$ k\"umesinden olan form\"uller k\"umesi olsun. $\Gamma_n$ sonsuz olabilir; ama $\Gamma_n$ k\"umesindeki form\"ullerin do\u gruluk tablolar\i n\i n k\"umesi, sonludur. Onun i\c cin $\Gamma_n\cup\{\lnot F\}$ k\"umesinin modeli vard\i r. $M_n$, o k\"umenin t\"um modellerinin k\"umesi olsun. $n\leq p$ ise, o zaman $M_n$, $M_p$ k\"umesini kapsar. Bir $d^*$ do\u gruluk g\"ondermesi i\c cin, her $n$ i\c cin, $d^*$ g\"ondermesinin $M_n$ k\"umesinin bir eleman\i\ oldu\u gunu g\"osterece\u giz. E\u ger bir $n$ i\c cin, $M_n$ k\"umesindeki her $d$ i\c cin, $d(P_1)=0$ ise, o zaman $d^*(P_1)=0$ olsun. \"Oteki durumda, her $n$ i\c cin, $M_n$ k\"umesindeki bir $d$ i\c cin, $d(P_1)=1$ olur; bu durumda, $d^*(P_1)=1$ olsun. Her durumda, her $n$ i\c cin, $M_n$ k\"umesinin $d(P_1)=d^*(P_1)$ oldu\u gu $d$ eleman\i\ vard\i r. E\u ger bir $n$ i\c cin, $M_n$ k\"umesindeki $d(P_1)=d^*(P_1)$ e\c sitli\u gini sa\u glayan her $d$ i\c cin, $d(P_2)=0$ ise, o zaman $d^*(P_2)=0$ olsun. \"Oteki durumda, her $n$ i\c cin, $M_n$ k\"umesindeki bir $d$ i\c cin, $d(P_1)=d^*(P_1)$ ve $d(P_2)=1$ olur; bu durumda, $d^*(P_2)=1$ olsun. Her durumda, her $n$ i\c cin, $M_n$ k\"umesinin $d(P_1)=d^*(P_1)$ ve $d(P_2)=d^*(P_2)$ e\c sitli\u gini sa\u glayan $d$ eleman\i\ vard\i r. Ayn\i\ \c sekilde devam ediyoruz. Bir $k$ i\c cin, $d^*(P_1)$, \dots, $d^*(P_k)$ de\u gerlerini se\c cti\u gimizi varsayal\i m, ve her $n$ i\c cin, $M_n$ k\"umesinin \begin{align*} d(P_1)&=d^*(P_1),& &\dots,& d(P_k)&=d^*(P_k) \end{align*} e\c sitliklerini sa\u glayan $d$ eleman\i n\i n oldu\u gunu varsayal\i m. E\u ger bir $n$ i\c cin, $M_n$ k\"umesindeki $d(P_1)=d^*(P_1)$, \dots, $d(P_k)=d^*(P_k)$ e\c sitliklerini sa\u glayan her $d$ i\c cin, $d(P_{k+1})=0$ ise, o zaman $d^*(P_{k+1})=0$ olsun. \"Oteki durumda, her $n$ i\c cin, $M_n$ k\"umesindeki bir $d$ i\c cin, $d(P_1)=d^*(P_1)$, \dots, $d(P_{k+1})=1$ olur; bu durumda, $d^*(P_{k+1})=1$ olsun. Her durumda, her $n$ i\c cin, $M_n$ k\"umesinin $d(P_1)=d^*(P_1)$, \dots, $d(P_{k+1})=d^*(P_{k+1})$ e\c sitliklerini sa\u glayan $d$ eleman\i\ vard\i r. \c Simdi her $n$ i\c cin $d^*$, $\Gamma_n\cup\{\lnot F\}$ k\"umesinin bir modelidir; o zaman $d^*$, $\Gamma\cup\{\lnot F\}$ k\"umesinin modelidir. Bu \c sekilde $\Gamma$, $F$ form\"ul\"un\"u gerektirmez. \end{proof} \chapter{Bi\c cimsel dizgeler} Tan\i ma g\"ore, bi\c cimsel bir kan\i tta, her sat\i r, \begin{compactenum}[1)] \item ya bir totoloji, \item ya \"onceki sat\i rlar taraf\i ndan gerektirilen bir form\"ul, \item ya da bir hipotezdir. \end{compactenum} Bir form\"ul, totoloji ise, bunu do\u gruluk tablosuyla g\"osterebiliriz. Bir form\"ul, ba\c ska form\"uller taraf\i ndan gerektiriliyorsa, bunu da do\u gruluk tablolar\i yla g\"osterebiliriz. Ancak, do\u gruluk tablolar\i n\i\ kullanmadan, bi\c cimsel bir kan\i t\i n hipotezlerini ve hipotez olmayan sat\i rlar\i n\i\ ay\i rt edebilmek isteriz. Bunu yapmak i\c cin bi\c cimsel bir y\"onteme, \emph{bi\c cimsel dizge} denir. Kesinlik i\c cin, \textbf{bi\c cimsel dizge,} \begin{compactenum}[1)] \item baz\i\ bilinen totolojilerden ve \item baz\i\ bilinen gerektirmelerden \end{compactenum} olu\c sur. Bu bilinen totolojilere dizgenin \textbf{aksiyomu} denir; bu bilinen gerektirmelere dizgenin \textbf{\c c\i kar\i m kural\i} denir. $D$, bi\c cimsel bir dizge; $\Gamma$, bir form\"uller k\"umesi; ve $K$, bi\c cimsel bir kan\i t olsun. E\u ger $K$ kan\i t\i n her sat\i r\i, \begin{compactenum}[1)] \item ya $D$ dizgesinin bir aksiyomu, \item ya $D$ dizgesinin bir \c c\i kar\i m kural\i na g\"ore \"onceki sat\i rlar taraf\i ndan gerektirilen bir form\"ul, \item ya da $\Gamma$ k\"umesinin bir eleman\i\ ise, \end{compactenum} o zaman $\Gamma$, $K$ kan\i t\i n sonucunu gerektirir, ve ayr\i ca, bu gerektirme, $D$ dizgesinin \textbf{(bi\c cimsel) bir teoremdir.} Her gerektirme, $D$ dizgesinin bir teoremi ise, bu dizgeye \textbf{tam} denir. \section{Bi\c cimsel $\bd1$ dizgesi} \c Simdi $\bd1$ adl\i\ bi\c cimsel dizgesini tan\i mlayaca\u g\i z. Aksiyomlar\i, iki \c sekilde: \begin{itemize} \item $1$ form\"ul\"u, \item her $\lnot F\lor F$ form\"ul\"u. \end{itemize} \c C\i kar\i m kurallar\i, \"u\c c \c sekilde: \begin{description} \item[Ekleme:] T\"um $F$ ve $G$ form\"ulleri i\c cin, $F$ form\"ul\"unden $G\lor F$ \c c\i kar. \item[Ba\u glama:] $F$ ile $G$ form\"ullerinden $F\land G$ \c c\i kar. \item[Yerine Koyma:] $F\sim G$, \ref{thm:denk} numaral\i\ Teoremden bir denklik olsun. Bu denklikten, \ref{th:sub} numaral\i\ Teoreme g\"ore, $F'\sim G'$ denkli\u gi sa\u glans\i n. E\u ger bir $K$ form\"ul\"un $F'$ alt form\"ul\"u var, ve bu alt form\"ul\"un yerine $G'$ koyarak $K^*$ form\"ul\"u, (\ref{th:rep} numaral\i\ Teoremdeki gibi) elde ediliyorsa, o zaman $K$ form\"un\"unden $K^*$ \c c\i kar. \end{description} $\bd1$ dizgesinin tam oldu\u gunu g\"osterece\u giz. Bunu yapmak i\c cin, ilk olarak, her form\"ul\"un \emph{tikel-evetlemeli normal bi\c cimi} oldu\u gunu g\"ozlemleyece\u giz. Tikel-evetlemeli normal bi\c cim, en iyi \"orneklerden anlanla\c s\i l\i r. $P\lor Q\lto R$ ve $(P\lto R)\land(Q\lto R)$ form\"ullerinin do\u gruluk tablolar\i, birbiriyle ayn\i d\i r, ve bu ortak tablo, %\ref{fig:tt-5} numaral\i\ \c Sekildedir. yukar\i daki \ref{fig:tt-5} numaral\i\ \c Sekildedir. Dolay\i s\i yla bu form\"ullerin tikel-evetlemeli normal bi\c cimleri birbiriyle ayn\i d\i r ve a\c sa\u g\i daki gibi yaz\i l\i r: \begin{multline*}%\label{eqn:dnf} (\lnot P\land\lnot Q\land\lnot R)\lor(\lnot P\land\lnot Q\land R)\lor(P\land\lnot Q\land R)\\ {}\lor(\lnot P\land Q\land R)\lor(P\land Q\land R). \end{multline*} Bu \"onermeyi anlamak i\c cin, \ref{fig:dnf} numaral\i\ \c Sekle bak\i n. \begin{figure}[ht] \centering $ \begin{array}{c|*8c} P &0&1&0&1&0&1&0&1\\ Q &0&0&1&1&0&0&1&1\\ R &0&0&0&0&1&1&1&1\\ P\lor Q\lto R &1&0&0&0&1&1&1&1\\ \lnot P\land\lnot Q\land\lnot R&1&0&0&0&0&0&0&0\\ \lnot P\land\lnot Q\land R&0&0&0&0&1&0&0&0\\ P\land\lnot Q\land R&0&0&0&0&0&1&0&0\\ \lnot P\land Q\land R&0&0&0&0&0&0&1&0\\ P\land Q\land R&0&0&0&0&0&0&0&1 \end{array}$ \begin{comment} \begin{sideways} $\begin{array}{ccc|c|c|c|c|c|c} P&Q&R&P\lor Q\lto R&\lnot P\land\lnot Q\land\lnot R&\lnot P\land\lnot Q\land R&P\land\lnot Q\land R&\lnot P\land Q\land R&P\land Q\land R\\\hline 0&0&0&1&1&0&0&0&0\\ 1&0&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0&0\\ 0&0&1&1&0&1&0&0&0\\ 1&0&1&1&0&0&1&0&0\\ 0&1&1&1&0&0&0&1&0\\ 1&1&1&1&0&0&0&0&1 \end{array}$ \end{sideways} \end{comment} \caption[Tikel-evetlemeli normal bi\c cim i\c cin do\u gruluk tablolar\i]{$P\lor Q\lto R$ form\"ul\"un\"un tikel-evetlemeli normal bi\c cimi i\c cin do\u gruluk tablolar\i} \label{fig:dnf} \end{figure} Genellikle, $F$, bir \"onerme form\"ul\"u olsun, ve onun \"onerme de\u gi\c skenleri, $P_1$, \dots, $P_n$ olsun. $d$, bir do\u gruluk g\"ondermesi olsun. O zaman \begin{equation*} (d(P_1),\dots,d(P_n)) \end{equation*} listesi i\c cin, $2^n$ tane se\c cenek var. Bir $m$ i\c cin, $m$ ve sadece $m$ tane se\c cenek i\c cin, $d(F)=1$. O se\c cenekler, \begin{align*} &(e_1^1,\dots,e_n^1),&&\dots,&&(e_1^m,\dots,e_n^m) \end{align*} olsun. (\"Orne\u gin, $P_1\lor P_2\lto P_3$ i\c cin, se\c cenekler, $(0,0,0)$, $(0,0,1)$, $(1,0,1)$, $(0,1,1)$, $(1,1,1)$ listeleridir.) $1\leq j\leq n$ ve $1\leq i\leq m$ varsayal\i m. \begin{compactitem} \item $e_j^i=0$ ise $P_j^i$, $\lnot P_j$ form\"ul\"u olsun; \item $e_j^i=1$ ise $P_j^i$, $P_j$ form\"ul\"u olsun. \end{compactitem} Ondan sonra $F^i$, \begin{equation*} P_1^i\land\dotsb\land P_n^i \end{equation*} \textbf{t\"umel-evetlemesi} olsun. O zaman \begin{equation*} F^1\lor\dotsb\lor F^m \end{equation*} \textbf{tikel-evetlemesi,} $F$ form\"ul\"un\"un \textbf{tikel-evetlemeli normal bi\c cimidir.} Yani, $F$ form\"ul\"un\"un tikel-evetlemeli normal bi\c cimi, \begin{equation*} (P_1^1\land\dotsb\land P_n^1)\lor\dotsb\lor(P_1^m\land\dotsb\land P_n^m) \end{equation*} form\"ul\"ud\"ur. Bu form\"ul\"un $F$ form\"ul\"une denk oldu\u gu g\"or\"unebilir. Burada $m=0$ olabilir. Bu durumda, $F$ form\"ul\"un\"un tikel-evetlemeli normal bi\c cimi, $0$ form\"ul\"ud\"ur. Bir de $n=0$ olabilir. Bu durumda, ya $F\denktir 0$ ya da $F\denktir1$. S\i ras\i yla $F$ form\"ul\"un\"un tikel-evetlemeli normal bi\c cimi, ya $0$ ya da $1$'dir. \c Simdi a\c sa\u g\i daki al\i\c st\i rma kolayl\i kla \c c\"oz\"ulebilir. \begin{exercise} Rastgele bir do\u gruluk tablosu i\c cin, do\u gruluk tablosu o olan bir form\"ul\"u yaz\i n. \end{exercise} \begin{theorem} Bir $\{F_1,\dots,F_n\}$ form\"uller k\"umesi, bir $G$ form\"ul\"un\"u gerektirir, ancak ve ancak $G\lor(F_1\land\dotsb F_n)$, $G$ form\"ul\"une denktir. \end{theorem} \begin{proof} \cexercise. %Al\i\c st\i rma. \end{proof} \begin{theorem} Bi\c cimsel $\bd1$ dizgesi tamd\i r. \end{theorem} \begin{proof} \.Ilk olarak $F$, bir totoloji olsun. Sadece Yerine Koyma kural\i\ kullanarak, $F$ form\"ul\"un\"u, tikel-evetlemeli normal $F'$ bi\c cimine getirebiliriz. T\"um ad\i mlar, tersine \c cevrilebilir; bu \c sekilde, $F'$ form\"ul\"un\"un $F$ form\"ul\"un\"u gerektirdi\u gi, $\bd1$ dizgesinin bir teoremidir. Ayr\i ca, $F'$ form\"ul\"un\"un totoloji oldu\u gu, $\bd1$ dizgesinin bir teoremidir. O zaman $F$ form\"ul\"un\"un totoloji oldu\u gu, $\bd1$ dizgesinin bir teoremidir. \c Simdi $\Gamma$ k\"umesi, $F$ form\"ul\"un\"u gerektirsin. \ref{th:tkz} numaral\i\ T\i k\i zl\i k Teoremine g\"ore, $\Gamma$ k\"umesinin bir $\{G_1,\dots,G_n\}$ altk\"umesi de $F$ form\"ul\"un\"u gerektirir. Ba\u glama ve Ekleme kurallar\i\ sayesinde, bu k\"umenin $F\lor(G_1\land\dotsb\land G_n)$ form\"ul\"un\"u gerektirdi\u gi, $\bd1$ dizgesinin bir teoremdir. \"Onceki teoreme g\"ore, $F$ ve $F\lor(G_1\land\dotsb\land G_n)$ form\"ulleri, birbirine denktir; dolay\i s\i yla, bu form\"ullerin ayn\i\ tikel-evetlemeli normal $F'$ bi\c cimi vard\i r. $F\lor(G_1\land\dotsb\land G_n)$ form\"ul\"un\"un $F'$ form\"ul\"un\"u gerektirdi\u gi, ve $F'$ form\"ul\"un\"un $F$ form\"ul\"un\"u gerektirdi\u gi, $\bd1$ dizgesinin teoremidir. O zaman $\Gamma$ k\"umesinin $F$ form\"ul\"un\"u gerektirdi\u gi, $\bd1$ dizgesinin teoremidir. \end{proof} \section{Bi\c cimsel $\bd2$ dizgesi} Bu a\c samada yeni simgeler yararl\i\ olacak. E\u ger $\Gamma$, $F$ form\"ul\"un\"u gerektirirse, \begin{equation*} \Gamma\models F \end{equation*} ifadesini yazaca\u g\i z. Bu $\models$ simgesine \textbf{turnike} denir. T\i k\i zl\i k Teoremine g\"ore, $\Gamma\models F$ ise, o zaman $\Gamma$ k\"umesinin sonlu bir $\Gamma_0$ altk\"umesi i\c cin $\Gamma_0\models F$ olur. E\u ger bir $\Gamma\models F$ gerektirmesi, bi\c cimsel $D$ dizgesinin bir teoremiyse, \begin{equation*} \Gamma\proves[D]F \end{equation*} ifadesini yazaca\u g\i z. Bu $\proves[]$ simgesi de, bir turnikedir. \.Istersek, $\models$ simgesine \textbf{yorumsal} turnike diyebiliriz; $\proves[]$ simgesine \textbf{dizimsel} turnike diyebiliriz. Ancak adlar \"onemli de\u gil. \ref{th:kanit} numaral\i\ Teoreme g\"ore \begin{center} her $\Gamma$ ve $F$ i\c cin, $\Gamma\proves[D]F$ ise $\Gamma\models F$. \end{center} Ayr\i ca $D$ dizgesi tamd\i r ancak ve ancak \begin{center} her $\Gamma$ ve $F$ i\c cin, $\Gamma\models F$ ise $\Gamma\proves[D]F$. \end{center} Tam bi\c cimsel bir dizge, $\bd1$ dizgesinden daha basit olabilir. \.Ilk olarak, bir form\"ul\"un tikel-evetlemeli normal bi\c cimi, sadece $\lor$, $\land$, $\lnot$, $0$, ve $1$ ba\u glay\i c\i lar\i n\i\ kullan\i r. Ayr\i ca \begin{align*} 0&\sim\lnot 1,& 1&\sim\lnot P_1\lor P_1,& F\land G&\sim\lnot(\lnot F\land\lnot G). \end{align*} \"Oyleyse her form\"ul, sadece $\lor$ ile $\lnot$ ba\u glay\i c\i lar\i n\i n kullan\i ld\i\u g\i\ bir form\"ule denktir. $\bd2$ adl\i\ bi\c cimsel dizge,\footnote{Bu dizgeyi Shoenfield'den \cite{MR1809685} ald\i m, ama ilk kayna\u g\i, Russell ile Whitehead'dir \cite{PM}.} sadece bu ba\u glay\i c\i lar\i\ kullanacak. $\Gamma\proves[D_2]F$ yerine, \begin{equation*} \Gamma\proves F \end{equation*} yazal\i m. $\bd2$ dizgesinin her aksiyomu, $\lnot F\lor F$ bi\c cimindedir: \begin{equation*} \proves\lnot F\lor F. \end{equation*} $\bd2$ dizgesinin \c c\i kar\i m kurallar\i, a\c sa\u g\i daki \c sekillerdedir. \begin{compactdesc} \item[Ekleme:] T\"um $F$ ve $G$ form\"ulleri i\c cin, $F$ form\"ul\"unden $G\lor F$ \c c\i kar: \begin{equation*} F\proves G\lor F. \end{equation*} \item[Daralma:] $F\lor F$ form\"ul\"unden $F$ \c c\i kar: \begin{equation*} F\lor F\proves F. \end{equation*} \item[Birle\c sme:] $F\lor(G\lor H)$ form\"ul\"unden $(F\lor G)\lor H$ \c c\i kar: \begin{equation*} F\lor(G\lor H)\proves(F\lor G)\lor H. \end{equation*} \item[Kesme:] $F\lor G$ ve $\lnot F\lor H$ form\"ullerinden $G\lor H$ \c c\i kar: \begin{equation*} F\lor G\virgul\lnot F\lor H\proves G\lor H. \end{equation*} \end{compactdesc} \begin{theorem}[De\u gi\c sme] $\Gamma\proves F\lor G$ ise $\Gamma\proves G\lor F$. \end{theorem} \begin{proof} E\u ger $\Gamma\proves F\lor G$ ise, o zaman $\proves\lnot F\lor F$ sayesinde Kesme kural\i yla $\Gamma\proves G\lor F$. \end{proof} $F\lor G\lor H$ demek $F\lor(G\lor H)$ oldu\u gunu hat\i rlay\i n, onun i\c cin \begin{center} $F_1\lor\dotsb\lor F_n$ demek $F_1\lor(F_2\lor\cdots(F_{n-1}\lor F_n)\cdots)$. \end{center} \begin{theorem}[Genelle\c stirilmi\c s Ekleme, Daralma, ve De\u gi\c sme]\label{th:gen} Bir $n$ say\i s\i\ i\c cin, $F_1$, \dots, $F_n$, form\"uller olsun. Bir $m$ i\c cin, her $i$ i\c cin, $1\leq i\leq m$ ise $1\leq k_i\leq n$ sa\u glayan $k_i$ say\i s\i\ se\c cilsin. O zaman \begin{center} $\Gamma\proves F_{k_1}\lor\dotsb\lor F_{k_m}$ ise $\Gamma\proves F_1\lor\dotsb\lor F_n$. \end{center} \end{theorem} \begin{proof} %\mbox{} \begin{asparadesc} \item[$\bm{m=1}$ durumu.] $1\leq k\leq m$ ve $\Gamma\proves F_k$ varsay\i yoruz. O zaman \begin{align*} \Gamma&\proves(F_{k+1}\lor\dotsb\lor F_n)\lor F_k,&&\text{[Ekleme]}\\ \Gamma&\proves F_k\lor F_{k+1}\lor\dotsb\lor F_n,&&\text{[De\u gi\c sme]}\\ \Gamma&\proves F_{k-1}\lor F_k\lor F_{k+1}\lor\dotsb\lor F_n,&&\text{[Ekleme]}\\ &\makebox[5cm]{\dotfill}&&\\ \Gamma&\proves F_1\lor\dotsb\lor F_k\lor F_{k+1}\lor\dotsb\lor F_n,&&\text{[Ekleme]} \end{align*} yani $\Gamma\proves F_1\lor\dotsb\lor F_n$. \item[$\bm{m=2}$ durumu.] $1\leq i\leq n$, $1\leq j\leq n$ ve \begin{equation*} \Gamma\proves F_i\lor F_j \end{equation*} varsay\i yoruz. E\u ger $i=j$ ise, o zaman Daralmayla $\Gamma\proves F_i$, ve $m=1$ durumundan $\Gamma\proves F_1\lor\dotsb\lor F_n$. E\u ger $j2$ ise, o zaman \begin{align*} \Gamma&\proves F_1\lor F_3\lor\dotsb\lor F_{k+1},&&\text{[$n=k$ durumu]}\\ \Gamma&\proves(F_3\lor\dotsb\lor F_{k+1})\lor F_1,&&\text{[De\u gi\c sme]}\\ \Gamma&\proves F_2\lor(F_3\lor\dotsb\lor F_{k+1})\lor F_1,&&\text{[Ekleme]}\\ \Gamma&\proves ((F_3\lor\dotsb\lor F_{k+1})\lor F_1)\lor F_2,&&\text{[De\u gi\c sme]}\\ \Gamma&\proves (F_3\lor\dotsb\lor F_{k+1})\lor F_1\lor F_2,&&\text{[Birle\c sme]}\\ \Gamma&\proves F_1\lor\dotsb\lor F_{k+1}.&&\text{[De\u gi\c sme]} \end{align*} \item E\u ger $i>1$ ise, o zaman \begin{align*} \Gamma&\proves F_2\lor\dotsb\lor F_{k+1},&&\text{[$n=k$ durumu]}\\ \Gamma&\proves F_1\lor\dotsb\lor F_{k+1}.&&\text{[Ekleme]} \end{align*} \end{compactitem} \item[$\bm{m>2}$ durumu.] $\ell\geq2$ olsun, ve $m=\ell$ durumunda teoremin ispatland\i\u g\i n\i\ varsayal\i m. $m=\ell+1$ durumunda ispatlayaca\u g\i z. O zaman \begin{equation*} \Gamma\proves F_{k_1}\lor\dotsb\lor F_{k_{\ell+1}} \end{equation*} varsay\i yoruz. Bu durumda, \begin{align*} \Gamma&\proves(F_{k_1}\lor F_{k_2})\lor\dotsb\lor F_{k_{\ell+1}},&&\text{[Birle\c sme]}\\ \Gamma&\proves(F_{k_1}\lor F_{k_2})\lor F_1\lor\dotsb\lor F_n,&&\text{[$m=\ell$ durumu]}\\ \Gamma&\proves(F_1\lor\dotsb\lor F_n)\lor F_{k_1}\lor F_{k_2},&&\text{[De\u gi\c sme]}\\ \Gamma&\proves((F_1\lor\dotsb\lor F_n)\lor F_{k_1})\lor F_{k_2},&&\text{[Birle\c sme]}\\ \Gamma&\proves((F_1\lor\dotsb\lor F_n)\lor F_{k_1})\lor F_1\lor\dotsb\lor F_n,&&\text{[$m=2$ durumu]}\\ \Gamma&\proves(F_1\lor\dotsb\lor F_n)\lor(F_1\lor\dotsb\lor F_n)\lor F_{k_1},&&\text{[De\u gi\c sme]}\\ \Gamma&\proves((F_1\lor\dotsb\lor F_n)\lor F_1\lor\dotsb\lor F_n)\lor F_{k_1},&&\text{[Birle\c sme]}\\ \Gamma&\proves((F_1\lor\dotsb\lor F_n)\lor F_1\lor\dotsb\lor F_n)&&\\ &\qquad\qquad\lor(F_1\lor\dotsb\lor F_n)\lor F_1\lor\dotsb\lor F_n,&&\text{[$m=2$ durumu]}\\ \Gamma&\proves(F_1\lor\dotsb\lor F_n)\lor F_1\lor\dotsb\lor F_n,&&\text{[Daralma]}\\ \Gamma&\proves F_1\lor\dotsb\lor F_n.&&\text{[Daralma]}\qedhere \end{align*} \end{asparadesc} \end{proof} $P$, herhangi bir \"onerme de\u gi\c skeni olsun. $P$ ve $\lnot P$ form\"ullerine \textbf{harf{}i} denir. \begin{theorem}\label{th:eb} $n$, bir say\i\ olsun, ve her $k$ i\c cin, $1\leq k\leq n$ ise, $F_k$ bir harf{}i olsun. E\u ger \begin{equation*} \models F_1\lor\dotsb\lor F_n \end{equation*} ise, o zaman $1\leq i\leq n$ ile $1\leq j\leq n$ ko\c sullar\i n\i\ sa\u glayan bir $i$ ve $j$ i\c cin $F_i$ form\"ul\"u, $\lnot F_j$ form\"ul\"ud\"ur. \end{theorem} \begin{proof} \cexercise. %Al\i\c st\i rma. \end{proof} \begin{theorem}\label{th:2} Her $n$ say\i s\i\ i\c cin, $n\geq2$ ise, ve $\models F_1\lor\dotsb\lor F_n$ ise, o zaman \begin{equation*} \proves F_1\lor\dotsb\lor F_n. \end{equation*} \end{theorem} \begin{proof} $n\geq2$ ve $\models F_1\lor\dotsb\lor F_n$ varsay\i yoruz. En basit durumda, her $F_k$ bir harf{}idir. Bu durumda, \ref{th:eb} numaral\i\ Teoreme g\"ore, bir $i$ ve $j$ i\c cin, $F_i$, $\lnot F_j$ form\"ul\"ud\"ur. O zaman \begin{align*} &\proves F_i\lor F_j,&&\text{[aksiyom]}\\ &\proves F_1\lor\dotsb\lor F_n.&&\text{[Teorem~\ref{th:gen}]} \end{align*} \c Simdi, bir $k$ i\c cin, $F_k$ form\"ul\"u harf{}i olmas\i n. \ref{th:gen} numaral\i\ Teorem sayesinde, $k=1$ varsayabiliriz. \"U\c c tane durum var. Her bir durumda, daha basit durumlar\i n ispatland\i\u g\i n\i\ varsayabiliriz. \begin{asparadesc} \item[$\bm{F_1}$, bir $\bm{\lnot\lnot G}$ form\"ul\"uyse,] $\models G\lor F_2\lor\dotsb\lor F_n$, dolay\i s\i yla \begin{align*} &\proves G\lor F_2\lor\dotsb\lor F_n,&&\text{[daha basit durum]}\\ &\proves F_1\lor\lnot G,&&\text{[aksiyom]}\\ &\proves\lnot G\lor F_1,&&\text{[De\u gi\c sme]}\\ &\proves(F_2\lor\dotsb\lor F_n)\lor F_1,&&\text{[Kesme]}\\ &\proves F_1\lor\dotsb\lor F_n.&&\text{[De\u gi\c sme]} \end{align*} \item[$\bm{F_1}$, bir $\bm{\lnot(G\lor H)}$ form\"ul\"uyse,] $\models\lnot G\lor F_2\lor\dotsb\lor F_n$ ve $\models\lnot H\lor F_2\lor\dotsb\lor F_n$, dolay\i s\i yla \begin{align*} &\proves\lnot G\lor F_2\lor\dotsb\lor F_n,&&\text{[daha basit durum]}\\ &\proves F_1\lor G\lor H,&&\text{[aksiyom]}\\ &\proves G\lor H\lor F_1,&&\text{[Teorem \ref{th:gen}]}\\ &\proves(H\lor F_1)\lor F_2\lor\dotsb\lor F_n,&&\text{[Kesme]}\\ &\proves(F_2\lor\dotsb\lor F_n)\lor H\lor F_1,&&\text{[De\u gi\c sme]}\\ &\proves H\lor(F_2\lor\dotsb\lor F_n)\lor F_1,&&\text{[Teorem \ref{th:gen}]}\\ &\proves\lnot H\lor F_2\lor\dotsb\lor F_n,&&\text{[daha basit durum]}\\ &\proves((F_2\lor\dotsb\lor F_n)\lor F_1)\lor F_2\lor\dotsb\lor F_n,&&\text{[Kesme]}\\ &\proves(F_2\lor\dotsb\lor F_n)\lor(F_2\lor\dotsb\lor F_n)\lor F_1,&&\text{[De\u gi\c sme]}\\ &\proves F_1\lor\dotsb\lor F_n.&&\text{[Teorem \ref{th:gen}]} \end{align*} \item[$\bm{F_1}$, bir $\bm{G\lor H}$ form\"ul\"ud\"uyse,] $\models G\lor H\lor F_2\lor\dotsb\lor F_n$, dolay\i s\i yla \begin{align*} &\proves G\lor H\lor F_2\lor\dotsb\lor F_n,&&\text{[daha basit durum]}\\ &\proves F_2\lor\dotsb\lor F_n\lor F_1,&&\text{[Teorem \ref{th:gen}]}\\ &\proves F_1\lor\dotsb\lor F_n.&&\text{[Teorem \ref{th:gen}]}\qedhere \end{align*} \end{asparadesc} \end{proof} \begin{theorem}[Totoloji] $\models F$ ise $\proves F$. \end{theorem} \begin{proof} $\models F$ ise, o zaman \begin{equation*} \models F\lor F, \end{equation*} dolay\i s\i yla \begin{align*} &\proves F\lor F,&&\text{[Teorem~\ref{th:2}]}\\ &\proves F.&&\text{[Daralma]}\qedhere \end{align*} \end{proof} \begin{theorem}[Ay\i rma] $\Gamma\proves F$ ile $\Gamma\proves\lnot F\lor G$ ise $\Gamma\proves G$. \end{theorem} \begin{proof} $\Gamma\proves F$ ile $\Gamma\proves\lnot F\lor G$ varsayal\i m. O zaman \begin{align*} \Gamma&\proves G\lor F,&&\text{[Ekleme]}\\ \Gamma&\proves F\lor G,&&\text{[De\u gi\c sme]}\\ \Gamma&\proves G\lor G,&&\text{[Kesme]}\\ \Gamma&\proves G.&&\text{[Daralma]}\qedhere \end{align*} \end{proof} \begin{theorem}[$\bd2$ dizgesinin taml\i\u g\i] $\Gamma\models F$ ise $\Gamma\proves F$. \end{theorem} \begin{proof} $\Gamma\models F$ varsayal\i m. T\i k\i zl\i k Teoremi sayesinde $\Gamma$ k\"umesinin bir $\{G_1\dots,G_n\}$ alt k\"umesi i\c cin $\{G_1\dots,G_n\}\models F$. O zaman \begin{equation*} \models\lnot G_1\lor\dotsb\lor\lnot G_n\lor F, \end{equation*} dolay\i s\i yla \begin{align*} &\proves \lnot G_1\lor\dotsb\lor\lnot G_n\lor F,&&\text{[Totoloji Teoremi]}\\ \Gamma&\proves \lnot G_1\lor\dotsb\lor\lnot G_n\lor F,&&\\ \Gamma&\proves G_1,&&\\ \Gamma&\proves\lnot G_2\lor\dotsb\lor\lnot G_n\lor F,&&\text{[Ay\i rma]}\\ &\makebox[3.6cm]{\dotfill},&&\\ \Gamma&\proves F.&&\qedhere \end{align*} \end{proof} %\bibliographystyle{amsplain} %\bibliography{../references} %\bibliography{../Dropbox/Public/references} \def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$} \providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace} \providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR } % \MRhref is called by the amsart/book/proc definition of \MR. \providecommand{\MRhref}[2]{% \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2} } \providecommand{\href}[2]{#2} \begin{thebibliography}{10} \bibitem{Burris} Stanley~N. Burris, \emph{Logic for mathematics and computer science}, Prentice Hall, Upper Saddle River, New Jersey, USA, 1998. \bibitem{MR18:631a} Alonzo Church, \emph{Introduction to mathematical logic. {V}ol. {I}}, Princeton University Press, Princeton, N.~J., 1956. \MR{18,631a} \bibitem{Demirtas} Abdurrahman Demirta{\c s}, \emph{Matematik s{\"o}zl{\"u}{\u g}{\"u}}, Bilim Teknik K{\"u}lt{\"u}r Yay{\i}nlar{\i}, Ankara, 1986. \bibitem{MTS} Teo Gr{\"u}nberg and Adnan Onart, \emph{Mant{\i}k terimleri s{\"o}zl{\"u}{\u g}{\"u}}, T{\"u}rk Dil Kurumu Yay{\i}nlar{\i}, Ankara, 1976. \bibitem{Nesin-OM} Ali Nesin, \emph{{\"O}nermeler mant{\i}{\u g}{\i}}, Bilgi {\"U}niversitesi Yay{\i}nlar{\i}, Ekim 2001. \bibitem{MR1200456} Proclus, \emph{A commentary on the first book of {E}uclid's \emph{{E}lements}}, Princeton Paperbacks, Princeton University Press, Princeton, NJ, 1992, Translated from the Greek and with an introduction and notes by Glenn R. Morrow, Reprint of the 1970 edition, With a foreword by Ian Mueller. \MR{MR1200456 (93k:01008)} \bibitem{MR1809685} Joseph~R. Shoenfield, \emph{Mathematical logic}, Association for Symbolic Logic, Urbana, IL, 2001, reprint of the 1973 second printing. \MR{MR1809685 (2001h:03003)} \bibitem{Struik-TR} Dirk Struik, \emph{K{\i}sa matematik tarihi}, Sarmal Yay\i nevi, {\.I}stanbul, 1996, T{\"u}rk{\c c}esi: Y{\i}ld{\i}z Silier. \bibitem{Struik} Dirk~J. Struik, \emph{A concise history of modern mathematics}, fourth revised ed., Dover, New York, 1987. \bibitem{PM} Alfred~North Whitehead and Bertrand Russell, \emph{Principia mathematica}, vol.~I, University Press, Cambridge, 1910. \end{thebibliography} \end{document}