Logic and Proofs Flashcards
What is a proposition?
is a statement that is either true or false.
What is logic?
is the study of formal reasoning
What is a truth value?
is a value indicating whether the proposition is actually true or false.
What is a compound proposition?
is created by connecting individual propositions with logical operations
What is a logical operator
Combines propositions using a particular composition rule.
Conjunction operator.
“AND” both must be true
What does a truth table do?
shows the truth value of a compound proposition for every possible combination of truth values for the variables contained in the compound proposition.
Disjunction operator
“OR” (∨) operation and evaluates to true when one or both of the propositions are true.
What is the difference between inclusive and exclusive “or” operator?
exclusive or: evaluates to true when p is true and q is false or when q is true and p is false.
inclusive or: is the same as the disjunction (∨) operation and evaluates to true when one or both of the propositions are true.
How to use the negation operator to search for something specific online?
Type: [what you want to search] and “-“ [what you don’t want to search]
What does the negation operator do? “-“
acts on just one proposition and has the effect of reversing the truth value of the proposition. The negation of proposition p is denoted ¬p and is read as “not p”.
How is the conditional operator represented?
The conditional operation is denoted with the symbol →. The proposition p → q is read “if p then q”..
What are p and q known as in a conditional proposition?
In p → q, the proposition p is called the hypothesis, and the proposition q is called the conclusion.
What is the converse of a conditional proposition?
The “reverse” of proposition. The converse of p → q is q → p.
What is the contrapositive of a conditional prop?
The reverse and negation of both props
The contrapositive of p → q is ¬q → ¬p.
What is the inverse of a conditional prop?
The negation of both props.
The inverse of p → q is ¬p → ¬q..
What is a programming implementation of using conditional operation?
Data Validation: Ensuring that two pieces of data meet the same criteria. For example, validating that a password and its confirmation match.
What is the biconditional operation?
biconditional operation
If p and q are propositions, the proposition “p if and only if q” is expressed with the biconditional operation and is denoted p ↔ q. .
What is a tautology?
A compound proposition is a tautology if the proposition is always true, regardless of the truth value of the individual propositions that occur in it.
What is a contradiction?
A compound proposition is a contradiction if the proposition is always false, regardless of the truth value of the individual propositions that occur in it.
What does it mean for two compound propositions to be logically equivalent?
Two compound propositions are said to be logically equivalent if they have the same truth value regardless of the truth values of their individual propositions.
What does De Morgan’s laws show you how to do?
De Morgan’s laws are logical equivalences that show how to correctly distribute a negation operation inside a parenthesized expression.
What are the laws of propositional logic supposed to do?
laws of propositional logic to simplify the propositions making them easier to evaluate.
What is a predicate?
A logical statement whose truth value is a function of one or more variables is called a predicate.
What is the domain of a variable?
The domain of a variable in a predicate is the set of all possible values for the variable.
What is a universal quantifier / universally quantified statement?
The symbol ∀ is a universal quantifier, and the statement ∀x P(x) is called a universally quantified statement.
Why is ∀x P(x) a proposition?
because it is either true or false. ∀x P(x) is true if and only if P(n) is true for every n in the domain.
What is a counterexample?
A counterexample for a universally quantified statement is an element in the domain for which the predicate is false.
What is an existential quantifier / existentially quantified statement?
The symbol ∃ is an existential quantifier, and the statement ∃x P(x) is called an existentially quantified statement.
What is a theorem?
A theorem is a statement that can be proven to be true.
What is a proof?
A proof consists of a series of steps, each of which follows logically from assumptions or from previously proven statements, whose final step should result in the statement of the theorem being proven.
What are axioms?
The proof of a theorem may make use of axioms, which are statements assumed to be true.
Explain proof by exhaustion.
If the domain of a universal statement is small, it may be easiest to prove the statement by checking each element individually. A proof of this kind is called a proof by exhaustion.
What is a counterexample?
A counterexample is an assignment of values to variables that shows that a universal statement is false.
What is a direct proof?
In a direct proof of a conditional statement, the hypothesis p is assumed to be true and the conclusion c is proven as a direct result of the assumption.
What is proof by contrapositive?
A proof by contrapositive proves a conditional theorem of the form p → c by showing that the contrapositive ¬c → ¬p is true.
What is proof by contradiction (inderect proof)?
A proof by contradiction starts by assuming that the theorem is false and then shows that some logical inconsistency arises as a result of this assumption.
What is proof by cases?
A proof by cases of a universal statement such as ∀x P(x) breaks the domain for the variable x into different classes and gives a different proof for each class.
What is the parity of a number?
The parity of a number is whether that number is odd or even.
