Propositional Logic

From Notes
Jump to navigation Jump to search

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

represented by a small letter "propositional variable" (usually , , , etc.)

Logical Connectives

(in order of precedence)

Connective Symbol English Value Read as
Negation ¬ "It is not the case that…" "not "
Conjunction "and", "but" " and "
Disjunction "or" " or "
Exclusive or "either or " " ex-or "
Conditional "if , [then] ", " is sufficient for ", " if ", " unless ¬", " implies ", " only if ", " whenever ", " is necessary for ", " follows from " " implies "
Biconditional " is necessary and sufficient for ", " if and only if " " if and only if "

Truth Table of Connectives

T T F T T F T T
T F F F T T F F
F T T F T T T F
F F T F F F T T

Conditionals

  • given conditional: p → q
  • converse: q → p
  • inverse: ¬p → ¬q
  • contrapositive: ¬q → ¬p

Logical Equivalence

two statements are logically equivalent if and only if they have the same truth table.

Equivalence Name

Identity laws

Domination laws

Idempotent laws
Double negation law

Commutative laws

Associative laws

Distributive laws

De Morgan's laws

Absorption laws

Negation laws

Quantifiers

  • Higher precedence than all logical operators
  • Distribute across parenthesized terms:

Universal Quantification

If a predicate is true for all values of in the domain,

To be contradicted, we need to find only one value of such that is false.

Existential Quantification

If a predicate is satisfiable for at least one value of in the domain,

To be contradicted, every value of has to be false.

Unique Quantification

If a predicate is satisfiable for only one value of in the domain,

To be contradicted, more than one has to be true or all values of evaluate to be false.


Variable Binding

A variable is bound if a quantifier is used on that variable. A bound variable does not mean anything outside of the quantification. For example, in , is bound, but is free (not bound). To fix this, we would write .

In the statement , the two bound variables are not related whatsoever.