Many-valued logics

Syntax and Semantics

content/many-valued-logic/syntax-and-semantics/syntax-and-semantics.tex

% Part: many-valued-logic% Chapter: syntax-and-semantics\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{mvl}{syn}{Syntax and Semantics}\olimport{introduction}\olimport{connectives}\olimport{formulas}\olimport{matrices}\olimport{valuations-sat}\olimport{semantic-notions}\olimport{sublogics}\OLEndChapterHook\end{document}

content/many-valued-logic/syntax-and-semantics/introduction.tex

% Part: many-valued-logic% Chapter: syntax-and-semantics% Section: introduction\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{syn}{int}\olsection{Introduction}In classical logic, we deal  with !!{formula}s that are built from!!{propositional variable}s using the propositional connectives$\lnot$, $\land$, $\lor$, $\lif$, and $\liff$.  When we define asemantics for classical logic, we do so using the two truth values$\True$ and $\False$.  We interpret !!{propositional variable}s in!!a{valuation}~$\pAssign{v}$, which assigns these truth values$\True$, $\False$ to the !!{propositional variable}s. Any!!{valuation} then determines a truth value $\pValue{v}(!A)$ for any!!{formula}~$!A$, and !!^a{formula} is satisfied in!!a{valuation}~$\pAssign{v}$, $\pSat{v}{!A}$, iff $\pValue{v}(!A) =\True$.Many-valued logics are generalizations of classical two-valued logicby allowing more truth values than just $\True$ and $\False$. So inmany-valued logic, !!a{valuation}~$\pAssign{v}$ is a functionassigning to every !!{propositional variable}~$p$ one of a range ofpossible truth values.  We'll generally call the set of allowed truthvalues~$V$.  Classical logic is a many-valued logic where $V =\{\True, \False\}$, and the truth value~$\pValue{v}(!A)$ is computedusing the familiar characteristic truth tables for the connectives.Once we add additional truth values, we have more than one naturaloption for how to compute~$\pValue{v}(!A)$ for the connectives we readas ``and,'' ``or,'' ``not,'' and ``if---then.''  So a many-valuedlogic is determined not just by the set of truth values, but also bythe \emph{truth functions} we decide to use for each connective.  Oncethese are selected for a many-valued logic~$\Log L$, however, thetruth value $\pValue{v}(!A)[\Log L]$ is uniquely determined by thevaluation, just like in classical logic. Many-valued logics, likeclassical logic, are \emph{truth functional}.With this semantic building blocks in hand, we can go on to define theanalogs of the semantic concepts of tautology, entailment, andsatisfiability.  In classical logic, !!a{formula} is a tautology ifits truth value $\pValue{v}(!A) = \True$ for any~$\pAssign{v}$.  Inmany-valued logic, we have to generalize this a bit as well. First ofall, there is no requirement that the set of truth values~$V$contains~$\True$. For instance, some many-valued logics use numbers,such as all rational numbers between $0$ and~$1$ as their set of truthvalues.  In such a case, $1$~usually plays the rule of~$\True$. Inother logics, not just one but several truth values do.  So, werequire that every many-valued logic have a set~$V^+$ of\emph{designated values}.  We can then say that !!a{formula} issatisfied in !!a{valuation}~$\pAssign{v}$, $\pSat{v}{!A}[\Log L]$, iff$\pValue{v}(!A)[\Log L] \in V^+$. !!^a{formula}~$!A$ is a tautology of thelogic, $\Entails[\Log L] !A$, iff $\pValue{v}(!A) \in V^+$ forany~$\pAssign{v}$. And, finally, we say that $!A$ is entailed by a setof !!{formula}s, $\Gamma \Entails[\Log L] !A$, if every !!{valuation} thatsatisfies all the !!{formula}s in~$\Gamma$ also satisfies~$!A$.\end{document}

content/many-valued-logic/syntax-and-semantics/connectives.tex

