Terminology Flashcards
Operator Precedence
Æ Ę ~ ^ v ->
Ü
“Fancy U”
Universe of Discourse (allowable choices)
Ż
“Fancy Z”
Set of all integers
{…-2, -1, 0, 1, 2,…}
M
“Fancy M”
Set of all muffins
Ę
“Backwards E”
Existential
“there exists”
Æ
“Upside down A”
Universal
“for all”
Predicate Calculus (Predicate Logic)
The manipulation of open statements
Negation of Quantifiers
DeMorgan’s Law for Quantifiers
~Æx d(x) = Ęx ~d(x)
~Ęx d(x) = Æx ~d(x)
Quantifiers
Quantify open statements and make them statements.
Existential and Universal quantifiers
Open Statement
Has one or more variables
Is not a statement, but becomes one when the variables are replaced by certain allowable choices (universe of discourse)
p(x): x is an integer
Dealing with Nested Quantifiers
Order matters
Read from left to right
Bound Variables
Variables with a quantifier applied to it.
Æx ( p(x) -> q(x) )
Unbound Variables
Variables with no quantifiers applied
Æx p(x) -> q(x)
If p q is a tautology, we can say…
p = q
p is logically equivalent to q
is interchangeable with…
Logical equivalence
For compound statements p and q, if p -> q is a tautology, we can say…
p logically implies q
p => q
Logically Implies
=>
Like logical equivalence but only works in one direction
Argument
A series of statements that end in a conclusion.
Can be valid or not.
Argument Structure
A bunch of premises conjoined together that lead to a conclusion.
An argument is valid…
Iff it is never possible to make the premises true but the conclusion false
Rules of Inference
Can only be applied of they match the WHOLE form of each premise they are being applied to.
Yield results in one direction but not necessarily both directions (are logical implications)
p
p -> q
________
:. q
(p ^ (p -> q)) -> q
Which is a tautology, so
p ^ (p -> q) => q
*this structure holds for all rules of inference
Theorem
A statement that can be shown to be true
Proof
A valid argument that establishes the truth of a theorem.
Lemma
A less important theorem that is used to prove other results.
Axiom
A statement that can be assumed to be true.
These are fundamental building blocks.
Conjecture
Something we believe to be true but has not yet been proven.
Informal Proof
Multiple rules of interference in one step, steps are skipped, rules or axioms not explicitly stated.
Proof by Contraposition
To prove p => q, Start with only ~q and use that to derive ~p.
Negate conclusion, then derive premise.
Proof by Contradiction
To show that p=> q, add ~q to our premise and then derive a contradiction.
Even
An integer n, is said to be even if there exists some integer k such that n = 2k.
Odd
If n is not even, we call it odd, and then there exists some integer k such that n = 2k +1.
Closure for the set of all integers.
A set is said to be closed under an operation if that operation takes elements of that set as input and only generates that set as output.
Ż is closed under +, -, *
Ż is not closed under /
