Semantics
- Semantics means “meaning”.
- Semantics relate two worlds. -n Semantics provide an interpretaiton (mapping) of values in one world to values in another world. They are often a funciton from expressions in one world to expressions in another world.
It’s a goal when we are asking the question “is it a theorem?“. It’s a theorem when we know it is valid.
The semantics of a logic defines the meaning of formulas in the logic leading to a definition of the symbol: (entails or valid or semantic entailment). is a meta-symbol (meaning not a symbol that can be used in a formula of the logic but a symbol about formulas in the logic).
Topics:
- Boolean valuations
- Truth tables
- Satisfiability, tautologies, contradictions, contingent formulas
- Logical implication
- Logical equivalence
- Consistency
Boolean Valuations
Definition: A Boolean valuation (BV) is a function from the set of wffs in propositional logic to the set Tr = {T, F}. The semantics of propositional logic are described using BV. The [] is a function mapping syntax to its value.
When describing a BV, we only need to describe the association of truth values with the proposition symbols.
- Ex:
Truth Tables
Describes the meaning of a formula in all Boolean valuations.
Satifiability
Definition: A formula P is satisfiable if there is a Boolean valuation such that [P] = T. A formula is satisfiable if its truth table has some T’s in the last column.
Tautologies
Definition: A propositional formula P is a tautology (or valid) if [P] = T for all Boolean valuations. A tautology is a formula that is T for all truths values of the proposition symbols used in the formula. The last column of the truth table for a tautology contains all T’s.
If a formula Q is a tautology, we write: Q ,“entails Q”.
Logical Implication
Definition: A formula P logically implies a formula Q if and only if for all Boolean valuations, if [P] = T then [Q] = T. P Q “P entails Q” or “P logically implies Q”. Definition: A set of formulas P1, P2, …, Pn logically imply a formula Q if and only if for all BV, if [P1] = T and [P2] = T, …, [Pn] = T then [Q] = T. P1, P2, …, Pn Q
Contradiction
Definition: A propositional formula A is a contradiction if [A] = F for all BV.
Contingent
Definition: A contingent formula is one that is neither a tautology nor a contradiction. It has a mixture of Ts and Fs in the column representing the formula in the truth table.
Summary
We can use TT to determine if formula is satisfiable, a tautology, a contradiction or a contingent formula.
| Formula | Last column of TT |
|---|---|
| contradiciton | all Fs |
| tautology () | all Ts |
| satisfiable | at least one T |
| contingent | at least one T and at least one F |
Logical Equivalence
Definition: Two formulas, P and Q are logically equivalent if and only if all BV, [P] = [Q].
Consistency
Definition: A collection of formulas is consistent if there is a BV in which all the formulas are T.