Disclaimer
This notes are for DIT-023 and discrete math in general
I'm writing this series of notes coupled with tools that help the problem solving process as a way to check how much i know about the topic and to share some of the things i've found along the way. (Also writing on LaTex makes me feel like i know what i'm doing)
The notes are gonna be divided by topics and in the beginning of each one you are will find some tools to automate and solve exercises in a more easy way
Logic & Boolean Logic
Resources to solve exercises
Logic
The rules of logic specify the meaning of mathematical statements. Such rules help to understand and
reason with statements like “There exists an integer that is not the sum of two squares” or “For every n×(n+1)
positive integer n, the sum of the positive integers not exceeding n is 2 .”
Logic is the basis of all mathematical and automated reasoning. It has practical applications to the design of computing machines, to the specification of systems, to artificial intelligence, to computer programming, to programming languages, and other areas of computer science and many other fields of study.
Propositional Logic
A proposition is a declarative sentence that is either true or false, but not both.
Ex: (a) Washington, D.C., is the capital of the United States of America.
Logical operators
Negation
Let p be a proposition. The negation of p, denoted by ¬p (also ∼ p), is the statement “It
is not the case that p.”
The proposition ¬p is read “not p”. The truth value of the negation of p, ¬p, is the opposite of the
truth value of p.
Conjuntion (AND operator) p∧q
Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q”. The conjunction p ∧ q is true when both p and q are true and is false otherwise. The ∧ operator for the two propositions p and q can also be understood as min(p,q) where true is represented with 1 and false is represented with 0.
Disyunction PvQ ("OR" operator)
Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise. The ∨ operator for the two propositions p and q can also be understood as max(p, q) where true is represented with 1 and false is represented with 0.
Exclusive "OR" / XOR ⊕
Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise. The ∨ operator for the two propositions p and q can also be understood as max(p, q) where true is represented with 1 and false is represented with 0.
Condtional ⇒
Let p and q be propositions. The conditional statement p =⇒ q is the proposition “if p, then q.” The conditional statement p =⇒ q is false when p is true and q is false, and true otherwise. In the conditional statement p =⇒ q, p is called the hypothesis (or antecedent or premise), and q is called the conclusion (or consequence). The =⇒ operator for the two propositions p and q can also be understood as max(¬(p),q) where true is represented with 1 and false is represented with 0.
The statement p =⇒ q is called a conditional statement because p =⇒ q asserts that q is true on the condition that p holds. A conditional statement is also called an implication. The truth table for the conditional statement p =⇒ q is shown in table above. Note that the statement p =⇒ q is true when both p and q are true and when p is false (no matter what the truth value of q is).
Biconditional ⇐⇒
Let p and q be propositions. The biconditional statement p ⇐⇒ q is the proposition “p if and only if q.” The biconditional statement p ⇐⇒ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications. The ⇐⇒ operator for the two propositions p and q can also be understood as |(p − q)| == 0 where true is represented with 1 and false is represented with 0.
Tautology , Contigency and Contradiction
A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology. A compound proposition that is always false is called a contradiction. A compound proposition that is neither a tautology nor a contradiction is called a contingency.
so to simplify
Tautology → Always tru
Contigency → Sometimes truth sometimes not
Contradiction → Always false
De Morgan’s laws
De Morgan’s laws are particularly important. They tell us how to negate conjunctions and how to negate disjunctions. In particular, the equivalence ¬(p ∨ q) ≡ ¬p ∧ ¬q tells us that the negation of a disjunction is formed by taking the conjunction of the negations of the component propositions. Similarly, the equivalence ¬(p ∧ q) ≡ ¬p ∨ ¬q tells us that the negation of a conjunction is formed by taking the disjunction of the negations of the component propositions.
Quantifiers
Predicate Logic
Formalism of proposition logic is extended and more complex expressions are possible
Add universe of discourse and examples of predicate logic
Language , grammar and automata and finite state machines
Resources to solve exercises
Context free grammar
Finite state machine (FSM)
Language and grammar
Definition : Grammar = valid combination of words
"Grammar for a very tiny subset of the english language"
1) Sentence —> Noun p , Verb p
2) Noun P —> Article , Adjetive noun
3) Noun P —> Adjetive noun
4) Verb P —> Verb , Adverb
5) Verb P —> verb
6) Article —> A | The (Terminal symbols)
7) Adjetive —> Large | Hungry
8) Adjetive —> Rabbit / Mathematician
9) Verbs —> Eats | hops
10) Adverbs —> Quickly | Widly
Def :
- Alphabet V is a finite , non-empty set of elements called symbols
- Word over V is a string of finite lengths of elements of V
- Empty String: λ "lambda" (word of all words: v* "V-STAR" length 0)
- Grammar: Rules to produce words = production rules
Context free grammar
Start symbol
Productions rules; every production rule must have at least one non-terminal symbol on it's left hand side
Example
Terminal symbols
S= Starting symbol
Language
Set of all string of terminals that are derivable from
Words containing npn-terminal symbols belong to but not to
Derivation
Finite state machines and automata
Finite state machines with output
Several types of finite-state machines are commonly used in models. All versions of finite-state machines include a finite set of states, with a designated starting state, an input alphabet, and a transition function that assigns a next state to every state and input pair. Finite-state machines are used extensively in applications in computer science and data networking. For example, finite-state machines are the basis for spelling checkers, grammar checking, indexing or searching large bodies of text,
Definition
A finite-state machine consist of a finite set of S of state , a finite input alphabet , an infinite ouput alphabet , a transition function that assigns to each pair of state and input a new state , an output function that assigngs to each pair of state and input a corresponding output and a initial state
Example
Finite state machines without output
One of the most important applications of finite-state machines is in language recognition. This appli- cation plays a fundamental role in the design and construction of compilers for programming languages. In the previous section we showed that a finite-state machine with output can be used to recognize a language, by giving an output of 1 when a string from the language has been read and a 0 otherwise.
Types of FSM
TYPES OF FINITE-STATE MACHINES Many different kinds of finite-state machines have
been developed to model computing machines. In this section we have given a definition of one type
of finite-state machine. In the type of machine introduced in this section, outputs correspond to
transitions between states. Machines of this type are known as Mealy machines, because they
were first studied by G. H. Mealy in 1955.
There is another important type of finite-state machine with output, where the output is deter-
mined only by the state. This type of finite-state machine is known as a Moore machine, because
E. F. Moore introduced this type of machine in 1956. A Moore machine M = (S, I, O, f, g, s0)
consists of a finite set of states, an input alphabet I, an output alphabet O, a transition function
f that assigns a next state to every pair of a state and an input, an output function g that assigns
an output to every state, and a starting state s0. A Moore machine can be represented either by a
table listing the transitions for each pair of state and input and the outputs for each state, or by a
state diagram that shows the states, the transitions between states, and the output for each state.
In the diagram, transitions are indicated with arrows labeled with the input, and the outputs are
shown next to the states.
Graph Theory
This part is gonna be taken completly from the notes because i ain't doing graphs on latex because i'm a lazy mf
Graphs
graphs describe relations and are discrete structures ; they are differentiated by direct edges , loops and ff graphs can used to determine whether to walk all streets without crossing one bridge twice (the seven Bridges of konigsberg problem)
Connectivity
Complexity
Definition of algorithm
An algorithm is a finite sequece of percise instructions for performing a computation or solving a problem
a) input (finite)
b) output (finite)
c) precisly defined steps (definitess)
d) correctness
e) finiteness (come to an end)
f) effectiveness (finite amount of time)
g) generality (all problems , not just for a particular set of input value)
Greedy algorithm
An algorithm that makes the best choice at every next step solutions but not necesarly optimal
Brute force
Neglecting computational efficiency
Divide and conquer
b)
We can compare two algorithms input sizes grow
Proofs
Not gonna make any jokes about the one on the right
Modus Ponens
Some definitions
Theorem: Statment , which has been proven on previously proven statements and axioms
Axiom: generally accepted statement "every natural number has a exactly one successor "
Proof: A clear and concise explanitation that concretizes another mathematical statement
So we write
Let X be an integer such that `
More examples
Direct proofs
Proof by contradiction
Mathematical induction
The end
I know at the end i've got tired of using Latex but that's life i guess.
If you made it to the end here some chocky milk because your are awesome.
