Logic 11: Soundness and Completeness

Question 1

S ⊨ A semantic entailment, set S semantically entails A

Answer 1

there is no model on which each member of S comes out true but A comes out false

Question 2

S ⊭ A, set S do not semantically entail A

Answer 2

there is a counter-example, a model on which each member of S comes out true but A false

Question 3

Semantic consequence

Answer 3

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

Question 4

Truth trees

Answer 4

check for syntactic consequence, ⊢

Question 5

S ⊢ A, syntactic consequence

Answer 5

there is a proof of A from the members of S

Question 6

S ⊬ A

Answer 6

set of sentences S do not syntactically entail sentence A, there is no proof of A from the members of S

Question 7

Syntactic consequence

Answer 7

all about proof, what, given some system for manipulating formulae of the language, can be proved from what

Question 8

Semantic and Syntactic Consequence Relationship

Answer 8

an argument is semantically valid iff it is syntactically valid
soundness and completeness

Question 9

Soundness

Answer 9

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

Question 10

Completeness

Answer 10

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

Question 11

Completeness simplified

Answer 11

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

Question 12

Soundness and completeness relationship

Answer 12

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

Question 13

informal proofs of soundness for truth-trees

Answer 13

if there is a proof of A from S, then any model that makes all the members of S true also makes A true

Question 14

Contraposition

Answer 14

the conditional if P then Q = if not Q then not P

Question 15

Reductio ad absurdum

Answer 15

if we assume P and can argue for something contradictory from that assumption, we can conclude that P is false

Question 16

Soundness & Contraposition

Answer 16

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

Question 17

completeness by contraposition

Answer 17

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

Question 18

Completeness by Conditional proof

Answer 18

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

Question 19

trick to proving completeness

Answer 19

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