Karteikarten
Logic Theory
Karten in diesem Stapel (81)
- 1What is logic?A branch of Mathematics, The science of reasoning - Reasoning conducted or assessed according to strict principles of validity
- 2What was Aristotle's contribution to logic?He wrote The Organon which is a collection of 6 works on logic. He categorised syllogisms: arguments with premises
- 3What is a premise?A statement or proposition from which another is inferred or follows as a conclusion
- 4Who were The Stoics?School of philosophers that worked on propositional logic, conditional statements, meanings and truth
- 5George BooleCreated boolean algebra, algebra of thought by reducing logical though to equations
- 6Boolean algebraAlgebra on collections, combination of ideas using AND, OR and NOT
- 7Set theorymembership, union, intersection, complement, subset, empty set, cardinality
- 8PropositionPart of a sentence that asserts that something is or is not the case
Has a truth value - 9TautologyA formula that is true regardless of the truth values assigned to the propositional variables
- 10Logical equivalenceTwo formulae are logically equivalent if they receive the same truth value regardless of the truth values assigned to the propositional variables
- 11ContradictionA formula that is false under all interpretations
- 12ContingentA formula that is true in some and false in other interpretations
- 13InterpretationSet of answers with specific propositional variables
- 14De Morgan's LawsExpressing conjunction and disjunction in terms of each other by negating them
- 15Rule of assumption (A)We can introduce at any stage of an argument any proposition we choose as an assumption of the argument
- 16Modus ponendo ponens (MPP)P → Q
P
Therefore, Q - 17Modus tolendo tollens (MTT)P → Q
-Q
Therefore, -P - 18Double negation (DN)--P
Therefore, P
P
Therefore, --P - 19AND Introduction (&I)Given any two premises permits to derive their conjunction as conclusion
P
Q
P ʌ Q - 20AND Elimination (&E)Given any conjunction as premise permits to derive either conjunct as a conclusion
P ʌ Q
P
Q - 21OR Introduction (vI)Given any proposition as premise permits us to derive the disjunction of that proposition and any proposition as conclusion
P
P v Q - 22Reducio Ab Absurdum (RAA)This rule rests on the natural principle that if a contradiction can be deducted from a proposition A, A cannot be true, so we are entitled to affirm his negation, -A
- 23Conditional Proof (CP)Use a conditional premise with it's antedecent or negation of it's consequent to obtain a conclusion
- 24Predicate calculusA new formal language where symbols replace words, more mathematical
- 25Universe of DiscourseThe domain that we are talking about
It can be defined or undefined - 26QuantifiersFor all ∀x
There exists ∃x - 27Everything with F has G∀x (Fx → Gx)
- 28Nothing with F has G∀x (Fx → -Gx)
- 29Something with F has G∃x (Fx ʌ Gx)
- 30Something with F has not G∃x (Fx ʌ -Gx)
- 31Are there different sizes of infinity?The Continuum Hypothesis: is there another number
size of natural numbers < x < size of real numbers?
Godel shows that this cannot be disproved from the Zemelo-Fraenkel set theory, Cohen showed that it cannot be proven from the same theory
Therefore CH is independent of ZF - 32Is the size of the set of natural numbers the same as the size of the set of prime numbers?Yes, it is because we can define a 1-1 correspondence between the two sets
Map n to the nth prime - 33How many rows will a truth table have?2^n, n = number of propositions
- 34Reflexive binary relationxRx
- 35IrreflexivexRy implies y is not equal to x
- 36SymmetricxRy implies yRx
- 37AntisymmetricxRy and yRx implies x=y
- 38TransitivexRy and yRz implies xRz
- 39Quantifier orderIs important as different order has different meaning
- 40Everyone knows someone∀x ∃y st Kxy
- 41Someone knows everyone∃x st ∀y Kxy
- 42Someone is known by everyone∃x st ∀y Kyx
- 43Every person x knows someone who doesn't know x∀x ∃y st (Kxy ʌ -Kyx)
- 44There is someone x who knows everyone who knows x∃x st ∀y (Kxy → Kyx)
- 45ValidityThe inference is valid when the conclusion necessarily follows from the premises
If it takes a form that makes it impossible for the premises to be
true and the conclusion nevertheless to be false. - 46SoundnessWhen the premises are valid and true
- 47DeductionUses MPP to reason from rule and specific case to conclusion, it is valid
- 48Theorem proversDavis (sum of two even number is even), The Logic Theory Machine (proved axioms from Pincipia Mathematica by using 3 deduction rules), Four-colour theorem (You can colour the countries in 4 different colours and the same colour will never share a border)
McCune (Organized Techniques for Theorem-proving and
Effective Research - inference rules infer a clause, if it's new and interesting it gets saved) - 49InductionFrom many specific cases to general rule, it is not valid
- 50Machine learningperforms generalisation, often a training set and test set are used
- 51Supervised learningThe computer is presented with labelled training data (example input and outputs), goal is to learn general rule that maps inputs to outputs
- 52Unsupervised learningNo labels are given to the learning algorithms, can be a goal in itself (finding hidden patterns) or a means towards an end (future learning)
- 53Reinforcement learningA computer program interacts with a dynamic environment in which it must perform a certain goal to maximise a reward, without a teacher explicitly telling it whether it has come close to a goal
- 54Abduction (Hypothesis)Abduction reasons from specific case and rule to a possible explanation for the case, it is not valid
- 55Expert systemsUse if-then rules to perform chains of abductive inference (Dendral: identifying unknown organic molecules, Mycin: diagnosing infectious diseases)
- 56Mathematical InductionDeductive reasoning, for a given property P that it is true, we would show P+1is also true so therefore it is true for all P
- 57Analogical inferenceCase based reasoning
- 58Classical logicPropositional, first-order logic
By the rules, used by computers, in mathematics - 59Informal logicCritical thinking, argumentation theory
Few rules, more 'street smart', used in natural communication - 60Relations in predicate logicN-place predicates, depends on how many things you're talking about
- 61Universal elimination (UE)from ∀x Fx infer Fa
- 62Existential elimination (EE)from ∃x Fx infer Fa
- 63Existential introduction (EI)from Fa infer ∃x Fx
- 64INCLUSIVE OR disjunctionTrue when one or both are true
x + y (arithmetic form), V (logic) , U (sets) - 65EXCLUSIVE ORTrue when one is true
⊻ (logic) - 66AND conjunctionTrue only when both true
xy (arithmetic), ʌ (logic), ∩ (sets) - 67NOTNegated, changes the value
- 68Commutative lawx + y = y + x
xy = yx
(arithmetic form, for sets change + to U and * to ∩, for logic change + to V and * to ʌ) - 69Associative lawx + (y + z) = (x + y) + z
x(yz) = (xy)z
(arithmetic form, for sets change + to U and * to ∩, for logic change + to V and * to ʌ) - 70Distributive lawx(y + z) = xy + xz
(arithmetic form, for sets change + to U and * to ∩, for logic change + to V and * to ʌ) - 71What is the analogue of 0 in set theory?x + 0 = x
x * 0 = 0
Analogue of 0 in set theory is an empty set - 72Are there any differences between Boolean algebra and standard arithmetic?Binary, involves only certain type of laws, uses or, and, not
- 73IMPLIESFalse only if T → F
→ - 74IF AND ONLY IF (IFF)True if both values the same
↔ - 75NeccesaryQ is necessary for P is equivalent to "P cannot be true unless Q is true"
P → Q - 76SufficientP is sufficient for Q is to say that, in and of itself, knowing P
to be true is adequate grounds to conclude that Q is true - 77IndependenceA sentence σ is independent of
a given first-order theory T if T neither proves nor
refutes σ; that is, it is impossible to prove σ from
T, and it is also impossible to prove from T that σ
is false - 78Axiom/PostulateStatement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments
- 79Rule of inferenceTransformation rule, a function which takes premises, analyses their syntax, and returns a conclusion
MPP, MTT - 80TheoremA general proposition not self-evident but proved by a chain of reasoning; a truth established by means of accepted truths
- 81ProofSufficient evidence or a sufficient argument for the truth of a proposition
Informationen
- Beschreibung
- Argumentation and Computing (Logic) Karteikarten am Logic Theory, erstellt von Neja Cesnik am 30/04/2018.
- Erstellt von
- Neja Cesnik
- Aufrufe
- 20
- Bewertung