Definitions Flashcards
(31 cards)
What is a proportional formula?
- Any propositional atom is a formula.
- T and falsity are formulas.
- If A is a formula, so is ~A
- If A, B are formulas, all boolean connective forms are also.
What is a literal?
A formula that’s either atomic or negated atomic
What is a clause?
Disjunction ( v ) of one or more literals
What is a situation?
Something that determines whether each propositional atom is true or false. It tells us the truth values of atoms.
For if-tests, a situation is some point in a program execution and thus the values of program variables at this point determine whether or not each atomic statement is true. (i.e the truth values of the propositional atoms)
What is a valid argument in propositional logic?
Given formulas A1…An, B an argument:
A1…An, therefore B
is valid if B is true in every situation in which A1….An are all true.
If so, we use double turnstile to say that A1….An logically entails B.
Alternative explanation of validity for propositional logic.
An argument is VALID if and only if it is impossible for all of the premises to be true and the conclusion to be false.
There can be a situation in which the premises are false and the conclusion is true.
Valid, satisfiable and equivalent formulas
Valid formula: A propositional formula is valid if it is true in every situation. - often called tautologies.
Satisfiable formula: A propositional formula is satisfiable if it is true in at least one situation.
Equivalent formulas: Two propositional formulas A and B are logically equivalent if they are true in exactly the same situations.
DNF and CNF
Disjunctive normal form:
Disjunction of conjunctions of literals and not further simplifiable without leaving this form.
Conjunctive normal form:
Conjunction of disjunction of literals (conjunction of clauses) and not further simplifiable without leaving this form.
What is a theorem?
A formula that can be established (‘proved’) by a given proof system.
In ND, a theorem is any formula A such that (single turnstile) A holds.
When is a proof system sound and complete?
A proof system is sound if every theorem is valid. (i.e every provable propositional formula is valid)
Therefore ND never makes mistakes.
A proof system is complete if every valid formula is a theorem.
(i.e every propositional validity can be proved)
ND is powerful enough to prove all valid formulas.`
Soundness of ND
Soundness: If A1 … An (single turnstile) B then A1 … An (double turnstile) B
Any provable propositional formula is valid.
Natural deduction never makes mistakes.
Completeness of ND
Completeness:
If A1 … An (double turnstile) B then A1 … An (single turnstile) B.
Any propositional validity can be proved.
Natural deduction is powerful enough to prove all valid formulas.
What is consistency?
A formula A is consistent if (not single turnstile) ~A.
In other words, a consistent formula is one whose negation cannot be proved. Does not contain a contradiction.
A formula is consistent if and only if it is satisfiable since
What is a signature?
A collection (set) of constants and relation symbols and function symbols with specified arities.
Replaces the collection of propositional atoms we had in propositional logic.
What is an L-Term
For a signature L,
- Any constant in L is an L-term.
- Any variable is an L-term.
- If f is an n-ary function symbol in L and t1…tn are L-terms then f(t1…tn) is an L-term.
- Nothing else.
What is a closed term/ground term?
A term that doesn’t involve a variable (i.e a constant)
What is a first-order formula?
- n-ary relation symbol R in L and t1 … tn are L-terms. R(t1…tn) is an atomic L-formula.
- If t and t’ are L-terms then t = t’ is an atomic L-formula.
- Truth and falsity.
- If A, B are L-formulas, so are all boolean connective combinations.
- If A is an L-formula and x is a variable then A(x) and E(x).
- Nothing else.
What is a structure in predicate logic?
Situations in predicate logic.
Let L be a signature. An L-structure M is a thing that:
- Identifies a non-empty collection of objects that M knows about. It’s called the domain of M ( dom(M) )
- Specifies what the symbols of L mean in terms of these objects.
Interpretation in M of a constant is an object in dom(M)
Interpretation in M of a relation symbol is a relation on dom(M)
What is the meaning of a constant in a structure M?
The meaning of a constant c is the object c^M in structure M.
c^M is the interpretation of c in M (it’s the object in dom(M) that c names in M)
What is the effect of the A(x) [p -> q] in evaluating formulas with quantifiers in a structure?
Since p -> q will be true in the structure whenever p is false, we only need to check the objects in the structure such that p is true.
Free and bound variables
Let A be a formula
Bound variable: If a variable lies under a quantifier A(x) or E(x) in the formation tree of A it is bound.
Free variable: If a variable does NOT lie under quantifiers in the formation tree of A then it is free.
What is a sentence?
A formula with no free variables.
What is an assignment?
Since free variables have no meaning in a structure, we must supply them with a value using an assignment.
Let M be a structure. An assignment into M is something that allocates an object in dom(M) to each variable.
For an assignment h and a variable x, we write h(x) for the object assigned to x by h.
What is the value of a term in an L-structure?
Let L be a signature, M an L-structure and h an assignment into M.
For any L-term t, the value of t in M under h is the object in M allocated to t by:
- M, if t is a constant — t^M
- h, if t is a variable — h(t)
- If t is f(t1…tn) and the values of t1…tn are known to be a1…an then value of t is f^M(a1….an)
