Editing Propositional calculus (section)

== Semantics ==
{{Main article|Semantics of logic|Model theory}}
To serve as a model of the logic of a given [[natural language]], a formal language must be semantically interpreted.<ref name=":21" /> In [[classical logic]], all propositions evaluate to exactly one of two [[Truth value|truth-values]]: ''True'' or ''False''.<ref name=":1" /><ref name=":26"/> For example, "[[Wikipedia]] is a [[Wikipedia:Free encyclopedia|free]] [[online encyclopedia]] that anyone can edit" [[Wikipedia:About|evaluates to ''True'']],<ref name="ms21"/> while "Wikipedia is a [[paper]] [[encyclopedia]]" [[Wikipedia:NOTPAPER|evaluates to ''False'']].<ref name="ms22"/>

In other respects, the following formal semantics can apply to the language of any propositional logic, but the assumptions that there are only two semantic values ([[Principle of bivalence|''bivalence'']]), that only one of the two is assigned to each formula in the language ([[Law of noncontradiction|''noncontradiction'']]), and that every formula gets assigned a value ([[Law of excluded middle|''excluded middle'']]), are distinctive features of classical logic.<ref name=":26" /><ref name="ms23"/><ref name="BostockIntermediate" /> To learn about [[Non-classical logic|nonclassical logics]] with more than two truth-values, and their unique semantics, one may consult the articles on "[[Many-valued logic]]", "[[Three-valued logic]]", "[[Finite-valued logic]]", and "[[Infinite-valued logic]]".

=== Interpretation (case) and argument ===
{{Main|Interpretation (logic)}}
For a given language <math>\mathcal{L}</math>, an '''interpretation''',<ref name=":24"/> '''valuation''',<ref name=":29" /> '''Boolean valuation''',<ref name="ms24"/> or '''case''',<ref name=":21" />{{refn|group=lower-alpha|The name "interpretation" is used by some authors and the name "case" by other authors. This article will be indifferent and use either, since it is collaboratively edited and there is no consensus about which terminology to adopt.}} is an [[assignment (mathematical logic)|assignment]] of ''semantic values'' to each formula of <math>\mathcal{L}</math>.<ref name=":21" /> For a formal language of classical logic, a case is defined as an ''assignment'', to each formula of <math>\mathcal{L}</math>, of one or the other, but not both, of the [[truth value]]s, namely [[truth]] ('''T''', or 1) and [[false (logic)|falsity]] ('''F''', or 0).<ref name="ms25"/><ref name=":19"/> An interpretation that follows the rules of classical logic is sometimes called a '''Boolean valuation'''.<ref name=":29" /><ref name="ms26"/> An interpretation of a formal language for classical logic is often expressed in terms of [[truth tables]].<ref name="metalogic"/><ref name=":1" /> Since each formula is only assigned a single truth-value, an interpretation may be viewed as a [[Function (mathematics)|function]], whose [[Domain of a function|domain]] is <math>\mathcal{L}</math>, and whose [[Range of a function|range]] is its set of semantic values <math>\mathcal{V} = \{\mathsf{T}, \mathsf{F}\}</math>,<ref name=":2" /> or <math>\mathcal{V} = \{1, 0\}</math>.<ref name=":21" />

For <math>n</math> distinct propositional symbols there are <math>2^n</math> distinct possible interpretations. For any particular symbol <math>a</math>, for example, there are <math>2^1=2</math> possible interpretations: either <math>a</math> is assigned '''T''', or <math>a</math> is assigned '''F'''. And for the pair <math>a</math>, <math>b</math> there are <math>2^2=4</math> possible interpretations: either both are assigned '''T''', or both are assigned '''F''', or <math>a</math> is assigned '''T''' and <math>b</math> is assigned '''F''', or <math>a</math> is assigned '''F''' and <math>b</math> is assigned '''T'''.<ref name="metalogic" /> Since <math>\mathcal{L}</math> has <math>\aleph_0</math>, that is, [[Denumerably infinite|denumerably]] many propositional symbols, there are <math>2^{\aleph_0}=\mathfrak c</math>, and therefore [[Cardinality of the continuum|uncountably many]] distinct possible interpretations of <math>\mathcal{L}</math> as a whole.<ref name="metalogic" />

