New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Key terms and concepts. both from the reading and the lectures.

by: Tiffani Friesendorf

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

Marketplace > Oregon State University > Computer science > CS 225 > Key terms and concepts both from the reading and the lectures
Tiffani Friesendorf
GPA 3.8

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Definitions and key concepts both from the lectures and the reading, to be used as a quick reference. Includes definitions and/or examples of: Statements/Propositions Logical Operators Condit...
Discrete Structures in Computer Science
Samina Ehsan
Class Notes
Discrete, Math, logic, logical, operators, propositions, Proposition Logic, Propositional Logic, conditional, contrapositive, converse, Inverse, biconditional, Logical Equivalence, distributivity, demorgan, Tautology, tautological, contradiction
25 ?




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.

Similar to CS 225 at OSU


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


Report this Material


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.”


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Jim McGreen Ohio University

"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."

Janice Dongeun University of Washington

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

Steve Martinelli UC Los Angeles

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

Parker Thompson 500 Startups

"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."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.