### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Key terms and concepts. both from the reading and the lectures. CS 225

OSU

GPA 3.8

### View Full Document

## About this Document

## 89

## 1

## Popular in Discrete Structures in Computer Science

## Popular in Computer science

This 3 page Class Notes was uploaded by Tiffani Friesendorf on Friday September 23, 2016. The Class Notes belongs to CS 225 at Oregon State University taught by Samina Ehsan in Fall 2016. Since its upload, it has received 89 views. For similar materials see Discrete Structures in Computer Science in Computer science at Oregon State University.

## Popular in Computer science

## Reviews for Key terms and concepts. both from the reading and the lectures.

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/23/16

Discrete Mathematics CS225 Terms and concepts: week 1 (book and lecture) Statement/Proposition:Adeclarative statement that is true or false, but not both. • 2 + 2 = 4 is a statement because it is always true. • x + y > 0 is not a statement. Depending on the values of x and y this statement can sometimes be true, and other times be false. Logical Operators: • ¬❑ = “not p” or “it is not the case that p” • ❑∧❑ is and. (Blocks are in place of numbers or symbols to denote values) ◦ p∧q read “p and q” ▪ conjunction of p and q ◦ In most cases, but translates the same way as and. ▪ p but q means: p and q. ◦ Neither p nor q means: ~p and ~q. • ❑∨❑ is or. ◦ p∨q Is read “p or q” ▪ disjunction of p and q p∨q ◦ is considered an inclusive or meaning “p or q or both.” ◦ p⊗q , (p∨q)∨❑∼(p∧q) , p XOR q all denote exclusive or meaning “p or q but not both.” Conditional Statements • p→q : Implication operator. “If p then q.” ◦ If/then is the last logical operator in the order of operations. ◦ To say “p implies q” is misleading. ◦ p is the hypothesis/antecedent. ◦ q is the conclusion/consequent. ◦ This is called a conditional statement because the truth of q is dependent on the truth of p. • Aconditional statement can only be stated as false if the hypothesis is true and the conclusion is false. ◦ If hypothesis is false, you do not know if the conclusion would be true if the hypothesis is true. ◦ In a truth table, only the row with the hypothesis being true and the conclusions being false should be labeled as false. The rest are labeled as true, including any occurrence of the hypothesis being false. • Vacuously true or true by default: when a conditional statement is true due to the hypothesis being false. • The contrapositive of a conditional statement “if p then q” is “if ~q then ~p” ◦ Aconditional statement is logically equivalent to its contrapositive. ◦ Contrapositives are sometimes easier to work with than the original statement. • The converse and inverse of a conditional statement ◦ Neither are logically equivalent to the conditional statement. ◦ For conditional statement “If p then q” ▪ The converse is: “If q then p.” ▪ The inverse is: “If ~p then ~q.” • Biconditional of p and q is “p if, and only if, q” ◦ p↔q or iff ◦ True if p and q have the same truth values, and false if p and q have opposite truth values. ◦ Equal with the if/then operator in order of operations. Order of operations for logical operators: 1. ~ Negations first. 2. ∧∨ Evaluate and and or second. 3. →↔ Evaluate if/then and biconditional statements last. • NOTE: ( ) Parentheses take precedence. Logical Equivalence • Two statement forms are logically equivalent if, and only if, they have identical truth values for each possible substitution of statements for their statement variables. ◦ p = “Dogs bark” q =”Cats meow.” ▪ No matter the order, both of these statements are true, soand q∧p are logical equivalents. • In a Truth table they would have the exact same truth values p q p∧q q∧p T T T T T F F F F T F F F F F F • Two statements are logically equivalent if, and only if, they have logically equivalent forms when identical component statement variables are used to replace identical component statements. ◦ Testing whether statement forms P and Q are logically equivalent: • Construct a truth table with one column for the truth values of P and another column for the truth values of Q. • 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. • 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. • If in any row their truth values differ, they are not logically equivalent. 2 useful equivalents: • Distributivity: ◦ p∨(q∧r)≡(p∨q)∧(p∨r) ◦ p∧(q∨r)≡(p∧q)∨(p∧r) • De Morgan’s Law: ◦ ¬(p∧q)≡¬p∨¬q ◦ ¬(p∨q)≡¬p∧¬q ◦ Be careful: De Morgan’s Laws apply only to complete statements, not sentence fragments. ▪ There must be a complete statement on both sides of the and or or. • Example of De Morgan’s Law: ◦ p: Jim is tall and Jim is thin. ◦ ~p: im is not tall or Jim is not thin. • Not an example because there is not a full statement on either side of the and or or: ◦ p: Jim is tall and thin. ◦ ~p: Jim is not tall and thin. Tautologies and Contradictions • Tautology:Astatement form that is always true regardless of the truth values of the statements the variables (p, q, etc) represent. • Contradiction:Astatement form that is always false regardless of the truth values of the statements the variables represent. • The truth of a tautological statement and the falsity of a contradictory statement are due to the logical structure of the statements themselves and are independent of the meanings of the statements. Necessary and Sufficient Conditions • r is a sufficient condition for s means “if r then s.” • r is a necessary condition for s means “if not r then not s.”

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.