3. Foundations in Discrete Structures
Todo
Under construction for spring 2025
3.1. Propositional Logic
Propositional logic, also known as propositional calculus or boolean logic, is a branch of logic that deals with propositions and their combinations using logical connectives.
3.1.1. Key Concepts
- Propositions
Propositions are statements that can be either true or false, but not both. For example, “It is raining” is a proposition.
- Logical Connectives
These are operators used to form compound propositions:
Conjunction (AND, denoted as \(\wedge\)) The compound proposition \(p \wedge q\) is true only if both \(p\) and \(q\) are true.
Disjunction (OR, denoted as \(\vee\)) The compound proposition \(p \vee q\) is true if either \(p\) or \(q\) (or both) is true.
Negation (NOT, denoted as \(\neg\)) The negation \(\neg p\) is true if \(p\) is false.
Implication (IF-THEN, denoted as \(\Rightarrow\)) The implication \(p \Rightarrow q\) is true unless \(p\) is true and \(q\) is false.
Biconditional (IF AND ONLY IF, denoted as \(\iff\)) The biconditional \(p \iff q\) is true if both \(p\) and \(q\) are either true or false.
- Syntax and Semantics
The syntax of propositional logic refers to the formal rules for constructing valid formulas, while semantics deals with the truth values of these formulas.
- Truth Tables
These are used to determine the truth value of propositions under all possible combinations of truth values of their components.
- Tautologies and Contradictions
A tautology is a proposition that is always true, regardless of the truth values of its components. A contradiction is always false.
- Inference and Deduction
Propositional logic allows for the derivation of conclusions from a set of premises using rules of inference.
Propositional logic is foundational in various fields, including computer science, mathematics, and philosophy, as it provides the basic structure for reasoning and decision-making processes.
3.1.2. Examples
Modus Ponens is a basic form of argument in propositional logic. It follows the structure: If p implies q, and p is true, then q must also be true. Here is an example involving Modus Ponens:
Propositions:
\(p\): “It is sunny outside.”
\(q\): “We will go for a walk.”
Logical Formulation:
Premise: \(p \Rightarrow q\) (If it is sunny outside, then we will go for a walk.)
Premise: \(p\) (It is sunny outside.)
Conclusion: \(q\) (Therefore, we will go for a walk.)
In this example, the premises lead to the conclusion using the Modus Ponens rule. If the first premise is true (it is sunny outside), and the second premise is also true (if it is sunny, we go for a walk), then the conclusion (we will go for a walk) logically follows.
3.2. Predicate Logic
Predicate logic, also known as first-order logic, extends propositional logic by dealing with predicates and quantifiers. Unlike propositional logic, which operates on simple, unanalyzable propositions, predicate logic analyzes the internal structure of propositions.
3.2.1. Key Concepts
- Predicate
A predicate is a function that takes an object and returns a truth value. It essentially describes a property or a relation among objects.
- Quantifiers
Quantifiers are operators that specify the quantity of specimens in the domain of discourse that satisfy an open sentence (predicate).
- Universal Quantifier (\(\forall\))
Indicates that the statement holds for all elements in the domain.
- Existential Quantifier (\(\exists\))
Indicates the existence of at least one element in the domain that satisfies the statement.
- Domain of Discourse
The set of all objects under consideration in a particular discussion or problem.
3.2.2. Examples
Consider a domain of discourse consisting of animals. Let \(P(x)\) represent “x is a cat.”
Now, consider the statement:
This statement is false if the domain includes animals other than cats.
Expanding on the previous example, let’s add another predicate:
Let \(Q(x)\) represent “x can meow.”
Now, consider the statement:
This statement implies that if an animal is a cat, then it can meow. It is a true statement in the context of our understanding of cats.
To negate this, we assert the existence of at least one cat that cannot meow, which is represented as:
In natural language, this translates to:
“There exists an x such that x is a cat and x cannot meow.”
3.2.3. Recap
Predicate logic allows for the expression of more complex and nuanced statements about the world compared to propositional logic. Its use of quantifiers and predicates enables detailed analysis of the properties of objects and their relationships.
Todo
Add material on Sets, Proofs, and Induction