Many-valued logics

Three-valued Logics

content/many-valued-logic/three-valued-logics/three-valued-logics.tex

% Part: many-valued-logic% Chapter: three-valued-logics\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{mvl}{thr}{Three-valued Logics}\olimport{introduction}\olimport{lukasiewicz}\olimport{kleene}\olimport{goedel}\olimport{multiple-designation}\OLEndChapterHook\end{document}

content/many-valued-logic/three-valued-logics/introduction.tex

% Part: many-valued-logic% Chapter: three-valued-logics% Section: introduction\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{thr}{int}\olsection{Introduction}If we just add one more value~$\Undef$ to $\True$ and $\False$, we get athree-valued logic. Even though there is only one more truth value,the possibilities for defining the truth-functions for $\lnot$,$\land$, $\lor$, and $\lif$ are quite numerous. Then a logic might useany combination of these truth functions, and you also have a choiceof making only $\True$ designated, or both $\True$ and~$\Undef$.We present here a selection of the most well-known three-valuedlogics, their motivations, and some of their properties.\end{document}

content/many-valued-logic/three-valued-logics/lukasiewicz.tex

% Part: many-valued-logic% Chapter: three-valued-logics% Section: lukasiewicz\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{thr}{luk}\olsection{\L ukasiewicz logic}One of the first published, worked out proposals for a many-valuedlogic is due to the Polish philosopher Jan \L ukasiewicz in 1921.  \Lukasiewicz was motivated by Aristotle's sea battle problem: It seemsthat, \emph{today}, the sentence ``There will be a sea battletomorrow'' is neither true nor false: its truth value is not yetsettled.  \L ukasiewicz proposed to introduce a third truth value,to such ``future contingent'' sentences.\begin{quote}I can assume without contradiction that my presence in Warsaw at acertain moment of next year, e.g., at noon on 21 December, is at thepresent time determined neither positively nor negatively. Hence it ispossible, but not necessary, that I shall be present in Warsaw at thegiven time. On this assumption the proposition ``I shall be in Warsawat noon on 21 December of next year,'' can at the present time beneither true nor false. For if it were true now, my future presence inWarsaw would have to be necessary, which is contradictory to theassumption. If it were false now, on the other hand, my futurepresence in Warsaw would have to be impossible, which is alsocontradictory to the assumption. Therefore the proposition consideredis at the moment neither true nor false and must possess a thirdvalue, different from ``0'' or falsity and ``1'' or truth. This valuewe can designate by ``$\frac{1}{2}$.'' It represents ``the possible,''and joins ``the true'' and ``the false'' as a third value.\end{quote}We will use $\Undef$ for \L ukasiewicz's third truthvalue.\footnote{\L ukasiewicz here uses ``possible'' in a way that isuncommon today, namely to mean possible but not necessary.}The truth functions for the connectives $\lnot$, $\land$, and $\lor$are easy to determine on this interpretation: the negation of a futurecontingent sentence is also a future contingent sentence, so$\tf{\lnot}(\Undef) = \Undef$.  If one conjunct of aconjunction is undetermined and the other is true, the conjunction isalso undetermined---after all, depending on how the future contingentconjunct turns out, the conjunction might turn out to be true, and itmight turn out to be false. So \[    \tf{\land}(\True, \Undef) =\tf{\land}(\Undef, \True) =\Undef.\]If the other conjunct is false, however, it cannotturn out true, so \[\tf{\land}(\False, \Undef) =\tf{\land}(\False, \Undef) = \False.\]The other values (if the arguments are settled truth values, $\True$or $\False$, are like in classical logic.For the conditional, the situation is a little trickier. Suppose $q$is a future contingent statement. If $p$ is false, then $p \lif q$will be true, regardless of how $q$ turns out, so we should set$\tf{\lif}(\False, \Undef) = \True$. And if $p$ is true, then$q \lif p$ will be true, regardless of what $q$ turns out to be, so$\tf{\lif}(\Undef, \True) = \True$. If $p$ is true, then $p\lif q$ might turn out to be true or false, so $\tf{\lif}(\True,\Undef) = \Undef$. Similarly, if $p$ is false, then $q\lif p$ might turn out to be true or false, so$\tf{\lif}(\Undef, \False) = \Undef$. This leaves thecase where $p$ and $q$ are both future contingents. On the basis ofthe motivation, we should really assign $\Undef$ in this case.However, this would make $!A \lif !A$ \emph{not} a tautology. \Lukasiewicz had not trouble giving up $!A \lor \lnot !A$ and $\lnot(!A\land \lnot !A)$, but balked at giving up $!A \lif !A$. So hestipulated $\tf{\lif}(\Undef, \Undef) =\True$.\begin{defn}\ollabel{def:lukasiewicz}Three-valued \L ukasiewicz logic is defined using the matrix:\begin{enumerate}  \item The standard propositional language $\Lang L_0$ with  $\lnot$, $\land$, $\lor$, $\lif$.  \item The set of truth values $V = \{\True, \Undef, \False\}$.  \item $\True$ is the only designated value, i.e., $V^+ = \{\True\}$.  \item Truth functions are given by the following tables:  \begin{center}    \begin{tabular}{c|c}       $\tf{\lnot}$ & \\       \hline        $\True$ & $\False$ \\       $\Undef$ & $\Undef$ \\      $\False$ & $\True$     \end{tabular}    \quad    \begin{tabular}{c|ccc}       $\tf{\land}[\LogLuk[3]]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\Undef$ & $\False$ \\       $\Undef$ & $\Undef$ & $\Undef$ & $\False$\\       $\False$ & $\False$ & $\False$ & $\False$     \end{tabular}    \\[2ex]    \begin{tabular}{c|ccc}       $\tf{\lor}[\LogLuk[3]]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\True$ & $\True$ \\       $\Undef$ & $\True$ & $\Undef$ & $\Undef$ \\      $\False$ & $\True$ & $\Undef$ & $\False$     \end{tabular}    \quad    \begin{tabular}{c|ccc}       $\tf{\lif}[\LogLuk[3]]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\Undef$ & $\False$ \\       $\Undef$ & $\True$ & $\True$ & $\Undef$  \\       $\False$ & $\True$ & $\True$ & $\True$     \end{tabular}  \end{center} \end{enumerate}\end{defn}As can easily be seen, any !!{formula}~$!A$ containing only $\lnot$,$\land$, and $\lor$ will take the truth value~$\Undef$ if allits !!{propositional variable}s are assigned~$\Undef$. So forinstance, the classical tautologies $p \lor \lnot p$ and $\lnot(p\land \lnot p)$ are not tautologies in $\LogLuk[3]$, since $\pValue{v}(!A)= \Undef$ whenever $\pAssign v(p) = \Undef$.On !!{valuation}s where $\pAssign v(p) = \True$ or $\False$, $\pValuev(!A)$ will coincide with its classical truth value.\begin{prop}  If $\pAssign v(p) \in \{\True, \False\}$ for all $p$ in~$!A$, then  $\pValue v(!A)[\LogLuk[3]] = \pValue v(!A)[\LogCL]$.\end{prop}\begin{prob}\label{mvl:thr:luk:prob:luk-iff} Suppose we define  $\pValue v(!A \liff !B) = \pValue v((!A \lif !B) \land (!B \lif  !A))$ in~$\LogLuk[3]$. What truth table would $\liff$ have?\end{prob}Many classical tautologies \emph{are} also tautologies in \LogLuk[3],e.g, $\lnot p \lif (p \lif q)$. Just like in classical logic, we canuse truth tables to verify this:\begin{center}\begin{tabular}{cc|cccccc}  $p$ & $q$ & $\lnot$ & $p$ & $\lif$ & $\smash{(}p$ & $\lif$ & $q\smash{)}$ \\ \hline  \True & \True & \False & \True & \True & \True & \True & \True \\  \True & \Undef & \False & \True & \True & \True & \Undef & \Undef \\  \True & \False & \False & \True & \True & \True & \False & \False \\  \Undef & \True & \Undef & \Undef & \True & \Undef & \True & \True \\  \Undef & \Undef & \Undef & \Undef & \True & \Undef & \True & \Undef \\  \Undef & \False & \Undef & \Undef & \True & \Undef & \Undef & \False \\  \False & \True & \True & \False & \True & \False & \True & \True \\  \False & \Undef & \True & \False & \True & \False & \True & \Undef \\  \False & \False & \True & \False & \True & \False & \True & \False \\  \end{tabular}\end{center}\begin{prob}  Show that the following are tautologies in \LogLuk[3]:  \begin{enumerate}    \item $p \lif (q \lif p)$    \item\label{mvl:thr:luk:prob:luk-taut-2} $\lnot(p \land q) \liff (\lnot p \lor \lnot q)$    \item\label{mvl:thr:luk:prob:luk-taut-3} $\lnot(p \lor q) \liff (\lnot p \land \lnot q)$  \end{enumerate}  (In \olref[mvl][thr][luk]{prob:luk-taut-2} and  \olref[mvl][thr][luk]{prob:luk-taut-3}, take $!A \liff !B$ as an  abbreviation for $(!A \lif !B) \land (!B \lif !A)$, or refer to your  solution to \olref[mvl][thr][luk]{prob:luk-iff}.)\end{prob}\begin{prob}  Show that the following classical tautologies are not tautologies in~\LogLuk[3]:  \begin{enumerate}    \item $(\lnot p \land p) \lif q)$    \item $((p \lif q) \lif p) \lif p$    \item $(p \lif (p \lif q)) \lif (p \lif q)$  \end{enumerate}\end{prob}One might therefore perhaps think that although not all classicaltautologies are tautologies in~$\LogLuk[3]$, they should at least takeeither the value~$\True$ or the value~$\Undef$ on every!!{valuation}. This is not the case. A counterexample is given by\[  \lnot(p \lif \lnot p) \lor \lnot(\lnot p \lif p)\]which is $\False$ if $p$ is~$\Undef$.\begin{prob}  Which of the following relations hold in \L ukasiewicz logic? Give a truth table for each.  \begin{enumerate}    \item $p, p \lif q \Entails q$    \item $\lnot\lnot p \Entails p$    \item $p \land q \Entails p$    \item $p \Entails p \land p$    \item $p \Entails p \lor q$  \end{enumerate}\end{prob}\L ukasiewicz hoped to build a logic of possibility on the basis of histhree-valued system, by introducing a one-place connective $\Diamond!A$ (for ``$!A$ is possible'') and a corresponding $\Box !A$ (for ``$!A$is necessary''):\begin{center}  \begin{tabular}{c|c}     $\tf{\Diamond}$ & \\     \hline      $\True$ & $\True$ \\     $\Undef$ & $\True$ \\    $\False$ & $\False$   \end{tabular}  \quad  \begin{tabular}{c|c}     $\tf{\Box}$ & \\     \hline      $\True$ & $\True$ \\     $\Undef$ & $\False$ \\    $\False$ & $\False$   \end{tabular}\end{center}In other words, $p$ is possible iff it is not already settled as false;and $p$ is necessary iff it is already settled as true.\begin{prob}  Show that $\Box p \liff \lnot\Diamond \lnot p$ and $\Diamond p \liff  \lnot \Box \lnot p$ are tautologies in~\LogLuk[3], extended with the  truth tables for $\Box$ and~$\Diamond$.\end{prob}However, the shortcomings of this proposed modal logic soon becameevident: However things turn out, $p \land \lnot p$ can never turn outto be true. So even if it is not now settled (and thereforeundetermined), it should count as impossible, i.e., $\lnot \Diamond(p\land \lnot p)$ should be a tautology. However, if $\pAssign v(p) =\Undef$, then $\pValue v(\lnot \Diamond(p \land \lnot p)) =\Undef$. Although \L ukasiewicz was correct that two truthvalues will not be enough to accommodate modal distinctions such aspossiblity and necessity, introducing a third truth value is also notenough.\end{document}

