Discrete Structures and Propositional Logic Note

Overview and Learning Outcomes

• Academic Institution: Superior University RAK Campus
• Subject: Discrete Structures
• Core Learning Outcomes:
  • Explain the importance and foundational applications of Discrete Structures in digital systems and computer science.
  • Identify, formalize, and construct logical statements and mathematical propositions.

Introduction to Discrete Structures

• Definition of Discrete Structures:
  • Discrete structures are mathematical objects characterized by distinct, separate values.
  • They provide the theoretical and mathematical foundation underlying computer science, digital logic, and computational systems.

• Primary Types of Discrete Structures:

  • Sets: Collections of distinct objects.
  • Functions: Mappings assigning elements from a domain to a codomain.
  • Sequences: Ordered lists of elements.
  • Relations: Structures defining associations between elements of sets.
  • Graphs: Networks comprising nodes (vertices) connected by edges.

• Discrete vs. Continuous Values:

  • Discrete Values:
  • Composed of integer values or isolated objects.
  • Countable in nature.
  • Either finite or countably infinite.
  • Continuous Values:
  • Composed of real numbers.
  • Uncountable in nature.
  • Infinite number of values exist between any two given distinct values.

• Why Study Discrete Structures?:

  • Foundation of Computer Science: Digital hardware and hardware logic operate fundamentally on discrete binary values ($0$\text{s} and $1$\text{s}).
  • Algorithm Design: Facilitates precise, rigorous reasoning regarding computational processes and efficiency.
  • Data Structures: Enables the systematic organization, storage, and manipulation of discrete data.
  • Cryptography: Underpins methods for securing information through discrete algebraic principles.
  • Database Theory: Governs the structuring and querying of discrete data relationships.
  • Artificial Intelligence: Provides the formal logic required to represent knowledge and construct automated reasoning engines.
  • Network Protocols: Assists in modeling, designing, and analyzing digital communication architectures.

Mathematical Propositions and Sentence Types

• Definition of a Proposition:

  • A proposition is a declarative statement that is strictly evaluated as either True or False, but never both simultaneously.

• Classification of English Sentence Types:

  • Declarative Sentences: Statements that state facts or opinions. Only declarative sentences can be propositions because they express factual claims capable of being assigned a truth value.
  • Interrogative Sentences: Sentences asking questions (e.g., "What time is it?"). These are non-propositions.
  • Imperative Sentences: Sentences giving commands or instructions (e.g., "Go out and play."). These are non-propositions.
  • Exclamatory Sentences: Sentences expressing strong emotion or feelings (e.g., "Have a nice day!"). These are non-propositions.

• Examples of Valid Propositions and Their Truth Values:

  • "The sun rises in the East and sets in the West" $\rightarrow\text{True}$
  • "$1 + 1 = 2$" $\rightarrow\text{True}$
  • "'b' is a vowel" $\rightarrow\text{False}$
  • "The Earth orbits around the Sun" $\rightarrow\text{True}$
  • "Water boils at $100\,^\circ\text{C}$ at sea level" $\rightarrow\text{True}$
  • "Humans need oxygen to survive" $\rightarrow\text{True}$

• Non-Examples of Propositions:

  • "What time is it?" $\rightarrow\text{Question (Interrogative)}$
  • "Go out and play." $\rightarrow\text{Command (Imperative)}$
  • "$x + 1 = 2$" $\rightarrow\text{Open Sentence (Truth depends on the value of variable } x \text{)}$
  • "Have a nice day!" $\rightarrow\text{Expression / Exclamation}$
  • "Please close the door" $\rightarrow\text{Command (Imperative)}$
  • "How old are you?" $\rightarrow\text{Question (Interrogative)}$
  • "What a beautiful day!" $\rightarrow\text{Exclamation}$

• Key Takeaway:

  • Only declarative sentences qualify as propositions because they make explicit factual assertions that evaluate to either True or False.

Practice Problems: Expressing Statements in Symbolic Form

