* Logic

Language

Alphabet (Set of elements/objects)

Sentence Letters

Predicate/Propositions

2 place , 3 place

Operators

x y (tt, tf, ft, ff)

Conectives

And (Conjunction), Or (Disjunction),

Not(Negation),

(Conditinal)If Then(t,f,tt), If and only if(t,f,f,t)

Quantifiers

Universal all (For all),

Existensial some (For a),

There is at least one thing such that

Syntacatagoromatic/Extra

Braces

Formation Rules/Syntax/Transformations/Relations

Universe of Discourse/Semantics/Pragmatics

Truth Functions

Rules and methodes of deduction

Modus Ponens

Equivalence Thesis

If x then y = Either not x or y

Tautology - Always logicaly true statements L -true

(A <-> B) v (A <-> -B)

~(p ^ q) <-> (~p) v (~q)

p V ~p

(p ^ q) -> p

q->(pVq)

(p^q)<->(q^p)

A is and is not x

p ^ ~p

Logically determinate

a sentence that is logiclly true or false - there truth value

is determined by logical structure alone

Logically indeterminate

the truth value is not determined by  logical structure alone

but in conjunction with the way the world happens to be

Logically intermediate

False under some interpretations and true under others

Implication

x=>y, x implies y if there is no interpretation that makes x

and y false

Equivalence

x<=> y , x is equivalent to y if there is no interpretation

r which x and y have opposing truth values.

Principle of replacement

Let s be a set of propositions and let r and s be propositions

generated by S. r and s are equivalent if r<->s is a

tuatology.  The equivalence of r and s is denoted by r <=>.

(p^q) V (~p ^ q) <=>q

p->q<=> ~q-> ~p

p v q <=> q V p

Equivalence is to logic what equalit is to algebra.

Types of Equivalence

Double Negation --x <=> x

Idempotency (x & x) <=> x, (x v x) <=> x

Commutativity

x & y <=> y & x

x v y <=> y v x

x <-> y <=> y <-> x

Associativity

(x& y) & z <=> x & (y & z)

Contraposition

x -> y <=> -y -> -x

1                              Distribution

x & (y v z) <=> (x & y)  v (x & z)

DeMorgans's

-(x & y) <=> (-x v -y)

Importation/Exportation

x & y -> z <=> x ->(y->z)

Nameless

x ->y <=> -(x & - y)

x ->y <=> (-x v y)

Biconditinals

-(x <-> y) <=> (-x <-> y)

(-x <-> y) <=> (x <-> -y)

(x <-> y) <=> (x & y) v (-x & -y)

(x <-> y)<=>(x->y) & (y->x)

Consequence- gneralization of implication

Let D ba a set of well formed formulas

D |= x , x is a consequence of D

If there is no interpretation that makes each member

of D true and x false.

x => y  iff {x} |= y

x <=> y iff {x} |=y and {y} |= x

x is L-true iff { } |=x

x is L-false iff { } |= -x

inconsistence = L-false

consistent formulas are true under at

least one interpretation

x is L indeterminate iff neither {x } |= -x nor {-x} |= x.

Satisfiability - generalization of the concept of consistency

A property of sets of sentences

D is satisfiable if there is some interpretation that

makes each of its members true.

x is consistent iff { x} is satisfiable.

( x1, ....xn) is satisfiable iff (x1 & ....& xn)

D is satisfialbe iff there is some x such that

D is not |= X.

quantifier converson laws(4)

(v) x <=> -(Some v) -x

....

distribution collection laws (7)

(v) (x & y) <=> (v)x & (v)y

(Some v) (x & y) => (Some v) x & (Some v) y

....

confinement expansion laws (10)

(v) (x & y) <=> (v) x & y

Theories

D is a theory if  D is nonempty and each sentence of

D that is a consequence of D is a member of D.

D is a theory iff D is nonempty and for each

sentence s if s element L(D) and D |= s then

s element D.

The sentences that are a member of a theory are

referred to as its thesis and said to be accepted by

the theory. Sentences who's negations are accepted

are sid to be rejected by the theory. A theory is

neutral with respect to those of its sentences that it

neither accepts nor rejects.

A formula is accepted by a theory if its universal

closure is accepted.

A set is said to be decidable if there is a decision

procddure for determining whether any given object

