DM I: Mathematical Statements

https://discrete.openmathbooks.org/dmoi3/sec_intro-statements.html

statement

any declarative sentence which is either true or false

atomic

describes a statement that cannot be divided into smaller statements

molecular

describes a statement that is not atomic, i.e. it can be divided into smaller statements

5 logical connectives

negation (“not”)
conjunction (“and”)
disjunction (“or”)
implication (“if…, then…”)
biconditional (“if and only if”)

negation

¬P, “not P”

conjunction

P∧Q, “P and Q”

disjunction

P∨Q, “P or Q”

implication / conditional

P→Q, “if P then Q”

True if P is false or Q is true (or both).

Only false if P is true and Q is false.

We make no claim about the conclusion Q if the hypothesis P is false.

If the conclusion Q is true, we make no claim about whether the hypothesis P was the cause.

biconditional

P↔Q, “P if and only if Q”

true if P and Q are both true, or both false

In the implication P→Q, what is P?

hypothesis / antecedent

In the implication P→Q, what is Q?

conclusion / consequent

converse

The converse of P→Q is Q→P.

These two are not logically equivalent (they can have different truth values).

contrapositive

The contrapositive of P→Q is ¬Q→¬P.

These two are logically equivalent (they are either both true or both false).

P↔Q is logically equivalent to…

(P→Q)∧(Q→P)

Equivalencies to “if I dream, then I am asleep”

1. I am asleep if I dream.

2. I dream only if I am asleep.

3. In order to dream, I must be asleep.

4. To dream, it is necessary that I am asleep.

5. To be asleep, it is sufficient to dream.

6. I am not dreaming unless I am asleep.

“P is necessary for Q”

Q→P

“P is sufficient for Q”

P→Q

“P is necessary and sufficient for Q”

P↔Q

free variable

a variable about which nothing has been specified

predicate

a sentence that contains variables

two main quantifiers

universal (“for all”, “every”) and existential (“there exists”, “there is”)

universal quantifier

“for all”, “every”
∀x(x≥0), “for all x such that x is greater than or equal to zero”

existential quantifier

“there exists”, “there is”
∃x(x<0), “there exists x such that x is less than zero”

In discrete mathematics, we almost always quantify over the _____ numbers.

In discrete mathematics, we almost always quantify over the natural numbers (0, 1, 2, 3, …).

¬∀xP(x) is equivalent to ____.

∃x¬P(x)

¬∃xP(x) is equivalent to ____.

∀x¬P(x)

S(x)→R(x) is, by convention, implicitly quantified as _______.

∀x(S(x)→R(x))