Combinatorial and Algorithmic Mathematics (eBook)

From Foundation to Optimization

Baha Alzalg (Autor)

eBook Download: EPUB

2024
961 Seiten
Wiley (Verlag)
978-1-394-23596-4 (ISBN)

Infos

Detailed review of optimization from first principles, supported by rigorous math and computer science explanations and various learning aids

Supported by rigorous math and computer science foundations, Combinatorial and Algorithmic Mathematics: From Foundation to Optimization provides a from-scratch understanding to the field of optimization, discussing 70 algorithms with roughly 220 illustrative examples, 160 nontrivial end-of-chapter exercises with complete solutions to ensure readers can apply appropriate theories, principles, and concepts when required, and Matlab codes that solve some specific problems. This book helps readers to develop mathematical maturity, including skills such as handling increasingly abstract ideas, recognizing mathematical patterns, and generalizing from specific examples to broad concepts.

Starting from first principles of mathematical logic, set-theoretic structures, and analytic and algebraic structures, this book covers both combinatorics and algorithms in separate sections, then brings the material together in a final section on optimization. This book focuses on topics essential for anyone wanting to develop and apply their understanding of optimization to areas such as data structures, algorithms, artificial intelligence, machine learning, data science, computer systems, networks, and computer security.

Combinatorial and Algorithmic Mathematics includes discussion on:

• Propositional logic and predicate logic, set-theoretic structures such as sets, relations, and functions, and basic analytic and algebraic structures such as sequences, series, subspaces, convex structures, and polyhedra
• Recurrence-solving techniques, counting methods, permutations, combinations, arrangements of objects and sets, and graph basics and properties
• Asymptotic notations, techniques for analyzing algorithms, and computational complexity of various algorithms
• Linear optimization and its geometry and duality, simplex and non-simplex algorithms for linear optimization, second-order cone programming, and semidefinite programming

Combinatorial and Algorithmic Mathematics is an ideal textbook resource on the subject for students studying discrete structures, combinatorics, algorithms, and optimization. It also caters to scientists across diverse disciplines that incorporate algorithms and academics and researchers who wish to better understand some modern optimization methodologies.

Baha Alzalg is a Professor in the Department of Mathematics at the University of Jordan in Amman, Jordan. He has also held the post of visiting associate professor in the Department of Computer Science and Engineering at the Ohio State University in Columbus, Ohio. His research interests include topics in optimization theory, applications, and algorithms, with an emphasis on interior-point methods for cone programming.

Textauszug

1
Mathematical Logic

CHAPTER CONTENTS

1. 1.1 Propositions
2. 1.2 Logical Operators
3. 1.3 Propositional Formulas
4. 1.4 Logical Normal Forms
5. 1.5 The Boolean Satisfiability Problem
6. 1.6 Predicates and Quantifiers
7. 1.7 Symbolizing Statements of the Form “All P Are Q”
   1. Exercises
   2. Notes and Sources
   3. References

The term “logic” has a broad definition, and countless logics have been explored by philosophers, mathematicians, and computer scientists. For most individuals, “logic” typically refers to either propositional logic or predicate logic. Propositional logic, a classical form, involves two truth values (true and false). Predicate logic, on the other hand, expands upon propositional logic by allowing explicit discussion of objects and their properties.

In this chapter, we first study the propositional logic which is the simplest, and most abstract logic we can study. After that, we study the predicate logic. We start by introducing the notion of a proposition.

Throughout this chapter (and the entire book), denotes the set of all natural numbers, denotes the set of all integers, and denotes the set of all rational numbers. For example, 2 and are rational numbers, but and are irrational numbers. We also let denote the set of all real (rational and irrational) numbers.

1.1 Propositions

In this section, we define a proposition and introduce two different types of propositions with examples. To begin with, we have the following definition.

Definition 1.1 A proposition is a statement that can be either true or false.

It is essential to emphasize that the proposition must hold either a true or false value, and it cannot simultaneously possess both. We give the following example.

Example 1.1

Identify each of the following statements as a proposition or not and provide any required clarifications.

1. .
2. .
3. Hillary Clinton is a former president of the United States.
4. Bill Clinton is a former president of the United States.
5. Be careful.
6. Is Abraham Lincoln the greatest president that the United States has ever had?
7. .

Solution

1. “” is a proposition (a true proposition).
2. “” is a proposition (a false proposition).
3. “Hillary Clinton is a former president of the United States” is a proposition (a false proposition).
4. “Bill Clinton is a former president of the United States” is a proposition (a true proposition).
5. “Be careful” is not a proposition.
6. “Is Abraham Lincoln the greatest president that the United States has ever had?” is not a proposition.
7. “” is not a proposition. In fact, the values of the variables have not been assigned. So, we do not know the values of and , and hence it is neither true or false.

▄

