Logical Form

•          Logical Form

–        Initial terms in logic: sentence, true, false

–        Statement (proposition) is a sentence that is true or false but not both

–        Compound statement is a statement built out of simple statements using logical operations: negation, conjunction, disjunction

–        Truth table

–        Precedence of logical operations

–        English words to logic:

•          It is not hot but it is sunny

•          It is neither hot nor sunny

–        Statement form (propositional form) is an expression made up of statement variables and logical connectives (operators)

–        Exclusive OR: XOR

–        Truth table for (~p Ù q) Ú (q Ù ~r)

–        Two statements are called logically equivalent if and only if (iff) they have identical truth tables

–        Double negation

–        Non-equivalence: ~(p Ú q) vs ~p Ú ~q

–        De Morgan’s Laws:

–        The negation of and AND statement is logically equivalent to the OR statement in which component is negated

–        The negation of an OR statement is logically equivalent to the AND statement in which each component is negated

–        Applying De-Morgan’s Laws:

•          Write negation for

•          The bus was late or Tom’s watch was slow

•          -1 < x <= 4

–        Tautology is a statement that is always true regardless of the truth values of the individual logical variables

–        Contradiction is a statement that is always false regardless of the truth values of the individual logical variables

Logic of Compound Statements

Discrete Mathematics Logic of Compound Statements

•          Logic of Statements

–        Logical Form and Logical Equivalence

–        Conditional Statements

–        Valid and Invalid Arguments

–        Digital Logic Circuits

–        Number Systems & Circuits for Addition

truth table discrete math

Truth Table discrete math

A truth table is table of truth values, commonly used to demonstrate which cases is a logic statement is true or false. 

For example, 

Logical AND. p & k is true only when both are true

p | k | p & k
---|---- |-------
T | T | T
F | F | F
T | F | F
F | T | F

Combinatorics

Combinatorics is the branch of mathematics studying the enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties.


Combinatorics studies the way in which discrete structures can be combined or arranged. Enumerative combinatorics concentrates on counting the number of certain combinatorial objects - e.g. the twelvefold way provides a unified framework for counting permutations, combinations and partitions. Analytic combinatorics concerns the enumeration (i.e., determining the number) of combinatorial structures using tools from complex analysis and probability theory. In contrast with enumerative combinatorics which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining asymptotic formulae. Design theory is a study of combinatorial designs, which are collections of subsets with certain intersection properties. Partition theory studies various enumeration and asymptotic problems related to integer partitions, and is closely related to q-series,special functions and orthogonal polynomials. Originally a part of number theory and analysis, partition theory is now considered a part of combinatorics or an independent field. Order theory is the study of partially ordered sets, both finite and infinite.

Set theory

Set theory

Set theory is the branch of mathematics that studies sets, which are collections of objects, such as {blue, white, red} or the (infinite) set of all prime numbers. Partially ordered sets and sets with other relations have applications in several areas.

In discrete mathematics, countable sets (including finite sets) are the main focus. The beginning of set theory as a branch of mathematics is usually marked by Georg Cantor's work distinguishing between different kinds of infinite set, motivated by the study of trigonometric series, and further development of the theory of infinite sets is outside the scope of discrete mathematics. Indeed, contemporary work in descriptive set theory makes extensive use of traditional continuous mathematics.

ref: wikipedia

Logic

Logic

Logic is the study of the principles of valid reasoning and inference, as well as of consistency, soundness, and completeness. For example, in most systems of logic (but not in intuitionistic logic) Peirce's law (((P→Q)→P)→P) is a theorem. For classical logic, it can be easily verified with a truth table. The study of mathematical proof is particularly important in logic, and has applications to automated theorem proving and formal verification of software.

Logical formulas are discrete structures, as are proofs, which form finite trees or, more generally, directed acyclic graph structures (with each inference step combining one or more premise branches to give a single conclusion). The truth values of logical formulas usually form a finite set, generally restricted to two values: true and false, but logic can also be continuous-valued, e.g., fuzzy logic. Concepts such as infinite proof trees or infinite derivation trees have also been studied, e.g. infinitary logic.

REF: wikipedia

Logic is a language for reasoning. It is a collection of rules we use when doing logical reasoning. Human reasoning has been observed over centuries from at least the times of Greeks, and patterns appearing in reasoning have been extracted, abstracted, and streamlined. The foundation of the logic we are going to learn here was laid down by a British mathematician George Boole in the middle of the 19th century, and it was further developed and used in an attempt to derive all of mathematics by Gottlob Frege, a German mathematician, towards the end of the 19th century. A British philosopher/mathematician, Bertrand Russell, found a flaw in basic assumptions in Frege's attempt but he, together with Alfred Whitehead, developed Frege's work further and repaired the damage. The logic we study today is more or less along this line.

In logic we are interested in true or false of statements, and how the truth/falsehood of a statement can be determined from other statements. However, instead of dealing with individual specific statements, we are going to use symbols to represent arbitrary statements so that the results can be used in many similar but different cases. The formalization also promotes the clarity of thought and eliminates mistakes.

There are various types of logic such as logic of sentences (propositional logic), logic of objects (predicate logic), logic involving uncertainties, logic dealing with fuzziness, temporal logic etc. Here we are going to be concerned with propositional logic and predicate logic, which are fundamental to all types of logic.

Ref: http://www.cs.odu.edu/~toida/nerzic/content/logic/intr_to_logic.html

Information theory

Information theory

Information theory involves the quantification of information. Closely related is coding theory which is used to design efficient and reliable data transmission and storage methods. Information theory also includes continuous topics such as: analog signals, analog coding, analog encryption.

source: http://en.wikipedia.org/wiki/Discrete_mathematics

Theoretical Computer Science

Theoretical computer science

Theoretical computer science includes areas of discrete mathematics relevant to computing. It draws heavily on graph theory and logic. Included within theoretical computer science is the study of algorithms for computing mathematical results. Computability studies what can be computed in principle, and has close ties to logic, while complexity studies the time taken by computations. Automata theory and formal language theory are closely related to computability. Petri nets and process algebras are used to model computer systems, and methods from discrete mathematics are used in analyzing VLSI electronic circuits. Computational geometry applies algorithms to geometrical problems, whilecomputer image analysis applies them to representations of images. Theoretical computer science also includes the study of various continuous computational topics

Source : http://en.wikipedia.org/wiki/Discrete_mathematics

Topics in discrete mathematics

Some Topics in discrete mathematics

1. Theoretical computer science
2. Information theory
3. Logic
4. Set theory
5. Combinatorics
6. Graph theory
7. Probability
8. Number theory
9. Algebra
10. Calculus of finite differences, discrete calculus or discrete analysis
11. Geometry
12. Topology
13. Operations research
14. Game theory, decision theory, utility theory, social choice theory
15. Discretization
16. Discrete analogues of continuous mathematics
17. Hybrid discrete and continuous mathematics

Discrete mathematics Introduction

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus and analysis. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets (sets that have the same cardinality as subsets of the natural numbers, including rational numbers but not real numbers). 


However, there is no exact, universally agreed, definition of the term "discrete mathematics." Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions. The set of objects studied in discrete mathematics can be finite or infinite. The term finite mathematics is sometimes applied to parts of the field of discrete mathematics that deals with finite sets, particularly those areas relevant to business.