Where <math>\mathcal{I}</math> is an interpretation and <math>\varphi</math> and <math>\psi</math> represent formulas, the definition of an ''argument'', given in {{section link||Arguments}}, may then be stated as a pair <math>\langle \{\varphi_1, \varphi_2, \varphi_3, ..., \varphi_n\} , \psi \rangle</math>, where <math>\{\varphi_1, \varphi_2, \varphi_3, ..., \varphi_n\}</math> is the set of premises and <math>\psi</math> is the conclusion. The definition of an argument's ''validity'', i.e. its property that <math>\{\varphi_1, \varphi_2, \varphi_3, ..., \varphi_n\} \models \psi</math>, can then be stated as its ''absence of a counterexample'', where a '''counterexample''' is defined as a case <math>\mathcal{I}</math> in which the argument's premises <math>\{\varphi_1, \varphi_2, \varphi_3, ..., \varphi_n\}</math> are all true but the conclusion <math>\psi</math> is not true.<ref name=":21" /><ref name=":13" /> As will be seen in {{section link||Semantic truth, validity, consequence}}, this is the same as to say that the conclusion is a ''semantic consequence'' of the premises.

=== Propositional connective semantics ===
{{Main article|Logical connective|Truth function}}An interpretation assigns semantic values to [[atomic formula]]s directly.<ref name=":24" /><ref name=":21" /> Molecular formulas are assigned a ''function'' of the value of their constituent atoms, according to the connective used;<ref name=":24" /><ref name=":21" /> the connectives are defined in such a way that the [[Truth value|truth-value]] of a sentence formed from atoms with connectives depends on the truth-values of the atoms that they're applied to, and ''only'' on those.<ref name=":24" /><ref name=":21" /> This assumption is referred to by [[Colin Howson]] as the assumption of the ''[[Truth function|truth-functionality]] of the [[Logical connective|connectives]]''.<ref name=":13" />

==== Semantics via. truth tables ====
{{Logical connectives sidebar}}
Since logical connectives are defined semantically only in terms of the [[truth value]]s that they take when the [[propositional variable]]s that they're applied to take either of the [[Principle of bivalence|two possible]] truth values,<ref name=":1" /><ref name=":21" /> the semantic definition of the connectives is usually represented as a [[truth table]] for each of the connectives,<ref name=":1" /><ref name=":21" /><ref name=":37" /> as seen below:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! <math>p</math>
! <math>q</math>
! <math>p \land q</math>
! <math>p \lor q</math>
! <math>p \rightarrow q</math>
! <math>p \Leftrightarrow q</math>
! <math>\neg p</math>
! <math>\neg q</math>
|-
| {{Success|}}T || {{Success|}}T || {{Success|}}T || {{Success|}}T || {{Success|}}T || {{Success|}}T || {{Failure|}}F || {{Failure|}}F
|-
| {{Success|}}T || {{Failure|}}F || {{Failure|}}F || {{Success|}}T || {{Failure|}}F || {{Failure|}}F || {{Failure|}}F || {{Success|}}T
|-
| {{Failure|}}F || {{Success|}}T || {{Failure|}}F || {{Success|}}T || {{Success|}}T || {{Failure|}}F || {{Success|}}T || {{Failure|}}F
|-
| {{Failure|}}F || {{Failure|}}F || {{Failure|}}F || {{Failure|}}F || {{Success|}}T || {{Success|}}T || {{Success|}}T || {{Success|}}T
|}

This table covers each of the main five [[logical connective]]s:<ref name=":5" /><ref name=":0" /><ref name=":3" /><ref name=":12" /> [[Logical conjunction|conjunction]] (here notated <math>p \land q</math>), [[Logical disjunction|disjunction]] ({{math|''p'' ∨ ''q''}}), [[Material conditional|implication]] ({{math|''p'' → ''q''}}), [[Logical biconditional|biconditional]] ({{math|''p'' ↔ ''q''}}) and [[negation]], (¬''p'', or ¬''q'', as the case may be). It is sufficient for determining the semantics of each of these operators.<ref name=":1" /><ref name="ms27"/><ref name=":21" /> For more truth tables for more different kinds of connectives, see the article "[[Truth table]]".

==== Semantics via assignment expressions ====
Some authors (viz., all the authors cited in this subsection) write out the connective semantics using a list of statements instead of a table. In this format, where <math>\mathcal{I}(\varphi)</math> is the interpretation of <math>\varphi</math>, the five connectives are defined as:<ref name="BostockIntermediate" /><ref name=":29" />

* <math>\mathcal{I}(\neg P) = \mathsf{T}</math> if, and only if, <math>\mathcal{I}(P) = \mathsf{F}</math>
* <math>\mathcal{I}(P \land Q) = \mathsf{T}</math> if, and only if, <math>\mathcal{I}(P) = \mathsf{T}</math> and <math>\mathcal{I}(Q) = \mathsf{T}</math>
* <math>\mathcal{I}(P \lor Q) = \mathsf{T}</math> if, and only if, <math>\mathcal{I}(P) = \mathsf{T}</math> or <math>\mathcal{I}(Q) = \mathsf{T}</math>
* <math>\mathcal{I}(P \to Q) = \mathsf{T}</math> if, and only if, it is true that, if <math>\mathcal{I}(P) = \mathsf{T}</math>, then <math>\mathcal{I}(Q) = \mathsf{T}</math>
* <math>\mathcal{I}(P \leftrightarrow Q) = \mathsf{T}</math> if, and only if, it is true that <math>\mathcal{I}(P) = \mathsf{T}</math> if, and only if, <math>\mathcal{I}(Q) = \mathsf{T}</math>
Instead of <math>\mathcal{I}(\varphi)</math>, the interpretation of <math>\varphi</math> may be written out as <math>|\varphi|</math>,<ref name="BostockIntermediate" /><ref name="ms28"/> or, for definitions such as the above, <math>\mathcal{I}(\varphi) = \mathsf{T}</math> may be written simply as the English sentence "<math>\varphi</math> is given the value <math>\mathsf{T}</math>".<ref name=":29" /> Yet other authors<ref name="ms29"/><ref name=":43"/> may prefer to speak of a [[Model theory|Tarskian model]] <math>\mathfrak{M}</math> for the language, so that instead they'll use the notation <math>\mathfrak{M} \models \varphi</math>, which is equivalent to saying <math>\mathcal{I}(\varphi) = \mathsf{T}</math>, where <math>\mathcal{I}</math> is the interpretation function for <math>\mathfrak{M}</math>.<ref name=":43" />

==== Connective definition methods ====
Some of these connectives may be defined in terms of others: for instance, implication, <math>p \rightarrow q</math>, may be defined in terms of disjunction and negation, as <math>\neg p \lor q</math>;<ref name="ms30"/> and disjunction may be defined in terms of negation and conjunction, as <math>\neg(\neg p \land \neg q</math>.<ref name=":29" /> In fact, a ''[[Functional completeness|truth-functionally complete]]'' system,{{refn|group=lower-alpha|A truth-functionally complete set of connectives<ref name=":2" /> is also called simply ''[[Functional completeness|functionally complete]]'', or ''adequate for truth-functional logic'',<ref name=":13" /> or ''expressively adequate'',<ref name="Smith2003"/> or simply ''adequate''.<ref name=":13" /><ref name="Smith2003" />}} in the sense that all and only the classical propositional tautologies are theorems, may be derived using only disjunction and negation (as [[Bertrand Russell|Russell]], [[Alfred North Whitehead|Whitehead]], and [[David Hilbert|Hilbert]] did), or using only implication and negation (as [[Gottlob Frege|Frege]] did), or using only conjunction and negation, or even using only a single connective for "not and" (the [[Sheffer stroke]]),<ref name=":18" /> as [[Jean Nicod]] did.<ref name=":2" /> A ''joint denial'' connective ([[logical NOR]]) will also suffice, by itself, to define all other connectives. Besides NOR and NAND, no other connectives have this property.<ref name=":29" />{{efn|[[Truth_table#Overview_table|See a table]] of all 16 bivalent truth functions.}}

Some authors, namely [[Colin Howson|Howson]]<ref name=":13" /> and Cunningham,<ref name="ms31"/> distinguish equivalence from the biconditional. (As to equivalence, Howson calls it "truth-functional equivalence", while Cunningham calls it "logical equivalence".) Equivalence is symbolized with ⇔ and is a metalanguage symbol, while a biconditional is symbolized with ↔ and is a logical connective in the object language <math>\mathcal{L}</math>. Regardless, an equivalence or biconditional is true if, and only if, the formulas connected by it are assigned the same semantic value under every interpretation. Other authors often do not make this distinction, and may use the word "equivalence",<ref name=":3" /> and/or the symbol ⇔,<ref name="ms32"/> to denote their object language's biconditional connective.

=== Semantic truth, validity, consequence ===
Given <math>\varphi</math> and <math>\psi</math> as [[formula (mathematical logic)|formulas]] (or sentences) of a language <math>\mathcal{L}</math>, and <math>\mathcal{I}</math> as an interpretation (or case){{refn|group=lower-alpha|Some of these definitions use the word "interpretation", and speak of sentences/formulas being true or false "under" it, and some will use the word "case", and speak of sentences/formulas being true or false "in" it. Published ''reliable sources'' ([[WP:RS]]) have used both kinds of terminological convention, although usually a given author will use only one of them. Since this article is collaboratively edited and there is no consensus about which convention to use, these variations in terminology have been left standing.}} of <math>\mathcal{L}</math>, then the following definitions apply:<ref name="metalogic" /><ref name=":19" />

* '''Truth-in-a-case:'''<ref name=":21" /> A sentence <math>\varphi</math> of <math>\mathcal{L}</math> is ''true under an interpretation'' <math>\mathcal{I}</math> if <math>\mathcal{I}</math> assigns the truth value '''T''' to <math>\varphi</math>.<ref name=":19" /><ref name="metalogic" /> If <math>\varphi</math> is [[logical truth|true]] under <math>\mathcal{I}</math>, then <math>\mathcal{I}</math> is called a ''model'' of <math>\varphi</math>.<ref name="metalogic" />
* '''Falsity-in-a-case:<ref name=":21" />''' <math>\varphi</math> is ''false under an interpretation'' <math>\mathcal{I}</math> if, and only if, <math>\neg\varphi</math> is true under <math>\mathcal{I}</math>.<ref name="metalogic" /><ref name=":20" /><ref name=":21" /> This is the "truth of negation" definition of falsity-in-a-case.<ref name=":21" /> Falsity-in-a-case may also be defined by the "complement" definition: <math>\varphi</math> is ''false under an interpretation'' <math>\mathcal{I}</math> if, and only if, <math>\varphi</math> is not true under <math>\mathcal{I}</math>.<ref name=":19" /><ref name="metalogic" /> In [[classical logic]], these definitions are equivalent, but in [[Non-classical logic|nonclassical logics]], they are not.<ref name=":21" />
* '''Semantic consequence:''' A sentence <math>\psi</math> of <math>\mathcal{L}</math> is a ''[[Logical consequence|semantic consequence]]'' (<math>\varphi \models \psi</math>) of a sentence <math>\varphi</math> if there is no interpretation under which <math>\varphi</math> is true and <math>\psi</math> is not true.<ref name=":19" /><ref name="metalogic" /><ref name=":21" />
* '''Valid formula (tautology):''' A sentence <math>\varphi</math> of <math>\mathcal{L}</math> is ''logically valid'' (<math>\models\varphi</math>),{{refn|group=lower-alpha|Conventionally <math>\models\varphi</math>, with nothing to the left of the turnstile, is used to symbolize a tautology. It may be interpreted as saying that <math>\varphi</math> is a semantic consequence of the empty set of formulae, i.e., <math>\{\}\models\varphi</math>, but with the empty brackets omitted for simplicity;<ref name="BostockIntermediate" /> which is just the same as to say that it is a tautology, i.e., that there is no interpretation under which it is false.<ref name="BostockIntermediate" />}} or a ''tautology'',<ref name="ms33"/><ref name="ms34"/>ref name="ms32<ref name=":29" /> if it is true under every interpretation,<ref name=":19" /><ref name="metalogic" /> or ''true in every case.''<ref name=":21" />
* '''Consistent sentence:''' A sentence of <math>\mathcal{L}</math> is ''[[Consistency|consistent]]'' if it is true under at least one interpretation. It is ''inconsistent'' if it is not consistent.<ref name=":19" /><ref name="metalogic" /> An inconsistent formula is also called ''self-contradictory'',<ref name=":1" /> and said to be a ''self-contradiction'',<ref name=":1" /> or simply a ''contradiction'',<ref name=":30" /><ref name=":31" /><ref name=":32" /> although this latter name is sometimes reserved specifically for statements of the form <math>(p \land \neg p)</math>.<ref name=":1" />

For interpretations (cases) <math>\mathcal{I}</math> of <math>\mathcal{L}</math>, these definitions are sometimes given:

* '''Complete case:''' A case <math>\mathcal{I}</math> is ''complete'' if, and only if, either <math>\varphi</math> is true-in-<math>\mathcal{I}</math> or <math>\neg\varphi</math> is true-in-<math>\mathcal{I}</math>, for any <math>\varphi</math> in <math>\mathcal{L}</math>.<ref name=":21" /><ref name="ms35"/>
* '''Consistent case:''' A case <math>\mathcal{I}</math> is ''consistent'' if, and only if, there is no <math>\varphi</math> in <math>\mathcal{L}</math> such that both <math>\varphi</math> and <math>\neg\varphi</math> are true-in-<math>\mathcal{I}</math>.<ref name=":21" /><ref name="ms36"/>

For [[classical logic]], which assumes that all cases are complete and consistent,<ref name=":21" /> the following theorems apply:

* For any given interpretation, a given formula is either true or false under it.<ref name="metalogic" /><ref name=":20"/>
* No formula is both true and false under the same interpretation.<ref name="metalogic" /><ref name=":20" />
* <math>\varphi</math> is true under <math>\mathcal{I}</math> if, and only if, <math>\neg\varphi</math> is false under <math>\mathcal{I}</math>;<ref name="metalogic" /><ref name=":20" /> <math>\neg\varphi</math> is true under <math>\mathcal{I}</math> if, and only if, <math>\varphi</math> is not true under <math>\mathcal{I}</math>.<ref name="metalogic" />
* If <math>\varphi</math> and <math>(\varphi \to \psi)</math> are both true under <math>\mathcal{I}</math>, then <math>\psi</math> is true under <math>\mathcal{I}</math>.<ref name="metalogic" /><ref name=":20" />
* If <math>\models\varphi</math> and <math>\models(\varphi \to \psi)</math>, then <math>\models\psi</math>.<ref name="metalogic" />
* <math>(\varphi \to \psi)</math> is true under <math>\mathcal{I}</math> if, and only if, either <math>\varphi</math> is not true under <math>\mathcal{I}</math>, or <math>\psi</math> is true under <math>\mathcal{I}</math>.<ref name="metalogic" />
* <math>\varphi \models \psi</math> if, and only if, <math>(\varphi \to \psi)</math> is [[logically valid]], that is, <math>\varphi \models \psi</math> if, and only if, <math> \models(\varphi \to \psi)</math>.<ref name="metalogic" /><ref name=":20" />