Natural Deduction proofs

only what have proofs? (this must be the case: Γ⊧ϕ)

only valid arguments

(P∧ -P) ⊧

means there is no L1-structure where (P∧ -P) have truth value T and any L1-sentence has the truth value F (cuz there isnt one) so its a contradiction

⊧ (P∧ -P)

means there is no L1-structure any set of L1 sentences have truth value T and (P∧ -P) has truth value F (so this is a tautology or logically true)

proofs in N.D start with an assumption which is that any sentence can be assumed, whats the assumption rule

The occurrence of a sentence ϕ with no sentence above it is an assumption. An assumption of ϕ is a proof of ϕ.

appending

the result (which appears under the horizontal line) from a proof certain sentences (ϕ or ψ)

∧Intro

The result of appending ϕ∧ψ to a proof of ϕ and a proof of ψ is a proof of ϕ∧ψ or ψ∧ϕ

∧Elim1

The result of appending ϕ to a proof of ϕ∧ψ is a proof of ϕ (this is to keep ϕ)

∧Elim2

∧Elim2 The result of appending ψ to a proof of ϕ∧ψ is a proof of ψ (this is to keep ψ)

when do we discharge the assumption A in ‘if A then B’

when one has proven B

how does one prove B in ‘if A then B’

by assuming A

→Intro

The result of appending ϕ→ψ to a proof of ψ and discharging all assumptions of ϕ in the proof of ψ is a proof of ϕ→ψ.

→Elim

The result of appending ψ to a proof of ϕand a proof of ϕ→ψ is a proof of ψ

The formula ϕis provable from Γ (where Γ is a set of L2 sentences) iff…

there is a proof of ϕ with only sentences in Γ as

non-discharged assumptions (this means that ϕ is being assumed in Γ: for example in ⊢P ∧Q →P, P ∧Q are assumed)

Γ ⊢ ϕ means what

ϕ is provable from Γ

∨Intro1

The result of appending a sentence ϕ∨ψ to a proof

of ϕ is a proof of ϕ∨ψ

∨Elim

The result of appending χ to a proof of ϕ∨ψ, a proof of χ

and another proof of χ, and of discharging all assumptions

of ϕin the first proof of χ and of discharging all assumptions

of ψ in the second proof of χ, is a proof of χ (if you can prove C from assuming A and prove C from assuming B, then one may conclude C since C can be derived from both cases)