Learn & Review: Master Discrete Math | Study Smarter with Asksia AI

Discrete Mathematics: Propositions and Connectives

This summary covers the fundamental concepts of propositions and logical connectives in discrete mathematics, including negation, conjunction, disjunction, and their corresponding truth tables.

1. Propositions

• Definition: A proposition is a declarative statement that is definitively either true or false.
• Representation: Propositions are typically represented by lowercase letters such as p, q, r, etc.

Examples of Propositions:

• "The sky is blue." (Can be assigned a truth value)
• "The moon is made of cheese." (Can be assigned a truth value, which is false)
• "Luke, I am your father." (Can be assigned a truth value, which is false)

Non-Examples of Propositions:

• "Sit down." (This is a command, not a statement that can be true or false.)
• "x + 1 = 2" (This is an open statement. It becomes a proposition only when a value is assigned to x. For example, if x=1, it's true; if x=5, it's false.)

2. Connectives

Connectives are operators used to form compound propositions from simpler propositions.

Types of Connectives:

• Negation:
  • Symbol: ¬ (or ~)
  • Read as: "not"
  • Example: If p is "The grass is green," then ¬p is "The grass is not green."
• Conjunction:
  • Symbol: ∧
  • Read as: "and"
  • Example: If p is "It is raining" and q is "I am home," then p ∧ q is "It is raining and I am home."
• Disjunction:
  • Symbol: ∨
  • Read as: "or"
  • Example: If p is "You passed MA 315" and q is "You passed MA 335," then p ∨ q is "You passed MA 315 or you passed MA 335."
• Implication:
  • Symbol: →
  • Read as: "if... then..."
  • Example: "If P then Q."
• Biconditional:
  • Symbol: ↔
  • Read as: "if and only if"
  • Example: "P if and only if Q." (Both propositions must share the same truth value.)

3. Truth Tables

Truth tables are used to determine the truth value of a compound proposition based on the truth values of its individual propositions.

Structure of a Truth Table:

• Left Side: Lists all possible combinations of truth values for the individual propositions.
• Right Side: Shows the resulting truth value of the compound proposition using the specified connective.

Truth Table for Negation (¬p):

• A truth table for a single proposition p has two rows: one for p being true and one for p being false.
• If p is True, ¬p is False.
• If p is False, ¬p is True.

| P | ¬p | | :---- | :---- | | True | False | | False | True |

Truth Table for Conjunction (p ∧ q):

• For two propositions (p and q), there are 2² = 4 possible combinations of truth values.
• A conjunction (p ∧ q) is true only if both p and q are true.

| P | Q | p ∧ q | | :---- | :---- | :---- | | True | True | True | | True | False | False | | False | True | False | | False | False | False |

Truth Table for Disjunction (p ∨ q):

• A disjunction (p ∨ q) is true if at least one of the propositions (p or q) is true.
• This is known as the inclusive OR.

| P | Q | p ∨ q | | :---- | :---- | :---- | | True | True | True | | True | False | True | | False | True | True | | False | False | False |

Inclusive OR vs. Exclusive OR (XOR):

• Inclusive OR (∨): True if p is true, q is true, or both are true. (Used in most mathematical contexts).
  • Example: Course prerequisites (passing either MA 315 or MA 335, or both, allows enrollment).
• Exclusive OR (XOR): True if either p is true or q is true, but not both.
  • Symbol: ⊕ (or sometimes indicated by context)
  • Example: Choosing between soup or salad with an entree (you can have one, but not both).

| P | Q | p ⊕ q | | :---- | :---- | :---- | | True | True | False | | True | False | True | | False | True | True | | False | False | False |

Combinations for Two Propositions:

When constructing truth tables with two propositions (p and q), it's recommended to list the combinations systematically:

1. p True, q True
2. p True, q False
3. p False, q True
4. p False, q False