Discrete Structures: Propositional Logic

Discrete Structures

• This course covers mathematical elements of IT and computer science.
• Topics include propositional logic, set theory, functions, relations, graphs, trees, and Boolean logic.
• Students will learn to recognize and express mathematical ideas graphically, numerically, symbolically, and in writing.

Course Intended Learning Outcomes

• Perform operations with sets, functions, and relations, and relate them to computer programming.
• Construct sound arguments in propositional and predicate logic using rules of inference.
• Construct valid mathematical proofs using mathematical induction, direct proof, and proof by contradiction.
• Use these proofs to simplify programs and prove program correctness.

Propositional Logic

• Logic provides meaning to mathematical assertions and differentiates between correct and incorrect mathematical arguments.
• This unit teaches how to understand and develop sound mathematical arguments through propositional logic.
• Logic is important for mathematical reasoning and has applications in technology, including:
  • Design of computer programs
  • Verification of program correctness
  • Development of automated proof systems

Learning Outcomes

• Write English sentences for logical expressions and vice-versa.
• Use standard notations of propositional logic.
• Construct complete and accurate truth tables for logical expressions involving logical connectives.
• Determine logical equivalence between propositions.
• Show that a compound proposition is a tautology, contradiction, or contingency.
• Identify rules of inference in compound propositions.
• Evaluate the validity of an argument by identifying critical rows.

Introduction to Discrete Structures: Logic and Propositions

• The basic building blocks of logic are propositions.
• Logic is the study of correct reasoning, focusing on the relationship among statements.
• Example sequence of statements:
• All students take IT 123.
• Anyone who takes IT 123 is BSIT.
• Therefore, all students are BSIT.
• If the first two statements are true, logic assures the third is also true.
• A proposition is a declarative sentence that is either true or false, but not both.
• Propositional logic operates at the sentential level.
• The smallest unit in propositional logic is a sentence (proposition).

Propositions Examples

• Examples of propositions:
• Washington, D.C. is the capital of the USA (true).
• Toronto is the capital of Canada (false).
• 1 + 1 = 2 (true).
• 2 + 2 = 3 (false).
• Examples of non-propositions:
• Where are you going? (not a statement)
• Read this carefully. (not a statement)
• x + 1 = 2 (variable not assigned a value)
• x + y = 3 (variables not assigned values)

Types of Propositions

• Primitive Propositions: Cannot be broken down into simpler propositions.
• The propositions in Example 1 are all primitive.
• Compound Propositions: Composite propositions made of sub-propositions and connectives.
• "Roses are red and violets are blue" has sub-propositions "Roses are red" and "violets are blue."
• "John is intelligent or studies every night" has sub-propositions "John is intelligent" and "John studies every night."

Propositions and Its Elements: Logical Connectives

• Compound propositions are formed using logical connectives.

Logical Connectives: Negation

• Negation of p: ¬p (not p)
• ¬p is read as "not p."
• The truth value of ¬p is the opposite of the truth value of p.
• Truth tables represent the relationships between a proposition's value and its variables.
• The truth table for negation:
• If p is true, ¬p is false.
• If p is false, ¬p is true.
• Example:
• Proposition: "Richard's PC runs Linux."
• Negation: "It is not the case that Richard's PC runs Linux" or "Richard's PC does not run Linux."
• Proposition: "Anna's smartphone has at least 32GB of memory."
• Negation: "It is not the case that Anna's smartphone has at least 32GB of memory" or "Anna's smartphone does not have at least 32GB of memory”.

Logical Connectives: Conjunction

• Conjunction of p and q: p ∧ q ("p and q")
• p ∧ q is true only when both p and q are true; otherwise, it is false.
• Truth Table for Conjunction:
• p is true, q is true, p ∧ q is true.
• p is true, q is false, p ∧ q is false.
• p is false, q is true, p ∧ q is false.
• p is false, q is false, p ∧ q is false.
• Example:
• p: Rebecca's PC has more than 16GB free hard disk space.
• q: The processor in Rebecca's PC runs faster than 1 GHz.
• p ∧ q: Rebecca's PC has more than 16GB free hard disk space, and its processor runs faster than 1 GHz.
• The conjunction is true only if both conditions are true; it is false if one or both are false.

Logical Connectives: Disjunction

