Syntax and Semantics

Propositional languages and arities

A propositional language consists of a set $\Lang L$source of connectives. Each connective $\star$source has an arity; a connective of arity $n$source is said to be $n$source-place. Connectives of arity $0$source are also called constants; connectives of arity $1$source are called unary, and connectives of arity $2$source, binary.

Standard propositional language and alternative operators

The standard language of propositional logic $\Lang L_0$source consists of the following connectives (with associated arities): $\lfalse$source ($0$source) $\lnot$source ($1$source), $\land$source ($2$source), $\lor$source ($2$source), $\lif$source ($2$source). 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$source instead of $\land$source. Sometimes it is convenient to add a new operator, e.g., the determinateness operator $\triangle$source ($1$source-place).

Inductive definition of formulas

[Formula] The set $\Frm[L]$source of formulas of a propositional language $\Lang L$source is defined inductively as follows:

1. Every propositional variable $\Obj p_i$source is an atomic formula.

2. Every $0$source-place connective (propositional constant) of $\Lang L$source is an atomic formula.

3. If $\star$source is an $n$source-place connective of $\Lang L$source, and $!A_1$source, dots, $!A_n$source are formulas, then $\star(!A_1, \dots, !A_n)$source is a formula.

4. Nothing else is a formula.

If $\star$source is $1$source-place, then $\star(!A_1)$source will often be written simply as $\star !A_1$source. If $\star$source is $2$source-place $\star(!A_1,!A_2)$source will often be written as $(!A_1 \star !A_2)$source.

Examples of formulas in different languages

In the standard language $\Lang{L_0}$source, $\Obj p_1 \lif (\Obj p_1 \land \lnot \Obj p_2)$source 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)$source. If we add the $1$source-place $\triangle$source 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)$source.

Matrix for a many-valued logic

[Matrix] A matrix for the logic $\Log L$source consists of:

1. a set of connectives making up a language $\Lang L$source;

2. a set $V \neq \emptyset$source of truth values;

3. a set $V^+ \subseteq V$source of designated truth values;

4. for each $n$source-place connective $\star$source in $\Lang L$source, a truth function $\tf{\star} : V^n \to V$source. If $n = 0$source, then $\tf{\star}$source is just an element of $V$source.

Classical logic as a many-valued matrix

The matrix for classical logic $\LogCL$source consists of:

1. The standard propositional language $\Lang L_0$source with $\lfalse$source, $\lnot$source, $\land$source, $\lor$source, $\lif$source.

2. The set of truth values $V = \{\True, \False\}$source.

3. $\True$source is the only designated value, i.e., $V^+ = \{\True\}$source.

4. For $\lfalse$source, we have $\tf{\lfalse} = \False$source. The other truth functions are given by the usual truth tables (see the figure of classical truth functions).

Valuation into a truth value set

[Valuations] Let $V$source be a set of truth values. A valuation for $\Lang{L}$source into $V$source is a function $\pAssign{v}$source assigning an element of $V$source to the propositional variables of the language, i.e., $\pAssign{v} \colon \PVar \to V$source.

Evaluation function on all formulas

Given a valuation $\pAssign{v}$source into the set of truth values $V$source of a many-valued logic $\Log L$source, define the evaluation function $\pValue{v} \colon \Frm[L] \to V$source inductively by:

1. $\pValue{v}(\Obj p_n) = \pAssign{v}(\Obj p_n)$source;

2. If $\star$source is a $0$source-place connective, then $\pValue{v}(\star) = \tf{\star}[\Log L]$source;

3. If $\star$source is an $n$source-place connective, then

   $$\pValue{v}(\star(!A_1, \dots, !A_n)) = \tf{\star}[\Log L] (\pValue{v}(!A_1), \dots, \pValue{v}(!A_n)).$$source

Satisfaction by designated values

[Satisfaction] The formula $!A$source is satisfied by a valuation $\pAssign{v}$source, $\pSat{v}{!A}[\Log L]$source, iff $\pValue{v}(!A)[\Log L] \in V^+$source, where $V^+$source is the set of designated truth values of $\Log L$source.

We write $\pSat/{v}{!A}[\Log L]$source to mean “not $\pSat{v}{!A}[\Log L]$source.” If $\Gamma$source is a set of formulas, $\pSat{v}{\Gamma}[\Log L]$source iff $\pSat{v}{!A}[\Log L]$source for every $!A \in \Gamma$source.

Satisfiability, tautology and entailment

