Mathematical Logic and Sets

Vocabulary flashcards covering mathematical logic, truth tables, connectives, implication types, basic set theory, set operations, and quantifiers.

Proposition

A statement that is True or False.

Predicate

A statement that depends on one or more variables and becomes a proposition when values are assigned to these variables.

Proposition or predicate

1 + 1=2

Proposition

Proposition or predicate

Pi =3.142 3

Proposition

Proposition or predicate

n is a prime number

Predicate

Proposition or predicate

N + m < 4

Predicate

Proposition or predicate

X²>y²

Predicate

Proposition or predicate

There exists a real number x such that x² >_ 1

Proposition

Proposition or predicate

X² +3x +2 = 0

Predicate

Proposition or predicate

All even integers greeted than 2 can be written as the sum of 2 primes

Proposition

What do we use to denote propositions

P and Q etc

How do we denote predicates

P(n) ,P(n,m) ,Q(x) etc

Free Variable

A variable that a predicate statement depends on before any specific value is assigned to it.

Statement

A mathematical statement referring to either a proposition or a predicate.

Which of the following are propositions and which are predicates

(a) There exists a real number x such that x^2 = x.

(b) x^2 - 3x - 4=0.

(c) 2^5 - 3^6.

(d) 31471 is a prime number.

(e) All natural numbers divisible by 2 are divisible by 4.

a - proposition

b -predicate

c - neither

D - proposition

e - proposition

Logical OR

A logical connective denoted by $\lor$ where the statement $P \lor Q$ is True precisely when one or both of $P$ and $Q$ are True.

Logical OR Truth Table

The truth table displaying all possible truth value combinations for $P \lor Q$.

Logical AND

A logical connective denoted by $\land$ where the statement $P \land Q$ is True precisely when both $P$ and $Q$ are True.

Logical AND Truth Table

The truth table displaying all possible truth value combinations for $P \land Q$.

Negation

The negation of a statement $P$, denoted $\neg P$ ('NOT $P$'), which is True when $P$ is False and False when $P$ is True.

Negation Truth Table

The truth table displaying the inverse truth values for $\neg P$ given $P$.

Logically Equivalent

Two statements that have the same truth tables, denoted by $P \equiv Q$ or $P \Leftrightarrow Q$.

Truth Table for De Morgan's Law $\neg(P \land Q)$ and $(\neg P) \lor (\neg Q)$

The truth table showing that $\neg(P \land Q)$ and $(\neg P) \lor (\neg Q)$ have identical truth values.

Implication

A logical conditional denoted $P \Rightarrow Q$ that is True in all cases except when $P$ is True and $Q$ is False.

Implication Truth Table

The truth table displaying all possible truth value outcomes for $P \Rightarrow Q$.

Hypothesis

The statement $P$ in an implication $P \Rightarrow Q$.

Conclusion

The statement $Q$ in an implication $P \Rightarrow Q$.

other ways of writing P implies Q

• if P , then Q

• Q if P

• P only if Q

• P is su”cient for Q

• Q is necessary for P

Negation of Implication Truth Table

The truth table for $\neg(P \Rightarrow Q)$, demonstrating that it is True only when $P$ is True and $Q$ is False.

Converse

The statement $Q \Rightarrow P$ formed by reversing the implication $P \Rightarrow Q$.

Contrapositive

The statement $\neg Q \Rightarrow \neg P$ formed from $P \Rightarrow Q$, which is logically equivalent to $P \Rightarrow Q$.

Equivalence Truth Table for $\neg(P \Rightarrow Q)$ and P ↔ (¬Q)

The truth table proving that $\neg(P \Rightarrow Q)$ is logically equivalent to $P \land (\neg Q)$.

If and Only If

A logical connective denoted by $\iff$ (or 'iff'), defining $(P \Rightarrow Q) \land (Q \Rightarrow P)$.

p if and only if q Truth Table

The truth table for $P \iff Q$, showing it is True when $P$ and $Q$ have the same truth values.

Set

A collection of objects.

Element

An object inside a set $A$, denoted by $x \in A$ .

how to denoted x is not an element of a

Empty Set

The set with no elements, denoted by $\emptyset$.

Natural Numbers

The set $\mathbb{N} = \{1, 2, 3, \dots\}$, also denoted as $\mathbb{Z}^+$. positive

Integers

The set $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$.

Rational Numbers

The set $\mathbb{Q}$ of all numbers that can be represented as $\frac{a}{b}$ for integers $a$ and $b$ with $b \neq 0$.

Real Numbers

The set $\mathbb{R}$ of all numbers that can be represented as a finite or infinite decimal expression.

Irrational Numbers

Real numbers that are not rational.

Subset

A set $A$ is a subset of $B$, written $A \subseteq B$, if and only if $x \in A \Rightarrow x \in B$.

Proper Subset

A subset $A \subseteq B$ where $A \neq B$, denoted $A \subset B$.

Equal Sets

Two sets $A$ and $B$ that contain exactly the same elements, defined as $A \subseteq B$ and $B \subseteq A$.

Universal Set

A reference set $U$ for which all sets under consideration in a given context are subsets.

Intersection

The set $A \cap B = \{x \in U \mid x \in A \text{ and } x \in B\}$.

Disjoint Sets

Two sets $A$ and $B$ whose intersection is empty ($A \cap B = \emptyset$).

Union

The set $A \cup B = \{x \in U \mid x \in A \text{ or } x \in B\}$.

Set Difference

The set $A \setminus B = \{x \in U \mid x \in A \text{ and } x \notin B\}$.

Complement

The set $A^c = \{x \in U \mid x \notin A\}$.

quantifiers

used to turn predicates into propositions

Existential Quantifier

The notation $\exists x \in A, P(x)$, meaning 'there exists an element $x$ of $A$ such that $P(x)$ is true'.

Universal Quantifier

The notation $\forall x \in A, P(x)$, meaning 'for all elements $x$ of $A$, $P(x)$ is true'.

Bound Variable

A variable in a statement that is introduced by a quantifier, making its truth value no longer freely dependent on that variable.

negation of there exists

for all

negation of for all

theres exists

negation of P ^ Q

not p V not q

Negation of p implies Q

P and not q