DISCRETE STRUCTURES NOTES
LESSON 1: LOGIC
PROPOSITIONAL LOGIC
Statements which contain no variables and they are either always true or false. George Boole used symbols such as p, q, r, and s to represent simple statements.
Examples of propositions:
p: Today is Friday.
q: It is not a multimedia authoring tool.
r: I am enrolled to distance education.
Examples of non-propositions:
1. 2 plus y equals 10.
2. Attend the asynchronous classes.
Operations on Propositions and Truth Value
The symbols ¬, ∧, ⊕, ∨, →, ↔ are logical operators. Applying any of these operations form a compound proposition.
TRUTH VALUE AND TRUTH TABLE
The truth value of a simple statement is either true (T or 1) or false (F or 0). The truth value of a compound statement depends on the truth values of its simple statements and its connectives. A truth table is a table that shows the truth value of a compound statement for all possible truth values of its simple statements.
Table 2: Truth table with logical connectives
p | q | p ∧ q | p ∨ q | p ⊕ q | p → q | p ↔ q |
T | T | T | T | F | T | T |
T | F | F | T | T | F | F |
F | T | F | T | T | T | F |
F | F | F | F | F | T | T |
LOGICAL EQUIVALENCE
Two statements are equivalent if they both have the same truth value for all possible truth values of their simple statements. The notation p ≡ q is used to indicate that the statements p and q are equivalent.
TAUTOLOGY, CONTRADICTION AND CONTINGENCY
A compound proposition that is always true, no matter what the truth values of the propositions that occur in it, is called a tautology. A compound proposition is called contradiction if it is always false. It is contingency if a compound proposition is neither a tautology nor a contradiction.
Example: Use a truth table to determine whether the given statement is a tautology, contradiction or contingency.
(p ∧ q) ∨ (p → ¬ q)
The table shows that (p ∧ q) ∨ (p → ¬ q) is always true. Thus (p ∧ q) ∨ (p → ¬ q) is a tautology.
(p ∧ q) ∧ (¬ r∨ q)
The table shows that (p ∧ q) ∧ (¬ r∨ q) is a combination of true and false. Thus (p ∧ q) ∧ (¬ r∨ q) is a contingency.
Table 3 Logical Equivalences
ARGUMENT AND IT'S VALIDITY
An argument consists of statements called premises and another statement called the conclusion. It is valid if the conclusion is true whenever all the premises are assumed to be true and invalid if it is not a valid argument.
Arguments can be written in symbolic form.
Truth Table Procedure to Determine the Validity of an Argument
Write the argument in symbolic form.
Construct a truth table for all combinations of truth values of the simple statements.
Validity of the argument:
3.a. Valid argument: The conclusion is true in every row of the truth table in which all the premises are true.
3.b. Invalid argument: The conclusion is false in any row in which all of the premises are true.
Example: Use a truth table the determine the validity of the argument.
Row 3 is the only row in which all the premises are true, so it is the only row that we examine. Because the conclusion is true in row 3, the argument is valid.
PREDICATE LOGIC AND QUANTIFIERS
A predicate (P(x)) is a statement that contains a variable. The value of the variable is a proposition. Universe of discourse or domain of the variable (U) is a specific set of values for the variable.
Predicates in a similar way to functions and considered a function, P: U → {0, 1}, where 1 represents truth, and 0 represents falsehood.
A predicate may have more than one variable, in which case we speak of predicates in two variables, three variables, and so on, denoted as Q(x, y), S(x, y, z), etc.
Examples:
P (x): x ≥ 2 for x ∈ R (for any real value of x, this statement is either true or false)
Q (x, y): x + y = 4 for x ∈ R
QUANTIFIERS
Given a predicate P (x) that is defined for all elements in a set A, P(x) is true for all x ∈ A, or if it’s at least true for some x ∈ A. Propositions are stated to this effect using the universal quantifier ∀ and the existential quantifier ∃.
Write as English sentences and determine whether they are true or false.
∀x ∈ R, ∃y ∈ R, x + y = 10
∀x ∈ Z+, ∃y ∈ R, y2 = x
Review for the quiz.
A. Complete the table then determine the validity of the argument. Use the space provided for your answers.