% Part: many-valued-logic% Chapter: syntax-and-semantics% Section: connectives\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{syn}{con}\olsection{Languages and Connectives}Classical propositional logic, and many other logics, use a set supplyof \emph{propositional constants} and \emph{connectives}. Forinstance, we use the following as primitives:\begin{enumerate}\tagitem{prvFalse}{The propositional constant for !!{falsity}~$\lfalse$.}{}\tagitem{prvTrue}{The propositional constant for !!{truth}~$\ltrue$.}{}\item The logical connectives:  \startycommalist  \iftag{prvNot}{\ycomma $\lnot$ (negation)}{}%  \iftag{prvAnd}{\ycomma $\land$ (conjunction)}{}%  \iftag{prvOr}{\ycomma $\lor$ (disjunction)}{}%  \iftag{prvIf}{\ycomma $\lif$ (!!{conditional})}{}%  \iftag{prvIff}{\ycomma $\liff$ (!!{biconditional})}{}%\end{enumerate}\iftag{defNot,defOr,defAnd,defIf,defIff,defTrue,defFalse,defEx,defAll}{%In addition to the primitive connectives above, we also use symbolsdefined as abbreviations, such as\startycommalist  \iftag{defNot}{\ycomma $\lnot$ (negation)}{}%  \iftag{defAnd}{\ycomma $\land$ (conjunction)}{}%  \iftag{defOr}{\ycomma $\lor$ (disjunction)}{}%  \iftag{defIf}{\ycomma $\lif$ (!!{conditional})}{}%  \iftag{defIff}{\ycomma $\liff$ (!!{biconditional})}{}%  \iftag{defFalse}{\ycomma $\lfalse$ (!!{falsity})}{}%  \iftag{defTrue}{\ycomma $\ltrue$ (!!{truth})}.}{}The same connectives are used in many-valued logics as well. However,it is often useful to include different versions of, say, conjunction,in the same logic, and that would require different symbols to keepthe versions separate. Some many-valued logics also includeconnectives that have no equivalent in classical logic. So, we'll be abit more general than usual.\begin{defn}  A \emph{propositional language} consists of a set $\Lang L$ of  \emph{connectives}. Each connective $\star$ has an \emph{arity}; a  connective of arity~$n$ is said to be \emph{$n$-place.}  Connectives of arity~$0$ are also called \emph{constants};  connectives of arity~$1$ are called \emph{unary}, and connectives of  arity~$2$, \emph{binary}.\end{defn}\begin{ex}  The standard language of propositional logic $\Lang L_0$ consists of  the following connectives (with associated arities):   $\lfalse$~($0$)  $\lnot$~($1$),  $\land$~($2$),  $\lor$~($2$),  $\lif$~($2$). Most logics we consider will use this language. Some  logics by tradition an convention use different symbols for some  connectives. For instance, in product logic, the conjunction symbol  is often $\odot$ instead of~$\land$. Sometimes it is convenient to  add a new operator, e.g., the determinateness operator $\triangle$  ($1$-place).\end{ex}\end{document}

content/many-valued-logic/syntax-and-semantics/formulas.tex

% Part: many-valued-logic% Chapter: syntax-and-semantics% Section: formulas\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{syn}{fml}\olsection{\usetoken{P}{formula}}\begin{defn}[Formula]\ollabel{defn:formulas}The set~$\Frm[L]$ of \emph{!!{formula}s} of a propositionallanguage~$\Lang L$ is defined inductively as follows:\begin{enumerate}\item Every !!{propositional variable}~$\Obj p_i$ is an atomic  !!{formula}.\item Every $0$-place connective (propositional constant) of~$\Lang L$is an atomic !!{formula}.\item If $\star$ is an $n$-place connective of~$\Lang L$, and $!A_1$,\dots, $!A_n$ are !!{formula}s, then $\star(!A_1, \dots, !A_n)$ is  !!a{formula}.\tagitem{limitClause}{Nothing else is !!a{formula}.}{}\end{enumerate}If $\star$ is $1$-place, then $\star(!A_1)$ will often be writtensimply as $\star !A_1$. If $\star$ is $2$-place $\star(!A_1,!A_2)$will often be written as $(!A_1 \star !A_2)$. \end{defn}As usual, we will often silently leave out the outermost parentheses.\begin{ex}  In the standard language~$\Lang{L_0}$, $\Obj p_1 \lif (\Obj p_1  \land \lnot \Obj p_2)$ is a formula. In the language of product  logic, it would be written instead as $\Obj p_1 \lif (\Obj p_1 \odot  \lnot \Obj p_2)$.  If we add the $1$-place $\triangle$ to the  language, we would also have formulas such as $\triangle (\Obj p_1  \land \Obj p_2) \lif (\triangle \Obj p_1 \land \triangle \Obj p_2)$.\end{ex}\end{document}