content/many-valued-logic/three-valued-logics/kleene.tex

% Part: many-valued-logic% Chapter: three-valued-logics% Section: kleene\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{thr}{skl}\olsection{Kleene logics}Stephen Kleene introduced two three-valued logics motivated by a logicin which truth values are thought of the outcomes of computationalprocedures: a procedure may yield $\True$ or $\False$, but it may alsofail to terminate.  In that case the corresponding truth value isundefined, represented by the truth value~$\Undef$.To compute the negation of a proposition~$!A$, you would first computethe value of~$!A$, and then return the opposite of the result.  If thecomputation of $!A$ does not terminate, then the entire procedure doesnot either: so the negation of $\Undef$ is $\Undef$.To compute a conjunction $!A \land !B$, there are two options: one canfirst compute~$!A$, then $!B$, and then the result would be $\True$ ifthe outcome of both is~$\True$, and $\False$ otherwise.  If eithercomputation fails to halt, the entire procedure does as well. So inthis case, the if one conjunct is undefined, the conjunction is aswell.  The same goes for disjunction.However, if we can evaluate $!A$ and $!B$ in parallel, we can do better.Then, if one of the two procedures halts and returns $\False$, we canstop, as the answer must be false.  So in that case a conjunction withone false conjunct is false, even if the other conjunct is undefined.Similarly, when computing a disjunction in parallel, we can stop oncethe procedure for one of the two disjuncts has returned true: then thedisjunction must be true. So in this case we can know what the outcomeof a compound claim is, even if one of the components is undefined. Onthis interpretation, we might read $\Undef$ as ``unknown'' rather than``undefined.''The two interpretations give rise to Kleene's strong and weak logic.The conditional is defined as equivalent to $\lnot !A \lor !B$.\begin{defn}\emph{Strong Kleene logic}~$\LogKs$ is defined using the matrix:\begin{enumerate}  \item The standard propositional language $\Lang L_0$ with  $\lnot$, $\land$, $\lor$, $\lif$.  \item The set of truth values $V = \{\True, \Undef, \False\}$.  \item $\True$ is the only designated value, i.e., $V^+ = \{\True\}$.  \item Truth functions are given by the following tables:  \begin{center}    \begin{tabular}{c|c}       $\tf{\lnot}$ & \\       \hline        $\True$ & $\False$ \\       $\Undef$ & $\Undef$ \\      $\False$ & $\True$     \end{tabular}    \quad    \begin{tabular}{c|ccc}       $\tf{\land}[\LogKs]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\Undef$ & $\False$ \\       $\Undef$ & $\Undef$ & $\Undef$ & $\False$\\       $\False$ & $\False$ & $\False$ & $\False$     \end{tabular}    \\[2ex]    \begin{tabular}{c|ccc}       $\tf{\lor}[\LogKs]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\True$ & $\True$ \\       $\Undef$ & $\True$ & $\Undef$ & $\Undef$ \\      $\False$ & $\True$ & $\Undef$ & $\False$     \end{tabular}    \quad    \begin{tabular}{c|ccc}       $\tf{\lif}[\LogKs]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\Undef$ & $\False$ \\       $\Undef$ & $\True$ & $\Undef$ & $\Undef$  \\       $\False$ & $\True$ & $\True$ & $\True$     \end{tabular}  \end{center} \end{enumerate}\end{defn}\begin{defn}\emph{Weak Kleene logic}~$\LogKw$ is defined using the matrix:\begin{enumerate}  \item The standard propositional language $\Lang L_0$ with  $\lnot$, $\land$, $\lor$, $\lif$.  \item The set of truth values $V = \{\True, \Undef, \False\}$.  \item $\True$ is the only designated value, i.e., $V^+ = \{\True\}$.  \item Truth functions are given by the following tables:  \begin{center}    \begin{tabular}{c|c}       $\tf{\lnot}$ & \\       \hline        $\True$ & $\False$ \\       $\Undef$ & $\Undef$ \\      $\False$ & $\True$     \end{tabular}    \quad    \begin{tabular}{c|ccc}       $\tf{\land}[\LogKw]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\Undef$ & $\False$ \\       $\Undef$ & $\Undef$ & $\Undef$ & $\Undef$\\       $\False$ & $\False$ & $\Undef$ & $\False$     \end{tabular}    \\[2ex]    \begin{tabular}{c|ccc}       $\tf{\lor}[\LogKw]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\Undef$ & $\True$ \\       $\Undef$ & $\Undef$ & $\Undef$ & $\Undef$ \\      $\False$ & $\True$ & $\Undef$ & $\False$     \end{tabular}    \quad    \begin{tabular}{c|ccc}       $\tf{\lif}[\LogKw]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\Undef$ & $\False$ \\       $\Undef$ & $\Undef$ & $\Undef$ & $\Undef$  \\       $\False$ & $\True$ & $\Undef$ & $\True$     \end{tabular}  \end{center} \end{enumerate}\end{defn}\begin{prop}  $\LogKs$ and $\LogKw$ have no tautologies.\end{prop}\begin{proof}  If $\pAssign v(p) = \Undef$ for all !!{propositional variable}s~$p$,  then any formula~$!A$ will have truth value~$\pValue v(!A) =  \Undef$, since  \[    \tf{\lnot}(\Undef) = \tf{\lor}(\Undef, \Undef) = \tf{\land}(\Undef,  \Undef) = \tf{\lif}(\Undef, \Undef) = \Undef  \]  in both logics. As $\Undef \notin V^+$ for either $\LogKs$ or  $\LogKw$, on this !!{valuation}, $!A$ will not be designated.\end{proof}Although both weak and strong Kleene logic have no tautologies, theyhave non-trivial consequence relations. \begin{prob}  Which of the following relations hold in (a) strong and  (b) weak Kleene logic? Give a truth table for each.  \begin{enumerate}    \item $p, p \lif q \Entails q$    \item $p \lor q, \lnot p \Entails q$    \item $p \land q \Entails p$    \item $p \Entails p \land p$    \item $p \Entails p \lor q$  \end{enumerate}\end{prob}Dmitry Bochvar interpreted $\Undef$ as ``meaningless'' and attemptedto use it to solve paradoxes such as the Liar paradox by stipulatingthat paradoxical sentences take the value~$\Undef$. He introduced alogic which is essentially weak Kleene logic extended by additionalconnectives, two of which are ``external negation'' and the ``isundefined'' operator:\begin{center}  \begin{tabular}{c|c}     $\tf{\sim}$ & \\     \hline      $\True$ & $\False$ \\     $\Undef$ & $\True$ \\    $\False$ & $\True$   \end{tabular}\quad  \begin{tabular}{c|c}     $\tf{+}$ & \\     \hline      $\True$ & $\False$ \\     $\Undef$ & $\True$ \\    $\False$ & $\False$   \end{tabular}\end{center}\begin{prob}  Can you define $\sim$ in Bochvar's logic in terms of $\lnot$  and~$+$, i.e., find !!a{formula} with only the !!{propositional  variable}~$p$ and not involving $\sim$ which always takes the same  truth value as~$\mathord{\sim}p$?  Give a truth table to show you're  right.\end{prob}\end{document}

