Propositional Logic
Propositional logic, also called sentential logic or order-zero logic, is a logical system of statements.
Given a set V of propositional variables, the set of well-formed formulas (WFFs) over V is generated by:
P,Q↦v∣⊤∣⊥∣¬P∣(P∨Q)∣(P∧Q)∣(P→Q)
Where v∈V.
Note that in order for this generation to be free (ie, for the resulting string to have a unique generation path), the parentheses are mandatory. However, in practice, they are often omitted; the string P∧Q→R is disambiguated to either (P∧Q)→R or P∧(Q→R) by convention or context.
For any set V of variables and a truth-assignment function v:V→{T,F}, we can lift it to a truth evaluation function v:WFF(V)→{T,F} over the set of WFFs with variables from V.
This is done recursively over the grammar of propositional logic as follows. Given ϕ a WFF, we define v(ϕ) as follows:
If
ϕ=a∈V, then
v(ϕ)=v(a)
If
ϕ=⊤, then
v(ϕ)=T
If
ϕ=⊥, then
v(ϕ)=F
If
ϕ=¬ψ1, then
v(ϕ)=T iff v(ψ)=F
If
ϕ=ψ1∨ψ2, then
v(ϕ)=T iff either
v(ψ1)=T or
v(ψ2)=T
If
ϕ=ψ1∧ψ2, then
v(ϕ)=T iff both
v(ψ1)=T and
v(ψ2)=T
We call a WFF ϕ over variable set V a tautology if for every variable assignment v:V→{T,F} we have that v(ϕ)=T.
We say that:
a truth-assignment
v satisfies a WFF
ϕ if
v(ϕ)=T
a truth-assignment
v satisfies a
set Φ of WFFs if for each
ϕ∈Φ we have that
v(ϕ)=T
We may say “models” or “is a model of” instead of “satisfies”
For a sentence ψ and set of sentences Φ, we say that Φ tautologically implies ψ and write Φ⊨ψ if for every truth-assignment v satisfying Φ, we have that v also satisfies ψ.
For two sentences ϕ and ψ, we say ϕ⊨ψ to mean {ϕ}⊨ψ.
If {ϕ}⊨ψ and {ψ}⊨ϕ, we say that ϕ and ψ are tautologically equivalent.
Propositional logic is said to be complete, which means essentially that the rules we have so far are enough to express “everything”. For instance, we may think about adding a new kind of sentence #(P,R,Q) which is true if and only if a majority of P, Q, and R are true.
But there’s no need to add anything new to do this! Instead of #(P,R,Q) we can write
(P∧R)∨(R∧Q)∨(P∧Q)
Which is true if and only if a majority of P, Q, and R are true. Completeness says that # is not a special case; no matter what we may think of adding, we already have it.
Rigorously, completeness says the following. Take:
n∈N
an
n-ary boolean
function b:{T,F}n→{T,F}
an ordered
set V={Vk} of
n variables
Then exists a sentence ϕ∈WFF(V) such that for each truth-assignment function v:V→{T,F}, we have that v(ϕ)=T if and only if b(v(v1),v(v2),…,v(vn))=T.
Conceptually, this means that for any n-ary boolean function b, we can create a sentence ϕ which is true exactly according to b; or, alternatively, we can say ϕ is a kind of a representation or encoding of b.
Another interpretation is that this means that the lanugage {∧,∨,¬,→,…} has “all the connectives we need”—if you add a new connective, no formula can be written with that connective which could not already have been written.
Proof sketch: express b as a disjunction of conjunctions of possible-negations over V.
Propositional logic exhibits a theorem called compactness. The statement of compactness is as follows.
Take V a set of variables and T⊆WFF(V) a set of propositional statements over V. Then if for every finite S⊆T exists a truth-assigment vS satisfying S, then exists a truth-assignment v satisfying T.
No proof right now.