logic

prop.log., operators, implication, logic/sets, pred.log., neg.quant., set min/max, quant.ex., alg.rules,

propositional logic

boolean algebra	logic
0/ 1	T/F
bool. fn.	statement form
value	truth value
equality	equivalence

tautology: statement form, always T
(↔ boolean function, always 1)

contradiction: statement form, always F
(↔ boolean function, always 0)

logical operators

~	negation			complement
∧	and	conjunction		min
∨	or	disjunction		max
⇔	if and only if	equivalence	⊕	=
⇒	implies		~( ) ∨ ( )	≤
⇐	implied by		( ) ∨ ~( )	≥

p	q	∧	∨	⇔	⇒	⇐
0	0	0	0	1	1	1
0	1	0	1	0	1	0
1	0	0	1	0	0	1
1	1	1	1	1	1	1

operator precedence

( )

∧

∨

⇒

⇔

p ∨ r ⇒ ~ s ⇔ t ∧ u = ( ( p ∨ r ) ⇒ ( ~s ) ) ⇔ ( t ∧ u )

implication

“if X then Y” corresponds to “X ⇒ Y”

but when X does not hold

English meaning of “if X then Y” may be ambiguous

logical value of “X ⇒ Y” is T (statement form is vacuously true)

example

p: "it is raining" q: "my hair is wet" value of p ⇒ q when . . .

it is raining and my hair is wet ?
it is raining and my hair is not wet ?
it is not raining and my hair is not wet ?
it is not raining and my hair is wet ?

contrapositive of p ⇒ q: ~q ⇒ ~p

equivalent

converse of p ⇒ q: q ⇒ p

inverse of p ⇒ q: ~p ⇒ ~q

equivalent to converse

example

let be p,q as above, let I be p ⇒ q . in English, state

I
contrapositive of I
converse of I
inverse of I

equivalent

if p then q
q only if p
p is sufficient for q
q is necessary for p
not p, or q

equivalent

p if and only if q
p is necessary and sufficient for q

equivalent

unless
or

equivalent

logic and sets

boolean algebra	logic	sets
min	∧	∩
max	∨	∪
(1-x)	~	complement

min(p, max(q,r)) =	p ∧ (q ∨ r) ⇔	P ∩ (Q ∪ R) =
max(min(p,q), min(p,r))	(p ∧ q) ∨ (p ∧ r)	(P ∩ Q) ∪ (P ∩ R)

predicate logic

predicate: says something about its subject
predicate logic: allows reasoning about statement collections

∀	for all	universal quantifier	∀ x ∈ D, S(x)
∃	exists, for some	existential quantifier	∃ x ∈ D, S(x)

integers

≥ 0

$mathcal{N}^+$ ≥ 1

$mathcal{N}^{++}$ ≥ 2

prime

reals

rationals

Goldbach's conjecture

∀ n ∈ $mathcal{N}^{++}$ , ∃ p,q ∈ mathcal{P} , p+q = 2n

order matters

∀ n . . . ∃ p . . . means:
- for each value of n, there is a particular p
- for different values of n, the values of p may differ
∃ p . . . ∀ n . . . means:
- there is some p, such that for this p and all values of n, . . .

silly conjecture

∃ p,q ∈ mathcal{P} , ∀ n ∈ $mathcal{N}^{++}$ , p+q = 2n

disprove this conjecture

negating quantifiers

~ ( ∀ x ∈ D, S(x) )	⇔	∃ x ∈ D, ~ S(x)
~ ( ∃ x ∈ D, S(x) )	⇔	∀ x ∈ D, ~ S(x)

all items not available in all stores ?

A(i,s)

item i available at store s

∀ i ∈ I, ∀ s ∈ S, A(i,s)

every item available in every store

∀ i ∈ I, ∀ s ∈ S, ~ A(i,s) ?

∀ i ∈ I, ~ ( ∀ s ∈ S, A(i,s) ) ?

~ ( ∀ i ∈ I, ∀ s ∈ S, A(i,s) ) ?

∀ i ∈ I, ∀ s ∈ S, ~ A(i,s)
∀ i ∈ I, ~ ( ∀ s ∈ S, A(i,s) )	∀ i ∈ I, ∃ s ∈ S, ~ A(i,s)
~ ( ∀ i ∈ I, ∀ s ∈ S, A(i,s) )	∃ i ∈ I, ~ ( ∀ s ∈ S, A(i,s) )	∃ i ∈ I, ∃ s ∈ S, ~ A(i,s)

