Semantics of propositional logic

Semantics determines the rules for interpreting propositions. Assigning truth values to each of the elementary propositions intervening in a proposition amounts to choosing a model of this proposition.

More precisely, if we place ourselves in classical logic, the interpretation of a proposition A is the fact of assigning a truth value (0 or 1) to the propositional variables and explaining how the connectives behave vis-à-vis with respect to truth values. This behavior is given by a truth table. In this way we can give a value 0 or 1 to each proposition which depends on the values ​​taken by the truth tables. There are the following cases of interpretation:

• When the proposition always takes the value 0 regardless of the values ​​of the propositional variables, the proposition is said to be an antilogy or a contradiction. It is also said to be unsatisfactory.
• When proposition A always takes the value 1, A is a tautology. We also say that A is valid and we denote this assertion ╞ A .
• If the proposition takes at least once the value 1, we say that we can satisfy A, or that A is satisfyable.
• If the proposition takes at least once the value 1 and at least once the value 0, it is a synthetic or contingent proposition.

Boolean interpretation of connectors

We explain the behavior, then give the associated truth table

• P ˅ Q will take the value 1 if and only if at least one of the two propositions P or Q takes the value 1.

P	Q	P ˅ Q
0	0	0
0	1	1
1	0	1
1	1	1

• P ˄ Q will take the value 1 if and only if the two propositions P and Q simultaneously take the value 1.

P	Q	P ˄ Q
0	0	0
0	1	0
1	0	0
1	1	1

• P → Q will take the value 0 if and only if P takes the value 1 and Q the value 0.

P	Q	P → Q
0	0	1
0	1	1
1	0	0
1	1	1

• ¬ P takes the value 1 if and only if P takes the value 0.

P	¬ P
0	1
1	0

• P ↔ Q will take the value 1 if and only if P and Q have the same value.

P	Q	P ↔ Q
0	0	1
0	1	0
1	0	0
1	1	1

• ⊥ takes the value 0.

Example 1:

(¬A → A) → A is a tautology.

Indeed, if we attribute to A the value 0, then ¬A takes the value 1, (¬A → A) takes the value 0, and (¬A → A) → A takes the value 1. Similarly, if we assigns A the value 1, then ¬A takes the value 0, (¬A → A) takes the value 1, and (¬A → A) → A takes the value 1.

Example 2:

A → (A → ¬A) is not a tautology.

Indeed, if we attribute to A the value 1, then ¬A takes the value 0, (A → ¬A) takes the value 0, and A → (A → ¬A) takes the value 0.

Complete connector systems

An n-input truth table defines an n-ary connector. A set of propositional connectors is said to be complete if any connector can be defined by means of the connectors of the set. Any truth table is described using conjunctions of disjunctions and negation, for example we fully describe the truth table of equivalence above by “p ↔ q takes the value true if and only if p and q evaluate to false or p and q evaluate to true”, i.e. p ↔ q ≡ (¬p ∧ ¬q) ∨ (p ∧ q). This method is general and allows to show that the system {¬, ∧, ∨} is a complete system of connectors. We deduce that {¬, ∧}, {¬, ∨} are also complete systems (because of Morgan’s laws, A∨B ≡ ¬ (¬A ∧ ¬B), A ∧ B ≡ ¬ (¬A ∨ ¬B)). The set {¬, →} is also complete: A ∨ B ≡ ¬A → B.

The set consisting of the single NAND connector (denoted “|” by Henry Sheffer and therefore called the Sheffer bar) is also complete, ¬P being equivalent to P|P and P∨Q to ( P|P) | (Q|Q). This feature is used for the construction of logic circuits, a single logic gate is then sufficient to design all existing circuits.

(Includes texts from Wikipedia translated and adapted by Nicolae Sfetcu)