What is ‘Discrete Math’?

Discrete mathematics is the study of mathematical structures that can be considered “discrete” (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than “continuous” (analogously to continuous functions). Objects studied in discrete mathematics include integers, graphs, and statements in logic. In this study, topics in “continuous mathematics”, real numbers, calculus, or Euclidean, are not taken care of.

Then Why does CS Major study discrete math?

First, develop mathematical maturity, which is understanding and creating mathematical aguments. Programmers are a dime a dozem. Software engineeers with strong math backgrounds are balued. Pattern recognition or machine learning includes automatic typing correction on your smartphone, face detection in its camera, and speech recognition when you call an automated telephone service. Computational tasks in fields ranging from biology to finance require a good knowledge of optimization.

Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in branches of computer science, such as computer algorithms, programming languages, cryptography, automated theorem proving, and software development. Computer implementations are significant in applying ideas from discrete mathematics to real-world problems. Simply saying, it provides an essential foundation for virtually every area of computer science, and its applications are correspondingly vast.

Why is Logic a meaningful topic for a CS major to learn?

Logic’ is the language used for most formal specification languages and is fundamental for understanding much of the literature in verification and programming language foundations and design. Program verification and formal methods are seeing increasing adoption in the industry, and are being used in tandem with traditional testing techniques to increase the confidence that software behaves as it is supposed to. Also, Logic is the basis of all mathematical reasoning, and of all automated reasoning. It has practical applications to the design of computing machines (hardware), to the specification of systems, to artificial intelligence, computer programming, to programming languages, and to other areas of computer science, as well as to many other fields of study. FOL and higher-order logics are applied a lot in databases. Many query language have logical foundations. For example, Datalog (essentially a restricted version of Prolog for querying data) is logic programming language whose semantic is defined based on models for FOL formulas. Integrity constraints are expressed in sublanguages of FOL.

Logic: the study of formal or valid reasoning. Logically allows precision for technical specifications, contracts, medical protocols, computer hardware and software, mathematics, etc.

Propositions and Logical Operations

• The raw material for logic is the proposition - a declarative statement that is either true or false.

• Every proposition has a truth value: exactly one of the values true, or false.

• A propositional variable, typically p, q, r, or similar letter, is often used to represent a proposition, perhaps with an unknown truth value.

• In most cases, we readily and empirically recognize a proposition because (a) it is clearly true, (b) it is clearly false, and (c) it has a truth value even though we don’t know it.

• Logical operators create new propositions from the old. Logical and and or create a (compound) proposition from two original propositions. Logical negation (\(\neg\)) creates a new proposition by flipping the truth value of a single proposition.
• Search engines use logic, typically the logical and, to return web pages that have both (or all) of a list of search terms.

Proposition

‘Proposition’ is a declarative sentence that is either true or false. Propositions (statements) that are either true or false are the raw material of the mathematical industry.

Propositions plus connectives $\rightarrow$ new propositions

Connective	prop. p: “It is ranning.” prop. q: “I am at home.”	prop. variable form
Negation	It is not raining	$\neg$p
Conjunction	It is raining and I am at home	p \(\wedge\) q
Disjunction	It is raning or I am at home	p \(\vee\) q
Exclusive or	It is raining or I am at home, but not both	p ⊕ q
Conditional	If it is raining then I am at home	p \(\rightarrow\) q
Biconditional	It is raining if and only if I am at home	p \(\leftrightarrow\) q

Example

The following statements are propositions whether it is Ture or not.

• There is an integer that is both even and odd.
• Mies van der Rohe’s buildings have ornate embellishments.
• IIT was founded in 1940.

Following statements are NOT propositions whether it is True or not.

• What game includes “Go directly to jail, and do not pass ‘GO’?”
  • Because the question is not a proposition statement.
• Log on to website with your card credentials.

With the propositions
              p: It is below freezing.      q: It is snowing.
Represent the following propositions using p, q, and logical connectives.

(a) It is below freezing and snowing: p \(\wedge\) q

(b) It is below freezing but not snowing: p \(\wedge\) \(\neg\)q

(c) It is not below freezing and it is not snowing: \(\neg\)p \(\wedge\) \(\neg\)q

(d) It is either snowing or below freezing (or both): p \(\vee\) q         \(\rightarrow\) because of “or both”, the logical connective of this statement is inclusive or, NOT exclusive or.

Truth Table

Negation

p	\(\neg\)p
T	F
F	T

Conjunction

p	q	p \(\wedge\) q
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction

p	q	p \(\vee\) q
T	T	T
T	F	T
F	T	T
F	F	F

Exclusive or

p	q	p ⊕ q
T	T	F
T	F	T
F	T	T
F	F	F

Evaluating Compound Propositions

• Propositions can be joined together by the logical operators \(\wedge\), \(\vee\). Negation (\(\neg\)) only acts on one proposition and cannot join two together.
• Compound propositions can be joined together \(\wedge\), \(\vee\).
• The operator precedence is 1. \(\neg\) 2. \(\vee\) 3. \(\wedge\) 4. \(\rightarrow\) 5. \(\leftrightarrow\). In the absence of clarifying parentheses, the operator leftmost in this order is evaluated first.

Example

1. p \(\wedge\) q \(\vee\) r: ((p \(\wedge\) q) \(\vee\) r
2. p \(\vee\) \(\neg\)q \(\wedge\) p \(\vee\) r: _(p \(\vee\) ((\(\neg\)q) \(\wedge\)p) \(\vee\) r)
3. \(\neg\)p \(\wedge\) \(\neg\) q \(\vee\) r: _((\(\neg\)p) \(\wedge\) (\(\neg\)q)) \(\vee\) r

Translate the following English sentence into a compound proposition Either I won’t stay home from school today or there will be a blizzard or my car will not start.

• p: stay home
• q: blizzard
• r: car no start \(\Rightarrow\) (\(\neg\)p) ⊕ q ⊕ r

The reason why it is not disjunction (\(\vee\)) is the sentence starts with ‘Either’. Therefore, use ‘exclusive or (⊕).

Conditional Statements

The conditional statement captures the logical meaning of “hypothesis implies conclusion.” A conditional statement p \(\rightarrow\) q can be thought of as a one-way contract. When are you happy with the contract? Certainly when q is true, regardless of p. Would be unhappy if p is true, but q is false. For example, “p: you pay the price; q: you get the item.” When you pay the price and get the item, you are happy, but when you pay the price and do not get the item, you are not happy. In the other situation, do not pay the price and get the item, you are a happy, a free item. And do not get the item without paying, you are also happy. There are many ways of posing a conditional statement in English. Some of them are intuitive, but most have to be gotten used to or memorized. The conditional statement has closely related, important, relatives that are also conditional statements: the converse, the contrapositive, and the inverse, all based on the original conditional but with other switched or with negation. The biconditional statement, p \(\leftrightarrow\) q, can be thought of as a two-way contract, in which both parties make sure they don’t give away anything for free.

Truth Table

Conditional statement

p	q	p \(\rightarrow\) q
T	T	T
T	F	F
F	T	T
F	F	T

Biconditional statement

p	q	p \(\leftrightarrow\) q
T	T	T
T	F	F
F	T	F
F	F	T

Expressing the conditional

p \(\rightarrow\) q can be expressed in many ways.

• if p then q
• p implies q
• p is sufficient for q
• q whenever p
• q is necessary for p
• p only if q
• q if p
• q follows from p

Example

p: “I put money in the drink machine,” and q: “I get a cock;” what truth values of p and q make you happy about the whole coke-buying situation? Does your answer correspond to a truth table?

• p \(\rightarrow\) q

p	q	p \(\rightarrow\) q
T	T	T
T	F	F
F	T	T
F	F	T

NOTE: Whatever the result of the right-hand side, q, if the left-hand side, p, is False, then the conditional statement is True.

Reference

• Illinois Institue of Technology, Discrete Structure, CS 330 Spring 2023, prof. Matthew Bauer