Karteikarten
Logic: Definitions
Karten in diesem Stapel (22)
- 1Prop Formula-every propositional variable
-if A,B formulas, then ~A and (A.B) for all binary connectives . are formula - 2Prop Valuation-a valuation is a function v:variables -> {T,F}
-extends to a function v*:Form(L) -> {T,F} recursively, where for a formula of length 1 v*(A)=v(A) etc - 3Satisfiability-a valuation satisfies A if v*(A)=T
-if A is satisfied by some v then it is satisfiable
-is A is satisfied by every v then it is a tautology - 4Logical Consequencefor a set G of formulas and A a formula, A is a logical consequence of G if, for all v, if V*(g)=T for all g in G, then v*(A)=T
- 5Logical EquivalenceA,B are logically equivalent if they are a logical consequence of each other
- 6Adequacy-Vn set of partial valuations
-n-ary truth function J:Vn -> {T,F}
-for A in Formn(L), then A determines the truth formula JA(v)=v*(A)
-for a set S of truth functional connectives, S is adequate if for all n and for all n-ary truth functions J, there is some A st JA=J - 7ProofA proof of A from the hypotheses G is a finite sequence of A1,A2,...,An st
-Ai is in G
-Ai is an axiom
-Ai follows from the previous Ajs by a rule of inference
-A=An - 8L0A1 (a->(b->a))
A2 ((a->(b->c))->((a->b)->(b->c)))
A3 ((~b->~a)->(a->b))
MP From a and a->b, then b - 9Sequent Calculus-A system of proof where a proof is a finite sequence of sequents
Ass: if a is in D then D proves a
MP: from D proves a and D' proves (a->b) then DuD' proves b
DT: from Du{A} proves B infer D proves (A->B)
PC: from Du{~A} proves B and D'u{~A} proves ~B then DuD' proves A - 10ConsistentG is consistent if, for no a, both G proves a and G proves ~a
- 11Maximal ConsistentG is consistent and for all a, either G proves a or G proves ~a
- 12Term-every variable
-every constant
-if t1,...,tk terms, then so if fn(k)(t1,...,tk) - 13Pred Atomic Formulastring of the form
-Pn(k)(t1,...,tk)
-t1=t2 - 14Pred Formula-atomic formula
-if A,B are formula then ~A and (A->B) are formula
-if A is a formula then for any xi ALLxiA is a formula - 15Interpretation-L structure A =
- 16Assignmentfunction v:variables -> A that extends to v*:Terms -> A
-v*(xi)=v(xi)
-v*(c)=c
-v*(f(t1,...,tk))=fA(v*(t1),...,v*(tk)) - 17Pred Valuationv*:Form -> {T,F}
-v*(P(t1,...,tk))= T if PA(v*(t1),...,v*(tk)), F otherwise
-v*(t1=t2)=T if v*(t1)=v*(t2)
-v*(~A)=T and v*(A->B) as expected
-v*(ALLxiA)=T iff v*'(A)=T for all assignments v' agreeing with v except possibly at xi - 18Validity-B logically valid if A models B[v] for all A and for all v
-B is satisfiable if there exists an A and a v st A models B[v]
-G proves B if for all A and all v st A models g[v] for all g in G, then A models B[v] - 19FreeThe occurrence x in A is free if
-A is atomic
-A=~B and x is free in B
-A=B->C and x is free in B or C
-A=ALLxiB and x is free in B and x does not equal xi - 20Sentenceif no free variables
- 21t is free for xi in B-if A atomic: then t is automatically free for xi in B
-if A=~B: the t is free for xi in A iff t is free for xi in B
-if A=B->C: the t is free for xi in A iff t is free for xi in B and C
-if A=ALLxjB: t is free for xi in A if i=j or if xj does not occur in t or t is free for xi in B - 22B[t/xi]the result of replacing every occurrence of xi in B by t
Informationen
- Beschreibung
- Mathematics Karteikarten am Logic: Definitions, erstellt von Joanna Engle am 12/04/2019.
- Erstellt von
- Joanna Engle
- Aufrufe
- 0
- Bewertung