Logic Flashcards
What is a proposition?
defn - a declaration which is either always true or always false.
eg - ‘2=2’, ‘2=3’
Truth values
True or T, if the proposition is true and False or F, if the proposition is false.
Negation
not - ¬
Conjunction
and - ∧
Disjunction
or - ∨
Implication
if…then… - →
Equivalence
if and only if - ↔
Notes about combining connectives
- Brackets show the order in which connectives are applied to build up a proposition.
- The truth values of the final proposition depend on the truth values of the propositional variables and on the bracketing.
- There may be several propositions with the same truth values.
Tautology
defn - a proposition which is always true, for all truth values of its propositional variables. Represented by ⇒.
eg. double negation law, modus ponens.
Contradiction
defn - a proposition which is always false, for all truth values of its propositional variables.
A ⇔ B
defn - if A ↔ B is a tautology, we say A is logically equivalent to B and write A ⇔ B. This means that A can be substituted for B whenever B occurs in a proposition.
Compare ↔ and ⇔
P ↔ Q is a proposition, with a truth value dependent on the truth values of P and Q.
P ⇔ Q is the assertion that P ↔ Q is a tautology. This distinction is only useful in logic.
Converse
defn - the converse of p → q is q → p
Compare → and ⇒.
P → Q is a proposition, with a truth value dependent on the truth values of its propositional variables.
P ⇒ Q is the assertion that P → Q is a tautology.
The distinction is only useful in logic.
Predicate
defn - a predicate, in the variable x from the set U, is a statement which contains the variables x and becomes a proposition when a value from U is substituted for x. A predicate can be written P(x) or P(x,y), for example.
eg - ‘z is a root of p(x)’
∀
universal quantifier - meaning ‘for all’
How do you read the following? ‘∀x ∈ R (x² ≥ 0)’
‘for all real numbers x, x² ≥ 0’. (This is a proposition and is true.)
What is the general format of a predicate P(x), with a variable x from the set U, using the universal quantifier?
∀x ∈ U (P(x))
∃
existential quantifier - ‘there exists’
How do you read the following? ‘∃x ∈ Z (2x = 1)’
‘there exists an integer x such that 2x = 1’ (This is a proposition and is false.)
What is the general format of a predicate P(x), with a variable x from the set U, using the existential quantifier?
∃x ∈ U (P(x))
