Please enable JavaScript.

Coggle requires JavaScript to display documents.

cs390, 270 module 2 334 lecture 11 and 12, cs381 notes modules 1,2,3 -…

- - - - propeties of integers: set Z is closed under addition,multiiplication, and subtraction
        
        example of proving a set is not closed under an operation: natural numbers are not closed under subtraction, as they can result in a negative number (an integer)
      - all sqrts of natural numbers are irrational, other than perfect squares
    - - real, rational. integer, integer, natural
  - - - ex: Proposition. If x and y are odd integers, then x * y is an odd integer. this is a "for all" proposition, meaning it cannot be proven by given examples, as we would be here all day listing every possible example of two odd numbers being multiplied together. instead we use a definition
  - - - constructing direct proofs
        
        start by assuming P is true, and proceed through a logical sequence of steps to arrive to the conclusion that Q must also be true
        
        require:
        
        Definitions
        
        precise statements used for setting up a proof
        
        ex, for the conditional statement "If x and y are odd integers, then x * y is an odd integer." what definition could we use to define an even/odd integer?
        
        integer a is an even integer if there exists an integer n such that a = 2n. integer a is an odd integer if there exists an integer n such that a = 2n + 1.
        
        1 more item...
        
        other useful tools:
        
        backwards question
        
        asks: "under what conditions is this proposition true or untrue?"
        
        asks when P is true or false
        
        forwards question
        
        asks: if the hypothesis is true, what conclusions can we draw?
        
        assumes P to be true and asks when Q is true or false
  - - - conjuction
        
        P $ \wedge$Q
        
        $ P \wedge Q $ is true if P AND Q are true
        
        $ \wedge $ = AND
      - disjunction
        
        P $ \vee $ Q
        
        P $ \vee $ Q is true if P OR Q is true
      - negation
        
        $ \neg Q $
        
        not Q is true if Q is false, not Q is false if Q is true
        
        negates the value of Q
      - implication
        
        aka
        
        conditional
        
        $P \Rightarrow Q $
        
        the statement $ P \Rightarrow Q $ is false if and only if P is true and Q is false
    - - $$P \oplus Q$$
        
        true if P is true and Q is false
        true if Q is true and P is false
        false if P is true and Q is true
        false if P is false and Q is false
        
        true if one is true and the other is false, false if both are true or both are false
    - - $$P \leftrightarrow Q$$
        
        true if both A and B are false
        true if both A and B are true
        false if either A or B are false
        
        both statements must share same truth value to be true, else statement is false
    - - $$\equiv$$
        
        when two statements, compound statements, or conditional statements have the same truth table
        
        E
        
        =
    - - $$P \rightarrow Q \equiv \neg P \vee Q$$
        
        P then Q is equal to Not P OR Q
      - $$\neg (P \rightarrow Q) \equiv P \wedge \neg Q$$
        
        the negation of P then Q is equal to P AND Not Q
      - $$P \rightarrow Q \equiv \neg Q \rightarrow \neg P$$
        
        P then Q is equal to Not Q then Not P
      - $$\neg(\neg P) \equiv P$$
        
        not not p equals p
      - distributive laws
        
        $$P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$$
        
        P OR (Q and R) equals (P OR Q) AND (P OR R)
        
        $$P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$$
        
        P AND (Q OR R) equals (P AND Q) OR (P AND R)
        
        if you can remember one, just swap operators and you have the other
        the operators alternate
        
        left statement and left operator are distributed to both statements with in the compound statement, and the two new compound statements are joined by the operator inside the original righthand statement
      - demorgans laws
        
        $$\neg{(P \wedge Q)} \equiv \neg P \vee \neg Q$$
        
        the negation of P and Q is equal to Not P OR Not Q
        
        $$\neg{(P \vee Q)} \equiv \neg P \wedge \neg Q$$
        
        the negation of P or Q is equal to Not P AND Not Q
      - $$(P \leftrightarrow Q) \equiv (P \rightarrow Q) \wedge (Q \rightarrow P)$$
      - $$P \rightarrow (Q \vee R) \equiv (P \wedge \neg Q) \rightarrow R$$
      - $$(P \vee Q) \rightarrow R \equiv (P \rightarrow R) \wedge (Q \rightarrow R)$$
      - rules of interference
        
        two modus
        
        modus tollens
        
        ( $\neg $ p $\wedge$ ( p $\rightarrow$ q) $\rightarrow$ $\neg $ p
        
        if NOT P AND P THEN Q, THEN NOT P
        
        modus ponens
        
        (p $\wedge$ ( p $\rightarrow$ q) $\rightarrow$ q
        
        if P AND P THEN Q, THEN Q
        
        two syllogisms
        
        disjunctive syllogism
        
        ( $\neg $ p $\wedge $ (p $\vee $ q ) ) $\rightarrow $ q
        
        if not p and p or q, then q
        
        hypothetical syllogism
        
        ( ( p $\rightarrow$ q) $\wedge $ (q $\rightarrow$ r)) q $\rightarrow$ r
        
        If P then Q and Q then R, then Q then R
        
        4(2) -tions
        
        simplification
        
        (p $\wedge$ q) $\rightarrow$ p
        
        conjunction
        
        ((p) $\wedge$ (q)) $\rightarrow$ (p $\wedge$ q)
        
        obvious
        
        resolution
        
        (( $\neg$ p $\vee$ r ) $\wedge$ (p $\vee$ q )) $\rightarrow$ (q $\vee$ r)
        
        addition
        
        p $\rightarrow$ (p $\vee$ q)
        
        obvious
        
        arguement forms used to make more complicated arguments
  - - - equations with one or more variables on either side, those only become statements when a value is substituted with a variable
    - - compound statement
        
        tautology and contradiction
        
        tautology is a compound statement S that always yields a true value, contradiction is always false
        
        a statement that contains an operator
      - conditional statement
        
        statement that asserts that if one thing is true, another thing must also be true
        
        converse and contrapositive
        
        converse swaps the original hypothesis and conclusion
        
        $P \rightarrow Q $
        becomes
        $ Q \rightarrow P $
        
        contrapositive swaps the positions of the original hypothesis with the position of the original conclusion, and negates both of them
        
        $P \rightarrow Q $
        becomes
        $ \neg Q \rightarrow \neg P$
  - - - if a variable exists in a set, its denoted by $y \in S $, otherwise $y \notin S $
    - - the set of all possible values that can be substituted in for that variable
      - U = {...}
  - - - 4 is a constant value, 1 and 2 are constants
  - - - universal quantifier
        
        for all x, P(x)
        
        false if there is a member of P(x) that is false
      - existential quantifier
        
        there is an x where P(x) is true
        
        false if P(x) is false for every x
      - nested quantifiers
        
        quantifiers within quantifers
        
        $ (\exists (\forall )) $
        
        $ (\forall (\exists )) $
        
        example: R(x,y) = "x relies on y"
        
        $ (\forall x (\exists y \text{ R(x,y)})) $
        
        all x rely on some y
        
        $ (\exists y (\forall x \text{ R(x,y)})) $
        
        all x rely on some y
        
        $ (\exists x (\forall y \text{ R(x,y)})) $
        
        some x relies on all y
        
        $ (\forall y (\exists x \text{ R(x,y)})) $
        
        all y's are relied on by some x
        
        $ (\forall x (\forall y \text{ R(x,y)})) $
        
        all ys are relied on by all xs
- - - - ex: S = {1,2,3,4,...}
  - - - $\subseteq $ contains elements of a set or all of them
      - empty set is a subset of every set(NOT AN ELEMENT of every set)
    - - contains elements of a set but not all elements, and must have at least one have element not included in the other set
        
        $\subset $
  - - - $$\supseteq$$
    - - contains all of the elements of another set, and at least one element not in that other set
        
        $\supset $
  - - - duplicates dont add to cardinality
        
        ex |{{1,2,3} , {4,5}|| = 2
        
        ex: |{a,b,c}| = 3
    - - size of the set
  - - - power set of a finite set
        
        |P(S)| = $2^{|S|}$
        
        size of power set of set S = 2^size of set S
  - - - set of ordered pairs of n-tuples of each element of one set combined with each element of another
      - set S = {a,b,c}
        set T = {d,e,f}
        S X T =
        {(a, d), (a, e), (a, f), (b, d), (b, e), (b, f), (c, d), (c, e), (c, f)}
    - - A $\cap$ B
        
        remove all elements not in both sets
      - multiple intersections
        
        $\cap^n_{i=1}$ = Ai = A1 $\cap$ A2 .... $\cap $ An
    - - A $\cup$ B
        
        combine the elements of both sets
      - multiple unions
        
        $\cup^n_{i=1}$ = Ai = A1 $\cup$ A2 .... $\cup $ An
    - - A - B
        
        remove elements of one set that are in another set
    - - $\overline{A}$
        
        all elements NOT in A (that are in the universal set)
  - - - ex:
        
        (1,2)
    - - {1,2} = {2,1}
        (1,2) $\neq $ (2,1)
  - - - A $ \cup \emptyset $ = A = A $\cap$ U
      - A $\cup$ A = A = A $\cap$ A
      - $\overline{\overline{A}}= A$
      - commutative
        
        $A \cup B = B \cup A $
        
        $A \cap B = B \cap A $
      - associative
        
        $A ( B \cup C ) = (A \cup B) \cup C $
        
        $A ( B \cap C ) = (A \cap B) \cap C $
    - - $\overline{A \cup B}$ = $\overline{A} \cap \overline{B}$
      - $\overline{A \cap B}$ = $\overline{A} \cup \overline{B}$
    - - $A \cup (B\ \cap C ) = (A \cup B) \cap (A \cup C ) $
      - $A \cap (B\ \cup C ) = (A \cap B) \cup (A \cap C ) $
- - - - KCCA
      - star, next ,plus
    - - i = state 1, j = state 2, R^k = transition function to get from i to j without going through any other states other than i and j,k represents the maximum number state that can be used to from i to j.
    - - for any dfa, these are any direct paths from one vertex to another, including from one vertex to itself.\nif there are 5 vertices, R11, R22, R33, R44, R55 = epsilon, and all direct paths between vertices are equal to their transition symbol(s). if a vertex has a loop/arc back to itself given a certain input symbol, it will be epsilon + that symbol
      - r222= r122 + (r122(r122)*r122)
        k=2 i=2 j=2 p=1
        r222 = a+e + ((a+e)(a+e)*(a+e))
        r222 = a + (a(a)*a)
        r11 = e
        r33 = e
        r12 = a+b
        r31 = b
        r23 = b
        r122 = a+e
    - - ex 1:
        
        https://gitmindhk.aoscdn.com/app%2Fgitmind-com%2Fresources%2Fdocs%2Fl8c19e1ohy7c%2F1696106220599_TeJtcoyphoaJrfUX3kA651O66Pse5i.png?auth_key=1725991673-512470-328105-646f0dee2ff4a61b3915946baa2c9d1f&Expires=1725991673
        
        solution
      - ex 2:
        
        https://gitmindhk.aoscdn.com/app%2Fgitmind-com%2Fresources%2Fdocs%2Fl8c19e1ohy7c%2F1696106168243_GDYwTy5t3xa5qaMkTR3z9gFDVSUMmv.png?auth_key=1725991673-148785-652520-349a4f925eb2923d8d4e31502a5ee749&Expires=1725991673
        
        solution:
        
        r514 = r414 + (r415(r455)*r454)
        k=5
        i=1
        j=4
        r414 = null
        r314 = null
        r214 = null
        r114 = null
        cant work backwards, impossible to go from 1 to 4 without going through 5, so k must be equal or greater than 5
        r414 = 0 +
        given r514 = 110*(110*)*
        i= start
        j = end
        k = max node to get to j
        p=k-1
        rkij = rpij + (rpik(rpkk)*rpkj)
        find r614
        k = 6
        i = 1
        j - 4
        r614 = r514 + (r516(r566)*r564)
        find r 516, 566, r564
        rkij = rpij + (rpik(rpkk)*rpkj)
        k=5 p=4 i=1 j=6
        r516 = r416 + (r415(r455)*r456)
        r416= null, cant get from 1 to 6 without k=>5
        r415 = 1
        r455 = e + (10*1)
        r456 = 0, can go from 5 to 6, but cant go from 5 to 6 to 5, or 5 to 6 and loop to 6, because they would use a node higher than 4 as an intermediate state
        r516 = 1(10*1)*0
        rkij = rpij + (rpik(rpkk)*rpkj)
        r566 = r466 + (r465(r455)*r456)
        r466 = e+1
        r465 = 0
        r455 = e + (10*1)
        r456 = 0
        r566 = e+1 + (0(10*1)*0)
        r564 = r464 + (r465(r455)*r454)
        k=5 i = 6 j = 4 p = 4
        r464 = null
        r465 = 0
        r455 = e + (10*1)
        r454 = 10*
        r564 = null + (0(e + (10*1))*10*)
        r564 = 0(10*1)*10*
  - - - language is not regular if there is any possible string that can be divided into a beginning, middle, and end, and have the middle part repeat infinitely, and not be considered a part of the language
      - Assume L is a regular language, for any string w of length n or greater than n, w can be broken into a beginning substring x, middle substring y, and ending substring z, such that
        
        y $\ne \epsilon $
        
        $ |xy| \le n $
        
        $\forall k \ge 0 $, $ \textrm{the string } xy^kz \textrm{ is also in L} $
        If there exists a string w of length greater than or equal to n in which any one of those properties is violated, the language is not regular.
    - - a language accepted by DFA AND regular expressions
    - - A $ \cup $ B
        A $\cap $ B
        A - B
        A^R
        changing a character in $\sum$ (alphabet of a language)
        or changing a character from a single character to a set of characters( ex: c is replaced with cat)\nchanging a substring in a list of strings to a symbol\nex: {aa,aaa,baa,aaaa,abaa,baaa,bbaa,...} replacing all strings "ba" with "w": {aa,aaa,wa,aaaa,waa,waa,bwa,...}
    - - two states are equal if both are accepting or neither are accepting, there are no strings in which one accepts and the other doesnt
        
        two states are distinguishable if the behavior of the two states are different, meaning if, given the same string, one state takes it to an acceptable state, and the other state does not
      - distinguishable FAs
        
        an FA is not distinguishable if there are two strings that it considers to be the same, despite them not being the same
      - decision procedure for distinguishing states
        
        set up table mapping each state to one another (2D table)
        
        first pass: mark final states with a "1"
        
        second pass: mark states that go to different acceptable/unacceptable states based on inputs as 2
        
        third pass
        
        same as second pass, go 2 characters deep and mark with 3 instead
        
        1 more item...
        
        if
        
        $ \begin{array} \\ & & q0 & q1 &q2 & q3 & q4 & q5 & q6 \\ \hline & q0 & & & 2 & 2 & 1 & 1 & & \\ \hline & q1 & & & 2 & 2 & 1 & 1 & & \\ \hline & q2 & 2 & 2 & & 2 & 1 & 1 & 2 & \\ \hline & q3 & 2 & 2 & 2 & & 1 & 1 & 2 & \\ \hline & q4 & 1 & 1 & 1 & 1 & X & X & 1 & \\ \hline & q5 & 1 & 1 & 1 & 1 & X & X & 1 & \\ \hline & q6 & & & 2 & 2 & 1 & 1 & & \\ \hline \end{array} $
        
        q0, 0 leads to q6, q0,1, leads to q1, move to third pass
        q1,0 leads to q3, q1,1 leads to q2 move to third pass
        q2,0 leads to q4, q2,1 leads to q6 distinguished from q01,q1 as q4 is known to be distinguishable from q6,q3 as shown by fist pass
        q3,0 leads to q6, q2,1 leads to q5 distinguished from q0,q1,q2 as q6 is known to be distinguishable from q1,q2,q6 as shown by first pass
        q6,0 leads to q6, q6,1 leads to q6 distinguished from q2,q3, as q4 and q5 are known to be distinguishable from q6 as shown by first pass
        
        1 more item...
        
        how to read: y axis is distinguishable from x axis
        row from column
        
        aka, states that act differently when fed the empty string
        
        states cannot be distinguisable from themselves, so all squares will be marked as 1 in their rows/column other than the squares where the row and column state are both final states, this same logic applies to all states, no state can be distinguished from itself
        
        $ \begin{array} \\ & q0 & q1 &q2 & q3 & q4 & q5 & q6 \\ \hline & q0& & & & 1 & 1 & & \\ \hline & q1& & & & 1 & 1 & & \\ \hline & q2& & & & 1 & 1 & & \\ \hline & q3& & & & 1 & 1 & & \\ \hline & q4 &1&1& 1 & & & 1& \\ \hline & q5 &1&1& 1 & & & 1& \\ \hline & q6 & & & & 1 & 1 & & \\ \hline \end{array} $
    - - decision procedure
- - - - shortened version of finite state automata
      - FA = FSA
      - deterministic
    - - circle = state, line = transition, line with text = input causing transition(input condition), line with text leading to and from a single state = that state when supplied that input will lead back to that state, state that is "final" has double circle
        
        transition = movement from one state to another
        
        heat causes change of state in matter
        
        final = accepted = accepted language
      - questions to ask when analyzing a state diagram
        
        what are the possible ways to get to final?
        
        what are the possible ways to NOT get to final state?
        
        what are the symbols on lines? thats your alphabet
        
        notes from analyzing this diagram
        
        answer:
        
        all strings a,b that do not contain the substring aa
        
        https://gitmindhk.aoscdn.com/app%2Fgitmind-com%2Fresources%2Fdocs%2Fqhd4kdriqm7j%2F1694886143810_EY9B1OA9iYtA4r8iuNQvnSYXcGaV4x.png?auth_key=1725989920-043512-737179-02e2d8eb65d364bb402bfaba5f3ec1e1&Expires=1725989920
        
        https://gitmindhk.aoscdn.com/app%2Fgitmind-com%2Fresources%2Fdocs%2Fqhd4kdriqm7j%2F1694886093561_nBQci6Q9kfPlO3tdjJjs2q9UX2kkOb.png?auth_key=1725989920-697750-038681-6db8264288b8a2652798c43918235919&Expires=1725989920
      - questions to ask when creating a state diagram
        
        what cases must be satisfied and how do i test them
        
        what boundary cases do i need to test for (ex: empty string)
        
        start with diagrams you know to be correct, then determine if you can merge start states and final states
        
        what set of strings does each state represent, if you dont know what set of strings would lead to a state, consider whther you need it or not
        
        ex: given $ \{\ 01,101\}\ ∗ $
        what do q1, q4, q5 represent?
        from image :https://gitmindhk.aoscdn.com/app%2Fgitmind-com%2Fresources%2Fdocs%2Fqhd4kdriqm7j%2F1694886514194_GoaXeig5X3CVangc5HrhxvehBgAP2n.png?auth_key=1725989920-184586-996606-18501134a9e8bbc39dd488aa8ffe47ce&Expires=1725989920
        
        q1 = strings starting with 01 and ending in 01, that may have an extra 0 (note the only symbol leading out is a 1), so as soon as it hits 1 it moves to next state, s0 {01,101}∗{0}
        
        q4 = strings starting and ending with 101 that may have an extra 1 ( note the only symbol leading out is a 0), so as soon as it hits 0 it moves to next state, so {01,101}∗{1}
        
        q5 = strings starting and ending with 101 that may or may not have an extra 10,
        
        the pattern is that each one can have as many repeating characters from previous transitions as they want, as long as they end in 01 or 101
    - - dfa = dfsa
      - deterministic = can only be in one state at a time
        
        state = collection of information remembered by a system
        
        state of the union is info about the us at that point in time
      - finite = only a finite number of possible states
        
        Q
      - finite automata (FA) definition
        
        FA = (Q,Σ,q0,A,δ)
        
        Q = finite set of states
        
        Σ = finite input alphabet(set of non-empty symbols
        
        q0 = initial state, q0 ∈Q ( the initial state is a member of the finite set of states)
        
        A = set of accepting states, A ⊆Q (A is a subset of the finite set of states)
        
        δ = , the transition function
        
        Q x Σ -> Q(each single state multiplied by each single input for each input leads to a state)
        
        set multiplication, ex
        
        {1,2,3} x {a,b} = {(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)}
        
        given Q={q0,q1,q2,0,1,2}\nΣ={0,1}δ would be
        $ \begin{array} \\ & &\text{Starting State}\\ \hline& & q0 & q1 &q2 & 0 & 1 & 2 \\ \hline \text{Input} & 0&q1&q2&q2&0&2&1 \\&1&1&q2&q2&1&0&2 \\ \hline \end{array} $
        
        set of pairs(functions), {state+input,result),(state+input,result2),....}
        
        the function (q0,0),q1) means state q0 when given input 0 will lead to q1
        
        the function (0,0),0) means state 0 when given input zero will lead to 0
        
        5-tuple
        
        tuple = finite SEQUENCE of elements
        
        5 tuple = sequence of 5 elements
        
        same for nondeterministic, only difference is δ
        
        for NFA, $δ = Q $ X $ Q $ x $Σ -> 2^Q $
        
        only difference in definitions between deterministic and nondeterministic is that the functions for DFA can only have one function for each input and output pair, while nondeterministic can have more than 1 function per input and output pair
    - - deterministic vs nondeterministic
        
        single thread vs multithread
      - nondeterministic = automata can be in multiple states at once
        
        like shrodingers cat, the state can either be outcome A or B given a single input
- - - - no memory, output can be represented using only truth tables with rows equal to $2^{numberOfVariables}$
      - 2 subtypes
        
        decoder
        
        converts n inputs to $2^n$ outputs
        
        encoder
        
        converts $2^n$ inputs to n outputs
    - - has memory, outputs determined by inputs combined with memory