INTECH 1100 REVIEWERR

The study of discrete, mathematical objects and Structures.

DISCRETE MATHEMATICS

defined as the study of correct reasoning.

Logic

allows you to give a temporary name to what you are seeking so that you can perform concrete computations with it to help discover its possible values.

variable

3 types of statement

universal, conditional, existential

certain property is true FOR ALL elements in a set.

Universal Statement

IF one thing is true THEN some other things also has to be true

Conditional Statement

THERE IS at least one thing for the property is true.

Existential Statement

a statement that is both universal and conditional.

universal conditional statement

first part says that a certain property is true for all objects of a given type, and it is existential because its second part asserts the existence of something.

EXAMPLE: For all real numbers r, there is an additive inverse for r.

universal existential statement

a statement that is existential because its first part asserts that a certain object exists and is universal because its second part says that the object satisfies a certain property for all things of a certain kind.

EXAMPLE: There is a positive integer that is less than or equal to every positive integer.

Existential Universal Statement

The central concept of deductive logic is the concept of argument form. An argument is a sequence of statements aimed at demonstrating the truth of an assertion.

Logical Form and Logical Equivalence

The assertion at the end of the sequence.

Conclusion

Also known as proposition - it is a sentence that is true or false but not both.

Statement

what is the meaning of this symbol ~

NOT

what is the meaning of this symbol Ʌ

And

what is the meaning of this symbol V

Or

symbol of Negation of p

“~p”

symbol of Conjunction of p and q .

“p Ʌ q”

symbol Disjunction of p and q.

“p V q”

a breakdown of a logic function by listing all possible values the function can attain.

Truth Values

an expression made up of statement variables (such as p, q, and r) and logical connectives (such as ~p, Ʌ, and V) that becomes a statement when actual statements are substituted for the component statement variables.

statement form (or propositional form)

Two statement forms are called _______if, and only if, they have identical truth values for each possible substitution of statements for their statement variables.

Logical Equivalence

The negation of an and statement is logically equivalent to the or statement

The negation of an or statement is logically equivalent to the and statement

De Morgan’s laws

is a statement form that is always true

Tautology

Contradiction

is a statement form that is always false

A _____ is a statement that can be written in the form “If P then Q,” where P and Q are sentences.

conditional statement

the symbol"→ " means

if then

In a symbol "p → q”. p is ____ and q is _____?

p is called the hypothesis
q is called the conclusion.

in and "if-then" statement it will get false when the hypothesis is ___ and the conclusion is ___

hypothesis (p) is true and conclusion (q) is false

the symbol for" Negation of a Conditional
Statement"

The negation of "if p then q" is logically equivalent to "p and not q

- Remove the if and then in a statement and negate the (q)

______ is logically equivalent to its contrapositive.

Conditional statement

what do you call to this kind of statement?
∼q →p

Contrapositive of a Conditional Statement

what do you call to this kind of statement?

"If q then p”

q → p,

converse

what do you call to this kind of statement?

"If ∼p then ∼q”

∼p → ∼q

inverse

A conditional statement and its converse are ?

not logically equivalent.

A conditional statement and its inverse?

not logically equivalent.

The converse and the inverse of a conditional statement ?

logically equivalent to each other.

↔ is a symbol of?

IF and ONLY IF

a sequence of statements ending in a conclusion.

Argument

is a sequence of statement forms

Argument form

statements in an argument and all statement forms in an argument form, except for the final one and this called?

premises (or assumptions or hypotheses).

The final statement or statement form is called the?

conclusion

An argument form is called valid when both premise and conclusion is?

true

the symbol" •" which is read as?

therefore

A row of the truth table in which all the premises are true

critical row

a logical form or guide consisting of premises (or hypotheses) and draws a conclusion

rule of inference

An argument form consisting of two premises and a
conclusion

modus ponens

Modus Tollens

Generalization

specialization

Elimination

Transitivity

Proof by Division into Cases

a sentence with variables that becomes a statement when specific values are substituted for the variables.

Predicate

a predicate variable is the set of all values that may be substituted in place of the variable.

Domain

Some ways to express the symbol ∀ in words are ______.

for all, for any.

Some ways to express the symbol ∃ in words are ______.

there exists, at least one.

A statement of the form ∀x ∈ D, Q(x) is true if, and only if,Q(x)is __________ for ______ .

A statement of the form ∀x ∈ D, Q(x) is true if, and only if,Q(x) is true for every x in D.

A statement of the form ∃x ∈ D such that Q(x) is true if, and only if, Q(x) is ______ for _____.

A statement of the form ∃x ∈ D such that Q(x) is true if, and only if, Q(x) is true for at least one x in D.

Let Q(n) be the predicate "n is a factor of 8." Find the truth set of Q(n) if the domain of n is the set Z+ of all positive integers

The truth set is {1,2,4,8} because these are exactly the positive integers that divide 8 evenly.

Let Q(n) be the predicate "n is a factor of 8." Find the truth set of Q(n) if the domain of n is the set Z of all integers.

The truth set is {1,2,4,8,−1,−2,−4,−8} because the negative integers −1,−2,−4, and −8 also divide into 8 without leaving a remainder.

Convert "All human beings are mortal" using universal quantifiers.

∀ human beings x , x is mortal.

Convert "For all x in the set of all human beings, x is mortal" using universal quantifiers.

∀x ∈ H, x is mortal

Rewrite the following statement using an equivalent non formal definition:

∀x∈R, x^2 ≥0

All real numbers have nonnegative squares.

Rewrite the following statement using an equivalent non formal definition:

∀x∈R,x^2 does not equal -1

All real numbers have squares that do not equal -1.

Rewrite the following statement using an equivalent non formal definition:

∃m ∈ Z+ such that m^2 = m

There is a positive integer whose square is equal to itself.

Rewrite the statement formally. Use quantifiers and variables.

All triangles have three sides.

∀ triangles t , t has three sides.

Rewrite the statement formally. Use quantifiers and variables.

No dogs have wings.

∀ dogs d, d does not have wings.

Rewrite the statement formally. Use quantifiers and variables.

Some programs are structured.

∃ a program p such that p is structured.

Rewrite the following statement informally, without quantifiers or variables.

∀x∈R, if x>2 then x^2 >4.

For all real numbers x, if x is greater than 2 its square is greater than 4.

Rewrite each of the following statements in the form
∀ ________, if ______ then _____ .

If a real number is an integer, then it is a rational number.

∀ real numbers x, if x is an integer then x is a rational number.

Rewrite each of the following statements in the form
∀ ________, if ______ then _____ .

All bytes have eight bits.

∀ x, if x is a byte then x has 8 bits.

Rewrite each of the following statements in the form
∀ ________, if ______ then _____ .

No fire trucks are green.

∀ x, if x is a firetruck then x is not green.

Rewrite the following statement in the two forms, all squares are rectangles.:

"∀x, if _____ then ______" and
"∀ _______ x, ______":

∀x, if x is a square then it is a rectangle.
∀ squares x, x is a rectangle.

Indicate which of the following statements are true and which are false. Justify your answers as best as you can.
a. Every integer is a real number.
b. 0 is a positive real number.
c. For all real numbers r, −r is a negative real number.
d. Every real number is an integer.

a. True, the statement is true. The integers correspond to certain points on the number line and the real numbers correspond to all the points on the number line.
b. False, 0 is neither positive or negative.
c. False, since - (-2) equals a positive 2.
d. False, for instance 1/2 is a real number but not an integer.