6D Lecture 1B: Logic and Propositions

proposition

statement that is either true or false

is x>5 a proposition?

yes, it is true.

truth value

the label we attach to a proposition, either true or false

compound proposition

proposition that connects simple proposition using logical operations

conjunction

• a compound proposition with the symbol ^ (and)

• true when both p and q are true

• if p or q is false, the conjunction as a whole is false

when is p^q false

when p or q is false

truth table

table that shows every possible combo of true or false for the variables, and the result

disjunction

• a compound proposition with the symbol v (or)

• has an inclusive and exclusive or

• the proposition is only false when both p and q are false, but is true when either p or q is true (or both)

what is the difference between inclusive or and exclusive or? which one should you assume?

• inclusive or includes the case where both p and q are true

• exclusive or is only true when p or q is true, not both

• assume or is always inclusive unless stated otherwise

negation

• symbol that flips the truth value (¬)

• if p is true, ¬p is false

• if p is false. ¬p is true

• instead of working with 2 variables p and q, it only operates on a single proposition like p and changes its state instead of comparing 2 propositions

what would a truth table for negation ¬ look like?

2 rows, if p is true ¬p is false and vice versa

what is the order of precedence when solving combined operations

1) ¬ 2) ^ 3) v 4) → 5) ≣

evaluate the order in which p v ¬q ^ r would be solved

p v [(¬q)^r]

logical equivalence

• when 2 propositions have the same truth value for every possible input combo

• check by making a truth table for each proposition and comparing the final result columns, match if they’re equivalent

which notation shows two propositions are logically equivalent

≣

De Morgan’s first law

• not (p and q) = not p, or not q

• ¬(p ^ q) = ¬p v ¬q

De Morgan’s second law

• not (p or q) = not p, and not q

• ¬(p v q) = ¬p ^ ¬q

evaluate using De Morgan’s Law: “Its not the case that its hot AND sunny”

its not hot, or its not sunny

conditional operation

• →, if p then q

• p is the hypothesis, q is the conclusion

• p→q is false when p is true but q is false

• when p is false, the conditional is automatically true

• its kinda like a contract between two parties

what is the converse of p → q

• q → p

what is the contrapositive of p→q

• ¬q → ¬p

• flip and negate to make it equivalent to the original

what is the inverse of p → q

• ¬p → ¬q

• negate both, equate it to the converse

which conditionals are logically equivalent to p→q

the contrapositive

biconditional

• p ≣ q

• p if and only if q/p iff q

• true when p and q have the same truth value (both T or both F)

when is p ≣ q true

when they have the same truth value, either both true or both false

predicate

• statement whose truth value depends on one or more variables

• outputs T or F

• p(x) isn’t a proposition but becomes one when you plug in a value like p(5) it becomes one because it has a definite truth value

• can have multiple variables like Q(x,y) = x² = y so Q(5,25) would be true in that case

why is “x is odd” not a proposition on its own

because you don’t know what x is so you can’t determine if the statement is true or false, which is why p(x) isn’t a proposition

domain

set of all values x is allowed to be

quantifiers

• ∀(for all)

• ∃(there exists)

• symbols that specify how many elements in a given domain satisfy a predicate or condition

essential quantifier, what does ∃x P(x) mean in plain english

• ∃

• there exists at least one x such that P(x) is true

• true so long as you can find one value in the domain satisfying P(x), false if no values in domain work

universal quantifier, what does ∀x P(x) mean in plain english

• ∀

• for all x in the domain, p(x) is true

• true if only every value in domain satisfies p(x), false otherwise

is ∃x(x+1<x) true or false for positive integers

• no, x+1 cannot be smaller than one if the integers are positive