content/many-valued-logic/syntax-and-semantics/matrices.tex

% Part: many-valued-logic% Chapter: syntax-and-semantics% Section: matrices\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{syn}{mat}\olsection{Matrices}A many-valued logic is defined by its language, its set of truthvalues~$V$, a subset of designated truth values, and truth functionsfor its connective.  Together, these elements are called a \emph{matrix}.  \begin{defn}[Matrix]\ollabel{defn:matrix}A \emph{matrix} for the logic~$\Log L$ consists of:\begin{enumerate}\item a set of connectives making up a language~$\Lang L$;\item a set $V \neq \emptyset$ of truth values;\item a set $V^+ \subseteq V$ of designated truth values;\item for each $n$-place connective $\star$ in $\Lang L$, a truthfunction~$\tf{\star} : V^n \to V$. If $n = 0$, then $\tf{\star}$ isjust an element of~$V$.\end{enumerate}\end{defn}\begin{ex}The matrix for classical logic~\LogCL{} consists of:\begin{enumerate}  \item The standard propositional language $\Lang L_0$ with  $\lfalse$, $\lnot$, $\land$, $\lor$, $\lif$.  \item The set of truth values $V = \{\True, \False\}$.  \item $\True$ is the only designated value, i.e., $V^+ = \{\True\}$.  \item For $\lfalse$, we have $\tf{\lfalse} = \False$. The other  truth functions are given by the usual truth tables (see  \olref{fig:tf-CL}).\end{enumerate}\begin{figure}  \begin{center}      \begin{tabular}{c|c}         $\tf{\lnot}$ & \\         \hline          $\True$ & $\False$ \\         $\False$ & $\True$       \end{tabular}      \quad      \begin{tabular}{c|cc}         $\tf{\land}$ & $\True$ & $\False$ \\         \hline         $\True$ & $\True$ & $\False$ \\         $\False$ & $\False$ & $\False$       \end{tabular}      \quad      \begin{tabular}{c|cc}         $\tf{\lor}$ & $\True$ & $\False$ \\         \hline         $\True$ & $\True$ & $\True$ \\         $\False$ & $\True$ & $\False$       \end{tabular}      \quad      \begin{tabular}{c|cc}         $\tf{\lif}$ & $\True$ & $\False$ \\         \hline         $\True$ & $\True$ & $\False$ \\         $\False$ & $\True$ & $\True$       \end{tabular}    \end{center}     \caption{Truth functions for classical logic~$\LogCL$.}    \ollabel{fig:tf-CL}  \end{figure}  \end{ex}\end{document}

content/many-valued-logic/syntax-and-semantics/valuations-sat.tex

% Part: many-valued-logic% Chapter: syntax-and-semantics% Section: valuations-sat\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{syn}{val}\olsection{\usetoken{P}{valuation} and Satisfaction}\begin{defn}[!!^{valuation}s] Let $V$ be a set of truth values. A \emph{!!{valuation}} for$\Lang{L}$ into~$V$ is afunction~$\pAssign{v}$ assigning !!a{element} of~$V$ to the!!{propositional variable}s of the language, i.e., $\pAssign{v} \colon\PVar \to V$.\end{defn}\begin{defn}\ollabel{defn:pValue}  Given !!a{valuation}~$\pAssign{v}$ into the set of truth values~$V$ of a  many-valued logic~$\Log L$, define the evaluation function  $\pValue{v} \colon \Frm[L] \to V$ inductively by:  \begin{enumerate}    \item $\pValue{v}(\Obj p_n) = \pAssign{v}(\Obj p_n)$;     \item If $\star$ is a $0$-place connective, then $\pValue{v}(\star)  = \tf{\star}[\Log L]$;    \item If $\star$ is an $n$-place connective, then     \[      \pValue{v}(\star(!A_1, \dots, !A_n)) = \tf{\star}[\Log L]      (\pValue{v}(!A_1), \dots, \pValue{v}(!A_n)).    \]  \end{enumerate}\end{defn}\begin{defn}[Satisfaction]\ollabel{defn:satisfaction} The !!{formula}~$!A$ is \emph{satisfied}  by !!a{valuation}~$\pAssign{v}$, $\pSat{v}{!A}[\Log L]$, iff  $\pValue{v}(!A)[\Log L] \in V^+$, where $V^+$ is the set of  designated truth values of~$\Log L$.     We write $\pSat/{v}{!A}[\Log L]$ to mean ``not $\pSat{v}{!A}[\Log  L]$.'' If $\Gamma$ is a set of !!{formula}s, $\pSat{v}{\Gamma}[\Log  L]$ iff $\pSat{v}{!A}[\Log L]$ for every~$!A \in \Gamma$.\end{defn}\end{document}