Sometimes a sentence does not provide enough information to determine whether it is true or false, so it is not a proposition. An example is, “Your answer to Question 13 is incorrect.” The sentence does not tell us who we are talking about. If we identify the person, say “Adam’s answer to Question 13 is incorrect,” then the sentence becomes a proposition.

Note that, for a given statement, being not able to decide whether it is true or false (due to the lack of information) is different from being not able to know how to verify whether it is true or false. Consider Goldbach’s conjecture1: “Every even integer greater than 2 can be written as the sum of two primes.”2 Despite its origin dating back to 1742 and computational data suggesting its validity, this conjecture remains an open problem in number theory. It is impossible for this sentence to be true sometimes, and false at other times. As of now, no one has proved or disproved this claim, classifying it as a proposition with an undetermined truth value because it cannot simultaneously be both true and false, and its resolution may await future mathematical breakthroughs.

There are some sentences that cannot be determined to be either true or false. For example, the sentence: “This statement is false.” This is not a proposition because we cannot decide whether it is true or false. In fact, if the sentence: “This statement is false” is true, then by its meaning it is false. On the other hand, if the sentence: “This statement is false” is false, then by its meaning it is true. Therefore, the sentence: “This statement is false” can have neither true nor false for its truth value. This type of sentence is referred to as paradoxes.3 The study of a paradox has played a fundamental role in the development of modern mathematical logic.

Note that the sentence “This statement is false,” which is self-contradicting, is different from the sentence “This statement is true,” which is self-consistent on either choice. Nevertheless, neither is a proposition. The latter type of sentence is referred to as an anti-paradox.4 The question that arises now is: Why the sentence “This statement is true” is not a proposition? This question is left as an exercise for the reader.

We now define atomic (or primitive) propositions. Intuitively, these are the set of smallest propositions.

Definition 1.2 An atomic proposition is one whose truth or falsity does not depend on the truth or falsity of any other proposition.

According to Definition 1.2, we find that all the propositions in items – of Example 1.1 are atomic.

Definition 1.3 A compound proposition is a proposition that involves the assembly of multiple atomic propositions.

The following connectives allow us to build up compound propositions:

Example 1.2 The following proposition is compound.

Note that

• compound proposition 1 = (atomic proposition 1) (atomic proposition 2),
• compound proposition 2 = (compound proposition 1) (atomic proposition 3).

▄

In the realm of natural language, such as English, ambiguity is a recurring challenge that writers and readers encounter. The following remark says that slight variations in context could drastically alter the intended message.

Remark 1.1 Sentences in natural languages can often be ambiguous and words can have different meanings in the context in which they are used.

To illustrate Remark 1.1, we consider the following sentences:

• The sentence “You can download WhatsApp or Skype to ring friends” could mean that you can only download one of the applications or it could mean that you can download just one or download both.
• The sentence “I smelled a chlorine-like odor and felt ill” implies that the odor of chlorine made you sick, but the sentence “I am majoring in CS and minoring in Math” does not imply that majoring in CS caused you to minor in Math.
• The sentence “I went to Chicago and took a plane” could mean that you took a plane to travel to Chicago or it could mean that you went to Chicago and then took a plane from Chicago to another destination, such as Las Vegas.

In mathematics and computer science, it is important to avoid ambiguity and for sentences to have a precise meaning. This is why people have invented artificial languages such as Java.

1.1.1 Notations

Rather than writing out propositions in full, we will abbreviate them by using propositional variables: , etc.

Example 1.3 (Example 1.2 revisited)

In Example 1.2, let be the proposition “It is raining,” be the proposition “You are outside,” and be the proposition “You get wet.” Then we can abbreviate the compound proposition

▄

In Section 1.2, we will learn more about the connectives AND, OR, NOT, IF-THEN, and IFF. This will enable us to gain a comprehensive understanding of how these connectives function within the context of formal logic and the role they play in constructing logical statements and arguments.

1.2 Logical Operators

In this section, we study the following logical operators or connectives: Negation, conjunction, disjunction, exclusive disjunction, implication, and double implication.

Before starting with the logical operators, we introduce the truth tables which help us understand how such operators work by calculating all of the possible return values of atomic propositions.

Definition 1.4 A truth table is a mathematical table used to show the truth or falsity of a compound proposition depending on the truth or falsity of the atomic propositions from which it is constructed.

Examples of truth tables will be seen very frequently throughout this chapter.

1.2.1 Negation, Conjunction, and Disjunction

This part is devoted to introducing the logical operators:...

Produkt-Details

• Erscheint lt. Verlag: 31.7.2024
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• Schlagworte: algorithms • Artificial Intelligence • combinations • combinatorics • Computer Security • Computer systems • counting principles • data structures • Discrete Structures • Networks • Optimization • permutations • Recurrence-solving techniques
• ISBN-10: 1-394-23596-8 / 1394235968
• ISBN-13: 978-1-394-23596-4 / 9781394235964