• Formalizing Statements into Propositional Logic ($P \land Q$, $P \lor Q$, or $\sim P$):
  1. Statement: "The number 8 is both even and a power of 2."
  • Variables: Let $P$: "8 is even", Let $Q$: "8 is a power of 2".
  • Required Form: $P \land Q$
  1. Statement: "The matrix A is not invertible."
  • Variables: Let $P$: "Matrix A is invertible".
  • Required Form: $\sim P$
  1. Statement: "$x < y$"
  • Variables: Let $P$: "$x < y$".
  • Required Form: $P$
  1. Statement: "$y \ge x$"
  • Variables: Let $P$: "$y \ge x$".
  • Required Form: $P \lor Q$ (representing $y > x \lor y = x$).
  1. Statement: "There is a quiz scheduled for Wednesday or Friday."
  • Variables: Let $P$: "There is a quiz on Wednesday", Let $Q$: "There is a quiz on Friday".
  • Required Form: $P \lor Q$
  1. Statement: "The number x equals zero, but the number y does not."
  • Variables: Let $P$: "$x = 0$", Let $Q$: "$y \neq 0$".
  • Required Form: $P \land Q$
  1. Statement: "At least one of the numbers x and y equals 0."
  • Variables: Let $P$: "$x = 0$", Let $Q$: "$y = 0$".
  • Required Form: $P \lor Q$

Notation and Foundations of Propositional Logic

• Propositional Notation:

  • In propositional logic, lowercase letters represent atomic propositions, analogous to algebraic variables.
  • Common symbolic designations:
  • $p$: First proposition
  • $q$: Second proposition
  • $r$: Third proposition

• Definition of Propositional Logic:

  • A branch of mathematics analyzing the logical connections between propositions treated as whole units.

• Core Focus Areas:

  • Relationships between propositions established via logical connectives.
  • Evaluation of truth values and construction of truth tables.
  • Analysis and derivation of logical equivalences.
  • Development of foundational structures for logical reasoning.

• Fields of Application:

  • Mathematics
  • Digital Circuits
  • Computer Science
  • Artificial Intelligence
  • Decision Making
  • Linguistics

Negation of Propositions

• Definition:

  • The negation of a proposition $p$ is denoted by $\neg p$ (or $\sim p$), which reads "not $p$".
  • The truth value of $\neg p$ is always the exact opposite of the truth value of $p$.

• Truth Table for Negation:

• Weather Example:

  • Let $p$ = "It is raining today"
  • Negation $\neg p$ = "It is not raining today"
  • Truth Value Analysis:
  • If it is raining ($p = \text{True}$), then "It is not raining today" is False ($\neg p = \text{False}$).
  • If it is not raining ($p = \text{False}$), then "It is not raining today" is True ($\neg p = \text{True}$).

• Real-Life Examples:

  • "The sky is blue" $\rightarrow$ "The sky is not blue"
  • "I am hungry" $\rightarrow$ "I am not hungry"
  • "The store is open" $\rightarrow$ "The store is not open"

Compound Propositions and Logical Connectives

• Definition:

  • A compound proposition is formed by joining two or more atomic propositions using logical connectives.

• Standard Logical Connectives:

  • Conjunction (AND): Denoted by $\land$
  • Disjunction (OR): Denoted by $\lor$
  • Exclusive OR (XOR): Denoted by $\oplus$
  • Implication (Conditional): Denoted by $\rightarrow$
  • Biconditional: Denoted by $\leftrightarrow$

• Examples of Compound Statements:

  • Conjunction: "I will go to the park and I will bring my dog"
  • Disjunction: "It is sunny or it is cloudy"
  • Implication: "If it rains, then I will take an umbrella"

• Structural Example Analysis:

  • Let $p$ = "Today is Friday"
  • Let $q$ = "It is raining today"
  • $p \land q$ = "Today is Friday and it is raining today"
  • Evaluates to True strictly when both $p$ and $q$ are True.
  • Evaluates to False if either "Today is Friday" is False or "It is raining today" is False.
  • $p \lor q$ = "Today is Friday or it is raining today"
  • $p \rightarrow q$ = "If today is Friday, then it is raining today"