content/many-valued-logic/syntax-and-semantics/semantic-notions.tex

% Part: many-valued-logic% Chapter: syntax-and-semantics% Section: semantic-notions\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{syn}{sem}\olsection{Semantic Notions}Suppose a many-valued logic $\Log L$ is given by a matrix.  Then wecan define the usual semantic notions for~$\Log L$.\begin{defn} \begin{enumerate}\item !!^a{formula}~$!A$ is \emph{satisfiable} if for  some~$\pAssign{v}$, $\pSat{v}{!A}$; it is  \emph{unsatisfiable} if for no $\pAssign{v}$, $\pSat{v}{!A}$;\item !!^a{formula}~$!A$ is a \emph{tautology} if $\pSat{v}{!A}$ for  all !!{valuation}s~$v$;\item If $\Gamma$ is a set of !!{formula}s, $\Gamma \Entails !A$ (``$\Gamma$  entails $!A$'') if and only if $\pSat{v}{!A}$ for every  !!{valuation}~$\pAssign{v}$ for which $\pSat{v}{\Gamma}$.\item If $\Gamma$ is a set of !!{formula}s, $\Gamma$ is  \emph{satisfiable} if there is !!a{valuation}~$\pAssign{v}$ for which  $\pSat{v}{\Gamma}$, and $\Gamma$ is  \emph{unsatisfiable} otherwise.\end{enumerate} \end{defn}We have some of the same facts for these notions as we do forthe case of classical logic:\begin{prop}\ollabel{prop:semanticalfacts} \begin{enumerate} \item $!A$ is a tautology if and only if  $\emptyset \Entails !A$; \item If $\Gamma$ is satisfiable then every finite subset of $\Gamma$  is also satisfiable; \item\ollabel{def:monotonicity}%Monotonicity: if $\Gamma \subseteq \Delta$  and $\Gamma \Entails !A$ then also $\Delta \Entails !A$;\item\ollabel{def:Cut}%Transitivity: if $\Gamma \Entails !A$ and  $\Delta \cup \{ !A\} \Entails !B$ then $\Gamma \cup \Delta \Entails  !B$;\end{enumerate}\end{prop}\begin{proof}Exercise.\end{proof}\begin{prob}Prove \olref[mvl][syn][sem]{prop:semanticalfacts}\end{prob}In classical logic we can connect entailment and the conditional. Forinstance, we have the validity of \emph{modus ponens}: If $\Gamma\Entails !A$ and $\Gamma \Entails !A \lif !B$ then $\Gamma \Entails!B$.  Another important relationship between $\Entails$ and $\lif$ inclassical logic is the semantic deduction theorem: $\Gamma \Entails !A\lif !B$ if and only if $\Gamma \cup \{!A\} \Entails !B$. Theseresults \emph{do not} always hold in many-valued logics. Whether theydo depends on the truth function~$\tf{\lif}$.\end{document}

content/many-valued-logic/syntax-and-semantics/sublogics.tex

