Discrete Math

Statement

Is a sentence that is true or false but not btoh

conjunction

The compound statement of hte joining of p and q to be “p and q”. It is true when and only when both p and q are true

disjunction

The compound statement formed by joining p and q using "or". It is true when at least one of p or q is true.

Logically equivalent

Statements that have the same truth value in every possible scenario.

Testing whether two statement forms P and Q are logically equivalent

1. Construct a truth table with one column for the truth values of P and the other Column for the truth value of Q.

2. Check each combination of truth values of the statement variables to see whether the truth value of P is the same as the truth value of Q

   1. If in each row the truth value of P is the same as the truth value of Q, then P and Q are logically equivalent

   2. If in some row P has a different truth value from Q, then P and Q are not logically equivalent

tautology

statement form that is always true regardless of the truth values regardless of the truth values of the individual statements substituted for its statement variables.

contradiction

statement form that is always false regardless of the truth values regardless of the truth values of the individual statements substituted for its statement variables.

Commutative Laws

^p∧ q = q /\ p & p\/ = q\/ p

Associative Laws

(p/\q)/\r= p/\(q/\r)

distributive laws

p/\(q\/r) = (p/\q)\/(p/\r)

identity laws

p/\ t= p & p\/c=p

negation laws

double negative law

-(-p) =p

idempotent laws

p/\p= p & p\/p=p

Universal bound laws

p\/t=t and p/\c=c

De morgans laws

-(p/\q)= -p \/-q and -(p\/q)= -p /\ -q

absorption laws

p \/(p/\ q) = p and p /\(pV q) =p

contrapositive of a conditional statement of the form if p then q is

if not q then not p

converse of if p then q is

if q then p

the inverse of if p then q is

if not p then not q

Testing an argument form for validity

1. Identify the premises and conclusion of the argument form.

2. Construct a truth table showing the truth values of all the premises and the conclusion.

3. A row of the truth table in which all the premises are true is called a critical row. If there is a critical row in which the conclusion is false, then it is possible for an argument of the given form to have true premises and a false conclusion, and so the argument form is invalid. If the conclusion in every critical row is true, then the argument form is valid.

A predicate

is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables.

The domain

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

Set Notation

A set is a collection of distinct objects, written with curly braces. For example {1, 2, 3}. The symbol ∈ means "is an element of" so 2 ∈ {1,2,3} is true. ∉ means "is not an element of."

Subset (⊆)

A is a subset of B if every element of A is also in B. Written A ⊆ B. The key thing is that A can be equal to B and it still counts. So {1,2} ⊆ {1,2,3} and also {1,2,3} ⊆ {1,2,3} are both true.

Proper Subset (⊂)

Same as subset BUT A cannot equal B. A must be strictly smaller. So {1,2} ⊂ {1,2,3} is true, but {1,2,3} ⊂ {1,2,3} is false.

Setup Rule

How do you start every truth tree?

Write all PREMISES then add ~CONCLUSION (negate the conclusion)

AND Rule (∧)

p ∧ q — branch or stack?

Stack

OR Rule (∨)

p ∨ q — branch or stack?

Branch

Conditional Rule (→)

p → q — what do you do first?

Convert: p→q ≡ ~p∨q then BRANCH

Negation of AND

~(p ∧ q) — what does this become?

De Morgan's: ~(p∧q) ≡ ~p∨~q then BRANCH

Negation of OR

~(p ∨ q) — what does this become?

De Morgan's: ~(p∨q) ≡ ~p∧~q then STACK

Negation of Conditional

~(p → q) — what does this become?

Negation of Conditional

~(p→q) ≡ p ∧ ~q then STACK p ~q

Double Negation

~~p — what does this simplify to?

~~p ≡ p Just write p and continue (no branching needed)