Conjunction

• Definition:

  • The conjunction of propositions $p$ and $q$ is denoted by $p \land q$, meaning "$p$ and $q$".
  • A conjunction is True only when both $p$ and $q$ are True.

• Truth Table for Conjunction:

• Real-Life Examples:

  • "I will study and I will pass the exam"
  • "The sky is blue and the grass is green"
  • "She is tall and she is smart"

• Algebraic Properties of Conjunction:

  • Commutative Property: $p \land q \equiv q \land p$
  • Associative Property: $(p \land q) \land r \equiv p \land (q \land r)$

Disjunction

• Definition:

  • The disjunction of propositions $p$ and $q$ is denoted by $p \lor q$, meaning "$p$ or $q$".
  • A disjunction is True when at least one proposition ($p$, $q$, or both) is True. It is False only when both propositions are False.

• Truth Table for Disjunction:

• Real-Life Examples:

  • "I will study or I will watch TV"
  • "It is sunny or it is cloudy"
  • "You can pay with cash or with a credit card"

• Algebraic Properties of Disjunction:

  • Commutative Property: $p \lor q \equiv q \lor p$
  • Associative Property: $(p \lor q) \lor r \equiv p \lor (q \lor r)$

Exclusive OR (XOR)

• Definition:

  • The exclusive OR of propositions $p$ and $q$ is denoted by $p \oplus q$, meaning "either $p$ or $q$, but not both".
  • An exclusive OR evaluates to True strictly when exactly one of $p$ or $q$ is True.

• Truth Table for Exclusive OR:

• Real-Life Examples:

  • "You can have either tea or coffee, but not both"
  • "The light is either on or off"
  • "You can choose either the red shirt or the blue shirt"

• Algebraic Properties and Equivalences:

  • Commutative Property: $p \oplus q \equiv q \oplus p$
  • Alternative Boolean Expression: $p \oplus q \equiv (p \lor q) \land \neg(p \land q)$

Implication (Conditional Statements)

• Definition:

  • The implication of propositions $p$ and $q$ is denoted by $p \rightarrow q$, meaning "if $p$ then $q$".
  • In $p \rightarrow q$, $p$ represents the premise (hypothesis) and $q$ represents the conclusion.
  • An implication is False only when the premise $p$ is True and the conclusion $q$ is False.

• Truth Table for Implication:

• Real-Life Examples:

  • "If it rains, then the ground will be wet"
  • "If you study, then you will pass the exam"
  • "If the traffic light is red, then you must stop"

• Key Logical Equivalences for Implication:

  • Alternative Expression: $p \rightarrow q \equiv \neg p \lor q$
  • Contrapositive Expression: $p \rightarrow q \equiv \neg q \rightarrow \neg p$

Types of Implication and Logical Equivalences

• The Four Related Conditional Statements:
  • Conditional Statement: $p \rightarrow q$
  • Converse Statement: $q \rightarrow p$
  • Inverse Statement: $\neg p \rightarrow \neg q$
  • Contrapositive Statement: $\neg q \rightarrow \neg p$

• Master Truth Table Comparison:

• Fundamental Equivalences:

  • A Conditional statement is logically equivalent to its Contrapositive:     $p \rightarrow q \equiv \neg q \rightarrow \neg p$
  • The Converse statement is logically equivalent to the Inverse statement:     $q \rightarrow p \equiv \neg p \rightarrow \neg q$

• Real-Life Illustrative Examples:

  • Conditional: "If it is raining, then I will take an umbrella"
  • Converse: "If I take an umbrella, then it is raining"
  • Inverse: "If it is not raining, then I will not take an umbrella"
  • Contrapositive: "If I do not take an umbrella, then it is not raining"

• Practical Proof Implications:

  • Proving a statement is logically identical to proving its contrapositive.
  • Disproving a statement is logically identical to disproving its contrapositive.

