Chapter 2: Definitions Flashcards
(11 cards)
Definition 2.1. The set of propositions, denoted by L0,
The set of propositions, denoted by L0, is defined inductively as follows:
1) Every primitive proposition is a proposition, i.e. if P ∈ LP
0, then P ∈ L0.
2) If α is a proposition, then so is (¬α).
3) If α, β are propositions, then so is (α ⇒ β).
Definition 2.2. valuation
A valuation is a function v : L0 → {0, 1}, satisfying the following conditions:
1) For α ∈ L0, v(¬α) = 1 if v(α) = 0, while v(¬α) = 0 if v(α) = 1, i.e. v(¬α) = 1 − v(α).
2) If α, β ∈ L0, then v(α ⇒ β) = 0 if v(α) = 1 and v(β) = 0, while v(α ⇒ β) = 1 otherwise
Definition 2.7. Model
If, for a valuation v, v(α) = 1 for a proposition α ∈ L0,
then we say that α is true in/for v, or that v is a model of α.
If, for a set of propositions S and a valuation v, v(α) = 1 for all α ∈ S, then we say that v is a model of S.
Definition 2.8. tautology
If a proposition α ∈ L0 satisfies v(α) = 1 for every possible valuation v, then we say that α is a tautology, and write |= α.
Definition 2.9. semantically equivalent
If, for two propositions α, β ∈ L0, it is the case that v(α) = v(β) for every possible valuation v, then we say that the propositions α and β are semantically equivalent.
Definition 2.18. semantically implies
Consider a subset S of the set L0 of all propositions, and a proposition α ∈ L0.
Then, we say that S semantically implies or entails α, and write
S |= α if, for every valuation v such that v(s) = 1 for all s ∈ S, we also have v(α) = 1.
Definition 2.25.
proof
Let S be a subset of L0, i.e. S ⊂ L0, and let α be a proposition, i.e. α ∈ L0. Then, a proof of α from S is a finite, ordered sequence of propositions (or lines), t1, t2, · · · , tn say, such that tn is the proposition α, and, such that, for each proposition ti, 1 ≤ i ≤ n:
a) ti is an (occurrence of an) axiom, or
b) ti is a proposition in S (we call such a proposition a hypothesis), or
c) ti is a proposition that can be deduced by modus ponens from two preceding propositions: ti is some proposition β, and, for some j, k < i, tj is some proposition α and tk is the proposition α ⇒ β.
Definition 2.26.syntactically implies
Consider a subset S of the set of all propositions L0, and a proposition α ∈ L0.
Then, we say that S syntactically implies or proves α, and write S |- αif there exists a proof of α from S (S being a set of hypotheses in this case).
Definition 2.27. theory
f there exists a proof of a proposition α ∈ L0 that uses no hypotheses, but perhaps only occurrences of the three given axioms and modus ponens,
then we say that α is a theorem, i.e.
α ∈ L0 is a theorem if ∅ |- α.
In such a case, we may also write |- α.
Definition 2.37. consistent
Consider a set of propositions, S (S ⊂ L0).
The set S is consistent if there does not exist a proposition α such that S |- α and S |- (¬α). If there exists a proposition α such that S |- α and S |- (¬α), we say that the set S is inconsistent.
define the symbols in propositional logic
symbols of the language of propositional logic consist of: 1) a countably infinite set of primitive propositions {P1,P2,P3···} or {P,Q,R,P′,Q′,R′,···}, denoted by LP0 ;
2) the symbols ¬, ⇒, (, ).