% Part: many-valued-logic% Chapter: syntax-and-semantics% Section: sublogics\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{mvl}{syn}{sub}\olsection{Many-valued logics as sublogics of~$\LogCL$}The usual many-valued logics are all defined using matrices in whichthe value of a truth-function for arguments in $\{\True, \False\}$agrees with the classical truth functions. Specifically, in theselogics, if $x \in \{\True, \False\}$, then $\tf{\lnot}[\Log L](x) =\tf{\lnot}[\LogCL](x)$, and for $\star$ any one of $\land$, $\lor$,$\lif$, if $x, y \in \{\True, \False\}$, then $\tf{\star}[\Log L](x,y) =\tf{\star}[\LogCL](x,y)$. In other words, the truth functions for$\lnot$, $\land$, $\lor$, $\lif$ restricted to $\{\True,\False\}$ areexactly the classical truth functions.\begin{prop}\ollabel{prop:mvl-cl}  Suppose that a many-valued logic~$\Log L$ contains the connectives  $\lnot$, $\land$, $\lor$, $\lif$ in its language, $\True, \False \in  V$, and its truth  functions satisfy:  \begin{enumerate}    \item\ollabel{prop:not} $\tf{\lnot}[\Log L](x) = \tf{\lnot}[\LogCL](x)$ if $x =    \True$ or $x = \False$;    \item\ollabel{prop:land} $\tf{\land}[\Log L](x,y) = \tf{\land}[\LogCL](x,y)$,    \item\ollabel{prop:lor} $\tf{\lor}[\Log L](x,y) = \tf{\lor}[\LogCL](x,y)$,    \item\ollabel{prop:lif} $\tf{\lif}[\Log L](x,y) = \tf{\lif}[\LogCL](x,y)$,    if $x, y \in \{\True, \False\}$.  \end{enumerate}  Then, for any valuation $\pAssign v$ into~$V$ such that $\pAssign  v(p) \in \{\True,\False\}$, $\pValue v[\Log L](!A) = \pValue  v[\LogCL](!A)$.\end{prop}\begin{proof}  By induction on~$!A$.  \begin{enumerate}  \item If $!A \ident p$ is atomic, we have $\pValue v[\Log L](!A) =  \pAssign v(p) = \pValue  v[\LogCL](!A)$.  \item If $!A \ident \lnot B$, we have  \begin{align*}    \pValue v[\Log L](!A) & = \tf{\lnot}[\Log L](\pValue v[\Log L](!B)) & &\text{by \olref[val]{defn:pValue}}\\    & = \tf{\lnot}[\Log L](\pValue v[\LogCL](!B)) && \text{by inductive hypothesis}\\    & = \tf{\lnot}[\LogCL](\pValue v[\LogCL](!B)) &&\text{by assumption \olref{prop:not},}\\&&&\text{since $\pValue v[\LogCL](!B) \in \{\True, \False\}$,}\\& = \pValue v[\LogCL](!A) &&\text{by \olref[val]{defn:pValue}}.\end{align*}\item If $!A \ident (!B \land !C)$, we have\begin{align*}  \pValue v[\Log L](!A) & = \tf{\land}[\Log L](\pValue v[\Log L](!B), \pValue v[\Log L](!C)) & &\text{by \olref[val]{defn:pValue}}\\  & = \tf{\land}[\Log L](\pValue v[\LogCL](!B),\pValue v[\LogCL](!C)) && \text{by inductive hypothesis}\\  & = \tf{\land}[\LogCL](\pValue v[\LogCL](!B),\pValue v[\LogCL](!C)) &&\text{by assumption \olref{prop:land},}\\&&&\text{since $\pValue v[\LogCL](!B),\pValue v[\LogCL](!C) \in \{\True, \False\}$,}\\& = \pValue v[\LogCL](!A) &&\text{by \olref[val]{defn:pValue}}.\end{align*}\end{enumerate}The cases where $!A \ident (!B \lor !C)$ and $!A \ident (!B \lif !C)$are similar.\end{proof}\begin{cor}  If a many-valued logic satisfies the conditions of  \olref{prop:mvl-cl}, $\True \in V^+$ and $\False \notin V^+$, then  ${\Entails[\Log L]} \subseteq {\Entails[\LogCL]}$, i.e., if $\Gamma  \Entails[\Log L] !B$ then $\Gamma \Entails[\LogCL] !B$. In  particular, every tautology of $\Log L$ is also a classical tautology.\end{cor}\begin{proof}  We prove the contrapositive. Suppose $\Gamma \Entails/[\LogCL] !B$.  Then there is some !!{valuation}~$\pAssign v\colon \PVar \to  \{\True, \False\}$ such that $\pValue v[\LogCL](!A) = \True$ for all  $!A \in \Gamma$ and $\pValue v[\LogCL](!B) = \False$. Since $\True,  \False \in V$, the !!{valuation}~$\pAssign v$ is also !!a{valuation}  for~$\Log L$. By \olref{prop:mvl-cl}, $\pValue v[\Log L](!A) =  \True$ for all $!A \in \Gamma$ and $\pValue v[\Log L](!B) = \False$.  Since $\True \in V^+$ and $\False \notin V^+$ that means $\pAssign v  \Entails[\Log L] \Gamma$ and $\pAssign v \Entails/[\Log L] !B$,  i.e., $\Gamma \Entails/[\Log L] !B$.\end{proof}\end{document}