Propositional logic Flashcards
define a PL-wff
(i) Every sentence letter is a PL-wff
(ii) if π, π are wff then Β¬π, (πβπ), (πβ¨π), (πβ§π), and (πβοΈπ) are also PL-wffs
(iii) only what can be shown to be PL-wffs using (i) and (ii) are PL-wffs
When is a formula valid?
When the formula is true for all possible interpretations
When is an argument valid?
When the premises cannot be true and the conclusion false.
What is an informal proof?
A proof conducted in the natural language
What is a direct proof?
A proof that goes directly from the interpretations
What is an indirect proof?
A proof by contradiction that begins by assuming the contrary. (reductio ad absurdum).
When are two equations π and π semantically equivalent?
for all interpretations V(π)=V(π)
What is the natural deduction system?
The proof system that uses those long lines.
what does it mean to say that a language of propositional logic is βexpressively adequateβ?
it can express all truth-functions
Define completeness
A proof system is complete iff any valid formula and argument are provable in that system.
define logical consequence
certain claims logically follow from others - if the premises are true, then the conclusion is true
True or False:
A logically valid proposition is called a logical consequence
FALSE
a logically valid proposition is called a logical truth, a logically valid argument is called a logical consequence
define meta-language
The language used to describe the object language
what is a REFLEXIVE relation?
a has that relation to itself
what is a SYMMETRIC relation?
if a has R to b, then b has R to a
what is an ASYMMETRIC relation?
there is no a,b such that if a has R to b, then b has R to a
what is an ANTISYMMETRIC relation?
there is no distinct a,b such that if a has R to b, then b has R to a e.g. the identity relation
what is a TRANSITIVE relation?
if a has R to b, and b has R to c, then a has R to c
What is a unary connective?
a connective that combines with one formula (i.e. Β¬)
What is a binary connective?
A connective that combines with two formulas (e.g. β,βοΈ,β¨,β§)
What, in particular, does Propositional Logic express?
Truth-functional thoughts
True or false:
what can be proved in one proof system can be proved in any other proof system
TRUE
Explain what is meant by βπ is provable from a set of formulasβ
there is a derivation that starts with the assumptions of the set of formulas and ends with π
Define soundness
A proof system is complete iff everything that we can prove in the system is valid
Which is the minimal standard and which is the gold standard of βCompletenessβ and βsoundnessβ?
Soundness is the minimal standard (makes no errors)
completeness is the gold standard (has no gaps)
is natural deduction complete?
yes