• Disjunction of p and q: p ∨ q ("p or q")
• p ∨ q is false only when both p and q are false; otherwise, it is true.
• Truth Table for Disjunction:
• p is true, q is true, p ∨ q is true.
• p is true, q is false, p ∨ q is true.
• p is false, q is true, p ∨ q is true.
• p is false, q is false, p ∨ q is false.
• Example:
• p: Rebecca's PC has more than 16GB free hard disk space.
• q: The processor in Rebecca's PC runs faster than 1 GHz.
• p ∨ q: Rebecca's PC has at least 16GB free hard disk space, or the processor in Rebecca's PC runs faster than 1 GHz.
• This disjunction is true if Rebecca's PC has at least 16GB hard disk space, if the PC's processor runs faster than 1 GHz, or both.
• It is false only if both conditions are false.

Conditional Statements

• Conditional statement: p→q ("if p, then q")
• p→q is false when p is true and q is false, and true otherwise.
• In p→q, p is the hypothesis (antecedent or premise), and q is the conclusion (consequence).
• p→q asserts that q is true on the condition that p holds.
• A conditional statement is also called an implication.
• Truth Table for Conditional Statement:
• p is true, q is true, p→q is true.
• p is true, q is false, p→q is false.
• p is false, q is true, p→q is true.
• p is false, q is false, p→q is true.

Conditional statements terminology

• Terminology to express p → q:
• "if p, then q"
• "if p,q"
• "p is sufficient for q”
• "q if p"
• "q when p”
• "a necessary condition for p is q"
• "q unless ¬p"
• "p implies q”
• "p only if q"
• “a sufficient condition for q is p”
• "q whenever p"
• "q is necessary for p"
• “q follows from p”
• Example:
• p: Maria learns Discrete Structures.
• q: Maria will find a good job.
• p → q: "If Maria learns Discrete Structures, then she will find a good job."
• Other expressions:
• "Maria will find a good job when she learns discrete structures.”
• "For Maria to get a good job, it is sufficient for her to learn discrete structures.”
• "Maria will find a good job unless she does not learn discrete structures.”

Converse, Contrapositive, and Inverse

• For a conditional statement p → q:
• Converse: q → p
• Contrapositive: ¬q → ¬p
• Inverse: ¬p → ¬q
• Example:
• "If Bobcats win this game, then they will be number one.”
• Contrapositive: If Bobcats aren't number one, then they didn't win.
• Converse: If Bobcats are number one, then they won the game.
• Inverse: If Bobcats don't win this game, then they will not be number one.
• The contrapositive is always logically equivalent to the original proposition.
• It has the same truth value regardless of the values of its constituent variables.
• Example:
• "If it rains, then I get wet" is logically equivalent to "If I don't get wet, then it does not rain."

Biconditional Statement

• Biconditional statement: p ↔ q
• Expresses that two propositions have the same truth value.
• p ↔ q is the proposition "p if and only if q."
• p ↔ q is true when p and q have the same truth values, and false otherwise.
• Biconditional statements are also called bi-implications.
• Truth Table for Biconditional Statement:
• p is true, q is true, p ↔ q is true.
• p is true, q is false, p ↔ q is false.
• p is false, q is true, p ↔ q is false.
• p is false, q is false, p ↔ q is true.
• Common ways to express p ↔ q:
• "p is necessary and sufficient for q”
• "if p then q, and conversely”
• "p iff q"
• Example:
• p: You can take the flight.
• q: You buy a ticket.
• p ↔ q: You can take the flight if and only if you buy a ticket.

Precedence Rules

• Rules for forming statements with logical connectives:
• Not (¬)
• And (∧)
• Or (∨)
• If-then (→)
• If and only if (↔)
• Parentheses can be used to specify the order of operations.
• The precedence order is defined to reduce the number of parentheses.

Translating English Sentences into Symbolic Form

• Example propositions:
• p: I will go to Manila
• q: I have money
• r: I will attend a seminar
• s: the topic is interesting
• m: I will learn a lot
• n: the speaker is intelligent
• English Statement: I will not go to Manila; Symbolic Form: ¬p
• English Statement: If I have money then I will go to Manila and I will attend a seminar; Symbolic Form: q → p ∧ r
• English Statement: Neither I will go to Manila nor I will attend a seminar; Symbolic Form: ¬(p ∨ r)
• English Statement: Either the topic is interesting or the speaker is intelligent then I will learn a lot; Symbolic Form: (s ∨ n) → m
• English Statement: I will go to Manila if and only if I have money; Symbolic Form: p ↔ q
• English Statement: The speaker is not intelligent or I will attend a seminar; Symbolic Form: ¬n ∨ r
• English Statement: I will go to manila if and only if I have money and I will attend a seminar; Symbolic Form: p ↔ (q ∧ r)
• English Statement: If the speaker is intelligent and the topic is interesting then I will learn a lot; Symbolic Form: n ∧ s → m
• English Statement: I will attend a seminar or I will go to Manila and I have money; Symbolic Form: r ∨ p ∧ q

