# Discrete Mathematics

## Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain exactly three 0s.

We will follow a similar approach to previous exercises to solve this exercise. Let’s define 5 states as follows: S0, the initial state S1 is the state when the automata read exactly one 0 S2 is the state when the automata read exactly two 0s S3 is the state when the automata read exactly three …

## Construct a deterministic finite-state automaton that recognizes the set of all bit strings that do not contain three consecutive 0s.

We will follow a similar approach to previous exercises to solve this exercise. Let’s define 4 states as follows: S0, the initial state S1 is the state when the automata read a 0 S2 is the state when the automata read a sequence of two 0s S3 is the state when the automata read a …

## Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain the string 101

We will follow a similar approach to previous exercises to solve this exercise. Let’s define 4 states as follows: S0, the initial state S1 is the state when the automata read a 1 S2 is the state when the automata read a 0 after a 1 S3 is the state when the automata read a …

## Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10

This exercise is a bit more difficult than the previous one. To solve this exercise, let’s use the following strategy: define states in which the automaton can be if it just reads a 1 or a 0. – We can have a state S1 which means the automaton read 0s. Therefore, from the state S0 …

## Construct a deterministic finite-state automaton that recognizes the set of all bit strings beginning with 01

To solve this exercise, we have to options. We can answer using a state table or state diagram. First, we need to consider that to be in the final state, we need first to start from S0, and recognize a 0, and then a 1. This tells us that we should have at least three …

## What rule of inference is used in each of these arguments?

“Rules of inferences” is an important topic in Discrete Mathematics. We can use a rule (s) of inferences to prove if an argument is valid or not. We can also use rules of inference to produce valid arguments. In mathematics, an argument is a sequence of statements. We have a valid argument if and only …

## Show that p → q and ¬q → ¬p are logically equivalent

The solution to this exercise is straightforward by constructing the truth table. By looking at the truth table for the two compound propositions p → q and ¬q → ¬p, we can conclude that they are logically equivalent because they have the same truth values (check the columns corresponding to the two compound propositions) Related …

## Negating propositions

A classic exercise in Discrete Mathematics is to negate a given proposition. Here, I’ll explain two things to consider after seeing how many students have problems solving this type of exercise. Background A proposition is a sentence that states a fact. It is True or False but not both. An example of a proposition is …

## Predicates and quantifiers: Exercise 9

Introduction The universal quantifier is denoted by ∀”. An example of how to interpret it is as follows: The statement “∀x P(x) is true if P(x) holds for all x in the universe of discourse.  On the other hand, if you can find x such that P(x) is false, then the statement “∀x P(x) is …

## What are propositional equivalences in Discrete Mathematics?

Propositional equivalences are used extensively in the construction of mathematical arguments. By using these equivalences, we can substitute propositions with other propositions with the same truth value. This proves to be very useful in different types of situations. Two compound propositions p and q are logically equivalent if p ↔ q is a tautology. The …