Logic 11: Soundness and Completeness Flashcards
S ⊨ A semantic entailment, set S semantically entails A
there is no model on which each member of S comes out true but A comes out false
S ⊭ A, set S do not semantically entail A
there is a counter-example, a model on which each member of S comes out true but A false
Semantic consequence
tested with truth-tables, listing all relevant models and checking whether members of S are true on any one row but A is not true on that row
all about truth and falsity- what has to be true given some other things are
Truth trees
check for syntactic consequence, ⊢
S ⊢ A, syntactic consequence
there is a proof of A from the members of S
S ⊬ A
set of sentences S do not syntactically entail sentence A, there is no proof of A from the members of S
Syntactic consequence
all about proof, what, given some system for manipulating formulae of the language, can be proved from what
Semantic and Syntactic Consequence Relationship
an argument is semantically valid iff it is syntactically valid
soundness and completeness
Soundness
for any set of sentences S and any sentence A: if S ⊢ A then S ⊨ A
whenever you have a proof of something A from some premises (members of S), the argument will also be valid according to truth tables
Truth-trees are sound- guarantees that when argument is proven using truth-trees, there will not be a possible counter-example using truth-TABLES
Completeness
if S ⊨ A then S ⊢ A
whenever an argument is valid with truth-tables, there will be a proof with truth-trees
if there is no row on the truth-table that makes all members of S true and A false, then, since truth-tree rules are complete, we can prove A from members of S using truth-trees
Completeness simplified
Truth-tree rules are all we need to prove everything we want
All the good arguments (all those valid according to truth-tables) are provable using truth-trees
Soundness and completeness relationship
the rules are enough to prove all the good arguments (completeness) and they don’t do any more than that, they don’t prove any bad arguments (soundness)
these are meta-logical results, they are features of the system of logic we are studying
informal proofs of soundness for truth-trees
if there is a proof of A from S, then any model that makes all the members of S true also makes A true
Contraposition
the conditional if P then Q = if not Q then not P
Reductio ad absurdum
if we assume P and can argue for something contradictory from that assumption, we can conclude that P is false
Soundness & Contraposition
if there is a model that makes all the members of S true but A false, then there is no proof of A from S
completeness by contraposition
if there is no proof of A from S, then there is a model that makes all the members of S true but that makes A false
if an argument is valid by truth-tables, then there is a proof using truth-trees
Completeness by Conditional proof
we can assume P and argue for Q on that assumption
“if P then Q”
to prove completeness, we assume that there is no proof of A from S, and then show that from this assumptions it follows that there is a model that makes all the members of S true but that makes A false
NOT VALID according to truth tables
trick to proving completeness
When we apply a tree rule to a formula, the truth of the formulae we get on each branch from that rule is sufficient for the truth of the formula we started from
ex. when we have P^Q on a branch and apply the tree rule, we got both P and Q on the branch
- the truth of P and Q individually is sufficient for the truth of P^Q
ex2. PvQ, we get 2 new branches, P —- Q, disjunction, the truth of P is sufficient for the truth of PvQ and the truth of Q is sufficient for the truth of PvQ