Truth Tables of Compound Propositions

• Truth tables determine the truth values of compound propositions.
• The truth value of a proposition depends on the truth values of its variables.
• The truth values of a compound proposition for each combination of truth values of the propositional variables are found in the final column of the table.
• Example: Construct the truth table of the compound proposition (p ∨ ¬q) → (p ∧ q)
• List all the truth values if p and q: TT, TF, FT, and FF
• Find the truth values of ¬q (needed to find the truth value of p ∨ ¬q)
• Find the truth values of p ∨ ¬q, p ∧ q and, (p ∨ ¬q) → (p ∧ q)

Propositional Equivalences

• Replacing an assertion with one of equal truth value maintains mathematical argument integrity.
• Compound propositions are created using logical operators with propositional variables.
• Compound propositions are categorized by their truth values.

Tautologies and Contradictions

• Tautology: Always true, regardless of the truth values of its variables.
• Contradiction: Always false, regardless of the truth values of its variables.
• Tautologies and contradictions play an important role in mathematical reasoning.
• Example:
• p ∨ ¬p is a tautology.
• p ∧ ¬p is a contradiction.

Logical Equivalences

• Logically equivalent compound propositions have identical truth values for all variable cases.
• Compound propositions p and q are logically equivalent if and only if they have identical truth values for each substitution of their component statement variables.
• This is denoted with the expression p ≡ q.
• The symbol ≡ is not a logical connective, and p ≡ q is not a compound proposition but rather it is the statement that p ↔ q is a tautology.

Verifying Logical Equivalences with Truth Tables

• Verify that ¬ (p ∨ q) is logically equivalent to ¬p ∧ ¬q.
  • If both propositions have the same truth, then they are logically equivalent.
• Show that p → q and ¬p ∨ q are logically equivalent.
  • If the truth value for all the statement variables for p → q and ¬p ∨ q is the same, then the propositions are logically equivalent.

Argument and Proofs: Valid Arguments in Propositional Logic

• An argument is an assertion: a set of propositions P1, P2, ..., Pn (premises) yields another proposition Q (conclusion).
• An argument is valid if true premises imply a true conclusion.
• Notation for such an argument: P1, P2, ..., Pn ⊢ Q.
• An argument is a sequence of statements:
  • Statement 1
  • Statement 2
  • Therefore, Statement 3
• Statements 1 and 2 are the premises, and statement 3 is the conclusion.

Evaluating Arguments

• Example:
• If you have a password, then you can log in to the computer.
• You have a password.
• Therefore, you can log in to the computer.
• This argument is valid if the conclusion "You can log in to the computer" is true when the premises "If you have a password, then you can log in to the computer" and "You have a password" are true.
• If p represents "You have a password" and q represents "You can log in to the computer", then the argument form is: p → q p ∴ q
• In this argument, if p → q and p are true, then q must also be true. This argument form is valid because whenever the premises (p → q and p) are true, the conclusion (q) must also be true.

Checking Argument Validity

• To check the validity of an argument:
• Construct a truth table for the premises and conclusion.
• Find rows where all premises are true (critical rows).
• If the conclusion is true in each critical row, the argument form is valid.
• If a row exists where the conclusion is false, the argument form is invalid or a fallacy.
• Example 1 (Valid Argument): p, p → q ⊢ q
• p is true in row 1 and row 2
• p → q is true in row 1, 3, and 4
• p and p → q are simultaneously true in row 1, therefore q is also true; the argument is valid.
• Example 2 (Fallacy): p → q, q ⊢ p
• Both p → q and q are true in row 3, but the conclusion p is false.

Rules of Inference for Propositional Logic

• A truth table can be used to determne valid argument form, but with larger propositional variables, it can become tedious
• Instead, establish the validity of an argument form( rule on inference)
• Used as building blocks to create more completed argument forms
• The tautology (p ∧ (p → q )) → q is the basis of the rule of inference called modus ponens, or the law of detachment
• Leads to valid arguments p→q p ∴ q
• Hypotheses are written in a column, followed by a horizontal bar, followed by a line that begins with the therefore symbol and ends with the conclusion
• Modus ponens tells us that if a conditional statement and the hypothesis of the conditional statement are both true, the conclusion must also be true.
• Example 1:
• Argument 1: If it snows today, then we will go skiing”.
• Argument 2: It is snowing today.
• Therefore: We will go skiing
• Solution:
• If argument 1 and 2 are the hypotheses, they are true
• By modus ponens, it follows that the conclusion of the conditional statement is true.
• A valid argument can lead to an incorrect conclusion if one or more of its premises is false.