Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
46 Cards in this Set
- Front
- Back
Proposition |
A proposition is a declarative sentence (a sentence that declares a fact) that is either true or false, but not both. |
|
Propositional logic |
The area of logic thaf deals with propositions |
|
Propositional variables |
Variables that represent propositions : p, q r s. |
|
Truth values |
T, F |
|
Logical operators |
Operators used to form new propositions from two or more existing propositions. Also called connectives. |
|
Atomic propositions |
Propositions that cannot be expressed in terms of simpler propositions. |
|
Compound propositions |
Composed from one or more atomic propositions by using logical operators. |
|
Negation |
Let p be a proposition. The negation of p is the statement "It is not the case that p". |
|
Conjunctions |
Let p and q be propositions. The conjunction of p and q, denoted by p^q , is the proposition "p and q". True when both p and q are true and false otherwise. |
|
Disjunction |
Let p and q be propositions the disjunction of p and q , denoted by pvq , is the proposition "p or q" . False when both p and q are false and is true otherwise. |
|
Inclusive or |
The disjunction is true when at least one of the two propositions is true. Eg. Students who have taken calculus or computer science can take this class. (those who take one or both classes) |
|
Exclusive or |
The exclusive or of p and q is the proposition that is true when exactly one of p and q is true, and is false otherwise. Eg. Students who have taken calculus or computer science, but not both, can take this class. |
|
Conditional statement (aka implication) |
The conditional statement p->q , is the proposition "if p, then q". False when p is true and q is false, and true otherwise. P is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence) |
|
Other ways of expressinf p‐>q |
"If p, then q" "If p, q" "q follows from p" "q whenever p" "q is necessary for p" "a necessary condition for p is q" "p is sufficient for q" "a sufficient condition for q is p" "p implies q" "p only if q" "q if p" "q when p" "q unless ~p" |
|
Biconditional statement |
Let p and q be propositions. The biconditional statement p <-> q is the proposition "p if and only if q" . True when p and q have the same truth values, false otherwise . Also called bi-implications. |
|
Bit operations |
A bit is a symbol with two possible values 0 and 1. By convention 1 representd T and 0 represents F. A variable is called a boolean variable if its value is either true or false. Bit operation - replace true by 1 and false by 0 in logical operations. |
|
Bit string |
A bit string is a sequence of zero and ones. The length of the string is the number of bits in the string. |
|
Tautology |
A compound proposition that is always true , no matter what the truth values of the propositions that occursbin it, is called a tautology. |
|
Contradiction |
A compound proposition that is always false is called a contradiction. |
|
Contingency |
A compound proposition that is neither a tautology or a contradiction is called a contingency. |
|
Logical equivalences |
Compound propositions that have the same truth values in all possible cases are called logically equivalent. P ≡ Q The compound propositions p and q are logically equivalent if p<->q is a tautology. |
|
Well-Formed Formulae (WFF) |
Every atomic propositional variable is well-formed formulae. If p and q are wff, then ~p, p^q, pvq, p->q and p<-> q are wff. |
|
Functionally complete set of connectives |
A collection of logical operators is called functionally complete if every compound proposition is logically equivalent to a compound proposition involving only these logical operators. |
|
Propositional satisfiability |
A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true. When no such assignments exists, the compound proposition is unsatisfiable. |
|
Predicate logic |
An extension of propositional logic. It adds the concept of predicates and quantifiers to better capture the meaning of statements that cannot be adequately expressed by propositional logic. |
|
Predicate n-place predicate n-ary predicate |
A statement of the form P(x1,x2,x3, , xn) is the value of the propositional function P at the n-tuple (x1,x2,... xn) and P also called the n-place predicate or a n-ary predicate. |
|
Quantification |
Express the extent to which a predicate is true over a range of elements. |
|
Universal quantification |
A predicate holds for every element under consideration. |
|
Existential quantification |
A predicate holds for one or more element under consideration. |
|
Universal quantifier |
The universal quantification of P(x) is the statement "P(x) for all values of x in the domain". The notation ¥xP(x) denotes the univeral quantification of P(x) . Here ¥ is called the universal quantifier. "For all xP(x)" or "for every xP(x)" An element for which P(x) is false is called a counterexample of xP(x). |
|
Existential quantifier |
The existential quantification of P(x) is the statement "There exists an element x in the domain such that P(x)." We use the notation ExP(x) for the existential quantification of P(x). Here E is called the existential quantifier. |
|
Uniqueness quantifier |
E!xP(x) or E1P(x) states " There exists a unique x such that P(x) is true" |
|
Precedence of Quantifiers |
¥ and E have higher precedence than all logical operators. |
|
Argument |
An argument in propositional logic is a sequence of propositions. All but the final proposition are called premises. The last statement is the conclusion. |
|
Valid argument |
The argument is valif if the premises imply the conclusion. |
|
Argument form |
An argument form in propositional logic is a sequence of compound propositions involving propositional variables. |
|
Inference rules |
Inference rules are building blocks to construct more complicated valid argument forms. |
|
Universal modus ponens |
Combining universal instantiation and modus ponens produces the rule of universal modus ponens. Eg. All men are mortal Socrates is a man => Socrates is mortal. |
|
Universal modus tollens |
Combining universal instantiation and modus tollens produces the rule of universal modus tollens. Eg. All men are mortal Phone is not mortal => Phone is not a man. |
|
Fallacy |
A fallacy is reasoning that is logically incorrect.
((p->q)^q) -> p is not a tautology. This type of incorrect reasoning is called the fallacy of affirming the conclusion. |
|
Fallacy of denying the hypothesis |
(P->q) ^ ~p) -> ~q is not a tautology. |
|
Induction |
Mathematical induction is used to show that P(n) is true for every positive integer n. |
|
Principle of mathematic induction Basis step Inductive step |
To prove that P(n) is true for all positive integers n, where P(n) is a propositional function, we complete two steps. Basis step : we verify that P(1) is true. (Or first element in domain) Inductive step : We show that the conditional statement P(k) -> P(k+1) is true for all positive integers k.
|
|
Inductive hypothesis for mathematical induction |
We assume P(k) is true. |
|
Strong induction |
To prove that P(n) is true for all positive integers n, where P(n) is a propositional function, we complete two steps Basis step : we verify P(1) is true. (Or if more than one basis case, then verify all are true) Inductive step : we show that the conditional statement [P(1) ^ P(2) ^... ^ P(k)] -> P(k+1) is true for all positive integers k. |
|
Inductive hypothesis for strong induction |
We assume that P(0), P(1) , P(2) , ... ,P(k) all are true. |