content/many-valued-logic/three-valued-logics/goedel.tex

% Part: many-valued-logic% Chapter: three-valued-logics% Section: goedel\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{thr}{god}\olsection{G\"odel logics}Kurt G\"odel introduced a sequence of $n$-valued logics that eachcontain all !!{formula}s valid in intuitionistic logic, and arecontained in classical logic.  Here is the first interesting one:\begin{defn}\ollabel{defn:goedel}\emph{$3$-valued G\"odel logic}~$\LogGod$ is defined using the matrix:\begin{enumerate}  \item The standard propositional language $\Lang L_0$ with  $\lfalse$, $\lnot$, $\land$, $\lor$, $\lif$.  \item The set of truth values $V = \{\True, \Undef, \False\}$.  \item $\True$ is the only designated value, i.e., $V^+ = \{\True\}$.  \item For $\lfalse$, we have $\tf{\lfalse} = \False$. Truth  functions for the remaining connectives are given by the following  tables:  \begin{center}    \begin{tabular}{c|c}       $\tf{\lnot}[\LogGod]$ & \\       \hline        $\True$ & $\False$ \\       $\Undef$ & $\False$ \\      $\False$ & $\True$     \end{tabular}    \quad    \begin{tabular}{c|ccc}       $\tf{\land}[\LogGod]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\Undef$ & $\False$ \\       $\Undef$ & $\Undef$ & $\Undef$ & $\False$\\       $\False$ & $\False$ & $\False$ & $\False$     \end{tabular}    \\[2ex]    \begin{tabular}{c|ccc}       $\tf{\lor}[\LogGod]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\True$ & $\True$ \\       $\Undef$ & $\True$ & $\Undef$ & $\Undef$ \\      $\False$ & $\True$ & $\Undef$ & $\False$     \end{tabular}    \quad    \begin{tabular}{c|ccc}       $\tf{\lif}[\LogGod]$ & $\True$ & $\Undef$ & $\False$ \\       \hline       $\True$ & $\True$ & $\Undef$ & $\False$ \\       $\Undef$ & $\True$ & $\True$ & $\False$  \\       $\False$ & $\True$ & $\True$ & $\True$     \end{tabular}  \end{center} \end{enumerate}\end{defn}You'll notice that the truth tables for $\land$ and~$\lor$ are thesame as in \L ukasiewicz and strong Kleene logic, but the truth tablesfor $\lnot$ and~$\lif$ differ for each. In G\"odel logic,$\tf{\lnot}(\Undef) = \False$. In contrast to \L ukasiewicz logic andKleene logic, $\tf{\lif}(\Undef, \False) = \False$; in contrast toKleene logic (but as in \L ukasiewicz logic), $\tf{\lif}(\Undef,\Undef) = \True$.As the connection to intuitionistic logic alluded to above suggests,$\LogGod[3]$ is close to intuitionistic logic. All intuitionistictruths are tautologies in~$\LogGod[3]$, and many classical tautologiesthat are not valid intuitionistically also fail to be tautologiesin~$\LogGod[3]$. For instance, the following are not tautologies:\begin{align*}  & p \lor \lnot p && (p \lif q) \lif (\lnot p \lor q) \\  & \lnot\lnot p \lif p && \lnot(\lnot p \land \lnot q) \lif (p \lor q) \\  & ((p \lif q) \lif p) \lif p && \lnot(p \lif q) \lif (p \land \lnot q)\end{align*}However, not every tautology of $\LogGod[3]$ is alsointuitionistically valid, e.g., $\lnot\lnot p \lor \lnot p$ or $(p\lif q) \lor (q \lif p)$.\begin{prob}  Give truth tables to show that the following are tautologies  of~$\LogGod[3]$:  \begin{align*}    & \lnot\lnot p \lor \lnot p\\    & (p \lif q) \lor (q \lif p) \\    & \lnot(p \land q) \lif (\lnot p \lor \lnot q) \\    & (p \lif q) \lor (q \lif r) \lor (r \lif s)  \end{align*}\end{prob}\begin{prob}  Give truth tables that show that the following are not tautologies  of~$\LogGod[3]$  \begin{align*}    & (p \lif q) \lif (\lnot p \lor q) \\    & \lnot(\lnot p \land \lnot q) \lif (p \lor q) \\    & ((p \lif q) \lif p) \lif p \\    & \lnot(p \lif q) \lif (p \land \lnot q)  \end{align*}\end{prob}\begin{prob}  Which of the following relations hold in G\"odel logic? Give a truth table for each.  \begin{enumerate}    \item $p, p \lif q \Entails q$    \item $p \lor q, \lnot p \Entails q$    \item $p \land q \Entails p$    \item $p \Entails p \land p$    \item $p \Entails p \lor q$  \end{enumerate}\end{prob}\end{document}

content/many-valued-logic/three-valued-logics/multiple-designation.tex

% Part: many-valued-logic% Chapter: three-valued-logics% Section: multiple-designation\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{thr}{mul}\olsection{Designating not just $\True$}So far the logics we've seen all had the set of designated truthvalues $V^+ = \{\True\}$, i.e., something counts as true iff its truthvalue is~$\True$.  But one might also count something as true if it'sjust not~$\False$. Then one would get a logic by stipulating in thematrix, e.g., that $V^+ = \{\True, \Undef\}$.\begin{defn}The \emph{logic of paradox}~$\LogLP$ is defined using the matrix:\begin{enumerate}  \item The standard propositional language $\Lang L_0$ with  $\lnot$, $\land$, $\lor$, $\lif$.  \item The set of truth values $V = \{\True, \Undef, \False\}$.  \item $\True$ and $\Undef$ are designated, i.e., $V^+ = \{\True, \Undef\}$.  \item Truth functions are the same as in strong Kleene logic.\end{enumerate}\end{defn}\begin{defn}Halld\'en's \emph{logic of nonsense}~$\LogHal$ is defined using the matrix:\begin{enumerate}  \item The standard propositional language $\Lang L_0$ with  $\lnot$, $\land$, $\lor$, $\lif$ and a $1$-place connective~$+$.  \item The set of truth values $V = \{\True, \Undef, \False\}$.  \item $\True$ and $\Undef$ are designated, i.e., $V^+ = \{\True, \Undef\}$.  \item Truth functions are the same as weak Kleene logic, plus the  ``is meaningless'' operator:  \begin{center}    \begin{tabular}{c|c}     $\tf{+}$ & \\     \hline      $\True$ & $\False$ \\     $\Undef$ & $\True$ \\    $\False$ & $\False$     \end{tabular}  \end{center}\end{enumerate}\end{defn}By contrast to the Kleene logics with which they share truth tables,these \emph{do} have tautologies. \begin{prop}\ollabel{prop:LP-taut-CL} The tautologies of $\LogLP$  are  the same as the tautologies of classical propositional logic.\end{prop}\begin{proof}  By \olref[syn][sub]{prop:mvl-cl}, if $\Entails[\LogLP] !A$ then  $\Entails[\LogCL] !A$. To show the reverse, we show that if there is  !!a{valuation}~$\pAssign v\colon \PVar \to \{\False, \True,  \Undef\}$ such that $\pValue v(!A)[\LogKs] = \False$ then there is  !!a{valuation}~$\pAssign {v'}\colon \PVar \to \{\False, \True\}$  such that $\pValue {v'}(!A)[\LogCL] = \False$. This establishes the  result for $\LogLP$, since $\LogKs$ and $\LogLP$ have the same  characteristic truth functions, and $\False$ is the only truth value  of $\LogLP$ that is not designated (that is the only difference  between $\LogLP$ and~$\LogKs$). Thus, if $\Entails/[\LogLP] !A$, for  some !!{valuation}~$\pAssign v$, $\pValue v(!A)[\LogLP] = \pValue  v[\LogKs](!A) = \False$. By the claim we're proving,  $\pValue{v'}[\LogCL](!A) = \False$, i.e., $\Entails/[\LogCL] !A$.    To establish the claim, we first define $\pAssign {v'}$ as  \[    \pAssign {v'}(p) =     \begin{cases}    \True & \text{if } \pAssign {v}(p) \in \{\True, \Undef\}\\    \False & \text{otherwise}  \end{cases}  \]  We now show by induction on $!A$ that (a)~if $\pValue v(!A)[\LogKs]  = \False$ then $\pValue {v'}(!A)[\LogCL] = \False$, and (b)~if  $\pValue v(!A)[\LogKs] = \True$ then $\pValue {v'}(!A)[\LogCL] =  \True$  \begin{enumerate}    \item Induction basis: $!A \ident p$. By    \olref[syn][val]{defn:pValue}, $\pValue v(!A)[\LogKs]    = \pAssign v(p) = \pValue {v'}(!A)[\LogCL]$, which implies both (a)    and~(b).        For the induction step, consider the cases:    \item $!A \ident \lnot !B$.     \begin{enumerate}      \item Suppose $\pValue v(\lnot!B)[\LogKs] = \False$. By the      definition of $\tf{\lnot}[\LogKs]$, $\pValue v(!B)[\LogKs]  =      \True$. By inductive hypothesis, case~(b), we get $\pValue      {v'}(!B)[\LogCL]  = \True$, so $\pValue {v'}(\lnot !B)[\LogCL] = \False$.      \item Suppose $\pValue v(\lnot!B)[\LogKs] = \True$. By the      definition of $\tf{\lnot}[\LogKs]$, $\pValue v(!B)[\LogKs]  =      \False$. By inductive hypothesis, case~(a), we get $\pValue      {v'}(!B)[\LogCL]  = \False$, so $\pValue {v'}(\lnot !B)[\LogCL] = \True$.    \end{enumerate}    \item $!A \ident (!B \land !C)$.    \begin{enumerate}      \item Suppose $\pValue v(!B \land !C)[\LogKs] = \False$. By the      definition of $\tf{\land}[\LogKs]$, $\pValue v(!B)[\LogKs]  =      \False$ or $\pValue v(!B)[\LogKs]  = \False$. By inductive      hypothesis, case~(a), we get $\pValue {v'}(!B)[\LogCL]  = \False$      or $\pValue {v'}(!C)[\LogCL]  = \False$, so $\pValue {v'}(!B \land      !C)[\LogCL] = \False$.      \item Suppose $\pValue v(!B \land !C)[\LogKs] = \True$. By the      definition of $\tf{\land}[\LogKs]$, $\pValue v(!B)[\LogKs]  =      \True$ and $\pValue v(!B)[\LogKs]  = \True$. By inductive      hypothesis, case~(b), we get $\pValue {v'}(!B)[\LogCL]  = \True$      and $\pValue {v'}(!C)[\LogCL]  = \True$, so $\pValue {v'}(!B \land      !C)[\LogCL] = \True$.    \end{enumerate}  \end{enumerate}  The other two cases are similar, and left as exercises. Alternatively,  the proof above establishes the result for all !!{formula}s only  containing $\lnot$ and~$\land$. One may now appeal to the facts that in  both $\LogKs$ and $\LogCL$, for any $\pAssign v$, $\pValue v(!B \lor  !C) = \pValue v(\lnot(\lnot!B \land \lnot !C))$ and $\pValue v(!B \lif  !C) = \pValue v(\lnot(!B \land \lnot !C))$.\end{proof}\begin{prob}  Complete the proof \olref[mvl][thr][mul]{prop:LP-taut-CL}, i.e.,  establish (a) and~(b) for the cases where $!A \ident (!B \lor !C)$  and $!A \ident (!B \lif !C)$.\end{prob}\begin{prob}Prove that every classical tautology is a tautology in~$\LogHal$.\end{prob}Although they have the same tautologies as classical logic, theirconsequence relations are different.  $\LogLP$, for instance, is\emph{paraconsistent} in that $\lnot p, p \Entails/ q$, and so theprinciple of explosion $\lnot !A, !A \Entails !B$ does not hold ingeneral. (It holds for some cases of $!A$ and $!B$, e.g., if $!B$~is atautology.)\begin{prob}  Which of the following relations hold in (a)~$\LogLP$  and in (b)~$\LogHal$? Give a truth table for each.  \begin{enumerate}    \item $p, p \lif q \Entails q$    \item $\lnot q, p \lif q \Entails \lnot p$    \item $p \lor q, \lnot p \Entails q$    \item $\lnot p, p \Entails q$    \item $p \Entails p \lor q$    \item $p \lif q, q\lif r \Entails p \lif r$  \end{enumerate}\end{prob}What if you make $\Undef$ designated in $\LogLuk[3]$?\begin{defn}  The logic \emph{3-valued R-Mingle}~$\LogRM[3]$ is defined using the matrix:  \begin{enumerate}    \item The standard propositional language $\Lang L_0$ with    $\lfalse$, $\lnot$, $\land$, $\lor$, $\lif$.    \item The set of truth values $V = \{\True, \Undef, \False\}$.    \item $\True$ and $\Undef$ are designated, i.e., $V^+ = \{\True, \Undef\}$.    \item Truth functions are the same as \L ukasiewicz logic~$\LogLuk[3]$.  \end{enumerate}\end{defn}\begin{prob}  Which of the following relations hold in $\LogRM[3]$?  \begin{enumerate}    \item $p, p \lif q \Entails q$    \item $p \lor q, \lnot p \Entails q$    \item $\lnot p, p \Entails q$    \item $p \Entails p \lor q$  \end{enumerate}\end{prob}Different truth tables can sometimes generate the same logic(entailment relation) just by changing the designated values.E.g., this happens if in G\"odel logic we take $V^+ = \{\True,\Undef\}$ instead of~$\{\True\}$.\begin{prop}\ollabel{prop:gl-udes}  The matrix with $V = \{\False, \Undef,\True\}$, $V^+=\{\True,  \Undef\}$, and the truth functions of $3$-valued G\"odel logic  defines classical logic.\end{prop}\begin{proof}  Exercise. \end{proof}\begin{prob}  Prove \olref[mvl][thr][mul]{prop:gl-udes} by showing that for the  logic~$\Log L$ defined just like G\"odel logic but with  $V^+=\{\True,\Undef\}$, if $\Gamma \Entails/[\Log L] !B$ then  $\Gamma \Entails/[\LogCL] !B$. Use the ideas of  \olref[mvl][thr][mul]{prop:LP-taut-CL}, except instead of proving  properties (a) and~(b), show that $\pValue v(!A)[\LogGod] = \False$  iff $\pValue {v'}(!A)[\LogCL] = \False$ (and hence that $\pValue  v(!A)[\LogGod] \in \{\True,\Undef\}$ iff $\pValue {v'}(!A)[\LogCL] =  \True$). Explain why this establishes the proposition.\end{prob}\end{document}