every item in every store is unavailable ?
every item is unavailable in some store?
some item in some store is unavailable ?
it is not the case that every item is available in every store
not every item is available in every store

set min/max

set: collection (possibly empty) of distinct elements

finite set S: empty, or exists pos. int. t, elements can be labelled s₁ . . . s_t
S = { } or ∃ t ∈ $mathcal{N}^+$ , S = { s₁ . . . s_t }
max: of S ⊆ : x ∈ S, ∀ s ∈ S, x ≥ s
min: of S ⊆ : y ∈ S, ∀ s ∈ S, y ≤ s

min/max of

{ 1, 3, 5 } ?
$mathcal{N}^+$ ?
{ r ∈ , 0 < r < 1 } ?

meaning?

∃ m ∈ S, ∀ s ∈ S, m ≥ s
∀ m ∈ S, ∃ s ∈ S, m < s
∃ n ∈ , ∀ s ∈ S, s < n
∀ n ∈ , ∃ s ∈ S, s ≥ n

theorem

for every nonempty finite S ⊆ , S has max/min

min ← max ← s_1
for j ← 2 to t
  #invariant: max >= s_1, ..., s_{j-1}
  if s_j < min then min ← s_j
  if s_j > max then max ← s_j

correctness?

prove by induction on t that, when program terminates, max is the value of the maximum element of S. hint: prove the invariant. remark: last time through the loop, j is set to t+1 in for-check

theorem

for every nonempty S ⊆ , S has min

min ← any s in S
for j ← min downto 0
  # invariant: ?
  if is_in(j,S) and j < min then min ← j

correctness?

find and prove invariants

theorem

for every nonempty S ⊆ , S has max ⇔ S finite

X: “S has max” F: “S is finite” want to show X ⇔ F.

first show X ⇒ F
assume X.
so S has max x.
so S ⊆ { 0, 1, . . . , x } .
so F.

next show F ⇒ X.
assume F.
use above theorem.

examples with quantifiers

twin primes

S(p)
≡ (p ∈ mathcal{P} ) ∧ (p + 2 ∈ )

conjecture
∀ m ∈ mathcal{N} , ∃ p ∈ , (p > m) ∧ S(p)

Fermat numbers

a^{b^c} ≡ a^{(b^c)} F_n ≡ 1 + 2^2ⁿ wikipedia Q(n) ≡ F_n ∈ mathcal{P}

Fermat conjecture: ∀ n ∈ , Q(n)

Euler counterexample: not Q(5)

open: ∀ m ∈ , ∃ n > m, Q(n) ?

straight-edge, compass

R(n) ≡ regular n-polygon straightedge/compass constructible wikipedia

ancient Greeks: ∀ k ∈ , R(3 ⋅ 2^k) ∧ R(5 ⋅ 2^k)

Gauss: ∀ m,k ∈ , m odd ⇒ ( R(m ⋅ 2^k) ⇔ ∃ finite S ⊂ , ( ∀ s ∈ S, Q(s) ) ∧ (m = Π s ∈ S) )

Mersenne numbers

Mersenne number: M_n ≡ 2ⁿ - 1

Mersenne prime: Mersenne number and prime wiki

open: ∀ k ∈ , ∃ p ∈ , ( (p > k) ∧ (M_p ∈ ) ) ?

open: ∀ k ∈ , ∃ t ∈ , ( (t > k) ∧ (M_t ∈ ) ) ?

Fermat's last theorem

around 1637: Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et generaliter nullam in infinitum ultra quadratum potestatem in duos ejusdem nominis fas est dividere : cujus rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.

∀ n ∈ mathcal{N} , n ≥ 3, ~ ( ∃ x,y,z ∈ mathcal{Z} , xⁿ + yⁿ = zⁿ )

predicates: algebraic rules

no quantifiers? same as prop. logic: P(x) ∨ ( Q(y) ∧ R(x,y) ) ⇔ ( P(x) ∨ Q(y) ) ∧ ( P(x) ∨ R(x,y) )
quantifiers?

∀ x, ( P(x) ∧ Q(x) ) ⇔ ( ∀ x, P(x) ) ∧ ( ∀ x, Q(x) )
∀ x, ( P(x) ∨ Q(x) ) ?? ( ∀ x, P(x) ) ∨ ( ∀ x, Q(x) )
∃ x, ( P(x) ∧ Q(x) ) ?? ( ∃ x, P(x) ) ∧ ( ∀ x, Q(x) )
∃ x, ( P(x) ∨ Q(x) ) ⇔ ( ∃ x, P(x) ) ∨ ( ∃ x, Q(x) )