Dms

Front 1

Proposition

Back 1

A proposition is a declarative sentence (a sentence that declares a fact) that is either true or false, but not both.

Front 2

Propositional logic

Back 2

The area of logic thaf deals with propositions

Front 3

Propositional variables

Back 3

Variables that represent propositions : p, q r s.

Front 4

Truth values

Back 4

T, F

Front 5

Logical operators

Back 5

Operators used to form new propositions from two or more existing propositions. Also called connectives.

Front 6

Atomic propositions

Back 6

Propositions that cannot be expressed in terms of simpler propositions.

Front 7

Compound propositions

Back 7

Composed from one or more atomic propositions by using logical operators.

Front 8

Negation

Back 8

Let p be a proposition. The negation of p is the statement "It is not the case that p".

Front 9

Conjunctions

Back 9

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.

Front 10

Disjunction

Back 10

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.

Front 11

Inclusive or

Back 11

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)

Front 12

Exclusive or

Back 12

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.

Front 13

Conditional statement (aka implication)

Back 13

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)

Front 14

Other ways of expressinf p‐>q

Back 14

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

Front 15

Biconditional statement

Back 15

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.

Front 16

Bit operations

Back 16

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.

Front 17

Bit string

Back 17

A bit string is a sequence of zero and ones. The length of the string is the number of bits in the string.

Front 18

Tautology

Back 18

A compound proposition that is always true , no matter what the truth values of the propositions that occursbin it, is called a tautology.

Front 19

Contradiction

Back 19

A compound proposition that is always false is called a contradiction.

Front 20

Contingency

Back 20

A compound proposition that is neither a tautology or a contradiction is called a contingency.

Front 21

Logical equivalences

Back 21

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.

Front 22

Well-Formed Formulae (WFF)

Back 22

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.

Front 23

Functionally complete set of connectives

Back 23

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.

Front 24

Propositional satisfiability

Back 24

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.

Front 25

Predicate logic

Back 25

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.

Front 26

Predicate

n-place predicate

n-ary predicate

Back 26

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.

Front 27

Quantification

Back 27

Express the extent to which a predicate is true over a range of elements.

Front 28

Universal quantification

Back 28

A predicate holds for every element under consideration.

Front 29

Existential quantification

Back 29

A predicate holds for one or more element under consideration.

Front 30

Universal quantifier

Back 30

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

Front 31

Existential quantifier

Back 31

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.

Front 32

Uniqueness quantifier

Back 32

E!xP(x) or E1P(x) states

" There exists a unique x such that P(x) is true"

Front 33

Precedence of Quantifiers

Back 33

¥ and E have higher precedence than all logical operators.

Front 34

Argument

Back 34

An argument in propositional logic is a sequence of propositions.

All but the final proposition are called premises.

The last statement is the conclusion.

Front 35

Valid argument

Back 35

The argument is valif if the premises imply the conclusion.

Front 36

Argument form

Back 36

An argument form in propositional logic is a sequence of compound propositions involving propositional variables.

Front 37

Inference rules

Back 37

Inference rules are building blocks to construct more complicated valid argument forms.

Front 38

Universal modus ponens

Back 38

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.

Front 39

Universal modus tollens

Back 39

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.

Front 40

Fallacy

Back 40

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.

Front 41

Fallacy of denying the hypothesis

Back 41

(P->q) ^ ~p) -> ~q is not a tautology.

Front 42

Induction

Back 42

Mathematical induction is used to show that P(n) is true for every positive integer n.

Front 43

Principle of mathematic induction

Basis step

Inductive step

Back 43

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.

Front 44

Inductive hypothesis for mathematical induction

Back 44

We assume P(k) is true.

Front 45

Strong induction

Back 45

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.

Front 46

Inductive hypothesis for strong induction

Back 46

We assume that P(0), P(1) , P(2) , ... ,P(k) all are true.