1. A formula $!A$source is satisfiable if for some $\pAssign{v}$source, $\pSat{v}{!A}$source; it is unsatisfiable if for no $\pAssign{v}$source, $\pSat{v}{!A}$source;

2. A formula $!A$source is a tautology if $\pSat{v}{!A}$source for all valuations $v$source;

3. If $\Gamma$source is a set of formulas, $\Gamma \Entails !A$source (“$\Gamma$source entails $!A$source”) if and only if $\pSat{v}{!A}$source for every valuation $\pAssign{v}$source for which $\pSat{v}{\Gamma}$source.

4. If $\Gamma$source is a set of formulas, $\Gamma$source is satisfiable if there is a valuation $\pAssign{v}$source for which $\pSat{v}{\Gamma}$source, and $\Gamma$source is unsatisfiable otherwise.

General facts about many-valued entailment

1. $!A$source is a tautology if and only if $\emptyset \Entails !A$source;

2. If $\Gamma$source is satisfiable then every finite subset of $\Gamma$source is also satisfiable;

3. Monotonicity: if $\Gamma \subseteq \Delta$source and $\Gamma \Entails !A$source then also $\Delta \Entails !A$source;

4. Transitivity: if $\Gamma \Entails !A$source and $\Delta \cup \{ !A\} \Entails !B$source then $\Gamma \cup \Delta \Entails !B$source;

Proof

Exercise.

Exercise on semantic facts

Prove the proposition on the four general semantic facts

Agreement with classical evaluation on classical inputs

Suppose that a many-valued logic $\Log L$source contains the connectives $\lnot$source, $\land$source, $\lor$source, $\lif$source in its language, $\True, \False \in V$source, and its truth functions satisfy:

1. $\tf{\lnot}[\Log L](x) = \tf{\lnot}[\LogCL](x)$source if $x = \True$source or $x = \False$source;

2. $\tf{\land}[\Log L](x,y) = \tf{\land}[\LogCL](x,y)$source,

3. $\tf{\lor}[\Log L](x,y) = \tf{\lor}[\LogCL](x,y)$source,

4. $\tf{\lif}[\Log L](x,y) = \tf{\lif}[\LogCL](x,y)$source, if $x, y \in \{\True, \False\}$source.

Then, for any valuation $\pAssign v$source into $V$source such that $\pAssign v(p) \in \{\True,\False\}$source, $\pValue v[\Log L](!A) = \pValue v[\LogCL](!A)$source.

Proof

By induction on $!A$source.

1. If $!A \ident p$source is atomic, we have $\pValue v[\Log L](!A) = \pAssign v(p) = \pValue v[\LogCL](!A)$source.

2. If $!A \ident \lnot B$source, we have

   $$\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}}.$$source
   References in this expression: the evaluation definition, the assumption that negation agrees on true and false, the evaluation definition.

3. If $!A \ident (!B \land !C)$source, we have

   $$\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}}.$$source
   References in this expression: the evaluation definition, the assumption that conjunction agrees on true and false, the evaluation definition.

The cases where $!A \ident (!B \lor !C)$source and $!A \ident (!B \lif !C)$source are similar.

Consequence relation included in classical consequence

If a many-valued logic satisfies the conditions of the proposition on agreement with classical evaluation, $\True \in V^+$source and $\False \notin V^+$source, then ${\Entails[\Log L]} \subseteq {\Entails[\LogCL]}$source, i.e., if $\Gamma \Entails[\Log L] !B$source then $\Gamma \Entails[\LogCL] !B$source. In particular, every tautology of $\Log L$source is also a classical tautology.

Proof

We prove the contrapositive. Suppose $\Gamma \Entails/[\LogCL] !B$source. Then there is some valuation $\pAssign v\colon \PVar \to \{\True, \False\}$source such that $\pValue v[\LogCL](!A) = \True$source for all $!A \in \Gamma$source and $\pValue v[\LogCL](!B) = \False$source. Since $\True, \False \in V$source, the valuation $\pAssign v$source is also a valuation for $\Log L$source. By the proposition on agreement with classical evaluation, $\pValue v[\Log L](!A) = \True$source for all $!A \in \Gamma$source and $\pValue v[\Log L](!B) = \False$source. Since $\True \in V^+$source and $\False \notin V^+$source that means $\pAssign v \Entails[\Log L] \Gamma$source and $\pAssign v \Entails/[\Log L] !B$source, i.e., $\Gamma \Entails/[\Log L] !B$source.