Biconditional Statements

• Definition:

  • The biconditional of propositions $p$ and $q$ is denoted by $p \leftrightarrow q$, meaning "$p$ if and only if $q$" (abbreviated as "$p$ iff $q$").
  • A biconditional evaluates to True when $p$ and $q$ possess the identical truth value (both True or both False).

• Truth Table for Biconditional:

• Real-Life Examples:

  • "You can vote if and only if you are 18 years or older"
  • "The light is on if and only if the switch is up"
  • "I will go to the party if and only if you go with me"

• Properties & Relationship to Implication:

  • Relationship to Implication: $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$
  • Commutative Property: $p \leftrightarrow q \equiv q \leftrightarrow p$

Comprehensive Practice Problems and Solutions

• Truth Table Verification Problems (Problems 1–9):

  1. Truth Table for $P \lor (Q \Rightarrow R)$

2. Truth Table for $(Q \lor R) \Leftrightarrow (R \land Q)$

3. Truth Table for $\sim(P \Rightarrow Q)$

4. Truth Table for $\sim(P \lor Q) \lor (\sim P)$

5. Truth Table for $(P \land \sim P) \lor Q$

6. Truth Table for $(P \land \sim P) \land Q$

7. Truth Table for $(P \land \sim P) \Rightarrow Q$

8. Truth Table for $P \lor (Q \land \sim R)$

9. Truth Table for $\sim(\sim P \lor \sim Q)$

• Analytical Deductive Problems Without Truth Tables:

  • Problem 10: Suppose the statement $((P \land Q) \lor R) \Rightarrow (R \lor S)$ is False. Find the truth values of $P, Q, R,$ and $S$

  • Step 1: An implication $X \Rightarrow Y$ is False if and only if premise $X$ is True and conclusion $Y$ is False. Here, $X = ((P \land Q) \lor R)$ and $Y = (R \lor S)$.

  • Step 2: Evaluate conclusion $(R \lor S) = \text{False}$. A disjunction is False if and only if both components are False. Therefore, $R = \text{False}$ and $S = \text{False}$.

  • Step 3: Substitute $R = \text{False}$ into the premise: $((P \land Q) \lor \text{False}) = (P \land Q)$. For the premise to be True, $(P \land Q)$ must be True.

  • Step 4: A conjunction $(P \land Q)$ is True if and only if both components are True. Therefore, $P = \text{True}$ and $Q = \text{True}$.

  • Final Results: $P = \text{True}$, $Q = \text{True}$, $R = \text{False}$, $S = \text{False}$.

  • Problem 11: Suppose $P$ is False and the statement $(R \Rightarrow S) \Leftrightarrow (P \land Q)$ is True. Find the truth values of $R$ and $S$

  • Step 1: Given $P = \text{False}$, the conjunction $(P \land Q)$ evaluates to False regardless of the value of $Q$.

  • Step 2: The biconditional $(R \Rightarrow S) \Leftrightarrow (P \land Q)$ is given as True. A biconditional is True when both sides share the same truth value.

  • Step 3: Since the right side $(P \land Q)$ is False, the left side $(R \Rightarrow S)$ must also be False.

  • Step 4: An implication $(R \Rightarrow S)$ is False if and only if the premise $R$ is True and the conclusion $S$ is False.

  • Final Results: $R = \text{True}$, $S = \text{False}$.

Applications of Discrete Structures in Computer Science

• Algorithm Design: Enables formal, precise mathematical reasoning and proof of correctness regarding computational steps and software processes.
• Cryptography: Provides foundational logical, modular, and algebraic principles required to build encryption algorithms and secure communications.
• Database Systems: Forms the mathematical model for relational databases (relational algebra), facilitating accurate query processing and data relationship management.
• Artificial Intelligence: Supplies propositional and predicate logic for knowledge representation, automated theorem proving, and cognitive reasoning frameworks.
• Programming: Underpins conditional execution logic ($\text{if-else}$ statements), boolean expression evaluation, and computer arithmetic operations.