is a member of the set.  The set of well formed

formulas and the set of tautaulogies are thus

decidable sets.

Modes of theory presentation.

Axomatic mode

Specify a decidable set of sentences, called axioms,

hen delcare the theses of the theory to be those

nces that are consequence sof the set. When a set is

nted axomaticcally the thesis are usually called

theorems.

Sematnic mode

`                              Specify the vocabular of a theory with an

interpretaton, and then declare the thesis of the

theory to be those of its sentences that are true

under the interpretation.

Implication

Let S ba  set of propositions and let r and s be propositions generted by S.

We say that r implies s if r -> is a tautology. We write r=>s to indicate this

implilcation.

p => ( V q)

p ->q <=> (~p) v q

p <-> q <=> (p ^ q) V (~p ^ ~q)

Basic logical laws

Commutative

p v q <=> q v p     p ^ q <=> q ^ p

Associative

( v  )  v  <=> v ( v )    ~ reverse ^

Distributive

^   v  <=> v  ^  v       ~reverse v ^

Identity Laws

p v 0 <=> p  p ^ 1 <=> p

Negation Laws

p ^ ~ p <=> 0    p v  ~ p <=> 1

Idempotenty Laws

p v p <=> p    p ^ p <=> p

Null Laws

p ^ 0 <=> 0  p V 1 <=> 1

Absorption Laws

p ^ (p v q)<=> p,   p v (p ^ q) <=> p

DeMorgans Laws

~(p v q) <=> (~p) ^ (~q)       ~(p ^q) <=>(~p) v (~q)

Involution Law

~p(~p) <=> p

A theory is :

Consistency- if there is no sentence that it accepts and rejects

Completness - if it is neutral w.r.t none of its sentenses

A complete theory is decisive if given any one of its sentences it

will either reject or accept the sentence.

If a theory is inconsistent then it is complete.

Independence

A set of sentence is independent if no one of its members is a

consequence of the other members.

All semantic theories are consistent and complete but not all axiomatic

theories.

A theory is axiomatizable if ech of its theses is a consequence of some

decidable subset of the theory.

A theory is said to be categorical if ti has a model and any two of its

models are isomorphic. If t is catagorical then t is complete.

Well Formed Formulas

Recursive definition

1.Sentence letters are all well formed

2. If y and z are well formed, then so are the following

-y, y&z, y v z, y -> z, y<->z

3. Nothing is well formed unless its being so can be

established on the basis of 1 and 2.

Derivation tree of the construction of well formed formulas

argument = any finite nonempty sequence of well formed

formulas

Premise > conclusion

Some arguments have no premise

Interpretation

If x is a sentence letter, then x is true under I if and only if I assigns

truth value truth to x.

If x = (y & z) then x is true under I iff y and z are both true under I.

...

It is always possible given a formula x and an interpretatin I, to

calculate the truth value of X under I.

An intepretation of logic of quantifiers,

a nonempty set, the universe or domain of the

interpretation, an assignment of appropriate extensions

tothe extralogical vocabulary of lq.

Domain - natural numbes

's' for the number of stars is even

'e' for one is even

Logical Argumentation:

Deductive - conclusively true

Inductive- not conclusively true, only probably true

Valid argument - impossible for its premises to be true while

its conclusion is false

Does not require that either the premises or the

conclusion of a valid argument be true. It only

requires that the conclusion be true if the premisis

are true. A valid argument of all whose premisies

are true is said to be sound.

No argument having the form that has true premisis

and a false conclusion. An argument is

deductively valid if it has a validating

argument form.

Methode of counterexample to establish invalidity.

An argument does not have a validating argument

form.

The methode of truth trees

Logical Relations: Countable, subset of, element of, intersection, union, product,

consistent, min, max, optimize, continous, discontiniouis, irregular, central, indentity,

universal, existential, void, combined, converse, relative product, symmetric, reflexive,

transitive, conex, orderings, partial, complete, well formed, mapping, inverse, sequences,

equivalence, congruence, abstract, isomorphic, domain of, properties of ordered pairs n-

place relation a property of ordered n-tuples, desireablity, probability/density, utility,

believability(probability, justified (deduce, induce), relative (opinion),  statistical,

normalize, linear, nonlinear, finite, stability, terminal, recursion, information value,

consistent, exhaustive, mutually exclusive, expansion,universal closure,  Deduce,

conclude, induction, deduction

then = implies=follows from=only if=if=is sufficient for=is necessary for

iff=is necessary and sufficient for=is equivalent to=

Other Relations:Fractality =Embedability =(Non-Destructive) Compressibility =

Turning Inside- Out ness =Scale Invariance =Spin Density =Information Density =

Charge Density =Sustainability =Share-Ability =Perfect Distributability =

Perfect Marketability, symmetry (a=b->b=a)..

Mathematical System

(1) A set or a universe U

(2) Definitions - sentences that explain the meaning of conepts that relate to the

universe. Any term used in describing the universe itself is said to be

undefined. All definitions are given in terms of these undefined concepts

of objects.

(3) Axioms - assertions about the properties of the universe and rules for creating

and justifiying more assetions. These rules always include the system of

logic that we have developed tothis point.

(4)  Theorems - the additional assertions mentioned above.

Proof - A proof of a theorem is a finite sequence of logically valid steps that

demonstrate that the premisis of a theorem imply the conclusion.

A research mathematician might require only a few steps to prove a theorem to a

colleaque, but might take an hour to give an effective proof to a class of students. What

constitutes a proof depends on the audience.

Computer proof theory

a, a-> b, b-> c, ..., x ->y, y->z =>z  can be proved by a computer using truth

tables:  (a ^ (a -b) ^....^ (y->z)) -> z.

The truth table will have 2^26 cases and at 1000 cases per second, it would take

aproximately 64,000 seconds (18 hours) to verity the theorem.

A similar theorem would , p1, p1 -> p2, ... p99->p100=> p!00 has 2^100 cases.

Rules of Formal Proofs

1. A proof must end in a finite number of steps

2. Each step must be either a premise or a proposition that is implied from

previoius steps using any valid equivalence or implication.

3. For a direct proof, the last step must be the conclusion of the theorem.

For  an indirect proof, the last step must be a contradiction.

A direct proof is a proof in which the truth of the premisis of a theorem are shown to

directly imply the truth of the theorem's conclusion.

Proof

Direct proof of ~p v q, s v p, ~q => s:

Step    Proposition    Justification

1       ~p v q         Premise

2       ~q             Premise

3.      ~p             Disjunction Simplification 1, 2

4       s v p          Premise

5       s              Disjunctive simplification 3, 4

Indirect Proofs

The method of indirect proof is based on teh equivalence P->C <=> ~P(P ^~C).

If p +. C, then  P ^ ~C is always false; P ^ ~C is a contradiction.

This means that a valid method of proof is to negate the conclusion of a theorem

and add this negation to the premisis.        If a contradiction can be implied from this

set of propositions, the proof is complete.

Definition: Propostion over the Universe. Let u be a nonempty  set. A propostion over U

is a sentence that contains a variable that can take on any value U and that has a definite

truth value as a result of any such substitution.  All of the laws of logic are valid for

propositions over a universe.  If p and q are propostions over the ingtegers, we can be

certain that p ^ q => p, because (p ^q) -> p is a tuatology and is true no matter what

values the varibles p and q are given.  If we specify p and  q to be p(n): n<=4 and q(n):

n<=8, we can also say that p implies p ^ q.

Truth Set

Definitinon: If p(n) is a proposition over U, the truth set of p(n) is Tp(n) = {a element of

U| p(a) is true}

The truth set of the propostion {1,2} ^ A = NULL taken as a proposition over the power

set of {1,2,3,4} is {NULL, {3}, {4},{3,4}}.

Definition: Tautology and Contradiction. A proposition over U is a tautology if its truth

set is U. It is a contradiction if its truth set is empty.

The truth set of compound propostions can be exressed in terms of simple propositions.

Tp^q = Tp ^ Tq

Tp v q = Tp v Tq

T~p = T(c p)

Tp<->q = (Tp ^ Tq) v (T(c p) ^ T(c p)

Tp->q = T(c p) v Tq

Equivalence: Two propositions are equivalent if p<->q is a tautology.  In terms of truth

sets, this means that p and q are equivalent if Tp = Tq.

Implication. If p and q are propostions over U, p implies q if p->q is a tautology.

Mathematical Induction: A technique for proving propostions over positive integers.

Mathematical induction reduces the proof that all of the positive integers belong to a

truth set to a finite number of steps.

The principle of mathematical induction.  Let p(n) be a proposition over the positive

integers, then p(n) is a tautology if

(a) p(I) is true, and

(b) n >= I and p(n) => p(n+1)

Note: The truth of p(1) is called the basis for the induction proof. The premise that p(n) is

true in Statement (b) is called the induction hypothesis. The proof the p(n) implies p(n+1)

is called the induction step of the proof.

Variations on the definitons of Mathematical Induction (Generalized)

If p(n) is a propostion over {k0, k0 + 1, k0 +2, ...}, where k0 is any integer, then p(n) is a

tautology if:

(1) p(k0) is true, and

(2) k >= k0 and p(k) => p(k +1)

The Course of Values Principle.  If p(n) is a propistion over {k0, k0+1, k0 +2, ...}, then

p(n) is a tautology if

(1) p(k0) is true, and

(2) k >= k0, p(k0), p(k0 +1), ...., p(k) => p(k +1).

An example of mathematical induction.

Consider the implication over the postive integers p(n):

q0 -> q1, q1 -> q2, ...., qn-1 ->qn, q0 =>qn.

A proof that p(n) is a tautology follows:

Basis: p(1) is q0->q1, q0 => q1.  This is the logical rule of detachment which we

know as true.  Wirte out the turth table of ((q0->q1) ^q0) -> q1 to

verifty this step.

Induction: Assume that n >= 1 and p(n) is true.  We want to prove that p(n +1)

must be true.  That is:

q0->q1, ..., qr-1 ->qn, qn->qn +1, q0 => qn+1.

Here is a direct proof of p(n + 1):

Steps   Proposition(s) Justification

_______________________________________

(1) - (n +1) q0 -> q1,,,,,,qn-1 ->qn, q0      Premises

(n +2) qn                                    (1) - (n +1), p(n)

(n +3)  qn ->qn+1                             Premise

(n +4)  qn +1                                 (n+2), (n+3),

Detachment #

Quantifiers

If p(n) is a proposition over a universe U, its turth set Tp(n) is equal to a subset of U. In

many cases such as when p(n) is an equation, we are most concerned with whether Tp(n)

=U, that is whether p(n) is a tautology.  Since the conditions Tp(n) not equal NULL

(Existensial) and Tp(n) =U (Universal ) ar so often an issue we have a special system of

notation for them.

Existensial Quantifier

If p(n) is a proposition over U with Tp(n) not equal 0, we commonly say there exists an n

in U such that p(n) (is true). We abbreviate this sentence, with  the symbols (E n) u

(p(n)), E is called the existential quatifier.

Universal Quantifier

If p(n) is a proposition over U with Tp(n) = U, we commonly  say for all n in U, p(n) is

(is true)".   We abbreviate this proposition with the symbols (An)u(p(n)). A is termed the

universal quantifier.

(Ax) (Ar(x) -> B(x)) is true = for all x such that Ar(x) = x lives in air, B(x), x is a bird.

Negation of a Quantified Proposition

~(Ax) (Ar(x) -> B(x)) <=> (Ex) (~(Ar(x) -> B(x))) <=> (E x) ((Ar(x) -> B(x)) .

The negation of a universially quantified proposition is an existentially quantified

propostion.    When you negate an existensially quantified propostion, you obtain a

universially quantified propostion. Symbolically, ~((A n) u (p(n)) <=> (E n) u (~p(n)),

and ~((E n) u (p(n))) <=> (A n)u(~p(n)).

Multiple Quantifiers

p(x,y) : x^2 -y^2 = (x+y) (x-y) is a tautology over the set of all pairs of real numbers

because it is true for each pair (x,y) in R x R. The asserttion that p(x,y) is a tuatology

could be quantified as (Ax)R ((Ay)R (p(x,y))) or (Ay) R ((Ax) R (p(x,y)).

Key Concepts In Proof

1. All theorems in mathematics can be expressed in "If P then C" (P=>C) format, or in

"C1 iffi C2" fromat.  The latter is equivalent to "If C1 then C2 and if C2 then C1."

2.If P then C, P is a premise (or hypothesis) and C is the conclusion.  It is important to

realize that theorem makes a statement that is dependent on the premise being true.

3.There are two basic methods for proving P => C:

(a) Direct: Assume P is true and prove C is true; and

(b) Indirect (proof by contradiction): Assume P is true C is false

4. The methode of proof for "iff" theorems is found in the law (P <->C) <=> ((P->C) ^ (C

->P)). Hence to prove an "If and only if" statment one must porve an "if ..then ..."

statment and its converse.

Propositional Connectives and Truth Values as Mappings

The propositional connectives thus far intorduced require two input sentences (p,q) into a

third sentence r = f(p,q).  x v y =   r = v(x,y). Since each sentence can be attributed the

truth value 0 or 1, it is convenient to allow X to denote a universal set of sentences and

then define the truth function T: X->{0,1), where T(p) =1 if the proposition p is true and

T(p) = 0 if the propositon if false. Consequently, as a mapping, f: X x X -> X, defined by

f(p,q) = r.  The disjunctive operation, p v q, r = v (p,q), is a function of two variables. The

truth value of the composite statement r can be found by knowing the truth values of the

sentences p and q and by knowing precisely which function f is being employed.   The

truth table is a function denoted by F. Commuting diagram:

X x X >  f > X .T > {0,1}<F<{0,1} x {0,1} < T x T< X x X

The meaning of the diagram is this: starting with a pair of sentences (p,q) in X x X

processing given truth values, the same value will be obtained by either traversing the

diagram across the top and then down, or by going down first and then traversing the

diagram horizontally along the bottom.  In sum the diagram states that:

T(f(p,q)) = F(T(p), T(q)).

Sets:

Sets: Set, Finite Set, Cardinatily, Subset, Equality(=), Intersection( ^), Union(U),

Disjoint(A ^ B=Null) (no elements in common), Universe, Compliment, Symmetric

Difference (In a and b but not in both), Venn Diagram,

Cartesian Product AXB = set of all possible ordereed pairs whose first component come

from a, and whose second component comes from b. , Power Sets P(A) - If A is any set,

the power set of A is the set of all subsets of a, including the empty set and A itself.

Summation Notation and Generalizations.

Permutations: (Subclass of the rule of the cartesian product)

Partitions of sets = Let A be a set. A partition of A is any set  of one or more nonempty

subsets or blocks A1, A2, ... of A  such that A1 U A2 ... and subsets Ai are mutually

dischoint Ai ^Aj = Null for i not equal to j. Let A = {a, b, c, d} then  3 partition of a are:

{{a},{b}, {c,d}}, 2. {{a,b}, {c, d}}, 3. {{a}, {b}, {c},{d}}.

How to partition a carton of 24 cans, 4 six packs, 3 8 packs, 2 twelve packs, in all cases

the sum of all packs must be 24, and a can must be in one and only one pack.

Basic Law of Addition= #A=#A1+#A2+....#An.  The sophomore computer science

majors where told they must take one (and only one) of the following courses. Calculus,

Data Structures, or Compiler Construction, in a given semester.  The numbers in each,

course, respectively, for sophomore C. S. majors, were 75, 60, 55. How many sophomore

C.S. majors are there?

A= the set of all sophomore .c.s majors, A1=set of all c.s. majors who took Calculus.

A2=set of all c.s. majors who took Calculus.   A3=set of all sophmores C.S. majors who

took Compiler, Construcion.

Since all sophmore C. S. majors must take at least one of the courses, the number we

want is : #A=#A(A1 U A2 U A3) = #A1+#A2+#A3 minus all duplications.

#A=#(A1U A2 U A3)

= #A1 +# A2 + #A3 - (duplications - triplications)

=#A1+#A2+A3- duplications + triplications

=#A1+#A2+#A3 - #(A1 ^ A2)-#(A1^A3) - #(A2 ^A2) + #(A1^A2^A3)

= 75+60+55-25-12-15+10 = 148.

Combinations: (Another subclass of the rule of products)

A = {a,b,c,d}?

Order is important in permutations.

There are P(4,3) = 4!/(4-3)!=24.

Order is not important in combinations.

How many ways can we simply list, or choose, three letters from the set A={a,

b,c,d}, all three elment subsets of A: The notation of choosing 3 elements from 4

is (4 3) =(C)ombinatorics(4,3) (4 choose 3), or the number of combinations for 4 objects

taken 3 at a time:

(n k) =C(n:k)  (read "n choose k") is the number of combinatinos of n

objects taken k at a time.

Relation between permutation and combination problems: (Used in Probability)

If A is any finite set of n elementsm, the number of k-element subsets of A is:

(n k) =  n!/(n-k)!k!,  where 0<=k<=n.

The binomial theorem gives us a procedure for expanding (x+y)^n where n is a postive

integer.  The coefficients of the expansion of (x + y)^n can be expressed compactly in the

form of the number (n k)- the binomial coefficient.]

The binomial theorem. (x + y)^n = (n 0) x^n + (n 1)x^n-1 y ^1 + .....+ ....= Sum (N, K=0)

(n k) x^n-k y^k.

Set Relations:

0 e B = an object is a member of set b

a  i  b =a is included in b

If a I b and b i a, then a = b

a  s  b = a is a subset of b

a + b = union of a or  b

a x b = intersection of a and b

a - b = relative complement

Order n tuple set of < o1, o2, ...>

n-ary relation of a set of objects

Combinatorics (Art of Counting)

Rule of products - If n operations must be performed, and the number of operations for

each operations is p1, p2, .. and pn, with each p independent of various choices, then the

n operations can be performed p1p2..;pnways.

The number of elements in the poser set of A, P(A) is #P(A)=2^#A.

Permutation= N!=N Factorial 3 Elements (a,b,c), then the number of permutiation is 3! =

3*2*1=6

Permutation of k elments taken from a set of n elements: P(n:k)= N!/(n-k)!.

Of (8)eight people who want to be president, .vp, treasurur (3), P(8,3)= 8!/(8-3)!=336

ways of choosing officers.

Derivations:

Basic model 1:

[opposition]>[chaos of  elements & relations & transformations-

falseness, ambiguity, uncertainty/most information=improbable

distributions]>[order(organization<positive feedback)>

Transformations(Evaluation of information within the system>

Stability of the system (limits of spectrum, levels of stability<negative

feedback)>Equilibrium of the system (Max. entropy (most probable

distributions=less information), certitude(Logic Deductive)>

permanence of the system /unity(more than sum of parts/order out of

instability/synergy/syncronicities(Overall system)/wholeness

Basic Model II:

preexistence of any sytem>all imaginatinos possible>

chaos>opposition (+,-, ~)>all universes possible/impossible>chaos[chaos of  elements &

relations & transformations-falseness, ambiguity, uncertainty/most

information=improbable distributions]>order(organization<positive feedback)>anaolog

spectrum>Logic (True, False, Neutral)>Duality(Bipolar,Binary), N-ary relations N-

Polarities>A universe in general > a universe of type

x(objects(properties),relations,meanings of a unvierse)>a real universe(genesis,

history(past, present, future, parrallel universes,dimensions of a universe(12(12(12)))>

Precreation>possible universes>possible ideas>possible sounds,vibrarions,energy

votexes, genes, memes>possilbe notation systems>symbols>alphabets

Transformations(Evaluation of information within the system>

Stability of the system (limits of spectrum, levels of stability<negative

feedback)>Equilibrium of the system (Max. entropy (most probable

distributions=less information), certitude(Logic Deductive)>

permanence of the system /unity(more than sum of parts/order out of

instability/synergy/syncronicities(Overall system)/wholeness

List of all ideas of a universe:

Precreation>possible universes>possible ideas>possible sounds,vibrarions,energy

votexes, genes, memes>possilbe notation

systems>symbols>alphabets>names(people(clans),

places),wordsds>languages(syntax, semantics,

pragmantics)>sciences,knowledge, facts,social systems and

arts>time frames(seasons, fesitvals, biological clocks, day,week, month,

year, generation, centruy, age, epoch,)>artifacts(buildings,

objects)>individuals>people>familes>cities>states>nations>

worlds>solar systems>galaxies>supergalaxies>unvierses>

Relations:

Binary, Bipolar relations:

+postive/true  -negative/false

good           evil

male           female

yin            yang

true           false

white          black

Trinary, Tripolar relations:

+positive, neutral, -negative

thesis, synthesis, antitheis

N-ary, N-Polar relations:

Spectrum/Analog/Numbers Theory

-infinity ............1............to infinity