Propositional Logic
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
January 14, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 1 / 20
1 Basics of Propositional Logic
2 Conditional Statements
3 Compound Propositions
4 Propositional Equivalences
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 2 / 20
Propositional Logic
Proposition
A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.
Examples
– Ottawa is the capital of Canada (True) – 9 × 3 = 17 (False)
These are not propositions:
– How are you? (Not declarative)
– Please solve the problem. (Not declarative) – x + y = z (Could be True or False ..)
– x + 9 = 11 (Could be True or False ..)
Propositional or Sentential Variables
Letters that represents propositions, just as letters are used to denote numerical variables.
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 3 / 20
Propositional Logic (cont.)
The truth value of a proposition can be true (T) or false (F).
Propositions that cannot be expressed in terms of simpler propositions
are called atomic propositions.
Many mathematical propositions are constructed by combining one or more propositions. Compound propositions are formed from existing propositions using logical operators.
The negation of a proposition p is denoted by ¬p (not p).
-(proposition) I eat rice.
-(negation of the proposition) I do not eat rice.
The negation operator works on a single proposition.
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 4 / 20
Propositional Logic (cont.)
The logical operators that work on two or more propositions to form new propositions are called connectives.
Conjunction (AND): p ∧ q is also read as p AND q
– p ∧ q is true when both p and q are true and is false otherwise.
Disjunction (Inclusive OR): p ∨ q is also read as p OR q
– p ∨ q is false when both p and q are false and is true otherwise.
Exclusive OR: p⊕q is also read as p XOR q
– p⊕q is true when exactly one of p and q is true and is false otherwise.
Truth tables are used to summarize all the possible combinations of truth values for a given statement.
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 5 / 20
Propositional Logic (cont.)
Table: Truth Table for conjunction (p ∧ q)
Table: Truth Table for disjunction (p ∨ q)
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 6 / 20
Propositional Logic (cont.)
Table: Truth Table for exclusive OR (p ⊕ q)
Truth tables are useful in proving logical equivalence between compound propositions. It takes 2N rows in a truth table to verify statements with N propositional variables.
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 7 / 20
Logical Implication
Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q”.
– The conditional statement p → q is false when p is true and q is false, and true otherwise.
– p is called the hypothesis (or antecedent or premise)
– q is called the conclusion (or consequence)
Table: Truth Table for p → q
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 8 / 20
Logical Implication (cont.)
There are many ways to state p → q, such as
– p implies q – p only if q – q unless ¬p
The implication of p → q can be confusing due to the different linguistic expressions. To avoid the confusion an obligation can be set:
– p cannot be true unless q is true. Thus, p → q is false when p is true but q is false.
– If you get 100% in the final (p), then you will get an A (q).
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 9 / 20
Logical Implication (cont.)
Converse
– The proposition q → p is called the converse of p → q
Contrapositive
– The contrapositive of p → q is the proposition ¬q → ¬p.
– Only the contrapositive always has the same truth value as p → q. Inverse
– The proposition ¬p → ¬q is called the inverse of p → q. Equivalent
– When two compound propositions always have the same truth values, regardless of the truth values of its propositional variables, they are called equivalent.
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 10 / 20
Logical Implication (cont.)
A conditional statement and its contrapositive are equivalent
The converse and the inverse of a conditional statement are also
equivalent
Biconditionals
The biconditional statement p ↔ q is the proposition “p if and only if q”.
It is true when p and q have the same truth values, and is false otherwise. p ↔ q has exactly the same truth value as (p → q) ∧ (q → p).
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 11 / 20
Compound Propositions
There are two ways to determine the truth values of compound propositions: (i) by constructing truth tables and (ii) by applying established logical laws.
The truth table of (p ∨ ¬q) → (p ∧ q):
Table: Truth Table of (p ∨ ¬q) → (p ∧ q)
(p ∨ ¬q) → (p ∧ q
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 12 / 20
Compound Propositions (cont.)
Compound propositions are constructed using the negation operator and the logical operators. Parentheses are used to specify the order of logical operations. However, the rule of precedence of logical operators can reduce the number of parentheses.
Table: Precedence of Logical Operators
Precedence
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 13 / 20
Propositional Equivalences
Tautology
A compound proposition that is always true, no matter the truth values of
the propositional variables that occur in it, called a tautology.
Contradiction
A compound proposition that is always false is called contradiction.
Contingency
A compound proposition that is neither a tautology nor a contradiction is
called a contingency.
Satisfiability
A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true (that is, when it is a tautology or a contingency).
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 14 / 20
Propositional Equivalences (cont.)
De Morgan’s Laws ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
Extended Version of De Morgan’s Laws ¬(∧Ni=1pi ) ≡ ∨Ni=1¬pi
¬(∨Ni=1pi ) ≡ ∧Ni=1¬pi
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 15 / 20
Logical Equivalences
Table: Logical Equivalences
Equivalence
p∧T≡p p∨F≡p
Identity laws
p∨T≡T p∧F≡F
Domination laws
p∨p≡p p∧p≡p
Idempotent laws
Double negation law
p∨q≡q∨p p∧q≡q∧p
Commutative laws
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Associative laws
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 16 / 20
Logical Equivalences (cont.)
Table: Logical Equivalences (cont.)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Distributive laws
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
De Morgan laws
p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
Absorption laws
p ∨ ¬p ≡ T p ∧ ¬p ≡ F
Negation laws
Also check the tables of Logical Equivalence Involving Conditional Statements and Logical Equivalence Involving Biconditional Statements in the textbook.
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 17 / 20
Logical Equivalences (cont.)
In-class Exercise#1
Show that ¬(p → q) and p ∧ ¬q are logically equivalent.
Solution
Method#1 (using the truth table)
Table: Truth Table
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 18 / 20
Logical Equivalences (cont.)
Method#2 (using established laws)
≡ ¬(¬p ∨ q) Using disjunction equivalence ≡ ¬(¬p) ∧ ¬q De Morgan’s Law
≡ p ∧ ¬q Double negation Law
In-class Exercise#2
Show that (p ∧ q) → (p ∨ q) is a tautology.
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 19 / 20
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 1b MdH W22 January 14, 2022 20 / 20
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com